icepro的遗传算法解析

这次为什么会突然提起遗传算法呢？主要是因为这次光光的学姐询问了一个关于多旅行商的MTPS问题，对此我没有做过这方面的研究，我最多做过的是一个单旅行商的TPS问题，这样一个多旅行商的多目标求最优解的方法还从未接触过，不过作为一个忠实的研究者，并不介意挑战来的有难度一点。

说起遗传算法，很久以前也玩过遗传算法，拿来做一下有意思的事情，比如当时我就做过一个图像的算法，拿一些_随机的多边形_，拼出一个图案，当时选的是火狐的图像，不过做了一些处理。

首先把火狐的图片切割成1616的区块，每一个区块取出色块的平均数，然后就认为这一块的颜色就是这个平均数的颜色，然后将拼凑出的图像，按照同样的规则求出每一个区块，并计算匹配率（方差的倒数10000）。

然后很遗憾的是，最后的图像误差是挺大的，当时跑了大概400代不是很多，不过可见的是值已经快速收敛了，但是可见的是结果不会再有更好的解决了。

然而令我不怎么开心的是这个实验是我高中的时候使用的，那时候的电脑已经摔坏了，悲剧的是，那时候我还没开始使用github，结局就是，数据已经灰飞烟灭了。

当时用的C语言吧，不过现在么我早就忘记C语言的语法了，还是那且算了吧，而且C语言对我来说一直都是噩梦般的存在，现在我当然不会再尝试去用C语言写这个了。

遗传算法是一种常见的搜索算法，为什么说是一种搜索算法呢？

那很简单因为遗传算法是在一个很大的解集里面，输入一个优势解集，然后通过这个优势解集去搜索和这个优势解集相关且有优势的其他解集，然后这些解就生成了一个有效的解集集合，他们对应的有各自的适应度（解），然后我们通过赌轮盘的方式，让适应度大的解能够被遗传下来，让适应度低的被淘汰。

而其中搜索算法就是交叉算子，变异算子，通过类似于遗传学中交叉和变异的操作来完成遗传保留优势基因，通过变异来寻找其他的可能解。

遗传算法最常见的编码方式就是二进制编码，比如：(2,1)

两个10进制数可以使用6位二进制码来表述：010001;

这是最常见的编码方式，通常的函数求近似最优解的时候都会使用这种编码方式。

这种编码方式的名字可能不太正确，这种编码通常用于TPS问题

比如某旅行商需要途经123456789点，每个点距离其他点的距离都不相同，假设旅行商从0开始，求旅行商总路程最短的方案。

使用这种编码可以有效解决上述二进制编码交叉时的问题，当然交叉算法也需要作出一定的调整。

这类编码的名字可能还是不太正确，这类编码可以完全表示某种含义，不过同样的其算法需要特殊设计。

代码是写好了有空继续更新

本文标题：icepro的遗传算法解析

作者授权：除特别说明外，本文由 icepro 原创编译并授权刊载发布。