今天我们一起来搞鸡，哦不，来探讨鸡兔同笼的问题。
鸡兔同笼是中国古代的数学名题之一。大约在1500年前，《孙子算经》中就记载了这个有趣的问题。书中是这样叙述的：
今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？
常规的解法这里就不讨论了，百度百科上面已经说得非常全了，今天我想尝试一下利用遗传算法的思路来解这个问题。是的，你们都被标题骗了，遗传算法才是今天的真正的主角，车门已经焊死，请乘客不要强行跳窗下车。
先替这个算法作个自我介绍，来自百度百科：
遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果.
划重点，遗传算法是一种求解最优解的方法。我们这个鸡兔同笼问题其实也可以看作是求最优解的问题，所以应用遗传算法理论上也是可行的，只不过遗传算法这里算是牛刀，用来杀鸡确是大材小用了。
下面继续来简单看一下遗传算法的计算过程：
1、选择初始生命种群，也就是用于进化的初始染色体们
2、循环评价种群中的个体适应度，这个适应度可以简单理解成染色体的优秀程度，所以这一步就是进化论里的优胜劣汰，越优秀的染色体越容易保留下来，就是概率更高，注意，这里只是概率高，并不表示只会淘汰染色体里最差的，如果每一步都选最优染色体，这就是典型的贪心，容易限入局部最优，而非全局最优。
3、改变种群，主要手段是交叉和变异，交叉就是交配，大家为了更美好的下一代交换一下祖传染色体。变异就是基因突变，我们用上帝之手让本来染色体上的基因发生一点小小的改变。
4、重复2和3，直到得到结果或者超过最大遗传代数。
很简单，就是在不断的挑选染色体，然后改变染色体，直到发展出我们需要的染色体为止。
这里面有一些设计算法时需要注意的地方，比如优秀的基因只是被保留的概率比不优秀的概率高，不是绝对要被保留，交配的概率需要大，这个好理解，如果完全不交配，那就不会产生比当前更好的染色体，变异的概率要小，因为如果变异概率过大，每次都产生我们不可预测的值，可能就变成随机了，效果会变差。
那下面就让小鸡和小兔来给我们演示一下遗传算法的工作过程。
选择初始种群
先确定种群，也就是染色体，既然要求鸡和兔子的个数，那就以鸡和兔子的数量作为基因好了，比如这样{10只鸡，10只兔子}，是携带两个基因的染色体，不过这样的数据计算机可不太明白，我们要说机话，将其转化成二进制序列，让电脑能够更方便的计算。从题目中我们可以推导出鸡最多不超过35只，兔子最多不超过23只，那就给鸡分配6个二进制位，给兔子分配5个二进制位，{10只鸡，10只兔子}可以表示成{001010，01010}，然后连起来，变成00101001010，这就是我们设计的一条基因序列了。那么我们再多随机几条出来，比如说我们得到下面的初始染色体：
00101001010, 01011101010, 00101001100，重新说人话就是{10，10}，{23，10}， {10，12}
评价个体适应度
接下来确定如何判断染色体携带基因的好坏呢，上帝现在随便决定一下，给每个染色体计算一下头和脚的数量，如果头大于35或者脚大于94了，就认为是最差的染色体，除此之外的，越接近35和94的更优秀，如果两两相比，各有一大一小，那认为同样优秀。那上面的按照这个原则排个序就是
{23,10} > {10,12} > {10,10}
好，现在上帝决定把{10，10}淘汰掉
交叉和变异
接下来上帝决定让留下的两位交叉一下，过程就是彼此交换一下基因，但不变异了，这时得到新的种群
{23，10}， {10，12}, {23，12}， {10，10}
上帝换个坐姿，再来一次
我们回过头再来评价一下，oh my god！{23，12}这个染色体竟然完美符合我们对优秀染色体的判断标准，我们的结果就得到了。
上面当然是我站在上帝视角精心设计的基因，才能在这么短的时间内得到结果，以上这些都是我YY出来的，并没有实验支撑，模拟这样的过程只是想深入㳀出的说明白这个算法。笔者先在这里挖个坑，后续会亲自写代码作实验，补充一下实验过程及结果。
遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用，旅行商问题就是最优路径问题，而笔者所在的公司是开发物流系统的，也有规划物流路径，优化货物装箱之类的需求，所以再次看到这个算法的时候勾起了学习的欲望，希望有一天能在公司的项目里落地。
网友评论