Аннотация
Рассмотрены проблемы применения генетических алгоритмов к многокритериальным задачам оптимизации. На примере задачи коммивояжера показаны некоторые особенности в настройке параметров генетического алгоритма. Продемонстрирован пример действия эволюции решений в задаче коммивояжера в многокритериальной постановке.
Рассмотрим применение аппарата генетических алгоритмов к задачам оптимизации на примере ставшей уже классической задачи коммивояжера.
Задачи коммивояжера в многокритериальном виде определяются следующим образом: в области существует N точек (городов), соединенных дорогами, согласно принципу «каждый с каждым», проезд по дороге характеризуется некоторым вектором стоимости. Задача бродячего торговца (коммивояжера) – пройти с минимальными затратами через каждый город по одному разу, при этом на последнем шаге вернуться в исходный город. Вектор стоимости маршрута в данной постановке задачи будет представлен тремя компонентами: пройденное расстояние, время в пути, материальные затраты. Так как маршрут должен проходить через каждый город только один раз, то выбор осуществляется среди гамильтоновых циклов. Отыскание гамильтоновых циклов так же, как и задача коммивояжера, является NP-полной задачей. Часто на задаче коммивояжера проводят обкатку новых подходов к эвристическому сокращению полного перебора [1].
Пространство решений для аппарата генетических алгоритмов будет составлять [2]:
Простейшие методы решения задачи коммивояжера: полный лексический перебор, «жадные» алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешёвого включения), метод минимального остовного дерева. На практике применяются различные модификации более эффективных методов: метод ветвей и границ, а также алгоритм муравьиной колонии.
Все эффективные (в смысле сокращения полного перебора) методы решения задачи коммивояжера эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближенное решение. Зачастую востребованы так называемые any-time алгоритмы, т.е. постепенно улучшающие некоторое текущее приближенное решение. Примером эвристических методов является также и генетический алгоритм.
Генетический алгоритм представляет собой метод, отражающий естественную эволюцию методов решения проблем и в первую очередь задач оптимизации. Генетические алгоритмы – процедуры поиска, основанные на механизмах естественного отбора и наследования. В них используется эволюционный принцип выживания наиболее приспособленных особей. Они отличаются от традиционных методов оптимизации несколькими базовыми элементами. В частности, генетические алгоритмы [3]:
1) обрабатывают закодированную форму параметров задачи;
2) осуществляют поиск решения исходя из некоторого множества точек пространства возможных решений;
3) используют только целевую функцию;
4) применяют вероятностные правила выбора.
Сложность грамотного применения и разработки программного обеспечения, использующего аппарат генетических алгоритмов, заключается в выборе:
1. функции приспособленности (fittnes function), т.е. таких условий, что помогут ограничить пространство поиска только теми значениями, которые, вероятно, являются решениями;
2. параметров генетического алгоритма (количество предков и потомков, частота мутаций и т.д.), которые, с одной стороны, должны не препятствовать быстрому прохождению процедуры ранжирования особей по приспособленности, с другой стороны, не должны приводить к преждевременному схождению к неверному результату.
Поскольку постановка задачи коммивояжера является в нашем случае многокритериальной, воспользуемся одним из возможных способов решения многокритериальных задач – методом свертывания векторного критерия в суперкритерий:
Для нахождения весовых коэффициентов проведем экспертную оценку по методу парных сравнений [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