Телефон: +7 (383)-235-94-57

УСТОЙЧИВОСТЬ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В РЕШЕНИИ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ С ОГРАНИЧЕНИЯМИ

Опубликовано в журнале: Инженерные решения №2(3)

Автор(ы): Парменов Олег Игоревич, Сизов Андрей Андреевич

Рубрика журнала: Математические и компьютерное моделирование

Статус статьи: Опубликована 18 февраля

DOI статьи: 10.32743/2658-6479.2019.2.3.86

Библиографическое описание

Парменов О.И., Сизов А.А. УСТОЙЧИВОСТЬ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В РЕШЕНИИ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ С ОГРАНИЧЕНИЯМИ // Инженерные решения: эл.научный журнал. –2019 – №2(3). URL: https://journaltech.ru/archive/3/86 (дата обращения: 13.11.2019). DOI: 10.32743/2658-6479.2019.2.3.86

Парменов Олег Игоревич

канд. техн. наук, доц. ФГАОУ ВО «Крымский федеральный  университет им. В.И.Вернадского»,

РФ, г.Симферополь

Сизов Андрей Андреевич

магистрант, ФГАОУ ВО «Крымский федеральный университет им. В.И.Вернадского»,

РФ, г.Симферополь

GENETIC ALGORITHMS STABILITY IN DISCRETE OPTIMIZATION TASKS WITH RESTRICTIONS

 

Oleg Parmenov

сandidate of technical sciences, Associate Professor of V.I.Vernadsky Crimean Federal University,

Russia, Simferopol

Andrey Sizov

master student of  V.I.Vernadsky Crimean Federal University,

Russia, Simferopol

 

АННОТАЦИЯ

Рассмотрены особенности применения генетических алгоритмов (ГА) в решении задач дискретной оптимизации на примере задачи коммивояжёра с учетом дополнительных ограничений. Проанализированы вопросы особенностей реализации, эффективности ГА и их устойчивости.

ABSTRACT

The advantage of genetic algorithms (GA) in discrete optimization problem of the traveling salesman is described. It’s analyzed GA implementation specifics to provide GA efficiency and sustainability taking into account additional restrictions. 

 

Ключевые слова: генетический алгоритм, дискретная оптимизация.

Keywords: genetic algorithm, discrete optimization.

 

Генетические алгоритмы (ГА), предложенные в 60-х годах XX века, хорошо зарекомендовали себя в задачах дискретной оптимизации [1]. Затраты на предварительную подготовку информации в форме специфических информационных последовательностей (т.н. хромосом, кодирующих данные решаемой задачи), окупаются высокой эффективностью ГА, в частности – при поиске решения сложных комбинаторных задач. Сам поиск решения имитирует процесс эволюции, когда решение получают отбором и рекомбинацией последовательностей.

Нами предварительно [2] рассмотрено решение с использованием ГА классической комбинаторной NP-задачи об отыскании кратчайшего маршрута, соединяющего n городов, при условии их однократного посещения. Решение определяется поиском среди гамильтоновых циклов, причем в задачах без ограничений алгоритм обеспечивает нахождение решения для любого начального приближения практически за одинаковое время.

 

Рисунок 1. Оптимальный маршрут для простых распределений с выбором начальной точки маршрута

 

В качестве начального приближения брались случайно сгенерированные особи (рис. 2), не являющиеся ни оптимальными, ни даже близкими к оптимальным; на рис. 3 для них представлены решения при указании ограничений, полученные соответственно за 1800 и 1500 итераций генетического алгоритма. Ограничениями являлись: указание начального города, максимального количества городов для посещения, количества итераций алгоритма. Было использовано целочисленное кодирование, упрощающее программную реализацию и уменьшающее время поиска решения.

 

Рисунок 2. Примеры начальных популяций для 25 городов

 

Рисунок 3. Найденные решения для заданных начальных популяций

 

С целью анализа устойчивости алгоритма и его эффективности, проведено тестирование на компактных, равномерных и неравномерных распределениях (рис.4).

 

Рисунок 4. Вид маршрутов для распределений равномерного и неравномерного с групповыми локализациями (40 элементов)

 

При компактных равномерных распределениях, с ростом количества городов алгоритм демонстрирует полиномиальную зависимость временных затрат на поиск решения (рис. 5). В то же время, при неравномерном распределении с групповыми локализациями алгоритм «переключается» с одной группы городов на другую, «откатывается» к ранее полученным маршрутам (специфика ГА), что увеличивает время поиска.

Тем не менее, рост временных затрат на неравномерных распределениях остается полиномиальным, а найденные маршруты оказываются вполне приемлемыми, что свидетельствует об устойчивости как алгоритма, так и программной реализации, не требующих дополнительных модификаций.

 

Рисунок 5. Зависимость временных затрат на поиск решения

 

Кроме того, большое влияние на качество найденного решения и на время его поиска оказывает выбор метода селекции. Обычно, в подобных случаях используется метод рулетки, для которого вероятность i-ой особи принять участие в скрещивании  пропорциональна значению ее приспособленности  и равна:

Сам процесс отбора особей для скрещивания напоминает игру в «рулетку». Рулеточный круг делится на сектора, причем площадь i-го сектора пропорциональна значению . Рулетка «вращается» n раз, где n – размер популяции. По номеру сектора, на котором останавливается рулетка, определяется особь, выбранная для скрещивания. Слабая сторона этого метода в том, что особи с малым значением функции приспособленности  слишком быстро исключаются из популяции, что приводит к преждевременной сходимости алгоритма к некоторому варианту, который может оказаться далек от оптимального. Поскольку при большом количестве особей в популяции площади секторов на рулетке отличаются незначительно, отбор особей методом рулетки сводится к практически случайной выборке. Мы полагаем, что такой способ отбора нерезультативен; генетические операторы при таком методе селекции используются неэффективно, что сводит преимущества ГА практически «на нет».

При использовании турнирного отбора также отбираются n особей популяции, из которой случайно выбираются t особей (формируется турнир), причем, чем больше значение t, тем большее давление селекции. Типичные значения размера турнира t = 2 (бинарный турнир), 3, 4, 5. При таком отборе самая приспособленная особь набора допускается к скрещиванию. Эта операция повторяется n раз, а сам размер турнира t варьируется. Использование такого метода селекции показало наилучшие результаты в обеспечении устойчивости реализации ГА.

Выводы:

  • Использование целочисленного кодирования дает преимущества во времени поиска решения; при большом числе городов предпочтителен турнирный метод селекции;
  • Фиксация начального города, являющаяся дополнительным ограничением, хотя и сужает пространство поиска, приводит к заметному увеличению времени на поиск решения;
  • При произвольном начальном распределении, с ростом количества городов алгоритм демонстрирует фактически полиномиальный рост временных затрат на поиск приемлемого решения (P-сложность).

 

Список литературы:

  1. John H. Holland Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence.- MIT Press, 1992.- 232p.
  2. Парменов О.И., Сизов А.А. Повышение эффективности генетических алгоритмов в решении задач дискретной оптимизации // Сб. ст. XV международной научно-практической конференции «Strategiczne pytania światowej nauki - 2019» (Перемышль, Польша, 2019).- Przemyśl, Nauka i studia, 2019.- Vol.2, C.31-34.