小试遗传算法
有些日子了,人工智能的老师讲了遗传算法,用老师的话说,就是有策略地瞎蒙。
老师给我们留了个简单的作业,就是把书本的例子实现了。
我们用的教材是,清华大学出版的《人工智能及其应用》第四版,蔡自兴、徐光祐著。
做的例子是,书本166页的遗传算法求解举例,求:f(x)=xsin(10PI*x)+1.0在[-1,2]区间上面的最大值。
做图可以看 这里 ,Google的做图,前提是,你用的是现代浏览器。
我写的代码如下,注释写了些了,应该挺好看懂的了。
#include <cstdio>
#include <cmath>
#include <cstdlib>//RAND_MAX rand()
#include <ctime>
//程序常量参数
const int
maxGen=1000,//最大代数
M=100,//种群限制
bitLen=22,//二进制位宽
mask=(1<<bitLen)-1,//二进制掩码,把多余的部分砍掉的
genThreshold=10;//跳出循环的检查,如果这个数值制定的最近代都没什么改变,退出
const double
pC=0.8,//交叉概率
pM=0.1,//变异概率
PI=acos(-1.0),//圆周率
bestFitnessEsp=0.000001,//没什么变化的界定
totalFitnessEsp=bestFitnessEsp*M;//同上,扩展到总体样本和
//变量
int currentI,gen;//当前的个体I,和现在第几代。
unsigned int oldPopulation[M],population[M],bestGen[maxGen];//新旧的两代,最优的基因
double possibility[M],fitness[M],bestFitness[maxGen],totalFitness[maxGen];//赌轮概率值,适应值,某代最优适应值,某代适应值之和
void printBit(unsigned int x){//二进制打印
for(int i=31;i>=0;i--){
if(1<<i&x)
putchar('1');
else
putchar('0');
}
}
double abs(double x){
if(x<0)return -x;
return x;
}
double f(double x){//函数,同时也是适应函数
return x*sin(PI*10*x)+1.0;
}
double convert(unsigned int x){//二进制转换
return double(x)/mask*3.0-1.0;
}
void populationInit(){//种群初始化
for(int i=0;i<M;i++){
population[i]=rand();//RAND_MAX = 32767,15个1,所以
population[i]<<=15;//右移
population[i]|=rand();//再加入15位
population[i]&=mask;//去掉多余
// printBit(population[i]);
}
}
bool canStop(){
if(gen<genThreshold)//达到最大进化代数
return false;
if(maxGen<=gen)
return true;
bool ret=true;
int lgen=gen-1;
for(int i=gen-genThreshold;i<lgen;i++){//最优没啥变化
ret=ret&&abs(bestFitness[lgen]-bestFitness[i])<bestFitnessEsp;
}
if(ret){
puts("最优没啥变化,算法终止。");
return true;
}
ret=true;
for(int i=gen-genThreshold;i<lgen;i++){//总值没啥变化(平均)
ret=ret&&abs(totalFitness[lgen]-totalFitness[i])<totalFitnessEsp;
}
if(ret){
puts("总值没啥变化(平均),算法终止。");
}
return ret;
}
void countFitness(){
totalFitness[gen]=0;
bestFitness[gen]=0;
for(int i=0;i<M;i++){
oldPopulation[i]=population[i];
fitness[i]=f(convert(population[i]));//适应值
totalFitness[gen]+=fitness[i];//统计所有的适应值之和,两个用途,一个决定退出循环,因为适应值没啥变化,一个是计算概率,所以不去除个平均值出来了
possibility[i]=totalFitness[gen];//概率范围,对于第i个,它的概率就是 possibility[i]-possibility[i-1],赌轮的范围就是: possibility[i-1] ~ possibility[i]
if(bestFitness[gen]<fitness[i]){//保存最优
bestFitness[gen]=fitness[i];
bestGen[gen]=population[i];
}
}
}
void copy(int from){//复制
population[currentI]=oldPopulation[from];
currentI++;
}
void cross(int a,int b){//交叉,书本介绍的价差只有一个交叉点,是不是太弱?不过简单,我喜欢。
int pos=rand()%(bitLen-1)+1 ;
unsigned int mask_1=(1<<pos)-1;
unsigned int mask_0=~mask_1;
population[currentI++]=(oldPopulation[a]&mask_1)|(oldPopulation[b]&mask_0);
population[currentI++]=(oldPopulation[b]&mask_1)|(oldPopulation[a]&mask_0);
/* printBit(mask_1);puts("");
printBit(oldPopulation[a]);puts("");
printBit(population[currentI-1]);puts("");
printBit(oldPopulation[b]);puts("");
printBit(population[currentI-2]);puts("");
getchar();*/
}
void heteromorphosis(int from){//变异
int pos=rand()%(bitLen-1);
population[currentI++]=oldPopulation[from]^(1<<pos);
/* printBit(1<<pos);puts("");
printBit(oldPopulation[from]);puts("");
printBit(population[currentI-1]);puts("");
getchar();*/
}
int select(){//赌轮选择一个个体
double p=totalFitness[gen]*rand()/RAND_MAX;
int l=0,r=M-1,m;
while(l<r){
m=(l+r)>>1;
if(possibility[m]<p){
l=m+1;
}else{
r=m;
}
}
if(!(p<possibility[m]&&p>possibility[m-1])){
m=r;
}
/*//这部分用来检查二分的正确性的。
if(m>=1){
if(!(p<possibility[m]&&p>possibility[m-1])){
printf("选择函数出错!#1 %f-%f-%f %f %dn",possibility[m-1],possibility[m],possibility[m+1],p,m);
getchar();
}
}else{
if(!(p<possibility[m])){
printf("选择函数出错!#2 %f %fn",possibility[m],p);
getchar();
}
}*/
return m;
}
void inherit(){
double p;
currentI=0;
while(currentI<M){
p=double(rand())/RAND_MAX;//随机决定这次进行的操作
if(p<pC){//0~pC,进行交叉
cross(select(),select());
}else if(p<pC+pM){//pC~pM 变异
heteromorphosis(select());
}else{//复制
copy(select());
}
// printBit(population[currentI-1]);puts("");
}
}
int main(){
srand((unsigned)time(NULL));//用时间初始化随机函数
while(true){
gen=0;
populationInit();
while(!canStop()){
countFitness();
printf("代数:%3d 基因:",gen);
printBit(bestGen[gen]);
printf(" f(%f) = %fn",convert(bestGen[gen]),bestFitness[gen]);
inherit();
gen++;
}
puts("nn计算完成,按回车再算一遍。");
getchar();
puts("nn");
}
return 0;
}
不过,测试的时候,发现这个算法的正确性是不保证的。
如果种群样本按照书本采取50个的时候,有比较大的概率得到的是1.65左右的这个解。如下图,我作图后发现,是一个较优解而已。代码里面,我把种群数量设置为1000了,基本都能得到解。不过让我想起了数值分析里面的二分法,效率比起这个算法高多了。