PDF《约束优化进化算法》

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.

ac.cn Journal of Software, Vol.20, No.1, January 2009, pp.11?29 http://www.jos.org.cn doi: 10.3724/SP.J.1001.2009.03363 Tel/Fax: +86-10-62562563 ? by Institute of Software, the Chinese Academy of Sciences. All rights reserved. 约束优化进化算法 ? 王勇1+ , 蔡自兴

1 , 周育人

2 , 肖赤心 1,3

1 (中南大学 信息科学与工程学院,湖南 长沙 410083)

2 (华南理工大学 计算机科学与工程学院,广东 广州 516040)

3 (湘潭大学 信息工程学院,湖南 湘潭 411105) Constrained Optimization Evolutionary Algorithms WANG Yong1+ , CAI Zi-Xing1 , ZHOU Yu-Ren2 , XIAO Chi-Xin1,3

1 (School of Information Science and Engineering, Central South University, Changsha 410083, China)

2 (School of Computer Science and Engineering, South China University of Technology, Guangzhou 516040, China)

3 (School of Information Engineering, Xiangtan University, Xiangtan 411105, China) + Corresponding author: E-mail: [email protected] Wang Y, Cai ZX, Zhou YR, Xiao CX. Constrained optimization evolutionary algorithms. Journal of Software, 2009,20(1):11?29. http://www.jos.org.cn/1000-9825/3363.htm Abstract: Constrained optimization problems (COPs) are mathematical programming problems frequently encountered in the disciplines of science and engineering application. Solving COPs has become an important research area of evolutionary computation in recent years. In this paper, the state-of-the-art of constrained optimization evolutionary algorithms (COEAs) is surveyed from two basic aspects of COEAs (i.e., constraint-handling techniques and evolutionary algorithms). In addition, this paper discusses some important issues of COEAs. More specifically, several typical algorithms are analyzed in detail. Based on the analyses, it concluded that to obtain competitive results, a proper constraint-handling technique needs to be considered in conjunction with an appropriate search algorithm. Finally, the open research issues in this field are also pointed out. Key words: evolutionary algorithm;

constraint-handling technique;

constrained optimization;

multi-objective optimization;

constrained optimization evolutionary algorithms 摘要: 约束优化问题是科学和工程应用领域经常会遇到的一类数学规划问题.近年来,约束优化问题求解已成 为进化计算研究的一个重要方向.从约束优化进化算法=约束处理技术+进化算法的研究框架出发,从约束处理技术 和进化算法两个基本方面对约束优化进化算法的研究及进展进行了综述.此外,对约束优化进化算法中的一些重要 问题进行了探讨.最后进行了各种算法的比较性总结,深入分析了目前约束优化进化算法中亟待解决的问题,并指出 了值得进一步研究的方向. 关键词: 进化算法;

约束处理技术;

约束优化;

多目标优化;

约束优化进化算法 ? Supported by the National Natural Science Foundation of China under Grant Nos.60805027, 60234030, 60673062,

90820302 (国家 自然科学基金);

the Academician Foundation Project of Hu'

nan Province of China under Grant No.06IJY3035 (湖南省院士基金);

the Graduate Degree Thesis Innovation Foundation of Central South University of China under Grant No.1373-74334000016 (中南大学研究 生学位论文创新基金) Received 2007-12-02;

Accepted 2008-04-15

12 Journal of Software 软件学报 Vol.20, No.1, January

2009 中图法分类号: TP18 文献标识码: A 约束优化问题(constrained optimization problems,简称 COPs)是一类广泛存在于实际工程中但又较难求解 的问题,因而对其研究具有十分重要的理论和实际意义.目前,求解约束优化问题的算法有很多,按照性质大体 可分为两类:确定性的算法和随机性的算法.确定性的算法通常是基于梯度的搜索方法,如投影梯度法、简约梯 度法、各类外点及内点惩罚函数法、Lagrangian 法和序列二次规划法等.这些方法存在的主要问题是,求解需要 设置很好的初值点并需要函数的梯度信息,它们对于不可导、可行域不连通、甚至根本没有显式数学表达式等 问题无能为力,而且求得的多为局部最优解.随机性的算法主要包括进化算法(evolutionary algorithms,简称 EAs)、模拟退火(simulated annealing,简称 SA)算法、禁忌搜索(tabu search,简称 TS)等.进化算法是一种模拟自 然进化过程的全局优化方法,它借用了达尔文 物竞天择、适者生存 的生物进化观点,通过选择、交叉、变异等 机制来提高个体的适应性.模拟退火算法利用统计力学中物质退火过程与优化问题求解的相似性,采用 Metropolis 接受准则并适当控制温度的下降过程实现模拟退火,从而达到求解全局优化问题的目的.禁忌搜索 是对局部邻域搜索的一种扩展,是一种全局逐步寻优的启发式搜索方法.它通过设置禁忌表和禁忌对象来避免 迂回搜索,并采用藐视准则来放松禁忌策略.与确定性的优化方法相比,进化算法是一种具有有向随机性的智能 优化方法,更适合于求解约束优化问题.此外,与随机性的优化方法(如模拟退火算法、禁忌搜索等)相比,进化算 法是一种基于群体的搜索技术,具有鲁棒性强、搜索效率高、不易陷入局部最优等特点. 近10 年来,利用进化算法求解约束优化问题已有许多学者进行了广泛的研究,并且提出了大量的约束优化 进化算法(constrained optimization evolutionary algorithms,简称 COEAs)[1,2] .特别值得一提的是,2006 年~2008 年, 进化计算国际大会(IEEE Congress on Evolutionary Computation)每年均为约束优化举办了 Special Session. 进化算法在约束优化问题中的成功应用取决于以下几个主要因素: (1) 进化算法从一个群体即多个点而不是一个点开始搜索,这使得它能够以较大概率找到全局最优解;