ПРО ОДНИЙ КЛАС ГЕНЕТИЧНИХ АЛГОРИТМІВ У ЗАВДАННЯХ ОПТИМІЗАЦІЇ НА КОМБІНАТОРНИХ КОНФІГУРАЦІЯХ
Ключові слова:
КОМБІНАТОРНА КОНФІГУРАЦІЯ, ОПТИМІЗАЦІЯ, ГЕНЕТИЧНИЙ АЛГОРИТМ, КРОСОВЕР, МУТАЦІЯ, ПЕРЕСТАНОВКААнотація
У статті введено поняття евклідової комбінаторної конфігурації як відображення абстрактної множини в арифметичний евклідовий простір. Сформульовано задачу оптимізації на множині евклідових комбінаторних конфігурацій. Розглянуто особливості застосуван- ня генетичних алгоритмів для розв’язання зазначеного класу задач. Описано принципи формування початкової популяції, механізму відбору, вибір операторів кросовера і мутації. Підхід ілюструється на задачах комбінаторної оптимізації на множині перестановок. Наведені приклади побудови різних операторів кросовера для евклідових конфігурацій перестановок.
Посилання
Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms. — Heidelberg; New York: Springer Berlin, 2002. — 660 pp.
Pardalos P., Du D.-Z., Graham R. L. Handbook of Combinatorial Optimization. — 2nd ed. — Heidelberg: Springer. — 2013, XXI.
Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. — К.: Наук. думка, 2003. — 261 с.
Гуляницький Л. Ф., Мулеса О. Ю. Прикладні методи комбінаторної оптимізації: навчальний посібник. — К: Видавничо-поліграфічний центр «Київський університет», 2016. — 142 с.
Субботін С.О., Олійник А.О., Олійник О.О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: монографія. — Запоріжжя : ЗНТУ, 2009.
Neri F., Cotta C., Moscato P. Handbook of Memetic Algorithms — Berlin, Heidelberg: Springer-Verlag, 2012.
Karaboga D., Gorkemli B., Ozturk C., Karaboga N. A comprehensive survey: artiicial bee colony (ABC) algorithm and applications — Artiicial Intelligence Review. - 2014. - 42 (1). — P. 21-57.
Nikolic M., Teodorovic D. Empirical study of the bee colony optimization (BCO) algorithm - Expert Systems with Applications. - 2013. - 40(11). — P. 4609-4620.
Dorigo M., Blum C. Ant colony optimization theory: A survey – Theoretical Computer Science. — 2005. —344. — P. 243-278.
Pintea C.-M. Advances in Bio-inspired Computing for Combinatorial Optimization Problems - Heidelberg: Springer, 2014. 138
Zhang P. Combinatorial optimization problem solution based on improved genetic algorithm. AIP Conference Proceedings 1864, 020206 (2017)
Eremeev A.V. Optimal recombination in genetic algorithms for combinatorial optimiyation problems part II. Yugoslav Journal of Operations Research, [S.l.], v. 24, n. 1, oct. 2016. ISSN 2334-6043
Venkatesan D., Balachandar Kannan S. R. A New Genetic Algorithm for Time Dependent Combinatorial Optimization Problem National Academy Science Letters, June 2016, Volume 39, Issue 3, pp 207–211.
Rajappa, Gautham P., Solving Combinatorial Optimization Problems Using Genetic Algorithms and Ant Colony Optimization”, PhD diss., University of Tennessee, 2012.
Berge C. Principes de combinatoire. – Paris: Dunod, 1968. – 146 p.
Сачков В.Н. Комбинаторные методы дискретной математики. – М.: Наука, 1975. – 319 с.
Стоян Ю.Г., Гребенник И.В. Описание классов комбинаторных конфигураций на основе отображений // Доклады НАН Украины. — 2008. — №10. — С. 28 – 31.
Донець Г.П., Колєчкіна Л.М. екстремальні задачі на комбінаторних конфігураціях. – Полтава: ПУеТ, 2011. – 328 с.
Гуляницкий Л.Ф., Сергиенко И.В. Метаэвристический метод деформированного многогранника в комбинаторной оптимизации // Кибернетика и системный анализ. — 2007. — № 6. — С. 70–79.
Гуляницкий Л.Ф., Сиренко С.И. Определение и исследование комбинаторных пространств // Теорія оптимальних рішень. – 2010. – № 9. – С. 17–25.
Яковлев С.В., Пичугина О.С. Задачи оптимизации на евклидовых комбинаторных конфигурациях и их свойства //Питання прикладної математики і математичного моделювання. – Дніпро. – 2017. – Вип.17 . – С. 228-235.
Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. — К.: Наук. думка, 1986. — 268 с.
Yakovlev S.V. Тhe method of artiicial space dilation in problems of optimal packing of geometric objects // Cybernetics and Systems Analysis. – 2017. – 53(5). – P. 725-732.
Pichugina O.S., Yakovlev S.V. Functional and analytic representations of the general permutations // Eastern-European Journal of Enterprise Technologies. – 2016. – 1(4). – P. 27-38.
Pichugina O.S., Yakovlev S.V. Continuous Representations and Functional Extensions in Combinatorial Optimization – Cybernetics and Systems Analysis. – 2016, 52(6), pp. 921-930.
