Применение генетического алгоритма для решения задачи коммивояжера

РОССИЙСКАЯ  ФЕДЕРАЦИЯ

МИНЕСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Институт  математики, естественных наук

и информационных технологий

Кафедра программного обеспечения

 

КУРСОВАЯ  РАБОТА

ПРИМЕНЕНИЕ  ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ  РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

 

 

Выполнил:

Студент 114 группы

Егоров Ю. А.

Проверил:

Научный руководитель

к. т. н., доцент

Воробьева Марина Сергеевна

 

 

 

 

 

 

 

 

 

 

 

 

 

Тюмень  - 2012 

Оглавление

Введение 3

Часть 1 5

Основные понятия 5

Основные этапы работы генетического алгоритма 7

Область применения генетических алгоритмов 10

Часть 2 12

Постановка задачи 12

Структура данных 12

Генерация первоначальной популяции 13

Кроссинговер 14

Селекция 14

Технические характеристики программы 17

Список литературы 18

 

  

Введение

Идея применения генетических алгоритмов была позаимствована из природы. Именно природе удалось создать  самоорганизующуюся и самобалансирующуюся  сложную систему, работающую на основе механизма эволюции. Но каким образом  природа выбирает нужное направление  эволюции? Почему и каким образом  природа экономно использует свои ресурсы? Как ей удается создавать устойчивые форму жизни? Как природе удалось создать порядок из хаоса? [1] Эти вопросы интересовали не только биологов, но и других ученых и инженеров, которые занимаются моделированием сложных интеллектуальных систем, так как понимание механизма эволюции, возможно, поможет совершить прорыв в создании сложных устойчивых структур, позволяющих решать многие проблемы. Впоследствии из этого интереса сформировалась целая теория эволюционного моделирования и методов его реализации. Одним из таких методов являются генетические алгоритмы.

Считается, что первые работы над генетическими алгоритмами  начали проводится в 1954 г. Нильсом Баричелли в Институте Продвинутых Исследований Принстонского университета. В последующие два десятилетия работы над генетическими алгоритмами носили чисто экспериментальный характер. Интерес к генетическим алгоритмам резво возрос в 70-х гг. XX в. после того как группе инженеров под руководством Инго Рехенберга удалось решить сложные инженерные задачи, опираясь на эволюционные методы. Несколькими годами позже вышел один из первых серьезны трудов по генетическим алгоритмам, написанный Джоном Холландом («Адаптация в естественных и искусственных системах», 1975 г.). В 1980-х. гг. стали продаваться первые коммерческие программные продукты (набор вычислительных средств), использующие генетические алгоритмы. [3]

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

Часть 1

Основные понятия

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

Генетический алгоритм (ГА) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Другими словами, генетический алгоритм представляет собой адаптивный поисковый метод, который основан на селекции лучших элементов в популяции, подобно эволюционной теории Ч. Дарвина.[2]

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

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

1. Абстрактно и формально объяснить адаптацию процессов в естественной системе и интеллектуальной исследовательской системе;
2. Моделировать естественные эволюционные процессы для эффективного решения оптимизационных задач.[2]

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

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

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

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

Хромосома – некоторый конечный вектор размерности , состоящий из генов – элементов хромосом.[2]

Каждый ген в хромосоме  имеет свою позицию – локус. Функциональное назначение гена называется аллель.

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

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

Поколение – генерация, или  процесс реализация одной итерации алгоритма.[1]

Генотип (набор хромосом) каждой особи популяции описывает  фенотип – его внешнее проявление. Фенотип каждого элемента оценивается при помощи «функции приспособленности», (fitness function). Эта функция используется для сравнения альтернативных решений между собой и выбора лучших. Отсюда следует, что основная задача генетических алгоритмов состоит в оптимизации целевой функции.[1]

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

Основные этапы  работы генетического алгоритма

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

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

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

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

Размножение (скрещивание). Генетический алгоритм предполагает два способа размножения: половое и бесполое. Бесполое размножение – самокопирование особи, которое может применяться, например, при недостаточном количестве элементов в множестве особей. Половое размножение в ГА обычно происходит между двумя особями, но допустимо использование большего количества объектов. Главное требование к размножению – чтобы потоки имели возможность унаследовать признаки от своих родителей. Основные методы кроссинговера:

1. Простой (одноточечный). Перед началом работы оператора выбирается точка оператора кроссинговера, или разрывающая точка, которая обычно определяется случайно. затем генерируется новы потомок, состоящий из двух блоков родительских генов.
2. Двухточечной оператор кроссинговера. В каждой хромосоме выделяются по две точки оператора кроссинговера, и хромосомы обмениваются участками, расположенными между двумя точками разрыва.
3. Упорядоченный оператор. Случайным образом выбирается разрывающая точка в одной из родительской хромосом. Затем блок генов, расположенный до точки разрыва копируется в новую хромосому. Остальные позиции в дочерней хромосоме дополняются генами из второй хромосомы в упорядоченном виде слева направо (берутся гены, которые еще не вошли в генотип дочерней хромосомы).
4. Циклический оператор. Он выполняет рекомбинации согласно циклам, которые существуют при установлении соответствия между генами первого и второго родителей.
5. Универсальный оператор кроссинговера. Широко применяется в решении задач из теории расписаний. Вместо разрезающей точки в универсальном операторе кроссинговера используется двоичная маска, длина которой равна длине заданных хромосом. Потомки получаются путем сложения в двоичной арифметике родительской хромосомы с маской.
6. «Жадный» оператор. На каждом шаге создания дочерней хромосомы происходит частичный выбор локально оптимального значения между генами родительских хромосом.[1]

Мутации. Проведение преобразований над генотипом одной особи. К основным операторам мутации относят:

1. Одноточечный. Выбирается произвольный ген в родительской хромосоме и меняется местами с рядом стоящим геном.
2. Двухточечная мутация. Выбираются две точки разреза в гене, затем производится перестановка генов между собой, расположенных справа от точек разреза.
3. Обмен строительных блоков (многоточечный оператор). Строительные блоки – тесно связанные между собой гены, которые нежелательно изменять при выполнении генетических операторов. Когда строительные блоки между точками разреза одинаковы, многоточечный оператор выполняется следующим образом: при четном числе точек разреза, меняются местами гены, расположенные справа и слева от выбранных точек, при нечетном – происходит обмен участками хромосом, расположенными между четными точками разреза.[1]

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

1. Селекция на основе рулетки – простой и широко используемый метод. При его реализации каждому элементу в популяции соответствует зона на колесе рулетки, пропорционально соразмеренная с величиной целевой функции. При этом каждый элемент имеет вероятность выбора для селекции.
2. Селекция на основе заданной шкалы. При применении этого метода популяция сортируется на основе заданного критерия. Каждому элементу назначается определенное число, и селекция выполняется согласно этому числу.
3. Элитная селекция. В этом случае выбираются лучшие (элитные) элементы, и преобразования происходят уже над ними. Этот процесс повторяется каждое поколение до тех пор, пока будут появляться новые элитные элементы.
4. Турнирная селекция. Некоторое число элементов выбирается случайно, и лучшие элементы в выбранной группе выбираются для дальнейшего эволюционного поиска.

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

Область применения генетических алгоритмов

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

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

1. Оптимизация функций
2. Оптимизация запросов в базах данных
3. Решение задач на графах
4. Настройка и обучение искусственной нейронной сети
5. Задачи компоновки
6. Составление расписаний
7. Фолдинг белков
8. Игровые стратегии
9. Моделирование искусственной жизни
10. Теория приближений
11. Распознавание изображений
12. Генерация звуков, изображений
13. Решение задач о покрытиях и разбиениях т др.