Algorithm 版 (精华区)

发信人: Lerry (戒网·学习), 信区: Algorithm
标  题: 基因算法（GA）
发信站: 哈工大紫丁香 (2001年11月20日21:01:08 星期二), 站内信件

基因算法（GA）
GA 是一种启发式的优化法 （heuristic optimization method）， 它是通过既定的随
机搜索进行操作．优化问题的可能的解的集合被认为是 个体（individuals）组成的 人
群（population）． 一个个体对它的环境的适应程度由它的 健康度（fitness）表示．

一个个体在搜索空间里的参照物是用 染色体（chromosomes）表示的， 实际上那是一套
字符串． 一个基因 （gene）是染色体的一个片段， 基因是被优化的单个参数的编码．
 对一个基因的典型的编码可以是二进制（binary）或 整数（integer）。
通过仿真进化过程的重组 （recombination）， 突变 （mutation）和 选择 （select
ion） 找到新一代的搜索点，它们的平均健康度要比它们的祖先好．
根据 "comp.ai.genetic" FAQ，我们不论怎么强调 GA 在解决一个问题时不是纯随机搜
索都不过份． GA 使用随机处理， 但是结果明显不是随机的（比随机更好）．
    GA 结构化框图：
---------------------------
P(t)    时刻t时的父代（generation of ancestors at a time t）
P''(t)  时刻t时的子代（generation of descendants at a time t）
+=========================================+
|>>>>>>>>>>>  Algorithm GA  <<<<<<<<<<<<<<|
+=========================================+
| INITIALIZE t := 0                       |
+=========================================+
| INITIALIZE P(t)                         |
+=========================================+
| evalute FITNESS of P(t)                 |
+=========================================+
| while not STOPPING CRITERION do         |
|   +-------------------------------------+
|   | P'(t)  := RECOMBINATION{P(t)}       |
|   +-------------------------------------+
|   | P''(t) := MUTATION{P'(t)}           |
|   +-------------------------------------+
|   | P(t+1) := SELECTION{P''(t) + P(t)}  |
|   +-------------------------------------+
|   | evalute FITNESS of P''(t)           |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]