遗传算法ppt课件

1、.第1，3章遗传算法，2，5。遗传算法的各种变形5.1其他编码方法5.2基因运算中的问题5.3相容性函数校准5.4选择策略5.5停止标准6。应用，遗传算法，3，5.1其他编码方法顺序代码：不允许重复的1到n的自然数的不同顺序编码，即自然数编码。该法适用得很广，包括分配问题、旅行企业问题、独立执行型日程问题等。合法性问题：是否遵守采用的编码规则，5 .GA的各种变体(1)，4，实数编码：r是实数集合的特征。运算简单但不反映基因的特性整数编码类似于顺序编码，但是编码对于新产品输入、时间优化、伙伴选择例如：322345对于顺序编码是合法的，对于整数编码是合法的。010200错误的01编码；5 .GA

2、的各种变体(2)、5，5.2基因运算的问题是在顺序编码基因运算的过程中遇到非法编码。这是2 :的拒绝或修改战略。示例：双切线相交后，后代编码无效21 345 67 21 125 67 43 125 76 43 345 76可以使用以下修正策略来使用上述编码：5 .GA的各种变体(3)，6，修改顺序编码的合法性：相互恢复策略分类如下：部分映射交叉顺序交叉循环交叉，5。GA的各种变体(4)，7，部分映射交叉点(PMX) (Partially Mapped Crossover):使用特殊更正程序解决简单双切点交叉点导致的非法问题，步骤： 933；切点x，y；中间部分交换；确定映射关系；根据映射关系将

3、未改变的部分恢复为合法性。5 .GA的各种变体(5)，8，PMX示例：5。GA的各种变体(6)、9，顺序交叉(OX )Order Crossover:可以看作是具有其他修正的某些贴图相交的变形。步骤OX:选择切点x，y；中间部分交换；切掉y字后，从第一个基因开始记载原始序列，去除现有基因；触点的y后，从第一个位置开始依次填充。5 .GA的各种变体(7)，10，OX示例：5。GA的各种变体(8)、11，OX的特征：保持良好的相邻关系、前后关系以满足TSP问题的要求，但不保留位值功能。5 .GA的各种变体(9)、12，循环交叉(CLARiiON)Cycle Crossover基本思想：子字符串位置

4、的值必须与父级相同位置的位值相同。步骤CX:选择第一个元素作为第一个元素，选择第一个元素作为第一个元素；5 .GA的各种变体(10)、13，找到的第一个元素重复此过程，直到指定的相对位置获得的第一个元素。对最早的基因按压、基因循环原理重复上述过程；重复上述过程，直到完成所有位。5 .GA的各种变体(11)，14，CX示例：5。GA的各种变体(12)、15，CX的特征：与x的特征不同，CLARiiON保留适合分配问题的位值特征。OX维持着相邻关系，为了满足TSP的要求，维持着先到先得的关系。5 .GA的各种变体(13)，16，变异的修复策略转移变异(最常用)随机选择染色体上的两个位置，以交换基因

5、的位值。范例：4 3 15 6 7 4 5 2 3 6 7位移变异：可选第一个例证的位移：4 3 1 5 6 5 3 1 6 7，5。GA的各种变体(14)、17，实数编码的合法性修复交叉短切点相交，5。GA的各种变化(15)、切点、18，双切线点相交(与单切线相交)此方法的最大问题：如何在实际优化中保持可行性。5 .GA的各种变体(16)，19，5。GA的各种变形(17)、凸组合相交：克服上述简单相交操作所产生的解决方案的可行性。约束是可以保持可行性的凸集，但由于方差太差，又出现了向中间收敛的问题。，20，可变位值变异：可选加(可变步长)，例如，5。GA的各种变体(18)，21，渐变方向上的

6、变化缺点：仅适用于目标函数最小的问题。实例：可以对最大化问题执行以下操作：优点：考虑问题本身的特性时效率更高。但是染色体的个体数倾向于聚集，因此个体数的多样性可能会下降。5 .GA的各种变体(19)，22，5.3相容性函数的校准(Scaling)，5 .GA的各种变体(20)、23，校准目的：使适合函数不太大，选择压力有一定差异的概念：选择压力是选择总量好与坏个人的概率的差异，差异称为选择压力。注意：在上述概念中，“差异大小”基于匹配函数。5 .GA的各种变体(21)，24，局部搜索，广域搜索和选择压力的关系局部搜索和广域搜索是GA的一对矛盾。如果只关注本地搜索，很有可能陷入局优秀，如果只关注

7、广域搜索，精密开发能力就不强。因此，好的算法必须同时考虑上述两方面。一般来说，算法应使用较小的选择压力，侧重于广域搜索，然后开始。随着迭代的进行，逐渐偏重于本地搜索，使用更大的选择压力完成。5 .GA的各种变体(22)、25，合法校准方法线性校准：函数表达式：目标函数的匹配函数，5。GA的各种变体(23)、26，对，=1，=，函数表达式：，对，=-1，=，=，函数表达式：，上述是一个较小的数字，使种群中最差的个体仍然有机会繁殖，增加种群的多样性。5 .GA的各种变体(24)，27，动态线性修正(最常用):线性修正的参数随重复次数的增加而变更时，具有动态线性修正的优点。计算中的时间函数表达式很脆

8、弱。重复指标最常用的最大化=1，函数表达式：5。GA的各种变体(25)，k代的最小目标函数值，28，5。GA的各种变体(26)、29，5。GA的多种变体(27)，引入目的：调整选择压力(好的、坏的或坏的个人选择概率的差异)，扩大广域搜索范围，保存人口的多样性，区域搜索细微保持聚合。下图开始：选择从以下项开始的压力.30，幂律校正：函数表达式：的值，1点选择压力增加1点选择压力减少对数校正：函数表达式：对数校正的效果：缩小目标函数值的差值，5。GA的各种变体(28)，31，指数校正：函数表达式：指数校正的作用：扩展差分窗口技术：函数表达式：上一代w的最小目标值，考虑到每一代的波动，记住，5。GA

9、的各种变体(29)，32，规范化技术：函数表达式：规范化技术的作用：映射到(0，1)区间，抑制超级染色体正则化技术的实体：5。GA的各种变化(30)、33，5.4选择战略传统的GA选择和遗传一起进行，即使子孙不如上级，也不能修改。下面介绍的选择策略都是先天遗传后选择的。这样，示例空间已扩展，可以选择的对象更多。5 .GA的各种变体(31)，34，剪切选择：选择最佳的第一个T对象，以获得平均NP/T的生成机会，每个对象的选择概率为1/T。例如，NP=100，T=50表示100名学生，成绩前50名学生。人均选择概率是1/50，平均有2个机会。缺点：此方法在适应值的排序上花费更多的时间。，5 .GA

10、的各种变体(32)、35，选择顺序：步骤：从好到坏定义所有对象的选择概率。最佳对象的选择概率如下：5.GA的各种变体(33)，36、36、由于限制性规范化，选择顺序的优点包括：选择概率可以离线计算，节省算法运行时间，控制选择压力。缺点：固定选择概率，无法调节选择压力。5 .GA的各种变体(34)，37、示例：和：随机生成的旋转、对象选择、5。GA的各种变化(35)、第一个i-1对象的选择概率、第一个I对象的选择概率、38，比例选择：对象I的选择概率命令：使用动态校正调整选择压力，使用旋转轮方法执行相同的群体选择。5 .GA的各种变体(36)，39，5.5指定停止标准最大代数(常用):此方法简单

11、但不准确。在人口中检查赤道的一致性：保持历史上最好的个体。计算公式：或第二种方法很难实施，因此很少使用。5 .GA的各种变体(37)，40，背包问题狗物品的价值，重量，背包容量。如何选择要放在背包里的东西最大限度地提高背包的价值。6 .应用(1)，41，模型：(二进制编码方式)，不装货，6。应用(2)、42，例如，7个项目的背包问题的背包容量W=100，具体数据如下表所示。检验代码x=(1 0 1 0 1 0)这表示物料1、2、5和6安装在背包中，计算结果无法解决。背包问题的例子，43，约束处理方法以保持可执行性拒绝策略：如果可执行解决方案不容易实现，则难以实现初始总体恢复策略：不可执行的解决

12、方案可行，但失去多样性。VI。应用(3)，44，惩罚策略：需要设计适当的惩罚函数，但设计不当会掩盖目标函数的优化。以下将分别以处罚方针和解码处理上述背包问题。6 .应用(4)，45，罚函数命令适应性函数。其中是目标函数命令。此处注意：和的两个端点，6 .应用(5)，46，基于函数的意义：的作用是保证可以执行，只有在没有处罚的情况下才能处罚。罚函数法的目的：把解拉到界，尽量填满。6 .应用程序(6)，47，解码方法First Fit Heuristic(优先于启动仪式)解码是修复程序(可恢复性方法)。步骤：按降序排列选择；选择上一个项目，所以；解码的关键：在GA中解决可行性问题的方法编码方法：顺序编码，6 .应用(7)，48，例如：=7的顺序(3 2 5 1 4 6 7)表示选择物料的顺序优先于发现性保留。也就是说，=3，(3 2 5)问题：编码长度可变，如何交叉和转换，6 .应用(8)、30，50，10，40、100、49，可变长度序列编码的遗传算法插入交叉算法上的随机断点选择；在随机选择基因片段的断点；消除重复的基因。优先启发式获得可能的答案是6。应用(9)、50，例如，6。应用(10)、