A Linear Evolutionary Algorithm for Solving Constrained Optimization Problems
TANG Ke-Zong1,3, YANG Jing-Yu1, GAO Shang2,3, LI Wei1
1.School of Computer Science and Technology, Nanjing University of Science and Technology, Nanjing 210094 2.School of Computer Science and Engineering, Jiangsu University of Science and Technology, Zhenjiang 212003 3.Key Laboratory of CAD＆CG,Zhejiang University,Hangzhou 310027
Abstract：A linear evolutionary algorithm for solving constrained optimization problems (LEACOP) based on real-coded method is proposed, and its complexity and convergence are also analyzed. One of the main advantages of the proposed algorithm is that the search space of constrained dominance problems with high dimensions is compressed into two dimensions. A linear fitness function based on mathematic analysis is deduced in two dimension space to fast evaluate fitness value of each individual in population. A crossover operator based on density function and a new mutation operator are developed to extend the search space and extract better solution. In addition, an average linkage based on hierarchical clustering method is introduced into the LEACOP to maintain the number of individuals on Pareto set. A few benchmark multi-objective optimization problem which is divided into three groups is introduced to test this algorithm. The numerical experiments show that proposed algorithm is feasible and effective, and it provides good performance in terms of uniformity and diversity of solutions.
[1] Beyer H G, Schwefel H P, Wegener I. How to Analyse Evolutionary Algorithms. Theoretical Computer Science, 2002, 287(1): 101-130 [2] Xie Bin. Web Mining Based on Chaotic Social Evolutionary Programming Algorithm. Journal of Systems Engineering and Electronics, 2008, 19(6): 1271-1276 [3] Deb K. Multi-Objective Genetic Algorithms:Problem Difficulties and Construction of Test Problem. Evolutionary Computation, 1999, 7(3): 205-230 [4] Cui Xunxue, Lin Chuang, Fang Tingjian. A Review of the Research on Multi-Objective Evolutionary Algorithms. Pattern Recognition and Artificial Intelligence, 2003, 16(3): 306-313 (in Chinese) (崔逊学,林 闯,方廷健.多目标进化算法的研究与进展.模式识别与人工智能, 2003, 16(3): 306-313) [5] Beyer Hg, Deb K. On Self-Adaptive Features in Real-Parameter Evolutionary Algorithms. IEEE Trans on Evolutionary Computation, 2001, 5(3): 250-270 [6] Zitzler E, Deb K, Thiele L. Comparison of Multi-Objective Evolutionary Algorithm: Empirical Results. Evolutionary Computation, 2000, 8(2): 173-195 [7] Zou Xiufen, Liu Minzhong, Wu Zhijian, et al. A Robust Evolutionary Algorithm for Constrained Multi-Objective Optimization Problems. Journal of Computer Research and Development, 2004, 41(6): 986-990 (in Chinese) (邹秀芬,刘敏忠,吴志健,等.解约束多目标优化问题的一种鲁棒的进化算法.计算机研究与发展, 2004, 41(6): 986-990) [8] Abido M A. A Niched Pareto Genetic Algorithm for Multiobjective Environmental/Economic Dispatch. Electrical Power & Energy Systems, 2003, 25(2): 97-105 [9] Jiao Licheng, Liu Jing, Zhong Weicai. Coherent Evolution Computing and Multi-Agent System. Beijing, China: Science Press, 2006: 5-51 (in Chinese) (焦李成,刘 静,钟伟才.协同进化计算与多智能体系统.北京:科学出版社, 2006: 5-51) [10] Ombach J. Stability of Evolutionary Algorithms. Journal of Mathematical Analysis and Applications, 2008, 342(1): 326-333 [11] Zhou Yuren, He Jun. Convergence Analysis of a Self-Adaptive Multi-Objective Evolutionary Algorithm Based on Grids. Information Processing Letters, 2007, 104(4): 117-122 [12] Eberbach E. Toward a Theory of Evolutionary Computation. Biosystems, 2005, 82(1): 1-19 [13] Hanne T. On the Convergence of Multiobjective Evolutionary Algorithms. European Journal of Operational Research, 1999, 117(3): 553-564 [14] Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. Chichester, UK: John Wiley & Sons, 2001 [15] Runarsson T, Yao Xin. Stochastic Ranking for Constrained Evolutionary Optimization. IEEE Trans on Evolutionary Computation, 2000, 4(3): 284-294 [16] Deb K, Agrawal S, Pratap A, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197 [17] Kelner V, Capitanescu F, Léonardand O, et al. A Hybrid Optimization Technique Coupling an Evolutionary and a Local Search Algorithm. Journal of Computational and Applied Mathematics, 2008, 215(2): 448-456 [18] Madavan N L. Multiobjective Optimization Using a Pareto Differential Evolution Approach // Proc of the World Congress on Computational Intelligence. Piscataway, USA, 2002: 1145-1150 [19] Zhou Yuren, Lin Yuanxiang, Wang Yong, et al. A Pareto Strength Evolutionary Algorithm for Constrained Optimization. Journal of Software, 2003, 14(7): 1243-1249 (in Chinese) (周育人,李元香,王 勇,等.Pareto强度值演化算法求解约束优化问题.软件学报, 2003, 14(7): 1243-1249)
2009, Vol. 22 
