再上一篇:5. 4  均场网的参数
上一篇:5. 5  二分图示例
主页
下一篇:6. 2  一个示例
再下一篇:6. 3  为什么遗传算法会奏效?
文章列表

第 6 章  遗 传 算 法

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

遗传算法(GA)是模拟自然选择和遗传的随机搜索算法。密执安大学约翰・郝兰德(John Holland)提出这一算法的最初目的是研究自然系统的自适应行为并设计具有自适应功能的软件系统。近来,遗传算法作为问题求解和最优化的有效工具,引起越来越多的注意(文献[30][64][67][143])。

遗传算法是一种迭代算法。它在每一次迭代时都拥有一组解答。这组解答最初是随机生成的。在每次迭代时又有一组新的解答由模拟进化和继承的遗传操作生成。每个解答都由一个目标函数给予评价,而且这一过程不断重复,直至达到某种形式上的收敛。新的一组解答不但可以有选择地保留一些目标函数值高的旧的解答,而且可以包括一些经由其它解答结合而得的新的解答。

遗传算法的术语借鉴于自然遗传学。一个解称为一个符号串或染色体。染色体由决定其特性的基因构成,而基因又可以有称为等位基因的不同取值。目标函数称为适度函数,而一组染色体称为群体。遗传算法的一次迭代称为一代。

最简单的遗传算法包括如下组成部分:

・ 一个对参数空间编码的符号串表示;

・ 一个评价符号串的适度函数;

・ 一组产生成新的符号串的遗传操作;

・ 一组控制遗传操作的概率值。

典型的遗传算法步骤有:

(1) 初始化  随机生成一个符号串群体。

(2) 基于适度函数对符号串进行评价。

(3) 应用一组遗传操作生成一个新的符号串群体。

(4) 重复步骤(2)和(3)直到解答收敛。

遗传算法成功的关键在于符号串表示和遗传操作的设计。下一节介绍一种具有三个简单操作的遗传算法。

6. 1  简单遗传操作

遗传操作通过模拟进化和继承过程而生成符号串(新的或旧的)。繁殖、交叉和突变是三个简单遗传操作,它们在实际应用中给出了很好的结果。

6.1.1  繁殖

在大自然中,生命力最强的物种征服弱小的物种以确保其生存。运用这一适者生存的

#第49页-

法则,繁殖操作在旧的群体中“随机”选择符号串生成一个新的群体。选择并不是完全随机

的,它基于一个符号串相对于整个群体的适度值。

假定一个群体有6个符号串,而且它们的适度值如下:

符号串(i) 适度值(fi) fi/ fi

∑i

A 25 0.5 v

B 10 0.2 v

C 6 0.12 ^_

C 6 0.12 ^_

D 2 0.04 ^_

E 1 0.02 ^_

总数 50 1.0 v

注意,一个群体中的每个符号串不必是唯一的。fi/∑ifi被视为符号串fi在下一代中存

活的概率。这意味着具有较高适度值的符号串会有较大的存活机会。另外,在整个算法运

行过程中,一个群体的符号串数目是一个常数。繁殖操作生成的是一个同样大小的群体。

这意味着适度值较大的符号串最终会在群体中成为多数。

实现上述选择过程的一种方法是偏置轮盘。每个符号串在轮盘上占有一格,而格的大

小则与符号串的适度值成正比。在选择一个新的符号串时,先转动轮盘,待轮盘停下,落在

标记处的格所对应的符号串被选中。

图6.1  偏置轮盘

图6.1勾画出了上例中的轮盘。轮盘转动6次生成一代新的群体,且符号串的期望组

符号串(i) 存活率(pi) 期望次数(6pi) 7

A 0.5 3 1

B 0.2 1.2 1

C 0.24 1.44 ^

D 0.04 0.24 ^

E 0.02 0.12 ^

#第50页-

合为基于期望次数①,新的群体可能是{A,A,A,B,C,C}。很明显,如果繁殖操作被重复运用,适度值较高的符号串最终会在整个群体中占据主导地位。由于繁殖操作并不生成新的符号串,我们需要其它操作以探究新的解答。

6.1.2  交叉

交叉操作利用了来自不同符号串的基因经由交配而混合以产生新符号串的概念。由于基因表达了符号串的特性,如果不同符号串的“好的”特性得以结合,所得符号串可能会有更好的特性。

假定一个符号串的基因被排成一条直线,则两个符号串的交叉可按如下步骤进行(见图6.2):

图6.2  简单交叉操作

(1) 随机选择一个将每个符号串断开为两部分的点(截点)。

(2) 交换符号串的后一部分。

两个具有其父母双方基因成分的符号串由此生成。这一交叉操作是交换信息、生成新解的简单而有效的方法。需要注意的是,如果整个群体只有一种符号串,交叉操作不会生成任何新的符号串。可以利用突变操作来避免这种情况的发生。

6.1.3  突变

突变操作随机选取符号串中的一个基因并将其改变为一个不同的等位基因以生成一个新的符号串(见图6.3)。它将可变性引入群体,从而提供逃脱局部最小值的手段。注意,一个仅应用突变操作的算法等同于随机搜索。

图6.3  突变操作

因为突变操作可以有很强的破坏性,并非总要用到它,而是由一个突变概率(pm)来控制。与此类似的,交叉操作的运用也由交叉概率(pc)来控制。

一个简单的遗传算法可归纳如下:

① 选中某一符号串次数的期望值。

#第51页-

(1) 生成一个具有m个符号串的起始群体。

(2) 重复步骤(3)直至解答的适度值收敛。

(3) 生成一个新的m符号串群体。步骤如下:

① 应用繁殖操作两次,亦即用轮盘选出两个符号串。

② 如果pc> rand[0,1],则应用交叉操作于这一对符号串。

③ 如果pm> rand[0,1],则应用突变操作于这一对符号串。

④ 将生成的两个符号串加入新的群体。

下节用一个例子来说明遗传算法和遗传操作的用法。