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

我说说我对基因算法的看法，请风满袖和各位指教。

我觉得基因算法的优越之处，在于它不是试图直接解决NP问题，而是在评估NP问题的解。从上次翻译中学到，对NP问题，在基因算法的解题过程中，验证解答比找到解答相对容易。用基因算法解决NP问题，NP问题就变成了两件问题：

1.寻找NP问题的解的评估方法

2.寻找快速有效的crossover的方法。

这两者都不是象直接解NP问题那样难。

至于初始解的来源，虽然有覆盖解题空间的要求，但不是解题的难点。同时，这种大规模的解题空间搜索，在评估不同解的时候不需要作大的数据共享，特别是适用于并行计算。

我的这本书里讲得是在半导体方面数字逻辑电路的布局布线中基因算法的应用。希望我在看完之后，也能像风满袖兄一样，基于具体例子对基因算法加以介绍。

你说的比我好，期待你的大作。不过有一点在我文章里漏掉了，就是突变（mutation）的重要性，在每一代个体中进行一定比例的突变可以防止过早的产生遗传的一致性。

看来要有一包子。

当年尝试搞非线性的全局优化问题，胡乱看过写文章，厚厚，还是老大总结的清晰呀，赞一个。

这不，有熟悉的兄弟提醒一下，就OK了嘛。

老大的文章实在是好呀。

偶实在是期待呀，让风刮满楼吧！

传统算法解决这类问题，也有两大类的。

第一是盲目搜索，代表的算法是广度优先和深度优先

广度优先是把每一步的可能性都列举出来、并以之为基础继续下一步，所以这种算法是发散性质的，不适于深度很大的搜索任务；

而深度优先则是优先发展深度，典型代表就是走迷宫――往前有路就一个劲向前；碰了壁则往回退一步再看看有没有别的出路.....这样的好处是很快就能查到解，但要想得到最优解则需要遍历完所有路径才行，一样不适于本问题；

第二大类则是智能搜索，代表算法是A*。

典型的思想呢，则是对下一步所有的局面进行分析、评估（自己定义“评估函数”），选取有发展性的节点进行下一步扩展（剪枝定界）。

这里最关键的自然就在于估价函数的策定了......

确实没有什么太过精妙之处。

你说的智能搜索，我的理解似乎不适合我举的推销者例子，因为在推销者的例子中他需要走过每一个城市。而智能搜索似乎只能给出一条从出发点到终点的最近路线，并不能保证他能经过每一个城市，何况在推销者例子中他的终点和起点都是一个城市。所以我觉得智能搜索不适用这类NP问题。不知我的理解对吗？

尤其是智能搜索(还有个名字,叫启发式搜索),利用目标函数和适应系数(或惩罚系数)来选择当前最优的方案.

对于线性或近似线性的问题,启发式搜索效率很高.

但它致命的确定是,无法应付非线性的全局最优问题.用老的算法,往往只能找到局部最优解,而无法搜索全局最优.就象老话说的,道路是曲折的,搜索算法往往一发现道路开始下降就停止了,会很容易错过无限风光和看穿柳暗花明.

针对搜索算法的特点,还有很多改进的算法,好象有什么禁忌算法(名字不确定翻译的对)之类的.

但针对非线性的全局最优,好象只有遗传和其他生物进化算法(偶只知道这些皮毛的,错了不要扁偶呀)可以比较保证找到全局最优解.在应用中,根据应用构造基因和快速验证目标函数往往是可以提高效率的捷径.

比如先构造出来一个初始解，即一个城市排列，然后试着以某种方式变换城市的访问次序，如果有某个新排列减少了总里程，这个新排列就成为当前解，然后在此基础上继续试着变换城市的访问次序。

能具体说说什么是启发式搜索吗？

其实我不太清楚‘启发式搜索’这个词对应的英文术语到底是什么，或许结合了‘启发’的搜索就是‘启发式搜索’吧。在这我就大概谈谈‘启发’（heuristics)是什么意思吧。当对一个问题无法找到一个完全科学的、确定性的方法，例如软件测试问题，或是没有现实可行的此类方法的时候，例如推销员问题，人们就只好求助于‘启发’。‘启发’可以在大多数情况下帮助大家迅速找到比较好的解。比如构造一个‘推销员问题’的初始解的时候，可以某一城市为起点，离这个城市最近的城市选做第二个被访问的城市，离第二个城市最近的城市选做第三个被访问的城市，依次类推。每次选取离的‘最近’的城市就是这里使用的‘启发’。当然这个‘启发’并不太好，只是它比较简单，适合作为例子。获得一个初始解之后，一般可以用‘local search’（不知道怎么译，或可叫做邻域搜索）来改善初始解。我上面帖子里说的就是一种local search的方法。在local search中，也要用到‘启发’，比如每次选取当前解的邻域里对当前解提高‘最大’的那个解做为新的当前解。

另外，我感觉‘遗传算法’里选取‘最好’的解进行杂交、变异也是一种‘启发’，因为大家相信‘龙生龙，凤生凤，老鼠的儿子会打洞’。事实是否如此呢？大部分情况下确实是这样，但并不一定。