遗传算法：鸭脖、鸡汤和九转大肠

“从零开始学数学建模”系列课程近期将更新“遗传算法”，课程详情关注微信公众号：数学建模BOOM，回复“课程”查看。

我们以做菜为例，理解一下遗传算法的基本思想。

一名大厨参加比赛，想要创造一道美味的菜肴，比赛由评委来打分。

首先随机生成多个原始配方，每种配方所用的原料不同，例如可用鸭脖、鸡肉、大肠等等。对应遗传算法中的初始化。

烹饪手法也不同，煎炒焖炸卤炖，爆烧溜涮煨烩。

这样一来，就有很多种组合：假设3种食材，12种烹饪手法，那么就有36种配方；而现实情况要远远比这复杂，例如放多少克盐？加不加香菜？烹饪时间多久？等等。多种因素考虑进去，可能的情况会非常多，我们无法每一种情况都尝试一遍。

那么较好的办法是，将现有的原始配方做成菜，由评委来打分，再选择分数高的配方，进行配方交叉，创造一组新的配方。而分数低的配方直接舍弃。这一步对应遗传算法中“交叉”的操作。

这样一来，我们保留了一部分评分高的配方要素、舍弃了评分低的配方，做出来的新菜就更有可能也是道美味佳肴。

例如配方A和配方C的分数都高，A是卤鸭脖，C是炖大肠；那么配方交叉尝试新方案：“炖鸭脖”或“卤大肠”。

为了增加创新和变化 ，有时会在配方交叉之后，再添加或替换某个食材或更换烹饪方式。

对应遗传算法中“变异”的概念。就像是在配方中随机使用了一些与原配方无关的调料或者做法。

例如前面我们交叉配方后准备做“炖鸭脖”，然后突发奇想改成了“炸鼠片”。

注意，这种尝试可能带来惊喜（提高评分），也可能有惊无喜（试试就逝世），所以并不是每次交叉配方后都进行变异，一般小概率进行。

不断重复进行“评分、交叉、变异、新配方做菜”→“评分……”，直到没有改进空间（连续多次评委给的都接近满分了）为止。

做菜、生物学中的遗传和数学建模的遗传算法概念对比：

以上为遗传算法的简介部分。完整的遗传算法讲解（模型简介+适用赛题+例题与原理讲解+MATLAB代码求解）将在近期更新。关注公众号：数学建模BOOM可获取最新消息。