本文实例讲述了C++实现简单遗传算法。分享给大家供大家参考。具体实现方法如下：
// CMVSOGA.h : main header file for the CMVSOGA.cpp //////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////// #if !defined(AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767__INCLUDED_) #define AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767__INCLUDED_ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #include "Afxtempl.h" #define variablenum 14 class CMVSOGA { public: CMVSOGA(); ~CMVSOGA(); void selectionoperator(); void crossoveroperator(); void mutationoperator(); void initialpopulation(int, int ,double ,double,double *,double *); //种群初始化 void generatenextpopulation(); //生成下一代种群 void evaluatepopulation(); //评价个体，求最佳个体 void calculateobjectvalue(); //计算目标函数值 void calculatefitnessvalue(); //计算适应度函数值 void findbestandworstindividual(); //寻找最佳个体和最差个体 void performevolution(); void GetResult(double *); void GetPopData(CList <double,double>&); void SetFitnessData(CList <double,double>&,CList <double,double>&,CList <double,double>&); private: struct individual { double chromosome[variablenum]; //染色体编码长度应该为变量的个数 double value; double fitness; //适应度 }; double variabletop[variablenum]; //变量值 double variablebottom[variablenum]; //变量值 int popsize; //种群大小 // int generation; //世代数 int best_index; int worst_index; double crossoverrate; //交叉率 double mutationrate; //变异率 int maxgeneration; //最大世代数 struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual current; //当前个体 struct individual current1; //当前个体 struct individual currentbest; //当前最佳个体 CList <struct individual,struct individual &> population; //种群 CList <struct individual,struct individual &> newpopulation; //新种群 CList <double,double> cfitness; //存储适应度值 //怎样使链表的数据是一个结构体????主要是想把种群作成链表。节省空间。 }; #endif 执行文件： // CMVSOGA.cpp : implementation file // #include "stdafx.h" //#include "vld.h" #include "CMVSOGA.h" #include "math.h" #include "stdlib.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// // CMVSOGA.cpp CMVSOGA::CMVSOGA() { best_index=0; worst_index=0; crossoverrate=0; //交叉率 mutationrate=0; //变异率 maxgeneration=0; } CMVSOGA::~CMVSOGA() { best_index=0; worst_index=0; crossoverrate=0; //交叉率 mutationrate=0; //变异率 maxgeneration=0; population.RemoveAll(); //种群 newpopulation.RemoveAll(); //新种群 cfitness.RemoveAll(); } void CMVSOGA::initialpopulation(int ps, int gen ,double cr ,double mr,double *xtop,double *xbottom) //第一步，初始化。 { //应该采用一定的策略来保证遗传算法的初始化合理，采用产生正态分布随机数初始化？选定中心点为多少？ int i,j; popsize=ps; maxgeneration=gen; crossoverrate=cr; mutationrate =mr; for (i=0;i<variablenum;i++) { variabletop[i] =xtop[i]; variablebottom[i] =xbottom[i]; } //srand( (unsigned)time( NULL ) ); //寻找一个真正的随机数生成函数。 for(i=0;i<popsize;i++) { for (j=0;j<variablenum ;j++) { current.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j]; } current.fitness=0; current.value=0; population.InsertAfter(population.FindIndex(i),current);//除了初始化使用insertafter外,其他的用setat命令。 } } void CMVSOGA::generatenextpopulation()//第三步，生成下一代。 { //srand( (unsigned)time( NULL ) ); selectionoperator(); crossoveroperator(); mutationoperator(); } //void CMVSOGA::evaluatepopulation() //第二步，评价个体，求最佳个体 //{ // calculateobjectvalue(); // calculatefitnessvalue(); //在此步中因该按适应度值进行排序.链表的排序. // findbestandworstindividual(); //} void CMVSOGA:: calculateobjectvalue() //计算函数值，应该由外部函数实现。主要因为目标函数很复杂。 { int i,j; double x[variablenum]; for (i=0; i<popsize; i++) { current=population.GetAt(population.FindIndex(i)); current.value=0; //使用外部函数进行，在此只做结果的传递。 for (j=0;j<variablenum;j++) { x[j]=current.chromosome[j]; current.value=current.value+(j+1)*pow(x[j],4); } ////使用外部函数进行，在此只做结果的传递。 population.SetAt(population.FindIndex(i),current); } } void CMVSOGA::mutationoperator() //对于浮点数编码，变异算子的选择具有决定意义。 //需要guass正态分布函数，生成方差为sigma，均值为浮点数编码值c。 { // srand((unsigned int) time (NULL)); int i,j; double r1,r2,p,sigma;//sigma高斯变异参数 for (i=0;i<popsize;i++) { current=population.GetAt(population.FindIndex(i)); //生成均值为current.chromosome，方差为sigma的高斯分布数 for(j=0; j<variablenum; j++) { r1 = double(rand()%10001)/10000; r2 = double(rand()%10001)/10000; p = double(rand()%10000)/10000; if(p<mutationrate) { double sign; sign=rand()%2; sigma=0.01*(variabletop[j]-variablebottom [j]); //高斯变异 if(sign) { current.chromosome[j] = (current.chromosome[j] + sigma*sqrt(-2*log(r1)/0.4323)*sin(2*3.1415926*r2)); } else { current.chromosome[j] = (current.chromosome[j] - sigma*sqrt(-2*log(r1)/0.4323)*sin(2*3.1415926*r2)); } if (current.chromosome[j]>variabletop[j]) { current.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j]; } if (current.chromosome[j]<variablebottom [j]) { current.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j]; } } } population.SetAt(population.FindIndex(i),current); } } void CMVSOGA::selectionoperator() //从当前个体中按概率选择新种群,应该加一个复制选择,提高种群的平均适应度 { int i,j,pindex=0; double p,pc,sum; i=0; j=0; pindex=0; p=0; pc=0; sum=0.001; newpopulation.RemoveAll(); cfitness.RemoveAll(); //链表排序 // population.SetAt (population.FindIndex(0),current); //多余代码 for (i=1;i<popsize;i++) { current=population.GetAt(population.FindIndex(i)); for(j=0;j<i;j++) //从小到大用before排列。 { current1=population.GetAt(population.FindIndex(j));//临时借用变量 if(current.fitness<=current1.fitness) { population.InsertBefore(population.FindIndex(j),current); population.RemoveAt(population.FindIndex(i+1)); break; } } // m=population.GetCount(); } //链表排序 for(i=0;i<popsize;i++)//求适应度总值，以便归一化,是已经排序好的链。 { current=population.GetAt(population.FindIndex(i)); //取出来的值出现问题. sum+=current.fitness; } for(i=0;i<popsize; i++)//归一化 { current=population.GetAt(population.FindIndex(i)); //population 有值,为什么取出来的不正确呢?? current.fitness=current.fitness/sum; cfitness.InsertAfter (cfitness .FindIndex(i),current.fitness); } for(i=1;i<popsize; i++)//概率值从小到大; { current.fitness=cfitness.GetAt (cfitness.FindIndex(i-1)) +cfitness.GetAt(cfitness.FindIndex(i)); //归一化 cfitness.SetAt (cfitness .FindIndex(i),current.fitness); population.SetAt(population.FindIndex(i),current); } for (i=0;i<popsize;)//轮盘赌概率选择。本段还有问题。 { p=double(rand()%999)/1000+0.0001; //随机生成概率 pindex=0; //遍历索引 pc=cfitness.GetAt(cfitness.FindIndex(1)); //为什么取不到数值???20060910 while(p>=pc&&pindex<popsize) //问题所在。 { pc=cfitness.GetAt(cfitness .FindIndex(pindex)); pindex++; } //必须是从index~popsize，选择高概率的数。即大于概率p的数应该被选择，选择不满则进行下次选择。 for (j=popsize-1;j<pindex&&i<popsize;j--) { newpopulation.InsertAfter (newpopulation.FindIndex(0), population.GetAt (population.FindIndex(j))); i++; } } for(i=0;i<popsize; i++) { population.SetAt (population.FindIndex(i), newpopulation.GetAt (newpopulation.FindIndex(i))); } // j=newpopulation.GetCount(); // j=population.GetCount(); newpopulation.RemoveAll(); } //current 变化后，以上没有问题了。 void CMVSOGA:: crossoveroperator() //非均匀算术线性交叉，浮点数适用,alpha ,beta是(0，1)之间的随机数 //对种群中两两交叉的个体选择也是随机选择的。也可取beta=1-alpha; //current的变化会有一些改变。 { int i,j; double alpha,beta; CList <int,int> index; int point,temp; double p; // srand( (unsigned)time( NULL ) ); for (i=0;i<popsize;i++)//生成序号 { index.InsertAfter (index.FindIndex(i),i); } for (i=0;i<popsize;i++)//打乱序号 { point=rand()%(popsize-1); temp=index.GetAt(index.FindIndex(i)); index.SetAt(index.FindIndex(i), index.GetAt(index.FindIndex(point))); index.SetAt(index.FindIndex(point),temp); } for (i=0;i<popsize-1;i+=2) {//按顺序序号,按序号选择两个母体进行交叉操作。 p=double(rand()%10000)/10000.0; if (p<crossoverrate) { alpha=double(rand()%10000)/10000.0; beta=double(rand()%10000)/10000.0; current=population.GetAt(population.FindIndex(index.GetAt(index.FindIndex(i)))); current1=population.GetAt(population.FindIndex(index.GetAt(index.FindIndex(i+1))));//临时使用current1代替 for(j=0;j<variablenum;j++) { //交叉 double sign; sign=rand()%2; if(sign) { current.chromosome[j]=(1-alpha)*current.chromosome[j]+ beta*current1.chromosome[j]; } else { current.chromosome[j]=(1-alpha)*current.chromosome[j]- beta*current1.chromosome[j]; } if (current.chromosome[j]>variabletop[j]) //判断是否超界. { current.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j]; } if (current.chromosome[j]<variablebottom [j]) { current.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j]; } if(sign) { current1.chromosome[j]=alpha*current.chromosome[j]+ (1- beta)*current1.chromosome[j]; } else { current1.chromosome[j]=alpha*current.chromosome[j]- (1- beta)*current1.chromosome[j]; } if (current1.chromosome[j]>variabletop[j]) { current1.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j]; } if (current1.chromosome[j]<variablebottom [j]) { current1.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j]; } } //回代 } newpopulation.InsertAfter (newpopulation.FindIndex(i),current); newpopulation.InsertAfter (newpopulation.FindIndex(i),current1); } ASSERT(newpopulation.GetCount()==popsize); for (i=0;i<popsize;i++) { population.SetAt (population.FindIndex(i), newpopulation.GetAt (newpopulation.FindIndex(i))); } newpopulation.RemoveAll(); index.RemoveAll(); } void CMVSOGA:: findbestandworstindividual( ) { int i; bestindividual=population.GetAt(population.FindIndex(best_index)); worstindividual=population.GetAt(population.FindIndex(worst_index)); for (i=1;i<popsize; i++) { current=population.GetAt(population.FindIndex(i)); if (current.fitness>bestindividual.fitness) { bestindividual=current; best_index=i; } else if (current.fitness<worstindividual.fitness) { worstindividual=current; worst_index=i; } } population.SetAt(population.FindIndex(worst_index), population.GetAt(population.FindIndex(best_index))); //用最好的替代最差的。 if (maxgeneration==0) { currentbest=bestindividual; } else { if(bestindividual.fitness>=currentbest.fitness) { currentbest=bestindividual; } } } void CMVSOGA:: calculatefitnessvalue() //适应度函数值计算，关键是适应度函数的设计 //current变化，这段程序变化较大，特别是排序。 { int i; double temp;//alpha,beta;//适应度函数的尺度变化系数 double cmax=100; for(i=0;i<popsize;i++) { current=population.GetAt(population.FindIndex(i)); if(current.value<cmax) { temp=cmax-current.value; } else { temp=0.0; } /* if((population[i].value+cmin)>0.0) {temp=cmin+population[i].value;} else {temp=0.0; } */ current.fitness=temp; population.SetAt(population.FindIndex(i),current); } } void CMVSOGA:: performevolution() //演示评价结果,有冗余代码,current变化，程序应该改变较大 { if (bestindividual.fitness>currentbest.fitness) { currentbest=population.GetAt(population.FindIndex(best_index)); } else { population.SetAt(population.FindIndex(worst_index),currentbest); } } void CMVSOGA::GetResult(double *Result) { int i; for (i=0;i<variablenum;i++) { Result[i]=currentbest.chromosome[i]; } Result[i]=currentbest.value; } void CMVSOGA::GetPopData(CList <double,double>&PopData) { PopData.RemoveAll(); int i,j; for (i=0;i<popsize;i++) { current=population.GetAt(population.FindIndex(i)); for (j=0;j<variablenum;j++) { PopData.AddTail(current.chromosome[j]); } } } void CMVSOGA::SetFitnessData(CList <double,double>&PopData,CList <double,double>&FitnessData,CList <double,double>&ValueData) { int i,j; for (i=0;i<popsize;i++) { current=population.GetAt(population.FindIndex(i)); //就因为这一句，出现了很大的问题。 for (j=0;j<variablenum;j++) { current.chromosome[j]=PopData.GetAt(PopData.FindIndex(i*variablenum+j)); } current.fitness=FitnessData.GetAt(FitnessData.FindIndex(i)); current.value=ValueData.GetAt(ValueData.FindIndex(i)); population.SetAt(population.FindIndex(i),current); } FitnessData.RemoveAll(); PopData.RemoveAll(); ValueData.RemoveAll(); } # re: C++遗传算法源程序 /******************************************************************** Filename: aiWorld.h Purpose: 遗传算法，花朵演化。 Id: Copyright: Licence: *********************************************************************/ #ifndef AIWORLD_H_ #define AIWORLD_H_ #include <iostream> #include <ctime> #include <cstdlib> #include <cmath> #define kMaxFlowers 10 using std::cout; using std::endl; class ai_World { public: ai_World() { srand(time(0)); } ~ai_World() {} int temperature[kMaxFlowers]; //温度 int water[kMaxFlowers]; //水质 int sunlight[kMaxFlowers]; //阳光 int nutrient[kMaxFlowers]; //养分 int beneficialInsect[kMaxFlowers]; //益虫 int harmfulInsect[kMaxFlowers]; //害虫 int currentTemperature; int currentWater; int currentSunlight; int currentNutrient; int currentBeneficialInsect; int currentHarmfulInsect; /** 第一代花朵 */ void Encode(); /** 花朵适合函数 */ int Fitness(int flower); /** 花朵演化 */ void Evolve(); /** 返回区间[start, end]的随机数 */ inline int tb_Rnd(int start, int end) { if (start > end) return 0; else { //srand(time(0)); return (rand() % (end + 1) + start); } } /** 显示数值 */ void show(); }; // ----------------------------------------------------------------- // void ai_World::Encode() // ----------------------------------------------------------------- // { int i; for (i=0;i<kMaxFlowers;i++) { temperature[i]=tb_Rnd(1,75); water[i]=tb_Rnd(1,75); sunlight[i]=tb_Rnd(1,75); nutrient[i]=tb_Rnd(1,75); beneficialInsect[i]=tb_Rnd(1,75); harmfulInsect[i]=tb_Rnd(1,75); } currentTemperature=tb_Rnd(1,75); currentWater=tb_Rnd(1,75); currentSunlight=tb_Rnd(1,75); currentNutrient=tb_Rnd(1,75); currentBeneficialInsect=tb_Rnd(1,75); currentHarmfulInsect=tb_Rnd(1,75); currentTemperature=tb_Rnd(1,75); currentWater=tb_Rnd(1,75); currentSunlight=tb_Rnd(1,75); currentNutrient=tb_Rnd(1,75); currentBeneficialInsect=tb_Rnd(1,75); currentHarmfulInsect=tb_Rnd(1,75); } // ----------------------------------------------------------------- // int ai_World::Fitness(int flower) // ----------------------------------------------------------------- // { int theFitness; theFitness=abs(temperature[flower]-currentTemperature); theFitness=theFitness+abs(water[flower]-currentWater); theFitness=theFitness+abs(sunlight[flower]-currentSunlight); theFitness=theFitness+abs(nutrient[flower]-currentNutrient); theFitness=theFitness+abs(beneficialInsect[flower]-currentBeneficialInsect); theFitness=theFitness+abs(harmfulInsect[flower]-currentHarmfulInsect); return (theFitness); } // ----------------------------------------------------------------- // void ai_World::Evolve() // ----------------------------------------------------------------- // { int fitTemperature[kMaxFlowers]; int fitWater[kMaxFlowers]; int fitSunlight[kMaxFlowers]; int fitNutrient[kMaxFlowers]; int fitBeneficialInsect[kMaxFlowers]; int fitHarmfulInsect[kMaxFlowers]; int fitness[kMaxFlowers]; int i; int leastFit=0; int leastFitIndex; for (i=0;i<kMaxFlowers;i++) if (Fitness(i)>leastFit) { leastFit=Fitness(i); leastFitIndex=i; } temperature[leastFitIndex]=temperature[tb_Rnd(0,kMaxFlowers - 1)]; water[leastFitIndex]=water[tb_Rnd(0,kMaxFlowers - 1)]; sunlight[leastFitIndex]=sunlight[tb_Rnd(0,kMaxFlowers - 1)]; nutrient[leastFitIndex]=nutrient[tb_Rnd(0,kMaxFlowers - 1)]; beneficialInsect[leastFitIndex]=beneficialInsect[tb_Rnd(0,kMaxFlowers - 1)]; harmfulInsect[leastFitIndex]=harmfulInsect[tb_Rnd(0,kMaxFlowers - 1)]; for (i=0;i<kMaxFlowers;i++) { fitTemperature[i]=temperature[tb_Rnd(0,kMaxFlowers - 1)]; fitWater[i]=water[tb_Rnd(0,kMaxFlowers - 1)]; fitSunlight[i]=sunlight[tb_Rnd(0,kMaxFlowers - 1)]; fitNutrient[i]=nutrient[tb_Rnd(0,kMaxFlowers - 1)]; fitBeneficialInsect[i]=beneficialInsect[tb_Rnd(0,kMaxFlowers - 1)]; fitHarmfulInsect[i]=harmfulInsect[tb_Rnd(0,kMaxFlowers - 1)]; } for (i=0;i<kMaxFlowers;i++) { temperature[i]=fitTemperature[i]; water[i]=fitWater[i]; sunlight[i]=fitSunlight[i]; nutrient[i]=fitNutrient[i]; beneficialInsect[i]=fitBeneficialInsect[i]; harmfulInsect[i]=fitHarmfulInsect[i]; } for (i=0;i<kMaxFlowers;i++) { if (tb_Rnd(1,100)==1) temperature[i]=tb_Rnd(1,75); if (tb_Rnd(1,100)==1) water[i]=tb_Rnd(1,75); if (tb_Rnd(1,100)==1) sunlight[i]=tb_Rnd(1,75); if (tb_Rnd(1,100)==1) nutrient[i]=tb_Rnd(1,75); if (tb_Rnd(1,100)==1) beneficialInsect[i]=tb_Rnd(1,75); if (tb_Rnd(1,100)==1) harmfulInsect[i]=tb_Rnd(1,75); } } void ai_World::show() { // cout << "/t temperature water sunlight nutrient beneficialInsect harmfulInsect/n"; cout << "current/t " << currentTemperature << "/t " << currentWater << "/t "; cout << currentSunlight << "/t " << currentNutrient << "/t "; cout << currentBeneficialInsect << "/t " << currentHarmfulInsect << "/n"; for (int i=0;i<kMaxFlowers;i++) { cout << "Flower " << i << ": "; cout << temperature[i] << "/t "; cout << water[i] << "/t "; cout << sunlight[i] << "/t "; cout << nutrient[i] << "/t "; cout << beneficialInsect[i] << "/t "; cout << harmfulInsect[i] << "/t "; cout << endl; } } #endif // AIWORLD_H_ //test.cpp #include <iostream> #include "ai_World.h" using namespace std; int main() { ai_World a; a.Encode(); // a.show(); for (int i = 0; i < 10; i++) { cout << "Generation " << i << endl; a.Evolve(); a.show(); } system("PAUSE"); return 0; }
希望本文所述对大家的C++程序设计有所帮助。
【C++实现遗传算法】相关文章：
★ C++中用两个标准容器stack,实现一个队列的方法详解