genetic

遗传算法（GeneticAlgorithm）

1、遗传算法的基本思想

遗传算法（GeneticAlgorithm,GA）是模拟达尔⽂⽣物进化论的⾃然选择和遗传学机理的⽣物进化过程的计算模型，是⼀种通过模拟⾃然

进化过程搜索最优解的⽅法。

遗传算法（GeneticAlgorithm,GA）起源于对⽣物系统所进⾏的计算机模拟研究。它是模仿⾃然界⽣物进化机制发展起来的随机全局搜索

和优化⽅法，借鉴了达尔⽂的进化论和孟德尔的遗传学说。其本质是⼀种⾼效、并⾏、全局搜索的⽅法，能在搜索过程中⾃动获取和积累有

关搜索空间的知识，并⾃适应地控制搜索过程以求得最佳解。

遗传算法(GeneticAlgorithm)遵循⾃然界“适者⽣存、优胜劣汰”的原则，是⼀类借鉴⽣物界⾃然选择和⾃然遗传机制的随机化搜索算

法。

达尔⽂进化论的主要观点是：物竞天择，适者⽣存。遗传算法（GeneticAlgorithm）的基本思想就是模仿⾃然进化过程，通过对群体中具

有某种结构形式的个体进⾏遗传操作，从⽽⽣成新的群体，逐渐逼近最优解。在求解过程中设定⼀个固定规模的种群，种群中的每个个体都

表⽰问题的⼀个可能解，个体适应环境的程度⽤适应度函数判断，适应度差的个体被淘汰，适应度好的个体得以继续繁衍，繁衍的过程中可

能要经过选择、交叉、变异，形成新的族群，如此往复，最后得到更多更好的解。

2、遗传算法的主要步骤

（1）编码：将问题的候选解⽤染⾊体表⽰，实现解空间向编码空间的映射过程。遗传算法不直接处理解空间的决策变量，⽽是将其转换成

由基因按⼀定结构组成的染⾊体。编码⽅式有很多，如⼆进制编码、实数向量编码、整数排列编码、通⽤数据结构编码等等。本⽂将采⽤⼆

进制编码的⽅式，将⼗进制的变量转换成⼆进制，⽤0和1组成的数字串模拟染⾊体，可以很⽅便地实现基因交叉、变异等操作。

（2）种群初始化：产⽣代表问题可能潜在解集的⼀个初始群体（编码集合）。种群规模设定主要有以下⽅⾯的考虑：从群体多样性⽅⾯考

虑，群体越⼤越好，避免陷⼊局部最优；从计算效率⽅⾯考虑，群体规模越⼤将导致计算量的增加。应该根据实际问题确定种群的规模。产

⽣初始化种群的⽅法通常有两种：⼀是完全随机的⽅法产⽣；⼆是根据先验知识设定⼀组必须满⾜的条件，然后根据这些条件⽣成初始样

本。

（3）计算个体适应度：利⽤适应度函数计算各个个体的适应度⼤⼩。适应度函数（FitnessFunction）的选取直接影响到遗传算法的收敛

速度以及能否找到最优解，因为在进化搜索中基本不利⽤外部信息，仅以适应度函数为依据，利⽤种群每个个体的适应程度来指导搜索。

（4）进化计算：通过选择、交叉、变异，产⽣出代表新的解集的群体。选择（lection）：根据个体适应度⼤⼩，按照优胜劣汰的原则，

淘汰不合理的个体；交叉（crossover）：编码的交叉重组，类似于染⾊体的交叉重组；变异（mutation）：编码按⼩概率扰动产⽣的变

化，类似于基因突变。

（5）解码：末代种群中的最优个体经过解码实现从编码空间向解空间的映射，可以作为问题的近似最优解。这是整个遗传算法的最后⼀

步，经过若⼲次的进化过程，种群中适应度最⾼的个体代表问题的最优解，但这个最优解还是⼀个由0和1组成的数字串，要将它转换成⼗

进制才能供我们理解和使⽤。

3、遗传算法的参数设计原则

（1）种群的规模

种群不宜过⼤也不宜过⼩。种群规模的⼀个建议值为0-100。

（2）变异概率

变异概率也不宜过⼤或者过⼩。⼀般取值为0.0001-0.2。

（3）交换概率

不宜过⼤或者过⼩。⼀般取值为0.4-0.99。

（4）进化代数

不宜过⼤或者过⼩。⼀般取值为100-500。

（5）种群初始化

初始种群的⽣成是随机的。在初始种群的赋予之前，尽量进⾏⼀个⼤概的区间估计，避免初始种群分布在远离最优解的编码空间，导致遗传

算法的搜索范围受到限制。

4、代码实现

（1）主函数main.m

functionmain()

clear;

clc;

%种群⼤⼩

popsize=100;

%⼆进制编码长度

chromlength=10;

%交叉概率

pc=0.6;

%变异概率

pm=0.001;

%初始种群

pop=initpop(popsize,chromlength);

fori=1:100

%计算适应度值（函数值）

objvalue=cal_objvalue(pop);

fitvalue=objvalue;

%选择操作

newpop=lection(pop,fitvalue);

%交叉操作

newpop=crossover(newpop,pc);

%变异操作

newpop=mutation(newpop,pm);

%更新种群

pop=newpop;

%寻找最优解

[bestindividual,bestfit]=best(pop,fitvalue);

x2=binary2decimal(bestindividual);

x1=binary2decimal(newpop);

y1=cal_objvalue(newpop);

ifmod(i,10)==0

figure;

fplot('10*sin(5*x)+7*abs(x-5)+10',[010]);

holdon;

plot(x1,y1,'*');

title(['迭代次数为n='num2str(i)]);

%plot(x1,y1,'*');

end

end

fprintf('ThebestXis--->>%5.2fn',x2);

fprintf('ThebestYis--->>%5.2fn',bestfit);

（2）⼆进制种群⽣成的⽅法initpop.m

%初始化种群⼤⼩

%输⼊变量：

%popsize：种群⼤⼩

%chromlength：染⾊体长度-->>转化的⼆进制长度

%输出变量：

%pop：种群

functionpop=initpop(popsize,chromlength)

pop=round(rand(popsize,chromlength));

%rand(3,4)⽣成3⾏4列的0-1之间的随机数

%rand(3,4)

%

%ans=

%

%0.81470.91340.27850.9649

%0.90580.63240.54690.1576

%0.12700.09750.95750.9706

%round就是四舍五⼊

%round(rand(3,4))=

%1101

%1110

%0011

%所以返回的种群就是每⾏是⼀个个体，列数是染⾊体长度

（3）把⼆进制返回对应的⼗进制binary2decimal.m

%⼆进制转化成⼗进制函数

%输⼊变量：

%⼆进制种群

%输出变量

%⼗进制数值

functionpop2=binary2decimal(pop)

[px,py]=size(pop);

fori=1:py

pop1(:,i)=2.^(py-i).*pop(:,i);

end

%sum(.,2)对⾏求和，得到列向量

temp=sum(pop1,2);

pop2=temp*10/1023;

（4）计算适应度函数cal_objvalue.m

%计算函数⽬标值

%输⼊变量：⼆进制数值

%输出变量：⽬标函数值

function[objvalue]=cal_objvalue(pop)

x=binary2decimal(pop);

%转化⼆进制数为x变量的变化域范围的数值

objvalue=10*sin(5*x)+7*abs(x-5)+10;

（5）选择新的个体lection.m

%如何选择新的个体

%输⼊变量：pop⼆进制种群，fitvalue：适应度值

%输出变量：newpop选择以后的⼆进制种群

function[newpop]=lection(pop,fitvalue)

%构造轮盘

[px,py]=size(pop);

totalfit=sum(fitvalue);

p_fitvalue=fitvalue/totalfit;

p_fitvalue=cumsum(p_fitvalue);%概率求和排序

ms=sort(rand(px,1));%从⼩到⼤排列

fitin=1;

newin=1;

whilenewin<=px

if(ms(newin))

newpop(newin,:)=pop(fitin,:);

newin=newin+1;

el

fitin=fitin+1;

end

end

（6）交叉crossover.m

%交叉变换

%输⼊变量：pop：⼆进制的⽗代种群数，pc：交叉的概率

%输出变量：newpop：交叉后的种群数

function[newpop]=crossover(pop,pc)

[px,py]=size(pop);

newpop=ones(size(pop));

fori=1:2:px-1

if(rand

cpoint=round(rand*py);

newpop(i,:)=[pop(i,1:cpoint),pop(i+1,cpoint+1:py)];

newpop(i+1,:)=[pop(i+1,1:cpoint),pop(i,cpoint+1:py)];

el

newpop(i,:)=pop(i,:);

newpop(i+1,:)=pop(i+1,:);

end

end

（7）变异mutation.m

%关于编译

%函数说明

%输⼊变量：pop：⼆进制种群，pm：变异概率

%输出变量：newpop变异以后的种群

function[newpop]=mutation(pop,pm)

[px,py]=size(pop);

newpop=ones(size(pop));

fori=1:px

if(rand

mpoint=round(rand*py);

ifmpoint<=0;

mpoint=1;

end

newpop(i,:)=pop(i,:);

ifnewpop(i,mpoint)==0

newpop(i,mpoint)=1;

elnewpop(i,mpoint)==1

newpop(i,mpoint)=0;

end

elnewpop(i,:)=pop(i,:);

end

end

（8）选择最优个体best.m

%求最优适应度函数

%输⼊变量：pop:种群，fitvalue:种群适应度

%输出变量：bestindividual:最佳个体，bestfit:最佳适应度值

function[bestindividual,bestfit]=best(pop,fitvalue)

[px,py]=size(pop);

bestindividual=pop(1,:);

bestfit=fitvalue(1);

fori=2:px

iffitvalue(i)>bestfit

bestindividual=pop(i,:);

bestfit=fitvalue(i);

end

end

5、遗传算法应⽤案例（----待续）