遗传算法原理.ppt

AGSAA的编码方式AGSAA采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为１，表示该弹药箱装入运输工具，为０则不装。第63页，共97页，星期日，2025年，2月5日AGSAA的解码和适应度函数AGSAA采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计算适应度函数值。第64页，共97页，星期日，2025年，2月5日弹药装载的启发式算法（1）定位规则（Locatingrule）定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。（2）定序规则（Orderingrule）定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。第65页，共97页，星期日，2025年，2月5日遗传算子的选择AGSAA的选择算子采用轮盘赌选择算子，并结合最优保存策略；突变算子采用基本位突变算子；同时，在突变运算之后，增加退火算子，以增强算法的局部有哪些信誉好的足球投注网站能力；交叉概率和突变概率为自适应概率，以提高种群的进化效率。第66页，共97页，星期日，2025年，2月5日交叉算子的选择由于AGSAA是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用传统方式进行，就有可能使个体的编码产生重复基因（即一个弹药箱编号在一个个体中出现两次以上），从而产生不符合条件的个体，因此，AGSAA采用的是部分映射交叉算子。第67页，共97页，星期日，2025年，2月5日部分映射交叉算子交叉前：87|43|126512|57|8346交叉后：83|67|124517|62|8345返回第68页，共97页，星期日，2025年，2月5日两个定义定义1：模式H中确定位置的个数称为模式H的阶，记作O(H)。例如O(10**1)=3。定义2：模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距，记作δ(H)。例如δ(10**1)=4。第31页，共97页，星期日，2025年，2月5日模式的阶和定义距的含义模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。第32页，共97页，星期日，2025年，2月5日模式定理模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。第33页，共97页，星期日，2025年，2月5日模式定理从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。返回第34页，共97页，星期日，2025年，2月5日积木块假设积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。返回第35页，共97页，星期日，2025年，2月5日2、遗传算法的收敛性分析遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和突变概率。第36页，共97页，星期日，2025年，2月5日种群规模对收敛性的影响通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。第37页，共97页，星期日，2025年，2月5日选择操作对收敛性的影响选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来