Применение генетических алгоритмов к задачам оптимизации

 Аннотация

Рассмотрены проблемы применения генетических алгоритмов к многокритериальным задачам оптимизации. На примере задачи коммивояжера показаны некоторые особенности в настройке параметров генетического алгоритма. Продемонстрирован пример действия эволюции решений в задаче коммивояжера в многокритериальной постановке.

 Рассмотрим применение аппарата генетических алгоритмов к задачам оптимизации на примере ставшей уже классической задачи коммивояжера.
 Задачи коммивояжера в многокритериальном виде определяются следующим образом: в области существует N точек (городов), соединенных дорогами, согласно принципу «каждый с каждым», проезд по дороге характеризуется некоторым вектором стоимости. Задача бродячего торговца (коммивояжера) – пройти с минимальными затратами через каждый город по одному разу, при этом на последнем шаге вернуться в исходный город. Вектор стоимости маршрута в данной постановке задачи будет представлен тремя компонентами: пройденное расстояние, время в пути, материальные затраты. Так как маршрут должен проходить через каждый город только один раз, то выбор осуществляется среди гамильтоновых циклов. Отыскание гамильтоновых циклов так же, как и задача коммивояжера, является NP-полной задачей. Часто на задаче коммивояжера проводят обкатку новых подходов к эвристическому сокращению полного перебора [1].

 Пространство решений для аппарата генетических алгоритмов будет составлять [2]:

 P = (N - 1)!, где P – мощность пространства поиска; N - количество городов.

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

 Все эффективные (в смысле сокращения полного перебора) методы решения задачи коммивояжера эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближенное решение. Зачастую востребованы так называемые any-time алгоритмы, т.е. постепенно улучшающие некоторое текущее приближенное решение. Примером эвристических методов является также и генетический алгоритм.

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

 1) обрабатывают закодированную форму параметров задачи;
 2) осуществляют поиск решения исходя из некоторого множества точек пространства возможных решений;
 3) используют только целевую функцию;
 4) применяют вероятностные правила выбора.

 Сложность грамотного применения и разработки программного обеспечения, использующего аппарат генетических алгоритмов, заключается в выборе:

 1. функции приспособленности (fittnes function), т.е. таких условий, что помогут ограничить пространство поиска только теми значениями, которые, вероятно, являются решениями;
 2. параметров генетического алгоритма (количество предков и потомков, частота мутаций и т.д.), которые, с одной стороны, должны не препятствовать быстрому прохождению процедуры ранжирования особей по приспособленности, с другой стороны, не должны приводить к преждевременному схождению к неверному результату.

 Поскольку постановка задачи коммивояжера является в нашем случае многокритериальной, воспользуемся одним из возможных способов решения многокритериальных задач – методом свертывания векторного критерия в суперкритерий:

F(x)=∑α_iF_i(x)  где α _i > 0 – весовой коэффициент; F _i(x) - значение функции приспособленности по критерию.

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

 Построим таблицу для нахождения весовых коэффициентов критериев оптимизации.

 Нахождение весовых коэффициентов для критериев оптимизации

Длина пути	1	2	2	5
Материальные затраты	7	1	2	10
Время в пути	7	7	1	15

 В данном случае была применена шкала (1-9), при этом «1» обозначает то, что критерии сравнимы или равнозначны. 2–9 определяет степень превосходства одного критерия над другим. По главной диагонали были проставлены «1», так как критерий сам с собой равнозначен. Остальные же оценки были получены исходя из условий вышеописанной ситуации.

 Для настройки генетического алгоритма также необходимо определить количество предков и потомков. Эти данные обычно находятся опытным путем или в результате имеющегося опыта подобных действий [4]. Выберем для конкретности количество предков равным 1000 особей задачи возьмем в два раза больше (2000 особей). Продемонстрируем на примере сходимость генетического алгоритма в случае наличия 10-ти городов, при этом время работы программного продукта составляет в среднем 0,1-2

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

  Список использованной литературы

  1. Википедия – свободная энциклопедия. Статья «Задача коммивояжера» [http: //ru. wikipedia. org/wiki/задачакоммивояжера]
  2. Weisstein E.W. Hamiltonian Circuit [http: //www. http: //mathwor ld. wolfram. com/HamiltonianCircuit.html]
  3. Рутковская Д., Пилиньский М Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И.Д. Рудинского. – М.: Горячая линия – Телеком, 2006. с. 452
  4. Холланд Дж.Х. Генетические алгоритмы: Пер. с англ. // В мире науки. – 1992. с. 9-10.
  5. Шелупанов А.А., Шумский А.А. Основы системного анализа: Учеб. пособие. – Томск: Том. межвуз. центр дистанционного образования, 2005. с. 225