РЕШЕНИЕ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ОБЩЕГО ВИДА ГЕНЕТИЧЕСКИМ АЛГОРИТМОМ
DOI:
https://doi.org/10.22213/2410-9304-2019-4-137-142Ключевые слова:
условная оптимизация, нелинейное программирование, генетический алгоритм, дополнительная популяция, учет ограниченийАннотация
В работе предложен генетический алгоритм решения задачи условной оптимизации общего вида с дополнительной популяцией для поиска допустимых особей и модифицированным турнирным отбором. При поиске решения акцент сделан на его допустимости, поэтому оценка приспособленности особей в первую очередь определяется не сравнением значений целевой функции, а качеством выполнения ограничений. Такой подход сочетает в себе эффективность генетических алгоритмов при решении задач глобальной оптимизации с простым и естественным непосредственным учетом условий в виде равенств или неравенств при поиске оптимального решения, не требуя дополнительных преобразований исходной задачи или сведения ее к безусловной оптимизации.
Важной особенностью метода является то, что он в значительной степени обладает универсальностью и хорошо подходит для задач с большим числом ограничений произвольного вида и функций со сложным характером − овражных, многоэкстремальных, недифференцируемых. В работе реализован гибридный генетический алгоритм с дополнительным обучением элиты, что значительно повышает скорость сходимости и качество получаемого решения по сравнению с классическим алгоритмом.
Сравнение результатов решения известных тестовых задач с опубликованными ранее результатами применения существующих подходов свидетельствует о перспективности и эффективности представленного алгоритма.Библиографические ссылки
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.