遗传算法课件

1、1，第3章遗传算法，2，5。遗传算法的各种变体5.1其他编码方法5.2遗传操作中的问题5.3适应度函数的缩放5.4选择策略5.5停止标准6。应用，遗传算法3.5.1其他编码方法的顺序编码：用从1到N的不同自然数序列进行编码，不允许重复，即也称为自然数。这种方法有着广泛的应用：分配问题、旅行商问题、单机调度问题等。合法性：是否符合采用的编码规则。5.遗传算法的各种变体(1)，4。实数编码：R是实数集的特征：操作方便简单，但不能反映基因的特征。整数编码类似于顺序编码，但编码允许重复应用：新产品投资、时间优化、合作伙伴选择示例：3212345对于顺序编码是非法的，但是对于整数编码是非法的。01020

2、0非法01代码；5.遗传操作中的问题在顺序编码遗传操作过程中会遇到非法编码。迎接挑战有两种策略：拒绝或修复。例如，在两个切点相交之后，后代编码是非法的21 345 67 21 125 67 43 125 76 43 345 76。我们采用以下修复策略使上述编码合法。5.遗传算法的各种变体(3)，6。顺序编码的合法性修复：交叉修复策略，分为以下几类：部分映射交叉、顺序交叉、循环交叉、5。遗传算法的各种变体(4)，7。部分映射交叉(PMX):通过特殊的修复程序解决简单双切点交叉造成的非法性，步骤：选择交换中间部分；确定映射关系；根据映射关系将未更改的部分恢复为合法。五、五、八、PMX示例的各种变体

3、五、六、九、十阶交叉的各种变体：可以将其视为具有不同修复程序的部分映射交叉。OX步骤：选择切点x，y；交换中间部分；在切点y后列出第一个基因的原始序列，并删除现有基因；从切点y后的第一个位置开始，依次填充。五、遗传算法的变体(7)、10、OX示例：五、遗传算法的变体(8)、11、OX的特征：邻接和优先关系得到很好的保留，满足了TSP问题的需要，但比特值特征没有得到保留。5.遗传算法(9)，12的变体，循环交叉(CX)基本思想：子串位置的值必须等于父串相同位置的位值。CX步骤：选择第一个元素作为第一位，选择第一个元素作为第一位；5.遗传算法(10)，13的各种变型，到由在中间找到的第一个元素分配

4、的相对位置，重复这个过程，直到在中间获得第一个元素，这被称为循环；根据基因旋转的原理，对第一个基因重复上述过程；重复上述过程，直到所有位都完成。五、遗传算法的各种变体(11)，14，CX示例：五、遗传算法的各种变体(12)，15，CX特征：不同于OX的特征，CX很好地保留了位值特征，适用于赋值问题；但是，OX很好地保持了相邻关系和优先关系，满足了旅行商问题的需要。各种变异的遗传算法(13)，16，突变转座突变的修复策略(最常用的)是在染色体上随机选择两个位置并交换基因位值。示例：4 3 1 2 5 6 7 4 5 1 2 3 6 7换档变化：选择一个换档到前面示例：4 3 1 2 5 6 7

5、5 4 1 2 6 7，5。各种变型的遗传算法(14)，17，实数编码的合法性，修复单切点的交点，5。遗传算法的各种变体(15)，切点，18，双切点交点(.遗传算法(16)、19、17的各种变体，凸组合交叉：可以克服上述简单交叉操作导致的解的不可行性。约束是一个凸集，它的可行性可以保持，但是它的离散性太差，出现了向中间收敛的问题。20，变化位值变化：添加任意一位(变化步长)，例如：5。遗传算法的各种变体(18)，21，梯度方向的变体缺点：它只能用于目标函数可微的问题。示例：可以采取以下行动来最大化问题：优势：考虑到问题本身的性质，效率更高。然而，染色体群体可能趋向于聚集，导致群体多样性差。5.

6、遗传算法的各种变体(19)、22、5.3适应度函数的缩放和5。遗传算法的各种变体(20)，23。校准的目的：为了使适应度函数不太大，选择压力的概念有一定的差异：选择压力是好的和坏的个体被选择的概率之差，大的差异意味着大的选择压力。注：上述概念中的“差异大小”与适应度函数有关。5.遗传算法的变体(21)，24，局部搜索、广域搜索和选择压力之间的关系局部搜索和广域搜索是遗传算法中的一对矛盾。只注重局部搜索很可能陷入局部优化，而只注重广域搜索将导致精确开发能力弱。因此，一个好的算法应该同时考虑以上两点。一般来说，该算法在开始时应注意广域搜索，用较少的选择压力来实现；随着迭代的进行，局部搜索逐渐被强调

7、，这是通过使用更大的选择压力来实现的。遗传算法(22)，25的各种变体，适应度线性校准的校准方法：函数表达式：它是一个目标函数，是一个适应度函数，以及遗传算法(23)，26，右，=1，=，函数表达式：右，=-1，=，函数表达式：上图，五。遗传算法(24)，27的各种变体，动态线性校准(最常用):当线性校准中的参数随着迭代次数的增加而变化时，获得动态线性校准。优点：计算简单，不占用时间。函数表达式：这是最常用的迭代索引。最大化=1，函数表达式：V .遗传算法的各种变体(25)，K代的最小目标函数值。增加的含义(在同一线性校准中的含义)是为了使最差的个体仍有繁殖的可能性，并且随着增加而减少的值是：

8、和，以便调整5的各种变量(26)和(29)。GA。引入的目的是调整选择压力，即好个体和坏个体的选择概率之差，以保持较宽的搜索范围。下图显示：开始时，我希望选择较小的压力，后来，我希望选择较大的压力，30。幂律校准：函数表达式的值：当1时，选择压力增加，当1时，选择压力减少。对数校准：函数表达式：对数校准的函数：减少目标函数值的差异，五、遗传算法的各种变化(28)，31、指数校准：函数表达式：指数校准的函数：扩展差窗技术：函数表达式：它是第一代W的最小目标值，考虑到每一代的波动，所以它有记忆。5.遗传算法的各种变体(29)，32。标准化技术：功能表述：标准化技术的功能：映射到(0，1)区间，抑制

9、超染色体标准化技术的实质：特殊动态校准，即其中：5。遗传算法的各种变体(30)，33，5.4选择策略。传统的遗传算法选择和遗传是一起进行的，但是即使后代不如他们的父母，他们也不能被纠正。下面描述的选择策略是选择前的继承。这样，样本空间扩大了，可供选择的个体数量增加了。5.遗传算法的各种变体(31)，34。截断选择：选择最好的前T个个体，让每个个体有1/T的选择概率，平均得到NP/T个繁殖机会。例：NP=100，T=50表示100名学生，选出前50名学生。每个人的选择概率是150，平均有2个机会。缺点：这种方法将花费更多的时间对适应值进行排序。5.遗传算法的各种变体(32)和(35)，顺序选择：

10、步骤：从好到坏对所有个体进行排序。如果最佳个体的选择概率被定义为0，那么第一个个体的选择概率是：5。遗传算法的各种变体(33)和(36)。由于归一化的时间有限，所以有以下公式：其中，顺序选择的优点是可以离线计算选择概率，节省算法执行时间。缺点：选择概率固定，选择压力不可调。5.遗传算法的各种变体(34)，37，例如，33，360，以及：使用旋转方法，随机生成选择个体的时间和时间的各种变体，5。遗传算法(35)，第一个i-1个体的选择概率，第一个I个体的选择概率，38，比例选择：个体I的选择概率是：使用动态校准，5。遗传算法(36)、39、5.5的各种变体。停止标准指定最大代数(常用):这种方法

11、简单但不准确。检查人群之间健康的一致性：保留历史上最好的个体。计算公式：或者第二种方法很少使用，因为很难实现。五、各种变型的GA (37)、40、背包问题，对于物品来说，值是，重量是，背包容量是。如何选择放在背包里的物品来最大化背包的价值。6.应用程序(1)，41，型号：(二进制编码方法)，加载文章，不加载文章，6。应用(2)，42，例如，对于一个7项背包问题，背包容量W=100，具体数据如下表所示，并且下面的代码X=(1 1 0 0 1 1 0)表示背包问题的例子，43，如何处理约束以保持可行拒绝策略：当可行解难以达到时，很难达到初始种群修复策略：修复不可行解为可行，但失去多样性。6.申请(

12、3)，44。惩罚策略：需要设计一个合适的惩罚函数，但是设计不好会掩盖目标函数的优化。接下来，我们将使用惩罚策略和解码方法来处理上述背包问题。6.用(4)、45、罚函数法来构造适应度函数，这是目标函数的排序，其中注：和是两个端点。6.使用(5)，46，函数公式的含义：函数是使它可行并且惩罚它，只有当它没有被惩罚的时候。罚函数法的目的是将解拉到边界并尽可能多地填充它。6.应用程序(6)，47，解码方法首先适合启发式(首先适合开发)解码方法是修复程序(修复可行性的方法)步骤：按降序排列所选项目；选择要制作的前几个项目；解码方法的关键是如何解决遗传算法中的可行性问题。编码方法：采用顺序编码。六.应用程序(7)，48，示例：=7。使用顺序(3 2 5 1 4 6 7)来指示选择项目的顺序。使用优先匹配启发式保持前K位，这样解是可行的，即：=3，(3 2 5)问题：编码长度是可变的，如何进行交叉和变异，VI。50、10、40、100、49，插入可变长度序列编码的遗传算法的交叉算法在顶部选择一个随机断点；随机选择插入基因片段的断点；去除互联网上重复的基因；请参见下一页的示例，了解根据优先级合适的启发式算法获得的可行解决方案。6.使用(9)，5