主题：【原创】试说遗传算法 1 -- 风满袖
家园 【原创】试说遗传算法 1 遗传算法（Genetic Algorithm）是什么？它是一种算法，它借助了生物进化理论，用来针对那些不能使用数学分析方法来解决的问题，例如NP（Non-deterministic Polynomial time）问题。推销者（或旅游者）的最佳行程就是个简单的例子，一个推销者（旅游者）要从他家乡开始旅行经过N个城市来达到自己的目的（推销或旅游），然后再返回老家。请给出一条最近的路线。这个问题在城市数N不多的情况下（小于12）很好解决，排列组合然后比较。一旦城市数量多了以后排列组合将爆炸性的增长（排列组合数为 N+1!/2），计算时间也将同比例的增长。例如当N为100时，大约有（5*10的159次方） 个排列组合，以现今的计算机能力大约需要运算（10的143次方） 年。这种问题在计算机学科里面称为NP问题，此类问题的特点是，随着问题涉及面（例子中城市数N）的增加，其计算量将指数性或失控式地增长。
那么遗传算法又是如何解决这个问题的呢？我想先简单介绍一下达尔文（Charles Darwin）进化论和格利高利.孟德尔（Gregor Mendel）遗传定律。后者孟德尔被称为现代遗传之父，他通过对大量数据的手工分析，发现了遗传的基本规律。
其中对进化论我们很容易理解，其核心思想为
第一，“Survival of the fittest”（适者生存），“Struggle for life”（为了生存而斗争）；
第二， 生物的基本特征将会被遗传到下一代身上，但这遗传如何发生，达尔文也不知道。
第三， 每一代生物中都会有一些个体随机异变，将一些新特征带到这个生物中去；
第四， 每一代能幸存下来的生物普遍来说都是最适合外部环境的，所以一个物种只要给他足够的时间，它可以适应环境的变化。
由于达尔文无法解释亲本的特征如何遗传给后代，所以他面临了很多科学家和的异议。十九世纪五十年代到六十年代，格利高利.孟德尔 通过植物培育试验开始解决这个问题。但是直到二十世纪初，遗传原理开始形成时，他的研究成果才广为人知。孟德尔通过多年细致观察豌豆的繁殖得出了以下结论：
第一， 物种的遗传是在每一个细胞中以指令代码的形式进行的。
第二， 这些指令代码被储存在染色体中
第三， 染色体是由很多基因组成
第四， 每个基因控制了一个特殊的物种个性（例如眼睛的颜色等等），因此有机体的全貌由基因控制。
第五， 染色体都是成对出现。在遗传中，在新一代中每个染色体都是由一对父染色体产生（分别来自不同的个体），其中具有“统治性”特征的基因将取代不具有“统治性”的基因。
好，只能介绍这么多了，生物不是我的专业，说不了很多，以上可能也有错误之处，还请河里各位高手指正。不过这些对于初步理解遗传算法已经足够了，现在我们就可以来看看遗传算法到底是怎么回事了。
元宝推荐：ArKrXe,家园 flower 家园 好文呀，支持支持，上花上花 当年尝试搞非线性的全局优化问题，胡乱看过写文章，厚厚，还是老大总结的清晰呀，赞一个。
家园 哈哈，吾道不孤锕 看来要有一包子。
家园 【原创】试说遗传算法 3 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问题有了初步解决的可能，接下来需要的工作就是慢慢改善，我觉得不久这类应用将会越来越多的出现在实际生活中。
终于写完了，虽然花了不少时间，不过知道自己水平有限，写得很一般，漏洞错误不少。不过我发这片东西的原意，第一就是想抛砖引玉，让高手指点。第二也正好整理一下自己的思路。呵呵。最后多谢各位捧场的朋友，能有耐心看完这几页干巴巴的东西。
元宝推荐：ArKrXe,家园 没能理会这种算法的精妙所在，说说俺们传统算法的思路吧 传统算法解决这类问题，也有两大类的。
第一是盲目搜索，代表的算法是广度优先和深度优先
广度优先是把每一步的可能性都列举出来、并以之为基础继续下一步，所以这种算法是发散性质的，不适于深度很大的搜索任务；
而深度优先则是优先发展深度，典型代表就是走迷宫――往前有路就一个劲向前；碰了壁则往回退一步再看看有没有别的出路.....这样的好处是很快就能查到解，但要想得到最优解则需要遍历完所有路径才行，一样不适于本问题；
第二大类则是智能搜索，代表算法是A*。
典型的思想呢，则是对下一步所有的局面进行分析、评估（自己定义“评估函数”），选取有发展性的节点进行下一步扩展（剪枝定界）。
这里最关键的自然就在于估价函数的策定了......
家园 其实,传统的搜索算法,有高效和快速的优点,但也有致命的缺点 尤其是智能搜索(还有个名字,叫启发式搜索),利用目标函数和适应系数(或惩罚系数)来选择当前最优的方案.
对于线性或近似线性的问题,启发式搜索效率很高.
但它致命的确定是,无法应付非线性的全局最优问题.用老的算法,往往只能找到局部最优解,而无法搜索全局最优.就象老话说的,道路是曲折的,搜索算法往往一发现道路开始下降就停止了,会很容易错过无限风光和看穿柳暗花明.
针对搜索算法的特点,还有很多改进的算法,好象有什么禁忌算法(名字不确定翻译的对)之类的.
但针对非线性的全局最优,好象只有遗传和其他生物进化算法(偶只知道这些皮毛的,错了不要扁偶呀)可以比较保证找到全局最优解.在应用中,根据应用构造基因和快速验证目标函数往往是可以提高效率的捷径.
家园 【探讨一下】GA其实是一种优化算法 确实没有什么太过精妙之处。
你说的智能搜索，我的理解似乎不适合我举的推销者例子，因为在推销者的例子中他需要走过每一个城市。而智能搜索似乎只能给出一条从出发点到终点的最近路线，并不能保证他能经过每一个城市，何况在推销者例子中他的终点和起点都是一个城市。所以我觉得智能搜索不适用这类NP问题。不知我的理解对吗？
家园 启发式搜索完全可以用来解决‘推销员问题’ 比如先构造出来一个初始解，即一个城市排列，然后试着以某种方式变换城市的访问次序，如果有某个新排列减少了总里程，这个新排列就成为当前解，然后在此基础上继续试着变换城市的访问次序。
家园 启发式搜索？这个思路和GA没什么不一样啊 能具体说说什么是启发式搜索吗？
家园 我胡说两句吧 其实我不太清楚‘启发式搜索’这个词对应的英文术语到底是什么，或许结合了‘启发’的搜索就是‘启发式搜索’吧。在这我就大概谈谈‘启发’（heuristics)是什么意思吧。当对一个问题无法找到一个完全科学的、确定性的方法，例如软件测试问题，或是没有现实可行的此类方法的时候，例如推销员问题，人们就只好求助于‘启发’。‘启发’可以在大多数情况下帮助大家迅速找到比较好的解。比如构造一个‘推销员问题’的初始解的时候，可以某一城市为起点，离这个城市最近的城市选做第二个被访问的城市，离第二个城市最近的城市选做第三个被访问的城市，依次类推。每次选取离的‘最近’的城市就是这里使用的‘启发’。当然这个‘启发’并不太好，只是它比较简单，适合作为例子。获得一个初始解之后，一般可以用‘local search’（不知道怎么译，或可叫做邻域搜索）来改善初始解。我上面帖子里说的就是一种local search的方法。在local search中，也要用到‘启发’，比如每次选取当前解的邻域里对当前解提高‘最大’的那个解做为新的当前解。
另外，我感觉‘遗传算法’里选取‘最好’的解进行杂交、变异也是一种‘启发’，因为大家相信‘龙生龙，凤生凤，老鼠的儿子会打洞’。事实是否如此呢？大部分情况下确实是这样，但并不一定。
家园 谢谢风满袖兄对基因算法的介绍。 我说说我对基因算法的看法，请风满袖和各位指教。
我觉得基因算法的优越之处，在于它不是试图直接解决NP问题，而是在评估NP问题的解。从上次翻译中学到，对NP问题，在基因算法的解题过程中，验证解答比找到解答相对容易。用基因算法解决NP问题，NP问题就变成了两件问题：
1.寻找NP问题的解的评估方法
2.寻找快速有效的crossover的方法。
这两者都不是象直接解NP问题那样难。
至于初始解的来源，虽然有覆盖解题空间的要求，但不是解题的难点。同时，这种大规模的解题空间搜索，在评估不同解的时候不需要作大的数据共享，特别是适用于并行计算。
我的这本书里讲得是在半导体方面数字逻辑电路的布局布线中基因算法的应用。希望我在看完之后，也能像风满袖兄一样，基于具体例子对基因算法加以介绍。
家园 呵呵，说的好，花一朵 你说的比我好，期待你的大作。不过有一点在我文章里漏掉了，就是突变（mutation）的重要性，在每一代个体中进行一定比例的突变可以防止过早的产生遗传的一致性。
家园 加油。 家园 水平太差，写得自己都晕了 估计看得人也差不多了，大家多多包涵
。头晕眼花，赶紧下了，明天再补个结尾吧。
