惩罚函数法在遗传算法处理约束问题中的应用
第24卷 第2期2002年2月
武 汉 理 工 大 学 学 报
JOURNAL OF WUHAN UNIVERSITY OF TECHNOLOGY
V o l. 24 No. 2 Feb. 2002
文章编号:1671-4431(2002) 02-0056-04
惩罚函数法在遗传算法处理约束问题中的应用
张 晶 翟鹏程
(武汉理工大学)
张本源
(湖北重型机器集团有限公司)
摘 要: 主要研究惩罚函数法在遗传算法中的应用。将传统优化方法中的惩罚函数法与遗传算法相结合, 研究了三种不同的惩罚函数法在遗传算法中的实现和应用, 编制了计算程序。通过对连续变量无约束优化、连续变量约束优化和离散变量约束优化等典型优化问题的计算分析, 将三种惩罚函数方法进行了比较, 指出了它们的特点及选用原则。同时, 对遗传算法中各种算子的不同形式也进行了研究和比较, 得出了一些有意义的结论。关键词: 遗传算法; 惩罚函数; 约束优化中图分类号: T B 12
[1]
文献标识码: A
遗传算法GAs (Genetic Algo rithm s) 是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法, 已成功地应用于函数优化、机器学习及复杂性问题研究等多种问题和领域中。现实生活中的大多数问题都是约束问题, 因此将遗传算法应用到约束优化问题中十分重要, 这其中的关键就是约束的处理问题。
通常处理约束优化问题主要有丢弃法、修理法、修改遗传算子法和惩罚函数法四种方法。
在理论分析的基础上, 编制了带惩罚函数的遗传算法程序, 对三种典型的优化问题进行了计算分析, 在惩罚函数、遗传算子的选择及相关控制参数的确定方面进行了分析和探讨, 得出了一些有指导意义的结论。
[2]
1 惩罚函数法的基本思想与应用
1. 1 在遗传算法和传统优化中使用的惩罚函数法的不同
在传统优化的惩罚函数法中, 优化过程从一点搜索到另一点, 根据约束特性构造惩罚项, 将惩罚项加到目标函数中, 使非线性规划问题转化为一系列的无约束极值子问题, 它们的极值是初问题的一个最优解。
遗传算法中惩罚函数法的基本思想是从传统优化中借鉴来的。遗传算法从包含有大量个体的初始种群开始搜索最优解, 通过选择算子把具有较好适应值的个体选择出来, 然后进行交叉、变异, 扩大搜索空间, 形成下一代种群。对于约束优化问题, 遗传算法中惩罚函数法是对于任一违反了的约束, 把一个惩罚项加到进化函数中, 使违反约束的个体的适应值降低, 再通过选择算子, 生成下一代种群, 从而在群体中保持一定数量的非可行解, 使遗传算法从可行域和不可行域两个方向进行搜索, 找到全局最优解。采用惩罚函数法的关键是确定合适的惩罚函数。
1. 2 惩罚函数法在遗传算法中的应用
1. 2. 1 进化函数的构造
构造带有惩罚项的进化函数一般有加法和乘法两种方式。1. 2. 2. 惩罚函数项的构造
下面是三种惩罚函数构造方法:
方法Ⅰ:Joines and Houck M ethod
求最小化的非线性规划问题, 采用加法形式构造进化函数, 惩罚项由变量惩罚因子和对违反约束的惩罚
收稿日期:2001-06-14.
作者简介:张 晶(1976-) , 女, 硕士; 武汉, 武汉理工大学工程结构与力学系(430070).
构成。
方法Ⅱ:Yo ko ta , Gen , Ida , and Taguchi Method
函数根据违反约束的相对惩罚系数构造惩罚项, 主要针对求最大化的非线性规划问题, 进化函数的构造采用乘法形式。
方法Ⅲ:Gen a nd Cheng Metho d [4]
在方法Ⅱ的基础上, 对不可行解定义了更严厉的惩罚。
2 带惩罚函数的遗传算法程序
根据遗传算法原理, 编制了遗传算法优化程序ga 2000。程序g a2000使用二进制编码, 将惩罚函数法与遗传算法(GAs) 结合在一起, 能够处理连续变量、离散变量、无约束优化和约束优化问题。程序流程如图1所示。各程序模块采用的方法如下:
(1) 交叉算子:单点交叉, 两点交叉, 均匀交叉; (2) 变异算子:均匀变异, 非均匀变异;
(3) 选择算子:2人竞争选择算子, 轮盘赌选择算子; (4) 子代的产生:双亲双子法, 双亲单子法; (5) niche 模块:小生境求解复杂问题;
(6) microga 模块:即采用小种群遗传算法(简称μGA) 。μGA 与SGA (Sim ple Genetic Alg o rithms ) 之间最主要的不同在于种群规模的选取上。在μGA 中, 一般可取群体大小为5, 而SGA 一般的群体取值范围在30～200之间。我们知道, 在群体规模很小的情况下遗传算法会因为信息量的不足而导致过早收敛到非最优解。μGA 成功的关键在于:a . 首先随机产生一代个体; b . 然后执行遗传算子选择和交叉; c. 若名义收敛, 则保留当前代最优个体, 同时随机产生若干个新个体形成新的一代, 否则按照第二步产生的新个体作为下一代的个体。反复执行后两步, 直到迭代次数达到最大迭代次数。不采用niche 技术和变异算子。
(7) 惩罚函数:惩罚函数的三种构造方法Ⅰ、Ⅱ、Ⅲ。
[3]
3 应用实例
应用遗传算法程序g a2000, 分别给出3个实例, 验证了程序的可靠性, 并得到有意义的结论。
3. 1 连续变量无约束优化
Ackley 函数优化问题:Ackley 函数是指数函数叠加上适度放大的余弦波再经过调制而得到的连续型实验函数, 表达式为无约束求最小值问题:
, x 2) =-20 ex p(-0. 2
222
x j ) -ex p(j co s(2π x j ) +20-2. 71282
2=12j =1
-5≤x j ≤5; j =1, 2
程序的优化结果与文献[4]中的结果同时在表1中给出。从表1可知, 对于简单函数优化问题, 2人竞争或轮盘赌选择算子的优化结果相差不大。例题中分别采用了均匀交叉、单点交叉、两点交叉等不同的交叉算子进行了优化, 从计算结果可知, 采用均匀交叉和两点交叉的优化结果基本相等, 单点交叉的优化结果相对较差。
表1 无约束优化结果对比
方法例题G A
g a2000(2人竞争选择算子) g a2000(轮盘赌选择算子)
最优变量取值(x 1, x 2)
-0. 000002, -0. 00000-0. 000038, 0. 001144-0. 000114, 0. 000038
最优结果-0. 005456-0. 00512-0. 005120
迭代次数1000100100
3. 2 连续变量约束优化
下面是一连续变量约束优化问题, 求函数的最小值:
5
min f (X ) =-10. 5x 1-7. 5x 2-3. 5x 3-2. 5x 4-1. 5x 5-10y -0. 5x i
i =1
表2 约束优化结果对比
方法全局最优解①ga 2000(Ⅰ) ②g a2000(Ⅱ) ③g a2000(Ⅲ) ④ga 2000(Ⅰ)+microg a ⑤ga 2000(Ⅱ)+microg a ⑥ga 2000(Ⅲ)+microg a
最优结果-213-211. 8-213. 2-211. 8-211. 9-213. 7-212. 2
x 1x 2x 3x 4x 5y
(0. 000, 1. 0, 0. 000, 1. 00, 1. 00, 20. 00) (0. 005, 1. 0, 0. 006, 1. 00, 1. 00, 19. 88) (0. 094, 1. 0, 0. 062, 0. 85, 0. 90, 19. 98) (0. 006, 0. 9, 0. 004, 0. 93, 0. 98, 19. 91) (0. 006, 1. 0, 0. 006, 1. 00, 1. 00, 19. 88) (0. 125, 1. 0, 0. 000, 1. 00, 1. 00, 20. 00) (0. 004, 1. 0, 0. 003, 0. 99, 1. 00, 19. 99)
6. 0486. 355. 9126. 0726. 756. 013g 1
2
g 1=6x 1+3x 2+3x 3+2x 4+x 5≤6. 5 g 2=10x 1+10x 3+y ≤20 0≤x i ≤1 0≤y
g 219. 9921. 5420. 0120. 021. 2520. 06
迭代数
[**************]
表3 遗传算法与拟满应力算法结果对比
杆件号
1
拟满应力
截面积/mm 2应力值/M Pa 与[σ]比值截面积/mm 2
应力值/MPa 与[σ]比值
507. 6114. 10. 76497. 8117. 40. 78
2
3
4
5113. 229. 50. 197
6174. 9145. 30. 97235. 9135. 00. 9
7
8
9
10
重量/kg
113. 21063. 7507. 647. 8-95. 96-68. 10. 32
0. 96
0. 68
736. 7265. 90. 79
0. 95
338. 2113. 2
35. 38
0. 96
0. 68
119. 2-95. 3144. 7-67. 5
遗传算法
145. 91063. 7334. 3174. 981. 3-95. 5-84. 20. 540. 960. 84
58. 7
0. 39
736. 7334. 3265. 9308. 6
118. 2-77. 9149. 7-54. 3232. 720. 790. 780. 9980. 36
注:工况2的应力值
三种方法①、②、③分别采用惩罚函数法Ⅰ、Ⅱ、Ⅲ, 种群规模为20; 后三种方法④、⑤、⑥采用μGA 及三种不同的惩罚函数, 种群规模为5。表2中列出的结果采用的遗传算子是:2人竞争选择算子、均匀交叉算子、
均匀和非均匀变异算子, 这种组合的优化结果较好。
从函数值、约束的满足程度、迭代次数及参数的选择难度等4个方面对三种惩罚函数方法进行分析。方法Ⅰ的函数优化值为-211左右, 与全局最优解相差较大。待定参数最多, 有C 、T、U, 交叉概率、变异概率5个。在相同的交叉概率、变异概率及种群规模下, 不采用μGA 方法时, 迭代次数最大, 但这种方法对约束条件的满足程度最好。方法Ⅱ的函数优化值为-213左右, 比全局最优解的值还好。待定参数有4个, 与方法Ⅰ相比较, 待定参数少。不采用μGA 方法时, 收敛速度比方法Ⅰ快, 但此方法对约束条件的满足程度最差。方法Ⅲ的函数优化值在方法Ⅰ、Ⅱ的函数优化值之间, 待定参数的个数同方法Ⅱ。对约束条件的满足程度在方法Ⅰ和方法Ⅱ之间。
与前三种方法分别进行比较, 后三种方法采用microga 模块。μG 种群大小一般为5, 在处理约束优化问题时参数更少, 收敛快。
第24卷 第2期 张 晶等:惩罚函数法在遗传算法处理约束问题中的应用
59
3. 3 十杆桁架结构截面优化
遗传算法的优化过程是在离散空间进行的, 对于离散变量优化问题, 遗传算法有非常好的效果。
图2所示十杆平面桁架结构。各杆件均为单根热轧等边角钢(GB 8978-88) 铰接, 设杆件可供选择的截面有16个截面取值为:(113. 2, 143. 2, 145. 9, 174. 9, 185. 9, 235. 9, 265. 9, 297. 1, 308. 6, 334. 3, 338. 2, 497. 8, 507. 6, 736. 7, 791. 2, 1063. 7) (m m ) , 弹性模量E =200GPa, 材
+]=150M Pa, 材料许用压应力[-]=100M Pa , 材料密料许用拉应力[e e
2
度为d =7. 8g /cm。此桁架承受两种工况, 工况1∶P 1=40kN , P 2=0;
工况2:P 1=60kN , P 2=20kN 。求解目标函数为结构最轻, 约束条件为两种工况下的应力约束条件, 变量为各杆件截面积。
10
3
图2 十杆平面桁架受力图
采用遗传算法, 目标函数为min i A i L i , 约束条件为±e i -[d e ]i ≤0, 进化函数采用加法形式, 采用micro-i =1
ga 模块, 种群规模为5, 惩罚函数法为Ⅰ, 选择算子为2人竞争选择算子, 均匀交叉概率0. 5, 均匀变异概率为0. 0, 惩罚参数c =0. 5, T =0. 042, U =0. 38, 迭代次数为50次。将计算结果与拟满应力结果[5]进行比较, 如表3所示。从表3中可知, 与惩罚函数结合的遗传算法可将结构的重量降至32. 72kg , 拟满应力法可将结构重量降至35. 38kg; 遗传算法优化结果中杆件的应力分布比拟满应力结果中杆件的应力分布好。
4 结 论
a. 惩罚函数法的选择, 由进化函数、目标函数及约束条件等来确定, 不同的惩罚函数法适用于不同的场合。方法Ⅰ可以更好的满足约束条件; 方法Ⅱ可以求得较好的优化目标值, 但对目标函数的形式及约束程度有一定的要求; 方法Ⅲ介于方法Ⅰ、Ⅱ之间。
b . μGA 方法对于种群大小、交叉概率和变异概率等参数的确定比较简单。
c. 均匀杂交算子和两点杂交算子在大多数问题上的精度相差不大, 均匀杂交略好于两点杂交, 但这两种交叉算子都好于单点交叉算子。
d . 对于简单优化问题, 2人竞争选择算子与轮盘赌选择算子的效果相近; 而对于复杂优化问题, 2人竞争选择算子优于轮盘赌选择算子。
参考文献
[1] Ho llo nd J . Adaptation in N atura l and A rtifica l Sy stems [M ].Ann A rbor :U niv er sity o f M ichig an Pr ess , 1975. [2] 任平. 遗传算法(综述) [J ].工程数学学报, 1999, 16(1):1～8. [3] Kalmanje Krish nakumar. M ic ro-ge netic Algo rithms fo r Sta tio na ry and N o n-sta tio na ry Function Optimiza tio n [J].Intel-lig ent Co ntro l a nd Adaptiv e Sy st em s, 1989(1196):289～296.
[4] 米凯利维茨Z . 演化程序-遗传算法与数据编码的结合[M ].北京:科学出版社, 2000.
[5] 郭鹏飞, 韩英仕, 魏英姿. 离散变量结构优化的拟满应力设计方法[J ].工程力学, 2000, 17(1):94～98.
Application of the Penalty Function Combined with Genetic Algorithm
Zhang Jing Zhai Pengcheng Zhang Benyuan
Abstract : T his pa per studies the applica tion of penalty func tion combined with Genetic Alg o rithm s (G As ). T hree differ -ent methods for co nstrained optimizatio n pr oblem is described , w hich is compar ed with the co nv entio na l pena lty func tion method. The selection of the key pa rameter s and g enetic o perato r s is discussed. The calcula tio n r esults o f th ree co mputa tio nal ex amples ar e giv en. The cha racteristic of the thr ee m etho ds is pointed. Th e penalty function combined w ith G As is show n to be steadily co nv er gent a t g lobal optimum .
Key words : Genetic Algo rithms; pena lty function; co nst rained optimiza tio n
: M. S. , Scho ol of St ructural Eng ineering a nd M echa nics, W U T , W uha n 430070, China.