在求解约束优化问题时，为了有效处理约束条件，克服文化算法易陷入局部极值点、混沌搜索优化初值敏感、搜索效率低等缺陷，将混沌搜索优化嵌入至文化算法框架，提出一种求解约束优化问题的混沌文化算法。该模型由基于混沌的群体空间和存储知识的信念空间组成，利用地形知识表达约束条件，标准知识和地形知识共同引导混沌搜索，并利用形势知识引导混沌扰动。实例表明，该算法具有较优良的搜索性能，尤其能有效处理高维复杂约束优化问题。
第5期 黄鶴,等:一种求解约束优化问题的混沌文化算法 1645 □半可行域 本文采用2“树的数据结构存储地形知识,该树的每个节 点代表一个信念细胞。在更新时,当某个信念细胞为半可行域 时,其所代表的解空间将被划分成2个f空间,分别由2个 子信念细胞表示。划分的方式为从n维决变量中随机选取 个维度进行区间的对等划分,直到树的最大深度。如图7所 图6信念细胞的划分 示,每个叶子节点代表当前域的最终划分。 地形知识措述为 D le[门=[le R (6) 其屮:Cas表示信念空间屮第i个信念细胞的类型;Cntl12表 示第i个信念细胞内可行解的个数;Cn2,表示第i个信念细胞 PQRS T U 内不可行解的个数;le表示第i个信念细胞对应的n维区间, 图7深度为2的2树存储的维空间 lc.,和ue.分别表示第i个信念细胞第j个决策变量的上下限。2.5接受函数 初始化时,地形知识只存储一个信念细胞,该细胞类型为未知 种群空间通过接受函数将个体经验传递到信念空间,实际 域,nt1和Cnt2为0,所代表的区域为标准知识所代表的区上是向信念空间提供一组最优子集。在最优化问题中,通常是 域,细胞类型为未知。 按一定的百分比取排行靠前的个体,一般取20%~25%,但也 2.4信念空间的更新 根据不同问题设置动态接受函数、模糊接受函数等。 信念空间的形势知识每代更新两次,一次在混沌搜索之在本文中,由于采取了锦标赛法更新形势知识,接受函数的处 后,一次在混沌扰动之后;标准知识和地形知识每代更新一次。理也相应作了改变。在更新形势知识时,接受函数将接受当代 24.1形势知识的更新 所有个体;在更新标准知识时,接受函数获取形势知识前TOP 本文对于形势知识更新的方法借鉴了锦标赛法。具休方位(本文TOP= popsize x25%)。 法如下 2.6影响函数 a)每次迭代后,将种群空间的全部个体集合和形势知识 在迭代过程中,信念空间的知识通过两种方式影响优化变 所代表的最优个体集合组成一个新的集合(文算法新集合量:a)在标准知识所代表的优胜区间附近和地形知识所表示 规模为2× wopsle) 的半可行域附近进行混沌搜索;b)在形势知识所代表的优秀 b)在新集合中随机选择出c个竞争者(一般c= pepsIn/个体附近进行混沌扰动。 2),将新集合中每个个体分别与c个竞争者比较适应值,记录2.6.1利用标准知识和地形知识进行混沌搜索 每个个体的胜利数,并将最优适应值的个体胜利数设置为最 标准知识存储了最优解最可能出现的范围,该范围用优胜 高,以保证形势知识存储了最优个体; 区间(4,)描述。由 Logistic映射产生的混沌变量在(O,1)上 c)选择胜利数最靠前的c个个体(本文e=ppie)作为在具有两头多中间少的分布特征。对于个体的每个决策变量 新的形势知识。 j,本文首先从地形知识中随机选取一个类型为半可行或未知 2.4.2标准知识的更新 的信念细胞,然后用这个信念细胞的上下限(le1,uc)和优胜区 假设第i个个体影响第j个决策变量的下边界,第个个间(l1,u)将j的取值范围(a,b)划分为五个区间:(a,1)、( 体影响第j个决策变量的上边界,则j的上、下边界及其对应的1e)、(l,c)、(ve,u)、(u,b),接着将混沌变量随机映射到 适应值分别为 这五个区间的任意一个。通过这种方法,新个体的每一维决策 x.,fx.,≤mrF(x)< 变量将主要分布在优胜区间和半可行域附近,即可行域与非 (7) Dtherwise 行域的边界上,充分发挥了半可行域的引导作用,达到了用标 f(x)ifx2,≤loF(x2)<l (8)准知识和地形知识来指导混沌搜索的日的。 otherwise a:+z;× f random x,fx1,≥orF(x)<U 4i +3i x Il-le I if random()=I otherwise ic:+z: x Ile, -uc. I if random()=2 (12) f(x2)fx,≥orF(x)< (10) herwise u:+3i x l if random()=4 2.4.3地形知识的更新 2.6.2利用形势知识进行混沌扰动 在选代过程中,每个个体是否可行取决于问题的约束条 形势知识是存储∫当前优秀个体的列表,是其他个体的典 件,因此每个个体都能反映其所在信念细胞的约束信息。假设范,用来指导其他个体的产生。其列表长度为群体空间规模的 第i个信念细胞内可行解的个数为Cnt1,不可行解的个数为大小。在本文算法中,形势知识是由混沌迭代形成的优秀个体 Cnt2;,则地形知识中第i个信念细胞 Class;的更新如下: 经验,存储了优秀个体的具体位置,因此,它弥补了混沌变量受 f Cntl=0 and Cnt2:=0 标准知识约束后丧失的全局性,具有较强的全局指导能力,能 feasible if Cntl >0 and Cnt2, =0 在搜索过程中起到逃逸作用 lass,= (11) uNfeasible if Cnt1, =0 and Cnt2 i>0 本文先进行混沌搜素,接着更新形势知识,得到一些优秀 semi-feasible otherwise 个体,再在优秀个体附近进行混沌扰动,有利于挖掘出更优秀 1646 计算机应用研究 第27卷 的个体,获取当前最优解的全局分布信息,因而能有效避免算 min fs(x)=(N+2)Dd- 汰陷入局部最优解。具体描述为 71785d4 2.7混沌文化算法的算法流程 12566(Dd2-d2)5108d (18) 综上所述,本文提出的求解约束优化问题的混沌文化算法 D-A 流程如下 D-d g 1≤0 )4=0 b)初始化混沌变量,随机产生初始混沌变量(不能为 针对前四个问题,采用本文提出的混沌文化算法进行求 Logistic映射不动点0.250.5和0.75); 解,与由 Slawomir等人提出的KM算法和由 Coello等人121 c)初始化样体空问和相关参数; 提出的文化算法(CAEP)进行比较(KM算法是一种比较有效 d)初始化信念空间中的形势知识和标准知识; 和前沿的处理约束优化问题的进化算法)。设置种群规模为 e)评价群体空间内个体适应度,若符合要求则结束,否则20,接受函数取前25%,标准知识每隔20代更新一次,形势知 往下执行; 识更新采用锦标赛法中的竞争者个数为10,地形知识采用23 f)更新信念空间的形势知认标准知识和地形知识 树的数据结构。将每个问题独立运行10次,每次最大迭代次 g)混沌变量迭代搜索,按式(2)产生新的混沌变量 数为2500,比较了10次运行后的最好结果、平均结果和最差 h)在信念空间标准知识和地形知识指导下,按式(12)进结果,如表1所示。其中,为实际最优值。 行混沌搜索 表1CAA与其他算法的对比 i)评价群体空间内个体适应度,更新信念空间的形势 函数 知识; 0.80361930665.539-0.095825 j)在信念空间形势知识的指导下,按式(13)进行混沌扰动; CAA 15.0-0.8019086-30665.539-0.095825 k)t=t+1; best CAEP- 15.0 0.77351 30665.5 0.095825 14.7864-0.79953 30)664.5 0.095825 1)转到e),直到满足终止条件。 CAA-15.0-0.6637489-30665.539-0.095825 Imcarl CAEP14.4990 66995 30662.5 0.095825 3实例研究 14.70820.79671 30655.3 0.089157 CAA 15.0-0.525589支-50665.539 095825 CAA综合了混沌搜索优化和文化算法的优势。为了验证 VOISL CAEP-12.00000.51762 30636.2 0.095825 算法的有效性,本文从文献[12]中选取了五个约束优化问题 14.61540.79119 30645.9 0.029144 如下所示: 表1表明,本文所采用的混沌文化算法(CAA)相比其他 min1(X)=5∑x-5∑x2 两种算法更具优势。在解决ff和,CAA相对其他两种算 法,不仅最优解更精确,而且具有更强的稳定性。在求解效率 :g1=2x1+2x2+x10+x11-10≤0 + 上,本文采用的混沌文化算法和文献12」提出的文化算法要 10≤0 比KM算法效率高。在2500次迭代中,KM算法需要对适应 g4=-8x1+x1n≤0 g5=-8x2+x1≤0 值函数进行约14000次计算,而文算法只需计算50000 4)次左 g7=-2t4-x5+x0≤0 第五个问题为来自于文献l12」的弹簧质量的最小化模 88=-2x6-xy+x1≤0 g9=-2xy-xy+x2≤0 型。该模型求解当弹簧的变形量、剪应力和颤动频率为最小值 0≤x:≤l(i=1.…,9) 时,弹簧质量的最小值。模型决策变量为弹簧簧丝直径d、弹 0≤x:≤100(1=10,11,12) 簧外径D和弹簧圈数N。 Arora和 Belegundu曾用各自的 0≤x1≤1 (x1)-211 最优化数值方法进行过求解,但 arora的方法违反了约束条件 X) g1, Belegundu的方法求解精度不高。 Coello也曾采用过文化算 L.:1=0.75-1x;≤0 (15)法进行求解21。现将本文提出的混沌文化算法用丁该模型的 求解,并将结果与上述的三种方法进行比较(表2)。 7.5n≤0 表2弹簧质量最小化问题的比较结果 sin(2Tx sin(2T , 最优值 变量 min fa(X CAA Arora[17 Belegundu i& x1(d) 0.051753 0.050000 0.053396 0.050000 L.:1=x1-2+1≤0 (16) 0.358249 0.3173950.3991800.315900 x1+(x,-4)2≤0 l1.201371 14.031795 9.185400 14.250000 0≤x1≤10,0≤x2≤ 0.000000 0.000014 minf3(x)=5.3578547r3+0.836891x15+37.2093239x1-40792.141 0.000020 0.000075 0.000018 0.003782 g1=85.334407+0.0056858x2x5+0.00202x1xA-0.0020533 82=-85.334107-0.0056858x2X5-0.0006262x1x4-0.002003x3yx5≤0 4.056105 3.938302 -0.726665 0.755070-0.698283-0.756067 g3=80.51249+0.0071317x25+0.00299551x2+0.0021813x-110≤ 17) X51249-(1.0m7131/r25-0.(995x12-008ix3+90≤0 0.01266700.01272100.01273030.0128334 g5=9.300961+0.0047026x3s+0.00125471x3+0.0019085x3x4-25≤0 S5=-9.300961-0.0047025xx5-0.0012547x123-0.0019095xyx4+20≤0 结果表明,混沌文化算法比其他方法能找到更好的解且满 8x1≤102,33≤x2≤45,27≤x;≤45(=3,4,5) 足所有约束条件。采用本文算法求解弹簧质量最小化问题时, 第5期 黄鶴,等:一种求解约束优化问题的混沌文化算法 1647 10次运行的平均值为0.0127766,标准差为0.0001830,最差7] CHUNG C. Know ledge-hased approaches to self-adaptation in 结果为0.0132789,表明了混沌文化算法在实际的工程应用 cultural algorithmE[D]. Detroit: Wayne State University, 1997. 中不仅具有较高的精度,而且具有良好的稳定性。 [8 JIN Xi-dong, REYNOLDS R G. Using knowledge-based evolutionary computation to solve nonlinear constraint optimization problems: a cul 4结束语 tural algorithm approach[ C]//Pmc of Congress on Evolutionary Com putation. Washington nC: IEE.. Service Center, 1999: 1672-1678 混沌文化算法结合了混沌搜索优化的遍历性和文化算法91李冰,慰孙,混沌优化方法及其应月[刀.控制理论与应月 的知识引导作用,既增强了算法全局搜索能力,避免出现过早 1997,14(4):613-615 收敛,同时又减少了盲目搜索的次数,提高了算法的搜索效率[101场迫雄,李刚,程耿东,非线性函数的混沌优化方法比较研究 和精度,増强了算法的通用性。算法利用地形知识处理约朿, [冂].计算力学学报,2004,21(3):257-262 标准知识引导混沌搜索,形势知识引导混沌扰动,:者交进[11 CHUNG C J, REYNOLDS R G.CAEP: an evolution- based tool for 行,有效处理了问题约束条件,提高了算法的整体性能。 real-valued function optim ization using cultural algorithms J. Jour 参考文献: nal on Artificial Intelligence Tools, 1998. 7(3): 239-292 [1 REYNOLDS R G. An introduction to cultural algorithms [C//Proc of 1 12 COELLO C A, BECERRA R I. Efficient evolutionary optimization the 3rd Annual Conference on Evolutionary Programming. Singapore through the use of a cultural algorithm[ J]. Engineering Optimiza World Scientific Puhlis hing, 1994: 131-139 tion,2004,36(2):219-236 2] COELLO C A, BECERRA R I Evolutionary mutilobjeetive optimiza 13] SALEEM S M. Know ledge-based solution to dy namic optimization tion using a cultural algorithm[ C] //Proc of IEEE Sw arm Intelligence problems using cultural algorithms[ D]. Detroit: Wayne State Universi Symposium. Indianapolis: IEEE Service Center, 2003: 6-13 ty,2001 3] REYNOLDS R G, SALEEM S Cultural algorithms in dynamic envi- [14] 7.HU Shi-nin, RFYNOIDS R G. Fuzzy cultural algorithms with evolu mnments[ C]//Proc of Congress on Evolutionary Computation.San ionary program ming[ C]//Proc of the 7th International E volution ary Diego:[s.n.J,2000:1513-1520 Program ming vIl. 1998: 209-218 [4] Y\ Xiaa-hui, YUAN Yan-bin. Application of cultural algorithm to 15] ZHU Shi-nin Fuzzy cultural algorithms with evolutionary programming generation scheduling of hydrothermal systems[ J]. Energy Conver- for real-valued function optimization[ D]. Detroit, Michigan: Wayne sion and management, 2006. 47(15-16): 2192-2201 Stale Universily, 1998 [5] REYNOLDS R G, ZHU Shi-nin Knowledge-based function optimiza- [16 SLA WOMIR K, MICHALEWICZ Z. Evolutionary algorithms, hULu- tion lsing fu y eu tural algorithms with evolutionary programming morphous mappings, and constrained parameter optimization J I [J. IEEE Trans on Systems, Man, and Cybernetics, Part B Evolutionary Computation, 1999, 7(1): 19-44 Cybernetics,2001,31(1):1-1 [6 CHUNG C J, REYNOLDS R G. A testbed for solving optimization 117 ARORA J S. Introduction to optimum design M. No problems using cultural algorithus[ C]//Prve of the 4th Annual Cull MeGraw-Hill, 989 ference on Evolutionary Programming C ambridge, Massachusetts: MIT 18] BELEGUNDU A D. A study of m athematical programming methods for Press,1996:225-236 structural optimization D]. lowa: University of lowa, 1982 上接第1642页) [13]李晓磊,路飞,田囯会,等,组合优化问题的人工鱼群算法应用 15 NIU Ben, ZHU Yun-long, HE Xiao-xian. Multi-population cooperative J」.山东大学学报:工学版,2004,34(5):64-67 particle swarm optimization[ C]//Proe of the 8th European Confe- [14] KENNEDY J, EBERHART R C Particle swarm optimization [C]// rence on Advances in Artificaial Life. 2005:874-883 Proc of ieee intern ational Conference on Neural Networks. Perth [6 NIU Ben, ZHU Yun-long, HE Xiao-xian. Construction of fuzzy model IEEE Service Center, 1995:1942-1948 for dynamic systems using multi-population cooperative particle swarm [15] MO Yuan-bin, LIU He-tong, WANG Qin. Conjugate direction particle optimizer[ C]//Proc of the 2 nd International Conference on Fuzzy swarm optimization solving systems of nonlinear equations[ J]. Com Systems and Knowledge Discovery. 2005: 987-1000 puters and Mathematics with Applications. 2009. 57(11-12) [7]李爱国.多粒子群协同优化算法[J].复旦大学学报:自然科学版, 1877-1882. 2004,43(5):923-925 「16刁东宁,赵英凯.带双重变异算子的自适应粒子群倪化算法「J I MENG Hong yun, ZHANG Xiao-hua, LIU San-yang. A co-evolutionary 计算机工程与设计,2009,30(5):11861188 particle swarm optimization- based method for multiobjective optimiza-[17]高丽丽,刘弘,李同喜.基于文化粒子群算法的约束优化问题求解 tion[ C]//Proc of the 18th Australian Joint Conference on Artificial [J].计算机工程,2008,34(5):179181 Intelligence. 2005: 349-359 [18]甘敏,彰探。一种新的自造应惩罚函教算決求解约柬优化问题 [9]李菲菲,姚坤,刘希玉。一种多徽粒群协同进化算法[J].计算机工 [冂].信息与控制,2009,38(1):25-28 程与应用,2007,43(22):44-46 19 ADJIMAN C S, DALL WIG S FLOUDAS C A, et al. A global optimiza [10]张创业,莫愿斌.基协司进化思想的人工鱼和粒了群混合优化 tion method, alpha BB, for general twice differentiable constrained 算法「J.广西民族大学学报;自然科学版,2009,15(1):74-77 NLPs-llJI. Theoretical Advance, 1998, 22(9): 1137-1158 l]」王凌,刘波,微粒頵优化与调度算沄[M」.北京:清华大学出版社,[20」贺益君,陈德钊.连续约朿蚁群优化算法的枃建及其在丁烯烷化 2008:85-87 过程中的应用[J」.化工学报,2005,56(9):1708-1713 12]李晓磊,邵之汇,钱积新.一神基动物自治体的寻优模式:鱼群21]黄渰燕,顾幸生,刘漫开,求解约炱优化问题的文化算法研究 算法[J].系统工程理论与实践,2002,22(11):32-38 [J].自动化学报,2007,33(10):1115-1120