种群遗传算法求解指派问题

前几日zhang88a悄悄的把遗传算法重构图片用python实现了，同时我也想发掘一下遗传算法的潜力，看看它对于各种优化问题是否都能轻松解决，我找了一个更加有实际意义的优化问题-指派问题，这个问题公认的解决方法是匈牙利算法。事实证明进化的力量依旧超乎我的想象，遗传算法几乎可以做到设置好环境之后解决任意的优化问题。

什么是遗传算法？

88a说了一个贝壳的例子，为了避嫌我举一个猴子的例子。在一个广阔的草原上长了一些很高很高的树，这些树上什么都没有，草原上生活了大量的猴子，他们有些可以爬很高，有些爬个几米就慌的要死，但是因为树上没有食物，所以爬的高不高根本不影响什么，爬的高的猴子也不会歧视爬不高的猴子。但是造化弄猴，有一天草原遭受了未知的外星科技的攻击，每隔几年就会有一场洪水光临这里，淹死那些恐高的猴子。那么过了很久很久这片草原上的猴子就都掌握会了爬树这个技能。这就是达尔文的物竞天择适者生存的理论，所以说遗传算法是大自然教给我们的算法。先贴一手达尔文的画像。

总之，通过上面这个小故事我们可以提炼出来一套算法。对于一个优化问题，需要提供的东西有：哪些解是合法的，优化的目标。那么合法的解就是猴子，我们向种群中投入大量的随机基因的猴子，优化的目标就是爬的越高越好，适应度就是一个猴子能爬多高，从种群中剔除适应度低的个体就是洪水，个体之间交换基因就是猴子的遗传过程，个体的变异就是猴子的基因突变。猴子的基因和性状就是算法的基因型和表现型，对于算法来说基因型的复杂度决定了问题的规模，88a的基因型包含了每个像素点的信息，可谓是非常庞大因此要算很久。

遗传算法如何构建？

对于一个种群遗传算法来说，需要包含这些概念：种群，个体，基因型，表现型，适应度函数，交叉算子，变异算子，选择算子。对于一些合法解约束比较少的问题，基因型和算子的构造是很简单的。遗传算法是一个极其灵活的算法，可以说是一个随心所欲的算法，我们把搜索结果的任务交给进化，而不是自己。我们只需保证几点：基因型和表现型能保留个体关于适应度的信息，适应度函数确实能保证更优秀的解有更高的适应度，选择算子趋向于让适应度高的个体更加容易生存，交叉算子趋于保护父代两个个体中相同的基因，变异要适度并且永远要变异出合法的个体。因为它这样灵活，我个人相信遗传算法有解决几乎所有优化问题的潜力。

什么是指派问题?

指派问题是一个经典的优化问题。我们假设现在有两个工人A和B，给他们指派两个工作j和k，A完成j需要1单位时间，完成k需要2单位时间，相反B完成j需要2单位时间，完成k需要2.5单位时间。现在每个人只能干一个工作，需要两个人花的时间最少。显然A分配j，B分配k是最优解。但是当这个问题扩张规模，答案就不再显而易见了，我们如果给8个人分配8个工作呢，或者给8个人分配10个工作，甚至给100个人分配100个工作，相信就没有人能立马报出答案了，因为问题的合法解在按照阶乘的规律增长。我们用一个叫效率矩阵的东西来记录每个分派的收益，向该矩阵寻找一个没有行列冲突的划分方法，对于假设的为题，效率矩阵就是[1,0.5;0.5,0.2]。解决这类问题的常规方法叫匈牙利算法，这是一种图论算法，可惜的是为了学习这个算法我们需要先研究研究一些图论的知识，而且这个算法只能解决这一个问题，这就让人很难受,当然匈牙利算法目前还是解决指派派问题的最好方法。

这波干了些什么？

很关键。指派问题不同于很多优化问题，它的合法解需要满足一个苛刻的条件，就是每个分派之间不允许冲突，这直接导致合法解的空间在同阶的空间里面是一堆离散的区域，这对遗传算法是一个不利的条件，相当于于一个局部最优解特别多的优化问题。遗传算法相对于最low的爬山算法的优点在于有一定的突破局部最优解的能力，不过对于很恶劣的环境也是力不从心。对于这个特定的问题，需要重新考虑基因型的构建，交叉算子和变异算子的设计。所幸这些问题都还没有超过我的能力范围，基因型用无重复采样函数实现了，交叉算子大胆尝试了一些别的思路，变异算子设计了两个部分，交换随机两个对象的分派以及在效率矩阵不是方阵时候追加的随机向一个未分配对象变异的变异方案。

看一下结果！

对于一个随机生成的10*10的效率矩阵

遗传算法给出的解

为了实现这个东东，设置了一个100个个体的种群，进化到100多代之后收敛到了最终结果

然后我失了智把问题规模变成20*20，也在500代左右收敛了。

机智的小伙伴应该发现了遗传算法的一个明显的缺陷，就是它不能保证这个解是最优的，它只能保证这个解是很优的，而且你不知道再运行个几千代会不会冒出一个更好的解来。所以这个算法在这里只能用来消遣，不能作为精确的解法来源。

最后题外话

初次接触到遗传算法的时候因为这东西给人眼前一亮的感觉，不像有些既没有创意又没有骚操作的算法，遗传算法几乎给了人一种重新认识算法的机会。我当时就跃跃欲试，并且找到了zhang88a同学，合伙弄了个已经有人提出过的用遗传算法重构图片的东西，可惜这玩意再matlab上消耗的运算量是惊人的，写完程序就没有跑出来过。于是在这个问题上我与88a算是分道扬镳，88a一直不愿意放弃这个问题，希望找到解决运算量问题的方法，最后用python重写了一波。我则是在考虑用遗传算法实现一些不那么庞大的问题，有段时间碰到任何问题我都要先想一下能不能套用遗传算法，终于以前研究的匈牙利算法浮现在脑海，试了一下果然有效。所以写了个这东西算是zhang88a的python实现单亲遗传算法的续集。我不知道88a为啥对遗传算法这么感兴趣，对于我来说这个算法给人一种用上帝视角操作数据的感觉，蛮好玩的。

顺便再此征集一下：对于遗传算法的应用如果哪个小伙伴有有趣的点子，欢迎私信我和zhang88a，这个很关键哦。