本文實例講述了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 14class 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_FILEstatic char THIS_FILE[] = __FILE__;#endif/////////////////////////////////////////////////////////////////////////////// CMVSOGA.cppCMVSOGA::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.hPurpose: 遺傳算法，花朵演化。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++程序設計有所幫助。
