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

 

Часть 2

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

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

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

 

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

[2]

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

class TGeneticGraph

{

Class TWay

{

public Int32[] Way;

public Int32 Length;

}

 

Int32[,] graph;

Int32 Size;

List<TWay> Population;

Int32 TheBestWay = 9999999, PrevoiusWay, TheWrostWay, PreWrost;

Int32 Generation = 0;

Int32[] Path;

}

где

Class TWay

{

public Int32[] Way;

public Int32 Length;

}

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

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

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

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

Int32 TheBestWay = 9999999, TheWrostWay– длинна лучшего и худшего путей. Необходимы для оценки сходимости алгоритма.

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

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

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

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

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

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

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

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

1. Для каждой пары родительских хромосом случайным образом выберем тоску кроссинговера и в качестве номера стартовой вершины в графе возьмем номер отмеченного гена в хромосоме.
2. Сравним частичную стоимость путей, ведущих из текущих вершин в хромосомах-родителях, и выберем из них кратчайший.
3. Если выбранная таким образом вершина графа уже была включена в частичный путь, то нужно взять случайную вершину из числа еще не отмеченных. Присвоить полученной таким образом вершине значение текущей.
4. При преждевременном образовании цикла выбирается другой кратчайший путь.
5. Повторяем шаги 2 и 3 до тех пор, пока не будет построен путь, который может быть предполагаемым гамильтоновым циклом.
6. Конец работы алгоритма.[2]

Селекция

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

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

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

Блок-схема 1

 

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

• Средства разработки: Microsoft Visual C# 2010 Express.
• Язык программирования: C#.
• Программа разработана для платформы Microsoft Windows.
• Для работы требуется наличие Microsoft .NET Framework версии не ниже 4.0.

 

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

1. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М: Физматлит, 2003;
2. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. — 2-е изд. — М: Физматлит, 2006;
3. http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC#.D0.9A.D0.BD.D0.B8.D0.B3.D0.B8