2遗传算法的基本原理.docx

第二章遗传算法的基本原理2.1遗传算法的基本描述2. 1. 1全局优化问题全局优化问题的定义：给定非空集合S作为搜索空间，f： S-＞R为目标函数, 全局优化问题作为任务max/（x）给出，即在搜索空间中找到至少一个使目标函 xeS数最大化的点全局最大值（点）的定义：函数值＜ +00称为一个全局最大值，当且仅当Vx G S /（X）＜ /（X*）成立吋，X* € S被称为一个全局最大值点（全局最大解）局部极大值与局部极大值点（解）的定义：假设在S上给定了某个距离度量°,如果对X 九＞0,使得对X/xwS,P（X,X）＜ £• =＞ /（X）＜ /（X ）,则称x'为一个局部极大值点，f（xj ）为一个局部极 大值当目标函数有多个局部极大点时，被称为多峰或多模态函数 （multi-modality function）主要考虑两类搜索空间：伪布尔优化问题：当S为离散空间B'={0, 1}L,即所有长度为L且取值为0或1 的二进制位串的集合吋，相应的优化问题在进化计算领域称为伪布尔优化问题连续参数优化问题：当取S伪n维实数空间R“中的冇界集合S二ni&Q］，英中勺 ＜勺，丫二1, 2,…,n时，相应的具有连续变量的优化问题称为连续参数优化问题。

对S为BL={O,1}L,常釆用的度量时海明距离,当S = 时，常采用的度量就是欧氏距离2.1.2遗传算法的基本流程遗传算法的基本步骤如口1） 选择编码策略，把参数集合X和域转换为位串结构空间S；2） 定义适应度函数f（X）,3） 确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率4） 生成初始种群P；5） 计算群体中各个体的适应度值；6） 按照遗传策略，将遗传算子作用于种群，产生下一代种群；7） 迭代终止判定遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计, 遗传操作的设计，控制参数的设定，迭代终止条件2. 1. 3遗传编码由于GA计算过程的鲁棒性，它对编码的要求并不苛刻原则上任何形式的 编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和 积木块假设由于编码形式决定了交叉算了的操作方式，编码问题往往称作编码-交叉问 题对于给定的优化问题，由GA个休的表现型集合做组成的空间称为问题（参 数）空间，由GA基因型个体所组成的空间称为GA编码空间遗传算子在GA编 码空间中对位串个体进行操作定义：由问题空间向GA编码空间的映射称为编码，而有编码空间向问题空 间的映射成为译码。

问题编码一般应满足以下三个原则：1） 完备性（completeness）：问题空间中的所有点都能能成为GA编码空间中的 点的表现型即编码应能覆盖整个问题空间2） 健全性（soundness）： GA编码空间中的染色体位串必须对应问题空间中的某 一潜在解即每个编码必须是有意义的3） 非冗余性（non-redundancy）：染色体和潜在解必须 对应在某些情况下，为了提高GA的运行效率，允许生成包含致死基因的编码位 串，它们对应丁•优化问题的非可行解虽然会导致兀余或无效的搜索，但可能冇 助于生成全局最优解所对应的个体，所需的总计算量可能反而减少根据模式定理，De Jong进一步提出了较为客观明确的编码评估准则，称之 为编码原理具体口J以概括为两条规则：1） 有意义积木块编码规则：编码应易于生成与所求问题相关的短距和低阶的积 木块2） 最小字符集编码规则：编码应采用最小字符集，以使问题得到自然、简单的 表示和描述1. 二进制编码1）连续实函数的二进制编码设一维连续实函数/（x）,x e[W,v]采用长度维L的二进制字符串进行定长编 码，建立位串空间：SL = {如卫2，・・・，你}， ak =（色1，纵2,…，％）， akl G {0,1}扫 1,2,…，K; 7=1,2, -,L; K=2l其中，个体的向量表示为妝=（%,纵2,，其字符串形式为sk = Clp'Clk?…°kL ' 6称为个体血对皿的位吊。

表不精度为AjC =（V — u） I（J1L — 1） o将个休乂位串空间转换到问题空间的译码函数r：{o,i}L^[w,v]的公式定义为：忑二厂（S，%，〒二7（孕岸7）对于n维连续函数/（%）,% =（為宀，…，兀）小G [%，匕]（，=12・・・,〃），各维变量 的二进制编码位串的长度为厶，那么x的编码从左到右依次构成总长度为L =/=1的二进制编码位串o相应的GA编码空间为：SL = ｛⑷，｝9 K=2e {0,1}该空间上的个体位串结构为ak =，ak2，•…,攵灿，，ak2，•…，akl2°，ak2，•…，灿,…°，Q&1，ak2，…，5对于给定的二进制编码位串弘位段译码函数的形式为%,. = V(

2.1.4群体设定遗传算法的两个主要特点之一就是基于群休搜索的策略，群体的设定，尤其 是群体规模的设定，对遗传算法性能有着重要的影响这中间包括两个问题：1） 初始群体如何设定；2）进化过程中各代的规模如何维持？1. 初始群体的设定遗传算法中初始群体中的个体是按一定的分布随机产生的，一般来讲，初始 群休的设定可以采用如下的策略：1） 根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布 范围，然后，在此分布范围内设定初始群体2） 先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体 中这一过程不断重复，直到初始群体中个体数达到了预定的规模2. 群体规模的设定根据模式定理，若群体规模为M，则遗传操作可从这M个个体中生成和检测0创? 个模式，并在此基础上不断形成和优化积木块，直到找到最优解显然M越大， 遗传操作处理的模式就越多，生成有意义的积木块并逐渐进化为最优解的机会就 越高换句话说，群体规模越大，群体中个体的多样性越高，算法陷入局部最优 解的危险就越小另外，群体规模太小，会使遗传算法的搜索空间分布范围有限，因而搜索有 口J能停止在未成熟阶段，引起未成熟收敛（premature convergence）现象。

但是，从计算效率來看，群体规模越大，其适应度评价次数越多，计算量也 就越大，从而影响算法的效率研究表明，在二进制编码的前提下，为了满足隐并行性，群体个体数只要设 定为刃人即可,L为个体串长度这个数比较大,实际应用中群体规模一般取几十〜 几百2.1.4适应度函数（评价函数）遗传算法在进化搜索中基本不用外部信息，仅用目标函数即适应度函数为依 据遗传算法的口标函数不受连续可微的约束H定义域可以为任意集合对适应 度函数的唯一要求是，针对输入可计算出能加以比较的非负结果（比例选择算子 需要）需耍强调的是，适应度函数值是选择操作的依据，适应度函数设计直接 影响到遗传算法的性能1. 目标函数映射成适应度函数对于给定的优化问题，口标函数有正有负，甚至可能是复数值，所以有必要 通过建立适应度函数与目标函数的映射关系，保证映射后的适应度值是非负 的，而且目标函数的优化方向应对应于适应度值增大的方向1）对最小化问题，建立如下适应函数和目标函数的映射关系：f(、_JSax—g(Q， 若 £(兀)<0 唤7 )_ [0, 否则其中，可以是一个输入值或是理论上的最大值，或者是当前所有大或最近 K代中g(X)的最大值，此时C啦随着代数会冇变化。

2) 对于最大化问题，一般采用以下映射：fM =g(Q —Sin，0,若gOO — Gin >° 否则其中，可以是一个输入值，或者是当前所冇代或最近K代中g(x)的最小值2. 适应度函数定标在遗传进化的初期，通常会岀现一些超常个体，若按比例选择策略，这些异 常个体有可能在群体中占据很大的比例，导致未成熟收敛显然，这些界常个体 因竞争力太突岀，会控制选择过程，从而影响算法的全局优化性能另以方面，在遗传进化过程中，虽然群体中个体多样性尚存在，但往往会出 现群体的平均适应度已接近最佳个体适应度，这时，个体间的竞争力相似，最佳 个体和其它个休在选择过程中有儿乎相等的选择机会，从而使有目标的优化过程 趋于无目标大的随机搜索过程对未成熟收敛现象，应设法降低某些异常个体的竞争力，这可以通过缩小相 应的适应度值來实现对于随机漫游现象，应设法提高个体间的竞争力差距，这 可以通过放大相应的适应度值来实现这种适应度的缩放调整称为适应度定标1) 线性定标(linear scaling)f' = af + b2) cr截断 (sigma truncation)3) 乘幕标4) 指数定标f' - exp (~bf)2.1.5遗传算子遗传操作是模拟生物基因遗传的操作。

包描三个基本遗传算子(genetic operator)：选择，交叉和变异这三个遗传算子具有一些特点：(1) 这三个算子的操作都是在随机扰动情况下进行的换句话说，遗传操 作是随机化操作，因此，群体中个体向最优解迁移的规则是随机的需 耍强调的是，这种随机化操作和传统的随机搜索方法是冇区别的遗传 操作进行的是高效有向的搜索，而不是如一般随机搜索方法所进行的无 向搜索2) 遗传操作的效果和所取的操作概率、编码方法、群体大小，以及适应 度函数的设定密切相关3) 三个基木算了的操作方法和操作策略随具体求解问题的不同而异或 者说，是和个体的编码方式直接相关1、选择(selection)算子从群体中选择优胜个体，淘汰劣质个体的操作叫选择选择算子有时又称为 再生算了(reproduction operator)选择即从当前群体中选择适应度值高的个 体以生成配对池(mating pool)的过程为了防止由于选择误差，或者交叉和 变异的破坏作用而导致当前群体的最佳个体在下一代的丢失，De Jong提出了精 英选择(elitist selection)策略和代沟的概念Holland等提出了稳态选择 (steady-state selection) 策略。

下而一些概念可以用来比较不同的选择算法：(1) 选择压力(selection pressure):最佳个休选中的概率与平均选中概率 的比值2) 偏差(bias)个体正规化适应度与其期望再生概率的绝对差值3) 个体扩展(spread)单个个体子代个数的范围4) 多样化损失(loss of diversity)在选择阶段末选中个体数口占种群的 比例5) 选择强度(selection intensity)将正规高斯分布应用于选择方法，期 望平均适应度6) 选择方差(selection variance)将正规高斯分布应用于选择方法，期 望种群适应度的方差1) 适应度比例选择是最基本的选择方法，其中每个个体被选择的期望数量与其适应度值和群体 平均适应度值的比例有关，通常采用轮盘赌(rou。