遗传算法中关于select部分的看不太懂,请高手指点!
这是遗传算法中关于select部分的源代码,因为是刚开始接触这种算法,所以看不太明白,主要是中间用随机数p来判断然后选择的部分...
另外,作者说这是比率选择,不知道怎么体现的?如果我想保留最优的话应该怎么编呢?嗬嗬 麻烦各位了!在此先谢过!!
void select(void)
{
int mem, i, j, k,m;
double sum = 0;
double p;
/* find total fitness of the population */
for (mem = 0; mem < POPSIZE; mem++)
{
sum += population[mem].fitness;
}
printf( "After selecting:\n\n ");
/* calculate relative fitness */
for (mem = 0; mem < POPSIZE; mem++)
{
population[mem].rfitness = population[mem].fitness/sum;
}
population[0].cfitness = population[0].rfitness;
/* calculate cumulative fitness */
for (mem = 1; mem < POPSIZE; mem++)
{
population[mem].cfitness = population[mem-1].cfitness +
population[mem].rfitness;
}
/* finally select survivors using cumulative fitness. */
for (i = 0; i < POPSIZE; i++)
{
p = rand()%1000/1000.0;
if (p < population[0].cfitness)
newpopulation[i] = population[0];
else
{
for (j = 0; j < POPSIZE;j++)
if (p > = population[j].cfitness &&
p <population[j+1].cfitness)
newpopulation[i] = population[j+1];
}
}
/* once a new population is created, copy it back */
for (i = 0; i < POPSIZE; i++)
{ population[i] = newpopulation[i];
for (m = 0; m < NVARS; m++)
{printf( "%d ",population[i].gene[m]);}
evaluate();
printf( " %f\n ",population[i].fitness);
}
}
[解决办法]
以下是我以前用C#写的一个选择类
------------------------------
using System;
namespace CourseArrangeAglorithem
{
/// <summary>
/// SelectIndividual 的摘要说明。
/// </summary>
public class SelectIndividual //选择个体
{
public SelectIndividual()
{
//
// TODO: 在此处添加构造函数逻辑
//
}
//轮盘赌选择法
public Individual[] SelectIndiv(Population pop)
{
double[] rand = this.Rand(pop.Popsize);
double[] selectpro = this.SelectPro(pop);
for( int k = 0; k < pop.Popsize; k++)
{
for(int kk = 0; kk < pop.Popsize; kk++)
{
if( kk == 0)
{
if(rand[k] <= selectpro[kk])
{
pop.newpop[k] = pop.oldpop[kk];
break;
}
}
else if(kk > 0)
{
if(rand[k] <= selectpro[kk] && rand[k] > selectpro[kk-1])
{
pop.newpop[k] = pop.oldpop[kk];
break;
}
}
else if( kk == pop.Popsize -1)
{
pop.newpop[k] = pop.oldpop[kk];
}
}
}
return pop.newpop;
}
private double[] Rand(int size)
{
double[] rand = new double[size];
Random random = new Random();
for(int k = 0; k < size; k++)
{
rand[k] = random.NextDouble();
}
return rand;
}
private double[] SelectPro(Population pop)
{
double allfit = 0;
for( int k = 0; k < pop.Popsize; k++)
{
allfit += pop.oldpop[k].Fitness;
}
double[] probability = new double[pop.Popsize];
for(int k = 0; k < pop.Popsize; k++)
{
probability[k] = pop.oldpop[k].Fitness / allfit;
if( k > 0)
{
probability[k] += probability[k-1];
}
}
return probability;
}
}
}
[解决办法]
你的程序的选择叫 "赌轮选择 ",或 "旋转轮选择 "。
其中rfitness[]是个体适应值,其总和=1;
而cfitness叫累加适应值,愈到后面,累加适应值愈大。
例如,假如n=5,population[i].fitness为: 3,4,2,6,5
则总和
sum = 3+4+2+6+5 = 20;
rfitness[0]-rfitness[4]分别为:
3/20,4/20,2/20,6/20,5/20
而rcfitness[0]-cfitness[4]分别为
0,3/20,(3+4)/20,(3+4+2)/20,(3+4+2+6)/20,(3+4+2+6+5)/20
用线段表示,它们就是以下6个刻度线:
|---|----|--|------|-----|
整个长度=1,
把这个直线弯曲成一个圆,就成为一个“赌轮”了,就可以用来 "摇奖 "式的选择了:
选择哪一个,就是随机选择一个0与1之间的实数p,
看p落在哪一个小区间中,就选哪一个。
-------------------------------------------
你可能以为选择是单纯根据适应值,所以看不懂了。
其实适应值大小只是确定被选上的机率大小,而不是一定选择它。