Question

一道算法题，要求用c++写

要求用遗传算法或者其他非暴力算法解。求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间[0,9]的最大值。要求结果保留到小数点后6位

Answer 1

如图

一开始就有点在最值附近了，但是还有“残余势力”在远离最值的地方。

最后误差居然消除了！总共耗时不到1s。

由于代码过长，只展示一部分，提供思路，具体代码请私聊发：

typedef unsigned int UINT32;
typedef unsigned short UINT16;
#define FOR_ITER(iter,object) for (auto (iter) = (object).begin(); (iter) != (object).end(); (iter)++)
class Random {
private:
	static bool init;
public:
	Random() {
		if (!init) {
			srand((int)time(0)); init= true;
		}
	}	//初始化随机数种子
//	static int rand() { return rand(); }
	static double rand_df(const double &a=0, const double &b=1);
	static UINT32 randUINT();
};
bool Random::init = false;
double Random::rand_df(const double & a, const double & b) {
	return a + (b - a)*rand() / RAND_MAX;
}
UINT32 Random::randUINT(){
	return UINT32(((rand() % 0x10000) << 16) | (rand() % 0x10000));
}

class GrayCode {
private:
	static bool init;
	static unsigned char gray2bi[512];	//查表法格雷码转二进制(0~255)第9位是进位标志
public:
	GrayCode() {
		if (!init) 
			for (UINT32 bi = 0; bi < 512; bi++)
				gray2bi[toGray(bi)] = bi%256;
	}
	//二进制转格雷码
	static UINT32 toGray(const UINT32 & bi) {	
		return bi ^ (bi >> 1);
	}	
	//格雷码转二进制★(难)
	static UINT32 toBi(const UINT32 &gray) {	
		int shift = 24;
		UINT32	bi=0;
		while (true) {				//从gray高位到低位转换
			bi |= gray2bi[			//bi的最低位作为查表的进位标志
				(bi | ((gray >> shift) & 0xff))%512];	
			if(shift>0){
				bi <<= 8;	shift -= 8;
			}else break;
		}
		return bi;
	}
	//输出为二进制字符。
	static void printBi(const int &num) {
		for (UINT32 p = 0x80000000,count=8; p != 0; p >>= 1){
			if (num&p)	putchar('1');
			else		putchar('0');
			if (--count == 0) {
				putchar(' '); count = 8;
			}
		}
	}
};
bool GrayCode::init = false;
unsigned char GrayCode::gray2bi[512];


//遗传算法 求最值
class Individuality:Random, GrayCode {
private:
	static UINT32 mutation_factor[32];	//突变因子 {1,2,4,8,16,...}
	static bool init;

	UINT32 gene;			//基因(格雷码)
	UINT32 transgenation_2();	//基因突变（非均匀，暂时弃用）

	//求解函数值
	double f() {
		double x = get_x();
		return x + 10 * sin(5 * x) + 7 * cos(4 * x);//★用户自定义，求解的函数 。
	}
	double y;	//y值（生成gene马上计算）
public:
	Individuality();
	Individuality(const UINT32 &gene) :gene(gene),y(f()) {}
	Individuality(const Individuality &a, const Individuality &b);	//交叉繁殖产生后代

	Individuality transgenation();	//均匀基因突变1位
	double get_y() { return y; }
	double adaptability;			//预留给用户自定义
	//gene(格雷码要先转二进制)映射到区间[0,9]的数
	double get_x() {
		return (double)toBi(gene) * ((double)9 / 0xffffffff);
	}
	static bool cmp_y(const Individuality &a, const Individuality &b) {
		return a.y < b.y;
	}
};
bool Individuality::init = false;
UINT32 Individuality::mutation_factor[32];
typedef vector<Individuality>::iterator Idv_Iter;


class Natrue {
private:
	vector<Individuality> idvs;	//个体集合
	int generation=0;		//代 0为初代
	int max_num;		// max_num÷num-1为繁殖率
	int num;			// 每一代总群数量控制
	//适应度函数（须具体问题具体定义），非负即可，可以不归一化，值为0代表必被淘汰
	void calculate_adaptability();
	int statistics_generation = -1;
	double error;
	pair<Idv_Iter, Idv_Iter> min_max_idv;
	//线程与安全
	bool wooking = false;
	Natrue();			//禁用默认构造
public:
	//初始化产生num个随机个体
	Natrue(int num,int max_num):num(num), max_num(max_num){
		idvs.reserve(max_num);
		idvs.resize(num);	//用默认构造num个。
	}
	//随机交叉繁殖（基因突变概率）；
	void reproduce(double GM_Probability);
	//轮盘赌选择
	void roulette_wheel_selection();
	//统计结果
	void statistics_y(double &min_y);

//	void statistics_y(Individuality *&min_y, Individuality *&max_y);
	double& get_error();
	const Idv_Iter get_max_idv();
	int get_generation() {return generation;}
};	


int main()
{

	Natrue s(50,100);
	for (int i = 100; i > 0;i--){
		s.reproduce(0.3);
		s.roulette_wheel_selection();
		printf("第%d代\n", s.get_generation());
		printf("error=%e\t", s.get_error());
		printf("x=%lf\ty= %lf\n", s.get_max_idv()->get_x(),s.get_max_idv()->get_y() );
	}
	
	system("pause");
	return 0;
}