Solving General Nonlinear Programming Problems with a Genetic Algorithm
DOI:
https://doi.org/10.22213/2410-9304-2019-4-137-142Keywords:
constrained optimization problem, nonlinear programming, genetic algorithm, additional population, constraint handlingAbstract
The paper proposes a genetic algorithm with an additional population to search for feasible individuals and modified tournament selection to solve the conditional optimization problem. When searching for a solution, the emphasis is on its feasibility, so the assessment of a fitness of individuals is primarily determined not by comparing the values of the objective function, but by the satisfaction of the implementation of constraints. This approach combines the effectiveness of genetic algorithms in solving global optimization problems with simple and natural direct consideration of constraints in the form of equality or inequalities in the search for the optimal solution, without requiring additional transformations of the original problem or reducing it to unconditional optimization.
An important feature of the method is that it is largely versatile and well-suited to problem with a large number of constraints and ravine, multi-extreme and non-differentiated functions. The work implemented a hybrid genetic algorithm with additional elite training, which significantly increases the rate of convergence and the quality of the resulting solution compared to the classic algorithm.
Comparing the results of the solution of known optimization benchmarks with the previously published results of the existing approaches shows the perspective and effectiveness of the presented algorithm.
References
Michalewicz Z. Handling Constraints in Genetic Algorithms. Proc. of the 4th International Conference on Genetic Algorithms, 1991. Pp. 151-157. URL: https://ci.nii.ac.jp/naid/10006390693/en/.
Helio Barbosa, Afonso Lemonge. An Adaptive Penalty Method for Genetic Algorithms in Constrained Optimization Problems. 2008. DOI: 10.5772/5446.
Mohamed Abdel-Baset, Ibrahim M. Hezam. An Effective Hybrid Flower Pollination and Genetic Algorithm for Constrained Optimization Problems. Advanced Engineering Tech-nology and Application. 4. 27-34. 2015. DOI: 10.12785/aeta/040203.
Wali Mashwani, Ozgur Yeniay, Habib Shah, Nasser Tairan, Muhammad Sulaiman. Hybrid Constrained Evolutionary Algorithm for Numerical Optimization Problems. Hacettepe University Bulletin of Natural Sciences and Engineering Series B: Mathematics and Statistics. 48. 2018. DOI: 931-950. 10.15672/HJMS.2018.625.
Yu X., Gen M. Introduction to Evolutionary Algorithms. London: Springer. 2010. DOI:0.1007/978-1-84996-129-5.
Kimbrough S. O., Lu M., Koehler G. J., & Wood D. H. On a Feasible–Infeasible Two-Population (FI-2Pop) Genetic Algorithm for Constrained Optimization: Distance Tracing and no Free Lunch. European Journal of Operational Research, 2008, 190 (2), 310-327. http://dx.doi.org/10.1016/j.ejor.2007.06.028.
Koziel S., Michalewicz Z. Evolutionary Algorithms, Homomorphous Mappings, and Constrained Parameter Opti-mization. Evolutionary computation. 1996. DOI: abs/10.1162/evco.1996.4.1.1.
Mezura-Montes E., Coello C. A. Constrainthandling in nature-inspired numerical optimization: Past, present and future. Swarm and Evolutionary Computation, 2011, 1(4), 173-194. DOI:10.1016/j.swevo.2011.10.001.
Rafael Garcia, Beatriz Lima, Breno Jacob, Afonso Lemonge. Handling optimization problems with constraints of different magnitudes using evolutionary algorithms. 2015. DOI: 10.20906/CPS/CILAMCE2015-0631.
Adam Chehouri, Rafic Younes, Jean Perron, Adrian Ilinca. A constraint-handling technique for genetic algorithms using a violation factor. 2016. 12. 350-362. DOI: 10.3844/jcssp.2016.350-362.
Прохоровская Е. В., Тененёв В. А., Шаура A. C. Генетические алгоритмы с вещественным кодированием при решении задач условной оптимизации // Интеллектуальные системы в производстве. 2008. № 2 (12) С. 46–55.
Kimbrough S. O., Lu M., Koehler G. J., & Wood D. H. On a Feasible–Infeasible Two-Population (FI-2Pop) Genetic Algorithm for Constrained Optimization: Distance Tracing and no Free Lunch. European Journal of Operational Research, 2008, 190 (2), 310-327. http://dx.doi.org/10.1016/j.ejor.2007.06.028.
Kalyanmoy Deb. An efficient constraint handling method for genetic algorithms / Comput. Methods Appl. Mech. Engrg. 2000. 186. 311-338.
Liang J. J. Thomas Philip Runarsson, Efren Mezura-Montes, Maurice Clerc P. N. Suganthan, Carlos A. Coello Coello, K. Deb. Problem Definitions and Evaluation Criteria for the CEC 2006. Special Session on Constrained Real-Parameter Optimization. Technical Report, September 18, 2006. рр. 24.
Schittkowski K. On the convergence of a sequential quadratic programming method with an augmented Lagrangian line search function, Mathematik Operationsforschung und Statistik, Serie Optimization, 1983, 14, 197-216.
Тененев В. А., Паклин Н. Б. Гибридный генетический алгоритм с дополнительным обучением лидера // Интеллектуальные системы в производстве. 2003. № 2. С. 181–206.
Редер Т., Тененев В. А., Мищенкова О. В. Идентификация динамической модели предохранительного клапана // Интеллектуальные системы в производстве. 2018. Т. 21. № 4. С. 13–21.
Helio Barbosa, Afonso Lemonge. An Adaptive Penalty Method for Genetic Algorithms in Constrained Optimization Problems. 2008. DOI: 10.5772/5446.
Wali Mashwani, Ozgur Yeniay, Habib Shah, Nasser Tairan, Muhammad Sulaiman. Hybrid Constrained Evolutionary Algorithm for Numerical Optimization Problems. Hacettepe University Bulletin of Natural Sciences and Engineering Series B: Mathematics and Statistics. 48. 2018. DOI: 931-950. 10.15672/HJMS.2018.625.
Rafael Garcia, Beatriz Lima, Breno Jacob, Afonso Lemonge. Handling optimization problems with constraints of different magnitudes using evolutionary algorithms. 2015. DOI: 10.20906/CPS/CILAMCE2015-0631.
