Материал: Генетический алгоритм как метод оптимизации

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

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

Пусть для простоты примера количество городов N = 8, тогда одной из возможных последовательностей городов будет путь, изображенный на рис. 2.3.1.

Рисунок 2.3.1. - Пример маршрута коммивояжера при обходе 8 городов

Закодируем города числами от 1 до 8. Тогда тот же самый путь примет вид.

Теперь нам нужно представить решение в виде хромосомы. Выше мы уже закодировали решение в виде последовательности номеров городов, теперь осталось перекодировать ее хромосому. Для определенности будем считать, что мы кодируем в хромосому в виде битового вектора. Очевидно, что длина гена в битах в хромосоме будет равна:

понадобиться 3 бита. Кодируем последовательность с помощью двоичного кодирования

Таблица 2.3.1 - Кодирование последовательности городов с помощью двоичного кодирования.

Однако представив решение таким образом, мы не учли несколько существенных факторов:

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

000 010

100 101 110 010.

.        хромосомы с повторяющимися генами может дать кроссинговер или мутация.

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

Вообще говоря, для генетических алгоритмов очень важен вопрос кодирования решений в последовательность генов. От того, насколько оно удачно, зависит качество работы алгоритма. Самое главное, и обязательное, требование к кодированию - хромосома должна однозначно представлять некоторое решение, чтобы не было возможности трактовать одну и ту же хромосому по-разному. Желательно, чтобы хромосомы занимали как можно меньше бит, были короче. Так же важным условием является простота кодирования. От этого зависит скорость работы.

После кодирования запускается генетический алгоритм с желаемыми параметрами.

2.4 Реализация генетического алгоритма для решения задачи коммивояжера с использованием пакета MATLAB 7.5

Пакет MALAB 7.5 предоставляет встроенную панель инструментов Genethic Algorithm and Direct Search Toolbox™, которая предназначена для расширенияфункциональных возможностей пакета генетическими алгоритмами. Работать с данной панелью инструментов можно двумя способами: с консоли или вызвав панель Genethic Algorithm Tool с помощью команды gatool. По сути, оба способа являются идентичными с той разницей, что используя панель Genethic Algorithm Tool, любые параметры генетического алгоритма настраиваются с использованием графической оболочки.

Рассмотрим встроенные функции для работы с генетическими алгоритмами [9]:

[x fval reason output population scores] =

ga(@fitnessfun, nvars, options) - функция для нахождения минимума целевой функции; Входные параметры:

@fitnessfun - указатель функции в М-файле, по которой производится расчет функции приспособленности;- число независимых переменных для функции приспособленности;- настраиваемые параметры генетического алгоритма; Выходные параметры: x - конечная точка расчета; fval - значение функции приспособленности в точке x; o reason - причина остановки алгоритма; output - структура с информацией о эффективности работы алгоритма для каждого выполненного поколения;- состояние последнего семейства; o scores - конечное состояние;= gaoptimget(options, ’Name’) - возвращает параметры используемого генетического алгоритма; Входные параметры:- структура с параметрами генетического алгоритма;’Name’- имя параметра, значение которого нужно извлечь;

Выходные параметры:

val - значение запрашиваемого параметра;

options = gaoptimset(’param1’, value1, ’param2’,

value2, ...) - устанавливает параметры генетического алгоритма;

Входные параметры:

’param1’ - имя параметра;- устанавливаемое значение;

Выходные параметры:

- структура с параметрами генетического алгоритма.

Для решения задачи коммивояжера будем генерировать города случайным образом в отрезке [0, 1], при этом расстояния между городами подчиняются правилу треугольника.

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

1.      Хромосома представлена в виде бинарного вектора;

2.      Размер популяции - 50 особей;

.        Для расчета функции приспособленности используется стандартная функция travelling_salesman_fitness, принимающая в качестве аргумента хромосому (то есть одна из возможных перестановок городов) и возвращающая значение функции приспособленности для нее;

4.      Кроссинговер: применяемая стратегия - генерация перестановок (используется стандартная функция crossover_permuation), вероятность кроссинговера - 0.8;

.        Мутации: стратегия - так же применяется стандартная функция mutate_permutation, которая с определенной вероятностью генерирует перестановки в векторе пути, вероятность мутации - 0.2. Величина мутации такая большая, так как используется относительно небольшая популяция и велика вероятность попадания в локальный минимум;

.        Применяется стратегия элитарности; из каждой предыдущей популяции остается 2 наилучшие особи;

7.      Критерием остановки выполнения алгоритма является сохранение значений функции приспособленности на протяжении 50 поколений (для количества городов >100), 1000 поколений (для 100 - 400 городов), 7500 поколений (>400 городов);

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

генетический алгоритм оптимизация коммивояжер

2 + 1,

где k - шаг оптимизации, генерировались всевозможные перестановки, то есть вокруг города i генерировались перестановки в участке пути, в который входят города

− … … + . Количество перестановок тогда будет равно 2 − 1 !.

Таблица 2.4.1 - Сравнение точности решения задачи коммивояжера с помощью генетических алгоритмов с эффективными методами решения на одинаковых наборах данных.

Таблица 2.4.2 - Сравнение времени решения задачи коммивояжера с помощью генетических алгоритмов с эффективными методами решения на одинаковых наборах данных (время в мс).

Таблица 2.4.3 - Сравнение времени решения задачи коммивояжера с помощью генетических алгоритмов с эффективными методами решения на одинаковых наборах данных (время в мс, продолжение.

Анализируя табл. 2.4.2 и табл. 2.4.3, очевидно, что генетический алгоритм находит более точное решение по сравнению с решением задачи с помощью минимального остова даже с оптимизацией. Однако при решении задачи коммивояжера с помощью генетического алгоритма возникает ряд проблем - нужно менять условие остановки алгоритма в зависимости от числа городов, поскольку генетические алгоритмы имеют относительно плохую сходимость при большой длине хромосомы; так же генетические алгоритмы имеют не очень хорошие показатели по времени (рис. 2.4.1.).

Согласно исследованиям генетические алгоритмы имеют трудоемкость в среднем

(nт),

где n - длина хромосомы (то есть количество городов), m - отражает влияние размера популяции и вероятностей генетических операторов. Узким местом генетических алгоритмов является многократное вычисление значения функции приспособленности.

Количество вычислений равняется:

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

Таблица 2.4.4.- Сравнение точности решения задачи коммивояжера с помощью генетических алгоритмов с эффективными методами решения

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

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

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

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

2.5 Развитие генетических алгоритмов в сторону модели с несколькими взаимодействующими популяциями

.5.1 Модель миграции генетических алгоритмов

Генетические алгоритмы применяются и при параллельных вычислениях (parallel implementations).

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