gaobject.txt

基于Visual C++ 语言的遗传算法求函数最小值的程序代码。

遗传算法实现求函数最小值

程序的各函数的简单算法说明如下：
void generateinitial ()和void input ()初始化种群和遗传算法参数。
input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。
void calculateobjectvalue();计算适应度函数值 。根据给定的变量用适应度函数计算然后返回适度值。可选计算最大值或计算最小值
选择函数selectoperator()
在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在；
显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。
染色体交叉函数crossoveroperator()
这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉。这时又要用rand()函数随机产生一位交叉位，把染色体的交叉位的后面部分交叉即可；若大于交叉概率，则进行简单的染色体复制即可。
染色体变异函数mutation()
变异是针对染色体字符变异的，而不是对个体而言，即个体变异的概率是一样。随机产生比较概率，若小于变异概率，则1变为0，0变为1。
long decodechromosome(char *,int,int) 本函数是染色体解码函数，它将以数组形式存储的二进制数转成十进制数，然后才能用适应度函数计算。
void findbestindividual()本函数是求最大适应度个体的，每一代的所有个体都要和初始的最佳比较，如果大于就赋给最佳。
void outputtextreport ()   输出种群统计结果
输出每一代的种群的最大适应度和平均适应度，最后输出全局最大值


------------以下内容为对上文补充-----------------------
设计遗传算法的基本内容
(1).编码方案，本例中-2.048<=x1,x2<=2.048
编码时将x1，x2各编为10位，这样可表示的数值大小为 temp= 0-1023
再通过x1=4.096*temp/1023.0-2.048刚好映射到-2.048<=x1,x2<=2.048
也可以选择你自己喜欢的编码方式
(2).适应度函数，即当前染色体与环境的适应情况，因为这里是求最小值，所以可以与估计最小值最比较，（这里一般是0）取差值作为适应度
(3)选择策略 用于选择产生下一代种群。
这里采用 轮盘赌选择算法（具体实现可以自己去搜索一下 ）主要是用到累计概率，然后产生各随机数，看落在那个概率区间就选择保留
(4)控制参数
主要有种群规模，最大代数，交叉概率，变异概率的参数，这些参数不同，直接影响最后的种群逼近程度
(5)遗传算子，实现优胜劣汰的进化过程，产生下一代种群。
主要有 选择 交叉 变异等操作
(6)算法终止规则，这里设置了最大种群数，达到了最大种群数，程序就结束了。
看下主程序 ：
while(generation<maxgeneration)
{
   generation++;
   generatenextpopulation();
   evaluatepopulation();
   //outputtextreport();
}
整个过程就是产生下一代，然后计算当前产生的种群的适应度以及当前最佳个体。。。


不知道本例程对大家有没有什么启发。。。
个人认为在算法实现较为复杂，同时并不需要精确的最大值或最小值时，遗传算法不失为一种好的应用。。。（不过本人还没有发现什么地方可以应用进去。。。=_=!!!）


参考文献：《人工智能及其应用》 王万良著


-----------------------------------------------------------

源代码
*/
#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<math.h>

#define POPSIZE 500                 //最大种群数
#define cmax 400                    //估计最大值
#define cmin 0
#define length1 10                   //x1
#define length2 10                   //x2
#define chromlength length1+length2 //染色体长度

int functionmode=2;                  //设定为求最小值
int popsize;                         //种群大小
int maxgeneration;                   //最大世代数
double pc;                           //交叉率
double pm;                           //变异率

struct individual
{
char chrom[chromlength+1];      //编码串
double value;                    //函数值
double fitness;                  //适应度
};                                 //定义个体数据结构

int     generation;                  //世代数
int     best_index;
int     worst_index;
struct individual bestindividual;   //最佳个体
struct individual currentbest;      //当前最佳个体
struct individual population[POPSIZE];// 种群

long decodechromosome(char *string ,int point,int length) //给染色体解码
{
int i;
long decimal=0;
char*pointer;
for(i=0,pointer=string+point;i<length;i++,pointer++)
   if(*pointer-'0')
    decimal +=(long)pow(2,i);
return (decimal);
}

void calculateobjectvalue() //计算函数值
{
int i;
long temp1,temp2;
double x1,x2;

for (i=0; i<popsize; i++)
{
   temp1=decodechromosome(population[i].chrom,0,length1);
   temp2=decodechromosome(population[i].chrom,length1,length2);
   x1=4.096*temp1/1023.0-2.048;
   x2=4.096*temp2/1023.0-2.048;
   population[i].value=100*(x1*x1-x2)* (x1*x1-x2)+(1-x1)*(1-x1);
}
}

void calculatefitnessvalue()//计算适应度
{
int i;
double temp;

for(i=0;i<popsize;i++)
{
   if(functionmode==1)
   {
    if((population[i].value+cmin)>0.0)
     temp=cmin+population[i].value;
    else
     temp=0.0;
   }//求最大值情况
   else
   {
    if (functionmode==2)
     if(population[i].value<cmax)
      temp=cmax-population[i].value;
     else
      temp=0.0;
   }//求最小值情况
   population[i].fitness=temp;
}
}

void selectoperator() //比例选择算法
{
int i,index;
double p,sum=0.0;
double cfitness[POPSIZE];//存每个个体的概率
struct individual newpopulation[POPSIZE];

for(i=0;i<popsize;i++)
   sum+=population[i].fitness;
for(i=0;i<popsize; i++)
   cfitness[i]=population[i].fitness/sum;
for(i=1;i<popsize; i++)//计算累计概率
   cfitness[i]=cfitness[i-1]+cfitness[i];

for (i=0;i<popsize;i++)
{
   p=rand()%1000/1000.0;
   index=0;
   while (p>cfitness[index])
    index++;
   newpopulation[i]=population[index];
}//轮盘赌选择
for(i=0;i<popsize; i++)
   population[i]=newpopulation[i];
}

void crossoveroperator() //交叉算法
{
int i,j;
int index[POPSIZE];
int point,temp;
double p;
char ch;

for (i=0;i<popsize;i++)
   index[i]=i;
for (i=0;i<popsize;i++)
{
   point=rand()%(popsize-i);
   temp=index[i];
   index[i]=index[point+i];
   index[point+i]=temp;
}//对当前个体进行随机排序

for (i=0;i<popsize-1;i+=2)
{
   p=rand()%1000/1000.0;
   if (p<pc){
    point=rand()%(chromlength-1)+1;
    for (j=point; j<chromlength;j++){
     ch=population[index[i]].chrom[j];
     population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
     population[index[i+1]].chrom[j]=ch;
    }
   }
}
}

void mutationoperator() //变异操作
{
int i,j;
double p;

for (i=0;i<popsize;i++){
   for(j=0;j<chromlength;j++){
    p=rand()%1000/1000.0;
    if (p<pm){
     population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';
    }
   }
}
}

void findbestindividual() //求当前最佳个体
{
int i;
double sum=0.0;

bestindividual=population[0];
for (i=1;i<popsize; i++){
   if (population[i].fitness>bestindividual.fitness){
    bestindividual=population[i];
    best_index=i;
   }
   sum+=population[i].fitness;
}
if (generation==0){
   currentbest=bestindividual;
}
else{
   if(bestindividual.fitness>=currentbest.fitness){
    currentbest=bestindividual;
   }
}
}

void input() //数据输入
{
printf("程序初始化:\n");
printf("输入种群大小(50-500偶数)：");
scanf("%d", &popsize);
printf("    最大世代数(100-300)：");
scanf("%d", &maxgeneration);
printf("    交叉率(0.2-0.99)：");
scanf("%f", &pc);
printf("    变异率(0.001-0.1)：");
scanf("%f", &pm);
}

void generateinitial( ) //种群初始化
{
int i,j;

for (i=0;i<popsize; i++)
{
   for(j=0;j<chromlength+1;j++)
   {
    population[i].chrom[j]=(rand()%10<5)?'0':'1';
   }
}
}

void generatenextpopulation() //生成下一代
{
selectoperator();
crossoveroperator();
mutationoperator();
}

void evaluatepopulation()   //评价个体，求最佳个体
{
calculateobjectvalue();
calculatefitnessvalue();
findbestindividual();
}

void outputtextreport()//数据输出
{
int i;
double sum;
double average;
sum=0.0;
for(i=0;i<popsize;i++)
{
   sum+=population[i].value;
}
average=sum/popsize;
printf("当前世代=%d\n当前世代平均函数值=%f\n当前世代最高函数值=%f\n",generation,average,population[best_index].value);
}

void main()    //主函数
{
int i;
printf("本程序用遗传算法求函数y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)的最小值   \n其中-2.048<=x1,x2<=2.048\n");
generation=0;
input();
generateinitial();
evaluatepopulation();
while(generation<maxgeneration)
{
   generation++;
   generatenextpopulation();
   evaluatepopulation();
   //outputtextreport();
}

printf("\n---------------计算结果----------\n");
printf("最小函数值等于：%f\n",currentbest.value);
printf("其染色体编码为：");
for (i=0;i<chromlength;i++)
{
   printf("%c",currentbest.chrom[i]);
}
printf("\n");

long temp1,temp2;
double x1,x2;
temp1=decodechromosome(currentbest.chrom,0,length1);
temp2=decodechromosome(currentbest.chrom,length1,length2);
x1=4.096*temp1/1023.0-2.048;
x2=4.096*temp2/1023.0-2.048;
printf("对应的参数值为： x1=%f x2=%f\n",x1,x2);
}


/*
运行结果：

本程序用遗传算法求函数y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)的最小值
其中-2.048<=x1,x2<=2.048
程序初始化:
输入种群大小(50-500偶数)：300
    最大世代数(100-300)：200
    交叉率(0.2-0.99)：0.3
    变异率(0.001-0.1)：0.008

---------------计算结果----------
最小函数值等于：0.026552
其染色体编码为：00000100110111001011
应的参数值为： x1=1.155128 x2=1.339308
*/