К.т.н., доцент Частикова В.А., Власов К.А.

Кубанский государственный технологический университет, Россия

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

Генетические алгоритмы – это сравнительно молодой эвристический метод поиска оптимальных решений. Данный алгоритм использует механизмы, напоминающие биологическую эволюцию. [1]

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

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

Для проведения исследования был разработан и реализован программный комплекс [3-4], позволяющий осуществлять сравнительный анализ работы ГА и классических методов. Для этого в программном комплексе были реализованы такие классические методы, как жадный алгоритм, модификация жадного алгоритма – метод кратчайших отрезков, полный перебор.

Сравнительный анализ длин найденных маршрутов различными алгоритмами при количестве городов от 200 на 350 представлен на рисунке 1.

Рисунок 1 – Гистограмма длин найденных маршрутов различными алгоритмами при количестве городов от 200 до 350

В работе была проведена настройка таких параметров ГА, как инициализация первого поколения, алгоритм скрещивания, отбор особей, переходящих в следующее поколение и др. А также было разработано несколько модификаций: «модификация жадным алгоритмом», «несколько популяций» и «модификация методом ветвей и границ». Инициализация первого поколения с применением предложенных модификаций, отбор особей в следующее поколение в пропорции 60% лучших родительских и 40% лучших дочерних, разведение нескольких независимо развивающихся популяций позволяют находить наиболее эффективные решения.

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

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

Для проведения исследования в разработанном программном комплексе [3-4] для сравнения эффективности работы ГА был реализован классический метод индексации. Была осуществлена настройка параметров ГА с учетом особенностей задачи поиска пути в графе. В частности, из-за ограничений, накладываемых графом, алгоритм скрещивания хромосом для данной задачи существенно отличается от классического.

Литература:

1. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989.

2. Greco Federico. Travelling Salesman Problem. Austria: I-Tech Education and Publishing KG, Vienna, 2008.

3. Частикова В.А., Власов К.А. Свидетельство о государственной регистрации программы для ЭВМ № 2011616886. Программный комплекс для исследования и сравнительного анализа работы модифицированного генетического алгоритма: зарегистрировано в Реестре программ для ЭВМ 6 сентября 2011.

4. Частикова В.А., Власов К.А. Свидетельство о государственной регистрации программы для ЭВМ № 2012612687. Генетический поиск оптимальных решений в задачах комбинаторики: зарегистрировано в Реестре программ для ЭВМ 15 марта 2012.