基于遗传算法的非线性规划问题求解
|
摘要
遗传算法是当前计算机科学的一个研究热点。遗传算法所具有的极度并行性、通用性和灵活性吸引着众多的学者对其进行研究。其中应用遗传算法解决非线性规划问题是遗传算法应用中的一个重要方向。
本文的主要内容是讨论遗传算法和将遗传算法应用于非线性规划问题时的算法设计，并对这类问题的求解提出了可靠、高效的算法。
首先我们介绍了非线性规划问题的特点，存在的领域，以及当前解决非线性规划问题的常用方法。还介绍了遗传算法解决非线性规划问题的成功实例。
在第二章中介绍了遗传算法的基本概念和基本理论以及用遗传算法解决非线性规划问题的常用策略。对遗传算法的各个组成部分，特别是对选择策略，杂交策略，变异策略作了详细的介绍。
在第三章中在我们提出了一种新的杂交算子：差分杂交算子，并对这个算子做了一系列的函数测试。我们还对混合遗传算法的一些参数进行了改进，并运用于遗传算法+单纯形算法的混合遗传算法中，证明这些改进较以前的方法在稳定性，收敛速度上都有提高。
在第四章中介绍了处理约束的四类方法：算子修正法，罚函数法，可行域搜索法，以及混合遗传算法，并对这些方法做了详细的分析，指出了他们优劣之处。在这里我们还提出了一种新的罚函数。将运用这种罚函数的遗传算法用于优化非线性约束函数，能够有效的提高解的质量。
在第五章中总结了我们利用遗传算法求解非线性规划问题的方法，指出我们提出的方法不足之处，并提出了改进的方案。
Genetic Algorithm is one of the current hot topics in the area of computer science. The massive parallelism, generality and flexibility it contains have attracted much attention from lots of experts in different fields. Solving nonlinear programming problem with genetic algorithm is the most important director of the application of genetic algorithm.
The main content of the thesis is discussing the genetic algorithm and designing genetic algorithms for solving nonlinear programming problems. In addition, we propose reliable, efficient algorithms for solving problems.
First, this thesis gives a brief introduction to the feature and application fields of the nonlinear programming and some methods often used to solve nonlinear programming problems. Several success solutions based on genetic algorithm will also introduced.
In the second chapter, the basic concepts and theory of genetic algorithms are introduced first and then the design of genetic algorithm has been discussed, some classical strategies used by genetic algorithm to solve nonlinear programming problems will be shown in this chapter as well.
In the third chapter, We also propose some methods to optimize the parameters of the hybrid genetic algorithm, when used these ways in hybrid genetic algorithm (GA+Simplex), the results we got are much better than before.
In the fourth chapter, several methods for handling constrains by genetic algorithms for nonlinear programming problems are introduced. These methods were grouped into four categories: methods based on preserving feasibility of solutions, methods based on penalty functions, methods which make a clear distinction between feasible and infeasible solutions and other hybrid methods. We analyze such methods in detail and designed a new penalty function, experiment result proved that the genetic algorithm used such penalty function can get better quality of the solution in solving nonlinear programming problems.
At the end of the chapter, the software complied based on the methods introduced in beyond chapters are introduced. Using this software, we can change the genetic operators as we want and add new operators are very convenience. Results compare this software and some commercial or noncommercial optimization software are listed in the end of the chapter.
本文的主要内容是讨论遗传算法和将遗传算法应用于非线性规划问题时的算法设计，并对这类问题的求解提出了可靠、高效的算法。
首先我们介绍了非线性规划问题的特点，存在的领域，以及当前解决非线性规划问题的常用方法。还介绍了遗传算法解决非线性规划问题的成功实例。
在第二章中介绍了遗传算法的基本概念和基本理论以及用遗传算法解决非线性规划问题的常用策略。对遗传算法的各个组成部分，特别是对选择策略，杂交策略，变异策略作了详细的介绍。
在第三章中在我们提出了一种新的杂交算子：差分杂交算子，并对这个算子做了一系列的函数测试。我们还对混合遗传算法的一些参数进行了改进，并运用于遗传算法+单纯形算法的混合遗传算法中，证明这些改进较以前的方法在稳定性，收敛速度上都有提高。
在第四章中介绍了处理约束的四类方法：算子修正法，罚函数法，可行域搜索法，以及混合遗传算法，并对这些方法做了详细的分析，指出了他们优劣之处。在这里我们还提出了一种新的罚函数。将运用这种罚函数的遗传算法用于优化非线性约束函数，能够有效的提高解的质量。
在第五章中总结了我们利用遗传算法求解非线性规划问题的方法，指出我们提出的方法不足之处，并提出了改进的方案。
Genetic Algorithm is one of the current hot topics in the area of computer science. The massive parallelism, generality and flexibility it contains have attracted much attention from lots of experts in different fields. Solving nonlinear programming problem with genetic algorithm is the most important director of the application of genetic algorithm.
The main content of the thesis is discussing the genetic algorithm and designing genetic algorithms for solving nonlinear programming problems. In addition, we propose reliable, efficient algorithms for solving problems.
First, this thesis gives a brief introduction to the feature and application fields of the nonlinear programming and some methods often used to solve nonlinear programming problems. Several success solutions based on genetic algorithm will also introduced.
In the second chapter, the basic concepts and theory of genetic algorithms are introduced first and then the design of genetic algorithm has been discussed, some classical strategies used by genetic algorithm to solve nonlinear programming problems will be shown in this chapter as well.
In the third chapter, We also propose some methods to optimize the parameters of the hybrid genetic algorithm, when used these ways in hybrid genetic algorithm (GA+Simplex), the results we got are much better than before.
In the fourth chapter, several methods for handling constrains by genetic algorithms for nonlinear programming problems are introduced. These methods were grouped into four categories: methods based on preserving feasibility of solutions, methods based on penalty functions, methods which make a clear distinction between feasible and infeasible solutions and other hybrid methods. We analyze such methods in detail and designed a new penalty function, experiment result proved that the genetic algorithm used such penalty function can get better quality of the solution in solving nonlinear programming problems.
At the end of the chapter, the software complied based on the methods introduced in beyond chapters are introduced. Using this software, we can change the genetic operators as we want and add new operators are very convenience. Results compare this software and some commercial or noncommercial optimization software are listed in the end of the chapter.
引文
1．潘正君 康立山．演化计算．清华大学出版社 1998．7
2．Z.Michalewicz.演化程序．科学出版社 2000．1
3．玄广男 程润伟．遗传算法与工程设计．科学出版社 2000．1
4．刘勇 康立山．非数值并行算法(第二册)：遗传算法．科学出版社 1996
5．邢文训 谢金星．现代优化计算方法．清华大学出版社 1999
6．黄豪 沈成武 雷建平．一种连续变量的遗传算法．武汉交通科技大学学报 No．2 vol．23 1999
7．樊会元 王尚锦 席光．遗传算法引入进化方向算子的一个改进及应用．西安交通大学学报 No．5 vol．23 1999
8．周济．机械设计优化方法及其应用 高等教育出版社 1989．
9．刘唯信 机械最优化设计 清华大学出版社 1993
10．郭涛 演化计算与优化 武汉大学博士学位论文 1999．3
11．希梅尔劳D．M 实用非线性规划 北京大学出版社 1981．2
12. J.E.Baker, Adaptive Selection Methods for Genetic Algorithms, in L.J.Eshelman, (Ed.), Proc. of the 6th Int'l. Conf. on Genetic Algorithms, Morgan Kaufmann, San Francisco, 110--111, 1985.
13. Xin Yao. Global Optimization by Landscape Approximation and Evolution Search. IWEC-2000
14. X. Yao Y. Liu and G. Lin. Evolutionary Programming made faster. IEEE Transaction on Evolutionary Computation 3(2) 82-102 July 1999
15. K. Liang X. Yao C. S. Newton. A Preliminary Study into Evolutionary Search of Approximated N-Dimensional Landscape. Proceedings of the third Australia-Japan Joint Workshop on Intelligent and Evolutionary System Canberra Australia 23-25 November 1999 pp201-208
16. S. Koziel Z. Michalewicz. Evolutionary Algorithms, Homomorphous
Mappings and Constrained Parameter Optimization. IWEC-2000
17． Kumar Chellapilla . Evolution Nonlinear Controllers for Backing up a Truck-and-Trailer using Evolutionary Programming. 1997
18． Storn, R. and Price, K., Differential Evolution-a Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces, Technical Report TR-95-012, ICSI, March 1995
19． Joines, J.and.C.Houck(1994) .On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with gas .In Z. Michalewicz, J. D. Schaffer, H.-P. Schwefel, Proceedings of the First IEEE International conference on Evolutionary Computation ,pp 579-584 IEEE Press
20． Eiben. A. E, R. Hinterding, and Z.Michealewicz, Parameter Control in Evolution Algorithms, IEEE Transactions on Evolution Computation 3 124-141,1999
21． Adam P.Gurson,Simplex Search Behavior in Nonlinear Optimization,A thesis submitted in partial fulfillment of the requirements for a Bachelor of science with Honors in Computer Science from the College of William&Mary in Virginia,2000
22． Grefenstette J J,Gopal R,Rosmaita B,et al.Genetic algorithm for TSP.In:Grefenstette J J,eds. Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Pittsburgh.Pittsburgh P A Carnegie-Mellon University, 1985． 160-168
23． Goldberg D E. Genetic algorithms in search,optimization and machine learning. MA:Addison Wesley Reading, 1989． 1-10
24． Cheng R W,Gen M.Crossover on intensive search and traveling salesman problem. In:Gen M eds. Proceedings of 16th International Conference on Computer & Industrial Enginerring. Japan:Nagoya Institute of Technology, 1994,7-9: 568-579
25． Holland J H. Adaptation in natural and artificial systems [M] . Ann
Arbor: University of Michigan Press, 1975．
26． Fogel L J, Owens A J, Walsh M J. Artificial intelligence through simulated evolution [M] . New York: John Wiley, 1966．
27． Schwefel H P. Numberical optimization of computer models [M] . Chichester: John Wiley, 1981．
28． Fogel D B. Evolutionary computation [M] .New York: IEEE Press, 1995．
29． Rudolph G. Convergence analysis of canonical genetic algorithm [ J ] . IEEE Transactions on Neural Networks, 1994,5(1) :96-101．
30． A.Homaifar, C.X.Qi, S.H.Lai, Constrained optimization via Genetic Algorithms, Simulation, 62(4) , 242-254,1994．
31． J.Joines and C.Houck, On the Use of Non-stationary Penalty Functions to Solve Nonlinear Constrained Optimization Problems with GAs, in ICEC94,579-584,1994．
32． Z.Michalewicz and N.Attia, Evolutionary Optimization of Constrained Problems, in EP94,98-108,1994．
33． J.C.Bean and A.B.Hadj-Alouane, A Dual Genetic Algorithm for Bounded Integer Programs, Technical Report TR 92-53, Department of Industrial and Operations Engineering, The University of Michigan, 1992．
34． A.B.Hadj-Alouane and J.C.Bean, A Genetic Algorithm for the Multi-choice Integer Program, Technical Report TR 92-50, Department of Industrial and Operations Engineering, The University of Michigan, 1992．
35． A.Smith and D.Tate, Genetic Optimization Using a Penalty Function, in ICGA93,499-503,1993．
36． D.Powell and M.M.Skolnick, Using Genetic Algorithms in Engineering design Optimization with Nonlinear Constraints, in ICGA93,424-430,1993．
37． J.T.Richardson, M.R.Palmer, G.Liepins and M.Hilliard, Some Guidelines for Genetic Algorithms with Penalty Functions, in ICGA89, 191-197,1989．
38． Z.Michalewicz, Genetic Algorithms, Numerical Optimization, and Constraints, in ICGA95,151-158,1995．
39． R.G.Le Riche, C.Knopf-Lenoir, R.T.Haftka, A Segragated Genetic Algorithm for Constrained Structural Optimization, in ICGA95, 558-565, 1995．
40． M.Schoenauer and S.Xanthakis, Constrained GA optimization, in ICGA93,573-580,1993．
41． Z.Michalewicz, A Perspective on Evolutionary Computation, in YAO95,73-89,1995．
42． Z.Michalewicz, G.Nazhiyath, Genecop III: A Co-evolutionary Algorithm for Numerical Optimization Problems with Nonlinear Constraints, in ICEC95,647-651,1995．
43． D.Waagen, P.Diercks, J.McDonnell, The Stochastic Direction Set Algorithm: a Hybrid Technique for Finding Function Extrema, in EP92, 35-42,1992．
44． H.Myung and J.-H.Kim, Constrained Optimization Using Two-phase Evolutionary Programming, in ICEC96,262-267,1996．
45． C.Maa and M.Shanblatt, A two-phase optimization neural networks, IEEE Trans, on Neural Networks, 3(6) , 1003-1009,1992．
46． J.D.Schaffer, Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, in ICGA85,93-100,1985．
47． I.Parmee, G.Purchase, The Development of Directed Genetic Search Tecnique for Heavily Constrained Design Spaces, in Proc. of the Conf. on Adaptive Computing in Engineering Design and Control, 424-430, Morgan Kaufmann.
2．Z.Michalewicz.演化程序．科学出版社 2000．1
3．玄广男 程润伟．遗传算法与工程设计．科学出版社 2000．1
4．刘勇 康立山．非数值并行算法(第二册)：遗传算法．科学出版社 1996
5．邢文训 谢金星．现代优化计算方法．清华大学出版社 1999
6．黄豪 沈成武 雷建平．一种连续变量的遗传算法．武汉交通科技大学学报 No．2 vol．23 1999
7．樊会元 王尚锦 席光．遗传算法引入进化方向算子的一个改进及应用．西安交通大学学报 No．5 vol．23 1999
8．周济．机械设计优化方法及其应用 高等教育出版社 1989．
9．刘唯信 机械最优化设计 清华大学出版社 1993
10．郭涛 演化计算与优化 武汉大学博士学位论文 1999．3
11．希梅尔劳D．M 实用非线性规划 北京大学出版社 1981．2
12. J.E.Baker, Adaptive Selection Methods for Genetic Algorithms, in L.J.Eshelman, (Ed.), Proc. of the 6th Int'l. Conf. on Genetic Algorithms, Morgan Kaufmann, San Francisco, 110--111, 1985.
13. Xin Yao. Global Optimization by Landscape Approximation and Evolution Search. IWEC-2000
14. X. Yao Y. Liu and G. Lin. Evolutionary Programming made faster. IEEE Transaction on Evolutionary Computation 3(2) 82-102 July 1999
15. K. Liang X. Yao C. S. Newton. A Preliminary Study into Evolutionary Search of Approximated N-Dimensional Landscape. Proceedings of the third Australia-Japan Joint Workshop on Intelligent and Evolutionary System Canberra Australia 23-25 November 1999 pp201-208
16. S. Koziel Z. Michalewicz. Evolutionary Algorithms, Homomorphous
Mappings and Constrained Parameter Optimization. IWEC-2000
17． Kumar Chellapilla . Evolution Nonlinear Controllers for Backing up a Truck-and-Trailer using Evolutionary Programming. 1997
18． Storn, R. and Price, K., Differential Evolution-a Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces, Technical Report TR-95-012, ICSI, March 1995
19． Joines, J.and.C.Houck(1994) .On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with gas .In Z. Michalewicz, J. D. Schaffer, H.-P. Schwefel, Proceedings of the First IEEE International conference on Evolutionary Computation ,pp 579-584 IEEE Press
20． Eiben. A. E, R. Hinterding, and Z.Michealewicz, Parameter Control in Evolution Algorithms, IEEE Transactions on Evolution Computation 3 124-141,1999
21． Adam P.Gurson,Simplex Search Behavior in Nonlinear Optimization,A thesis submitted in partial fulfillment of the requirements for a Bachelor of science with Honors in Computer Science from the College of William&Mary in Virginia,2000
22． Grefenstette J J,Gopal R,Rosmaita B,et al.Genetic algorithm for TSP.In:Grefenstette J J,eds. Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Pittsburgh.Pittsburgh P A Carnegie-Mellon University, 1985． 160-168
23． Goldberg D E. Genetic algorithms in search,optimization and machine learning. MA:Addison Wesley Reading, 1989． 1-10
24． Cheng R W,Gen M.Crossover on intensive search and traveling salesman problem. In:Gen M eds. Proceedings of 16th International Conference on Computer & Industrial Enginerring. Japan:Nagoya Institute of Technology, 1994,7-9: 568-579
25． Holland J H. Adaptation in natural and artificial systems [M] . Ann
Arbor: University of Michigan Press, 1975．
26． Fogel L J, Owens A J, Walsh M J. Artificial intelligence through simulated evolution [M] . New York: John Wiley, 1966．
27． Schwefel H P. Numberical optimization of computer models [M] . Chichester: John Wiley, 1981．
28． Fogel D B. Evolutionary computation [M] .New York: IEEE Press, 1995．
29． Rudolph G. Convergence analysis of canonical genetic algorithm [ J ] . IEEE Transactions on Neural Networks, 1994,5(1) :96-101．
30． A.Homaifar, C.X.Qi, S.H.Lai, Constrained optimization via Genetic Algorithms, Simulation, 62(4) , 242-254,1994．
31． J.Joines and C.Houck, On the Use of Non-stationary Penalty Functions to Solve Nonlinear Constrained Optimization Problems with GAs, in ICEC94,579-584,1994．
32． Z.Michalewicz and N.Attia, Evolutionary Optimization of Constrained Problems, in EP94,98-108,1994．
33． J.C.Bean and A.B.Hadj-Alouane, A Dual Genetic Algorithm for Bounded Integer Programs, Technical Report TR 92-53, Department of Industrial and Operations Engineering, The University of Michigan, 1992．
34． A.B.Hadj-Alouane and J.C.Bean, A Genetic Algorithm for the Multi-choice Integer Program, Technical Report TR 92-50, Department of Industrial and Operations Engineering, The University of Michigan, 1992．
35． A.Smith and D.Tate, Genetic Optimization Using a Penalty Function, in ICGA93,499-503,1993．
36． D.Powell and M.M.Skolnick, Using Genetic Algorithms in Engineering design Optimization with Nonlinear Constraints, in ICGA93,424-430,1993．
37． J.T.Richardson, M.R.Palmer, G.Liepins and M.Hilliard, Some Guidelines for Genetic Algorithms with Penalty Functions, in ICGA89, 191-197,1989．
38． Z.Michalewicz, Genetic Algorithms, Numerical Optimization, and Constraints, in ICGA95,151-158,1995．
39． R.G.Le Riche, C.Knopf-Lenoir, R.T.Haftka, A Segragated Genetic Algorithm for Constrained Structural Optimization, in ICGA95, 558-565, 1995．
40． M.Schoenauer and S.Xanthakis, Constrained GA optimization, in ICGA93,573-580,1993．
41． Z.Michalewicz, A Perspective on Evolutionary Computation, in YAO95,73-89,1995．
42． Z.Michalewicz, G.Nazhiyath, Genecop III: A Co-evolutionary Algorithm for Numerical Optimization Problems with Nonlinear Constraints, in ICEC95,647-651,1995．
43． D.Waagen, P.Diercks, J.McDonnell, The Stochastic Direction Set Algorithm: a Hybrid Technique for Finding Function Extrema, in EP92, 35-42,1992．
44． H.Myung and J.-H.Kim, Constrained Optimization Using Two-phase Evolutionary Programming, in ICEC96,262-267,1996．
45． C.Maa and M.Shanblatt, A two-phase optimization neural networks, IEEE Trans, on Neural Networks, 3(6) , 1003-1009,1992．
46． J.D.Schaffer, Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, in ICGA85,93-100,1985．
47． I.Parmee, G.Purchase, The Development of Directed Genetic Search Tecnique for Heavily Constrained Design Spaces, in Proc. of the Conf. on Adaptive Computing in Engineering Design and Control, 424-430, Morgan Kaufmann.