Решение задачи коммивояжера

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

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

Г1 Г2 Г3 Г4 Г5

Город 1 0 4 6 2 9

Город 2 4 0 3 2 9

Город 3 6 3 0 5 9

Город 4 2 2 5 0 8

Город 5 9 9 9 8 0

Для решения задачи применим следующий генетический алгоритм. Решение представим в виде перестановки чисел от 1 до 5, отображающей последовательность посещения городов. Значение целевой функции будет равно стоимости всей поездки, вычислений в соответствии с вышеприведенной матрицей. Одним из оптимальных решений задачи является последовательность 12345 стоимостью 29. Из первого города во второй стоимость равна 4 из второго в третий – 3, из третьего в четвертый - 5, из четвертого в пятый – 8, из пятого в пятый - 9. Таким образом, 4+3+5+8+9=29.

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

В качестве оператора скрещивания выберем более изощренную процедуру, похожую на двухточечный оператор скрещивания. Пусть есть две родительские перестановки (1/234/5) и (3/452/1). Случайно и равновероятно выбираются две точки разрыва. Для примера возьмем ситуацию, когда первая точка разрыва находится между первым и вторым элементами перестановки, а вторая точка – между четвертым и пятым: (1/234/5), (3/452/1). На первом этапе перестановки обмениваются фрагментами, заключенными между точками разрыва: (*/452/*), (*/234/*). На втором этапе вместо звездочек вставляются соответствующие числа из исходной родительской перестановки, начиная со второго числа. В данном случае в первой перестановке (1/234/5) таким начальным числом является 3, а за ним идет 4, которое есть в новой перестановке, и мы его пропускаем, также пропускаем число 5, переходим на начало перестановки и выбираем число 1. В итоге вместо (*/452/*) получаем (34521), аналогично из (/3/452/1) и (*/234/*) получаем (52341).

Оператор мутации будет представлять собой случайную перестановку двух чисел в хромосоме, также выбранных случайно по равномерному закону. Например, вероятность мутации равна 0,01. Размер популяции выберем равным 4. Исходная популяция представлена в таблице 5.

Таблица 5

№ строки	Код	Значение целевой функции	Вероятность участия в процессе размножения
			32/122 (0,26)
			32/122
			29/122 (0,23)
			29/122

Пусть для скрещивания были выбраны следующие пары: (1,3) и (2,4). В результате были получены потомки, представленные в таблице 6.

Таблица 6

№ строки	Родители	Потомки	Значение целевой функции для потомков
1 (1)	1|23|45	5|43|12
2 (3)	5|43|12	1|23|54
3 (2)	2|143|5	4|312|5 мутация 13254
4 (4)	4|312|5	2|143|5

Пусть для потомка (12354) сработал оператор мутации, и обменялись местами числа 2 и 3. В данном случае строка (12354) изменилась и приняла значение (13254). Популяция первого поколения после отсечения «худших» особей в результате работы оператора редукции приняла вид, представленный в таблице 7.

Таблица 7

№ строки	Код	Значение целевой функции	Вероятность участия в процессе размножения
			28/111 29/115
			28/111 28/115
			29/111 29/115
			28/111 28/115

Пусть для получения второго поколения были выбраны следующие пары строк: (1, 4) и (2, 3). В результате были получены потомки, показанные в таблице 8.

Таблица 8

№ строки	Родители	Потомки	Значение целевой функции для потомков
	|123|45	|214|35
	|214|35	|123|45
	|21|435	|13|452
	|13|254	|21|354

Популяции второго поколения после отсечения худших особей приняла вид, показанный в таблице 9.

Таблица 9

№ строки	Код	Значение целевой функции	Вероятность участия в процессе размножения
1 (1)			29/114
2 (2)			28/114
3 (3)			29/114
4 (н)			28/114

Таким образом, после двух итераций значение целевой функции для лучшего решения изменилось с 29 на 28, среднее значение изменилось с 30,5 до 28,75, а общее качество с 122 до 114. Наблюдается улучшение популяции.

Задача 1. Провести поиск минимума одномерной функции f(x)= x²-16х +5 с помощью генетических алгоритмов. Описать 2 популяции. Генотип алгоритма представляет собой строку из 5 бит. Размер популяции - 4. Например, строка 01011 соответствует числу х=11, а f(x)= -50. Использовать одноточечный кроссовер. Мутация заключается в инверсии одного из битов строки, выбираемого случайно. Элитизм необходимо использовать.

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

Основой для возникновения генетических алгоритмов послужили модель биологической эволюции и методы случайного поиска. Л. Растригин отмечал, что методы случайный поиск возник как реализация простейшей модели эволюции, когда случайные мутации моделировались случайными шагами оптимального решения, а отбор – «устранением» неудачных вариантов.

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

Цель генетических алгоритмов состоит в том, чтобы:

· абстрактно и формально объяснять адаптацию процессов в естественной системе и интеллектуальной исследовательской системе;

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

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

Генетические алгоритмы отличаются от других оптимизационных и поисковых процедур следующим:

· работают в основном не с параметрами задачи, а с закодированным множеством параметров;

· осуществляют поиск не путем улучшения одного решения, а путем использования сразу нескольких альтернатив на заданном множестве решений;

· используют целевую функцию, а не её различные приращения для оценки качества принятия решений;

· применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.

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

2. Приведем некоторые понятия и определения из теории генетических алгоритмов. Все генетические алгоритмы работают на основании начальной информации, в качестве которой выступает популяция альтернативных решений Р. Популяция Р_t ={ P₁, P_2,…, Р_i,…, Р_Np } есть множество элементов Р_i, t =0,1,2… - номер генерации генетического алгоритма, Np – размер популяции. Каждый элемент Р_i этой популяции, как правило, представляет собой одну или несколько хромосом или особей, или индивидуальностей (альтернативных упорядоченных или неупорядоченных решений). Хромосомы состоят из генов Р_t ={ g₁, g₂,…, g_v } (элементы, части закодированного решения), и позиции генов в хромосоме называются лоции или локус для одной позиции, т.е. ген – подэлемент (элемент в хромосоме), локус – позиция в хромосоме, аллель – функциональное значение гена.

Гены могут иметь числовые или функциональные значения. Обычно эти числовые значения берутся из некоторого алфавита. Генетический материал элементов обычно кодируется на основе двоичного алфавита {0,1}, хотя можно использовать буквенные, а также десятичные и другие алфавиты. Примером закодированной хромосомы длины девять на основе двоичного алфавита может служить хромосома Р_t =(001001101).

Элементы в генетических алгоритмах часто называют родителями. Родители выбираются из популяции на основе заданных правил, а затем смешиваются (скрещиваются) для производства «детей» (потомков). Дети и родители в результате генерации, т.е. одного цикла (подцикла) эволюции, создают новую популяцию. Генерация, то есть процесс реализации одной итерации алгоритма, называется поколением.

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

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

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

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

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

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

3. При решении практических задач с использованием генетических алгоритмов обычно выполняют четыре предварительных этапа:

· выбор способа представления решения;

· разработка операторов случайных изменений;

· определение способов «выживания» решений;

· создание начальной популяции альтернативных решений.

Рассмотрим некоторые особенности выполнения этих этапов.

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

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

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

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

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