About Genetic Algorithm

Course is finished. Project is half on the way. It is time to glean the relevant stuff.

1. Discussion, maybe contrdiction, about genetic algorithm, in AI board of http://newsmth.net

如何深入学习<<遗传算法>>?

Some excerpts, challenger's point of view:
1) 没用的东西学他干吗?
2) by the way, GA是我本科毕业时作的论文, 10年过去了, 现在还在搞, 这帮老师也够混的.
[[Why do you think this is impressive? odd]]

3) fitness是启发函数，或者甚至是目标值
我觉得kernel方法也用的有点滥了，其实我觉得从模型入手解决问题不是正道，但是解决问题又不能缺少一个适合的模型。我相信统计是最有希望的一条路。不过或者有天才能走出另一条路，但GA这种方法，包括禁忌搜索，蚁群算法之类的，没有太多希望。

统计上也还有问题，比如说有很多模型仍然没有很好的实用算法，或者有比较苛刻的应用条件。不过值得乐观的一点就是，很多问题我们仍然处于牛顿时代，就是说，也许我们能发现一种新的方法，比过去的有效多了，原因并不是新的算法有多牛，而是过去的算法（也就是现有的）实在太烂了。。。

Some excerpts, agreer's point of view:
1) 实践上来说目前的文章里ga用的明显比sa要多, 而且我感觉ga或者更广义的演化计算的优势在于只提供了一个框架
演化算子的选择提供了很大的自由度，能针对不同问题设计不同算子, 出现了很多优化效率非常高的算法，实际工程应用也能见得到

要说文字游戏，ai里面有几个不是在搞文字游戏的？

2) To debate this:
选择本来就是一个启发的过程。随机算法大部分时候是用来解决没有好的确定性算法，包括好的启发性算法的问题。至于全局最优，只是个谣言。

这个同意, 按NFL理论来说，所有算法的平均性能都是一样的, 所以针对不同问题采用不同算法和具体的改进是十分必要的, 我感觉GA正是在这方面提供了一个宽松的结构

: 我说它扯淡，就是在编码和遗传这两个地方，并没有什么实质的理论支持。

fine, 实际上早期的优化算法都没有什么理论支持和收敛性证明，一般而言都是先有算法后有证明, 举个更悠久的例子，牛顿在17世纪拿无穷小量来研究物理问题，但是严格的数学基础, 直到19世纪才被数学家们艰难的完善. 我相信是会有比较完善的理论来阐释ga，但确实很困难就是了

3) 我也觉得GA没什么很大的道理，其用得的启发式知识还不如SA可靠，但既然大家都觉得GA比SA好，那么总还是有点道理的，起码在比SA强这个层次上。但论文中的结论真地很少有道理的，真的想搞点东西的人都需要自己动手做一遍才能确信。论文中胡说八道，明明是垃圾说得像是黄金的事情看到太多了，害得别人浪费时间跟着做一遍，浪费大家时间和感情，可恶死了。

我想没有付出，就没有收获的事情还是对的，真正尝试各种方法，有自己的体会，对不同方法有一种感觉。然后针对不同问题的特性，用最适当的方法对其建模，解决之，才是真正体现牛人牛的地方。这些东西在语音识别、手写体识别之类老牌模式识别领域的教科书上都能看到，那里面的方法，才是真正久经考验的方法，而不是信口开河。

Something interesting:

一个不大恰当的比方可以这么来看：有一个方法很笨（比如穷举法），另一个方法则通过一个相对小得多的时间以一个概率找到全局最优，但通过算法的合理设计，可以以一个较大概率找到一个满意解（许多工程实际问题并不一定要获得全局最优解，而是需要获得一个满意解）。 在这种情况下，GA就显得很有意义了。

至于该研究的东西嘛，那就更多了：算法框架的改进，参数规范化处理，遗传操作算子的设计（尤其是诸如FLOW SHOP、JOB SHOP这样的生产作业排序问题，遗传操作算子的设计好坏与算法效率的关系非常紧密），在单目标遗传算法基础上发展起来的多目标遗传算法及多层优化问题的遗传算法，更是可以解决传统基于权及约束规划方法所不能解决
的一般非凸及不连续多目标优化问题，而这些，只是GA伟大思想在我做课题方面的一些应用，比起它在其他工程设计领域的应用，就更是多得不胜枚举了：）

总言之，在研究算法方面要做点真正有突破的东西真的难，就象以前一位师兄所描述的做论文就想刨坑挖井，没读博士的时候发现坑其实很多，可以挖的方向很大；但真正开始做得深入了，才发现原来好挖的都被人挖光了：（

这是他一个玩笑比喻，但从一个侧面也反映了做这些基础算法工作的艰难性。以上是我对GA的一点点认识：它有自身的限制，但很有用

2. something worth more attention

1) Roger W's EC links
2) GP Search Interface

use IDS or security as key words