第八章-启发式算法

第八章启发式算法组合优化模型与算法设计

ModelofCombinatorialOptimizationandDesignofAlgorithm

1第八章启发式算法

本章介绍的启发式算法也称智能算法、现代优化算法，自20世纪80年代初以来已得到深入研究和广泛应用，主要包括模拟退火算法、神经网络算法、遗传算法、蚁群优化算法等等.它们的共性是基于客观世界中的一些自然现象,通过与组合优化求解进行类比，找出它们的一些共性，建立相应的算法.仿生学这些算法的目标是希望求解NP难问题的全局最优解，有一定的普适性，可用于解决大量的实际应用问题.生命科学与工程科学的相互交叉、相互渗透、相互促进是近代科学技术发展的显著特点之一.2第八章启发式算法§1模拟退火算法§2神经网络算法§3遗传算法3第八章启发式算法§1模拟退火算法

模拟退火（SimulatedAnnealing，简记SA）算法是一种通用的随机搜索算法.

模拟退火算法最初的思想由Metropolis在1953年提出，它来源于固体的退火过程，Kirkpatrick在1983年成功将其应用在组合优化问题中.

目的是降低硬度，改善切削加工性；消除残余应力，稳定尺寸，减少变形与裂纹倾向；细化晶粒，调整组织，消除组织缺陷.

金属物体在加热至一定的温度后，它的所有分子在状态空间D中自由运动，系统能量增大.随着温度的下降，这些分子逐渐停留在不同的状态，系统能量逐渐下降，最后在常温时达到基态，分子重新以一定的结构排列，系统能量下降至最小值.这种由高温向低温逐渐降温的过程称为退火.

4§1模拟退火算法一、原理与步骤进一步研究表明，在同一温度分子停留在能量小的状态的概率比停留在能量大的状态的概率大.

由统计力学的研究表明，在温度T，分子停留在状态r满足Boltzmann概率分布其中，E(r)表示状态r的能量，kB>0为B–常数，表示分子能量的一个随机变量.Z(T)为概率分布的标准化因子Metropolis准则：如果，则接受新状态，否则按概率接受新状态.其中；T=T(t)为一随时间t增加而下降的参数，它相当于退火过程中的温度.对固体在恒定温度下达到热平衡过程的模拟

在温度趋向于零时，分子停留在最低能量状态的概率趋向于1.温度下降过快，会如何？5第八章启发式算法金属物体组合优化问题状态能量最低的状态最优解能量费用函数解模拟退火算法的基本原理：称为Metropolis过程1、给定温度t及点x0，计算函数值f(x0);2、随机产生扰动，得到新点x1=x0+，计算f(x1)及；3、若，则接受新点，作为下一次模拟的出发点;4、若，则计算新点接受概率，,

产生[0,1]区间上均匀分布的伪随机数r,若则接受新点作为下一次模拟的出发点；否则放弃新点，仍取原来的点作为下一次模拟的出发点.

按照一定的退火方案逐渐降低温度，重复M-过程，构成了模拟退火算法.6§1模拟退火算法令控制参数t担当固体退火过程中温度的角色，对于t的每一取值，算法采用Metropolis过程，持续进行“产生新解——判断——接受/舍弃”的迭代过程而达到该“温度”下的“平衡点”，随着参数t徐徐“降温”并趋向于零时，最终求得组合优化问题的相对全局最优解.简单的模拟退火算法的步骤：Step1任选一初始解xi0；xi

=xi0;k=0;t0=tmax.初始温度Step2若在该温度达到内循环停止条件，则到Step3;否则，从邻域N(xi)中随机选取一xj

,计算；若，则xi=xj,否则

若时，则xi=xj;重复Step2.Step3tk+1=d(tk);k=k+1;若满足停止条件，终止计算；否则，回到Step2.温度下降规则（衰减函数）在（0,1）之间均匀分布的伪随机数7第八章启发式算法在上述的SA算法中，包含一个内循环和一个外循环.内循环是Step2，它表明在同一个温度tk时，在一些状态随机搜索.外循环主要包括Step3.温度下降规则；迭代步数增加；停止条件.SA算法的每一次迭代都体现集中和扩散两个策略的平衡.对遇到的下一个迭代解，如果这个解更好，则采用集中策略，选择这个解为新解.不然的话，采用扩散策略，以某一概率选择这个解为新解.

由于在给定领域结构后，模拟退火过程是从一个状态到另一个不断地随机游动，所以可以用Markov链来描述.

设{X(k)}k=0,1,2,…为随机变量序列，X(k)=i称在时刻k处于状态i，i∈D.D称为状态空间.当D中的状态数有限时，称为有限状态空间.若对任意的正整数n，P{X(n)=j︱X(1)=i1,X(2)=i2,…,X(n-1)=i

}=P{X(n)=j︱X(n-1)=i}i1,i2,…,，i，j∈D.则称{X(k)}k=0,1,2,…Markov链.Markov链具有记忆遗忘特性，它只记忆前一时刻的状态.8§1模拟退火算法模拟退火算法主要可以分为两类：

第一类为时齐算法，对每一个固定的t，计算对应的Markov链，直至达到一个稳定状态，然后再让温度下降；第二类为非时齐算法，基本计算框架是由一个Markov链组成，要求在两个相邻的转移中，温度t是下降的.9第八章启发式算法二、实现的技术问题 以时齐算法为主根据理论要求，SA得到全局最优解必须达到平稳分布，而时齐的算法要在每一个温度迭代无穷步，才能达到平稳分布.所以，本节介绍的技术问题无法保证

SA得到全局最优解，只是一种启发式算法，得到的是满意解.1、解的形式和邻域结构这是每个搜索算法都要涉及的问题解的表现形式直接决定邻域的构造对求f(x)=x2在区域0≤x≤100最大值的实例，其中x为整数.采用0-1编码表示解10§1模拟退火算法对TSP这一类问题，可采用n个城市的一个排序表示问题的一个解，直观地可通过城市间不同位置交换构造邻域.如采用2-opt.以上两种邻域表示的共同特征：（1）每一个邻域所含的状态个数相同；如前例每个解的邻域有个邻居TSP中采用2-opt时每个邻域有个邻居（2）每个邻居都是可行解；（3）解空间中的任何两个状态可达.11第八章启发式算法同样解的表达式和邻域结构，将前一种表示形式应用到背包问题时，后一种表示形式应用到车间作业问题（参见

[4]p71）就会出现新的问题.

由于背包问题有容量约束和车间作业的死锁现象,无法保证每个邻域中邻居都是可行解.处理这类问题的常用方法有两种：（1）罚值法将不可行解视为可行解，目标值为一个充分大的数（罚值）.缺点：扩大了搜索区域.（2）研究解和邻域结构在可行域内构造邻域.（[4]p74）实践中更关心应用的效果处理机集设有作业集每个作业Jj

有m道工序：T1j，T2j，…，Tmj，工序Tij

的加工时间为tij各作业分别在处理机P1，P2,…,Pm上完成各道工序.在一定条件下使最后一个完工的作业加工时间最短.12§1模拟退火算法2、温度参数的控制温度参数是模拟退火时齐算法的关键参数之一.主要包括起始温度的选取、温度的下降方法和停止温度的确定等.（1）起始温度的选取

起始温度高，算法搜索到全局最优解的可能性大,但花费的计算时间长；反之，则可节省计算时间，但影响全局搜索性能.实际应用过程中，起始温度的选择一般要依据实验结果进行若干次调整.（[4]p97）13第八章启发式算法从理论上说，起始温度t0应保证平稳分布中每一状态的概率相等，即其中很容易估计一个值为

实际计算中，可选取K=10,20,100,…的试验值.其中K为充分大的数，对TSP,记对应的距离矩阵为(dij)n×n则14§1模拟退火算法（2）温度下降方法的确定在SA中，降温的方式对算法有很大影响.如果温度下降过快，可能会丢失极值点；如果温度下降过慢，算法的收敛速度大大降低.实际应用中，常采用以下方法：a.每一步温度以相同比率下降，即tk+1=atk其中k≥0为降温次数,0<a<1，a为降温系数.A越接近1温度下降越慢b.每一步温度以相同长度下降，即

tk=t0(K-k)/K其中t0为起始温度，K为温度下降的总次数.15第八章启发式算法c.经典退火方式：tk=t0/ln(1+k)特点：温度下降很缓慢，因此算法的收敛速度很慢.当解的质量变差的概率呈Boltzmann分布，或搜索的前期d.快速退火方式：tk=t0/(1+ak)特点：在高温区降温比较快，而在低温区降温较慢.当解的质量变差的概率呈Cahchy分布，或搜索的后期16§1模拟退火算法（3）每一温度迭代长度的确定

SA

的全局搜索性能与每一温度的迭代长度密切相关.一般来说，同一温度下的充分搜索是十分必要的，但需要付出计算时间增加的代价.a.固定迭代步数

在每一温度都设置相同的迭代步数，步数的选取通常采用与邻域大小直接相关的规则.如TSP采用2-opt，则邻居数为n(n-1)/2，在同一温度,它的迭代步数可取n,n/2,n2,nk

（k≥3）等.17第八章启发式算法b.根据接受和拒绝概率控制迭代步数当温度很高时，每一个状态被接受的概率基本相同，而且几乎所有的状态都被接受.可使同一温度的迭代步数尽量少些；

温度渐渐变低后，越来越多的状态被拒绝，则可相应增大迭代步数.在此温度的迭代太少，则可能造成过早地陷入局部最优.实现方法有二：一是给定一个充分大的步数上限U和一个接受次数指标R,当在给定温度接受次数等于R时，不再迭代而使温度下降，否则继续迭代至上限步数U;直观、有效的方法是随着温度的下降，将同一温度的迭代步数增加.二是给定一个接受比率指标R、迭代步数的上限U和下限L,每一温度至少迭代L次且纪录同一温度迭代的总次数和被接受的次数，当迭代次数超过L时，若接受次数同总次数的比率不小于R时，不再迭代而使温度下降，否则继续迭代至上限步数U.18§1模拟退火算法（4）算法的终止原则

SA从起始温度开始，通过在每一温度的迭代和温度的下降，最后达到终止原则而停止.尽管有些原则有一定理论的指导，终止原则大多是直观点.a.零度法给定一个比较小的正数，当温度tk

≤时，算法终止，表示达到最低温度.b.循环总数控制法设定温度下降的总次数为K,当温度迭代次数达到K时算法终止.可以考虑整个算法的总迭代步数为一定数，容易计算算法的计算复杂性，但需要合理分配内循环的长度和温度下降的次数.19第八章启发式算法c.基于不改进规则的控制法在一个温度，在给定的迭代次数内没有改进当前的局部最优解，则停止运算.直观的结论是在较高的温度没能跳出局部最优解，则在低温时跳出局部最优解的可能更小了.d.接受概率控制法给定一个比较小的数p>0，在给定温度，除局部最优解，其他状态的接受概率都小于p时，则停止运算.其他还有邻域法、Lundy和Mees方法、Aarts

和vanLaarhoven法等.（参见[4]p

103）20§1模拟退火算法

模拟退火算法——一种自适应启发式随机搜索算法，1、对目标函数、约束条件没有要求，可以不可微甚至不连续；2、能以较大概率求得全局最优解；3、具有较强的鲁棒性、广泛的适应性.具有以下缺点：1、优化效果与计算时间存在矛盾；2、马尔科夫链的长度不易控制.具有以下优点：21第八章启发式算法三、应用案例——TSP

设完全连通图G有n个顶点x1，x2,…，xn

.已知任意两点之间的距离为dij

=d(xi，xj)，其中1≤i,j≤n.解的表现形式:

（解空间）目标函数：定义

km+1=k122§1模拟退火算法SA算法的求解过程：（1）定义相关参数

初始解s0

（随机得到）；初始温度T0

（开始可以高一些）；Markov链的长度L；温度下降方法tk+1=atk，a为降温系数；终止原则.（2）产生新解

新解可通过分别或交替使用以下两种方法来产生：a、2变换法：随机产生1和n之间的2个相异数h和

m，不妨设h＜m,则将原路径（k1，k2,…,kh，kh+1，…,km，km+1，…，kn）变为新路径（k1,…,kh-1,km，km-1，…,kh+1,kh，km+1，…，kn）23第八章启发式算法b、3变换法：随机产生1和n之间的3个数h、m和

p，不妨设h≤m＜p,则将原路径中h和m之间的路径插到p之后，得到新路径（k1,…,kh-1,km+1,…,kp-1，kp,kh,…,km，kp+1,…，kn）（3）计算目标函数差可类似计算.若dij

=dji,则c、2-opt24§1模拟退火算法（4）接受准则或城市xy城市xyA5.2941.558K4.3991.194B4.2863.622L4.6602.949C4.7192.774M1.2326.440D4.1852.230N5.0360.244E0.9153.821O2.7103.140F4.7716.041P1.0723.454G1.5242.871Q5.8556.203H3.4472.111R0.1941.862I3.7183.665S1.7622.693J2.6492.556T2.6826.09720个城市TSP的坐标[5]p.129-24.38实验设计、结果的讨论.25第八章启发式算法§2神经网络算法26第八章启发式算法遗传算法是20世纪60~70年代主要由美国Michigon

大学JohnHolland教授提出.其内涵哲理启迪于自然界生物从低级、简单到高级、复杂，乃至人类这样一个漫长而绝妙的进化过程.借鉴Darwin的物竞天择、优胜劣汰、适者生存的自然选择和自然遗传的机理.其本质是一种求解问题的高效并行全局搜索方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解.§3遗传算法27§3遗传算法一、基本概念GA

的基本思想：从一初始化的群体出发，通过随机选择(复制)（使群体中优秀的个体有更多的机会传给下一代），交叉（体现了自然界中群体内个体之间的信息交换），和变异（在群体中引入新的变种确保群体中信息的多样性）等遗传操作，使最具有生存能力的染色体以最大可能生存,群体一代一代地进化到搜索空间中越来越好的区域.28生物遗传概念在遗传算法中的对应关系生物遗传概念遗传算法中的作用适者生存最优目标值的解有最大可能留住个体解染色体解的编码（字符串、向量等）基因解中每一分量的特征（如分量的值）适应性适应函数值群体选定的一组解种群根据适应函数值选取的一组解交叉（基因重组）通过交叉原则产生一组新解的过程变异编码的某一个分量发生变化的过程第八章启发式算法29Example1某快餐店要作出以下三项决定：价格汉堡包的价格应定在1美元还是50美分;饮料和汉堡包一起供应的应该是酒还是可乐;服务速度饭店应提供慢的还是快的服务速度.Solution:编码有3个决策变量共有23=8种方案用三位0-1数串，表示一个方案染色体基因a1表示价格0——高价格1——低价格a2表示饮料0——酒1——可乐a3表示速度0——慢1——快§3遗传算法30适应函数即目标函数就取每种方案实行后的利润，为简单起，每种方案所对应的利润（适应值）恰为这三位二进制所对应的十进制数值.确定群体规模NGA不是一个个的考虑方案，而是同时考虑N个方案，体现了并行性

.取N=4，在8个方案中随机抽取4个方案作为初始群体（第0代）.xi011001110010f(xi)3162总和12最小值1平均值3最大值6第八章启发式算法31选择算子希望110在新的群体中出现次,类似希望011、010各出现1次，而001消失.因GA是随机的,按概率随机选择，以上只是期望.6321如随机数5选择的个体1102129011010110由选择算子产生的新群体（可能有重复）称为种群，其规模仍为N

.0110011100100341012§3遗传算法把当前群体中的个体按与适应值成比例的概率复制到新的群体中（适者生存）.轮盘赌选择：2、产生一个在0与S之间的随机数m;步骤：1、求群体中所有个体的适应值的总和S;

3、从群体中编号为1的个体开始，将其适应值与后继个体的适应值相加，直到累加和等于或大于m,则停止.其中那个最后加进去的个体即为选择的个体.32xi110011010110f(xi)6326总和17最小值2平均值4.25最大值6选择算子作用的效果是提高了群体的平均适应值及最差的适应值，低适应值的个体趋于被淘汰，高适应值的个体趋于被复制.但是以损失群体的多样性为代价，选择算子并没有产生新的个体，当然群体中最好个体的适应值不会改进.第八章启发式算法33交叉（杂交）算子交叉算子每次作用在种群中随机选取的两个个体上,产生两个不同的子个体，它们一般与父个体不同，但又包含两个父个体的遗传物质.介绍一个最简单的方法.首先，产生一个1到l-1（其中l为染色体分量的个数）的随机数i(交叉点),然后配对的两个个体相互交换从i+1到l的位子.如对x1，x2配对且交叉点选在2，则对种群要确定交叉概率

Pc,随机选择

N×Pc

个个体进行交叉，其余不变.假设Pc=50%xi111010010110f(xi)7226总和17最小值2平均值4.25最大值7§3遗传算法34

显然，利用选择、交叉算子可以产生具有更高平均适应值和更好个体的群体.但如果仅仅如此，很容易近亲繁殖，会早熟（局部最优解）.骗问题（遍历性差）变异算子以一个很小的变异概率Pm(=0.02)随机地改变染色体上的某个基因,具有增加群体多样性的效果.如：选择x3第2位，则得到新的群体.称为第1代，再进行选择、交叉、变异….第八章启发式算法35Example2Solution:用GA求对连续变量求解，要解决如何编码问题.假设对解的误差要求是，则可采用4位二进制编码，对应关系一次迭代的结果.(交叉概率Pc

=1，变异概率Pm=0.02)x值共有16种方案群体规模为4群体

xif(xi)概率分布种群交叉位交叉结果变异？误差要求是g，区间为，如何处理？新群体x值f(xi)1/161/43/167/800010100001111100.990.930.960.230.3180.2990.3080.07500010100000100110000010100010011NYNN0000110100010011013/161/163/1610.340.990.96第0代总和3.133最小值0.234平均值0.7833最大值0.996;第1代总和3.301最小值0.340平均值0.8253最大值1.§3遗传算法36遗传算法的步骤：step1选择问题解的一个编码，给出一个有N个染色体的初始群体pop(1)，t=1;step2

对群体中每一个染色体popi(t)计算它的适应函数值fi=fitness(popi(t));step3

若停止规则满足,则算法停止,否则计算概率并以此概率分布，从pop(t)中随机选N个染色体构成一个种群，;

第八章启发式算法37step4

通过交叉(交叉概率)为Pc,得到有N个染色体的crosspop(t+1);step5以较小的概率（变异概率）Pm

使得某染色体的一个基因发生变异，形成新的群体mutpop(t+1)令t=t+1pop(t)=nutpop(t)gotostep2.§3遗传算法38遗传算法的优越性：1、作为数值求解方法，具有普适性.对目标函数几乎没有要求，总能以极大的概率找到全局最优解；2、GA在求解很多组合优化问题时，不需要很高的技巧和对问题有非常深入的了解，在给问题的决策变量编码后，其计算过程是比较简单的，且可较快地得到一个满意解；3、与其他启发式算法有较好的兼容性，易与别的技术相结合，形成性能更优的问题求解方法.可以不连续、不规则、伴有噪声，甚至不一定要显式写出.这是关键.Goback第八章启发式算法39二、实现的技术问题GA的主要问题之一是算法如何实现的技术问题，以下的一些技术方法，有的借助于直观，有的则有一定的理论，在此仅给出技术细节.（一）编码

编码是GA中的基础工作之一，GA不能直接处理解空间的解数据，必须通过编码表成遗传空间的基因型数据.比较直观和常规的方法是0、1二进制编码,称为常规码.这种编码方法使算法的三个算子构造比较简单.这与人类的染色体成对结构类似.§3遗传算法40如0–1背包问题的解是一个0-1向量，可以按(x1，x2,…,xn)的取值形成一个自然编码.▲采用0–1编码可以精确地表示整数.如则可用5位二进制编码.精确表示a到b整数的0–1编码长度n满足：第八章启发式算法41▲连续变量也可采用二进制编码,但要考虑精度.对给定的区间[a,b]，设采用二进制编码长为n，则任何一个变量对应一个二进制码（x1,x2,…,xn）,二进制码与实际变量的最大误差为.▲常规码在表示有些组合优化问题会显得无效或不方便

如TSP问题n个城市二进制编码（x1,x2,…,xn(n-1)）编码长为n(n-1)所有解的个数2n(n-1)

可行解的个数(n-1)!n=10编码长为90，但可行解只有10个基因取1其余取零.可行解占所有解的极小比例，大量的计算浪费，且对非可行解通过约束限制也增加计算量.§3遗传算法42

对TSP的一个自然的表示方法是n个城市的序号的排列.n=109408712536、3802617945etc.理论上而言，编码应该适合要解决的问题，而不是简单的描述问题.编码是一个很值得研究的问题.（二）评价GA的常用方法GA

的最优性效果的理论分析是一种趋势讨论，或无穷代的概率结果.用一个方法监察计算过程中解的变化趋势，可以了解进化的程度以便决定是否继续下去.GA求解最优化问题的一个目的是得到最优解，于是需要了解GA求最优解的功效.有一些测试函数,见[2]p21Goon第八章启发式算法43约束机器排序(CapacitatedMachineScheduling)

n个加工量为的产品在一台机器上加工，机器在第t个时段的工作能力为Ct，求出所有产品得以加工的最少时段数.数学模型：区别？44一个自然的编码——决策变量的0–1码问题：1、T的估计；2、可行性.是一个n×T的向量每个解用一个nT的向量表示，解空间中共有2nT个解，若假设每个时段最多可以加工P个产品，则至少有2(n-P)T-1个解是不可行.一个有效的编码方法是给产品（1，2，…，n）一个加工序（i1，i2，…，in）,由加工序按能力约束以最小的剩余能力依次安排时段加工,在加工的过程中不允许改变产品的加工序.如产品需求为(d1=5，d2=3，d3=10，d4=4)，前五个时段可提供能力为(3，9，10，5，20)，若按（1，2，3，4）顺序加工，各时段加工的产品为：第一个时段不加工，第二个时段加工产品1和2，第三个时段加工产品3，第四个时段加工产品4.

最优解为第一时段加工产品2，第二时段加工产品1和4，第三时段加工产品3，最优序为(2，1，4，3).451、当前最好解（best–so–far）方法在每一代的进化中,记录下最好的解,通过这个最好解展示算法的效果.这个最好解可以用于不同算法的横向比较；如果知道问题的界，也可以自身比较它的功效.2、在线（on–line）比较法用进化过程中的每一个解来了解进化趋势其计算公式：其中T为当前计算中群体中出现的染色体总数,v(t)为第t个染色体的目标值.§3遗传算法462、离线（off–line）比较法其中T为当前计算中出现的遗传代数，v*(t)为第

t代前（包括第t代）时，所得最优值.即表示中的最优目标值.Note

(*)与(**)中t的区别：在（*）中t表示第t个染色体；而（**）中t表示第t代.

(**)的另一种理解方法是v*(t)为第t代时所得的最优目标值，即

这与best–so–far方法类似.第八章启发式算法47从直观可以看出，当优化问题是最大化目标函数时，随着T的增加（**）应该具有上升趋势，因为适应函数取决于目标函数，随着一代代进化使适应能力强的染色体生存下来，（**）的平均值上升.(*)总体是上升的，但某些代可能会有波动.

通过（*）、（**）、（***）的监控，可以掌握遗传算法计算的进展情况，以决定如何改进？何时停止算法.自适应问题§3遗传算法48（三）初始参数的选取和停止原则1、群体的规模群体规模的确定，根据模式定理，受遗传操作中选择操作的影响很大.一般来说，群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险就越小.但太大从计算效率着眼,群体越大其适应度评估次数增加,所以计算量增加，从而影响计算效能；太小会使GA的搜索空间中分布范围有限，因而搜索有可能停止在未成熟阶段，引起早熟收敛现象.第八章启发式算法49群体的规模取个体编码长度数的一个线性倍数是实际应用时经常采用的方法之一

.如：m在n和2n之间的一个数.②群体规模的选择也可以变化的.体现GA的自适应性如：当多个进化代没有改变解的性能，保持现有的群体规模已很难改进解，此时可扩大群体规模；反之，若解的改进非常好，则可以减少群体的规模以便加快计算的速度.§3遗传算法502、初始群体的选取①用随机方法产生只有这样选取才能达到所有状态的遍历，使最优解在GA的进化中最终得以生存.②用其他优化方法或启发式方法选取使初始群体更优良.第八章启发式算法513、终止规则①给定一个最大的遗传代数Maxgen;②给定问题的一个上界UB，当进化中达到要求的偏差度时，算法终止；③按前面的（*）、（**）、（***）式的评价算法规则，当由它们监控得到算法再进化已无法改进解的性能，则终止计算;④以上多种规则的组合.§3遗传算法52（四）进化过程中的技术问题1、适应函数一般适应函数取正的①简单适应函数优化目标为最大时，fitness(x)=f(x)目标函数优化目标为最小时，fitness(x)=M-f(x)优点：简单、与目标函数直接相关.缺点：有时使适应度很接近.如：若采取四位编码且适应函数为优化问题的目标函数.x群体fitness(x)概率分布1/200000.6890.2215/801000.7960.25221/3201010.8170.25923/3201110.8570.271

此时，若从群体中以概率分布选取种群，由于概率分布值相差很小，因此，很难区别哪一个染色体占先.第八章启发式算法53②非线性加速适应函数M一个充分大的数，fmax是当前的最优目标值.如前例Note

M选取的策略：初始迭代时，M同第一大与第二大目标差值的倒数尽量接近以避免早熟，后期迭代中逐步扩大差距.决定当前最优解的继承性x群体fitness(x)概率分布1/200005.950.0795/8010016.390.21821/320101250.33223/320111280.372§3遗传算法54△适应函数的设计应满足的条件:①单值、连续、非负、最大化②合理、一致性③计算量小④通用性强△遗传算法的欺骗问题:①在遗传进化的初期,通常会产生一些超常个体,按比例选择,这些个体竞争力太强,而控制了选择过程，影响算法的全局优化性能；②在遗传进化的后期,即算法接近收敛时,由于种群中个体适应度差异较小时,继续优化的潜能降低,可能获得某个局部最优解.能反映对应解的优劣程度第八章启发式算法552、选择策略选择——从群体中选择优胜的个体，淘汰劣质个体，得到种群的操作.选择算子是遗传算法的关键，体现了自然界中适者生存的思想，基于适应函数值的计算.①

基于适应函数值比例的策略计算各个体的相对适应度，以pi

为选择概率，用论盘赌或MonteCarlo选择种群.§3遗传算法56②基于排名的策略比①表现出更好的鲁棒性

不计算各个体的相对适应度，而根据个体适应度在群体中的排名来确定其选择概率.

将同一代群体中的m个染色体按适应函数值,从小到大排列，记为1，2,...,m.取选择概率

再用①的方法选择.这可避开非线性加速可能产生的早熟现象.第八章启发式算法57③基于局部竞争机制的策略在群体中随机选择k个个体（常取k=2）进行比较，其中适应度最好的个体被确定为生成下一代的父体.④最优保存选择策略优点：阶段最优不被随机性破坏；缺点：影响全局搜索能力.强行遗传§3遗传算法583、交叉（杂交）规则交叉操作是基因算法获得优良个体的重要手段.内容包括：a、从种群中对个体随机配对，并按预定的交叉概率来决定是否进行交叉操作;b、设定个体的交叉点，并对这些点前后的配对个体的基因相互交换.①单交叉位法父代

A100100父代

B010010子代

A100010子代

B010100双亲双子法---常用方法

第八章启发式算法59②变化交叉法父代

A1101001父代

B1100010子代

A1100010子代

B1101001

若交叉点在1、2、3，则交叉后无任何变化.因此交叉点需避开这三个位置，采用方法：从左开始，先比较它们的相同的基因，从不同基因位置按①进行交叉.父代

A1101001父代

B1100010子代

A1101010子代

B1100001§3遗传算法60③多交叉位法

随机选择多个交叉点，双亲以一个交叉点到下一个交叉点基因相互替代和下一个交叉点到再下一个交叉点不变这样交叉形成两个新的后代.父代

A1101001父代

B1100010子代

A1100001子代

B1101010父代

A1101001父代

B1100010子代

A1100000子代

B1101011第八章启发式算法61④双亲单子法a、从前述方法得到双子后，随机选一个；b、从前述方法得到双子后，选一个好的.

⑤显性遗传法对双亲中的基因，有些是具有优超关系的，这些基因必将遗传给下一代.如：则1永远比0好，所以父代

A10101父代

B10010子代10111Goldberg和Smith将这种方法应用在背包问题中.§3遗传算法62⑥单亲遗传法单亲遗传的一个特点是只有一个父代，下一代的产生通过单亲自身的基因变化.如选定一个单亲，随机选两个基因位置，将两个位置的元素进行交换：父代1101001子代1001011或选定两个交叉位，通过交叉位之内的基因倒排得到子代.父代110100

1子代101010

1

单亲遗传法使得染色体中的基因取值受到限制，如例中的1的个数为4个，0的个数为3因此限制搜索的范围.在使用单亲遗传时应加大变异的概率.单亲遗传法可以同双亲遗传法结合使用.第八章启发式算法63⑦基于“与/或”交叉法对父代A、B按位“与”逻辑运算产生一子代A;按位“或”逻辑运算产生另一子代B.父代