一、实验目的:
理解和掌握遗传算法的应用及意义,能用一门自己擅长的语言实现遗传算法的基本功能,在此基础上进一步理解和巩固对遗传算法的重要,以便在今后的学习和工作中能有效的运用和借鉴!需要指出的是遗传算法并不是能保证所得到的就是最佳的答案但通过一定的方法可以将误差控制在一定的范围内!
二、实验原理和题目:
1.遗传算法是一种基于空间搜索的算法,它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论,模拟自然进化过程来寻找所求问题的答案。其求解过程是个最优化的过程。一般遗传算法的主要步骤如下:
(1)随机产生一个确定长度的特征字符串组成的初始种群。
(2)对该字符串种群迭代地执行下面的步骤a和步骤b,直到满足停止准则为止:
a计算种群中每个个体字符串的适应值;
b应用复制、交叉和变异等遗传算子产生下一代种群。
(3)把在后代中表现的最好的个体字符串指定为遗传算法的执行结果,即为问题的一个解。
2.通过编码、设置种群、设置适应度函数、遗传操作、解码产生需要的解。
f(x)=x*sin(x)+1, x[0,2],求解f(x)的最大值和最小值。
三、实验条件
硬件:微型计算机。
语言:本实验选用的为C++语言。
四、实验内容:
建造针对f(x)的遗传算法程序,然后进行运行求解。
五、实验步骤:
1. 确定基本功能:本实验是实现f(x)的最大值和最小值的求解。
2. 对f(x)进行编码:用一个二进制矢量表示一个染色体,由染色体来代表变量x的实数值,这里精度取小数点后6位数,变量x的域长为2,整个区间被分为2*1000000个等长的区间。由于2*1000000在23位二进制数的表示范围呢,所以,编码长度为23位。
3. 设计适应度函数:由于要求f(x)的最值,所以适应度函数可根据f(x)做适当的改变。最大值:f(x)=x*sin(x)+5;最小值:f(x)=1/(x*sin(x)+5 );
4. 针对f(x)的设计并且实现遗传算法程序:遗传操作主要包括复制、交叉和变异。复制是直接将父代遗传给子代,即根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。交叉从能进入下一代的个体中选出两个,将两者的部分码值进行交换。变异是根据变异概率选出一个个体,随机对其某位编码进行改变。复制由void Selection_operation(bool flag);实现;交叉由void Crossover_operation();实现;变异由void Mution-operation();实现。
5. 设计初始种群:默认设置为50个随机产生的23位字节的染色体。
6. 调试交叉和变异概率:在常用的交叉和变异概率范围内,结果随交叉和变异的概率的改变而改变,之间差异相对来说不太明显
7. 实验参数:实验中主要的参数有遗传代数、群体规模、交叉概率、变异概率。
实验结果:
求最大值:
求最小值:
程序主要代码如下(后台代码):
class GA{
vector
vector
double Pc;
double Pm;
int Num_Iteration;
int Num_Population;
double Optimal_Max_X_Solution;
double Optimal_Min_X_Solution;
double Optimal_Max_Function_Vlaue;
double Optimal_Min_Function_Value;
string Optimal_Individual;
vector
ength()-1;i>=0;--i){
t=t*2;
DecNum1+=((*iter)[i]-48)*t;
}
DecNum1=DecNum1*((2*PI)/ValueOfString);
//cout< double Temp=Function(DecNum1);// 求函数值 //cout< if(flag){ // find the maximum if(Temp>Optimal_Max_Function_Vlaue){ Optimal_Max_Function_Vlaue=Temp; Optimal_Max_X_Solution=DecNum1; Optimal_Individual=*iter; //fitness=Temp+5; } } else{ //find the minimum if(Temp Optimal_Min_Function_Value=Temp; Optimal_Min_X_Solution=DecNum1; Optimal_Individual=*iter; //fitness=Temp+5; } } } } //Initialize the Populations void GA::GA_Init(){ for(int ixx=0;ixx string STRing; for(int i=0;i<23;i++){ int rnd=rand()%2; (rnd+48); } (STRing); (); } //for(vector // cout<<*iter< //} } //Select Operation void GA::Select_Operation(){ //随机选择个体 double rnd=*(rand()%10000); for(vector if(rnd<=*iter){ (*()+()))); //cout<<*()+()))< break; } } } //Crossover Operation void GA::Crossover_Operation(){ //随机选择两个个体进行交叉操作 double rnd=*(rand()%10000); for(vector if(rnd<=*iter){ string STRing=*()+())); double rnd1=*(rand()%10000); for(vector if(rnd1<=*iter1){ string STRing1=*()+())); int rnd2=rand()%23; char Temp; for(int i=rnd2;i<();++i){ Temp=STRing[i]; STRing[i]=STRing1[i]; STRing1[i]=Temp; } (STRing); (STRing1); break; } } break; } } } //Mutation Operation void GA::Mutation_Operation(){ //选择个体进行突变操作 double rnd=*(rand()%10000); for(vector string STRing=*()+())); int rnd1=rand()%23; if(STRing[rnd1]=='0'){ STRing[rnd1]='1'; } else{ STRing[rnd1]='0'; } (STRing); break; } } //cout<<"Mutation"< } //Evaluation Operation void GA::Evaluation(bool flag){ srand(time(NULL)); (); GA_Init(); Extreme_Value(flag); Display(flag,0); /*srand(time(NULL));*/ for(int i=1;i<=Num_Iteration;++i){ LunPan_Operation(flag); //for(vector // cout<<*iter< //} for(int j=0;j /*srand(time(NULL));*/ double rnd=*(rand()%10000); //cout< if(rnd Mutation_Operation(); //cout<<"Mutation"< } else{ if(rnd<(Pc+Pm)){ ++j; Crossover_Operation(); //cout<<"Crossover"< } else{ Select_Operation(); //cout<<"Selection"< } } } //for(vector // cout<<*iter< //} //cout< //cout< for(vector } //for(vector // cout<<*iter< //} (); (); Extreme_Value(flag); Display(flag,i); } if(flag){ cout<<"Maxmum: "< } else{ cout<<"Minimum: "< } }