启发式搜索算法A* （可参考http://theory.stanford.edu/~amitp/GameProgramming/） 和遗传算法GA分别是精确搜索和近似搜索，两者原理完全不同。但是在研究过程中我发现，它们却有着内在的联系，如数据结构上非常相似，几乎可以一一对应，如下表：
前者原理是在一棵搜索树上，通过启发函数"直捣黄龙"，并尽量"砍枝"；后者原理是"养活"一群物种，通过适应度函数"物竞天择"，尽量保持多样化，让它们交叉，子代尽量继承父代优良基因，并通过变异来跳出局部最优。
若将两个算法并行求解，找到更好的解通知对方：GA可以用来繁殖出更好的解；A*可以提高"砍枝条件"。GA 虽然是近似求解，但是拥有的变异机制常常可以跳出局部最优，因此两种算法结合可以优势互补，我们暂且称此算法为GA*
*注，可能有同学会觉得奇怪，A*是用来规划路径的，怎么拖这里来了，其实改造下它可以用到好多地方。
总体思路如上图，对于一个离散型优化问题：
- 在一定条件下，A*, GA, GA*三种算法都可以独立求解；
- 若解空间可以组织成树型结构，那么就可以采用A*精确求解（当然其他两种也可以了）；
- 若解空间可以组织成树型结构，但是解空间太大，那么可以采用GA*混合求解；
- 若解空间无法列举，可以尝试设计GA。可以看出，其普适性最广，唯一缺点是不保证最优。
这个搜索框架具备良好的可扩展性，可以解决很多问题，下面简单列出UML类图，后续连载再step by step解释吧：）
Read full article from 编程之美学习 连载之十三：4.4 离散优化问题搜索框架 overview - Silver的日志 - 网易博客
No comments:
Post a Comment