РЕШЕНИЕ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ОБЩЕГО ВИДА ГЕНЕТИЧЕСКИМ АЛГОРИТМОМ

Авторы

  • В. А. Тененев
  • А. С. Шаура

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.

Загрузки

Опубликован

12.01.2020

Как цитировать

Тененев, В. А., & Шаура, А. С. (2020). РЕШЕНИЕ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ОБЩЕГО ВИДА ГЕНЕТИЧЕСКИМ АЛГОРИТМОМ. Интеллектуальные системы в производстве, 17(4), 137–142. https://doi.org/10.22213/2410-9304-2019-4-137-142

Выпуск

Раздел

Статьи