第二章 遗传算法的基本原理2.1 遗传算法的基本描述2.1.1 全局优化问题全局优化问题的定义：给定非空集合S 作为搜索空间，f ：S —>R 为目标函数，全局优化问题作为任务)(max x f Sx ∈给出，即在搜索空间中找到至少一个使目标函数最大化的点。

全局最大值（点）的定义：函数值+∞<=)(**x f f 称为一个全局最大值，当且仅当x ∀S x ∈，(ρi i b a <，i 12）定义适应度函数f(X)；3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。

4）生成初始种群P ；5）计算群体中各个体的适应度值；6）按照遗传策略，将遗传算子作用于种群，产生下一代种群；7）迭代终止判定。

遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。

2.1.3 遗传编码由于GA 计算过程的鲁棒性，它对编码的要求并不苛刻。

原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。

由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。

对于给定的优化问题，由GA 个体的表现型集合做组成的空间称为问题（参数）空间，由GA 基因型个体所组成的空间称为GA 编码空间。

遗传算子在GA 编码空间中对位串个体进行操作。

定义：由问题空间向GA 编码空间的映射称为编码，而有编码空间向问题空间的映射成为译码。

1）2）3）它们对1）2）k =1,2,…,K; l =1,2,…,L; K=2L其中，个体的向量表示为),,,(21kL k k k a a a a =，其字符串形式为kL k k k a a a s 21=，s k 称为个体a k 对应的位串。

表示精度为)12/()(--=∆L u v x 。

将个体又位串空间转换到问题空间的译码函数],[}1,0{:v u L →Γ的公式定义为：对于n 维连续函数),,2,1](,[),,,,(),(21n i v u x x x x x x f i i i n =∈=，各维变量的二进制编码位串的长度为l i ,那么x 的编码从左到右依次构成总长度为∑==ni i l L 1的二进制编码位串。

相应的GA 编码空间为：},,,{21K L a a a S =，K=2L该空间上的个体位串结构为对于给定的二进制编码位串s k ,位段译码函数的形式为)2(),,,(--+=Γ=i i l j l i l i i i i i i a u v u a a a x ， i = 1,2,…,n 模的设定，对遗传算法性能有着重要的影响。

这中间包括两个问题：1）初始群体如何设定；2）进化过程中各代的规模如何维持？1． 初始群体的设定遗传算法中初始群体中的个体是按一定的分布随机产生的，一般来讲，初始群体的设定可以采用如下的策略：1） 根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。

2） 先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。

这一过程不断重复，直到初始群体中个体数达到了预定的规模。

2．群体规模的设定根据模式定理，若群体规模为M，则遗传操作可从这M个个体中生成和检测O(M3)个模式，并在此基础上不断形成和优化积木块，直到找到最优解。

显然M越大，遗传操作处理的模式就越多，生成有意义的积木块并逐渐进化为最优解的机会就越高。

换句话说，群体规模越大，群体中个体的多样性越高，算法陷入局部最优解的危险就越小。

另外，群体规模太小，会使遗传算法的搜索空间分布范围有限，因而搜索有可能停止在未成熟阶段，引起未成熟收敛（premature convergence）现象。

但是，从计算效率来看，群体规模越大，其适应度评价次数越多，计算量也就越大，从而影响算法的效率。

2L/2K代中g(x)另以方面，在遗传进化过程中，虽然群体中个体多样性尚存在，但往往会出现群体的平均适应度已接近最佳个体适应度，这时，个体间的竞争力相似，最佳个体和其它个体在选择过程中有几乎相等的选择机会，从而使有目标的优化过程趋于无目标大的随机搜索过程。

对未成熟收敛现象，应设法降低某些异常个体的竞争力，这可以通过缩小相应的适应度值来实现。

对于随机漫游现象，应设法提高个体间的竞争力差距，这可以通过放大相应的适应度值来实现。

这种适应度的缩放调整称为适应度定标。

1）线性定标（linear scaling）f’ = af + b2）σ截断（sigma truncation ）3） 乘幂标f ’ = f K4） 指数定标f ’ = exp(-bf)2.1.5 遗传算子遗传操作是模拟生物基因遗传的操作。

包括三个基本遗传算子（genetic operator ）：选择，交叉和变异。

这三个遗传算子具有一些特点：1、（mating(6)选择方差(selection variance) 将正规高斯分布应用于选择方法，期望种群适应度的方差。

1） 适应度比例选择是最基本的选择方法，其中每个个体被选择的期望数量与其适应度值和群体平均适应度值的比例有关，通常采用轮盘赌（roulette wheel ）方式实现。

这种方式首先计算每个个体的适应度值，然后计算出此适应度值在群体适应度值总和中所占的比例，表示该个体在选择过程中被选中的概率。

选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想。

对于给定的规模为n 的群体},,,{21n a a a P =，个体P a j ∈的适应度值为)(j a f ，其选择概率为：经过选择操作生成用于繁殖的配对池，其中父代种群中个体生存的期望数目为：当群体中个体适应度值的差异非常大时，最佳个体与最差个体被选择的概率之比（选择压力）业将按指数增长。

最佳个体在下一代的生存机会将显着增加，而最差个体的生存机会将被剥夺。

当前群体中的最佳个体将快速充满整个群体，导致群体的多样性迅速降低，GA 也就过早地丧失了进化能力。

这是适应度比例选择容易出现地问题。

2）Boltzmann 选择在群体进化过程中，不同阶段需要不同地选择压力。

早期阶段选择压力较小，我们希望较差地个体也又一定地生存机会，使得群体保持较高地多样性；后期阶段，选择压力较是控制(f +η，即+η)，故现由n n j j =∑=1η可以导出2=+-+ηη。

要求0,0≥≥-ηi p ，故21≤≤+η。

当0,2==-+ηη时，即最差个体在下一代生存的期望数量为0，群体选择压力最大；当1==-+ηη时，选择方式为按均匀分布的随机选择，群体选择压力最小。

4）联赛选择（tournament selection ）联赛选择的基本思想是从当前群体中随机选择一定数量的个体（放回或者不放回），将其中适应值最大的个体放入配对池中。

反复执行这一过程，直到配对池中的个体数量达到设定的值。

联赛规模用q 表示，也称q-联赛选择。

联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。

根据大量实验总结，联赛规模一般取q=2。

联赛选择的选择概率也是比较容易控制的，实际计算中也经常采用，适用于在GA迭代过程中动态调整选择概率，将进化效果与群体选择压力联系起来。

研究证明，当群体规模比较大时，联赛选择与排序选择的个体选择概率基本相同。

5）精英选择从GA的整个选择策略来讲，精英选择时群体收敛导优化问题全局最优解的一种基本保障。

如果下一代群体的最佳个体适应度值小于当前群体最佳个体的适应度值，则将当前群体最佳个体或者适应度值大于下一代最佳个体适应度值的多个个体直接复制到下一代，随机替代和替代最差的下一代群体中的相应数量的个体。

（2、k作为一点交叉是由Holland提出的最基础的一种交叉方式。

一点交叉操作的信息量比较小，交叉点位置的选择可能带来较大的偏差（position bias）。

按照Holland的思想，一点交叉算子不利于长距模式的保留和重组，而且位串末尾的重要基因总是被交换（尾点效应，end-point effect）。

故实际应用中采用较多的是两点交叉。

位串A：1 1 0 1| 1 0 1 0位串B：1 0 1 1| 0 1 0 1位串A’：1 1 0 1 0 1 0 1位串B’：1 0 1 1 1 0 1 02）两点交叉（two-point crossover）位串A：1 1| 0 1 1| 0 1 0位串B：1 0| 1 1 0| 1 0 1位串A’：1 1| 1 1 0| 0 1 0位串B’：1 0| 0 1 1| 1 0 13）多点交叉（multi--point crossover）多点交叉是上述两种交叉的推广，有时又被称为广义交叉。

一般来讲，多点交叉较少采用，因为它影响遗传算法的在线和离线性能。

多点交叉不利于有效保存重要的模式。

3、中相当逆转操作首先在个体位串上随机地选择两个点，位串染色体被这两个点分成三段，将中间段的左右顺序倒转过来与另两段相连，形成新的个体位串。

比如：长度为10的二进制位串，其中下划线标示的等位基因为重要基因：10^111011^01（^是倒位位置）经倒位后变为1011011101。

新的位串中重要基因更为靠近，被单点交叉算子分离的可能性大大降低了。

逆转算子一般要求采用类似于乱序编码的带基因位标号的染色体结构。

比如，长度为10的位串：位串： 1 0 1 1 1 0 1 1 0 1基因位编号：1 2 3 4 5 6 7 8 9 10按照上述方法实施逆转操作后，编号也随之翻转：位串： 1 0 1 1 0 1 1 1 0 1基因位编号：1 2 8 7 6 5 4 3 9 10这样倒位操作就不会影响个体位串的适应值计算。

但是，逆转算子对交叉算子有一定影响。

考虑下列A ，B 位串之间的单点交叉： 位串A ：1 0 1 1 1 0 1 1 0 1基因位编号：1 2 3 4 5 6 7 8 9 10对于某些问题要求采用具有显着物理含义的特殊编码方式，可以根据GA 进化的困难程度适当应用。

4、变异（mutation ）算子变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。

在遗传算法中，变异算子通过按变异概率p m 随机反转某位等位基因的二进制字符值来实现。

对于给定的染色体位串L a a a s 21=，具体如下：生成新的个体L a a a s ''''21 =。

其中，x i 是对应于每一个基因位产生的均匀随机变量，]0,1[∈i x 。

变异操作作用于个体位串的等位基因上，由于变异概率比较小，在实施过程中一些个体可能根本不发生一次变异，造成大量计算资源的浪费。

因此，在GA 具体应用中，我们可以采用一种变通措施，首先进行个体层次的变异发生的概率判断，然后再实施基因层次上的变异操作。