遗传算法简述及代码详解
声明：本文内容整理自网络，认为原作者同意转载，如有冒犯请联系我。
遗传算法基本内容
遗传算法为群体优化算法，也就是从多个初始解开始进行优化，每个解称为一个染色体，各染色体之间通过竞争、合作、单独变异，不断进化。
遗传学与遗传算法中的基础术语比较
染色体(chromosome) 数据，数组，序列
基因(gene) 单个元素，位
等位基因(allele) 数据值，属性，值
基因座(locus) 位置，iterator位置
表现型(phenotype) 参数集，解码结构，候选解
染色体：又可以叫做基因型个体(individuals)
群体/种群(population)：一定数量的个体组成，及一定数量的染色体组成，群体中个体的数
量叫做群体大小。
初始群体：若干染色体的集合，即解的规模，如30，50等，认为是随机选取的数据集合。适应度(fitness)：各个个体对环境的适应程度
优化时先要将实际问题转换到遗传空间，就是把实际问题的解用染色体表示，称为编码，反过程为解码/译码，因为优化后要进行评价（此时得到的解是否较之前解优越），所以要返回问题空间，故要进行解码。SGA采用二进制编码，染色体就是二进制位串，每一位可称为一个基因；如果直接生成二进制初始种群，则不必有编码过程，但要求解码时将染色体解码到问题可行域内。
遗传算法的准备工作:
1) 数据转换操作，包括表现型到基因型的转换和基因型到表现型的转换。前者是把求解空间中的参数转化成遗传空间中的染色体或者个体(encoding)，后者是它的逆操作(decoding)
2) 确定适应度计算函数，可以将个体值经过该函数转换为该个体的适应度，该适应度的高低要能充分反映该个体对于解得优秀程度。非常重要的过程。
遗传算法基本过程为:
1) 编码，创建初始群体
2) 群体中个体适应度计算
3) 评估适应度
4) 根据适应度选择个体
5) 被选择个体进行交叉繁殖
6) 在繁殖的过程中引入变异机制
7) 繁殖出新的群体，回到第二步
实例一：（建议先看实例二）
求 []30,0∈x 范围内的()2
10-=x y 的最小值
1) 编码算法选择为"将x 转化为2进制的串"，串的长度为5位（串的长度根据解的精度设 定，串长度越长解得精度越高）。(等位基因的值为0 or 1)。 2) 计算适应度的方法是：先将个体串进行解码，转化为int 型的x 值，然后使用()
2
10-=x y 作为其适应度计算合适(由于是最小值，所以结果越小，适应度也越好)。
需要说明，将原目标函数设置为适应度函数是一种选择，但未必是最贴切的方法。 3) 正式开始，先设置群体大小为4，然后初始化群体 => (在[0，31]范围内随机选取4个整 数就可以编码)
4) 计算适应度Fi(由于是求解最小值，可以选取一个大的基准线1000 ()2
101000--=x Fi ）
5) 计算每个个体的选择概率，选择概率要能够反映个体的优秀程度。这里用一个很简单的 方法来确定选择概率 )(/Fi TOTAL Fi p =
6) 选择
根据所有个体的选择概率进行淘汰选择。这里使用的是一个赌轮的方式进行淘汰选择。先按照每个个体的选择概率创建一个赌轮，然后选取4次，每次先产生一个0-1的随机小数，然后判断该随机数落在那个段内就选取相对应的个体。这个过程中，选取概率p 高的个体将可能被多次选择，而概率低的就可能被淘汰。 下面是一个简单的赌轮的例子
13% 35% 15% 37% ----------|----------------------------|------------------|---------------------------------| 个体1 个体2 个体3 ^0.67 个体4 随机数为0.67落在了个体4的端内，本次选择了个体4。
被选中的个体将进入配对库(mating pool ，配对群体)准备开始繁殖。 7) 简单交叉
先对配对库中的个体进行随机配对，然后在配对的2个个体中设置交叉点，交换2个个体的信息后产生下一代。
比如( | 代表简单串的交叉位置)
( 0110|1，1100|0 ) --交叉--> (01100，11001) ( 01|000，11|011 ) --交叉--> (01011，11000)
2个父代的个体在交叉后繁殖出了下一代的同样数量的个体.
复杂的交叉在交叉的位置，交叉的方法，双亲的数量上都可以选择.其目的都在于尽可能的培育出更优秀的后代 8) 变异
变异操作时按照基因座来的，比如说每计算2万个基因座就发生一个变异(我们现在的每个个体有5个基因座。也就是说要进化1000代后才会在其中的某个基因座发生一次变异)变异的结果是基因座上的等位基因发生了变化。我们这里的例子就是把0变成1或则1变成0。 至此，我们已经产生了一个新的(下一代)群体，然后回到第4步，周而复始，生生不息下去。
实例二：
为了便于理解，手工计算来简单地模拟遗传算法的各个主要执行步骤：
（1）个体编码
遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种符号串。本题中，用无符号二进制整数（编码方式较多）来表示。
因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。 例如，基因型 X ＝101110 所对应的表现型是：x ＝[ 5，6 ]。 个体的表现型x 和基因型X 之间可通过编码和解码程序相互转换。
(2) 初始群体的产生
遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始群体数据。
本例中，群体规模的大小（随机选取）取为4，即群体由4个个体组成，每个个体可通过随机方法产生。
如：011101，101011，011100，111001
(3) 适应度汁算
遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。
本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度（适应度函数可以有许多）。
(4) 选择运算
选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。 本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是：
? 先计算出群体中所有个体的适应度的总和 ∑===M
i M i fi
FI 1
),,1( ；
? 其次计算出每个个体的相对适应度的大小),,1(/M i FI
fi =，它即为每
个个体被遗传到下一代群体中的概率；
? 每个概率值组成一个区域，全部概率值之和为1；
? 最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率 区域内来确定各个个体被选中的次数。（详见下图）
(5)交叉运算
交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。
本例采用单点交叉的方法，其具体操作过程是：
?先对群体进行随机配对；
?其次随机设置交叉点位置；
?最后再相互交换配对染色体之间的部分基因。
(6) 变异运算
变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。
本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：?首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，
其中的数字表示变异点设置在该基因座处；
?然后依照某一概率将变异点的原有基因值取反。
对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。
从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体“111111”。
[注意]
需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中，有可能需要一定的循环次数才能达到这个最优结果。
选择要能够合理的反映“适者生存”的自然法则，而交叉必须将有利的基因尽量遗传给下一代(这是算法的关键！)
算法过程当中有几个随机过程：
（1）初始种群的产生是随机产生，但有时为了更好迭代，知道解在某一个值附近，可以认为设定初始种群
（2）确定个体被选中次数时，运用到轮赌法，其产生的数据为随机数据
（3）交叉点
（4）变异点
伪代码:
//Init population
foreach individual in population
{
individual = Encode(Random(0,31));
}
while (App.IsRun)
{
//计算个体适应度
int TotalF = 0;
foreach individual in population
{
individual.F = 1000 - (Decode(individual)-10)^2;
TotalF += individual.F;
}
//------选择过程,计算个体选择概率-----------
foreach individual in population
{
individual.P = individual.F / TotalF;
}
//选择
for(int i=0;i<4;i++)
{
//SelectIndividual(float p)是根据随机数落在段落计算选取哪个个体的函数
MatingPool[i] = population[SelectIndividual(Random(0,1))];
}
//-------简单交叉---------------------------
//由于只有4个个体,配对2次
for(int i=0;i<2;i++)
{
MatingPool.Parents[i].Mother = MatingPool.RandomPop();
MatingPool.Parents[i].Father = MatingPool.RandomPop();
}
//交叉后创建新的集团
population.Clean();
foreach Parent in MatingPool.Parents
{
//注意在copy 双亲的染色体时在某个基因座上发生的变异未表现.
child1 = Parent.Mother.DivHeader + Parent.Father.DivEnd;
child2 = Parent.Father.DivHeader + Parent.Mother.DivEnd;
population.push(child1);
population.push(child2);
}
}
完整代码如下：
#include"stdafx.h"
#include
#include
#include
#define POPSIZE 500
#define MAXIMIZATION 1 //求解函数为求最大值
#define MINIMIZATION 2 //求解函数为求最小值
#define Cmax 100 //求解最大值时适应度函数的基准数#define Cmin 0 //求解最小值时适应度函数的基准数#define LENGTH110 //每一个解用位基因表示
#define LENGTH210
#define CHROMLENGTH LENGTH1+LENGTH2
int FunctionMode=MAXIMIZATION; //函数值求解类型是最大值int PopSize=80; //种群规模
int MaxGeneration =100; //最大世代数，即最大迭代数double Pc = 0.6; //变异概率
double Pm = 0.001; //交叉概率
struct individual//定义个体
{
char chrom[CHROMLENGTH+1]; //个体数
double value; //个体对应的变量值
double fitness; //个体适应度
};
int generation;
int best_index;
int worst_index;
struct individual bestindividual;
struct individual worstindividual;
struct individual currentbest;
struct individual population[POPSIZE];
void GenerateInitialPopulation(void); / /初始种群生成
void GenerateNextPopulation(void); //产生下一代种群
void EvaluatePopulation(void);
void CalculateObjectValue(void);
long DecodeChromosome(char *,int,int); //译码
void CalculateFitnessValue(void);
void FindBestAndWorstIndividual(void);
void PerformEvolution(void);
void SelectionOperator(void);
void CrossoverOperator(void);
void MutationOperator(void);
void OutputTextReport(void);
void main(void)
{
generation=0;
GenerateInitialPopulation(); //初始种群生成
EvaluatePopulation(); //计算种群值，即计算种群适应度
while(generation { generation++; GenerateNextPopulation(); //产生下一代种群 EvaluatePopulation(); //计算种群值，即计算种群适应度 PerformEvolution(); OutputTextReport(); } } void GenerateInitialPopulation(void) //随机产生初始种群，且用0,1表示{ int i,j; for(i=0;i { for(j=0;j { population[i].chrom[j]=(rand()%10<5)?'0':'1'; //rand()%n产生一个 // ~n-1的数} population[i].chrom[CHROMLENGTH]='\0'; } } void GenerateNextPopulation(void) { SelectionOperator(); CrossoverOperator(); MutationOperator(); } void EvaluatePopulation() { CalculateObjectValue(); CalculateFitnessValue(); FindBestAndWorstIndividual(); } long DecodeChromosome(char *string,int point,int length) //译码，换算为十进 //制数 { int i; long decimal=0L; char *pointer; for(i=0,pointer=string+point;i { decimal+=(*pointer-'0')<<(length-1-i); //移位操作，染色体实现十进 //制化 } return(decimal); } void CalculateObjectValue(void) //计算函数值 { int i; long temp1,temp2; double x1,x2; for (i =0;i { //从染色体中读取基因 temp1=DecodeChromosome (population [i ].chrom ,0,LENGTH1); temp2=DecodeChromosome (population [i ].chrom ,LENGTH1,LENGTH2); x1=4.0 *temp1/1023.0-2.0 ; //x ∈[a, b]； x2=4.0 *temp2/1023.0-2.0 ; // 1 21 *)(10 --+=temp a b a x population [i ].value =100*(x1*x2+x2)*(x1*x2-x2)*x2;// 函数表达式 } } void CalculateFitnessValue (void ) //针对不同函数类型计算个体适应度 { int i ; double temp ; for (i =0;i if ((population [i ].value +Cmin )>0.0) { temp =Cmin +population [i ].value ; } else { temp =0.0; } } else if (FunctionMode ==MINIMIZATION ) //函数类型为求解最小值 { if (population [i ].value temp =Cmax -population [i ].value ; } else { temp=0.0; } } population[i].fitness=temp; } } void FindBestAndWorstIndividual(void ) { int i; double sum=0.0; bestindividual=population[0]; worstindividual=population[0]; for (i=1;i { if (population[i].fitness>bestindividual.fitness) { bestindividual=population[i]; best_index=i; } else if (population[i].fitness { worstindividual=population[i]; worst_index=i; } sum+=population[i].fitness; } if (generation==0) { currentbest=bestindividual; } else { if(bestindividual.fitness>=currentbest.fitness) { currentbest=bestindividual; } } } void PerformEvolution(void) //执行进化 { if (bestindividual.fitness>currentbest.fitness) { currentbest=population[best_index]; } else { population[worst_index]=currentbest; } } void SelectionOperator(void) //选取最优进化代 { int i,index; double p,sum=0.0; double cfitness[POPSIZE]; struct individual newpopulation[POPSIZE]; for(i=0;i { sum+=population[i].fitness; } for(i=0;i { cfitness[i]=population[i].fitness/sum; // 个体的适应度比例} for(i=1;i { cfitness[i]=cfitness[i-1]+cfitness[i]; } for (i=0;i { p=rand()%1000/1000.0; index=0; while (p>cfitness[index]) { index++; } newpopulation[i]=population[index]; } for(i=0;i { population[i]=newpopulation[i]; } } void CrossoverOperator(void) //染色体交叉 { int i,j; int index[POPSIZE]; int point,temp; double p; char ch; for (i=0;i { index[i]=i; } for(i=0;i { point=rand()%(PopSize-i); temp=index[i]; index[i]=index[point+i]; index[point+i]=temp; } for (i=0;i { p=rand()%1000/1000.0; //随机产生交叉概率 if (p { point=rand()%(CHROMLENGTH-1)+1; for (j=point; 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(void) //基因变异 { int i,j; double p; for(i=0;i { for(j=0;j { p=rand()%1001/1000.0; if (p { population[i].chrom[j]=(population[i].chrom[j]==0)?'1':'0'; } } } } void OutputTextReport(void) //列印结果 { int i; double sum; double average; sum=0.0; for(i=0;i { sum+=population[i].value; } average=sum/PopSize; printf("gen=%d,avg=%f,best=%f,",generation,average,currentbest.value); printf("chromosome="); for (i=0;i { printf("%c",currentbest.chrom[i]); } Long temp1=DecodeChromosome(population[i].chrom,0,LENGTH1); //从染色体中读取基因 long temp2=DecodeChromosome(population[i].chrom,LENGTH1,LENGTH2); double x1=4.0*temp1/1023.0-2.0;//基因型换为表现型 double x2=4.0*temp2/1023.0-2.0; printf(" x1=%f,x2=%f",x1,x2); printf("\n"); } 一需求分析 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．测试数据 输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 二概要设计 1．程序流程图 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 worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 4．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在； 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。 （4）染色体交叉函数crossoveroperator() 这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色 遗传算法实例: 也是自己找来的，原代码有少许错误，本人都已更正了，调试运行都通过了的。 对于初学者，尤其是还没有编程经验的非常有用的一个文件 遗传算法实例 % 下面举例说明遗传算法% % 求下列函数的最大值% % f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]% % 将x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为(10-0)/(2^10-1)≈。% % 将变量域[0,10] 离散化为二值域[0,1023], x=0+10*b/1023, 其 中 b 是[0,1023] 中的一个二值数。% % % %--------------------------------------------------------------------------------------------------------------% %--------------------------------------------------------------------------------------------------------------% % 编程 %----------------------------------------------- % 初始化(编码) % 函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength 表示染色体的长度(二值数的长度)， % 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name: %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元 为{0,1} 行数为popsize，列数为chromlength的矩阵， % roud对矩阵的每个单元进行圆整。这样产生的初始种群。 % 计算目标函数值 % 将二进制数转化为十进制数(1) %遗传算法子程序 %Name: %产生[2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制 自适应遗传算法 自适应遗传算法 一.主要流程： 1. 参数的初始化。设定遗传种群规模N ，阵元数M ，信源数P 等。 2. 编码。采用十进制编码方法。 3. 初始种群的产生。随机数生成。 4. 适应度函数的评价。选取 ()() R P ΘA )tr f = （1） 其中， H 1H )(A A A A P A -= （2） P A 是A 的投影矩阵，A 是阵列流型。 ∑==L i L 1 H 1XX R ) （3） R )是数据协方差矩阵的最大似然估计。 5. 选择。比例选择方法与精英选择方法结合使用，在当代种群中选择优良个体遗传到下一代。既保证了种群的多样性，也使最优个体得以保留。 1）比例选择方法（赌轮盘法）：每个个体被选中的概率与它的适应度函数值大小成正比，即适应度函数越高的个体被选中的概率也就越高。 2）精英选择方法：让种群中适应度函数值最高的个体不进行配对交叉，直接复制到下一代中。但是容易陷入局部最优解，全局搜索能力差。 6. 交叉。按照概率P c 对种群中个体两两配对，进行交叉操作。本文中选取算数交叉的方式。 算数交叉：是由两个个体的线性组合来产生新的个体，假设第t 代的两个个体为A (t)、B (t)，则算数交叉后产生的新个体是 ()()()()t t t A B A αα-+=+11 （4） ()()()()t t t B A B αα-+=+11 （5） 其中，α选取（0，1）之间的随机数。 交叉概率：使交叉概率随着遗传代数的增长，逐渐减小，目的是进化前期注重交叉运算，全局搜索能力强。 2.02cos *4.0+?? ? ??*=πK T P c （6） 其中，T 是进化代数，K 是总进化次数。 7. 变异。按照概率P m 对种群个体进行变异。本文中选取均匀变异的方式。 均匀变异：如某基因座上的基因值为X k ，其取值范围为[Umin,Umax],对其进行变异后的值为 )U -r(U +U =X min max min k （7） 其中，r 选取[0,1]之间的随机数。 变异概率：使变异概率随着遗传代数的增长，逐渐增加，目的是进化后期注重变异运算，局部搜索能力强。 005.02sin *045.0+?? ? ??*=πK T P m （8） 其中，T 是进化代数，K 是总进化次数。 8. 终止条件判断。若已达到设定的最大遗传代数，则迭代终止，输出最优解；若不满足终止条件，则返回第4步，进行迭代寻优过程。 硕士生考查课程考试试卷 考试科目： 考生姓名：考生学号： 学院：专业： 考生成绩： 任课老师(签名) 考试日期：年月日午时至时 《MATLAB 教程》试题： A 、利用MATLA B 设计遗传算法程序，寻找下图11个端点最短路径，其中没有连接端点表示没有路径。要求设计遗传算法对该问题求解。 a e h k B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。 以上四题任选一题进行实验，并写出实验报告。 选择题目： B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 一、问题分析（10分） 这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。 在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。 二、实验原理与数学模型（20分） （1）试验原理： 用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。 遗传算法是一种现代智能算法，实际上它的功能十分强大，能够用于求解一些难以用常规数学手段进行求解的问题，尤其适用于求解多目标、多约束，且目标函数形式非常复杂的优化问题。但是遗传算法也有一些缺点，最为关键的一点，即没有任何理论能够证明遗传算法一定能够找到最优解，算法主要是根据概率论的思想来寻找最优解。因此，遗传算法所得到的解只是一个近似解，而不一定是最优解。 （2）数学模型 对于求解该问题遗传算法的构造过程： （1）确定决策变量和约束条件； 遗传算法解决简单问题 %主程序：用遗传算法求解y=200*exp(-0.05*x).*sin(x)在区间[-2,2]上的最大值clc; clear all; close all; global BitLength global boundsbegin global boundsend bounds=[-2,2]; precision=0.0001; boundsbegin=bounds(:,1); boundsend=bounds(:,2); %计算如果满足求解精度至少需要多长的染色体 BitLength=ceil(log2((boundsend-boundsbegin)'./precision)); popsize=50; %初始种群大小 Generationmax=12; %最大代数 pcrossover=0.90; %交配概率 pmutation=0.09; %变异概率 %产生初始种群 population=round(rand(popsize,BitLength)); %计算适应度，返回适应度Fitvalue和累计概率cumsump [Fitvalue,cumsump]=fitnessfun(population); Generation=1; while Generation yj1.m ：简单一元函数优化实例，利用遗传算法计算下面函数的最大值 0.2)*10sin()(+=x x x f π，∈x [-1, 2] 选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9， 最大遗传代数为25 译码矩阵结构：?????????? ??????? ???? ?=ubin lbin scale code ub lb len FieldD 译码矩阵说明： len – 包含在Chrom 中的每个子串的长度，注意sum(len)=length(Chrom)； lb 、ub – 行向量，分别指明每个变量使用的上界和下界； code – 二进制行向量，指明子串是怎样编码的，code(i)=1为标准二进制编码， code(i)=0则为格雷编码； scale – 二进制行向量，指明每个子串是否使用对数或算术刻度，scale(i)=0为算术 刻度，scale(i)=1则为对数刻度； lbin 、ubin – 二进制行向量，指明表示范围中是否包含每个边界，选择lbin=0或 ubin=0，表示从范围中去掉边界；lbin=1或ubin=1则表示范围中包含边界； 注：增加第22行：variable=bs2rv(Chrom, FieldD);否则提示第26行plot(variable(I), Y, 'bo'); 中variable(I)越界 yj2.m ：目标函数是De Jong 函数，是一个连续、凸起的单峰函数，它的M 文件objfun1包含在GA 工具箱软件中，De Jong 函数的表达式为： ∑ == n i i x x f 1 2 )(， 512512≤≤-i x 这里n 是定义问题维数的一个值，本例中选取n=20，求解 )(min x f ，程序主要变量： NIND （个体的数量）：＝40； MAXGEN （最大遗传代数）：=500； NV AR （变量维数）：=20； PRECI （每个变量使用多少位来表示）：=20； GGAP （代沟）：=0.9 注：函数objfun1.m 中switch 改为switch1，否则提示出错，因为switch 为matlab 保留字，下同！ yj3.m ：多元多峰函数的优化实例，Shubert 函数表达式如下，求)(min x f 【shubert.m 】 遗传算法经典学习Matlab代码 遗传算法实例: 也是自己找来的，原代码有少许错误，本人都已更正了，调试运行都通过了的。 对于初学者，尤其是还没有编程经验的非常有用的一个文件 遗传算法实例 % 下面举例说明遗传算法% % 求下列函数的最大值% % f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]% % 将x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为(10-0)/(2^10-1)≈0.01。% % 将变量域[0,10] 离散化为二值域[0,1023], x=0+10*b/1023, 其 中 b 是[0,1023] 中的一个二值数。% % % %--------------------------------------------------------------------------------------------------------------% %--------------------------------------------------------------------------------------------------------------% % 编程 %----------------------------------------------- % 2.1初始化(编码) % initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)， % 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name: initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元 为{0,1} 行数为popsize，列数为chromlength的矩阵， % roud对矩阵的每个单元进行圆整。这样产生的初始种群。 % 2.2 计算目标函数值 % 2.2.1 将二进制数转化为十进制数(1) %遗传算法子程序 %Name: decodebinary.m %产生[2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制 function pop2=decodebinary(pop) [px,py]=size(pop); %求pop行和列数 for i=1:py pop1(:,i)=2.^(py-i).*pop(:,i); end pop2=sum(pop1,2); %求pop1的每行之和 % 2.2.2 将二进制编码转化为十进制数(2) % decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置 function youhuafun D=code; N=50;%Tunable maxgen=50;%Tunable crossrate=0.5;%Tunable muterate=0.08;%Tunable generation=1; num=length(D); fatherrand=randint(num,N,3); score=zeros(maxgen,N); while generation<=maxgen ind=randperm(N-2)+2;%随机配对交叉 A=fatherrand(:,ind(1:(N-2)/2)); B=fatherrand(:,ind((N-2)/2+1:end)); %多点交叉 rnd=rand(num,(N-2)/2); ind=rnd tmp=A(ind); A(ind)=B(ind); B(ind)=tmp; %%两点交叉 %for kk=1:(N-2)/2 %rndtmp=randint(1,1,num)+1; %tmp=A(1:rndtmp,kk); %A(1:rndtmp,kk)=B(1:rndtmp,kk); %B(1:rndtmp,kk)=tmp; %end fatherrand=[fatherrand(:,1:2),A,B]; %变异 rnd=rand(num,N); ind=rnd[m,n]=size(ind); tmp=randint(m,n,2)+1; tmp(:,1:2)=0; fatherrand=tmp+fatherrand; fatherrand=mod(fatherrand,3); %fatherrand(ind)=tmp; %评价、选择 scoreN=scorefun(fatherrand,D);%求得N个个体的评价函数 score(generation,:)=scoreN; [scoreSort,scoreind]=sort(scoreN); sumscore=cumsum(scoreSort); sumscore=sumscore./sumscore(end); childind(1:2)=scoreind(end-1:end); for k=3:N tmprnd=rand; tmpind=tmprnd difind=[0,diff(t mpind)]; if~any(difind) difind(1)=1; end childind(k)=scoreind(logical(difind)); end fatherrand=fatherrand(:,childind); generation=generation+1; end %score maxV=max(score,[],2); minV=11*300-maxV; plot(minV,'*');title('各代的目标函数值'); F4=D(:,4); FF4=F4-fatherrand(:,1); FF4=max(FF4,1); D(:,5)=FF4; save DData D function D=code load youhua.mat %properties F2and F3 F1=A(:,1); F2=A(:,2); F3=A(:,3); if(max(F2)>1450)||(min(F2)<=900) error('DATA property F2exceed it''s range (900,1450]') end %get group property F1of data,according to F2value F4=zeros(size(F1)); for ite=11:-1:1 index=find(F2<=900+ite*50); F4(index)=ite; end D=[F1,F2,F3,F4]; function ScoreN=scorefun(fatherrand,D) F3=D(:,3); F4=D(:,4); N=size(fatherrand,2); FF4=F4*ones(1,N); FF4rnd=FF4-fatherrand; FF4rnd=max(FF4rnd,1); ScoreN=ones(1,N)*300*11; %这里有待优化 GATBX遗传算法工具箱函数及实例讲解 基本原理： 遗传算法是一种典型的启发式算法，属于非数值算法范畴。它是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。它是采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法的操作对象是一群二进制串（称为染色体、个体），即种群，每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应度函数的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化进行不断演化，直到满足期望的终止条件。 运算流程： Step 1：对遗传算法的运行参数进行赋值。参数包括种群规模、变量个数、交叉概率、变异概 率以及遗传运算的终止进化代数。 Step 2：建立区域描述器。根据轨道交通与常规公交运营协调模型的求解变量的约束条件，设置变量的取值范围。 Step 3：在Step 2的变量取值范围内，随机产生初始群体，代入适应度函数计算其适应度值。 Step 4：执行比例选择算子进行选择操作。 Step 5：按交叉概率对交叉算子执行交叉操作。 Step 6：按变异概率执行离散变异操作。 Step 7：计算Step 6得到局部最优解中每个个体的适应值，并执行最优个体保存策略。 Step 8：判断是否满足遗传运算的终止进化代数，不满足则返回Step 4，满足则输出运算结果。 运用遗传算法工具箱: 运用基于Matlab的遗传算法工具箱非常方便，遗传算法工具箱里包括了我们需要的各种函数库。目前，基于Matlab的遗传算法工具箱也很多，比较流行的有英国设菲尔德大学开发的遗传算法工具箱GATBX、GAOT以及Math Works公司推出的GADS。实际上，GADS就是大家所看到的Matlab中自带的工具箱。我在网上看到有问为什么遗传算法函数不能调用的问题，其实，主要就是因为用的工具箱不同。因为，有些人用的是GATBX带有的函数，但MATLAB自带的遗传算法工具箱是GADS，GADS当然没有GATBX里的函数，因此运行程序时会报错，当你用MATLAB来编写遗传算法代码时，要根据你所安装的工具箱来编写代码。 以GATBX为例，运用GATBX时，要将GATBX解压到Matlab下的toolbox文件夹里，同时，set path将GATBX文件夹加入到路径当中。 这块内容主要包括两方面工作：1、将模型用程序写出来（.M文件），即目标函数，若目标函数非负，即可直接将目标函数作为适应度函数。2、设置遗传算法的运行参数。包括：种群规模、变量个数、区域描述器、交叉概率、变异概率以及遗传运算的终止进化代数等等。 一个简单实用的遗传算 法c程序 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 一个简单实用的遗传算法c程序（转载） 2009-07-28 23:09:03 阅读418 评论0 字号：大中小 这是一个非常简单的遗传算法源代码，是由Denis Cormier (North Carolina State University)开发的，Sita (University of North Carolina at Charlotte)修正。代码保证尽可能少，实际上也不必查错。对一特定的应用修正此代码，用户只需改变常数的定义并且定义“评价函数”即可。注意代码的设计是求最大值，其中的目标函数只能取正值；且函数值和个体的适应值之间没有区别。该系统使用比率选择、精华模型、单点杂交和均匀变异。如果用Gaussian变异替换均匀变异，可能得到更好的效果。代码没有任何图形，甚至也没有屏幕输出，主要是保证在平台之间的高可移植性。读者可以从,目录 coe/evol中的文件中获得。要求输入的文件应该命名为‘’；系统产生的输出文件为‘’。输入的文件由几行组成：数目对应于变量数。且每一行提供次序——对应于变量的上下界。如第一行为第一个变量提供上下界，第二行为第二个变量提供上下界，等等。 /**************************************************************************/ /* This is a simple genetic algorithm implementation where the */ /* evaluation function takes positive values only and the */ /* fitness of an individual is the same as the value of the */ /* objective function */ /**************************************************************************/ #include <> #include <> #include <> /* Change any of these parameters to match your needs */ #define POPSIZE 50 /* population size */ % f(x)=11*sin(6x)+7*cos(5x),0<=x<=2*pi; %%初始化参数 L=16;%编码为16位二进制数 N=32;%初始种群规模 M=48;%M个中间体，运用算子选择出M/2对母体，进行交叉；对M个中间体进行变异 T=100;%进化代数 Pc=0.8;%交叉概率 Pm=0.03;%%变异概率 %%将十进制编码成16位的二进制，再将16位的二进制转成格雷码 for i=1:1:N x1(1,i)= rand()*2*pi; x2(1,i)= uint16(x1(1,i)/(2*pi)*65535); grayCode(i,:)=num2gray(x2(1,i),L); end %% 开始遗传算子操作 for t=1:1:T y1=11*sin(6*x1)+7*cos(5*x1); for i=1:1:M/2 [a,b]=min(y1);%找到y1中的最小值a，及其对应的编号b grayCodeNew(i,:)=grayCode(b,:);%将找到的最小数放到grayCodeNew中grayCodeNew(i+M/2,:)=grayCode(b,:);%与上面相同就可以有M/2对格雷码可以作为母体y1(1,b)=inf;%用来排除已找到的最小值 end for i=1:1:M/2 p=unidrnd(L);%生成一个大于零小于L的数，用于下面进行交叉的位置if rand() 遗传算法程序示例 %% I. 清空环境变量 %optimtool solver 中选择GA %添加gaot工具箱 clear all clc %% II. 绘制函数曲线 x = 0:0.01:9; y = x + 10*sin(5*x)+7*cos(4*x); figure plot(x, y) xlabel('自变量') ylabel('因变量') title('y = x + 10*sin(5*x) + 7*cos(4*x)') grid %% III. 初始化种群 initPop = initializega(50,[0 9],'fitness'); %种群大小；变量变化范围；适应度函数的名称 %看一下initpop 第二列代表适应度函数值 %% IV. 遗传算法优化 [x endPop bpop trace] = ga([0 9],'fitness',[],initPop,[1e-6 1 1],'maxGenTerm',25,... 'normGeomSelect',0.08,'arithXover',2,'nonUnifMutation',[2 25 3]); %变量范围上下界；适应度函数；适应度函数的参数；初始种群；精度和显示方式；终止函数的名称； %终止函数的参数；选择函数的名称；选择函数的参数；交叉函数的名称；交叉函数的参数；变异函数的 %名称；变异函数的参数 % X 最优个体endpop 优化终止的最优种群bpop 最优种群的进化轨迹trace 进化迭代过程中 %最优的适应度函数值和适应度函数值矩阵 %% V. 输出最优解并绘制最优点 x hold on plot (endPop(:,1),endPop(:,2),'ro') matlab遗传算法工具箱函数及实例讲解 核心函数： (1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始种群的生成函数 【输出参数】 pop--生成的初始种群 【输入参数】 num--种群中的个体数目 bounds--代表变量的上下界的矩阵 eevalFN--适应度函数 eevalOps--传递给适应度函数的参数 options--选择编码形式(浮点编码或是二进制编码)[precision F_or_B], 如 precision--变量进行二进制编码时指定的精度 F_or_B--为1时选择浮点编码，否则为二进制编码,由precision指定精度) (2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,... termFN,termOps,selectFN,selectOps,xOverFNs,xOverO ps,mutFNs,mutOps)--遗传算法函数 【输出参数】 x--求得的最优解 endPop--最终得到的种群 bPop--最优种群的一个搜索轨迹 【输入参数】 bounds--代表变量上下界的矩阵 evalFN--适应度函数 evalOps--传递给适应度函数的参数 startPop-初始种群 opts[epsilon prob_ops display]--opts(1:2)等同于initializega 的options参数，第三个参数控制是否输出，一般为0。如[1e-6 1 0] termFN--终止函数的名称,如['maxGenTerm'] termOps--传递个终止函数的参数,如[100] selectFN--选择函数的名称,如['normGeomSelect'] selectOps--传递个选择函数的参数,如[0.08] xOverFNs--交叉函数名称表，以空格分开，如['arithXover heuristicXover simpleXover'] xOverOps--传递给交叉函数的参数表，如[2 0;2 3;2 0] mutFNs--变异函数表，如['boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation'] mutOps--传递给交叉函数的参数表,如[4 0 0;6 100 3;4 100 3;4 0 0] C语言遗传算法代码 以下为遗传算法的源代码，计算一元代函数的代码和二元函数的代码以+++++++++++++++++++++++++++++++++++++为分割线分割开来，请自行选择适合的代码，使用时请略看完代码的注释，在需要更改的地方更改为自己需要的代码。 +++++++++++++++++++++++++++++++一元函数代码++++++++++++++++++++++++++++ #include matlab遗传算法工具箱函数及实例讲解（转引） 核心函数：? (1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始种群的生成函数?【输出参数】? ?pop--生成的初始种群?【输入参数】? ?num--种群中的个体数目? ?bounds--代表变量的上下界的矩阵? ?eevalFN--适应度函数? ?eevalOps--传递给适应度函数的参数? ?options--选择编码形式(浮点编码或是二进制编码)[precision F_or_B],如? precision--变量进行二进制编码时指定的精度? F_or_B--为1时选择浮点编码，否则为二进制编码,由precision指定精度)? (2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts.? ?termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs ,mutOps)--遗传算法函数?【输出参数】? x--求得的最优解? endPop--最终得到的种群? bPop--最优种群的一个搜索轨迹?【输入参数】? bounds--代表变量上下界的矩阵? evalFN--适应度函数? evalOps--传递给适应度函数的参数? startPop-初始种群? opts[epsilon prob_ops display]--opts(1:2)等同于initializega 的options参数，第三个参数控制是否输出，一般为0。如[1e-6 termFN--终止函数的名称,如['maxGenTerm']? termOps--传递个终止函数的参数,如[100]? selectFN--选择函数的名称,如['normGeomSelect']? selectOps--传递个选择函数的参数,如[0.08]? xOverFNs--交叉函数名称表，以空格分开，如['arithXover heuristicXover simpleXover']? xOverOps--传递给交叉函数的参数表，如[2 0;2 3;2 0]? mutFNs--变异函数表，如['boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation']? mutOps--传递给交叉函数的参数表,如[4 0 0;6 100 3;4 100 3;4 0 0]?注意】matlab工具箱函数必须放在工作目录下?【问题】求f(x)=x+10*sin(5x)+7*cos(4x)的最大值，其中0=x=9?【分析】选择二进制编码，种群中的个体数目为10，二进制编码长度为20，交叉概率为0.95,变异概率为0.08?【程序清单】? 遗传算法的C语言程序案例 一、说明 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．举个例子，输入初始变量后，用y= (x1*x1)+(x2*x2)，其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 4．程序流程图 5．类型定义 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 worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 6．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个遗传算法的c语言程序
遗传算法经典MATLAB代码
自适应遗传算法讲解学习
MATLAB课程遗传算法实验报告及源代码
遗传算法MATLAB完整代码(不用工具箱)
遗传算法求解实例
遗传算法经典MATLAB代码资料讲解
基于遗传算法的matlab源代码
遗 传 算 法 详 解 ( 含 M A T L A B 代 码 )
一个简单实用的遗传算法c程序完整版
遗传算法Matlab程序
遗传算法程序示例
(实例)matlab遗传算法工具箱函数及实例讲解
遗传算法C语言源代码(一元函数和二元函数)
遗 传 算 法 详 解 ( 含 M A T L A B 代 码 )
遗传算法的C语言程序案例
相关主题
文本预览