再上一篇:5. 5  二分图示例
上一篇: 第 6 章  遗 传 算 法
主页
下一篇:6. 3  为什么遗传算法会奏效?
再下一篇:6. 4  其它遗传操作
文章列表

6. 2  一个示例

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

以求解下列函数的最大值为例。

f(x) = 0.4+ sinc(4x) + 1.1sinc(4x + 2) + 0.8sinc(6x - 2) +

0.7sinc(6x - 4), x ∈[- 2,2] (6.1)其中

1  x = 0

sinc(x) = sin(πx) (6.2)

πx x ≠0

图6.4给出了函数f(x)在变量x 取值[- 2,2]时的曲线。f 的最大值1.501564对应于x= - 0.507179。

图6.4  函数f(x)在x∈[- 2,2]上的曲线

在运用遗传算法求解f 的最大值时,可以将x 的值用一个二值形式表达为二值向量。一个16位的二值数提供的分辨率是每位(2- (- 2))/(216- 1)= 0.000061。(6.3)式将变量域[- 2,2]离散化为二值数[0,65535]。

x = - 2+ 4b (6.3)

65535

其中b是[0,65535]中的一个二值数。例如,

#第52页-

v1 = (10 11 10 11 11 10 01 10) x = 2.93506

v2 = (00 11 00 11 11 11 11 10) x = - 1.87610

在运用遗传算法求解(6.1)式给出的函数的最大值时,用到了繁殖、交叉和突变等三

个遗传操作。

繁殖操作由上节给出的偏置轮盘实现。交叉操作将两个二值向量混合在一起,并生成

两个新的二值向量。在这里我们采用最简单的交叉形式,即随机选取两相邻位之间作为截

点,交换两向量在截点后的尾部以获取两个新的向量。

例如,若选取截点如下(以‖表示):

v1= (10 11 10 11 11 1‖0 01 10)

v2= (00 11 00 11 11 1‖1 11 10)

则两个新的二值向量为

v1= (10 11 10 11 11 1‖1 11 10)

v2= (00 11 00 11 11 1‖0 01 10)

突变操作十分直截了当。给定一个二值向量,随机选取一位并将其反置即可。例如,

若v1 中带下划线的一位被选中,则突变后的新向量为v1′

v1= (10 11 10 11 11 10 01 10) - 甗

v1′= (10 11 10 11 11 00 01 10)

在求解中用到了下列参数:

・ 群体大小= 30;

・ 交义概率= 0.3;

・ 突变概率= 0.01。

从不同的起始群体出发,运用遗传算法100次。算法找到最优解的成功率为80%。图

6.5给出了一次成功运用的收敛过程。注意,经过400次迭代,一个群体大小为30的遗传

算法在终止时已经评价了400 30个二值向量(有些向量会重复出现)。

图6.5  一次成功运用的收敛过程

#第53页-