遗传算法小记【理论篇】

随机化

是这样的，今天某人想点一下逆天的科技树，用于弥补不会模拟退火

遗传算法的核心主要是四个部分：估价函数，选择，交叉，变异

选择

适者生存，假设我们有 $n$ 条染色体， $f_i$ 表示第 $i$ 条对环境的适应程度（就是估价函数）

瞎几把乱选

随机，爱咋地咋地

占比选择法

根据 $f_i$ 占 $\sum f_i$ 的比例去 $rand$，实现可以考虑用前缀和

实际上比较搞笑的是基本都写的乱选，都懒得写占比

而且占比会导致复杂度变差，要多遍历种群，一般来说不如不写其实

选择的改进策略

精英保留策略

我们可以把适应性最好的若干比例或者若干个个体强行保留下来

这样更像自然选择适者生存的过程了，事实证明这样对算法的改进效果非常强

Stoffa改进方法

简而言之就是为了防止亲本生出弱智后代浪费时间，把dinner直接扔掉

不妨假设我们现在需要让收敛到最低 $f_i$，亲本适应度为 $x$，子代为 $y$ ，那么设 $\Delta=y-x$，如果 $\Delta<0$ 说明子代胜过了亲本，那么取子代自然是优的

假如 $\Delta>0$ 怎么办？好像生出傻子了，要不要扔掉

欸冷静，我们不能乱扔，我们考虑以一定的概率接受（有概率投胎到良心父母还愿意养一下）

此处给出一个概率函数：

其中 $t$ 是我们设定的一个参数，一般随着次数增加而增加（越到后期越不希望变化）

如果希望最大适应度同理差不多

好像有点模拟退火的味道

那我为什么不写模拟退火

交叉

杂交

其实就是亲本的杂交过程

推荐的实现方式是以 $0.5$ 的概率从父母继承染色体

也可以考虑从当前所有染色体随机选两个随机选一段交换若干次，随便吧

但是杂交通常会引起一点点问题，比如当染色体的信息是一个排列的时候随意交换会寄掉，所以杂交不一定能用

变异

考虑随机用一个较低的概率随机改动染色体的某一位，这种操作称为变异

自交

需要特殊考虑的是有些题不能杂交怎么办，那种题貌似变异也不是很能搞，也会破坏可爱的排列

可以考虑自交，随机交换亲本自己的染色体两个位置，我们叫他自交

本篇到此结束，理论部分到此为止