遗传算法专题知识专家讲座

第三章

遗传算法1遗传算法专题知识专家讲座第1页五.遗传算法各种变形5.1其它编码方法5.2遗传运算中问题5.3适值函数标定(Scaling)5.4选择策略5.5停顿准则六.应用

遗传算法2遗传算法专题知识专家讲座第2页5.1其它编码方法次序编码：用1到N自然数不一样次序来编码，此种编码不允许重复，即且，又称自然数编码。该法适用范围很广：指派问题、旅行商问题和单机调度问题等等。正当性问题：是否符合采取编码规则问题五.GA各种变形（1）3遗传算法专题知识专家讲座第3页实数编码：,R为实数集特征：方便运算简单，但反应不出基因特征整数编码类似于次序编码，但编码允许重复适合用于：新产品投入，时间优化，搭档挑选例：3212345对次序编码来说是不正当，而对整数编码来说是正当；010200不正当01编码；五.GA各种变形（2）4遗传算法专题知识专家讲座第4页5.2遗传运算中问题 在次序编码遗传运算过程中会遇见不正当编码，应战策略有二:拒绝或修复。比如：经双切点交叉后，后代编码不正当

21¦345¦6721¦125¦6743¦125¦7643¦345¦76我们采取下面修复策略使以上编码正当。五.GA各种变形（3）5遗传算法专题知识专家讲座第5页次序编码正当性修复：交叉修复策略，分为以下几个：部分映射交叉次序交叉循环交叉

五.GA各种变形（4）

6遗传算法专题知识专家讲座第6页部分映射交叉(PMX)(PartiallyMappedCrossover)：用尤其修复程序处理简单双切点交叉引发非法性，步骤：⑴选切点X,Y；⑵交换中间部分；⑶确定映射关系；⑷将未换部分按映射关系恢复正当性。五.GA各种变形（5）7遗传算法专题知识专家讲座第7页PMX例题：五.GA各种变形（6）映射关系：3-1，4-2，5-5则：43¦125¦6721¦345¦76

21¦345¦67¦125¦

43¦125¦76¦345¦

XY8遗传算法专题知识专家讲座第8页次序交叉(OX

)OrderCrossover：可看做是带有不一样修复程序部分映射交叉变形。OX步骤：⑴选切点X,Y；⑵交换中间部分；⑶从切点Y后第一个基因起列出原次序，去掉已经有基因；⑷从切点Y后第一个位置起，按次序填入。五.GA各种变形（7）9遗传算法专题知识专家讲座第9页OX例题：五.GA各种变形（8）列出基因：67213457643125则：34¦125¦6712¦345¦76

21¦345¦67¦125¦

43¦125¦76¦345¦

XY10遗传算法专题知识专家讲座第10页OX特点：很好保留了相邻关系、先后关系,满足了TSP问题需要,但不保留位值特征。五.GA各种变形（9）11遗传算法专题知识专家讲座第11页循环交叉(CX)CycleCrossover基本思想：子串位置上值必须与父母相同位置上位值相等。CX步骤：⑴选第一个元素作为第一位， 选第一个元素作为第一位；五.GA各种变形（10）12遗传算法专题知识专家讲座第12页⑵到中找第一个元素赋给相对位置…，重复此过程，直到上得到第一个元素为止，称为一个循环；⑶对最前基因按、基因轮替标准重复以上过程；⑷重复以上过程，直到全部位都完成。五.GA各种变形（11）13遗传算法专题知识专家讲座第13页CX例题：五.GA各种变形（12）

245389617236

398654271362

32，94，58，716

29346

34692

295384671

34865921714遗传算法专题知识专家讲座第14页CX特点：与OX特点不一样是，CX很好保留了位值特征，适合指派问题；而OX很好保留了相邻关系、先后关系满足了TSP问题需要。五.GA各种变形（13）15遗传算法专题知识专家讲座第15页变异修复策略换位变异(最惯用)是随机地在染色体上选取两个位置，交换基因位值。

例：43125674512367

移位变异：任选一位移到最前例：43125675431267五.GA各种变形（14）16遗传算法专题知识专家讲座第16页实数编码正当性修复

交叉单切点交叉五.GA各种变形（15）切点17遗传算法专题知识专家讲座第17页双切点交叉(与单切点交叉类似)

该方法最大问题：怎样在实际优化中保持可行性。五.GA各种变形（16）切点切点18遗传算法专题知识专家讲座第18页五.GA各种变形（17）凸组合交叉：能够克服上面简单交叉操作造成解不可行性。约束是个凸集，可行性能够保持，不过分散性太差，又出现了向中间聚集问题。19遗传算法专题知识专家讲座第19页变异位值变异： 任选一位加Δ（变异步长），

例：五.GA各种变形（18）20遗传算法专题知识专家讲座第20页向梯度方向变异缺点：只能用于目标函数可微问题。 例:对于最大化问题可采取以下操作：优点：考虑到了问题本身性质，效率较高。但染色体种群也可能所以而趋于聚集，造成种群多样性较差。五.GA各种变形（19）21遗传算法专题知识专家讲座第21页5.3适值函数标定(Scaling)五.GA各种变形（20）

相对差异放大，选择压力变大，选优功效强化了标定

相对差异小，选择压力小，选优功效弱化了22遗传算法专题知识专家讲座第22页标定目标： 使适值函数不会太大，有一定差异选择压力概念： 选择压力是种群好、坏个体被选中概率之差，差大称为选择压力大。注意：上述概念中“差大小”是相对于适值函数而言。五.GA各种变形（21）23遗传算法专题知识专家讲座第23页局部搜索、广域搜索与选择压力关系局部搜索与广域搜索是GA中一对矛盾，只重视局部搜索很可能陷入局优，只重视广域搜索则会造成准确开发能力不强。所以，好算法要将以上二者综合考虑。普通来说，算法开始时应重视广域搜索，经过使用较小选择压力来实现；伴随迭代进行，逐步偏重于局部搜索，经过使用较大选择压力来实现。五.GA各种变形（22）24遗传算法专题知识专家讲座第24页适值标定方法线性标定：函数表示式：,

为目标函数，为适值函数五.GA各种变形（23）25遗传算法专题知识专家讲座第25页对， =1，=

+ξ， 函数表示式： +ξ，对， =-1，=

+ξ, 函数表示式： +ξ，

上述中ξ是一个较小数，目标是使种群中最差个体依然有繁殖机会，增加种群多样性。五.GA各种变形（24）26遗传算法专题知识专家讲座第26页动态线性标定(最惯用)：线性标定中参数伴随迭代次数增加而改变时就得到了动态线性标定 优点：计算轻易不占用时间函数表示式：，为迭代指标最惯用最大化

=1,函数表示式：五.GA各种变形（25）第k代最小目标函数值27遗传算法专题知识专家讲座第27页加入意义（同线性标定中ξ意义） 加入使最坏个体仍有繁殖可能，随增大而减小取值： ，，， 调整和，从而来调整五.GA各种变形（26）28遗传算法专题知识专家讲座第28页五.GA各种变形（27）引入目标： 调整选择压力，即好坏个体选择概率差，使广域搜索范围宽保持种群多样性，而局域搜索细保持收敛性。以下列图表示： 开始：希望选择压力小 以后：希望选择压力大k29遗传算法专题知识专家讲座第29页幂律标定： 函数表示式： 取值，>1时选择压力加大

<1时选择压力减小对数标定： 函数表示式： 对数标定作用：缩小目标函数值差异五.GA各种变形（28）30遗传算法专题知识专家讲座第30页指数标定： 函数表示式： 指数标定作用：扩大差异窗口技术： 函数表示式： 为前W代中最小目标值，它考虑了各代 波动，这么含有记忆性五.GA各种变形（29）31遗传算法专题知识专家讲座第31页正规化技术： 函数表示式： 正规化技术作用： 将映射到(0,1)区间，抑制超级染色体 正规化技术实质：特殊动态标定 即 其中：五.GA各种变形（30）32遗传算法专题知识专家讲座第32页5.4选择策略 传统GA选择和遗传是一起进行，即使后代不如父代，却无法纠正。下面介绍选择策略都是先遗传后选择。这么，样本空间扩大了，可供选择个体增多了。五.GA各种变形（31）33遗传算法专题知识专家讲座第33页截断选择： 选择最好前T个个体，让每一个有1/T选择概率，平均得到NP/T个繁殖机会。例：NP=100,T=50 即100名学生，成绩前50名选出。每人选择概率为1／50，有平均2个机会。缺点：这种方法将花费较多时间在适应值排序上。五.GA各种变形（32）34遗传算法专题知识专家讲座第34页次序选择：步骤：⑴从好到坏排序全部个体⑵定义最好个体选择概率为,则第个个体选择概率为：五.GA各种变形（33）35遗传算法专题知识专家讲座第35页⑶ 因为 有限时要归一化，则有下面公式：，其中次序选择优点：选择概率能够离线计算，节约算法执行时间，且选择压力可控；缺点：把选择概率固定化了，选择压力不可调整。五.GA各种变形（34）36遗传算法专题知识专家讲座第36页举例:

且：采取旋轮法，随机产生当，选择个体五.GA各种变形（35）前i-1个个体选择概率前i个个体选择概率37遗传算法专题知识专家讲座第37页正比选择：个体i选择概率 令： ，用动态标定来调整选择压力，采取旋轮法来共同完成种群选择。

五.GA各种变形（36）38遗传算法专题知识专家讲座第38页5.5停顿准则指定最大代数（惯用）：该方法简单但不准确。检验种群中适值一致性：保持历史上最好个体。计算公式： 或第二种方法因极难实现，所以极少使用。五.GA各种变形（37）39遗传算法专题知识专家讲座第39页背包问题 个物品，对物品，价值为，重量为，背包容量是。怎样选取物品装入背包，使背包中价值最大。

六.应用（1）40遗传算法专题知识专家讲座第40页模型:

（二进制编码方法）

，装入物品 ，不装入物品

六.应用（2）41遗传算法专题知识专家讲座第41页比如，对于一个7个项目标背包问题，背包容量W=100，详细数据见下表，考查以下编码X=（1100110）这表示项目1、2、5和6被装入了背包，经过计算可知产生解不可行。背包问题示例i1234567wi40503010104030pi4060101032060Pi/wi11.20.3310.30.5242遗传算法专题知识专家讲座第42页怎样处理约束来保持可行性拒绝策略：可行解不易到达时，极难到达一个初始种群修复策略：将不可行解修复为可行，但将失去多样性。六.应用（3）43遗传算法专题知识专家讲座第43页处罚策略：要求设计适当处罚函数，但设计不好会掩盖目标函数优化。 下面，我们将分别采取处罚策略和解码法来处理上面背包问题。 六.应用（4）44遗传算法专题知识专家讲座第44页罚函数法令适值函数 ，其中是目标函数令 ，其中

注： 与 是 两个端点六.应用（5）罚函数45遗传算法专题知识专家讲座第45页函数式意义：⑴ 作用是使 ，确保⑵可行也处罚，只有当 时不处罚。⑶罚函数法目标：把解拉向边界，尽可能装满。六.应用（6）46遗传算法专题知识专家讲座第46页解码法——FirstFitHeuristic(优先适合启发式)解码法是一段修复程序(修复可行性方法)⑴步骤：将选上物品按降序排列；选前个物品，使 ；⑵解码法关键：怎样在GA中处理可行性问题⑶编码方法：采取次序编码 六.应用（7）47遗传算法专题知识专家讲座第47页例：=7

用次