ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА С ИСПОЛЬЗОВАНИЕМ СРЕДСТВ ЯЗЫКА ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ

АННОТАЦИЯ

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

ABSTRACT

An example of the genetic algorithm for solving the traveling salesman problem is considered. The basics of the program that implements the task are described.

Ключевые слова: генетический алгоритм, задача коммивояжера.

Keywords: genetic algorithm, salesman problem.

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

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

Основной (классический) генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

• инициализация, или выбор исходной популяции хромосом;
• оценка приспособленности хромосом в популяции;
• проверка условия остановки алгоритма;
• селекция хромосом;
• применение генетических операторов;
• формирование новой популяции;
• выбор «наилучшей» хромосомы.

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

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

Общая схема алгоритма для реализации задачи коммивояжера:

1. Загрузить в список cityList координаты всех городов либо из XML-файла (процедура openCityListButton_Click), либо ударяя мышкой по графической части формы (процедура tourDiagram_MouseDown), либо комбинируя первое и второе. Номер города – это индекс списка cityList.
2. Найти и запомнить в списке Distances для каждого города расстояния до всех прочих городов (метод CalculateCityDistances класса Cities.)
3. Найти и запомнить в списке CloseCities для каждого города номера его городов-соседей, то есть наиболее близко расположенных к нему городов. Их число равно numberofCloseCities (метод CalculateCityDistances класса Cities и метод FindClosestCities класса City).
4. Сформировать начальную популяцию – список маршрутов, создаваемых на основе жадного алгоритма (метод CreateRandomPopulation класса Population).
5. Рассчитать для каждого маршрута его длину (Fitness).
6. generation = 0 (текущее поколение).
7. Отобрать случайным образом из популяции population несколько (GroupSize) маршрутов и поместить их в рабочую группу – массив tourGroup.
8. Упорядочить tourGroup по возрастанию длины маршрута (применяется метод пузырьковой сортировки).
9. Взять два первых (лучших) маршрута массива tourGroup в качестве родительских и сформировать, используя скрещивание и мутацию, дочерний маршрут child (вероятность мутации задается параметром mutation).
10. Заменить в популяции худший маршрут tourGroup на маршрут child.
11. Вычислить длину маршрута child, и если она меньше длины лучшего маршрута, то признать child в качестве лучшего маршрута. Отобразить новый лучший маршрут в графической части формы (процедура desplayTour). Обновить также и информационные поля формы.
12. generation = generation + 1.
13. Если generation < maxGenerations, то перейти к п. 7 алгоритма, иначе завершить вычисления.

Реализация включает в себя 9 классов: City, Cities, Populatoin, Tour, Tsp, TspEventArgs, Link, TspForms, Program. Каждый класс соответствует определенной задаче алгоритма: City обеспечивает формирование и хранение позиции города; Cities содержит список городов, которые нужно посетить; Population содержит список маршрутов, с которыми работает генетический алгоритм; Tour представляет маршрут по всем городам; Tsp координирует решение задачи коммивояжера; TspEventArgs устанавливает аргументы события foundNewBestTour (найден очередной лучший маршрут), при наступлении которого отображается очередной лучший маршрут; Link обеспечивает связь маршрута; TspForm управляет формой приложения; Program предоставляет метод Main для точки входа.

Интерфейс финальной версии проекта получил следующий вид (см. Рис.1):

Рисунок 1. Интерфейс программного приложения

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

1. Отобразить на карте города в виде окружностей, а фрагменты маршрута – в виде отрезков прямых. Стартовый город отображается красным цветом, предпоследний – синим (первый и последний города маршрута совпадают).
2. Задать значения параметров алгоритма.
3. Выбрать XML-файл с координатами городов.
4. Создать список посещаемых городов по данным XML-файла.
5. Добавить на карте город.
6. Очистить список городов и карту.
7. Выводить информационные сообщения.
8. Запускать и останавливать поиск лучшего маршрута.

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