用遗传算法解决一个简单问题

字数统计: 2,325字  | 阅读时长:约 8 分钟
总阅读量次


　　学习算法，就我看来，其实就是学习解决问题的一种思想或者方法，应该是一种体验过程的学习，在过程中感悟与升华，最终把它吸收转化成自己的独特的思想；在学习中感受与惊叹先贤的解决问题的思想，未尝不是一种乐趣?这不也昭示了学习本身就是快乐的过程吗？如果连学习都体验不到快乐，那还有什么能体验到快乐呢？
　　本文是可以作为遗传算法介绍性文章，是关于一次简单、浅显的利用遗传算法来解决函数优化问题的介绍性文章。

要解决的问题

求解函数 在区间的最大值。

知识准备

　　首先列举一下遗传算法的构成要素

1.染色体的编码以及编码方法

　　我们要把问题的解空间进行编码，以便于遗传算法能进行操作。编码方式主要有二进制编码，浮点数编码，格雷码等。

二进制编码

　　假设参数范围为,我们有长度为a的二进制串来编码，则共有种不同编码，可以将分成份，等分长度为，

因为当二进制串长度过长时会影响遗传算法的运行效率，所以这类问题就要重新考虑编码方式了。

浮点数编码

　　对于函数优化问题，例如本题，浮点数编码则更合适了。浮点数编码就是用在一定范围内的浮点数表示每个个体的染色体。

格雷码

　　其是一种绝对编码的格式，是具有反射特性和循环特性的单步自补码。这些特性保证了它不会出现重大错误。因为它的每次变化都只有相邻两位发生变化，即每次变化与上一次都只有一位不相同。而自然二进制串在向高位进位时却至少有$1$位不同。相比于改变多位，明显格雷码的改变一位更稳定些，且出错几率也更小些。其构造方法：

以二进制$0$为第$0$项，第$1$项改变最右边的位，第二项改变右起第一位非$0$的位的左边那一位，第三项改变最右边的位…如此反复，即可得到位的Gray code.

2.群体初始化以及计算个体适应度

　　适应度函数是评估个体的适应性的唯一标准，也是后面选择个体阶段的唯一标准。对于很多问题可以直接将目标函数作为适应度函数。遗传算法的目标函数不受连续可微的约束且定义域可以是任意集合。但对适应度函数有一个要求：针对输入可以计算出的、能加以比较的结果，必须是非负的。

3.遗传算子(操作算子)

选择

　　根据个体的适应度选择进入下一代的个体，个体的适应度越大，则其越有可能被选入下一代。选择机制有轮盘赌方法，最佳个体保存法、期望值方法、排序选择方法、联赛选择方法、排挤方法等。一般都采用轮盘赌方法。下面描述一下轮盘赌算法：

1.设种群数量为n，先计算出种群内所有个体适应度，
再计算出种群总适应度，
个体适应度与种群总适应度的比值得到个体选择概率。
积累概率表示从第一个个体的选择概率累加，累加到某项即为相应染色体的积累概率。
2.生成一个随机数，若,则选中号染色体;
3.若，则号染色体被选中。
对于积累概率，如下图先给出个体选中概率:


由图得积累概率:
$q(x{0})=0.2$
$q(x{1})=0.3$
$q(x{2})=0.7$
$q(x{3})=1$
染色体的选择概率越大，在上面饼图占的比例也就越大，被选入下一代可能性也就越大
轮盘赌选择算子在个体较少时，可能会出现不正确的反映个体适应度的选择过程，即适应的高的个体可能被淘汰了。此时就要考虑其他的选择算子。

交叉

　　交叉算子即把两个亲代个体的部分结构进行替换重组而生成新子代个体的操作。其两个特点：

  • 设计的交叉算子必须保证亲代的优良性状能在子代个体中得到遗传和继承。
  • 交叉算子的设计与问题的编码是相互协调的，即编码-交叉设计。
  • 对于二进制串编码，交叉算子主要有一点交叉，两点交叉，多点交叉，一致交叉。其中一点交叉的操作如下：
个体 对应编码
$P_{1}$ 01010010
$P_{2}$ 00101110

假设从左起第$5$位开始进行一点交叉，得到

个体 取出的二进制串
$P_{1}$ 0010
$P_{2}$ 1110

进行一点交叉后得到两个新个体，

个体 对应编码
$P_{1}’$ 00101110
$P_{2}’$ 01010010

这样就完成了一次一点交叉运算。

  • 对于实数编码，主要采用算术交叉算子。假设存在个体$P{1}$、$P{2}$，对于它们进行算术交叉后得到新个体$P{1}’$、$P{2}’$的运算如下,其中伪随机数$\lambda$$\in$[0,1]：

$\large P{1}’=\lambda P{1}+(1-\lambda) P{2}$
$\large P{2}’=(1-\lambda) P{1}+\lambda P{2}$

变异

引入变异算子有两个目的：

  • 使遗传算法具备局部搜索能力。当遗传算子通过交叉算子接近最优解领域时，变异算子可以使遗传算法快速向最优解收敛。在这种情况下，变异概率应取较小的值。
  • 使种群具备较好的群体多样性，防止遗传算法出现未成熟收敛情况。此时，比那一概率应取较大的值。

1.对于二进制编码，其变异方式为随机的选择某些基因位，对这些基因位进行概率性的翻转变异，即$0$变为$1$,$1$变为$0$。
2.对于实数编码，其变异方式为随机变异。使变异个体变量分量加上一个伪随机数，该随机数为均匀分布或高斯分布。
变异方式还有逆转变异算子，自适应变异算子等。

遗传算子的性质

　　交叉算子具备良好的全局搜索能力，是遗传算法的主要操作算子；变异算子具备局部搜索能力，是遗传算法的辅助操作算子。交叉和变异使遗传算法具备均衡的全局搜索能力和局部搜索能力。

回到上面的问题，

　　对于这个问题，我采取浮点数编码，下面是遗传算法的运行参数：

const double PI = 3.1415927;                 // π
#define N 50                                  // 群体规模
#define T 100                               // 进化代数
#define PC  0.75                              // 参加交配概率
#define PM 0.0875                            // 变异概率

完整实现代码请移至我的Github

　　说一下感想，对于解决问题的范式，无外乎就是从所有可能解决问题的方法中将这个方法找出来，也即搜索。最开始我们有广度搜索和深度搜索，它们都可能在有限时间内搜索到问题的解决方法。但是，它们是盲目搜索，在今天的计算机条件下，一来计算机能表示的状态空间有限，二来其运行速度对一些状态空间稍微大一些的问题，往往要花大量的时间去计算。所以睿智的前人就发明了启发式搜索，通过预先设置一些方法，引导搜索的方向，使它能更快速的进行搜索，得到更满意的答案。根据达尔文进化论，物竞天择，适者生存，不适者淘汰。我们有一种思想叫做类比，既然大自然能淘汰掉不适合生存其中的物种，保留适合的物种，那我们是否可以借鉴这种方式，淘汰掉不合适的搜索路径，留下适合的搜索路径，这样最后得到的就是最佳解决路径了。这就是遗传算法的本质了。这里只是见到了它的冰山一角而已。就当做领略风光了。

另外，在这里总结一下c语言获取伪随机数方法

1.先设置伪随机数种子

srand((int)time(0));

2.其次，获取随机数，假如要在子函数里生成随机数，则只能在主函数里设置随机数种子。也就是只用在主函数最开始设置一次种子就可以了。
下面是获取伪随机数的一般形式：

rand()%y + x

表示生成$[x,y+x)$的伪随机整数。
如果需要闭区间$[x,y+x]$的话，可以再给y加个1，即

rand()%(y+1) + x