摘要
在自然学科和社会学科领域中存在很多多目标优化问题,传统的多目标优化方法对复杂优化问题难以有效求解。基于Pareto概念的多目标进化算法由于具有高效的搜索能力,己成为当今研究热点。差分进化算法作为一种新兴的进化计算技术,具有全局搜索能力强、收敛速度快、简单易行等优点,已在优化领域得到了广泛的关注。
本文对差分进化算法进行深入探索和研究,并与局部搜索算法进行有机融合,旨在针对多目标优化问题设计高效的差分进化混合算法,并应用求解磨矿分级过程多目标优化问题。
论文通过对多目标优化方法和差分进化算法进行分析研究,针对目前一般多目标差分进化算法中存在的退化现象和“早熟”问题,提出一种多目标差分进化混合算法。通过改进的选择操作合并父代和子代所有个体,进行Pareto非劣排序,加强各个体间的信息交流和充分比较,防止退化;并对个体的排序指标进行改进以克服搜索不均匀的问题;同时融入了单纯形局部搜索,以期能够丰富优化过程的搜索行为,达到脱离局部最优、提高搜索效率的目的。
进一步对约束多目标优化问题的约束处理机制进行研究,提出了基于多种群差分进化的约束多目标混合优化算法,对某些具有优良特性的不可行解采取保留和随机优化策略,避免了惩罚函数的构造,同时避免了一些有意义的不可行解被删除或忽略。通过测试函数仿真表明,提出的算法能够快速有效地收敛于真实Pareto前沿,获得高质量的解集,具有较好的分布性。
最后,将基于多种群差分进化的约束多目标混合优化算法用于求解磨矿分级过程产品产量和质量的多目标优化问题,采用TOPSIS决策获得优化磨矿分级过程的最优方案,达到提高生产效率的目的,获得最大经济效益。
Multi-objective optimization problems exist widely in natural and social sciences. The traditional optimization methods can not solve the complex problems effectively. Multi-objective evolutionary algorithms based on Pareto theory have become a hot issue for its highly efficient searching capability. Differential evolution algorithm is a newly arisen evolutionary computation technique. Due to its feasible and simple structure, strong global search ability and fast convergence speed, DE has attracted wide attention in the optimum area.
Based on the intensive research of DE algtorithm and hybrid strategy with local search algorithm, the objective of this paper is to design a fast and efficient hybrid DE algorithm for solving multi-objective optimization problems, which is then applied to solve the MOPs in the grinding and classification process.
In order to overcome the problems such as degradation and local optimum exist in common multi-objective DE algorithms, a novel hybrid DE algorithm for MOPs is proposed. It strengthens the exchanges of information among individuals and prevents degradation using a modified selecting method, which sorts all individuals including the parents and offspring based on the Pareto non-dominated theory. Meanwhile, the ranking index of individuals is improved to overcome the problem of uneven search. In addition, the simplex local search method is mixed in the evolution algorithm to enrich the searching behavior in the optimization process, get out from the local optimum and improve searching efficiency.
Moreover, based on further research on the constraints processing mechanism of constrained multi-objective optimization problems, a hybrid DE algorithm with multi-population is designed for CMOPs. Some infeasible solutions with better performance are allowed to save and participate optimization randomly in the evolution. The advantage of the proposed algorithm is the avoidance of difficulties such as constructing penalty function and deleting meaningful infeasible solutions directly. Simulation results on benchmarks indicate that the proposed algorithm can converge quickly and effectively to the true Pareto front with better distribution.
Finally, the proposed algorithm is applied to solve multi-objective optimization model of product output and quality in grinding and classification process. Based on TOPSIS, the satisfactory solution is obtained by using decision-making method on multiple attribute, achieving the goals of improving the production efficiency and maximum economic benefits.
引文
[1]安伟刚.多目标优化方法研究及其工程应用[D].西安:西北工业大学,2005.
[2]Coello C. Evolutionary multi-objective optimization:A historical view of the field[J]. IEEE Computational Intelligence Magazine,2006,1(1):28-36.
[3]Storn R, Price K. Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997,11(4):341-359.
[4]牛大鹏,王福利,何大阔.多目标混沌差分进化算法[J].控制与决策,2009,24(3):361-370.
[5]Carlos A.an updated survey of GA-based multi-objective optimization techniques [J]. ACM Computing Surveys 2000,32(2):109-143.
[6]祁荣宾,钱锋,杜文莉,等.基于精英选择和个体迁移的多目标遗传算法[J].控制与决策,2007,22(2):164-168.
[7]赖红松,董品杰,祝国瑞.求解多目标规划问题的Pareto多目标遗传算法[J].系统工程,2003,21(15):24-28.
[8]徐玖平,李平.多目标决策的理论与方法[M].北京:清华大学出版社,2005.
[9]温丽敏.氧化铝生料浆调配过程的智能满意优化方法及应用[D].长沙:中南大学,2008.
[10]Schaffer J D. Multiple objective optimization with vector evaluated genetic algorithms [C]. Proceedings of the 1st International Conference on Genetic Algorithms, Lawrence Erlbsum,1985,93-100.
[11]吴亮红.差分进化算法及应用研究[D].长沙:湖南大学,2007.
[12]谢涛.多目标优化与决策问题的演化算法[J].中国工程科学,2002,4(2):59-68.
[13]Jaszkiewicz A. Genetic Local Search for Multiple Objective Combinatorial Optimization[J]. European Journal of Operational Research,2002, vol.137: 50-71.
[14]Fonseca C M, Fleming P J. Genetic algorithms for multi-objective optimization: formulation, discussion and generalization. In:Proc of the Fifth Int Conf on Genetic Algorithms. SanMateo:Morgan Kauffman Publishers,1993:416-423.
[15]Srinivas N, Deb K. Multi-objective Optimization Using Non-dominated Sorting in Genetic Algorithms. Evolutionary Computation,1994,2(3):221-248.
[16]Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multi-objective genetic algorithm:NSGA-Ⅱ[J]. IEEE Trans.On Evolutionary Computation,2002, 6(2):182-197.
[17]Horn J, Nafpliotis N, Goldberg D E.A niched pareto genetic algorithms for multi-objective optimization[C].Proc.of the 1st IEEE Congress on Evolutionary Computation, Piscataway,1994,82-87.
[18]郑金华.多目标进化算法及其应用[M].科学出版社,2007.
[19]Zitzler E, Thiele L. Multi-objective evolutionary algorithms:A comparative case study and the strength pareto approach[J]. IEEE Trans.on Evolutionary Computation,1999,3(4):257-271.
[20]Knowles J D, Corne D W. Approximating the non-dominated front using the pareto archived evolution strategy[J]. Evolutionary Computation,2000,8(2): 149-172.
[21]Zitzler E, Laumanns M, Thiele L. SPEA2:Improving the strength pareto evolutionary algorithm[C]. In Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, Athens, Greece,2002, 95-100.
[22]Corne D W, Knowles J D, Oates M J. The pareto-envelope based selection algorithm for multi-objective optimization[C]. Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, Berlin,2000, 839-848.
[23]Corne D W, Jerram N R, Knowles J D, Oates M J. PESA-Ⅱ:Region-based selection in evolutionary multi-objective optimization[C]. Proc.of the Genetic and Evolutionary Computation Conf., San Francisco,2001,283-290.
[24]LI Xiaodong. A Real-Coded Predator-Prey Genetic Algorithm for Multiobjective Optimization[A]. EMO 2003[C]:207-221.
[25]Parsopoulos K E, Vrahatis M N.Particle swarm optimization method in multiobjective problems[C]. In:Proc of the ACM Symposium on Applied Computing. Madrid,2002:603-607.
[26]Mariano C E, Morales E.MOAQ an Ant-Q Algorithm for Multiple Objective Optimization Problems[C]. In:Proc of the 1999 Genetic and Evolutionary Computing Conf. San Francisco,1999:894-901.
[27]Abbass, H.A., Sarker, R., Newton, C. PDE:A pareto-frontier differential evolution approach for multi-objective optimization problems[J]. In: Proceedings of the Congress on Evolutionary Computation 2001 (CEC'2001). Volume 2, Piscataway, New Jersey, IEEE Service Center (2001) 971-978.
[28]Abbass, H.A. The self-adaptive pareto differential evolution algorithm[C]. In: Congress on Evolutionary Computation (CEC'2002). Volume 1, Piscataway, New Jersey, IEEE Service Center (2002) 831-836.
[29]B.V.Babu, M.Mathew, L.Jehan. Differential Evolution for multi-objective optimization [A]. IEEE Congress on Evolutionary Computation[C], Canberra, 2003:2696-2703
[30]Madavan, N.K. Multiobjective optimization using a pareto differential evolution approach[C]. In:Congress on Evolutionary Computation (CEC'2002). Volume 2, Piscataway, New Jersey, IEEE Service Center (2002) 1145-1150.
[31]Robic T, Filipic B. DEMO:Differential evolution for multi objective optimization [C]. Lecture Notes in Computer Science. Berlin:Springer,2005: 520-533.
[32]Kukkonen S, Lampinen J. GDE3:The third evolution step of generalized differential evolution [C]. Proc of CEC 05.Piscataway, NJ:IEEE,2005: 443-450.
[33]Kukkonen S, Lampinen J. An extension of generalized differential evolution for multi-objective optimization with constraints [G]. LNCS3242:Proc of Parallel Problem Solving from Nature. Berlin:Springer,2004:752-761.
[34]Iorio A, Li X. Solving rotated multi-objective optimization problems using differential evolution [G]. LNAI 3339:Proc of Advances in Artificial Intelligence. Berlin:Springer,2004:861-872.
[35]Zitzler E, Deb K, Thiele L. Comparison of multi-objective evolutionary algorithms:Empirical results[J]. Evolutionary Computation,2000,8(2):173-195.
[36]Deb K, Thiele L, Laumanns M, Zitzler E. Scalable multi-objective optimization test problems[C]. Proc.of the IEEE Congress on Evolutionary Computation, Piscataway,2002,825-830.
[37]K Price. Differential evolution vs.the functions of the 2nd ICEO[C]. IEEE International Conference on Evolutionary Computation. Indianapolis,1997. 153-157.
[38]K Price. Differential evolution a fast and simple numerical optimizer[C].1996 Biennial Conference of the North American Fuzzy Information Processing Society. New York,1996.524-527.
[39]Junhong Liu, Jouni Lampinen. A fuzzy adaptive differential evolution algorithm [C]. Proc.IEEE Conf on Computers, Communications, Control and Power Engineering,2002,606-611.
[40]谢晓峰,张文俊,张国瑞,等.差异演化的实验研究[J].控制与决策,2004,19(1):49-52.
[41]Fan H Y, Lampinen J. A trigonometric mutationoperation to differential evolution [J]. J of Global Optimization,2003,27 (1):105-129.
[42]Kaelo P, Ali M M. A numerical study of some modified differential evolution algorithms[J]. European J of Operational Research,2006,1,69(3):1176-1184.
[43]Lin Y C, Wang Fengsheng, HwangK S. A Hybrid Method of Evolutionary Algorithms for Mixed-Integer Nonlinear optimization Problems[C]. Proc of Congresson Evolutionary Computation. Washington,USA,1999,111:2159-2166.
[44]Zaharie D. A multi-population differential evolution algorithm for multi-modal optimization[C]. The 10th Int Conf on Soft Computing. Mendel,2004:16-18.
[45]Tasgeriren M F, Suganthan P N. A Multi-Populated Differential Evolution Algorithm for Solving Constrained optimization problem [C]. Proc Of the IEEE Congress on Evolutionary Computation.Vancouver, USA,2006:33-40.
[46]Parsopoulos K E, Tasoulis D K, Pavlidis N G, et al.Vector Evaluated Differential Evolution for Multi-objective optimization[C]. Proc of the IEEE Congress on Evolutionar Computation.Portland, USA,2004,1:204-211.
[47]Chiou J P, Chang C F, Su C T. Ant direction hybrid differential evolution for solving large capacitor placement problems [J]. IEEE Trans on Power Systems, 2004,19(4):1794-1800.
[48]奕丽君,谭立静,牛奔.一种基于粒子群优化算法和差分进化算法的新型混合全局优化算法[J].信息与控制,2007,36(6):708-714.
[49]方强,陈德钊,俞欢军,等.基于优进策略的差分进化算法及其化工应用[J].化工学报,2004,55(4):598-602.
[50]范瑜,金荣洪,耿军平,等.基于差分进化算法和遗传算法的混合优化算法及其在阵列天线方向图综合中的应用[J].电子学报,2004,32(12):1997-2000.
[51]Luis V. Santana-Quintero, Alfredo G. Hernandez-Diaz.etc. DEMORS:A hybrid multi-objective optimization algorithm using differential evolution and rough set theory for constrained problems[J]. Computers & Operations Research 2010(37): 470-480.
[52]张利彪,周春光,马铭,等.基于极大极小距离密度的多目标微分进化算法[J].计算机研究与发展,2007,44(1):177-184.
[53]龚文引,蔡之华.基于ε占优的正交多目标差分演化算法研究[J].计算机研究与发展,2009,46(4):655-666.
[54]余建军,孙树栋,王军强.单纯形免疫算法及其在高维非凸函数优化中的应用[J].机械科学与技术,2007,26(3):296-303.
[55]王芳,邱玉辉.一种引入单纯形法算子的新颖粒子群算法[J].信息与控制.2005,34(5):517-522.
[56]张志新,张明廉.基于并行混沌和单纯形法的混合全局优化算法[J].系统仿真学报.2004.16(1):35-37.
[57]SRINIVAS N, DEB K. Multi-objective function optimization using non--dominated sorting genetic algorithms [J]. Evolutionary Computation,1995,2(3): 221-248.
[58]Z. Michalewicz and M. Schoenauer. Evolutionary algorithm for constrained parameter optimization problems [J]. Ev01. Comput., v01.4, no.1, PP,1-32,1996.
[59]C.A.C.Coello. Theoretical and numerical constaint-handling techniques used with evolutionary algorithms:a survey ofthe state ofthe art[J]. Comput. Methods Appl. Mech. Eng., V01. 191. No.11-12, PP.1245-1287, January 2002.
[60]Homaifar A, Charlene X Q, Steven H L. Constrained optimization via genetic algorithms[J]. Simulation,1994,62(4):242-254.
[61]Michalewicz Z, Attia N F. Evolutionary optimization of constrained problems [C]. Proc. of CEP,1994,98-108.
[62]Hadj-Alouane A B, Bean J C. A genetic algorithm for the multiple-choice interger program[J]. Operations Research,1997,45:92-101.
[63]S.B. Hamida and M. Schoenauer. ASCHEA. New resulm using adaptive segregational constraint handling[C]. Proc. Congr. Evolutionary Computation, v01.1, May 2002, PP.884-889.
[64]Carlos A. Coello Coello. Use of a Self-Adaptive Penalty Approach for Engineering Optimization Problems[J]. Computers in Industry,41(2):113-127, January 2000.
[65]Fernando Jimenez and Jose L. Verdegay. Evolutionary techniques for constrained optimization problems[G]. In Hans-Jirgen Zimmermann, editor,7th European Congress on Intelligent Techniques and Soft Computing (ELJFIT'99), Aachen, Germany,1999.
[66]Cai Z X, Wang Y. A Multiobjective Optimization based on evolutionary algorithm for constrained optimization[J]. IEEE Trans on Evolutionary Computation(S1089-778X),2006,10(3):658-575.
[67]Patrick D. Surry and Nicholas J. Radcliffe. The COMOGA Method: Optimisation by Multiobjective Genetic Algorithms[J]. Control and Constrained Cybernetics,26(3):391-412,1997.
[68]Z. Michalewicz and D.B. Fogel. How to solve it:modem heuristics[C]. Berlin, Germany:Springer-Verlag,2000.
[69]T. Ray, and K.M. Liew. Society and civilization:An optimization algorithm based on the simulation of social behavior[J]. IEEE Trans. Evol. Comput., vol.7, no.4, PP.386-396, Aug,2003.
[70]Montes E M, Coello C A C. A simple multi-membered evolution strategy to solve constrained optimization problems[J]. IEEE Trans. On Evolutionary Computation,2005,9:1-17.
[71]Farmani R, Wright JA. Self adaptive fitness formulation for constrained optimization[J]. IEEE Trans on Evolutionary Computation,2003,7(5):445-455.
[72]孟红云,张小华,刘三阳.用于约束多目标优化问题的双群体差分进化算法[J].计算机学报,2009,31(2):228-234.
[73]Deb K, Pratap A, Meyarivan T. Constrained test problems for multi-objective evolutionary optimization. Proceedings of the lst International Conference on Evolutionary Multi-Criterion Optimization[C]. Zurich, Switzerland,2001: 284-298.
[74]朱继平,桂卫华,阳春华.基于RBF神经网络的磨矿粒度预测模型[J].计算机测量与控制.2008.16(10):1421-1423.
[75]Heechan C, Austin L G. An equation for the breakage of particles under impact[J]. Powder Technology,2003,132(2):161-166.
[76]谢恒星,李松仁.分级效率计算方法的改进[J].有色金属(季刊),1990,1(42):39-45.
[77]中南大学信息科学与工程学院.铝土矿磨矿-分级数学模型开发结题报告(内部资料)[R].2010.3.
[78]刘军霞,阳春华,王雅琳.螺旋分级过程数学模型研究及应用[J].计算机工程与应用.2010,46(4):230-232.
[79]桂卫华,王雅琳,王晓丽,等.一种球磨机磨矿产品的粒度分布预测方法[P].中国,201010191503.3,2010.
[80]高健.磨矿过程的稳态优化[D].沈阳:东北大学,2007.
[81]Kishalay Mitra, Ravi Gopinath. Multiobjective optimization of an industrial grinding operation using elitist nondominated sorting genetic algorithm[J]. Chemical Engineering Science 59 (2004) 385-396.