C++实现遗传算法
本文实例讲述了C++实现简单遗传算法。分享给大家供大家参考。具体实现方法如下：
//CMVSOGA.h:mainheaderfilefortheCMVSOGA.cpp
////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////
#if!defined(AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767__INCLUDED_)
#defineAFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767__INCLUDED_
#if_MSC_VER>1000
#pragmaonce
#endif//_MSC_VER>1000
#include"Afxtempl.h"
#definevariablenum14
classCMVSOGA
{
public:
CMVSOGA();
~CMVSOGA();
voidselectionoperator();
voidcrossoveroperator();
voidmutationoperator();
voidinitialpopulation(int,int,double,double,double*,double*);//种群初始化
voidgeneratenextpopulation();//生成下一代种群
voidevaluatepopulation();//评价个体，求最佳个体
voidcalculateobjectvalue();//计算目标函数值
voidcalculatefitnessvalue();//计算适应度函数值
voidfindbestandworstindividual();//寻找最佳个体和最差个体
voidperformevolution();
voidGetResult(double*);
voidGetPopData(CList<double,double>&);
voidSetFitnessData(CList<double,double>&,CList<double,double>&,CList<double,double>&);
private:
structindividual
{
doublechromosome[variablenum];//染色体编码长度应该为变量的个数
doublevalue;
doublefitness;//适应度
};
doublevariabletop[variablenum];//变量值
doublevariablebottom[variablenum];//变量值
intpopsize;//种群大小
//intgeneration;//世代数
intbest_index;
intworst_index;
doublecrossoverrate;//交叉率
doublemutationrate;//变异率
intmaxgeneration;//最大世代数
structindividualbestindividual;//最佳个体
structindividualworstindividual;//最差个体
structindividualcurrent;//当前个体
structindividualcurrent1;//当前个体
structindividualcurrentbest;//当前最佳个体
CList<structindividual,structindividual&>population;//种群
CList<structindividual,structindividual&>newpopulation;//新种群
CList<double,double>cfitness;//存储适应度值
//怎样使链表的数据是一个结构体????主要是想把种群作成链表。节省空间。
};
#endif
执行文件：
//CMVSOGA.cpp:implementationfile
//
#include"stdafx.h"
//#include"vld.h"
#include"CMVSOGA.h"
#include"math.h"
#include"stdlib.h"
#ifdef_DEBUG
#definenewDEBUG_NEW
#undefTHIS_FILE
staticcharTHIS_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();
}
voidCMVSOGA::initialpopulation(intps,intgen,doublecr,doublemr,double*xtop,double*xbottom)//第一步，初始化。
{
//应该采用一定的策略来保证遗传算法的初始化合理，采用产生正态分布随机数初始化？选定中心点为多少？
inti,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命令。
}
}
voidCMVSOGA::generatenextpopulation()//第三步，生成下一代。
{
//srand((unsigned)time(NULL));
selectionoperator();
crossoveroperator();
mutationoperator();
}
//voidCMVSOGA::evaluatepopulation()//第二步，评价个体，求最佳个体
//{
//calculateobjectvalue();
//calculatefitnessvalue();//在此步中因该按适应度值进行排序.链表的排序.
//findbestandworstindividual();
//}
voidCMVSOGA::calculateobjectvalue()//计算函数值，应该由外部函数实现。主要因为目标函数很复杂。
{
inti,j;
doublex[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);
}
}
voidCMVSOGA::mutationoperator()//对于浮点数编码，变异算子的选择具有决定意义。
//需要guass正态分布函数，生成方差为sigma，均值为浮点数编码值c。
{
//srand((unsignedint)time(NULL));
inti,j;
doubler1,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)
{
doublesign;
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);
}
}
voidCMVSOGA::selectionoperator()//从当前个体中按概率选择新种群,应该加一个复制选择,提高种群的平均适应度
{
inti,j,pindex=0;
doublep,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变化后，以上没有问题了。
voidCMVSOGA::crossoveroperator()//非均匀算术线性交叉，浮点数适用,alpha,beta是(0，1)之间的随机数
//对种群中两两交叉的个体选择也是随机选择的。也可取beta=1-alpha;
//current的变化会有一些改变。
{
inti,j;
doublealpha,beta;
CList<int,int>index;
intpoint,temp;
doublep;
//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++)
{
//交叉
doublesign;
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();
}
voidCMVSOGA::findbestandworstindividual()
{
inti;
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;
}
elseif(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;
}
}
}
voidCMVSOGA::calculatefitnessvalue()//适应度函数值计算，关键是适应度函数的设计
//current变化，这段程序变化较大，特别是排序。
{
inti;
doubletemp;//alpha,beta;//适应度函数的尺度变化系数
doublecmax=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);
}
}
voidCMVSOGA::performevolution()//演示评价结果,有冗余代码,current变化，程序应该改变较大
{
if(bestindividual.fitness>currentbest.fitness)
{
currentbest=population.GetAt(population.FindIndex(best_index));
}
else
{
population.SetAt(population.FindIndex(worst_index),currentbest);
}
}
voidCMVSOGA::GetResult(double*Result)
{
inti;
for(i=0;i<variablenum;i++)
{
Result[i]=currentbest.chromosome[i];
}
Result[i]=currentbest.value;
}
voidCMVSOGA::GetPopData(CList<double,double>&PopData)
{
PopData.RemoveAll();
inti,j;
for(i=0;i<popsize;i++)
{
current=population.GetAt(population.FindIndex(i));
for(j=0;j<variablenum;j++)
{
PopData.AddTail(current.chromosome[j]);
}
}
}
voidCMVSOGA::SetFitnessData(CList<double,double>&PopData,CList<double,double>&FitnessData,CList<double,double>&ValueData)
{
inti,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:
*********************************************************************/
#ifndefAIWORLD_H_
#defineAIWORLD_H_
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cmath>
#definekMaxFlowers10
usingstd::cout;
usingstd::endl;
classai_World
{
public:
ai_World()
{
srand(time(0));
}
~ai_World(){}
inttemperature[kMaxFlowers];//温度
intwater[kMaxFlowers];//水质
intsunlight[kMaxFlowers];//阳光
intnutrient[kMaxFlowers];//养分
intbeneficialInsect[kMaxFlowers];//益虫
intharmfulInsect[kMaxFlowers];//害虫
intcurrentTemperature;
intcurrentWater;
intcurrentSunlight;
intcurrentNutrient;
intcurrentBeneficialInsect;
intcurrentHarmfulInsect;
/**
第一代花朵
*/
voidEncode();
/**
花朵适合函数
*/
intFitness(intflower);
/**
花朵演化
*/
voidEvolve();
/**
返回区间[start,end]的随机数
*/
inlineinttb_Rnd(intstart,intend)
{
if(start>end)
return0;
else
{
//srand(time(0));
return(rand()%(end+1)+start);
}
}
/**
显示数值
*/
voidshow();
};
//-----------------------------------------------------------------//
voidai_World::Encode()
//-----------------------------------------------------------------//
{
inti;
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);
}
//-----------------------------------------------------------------//
intai_World::Fitness(intflower)
//-----------------------------------------------------------------//
{
inttheFitness;
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);
}
//-----------------------------------------------------------------//
voidai_World::Evolve()
//-----------------------------------------------------------------//
{
intfitTemperature[kMaxFlowers];
intfitWater[kMaxFlowers];
intfitSunlight[kMaxFlowers];
intfitNutrient[kMaxFlowers];
intfitBeneficialInsect[kMaxFlowers];
intfitHarmfulInsect[kMaxFlowers];
intfitness[kMaxFlowers];
inti;
intleastFit=0;
intleastFitIndex;
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);
}
}
voidai_World::show()
{
//cout<<"/ttemperaturewatersunlightnutrientbeneficialInsectharmfulInsect/n";
cout<<"current/t"<<currentTemperature<<"/t"<<currentWater<<"/t";
cout<<currentSunlight<<"/t"<<currentNutrient<<"/t";
cout<<currentBeneficialInsect<<"/t"<<currentHarmfulInsect<<"/n";
for(inti=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"
usingnamespacestd;
intmain()
{
ai_Worlda;
a.Encode();
//a.show();
for(inti=0;i<10;i++)
{
cout<<"Generation"<<i<<endl;
a.Evolve();
a.show();
}
system("PAUSE");
return0;
}
希望本文所述对大家的C++程序设计有所帮助。