遗传算法的主要步骤

为了使用遗传算法来解决优化问题，准备工作分为以下四步［56，57，61］。

7.4.1 确定问题的潜在解的遗传表示方案

在基本的遗传算法中，表示方案是把问题的搜索空间中每个可能的点表示为确定长度的特征串（通常是二进制串）。表示方案的确定需要选择串长l和字母表规模k。在染色体串和问题的搜索空间中的点之间选择映射有时容易实现，有时又非常困难。选择一个便于遗传算法求解问题的表示方案经常需要对问题有深入的了解。

7.4.2 确定适应值的度量

适应值度量为群体中每个可能的确定长度的特咐伍征串指定一个适应值，它经常是问题本身所具有的。适应值度量必须有能力计算搜索空间中每个确定长度的特征串的适应值。

7.4.3 确定控制该算法的参数和变量

控制遗传算法的主要参数有群体规模Pop-Size、算法执行的最大代数N-Gen、交叉概率Pc、变异概率Pm和选择策略R等参数。

（1）群体规模Pop-Size。群体规模影响到遗传算法的最终性能和效率。当规模太小时，由于群体对大部分超平面只给出了不充分的样本量，所以得到的结果一般不佳。大的群体更有希望包含出自大量超平面的代表，从而可以阻止过早收敛到局部最优解；然而群体越大，每一代需要的计算量也就越多，这有可能导致一个无法接受的慢收敛率。

（2）交叉率Pc。交叉率控制交叉算子应用的频率，在每代新的群体中，有Pc·Pop-Size个串实行交叉。交叉率越高，群体中串的更新就越快。如果交叉率过高，相对选择能够产生的改进而言，高性能的串被破坏得更快。如果交叉率过低，搜索会由于太小的探查率而可能停滞不前。

（3）变异率Pm。变异是增加群体多样性的搜索算子，每次选择之后，新的群体中的每个串的每一位以相等的变异率进行随机改变。对于M进制串，就是相应的位从1变为0或0变为1。从而每代大约发生Pm·Pop-Size·L次变异，其中L为串长。一个低水平的变异率足以防止整个群体中任一给定位保持永远收敛到单一的值。高水平的变异率产生的实质是随机搜索。

比起选择和交叉，变异在遗传算法中是次要的，它在恢复群体中失去的多样性方面具有潜在的作用。例如，在遗传算法执行的开始阶段，串中一个特定位上的值1可能与好的性能紧密联系，也就是说从搜索空间中某些初始随机点开始，返大在那个位上的值1可能一致地产生适应性度量好的值。因为越好的适应值与串中那个位上的值1相联系，复制作用就越会使群体的遗传多样性损失。当达到一定程度时，值0会从整个群体中的那个位上消失，然而全局最优解可能在串中那个位上是0。一旦搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好衡世或是达到全局最优解所需的。这仅仅是一种说明搜索空间是非线性的方式，这种情形不是假定的，因为实际上所有我们感兴趣的问题都是非线性的。变异作用提供了一个恢复遗传多样性的损失的方法。

（4）选择策略R。有两种选择策略。一是利用纯选择，即当前群体中每个点复制的次数比与点的性能值成比例。二是利用最优选择，即首先执行纯选择，且具有最好性能的点总是保留到下一代。在缺少最优选择的情况下，由于采样误差、交叉和变异，最好性能的点可能会丢失。

通过指定各个参数Pop-Size、Pc、Pm和R的值，可以表示一个特定的遗传算法。

7.4.4 确定指定结果的方法和停止运行的准则

当遗传的代数达到最大允许代数时，就可以停止算法的执行，并指定执行中得到的最好结果作为算法的结果。

基本的遗传算法

1）随机产生一个由固定长度字符串组成的初始群体。

2）对于字符串群体，迭代地执行下述步骤，直到选择标准被满足为止。

①计算群体中的每个个体字符串的适应值；

②实施下列三种 *** 作（至少前两种）来产生新的群体， *** 作对象的选取基于与适应度成比例的概率。

选择：把现有的个体串按适应值复制到新的群体中。

交叉：通过遗传重组随机选择两个现有的子串进行遗传重组，产生两个新的串。

变异：将现有串中某一位的字符随机变异产生一个新串。

3）把在后代中出现的最好适应值的个体串指定为遗传算法运行的结果。这一结果可以是问题的解（或近似解）。

基本的遗传算法流程图如图7-1所示。

遗传 *** 作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传 *** 作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的 *** 作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传 *** 作可使问题的解，一代又一代地优化，并逼近最优解。

遗传 *** 作包括以下三个基本遗传算子(genetic operator):选择(selection)；交叉(crossover)；变异(mutation)。这三个遗传算子有如下特点：

个体遗传算子的 *** 作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化 *** 作和传统的随机搜索方法是有区别的。遗传 *** 作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。

遗传 *** 作的效果和上述三个遗传算子所取的 *** 作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。 从群体中选择优胜的个体，淘汰劣质个体型野唤的 *** 作叫选择。选择算子有时又称为再生算子(reproduction operator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择 *** 作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种：适应度比例方法、随机遍历抽样法、局部选择法。

其中轮盘赌选择法 （roulette wheel selection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率，为遗传算法

显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个[0，1]之脊运间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉 *** 作。 在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传 *** 作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而卜凯生成新个体的 *** 作。通过交叉，遗传算法的搜索能力得以飞跃提高。

交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法：

a)实值重组（real valued recombination）

1)离散重组（discrete recombination）

2)中间重组（intermediate recombination）

3)线性重组（linear recombination）

4)扩展线性重组（extended linear recombination）。

b)二进制交叉（binary valued crossover）

1)单点交叉（single-point crossover）

2)多点交叉（multiple-point crossover）

3)均匀交叉（uniform crossover）

4)洗牌交叉（shuffle crossover）

5)缩小代理交叉（crossover with reduced surrogate）。

最常用的交叉算子为单点交叉(one-point crossover)。具体 *** 作是:在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子：

个体A：1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新个体

个体B：0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新个体 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：

a)实值变异

b)二进制变异。

一般来说，变异算子 *** 作的基本步骤如下：

a)对群中所有个体以事先设定的变异概率判断是否进行变异

b)对进行变异的个体随机选择变异位进行变异。

遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。

遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的 *** 作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合.是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异 *** 作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异 *** 作有可能破坏这些积木块。如何有效地配合使用交叉和变异 *** 作，是目前遗传算法的一个重要研究内容。

基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动(以变异概率P.做变动)，(0，1)二值码串中的基本变异 *** 作如下：

基因位下方标有*号的基因发生变异。

变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值，一般取0.001－0.1。 当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。

我发一些他们的源程序你，都是我在文献中搜索总结出来的：

%

下面举例说明遗传族裤算法

%

%

求下列兆庆简函数的最大值

%

%

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)

%

decodechrom.m函数的功能是将染色体(或二进制编码差肆)转换为十进制，参数spoint表示待解码的二进制串的起始位置

%

(对于多个变量而言，如有两个变量，采用20为表示，每个变量10为，则第一个变量从1开始，另一个变量从11开始。本例为1)，

%

参数1ength表示所截取的长度（本例为10）。

%遗传算法子程序

%Name:

decodechrom.m

%将二进制编码转换成十进制

function

pop2=decodechrom(pop,spoint,length)

pop1=pop(:,spoint:spoint+length-1)

pop2=decodebinary(pop1)

%

2.4

选择复制

%

选择或复制 *** 作是决定哪些个体可以进入下一代。程序中采用赌轮盘选择法选择，这种方法较易实现。

%

根据方程

pi=fi/∑fi=fi/fsum

，选择步骤：

%

1）

在第

t

代，由（1）式计算

fsum

和

pi

%

2）

产生

{0,1}

的随机数

rand(

.)，求

s=rand(

.)*fsum

%

3）

求

∑fi≥s

中最小的

k

，则第

k

个个体被选中

%

4）

进行

N

次2）、3） *** 作，得到

N

个个体，成为第

t=t+1

代种群

%遗传算法子程序

%Name:

selection.m

%选择复制

function

[newpop]=selection(pop,fitvalue)

totalfit=sum(fitvalue)

%求适应值之和

fitvalue=fitvalue/totalfit

%单个个体被选择的概率

fitvalue=cumsum(fitvalue)

%如

fitvalue=[1

2

3

4]，则

cumsum(fitvalue)=[1

3

6

10]

[px,py]=size(pop)

ms=sort(rand(px,1))

%从小到大排列

fitin=1

newin=1

while

newin<=px

if(ms(newin))

评论

0

0

加载更多

---