启发式算法详解——遗传算法

算法原理

遗传算法(Genetic Algorithm)遵循『适者生存』、『优胜劣汰』的原则，是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。通过选择、交叉以及变异等机制，在每次迭代中都保留一组候选个体，重复此过程，种群经过若干代进化后，理想情况下其适应度达到近似最优的状态。

用大白话说，遗传算法就是模拟一个人工种群的进化过程，进化会有淘汰、交配、生殖、基因突变。我们的一维数组在这里就相当于是一个基因，交配相对于两个数组互相交叉，产生出一个新的数组，基因突变则是随机交互数组中一对元素的位置。淘汰则是从一堆数组中丢弃那些表现不好的数组。

算法详解

1.初始化种群：对输入的数组进行打乱，每个打乱后的数组就是一个种群。

2.评估个体适应度：计算这个数组一维装箱的解，可以选择 first-fit、best-fit等贪心算法来计算.

3.选择：从种群中选取若干个解，这里有很多选择方式，例如轮盘赌选择、随机选择、最佳保留选择

4.交叉：从第3步选择出的数组中，进行两个数组元素的交叉。交叉必须保证只有数组的顺序发生变化

5.变异：以一定概率将第4步产生的数组进行元素交互

算法详解

代码比较长就不贴了

算法总结

从其他地方看到关于启发式算法的总结，觉得很有意思：

为了找出地球上最高的山，一群有志气的兔子们开始想办法:兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是贪心算法，它不能保证局部最优值就是全局最优值。

兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝他踏过的最高方向跳去。这就是模拟退火。

兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。

兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。