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

Реферат

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

Оглавление

Введение

Часть 1

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

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

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

Часть 2

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

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

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

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

Селекция

Техническое описание программы и руководство пользователя

Технические характеристики

Руководство пользователя

Заключение

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

Введение

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

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

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

генетический алгоритм локальный оптимум

Часть 1

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

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

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

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

Цель генетических алгоритмов состоит в том, чтобы:)     Абстрактно и формально объяснить адаптацию процессов в естественной системе и интеллектуальной исследовательской системе;

b)      Моделировать естественные эволюционные процессы для эффективного решения оптимизационных задач [2].

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

2.      "дробовик" - случайный выбор альтернатив из всей области решений данной задачи;

.        "фокусировки" - реализует случайный выбор допустимых альтернатив из заданной области решений данной задачи;

.        комбинирования - состоит в различных совместных реализациях первых трех принципов.

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

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

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

2.      Двухточечной оператор кроссинговера. В каждой хромосоме выделяются по две точки оператора кроссинговера, и хромосомы обмениваются участками, расположенными между двумя точками разрыва.

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

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

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

.        "Жадный" оператор. На каждом шаге создания дочерней хромосомы происходит частичный выбор локально оптимального значения между генами родительских хромосом [1].

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

.        Одноточечный. Выбирается произвольный ген в родительской хромосоме и меняется местами с рядом стоящим геном.

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

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

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

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

2.      Селекция на основе заданной шкалы. При применении этого метода популяция сортируется на основе заданного критерия. Каждому элементу назначается определенное число, и селекция выполняется согласно этому числу.

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

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

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

 

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

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

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

.        Оптимизация функций

2.      Оптимизация запросов в базах данных

.        Решение задач на графах

.        Настройка и обучение искусственной нейронной сети

.        Задачи компоновки

.        Фолдинг белков

.        Игровые стратегии

.        Моделирование искусственной жизни

.        Теория приближений

.        Распознавание изображений

.        Генерация звуков, изображений

.        Решение задач о покрытиях и разбиениях т др.

Часть 2

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

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

Требуется найти перестановку  из элементов множества  такую, что значение целевой функции равно

Для неполного графа дополнительным ограничением на величину  являются:

 [2]

 

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

class TGeneticGraph

{

Class TWay

{Int32 [] Way;Int32 Length;

}[,] graph;Size;<TWay> Population;TheBestWay = 9999999, PrevoiusWay, TheWrostWay, PreWrost;Generation = 0;[] Path;

}

гдеTWay

{Int32 [] Way;Int32 Length;

}

Класс, представляющий собой хромосому - список узлов, которые посетит коммивояжер и длину его пути.

Int32 [,] graph - матрица смежности данного графа.

Int32 Size - размерность графа.

List<TWay> Population - популяция возможных маршрутов коммивояжера, список хромосом.

Int32 TheBestWay = 9999999, TheWrostWay - длина лучшего и худшего путей. Необходимы для оценки сходимости алгоритма.[] Path - лучший из предложенных маршрутов. Данный маршрут ранится отдельно, так как с ним могут проводится операции мутации, несмотря на то, что этот маршрут будет являться глобальным оптимумом.

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

 

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

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

Для обеспечение выполнения заданных условий используется структура SortedSet<Int32>, доступная пользователям платформы Microsoft.net Framework. Контроль за реальным существованием сгенерированного пути в графе не важен, так как нежизнеспособные особи будут преобразованы и устранены в ходе выполнения алгоритма.

 

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

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

"Жадный" алгоритма кроссинговера:

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

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

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

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

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

.        Конец работы алгоритма [2].

 

Селекция

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

На блок-схеме 1 наглядно представлен общий ход алгоритма и взаимодействие всех вышеперечисленных операторов.

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

Блок-схема 1

 

Техническое описание программы и руководство пользователя

Технические характеристики

•        Средства разработки: Microsoft Visual C# 2010 Express.

•        Язык программирования: C#.

•        Программа разработана для платформы Microsoft Windows.

•        Для работы требуется наличие Microsoft.net Framework версии не ниже 4.0.

•        При работе программы используются текстовые файлы

 

Руководство пользователя

При запуске программы пользователь увидит окно, показанное на рисунке 1.

Рисунок 1 (пустых скриншотов быть не должно)

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

·        Размерность графа (количество вершин);

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

Кроме того пользователь может выбрать один из уже заданных графов.

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

Рисунок 2

Заключение

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

Кроме обзора генетических алгоритмов был представлен пример их применения - решение задачи коммивояжера. Но данная работа оставляет открытым вопрос использования данного метода в более сложных и интересных областях, таких как системы принятия решения и прогнозирования, системы моделирования и др.

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

1.      Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. - М: Физматлит, 2014.

2.      Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: Учебное пособие. - 2-е изд. - М: Физматлит, 2006.

.        Фленов М.Е. Библия C# - 2-е издание. - Спб.: БХВ-Петербург, 2011.

.        Генетический алгоритм. [Online]: http://ru. wikipedia.org/wiki/Генетический_алгоритм, 2012 г.

5.      Справочная служба Microsoft [Online]: http://msdn. microsoft.com/ru-RU/aa570318 <http://msdn.microsoft.com/ru-RU/aa570318>, 2012 г (писать конкретнее).