Назад в библиотеку

Исследование автоколебаний при моделировании гармонического осциллятора с использованием комплексов моделирования

Автор: A.A. Авдеев
Источник: [Ссылка]

Аннотация

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

Рассмотрим применение аппарата генетических алгоритмов к задачам оптимизации на примере ставшей уже классической задачи коммивояжера.

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

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

P = (N − 1)!,

где P – мощность пространства поиска; N – количество городов.

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

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

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

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

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

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

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

F(x) = ∑ i = 0 2 α i F i (x),

где αi>0 – весовой коэффициент; Fi(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 – График улучшения приспособленности в популяции

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

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

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

  1. Википедия – свободная энциклопедия. Статья «Задача коммивояжера» [Ссылка]
  2. Weisstein, Eric W. "Hamiltonian Cycle." From MathWorld – A Wolfram Web Resource. [Ссылка]
  3. Рутковская Д., Пилиньский М Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И.Д. Рудинского. – М.: Горячая линия – Телеком, 2006. с. 452
  4. Холланд Дж.Х. Генетические алгоритмы: Пер. с англ. // В мире науки. – 1992. с. 9-10.
  5. Шелупанов А.А., Шумский А.А. Основы системного анализа: Учеб. пособие. – Томск: Том. межвуз. центр дистанционного образования, 2005. с. 225