主题：【原创】试说遗传算法 1 -- 风满袖

Crossover也有很多种方法，比如：

1、OnePoint Crossover：随机产生一个数r（在本文例子中1<r<N），然后将两个染色体中从r点开始一直到结束范围内的所有基因进行交换，产生两个新的染色体。例如：

染色体A：AGTATC

染色体B：CAGCAT

然后随机选择一个一个数r（1<r<5），比如r=3。交换后：

染色体A：AGTCAT

染色体B：CAGATC

2、TwoPoint Crossover：随机产生两个数b和e，b代表开始，e代表结束。将染色体中位于b和e之间的基因进行交换。

3、N-Point Crossover：随机产生一个二进值的Vector，其二进值的数量和染色体中基因的数量相同。比如分别有五个基因的一对染色体，则随机产生一个有5个数的Vector：{0, 1, 1, 0, 1}。然后规定对相应在Vector中0位的基因进行交换，在这里就交换1位和4位的基因，其余的基因保持不变。

遗传算法的基本原理就是这样，繁殖新一代，选择，再繁殖。就像地球上所有生物一样，唯一不同的是在计算机上受到时间和计算能力的限制。我的理解，遗传算法的关键在于繁殖和突变，选择一个合适的方式进行繁殖和突变是整个算法的重点，但这也是最难的，因为没有一个通用的繁殖和突变方式适合所有的环境。人们必须自己在实践中积累经验然后进行总结得出合适自己的方式。

在应用中遗传算法适合于这类离散变量的优化问题，它可以在较短的时间里给出一个相对满意的答案。在现在全球化和生产程序逐步细化的环境下，不可知的变量和生产规模会越来越大，类似的NP问题将会越来越多的出现在供应，采购和生产等各个环节上。

比如现在生产和运输都讲究集中化，批量化，以求最低成本。但在销售时却讲究个性化，同样一辆汽车两个买主的要求可能完全不一样，这就是一对矛盾。如果讲究个性化销售你就很难降低成本，每人一个样啊；同样如果批量生产成本是低了，但产品千人一面，肯定销量不好。这类矛盾往往就是个NP问题，小产品还好点，象汽车之类的大件，这种问题就很严重了。还有在生产中，例如自动化制定所有工人的排班表，在工人人数少时没关系，很简单。但对上千上万人的工厂做一个公平合理的排班表（比如要满足不能让一个工人连续上两天夜班和上完夜班要休息等等各类条件），就会产生NP问题。遗传算法无疑为这类问题的计算机化处理提供了一个不错的方法。

但遗传算法的实际应用也有不足的地方，同样也是在繁殖和突变方式的选择。由于繁殖和突变方式的选择需要软件设计者有很多相关的实际经验，甚至是相关方面的专家，这样设计出来的软件才不会太离谱。而这类人才相对很少。同样由于通过遗传算法得不到一个最佳的答案，这类软件在目前只能起一个辅助决策的作用，最终结果还是需要人为修改、决定。

无论如何，遗传算法的出现使得NP问题有了初步解决的可能，接下来需要的工作就是慢慢改善，我觉得不久这类应用将会越来越多的出现在实际生活中。

终于写完了，虽然花了不少时间，不过知道自己水平有限，写得很一般，漏洞错误不少。不过我发这片东西的原意，第一就是想抛砖引玉，让高手指点。第二也正好整理一下自己的思路。呵呵。最后多谢各位捧场的朋友，能有耐心看完这几页干巴巴的东西。