РАЗРАБОТКА ОПЕРАТОРОВ СКРЕЩИВАНИЯ И МУТАЦИИ ДЛЯ ПРИМЕНЕНИЯ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ К РЕШЕНИЮ ЗАДАЧИ КОММИВОЯЖЕРА

Санников М. А.

Студент,

Томский политехнический университет

РАЗРАБОТКА ОПЕРАТОРОВ СКРЕЩИВАНИЯ И МУТАЦИИ ДЛЯ ПРИМЕНЕНИЯ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ К РЕШЕНИЮ ЗАДАЧИ КОММИВОЯЖЕРА

Аннотация

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

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

Sannikov M. A.

Student,

Tomsk polytechnic university

DEVELOPMENT OF CROSSOVER AND MUTATION OPERATORS FOR TRAVELLING SALESMAN PROBLEM SOLVING USING EVOLUTIONARY ALGORITHM

Abstract

The article contains description of main parts of evolutionary algorithms, native crossover and mutation operators and some its modification for travelling salesman problem solving provided

Keywords: evolutionary algorithm, travelling salesman problem, crossover operator, mutations.

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

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

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

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

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

Литература

1. Генетические алгоритмы и не только [Электронный ресурс] – Режим доступа: свободный, http://www.qai.narod.ru/ – Дата обращения 22.11.2014.
2. Искусственный интеллект [Электронный ресурс] – Режим доступа: свободный, http://www.gotai.net/ – Дата обращения 01.12.2014.
3. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А., Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности, Харьков, ОСНОВА, 1997. – 112с.
4. Holland J. H. Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence.— London: Bradford book edition, 1994 —211 p.
5. De Jong K.A. An analysis of the behavior of a class of genetic adaptive systems. Unpublished PhD thesis. University of Michigan, Ann Arbor, 1975. (Also University Microfilms No. 76-9381).

References

1. Geneticheskie algoritmy i ne tol'ko [Jelektronnyj resurs] – Rezhim dostupa: svobodnyj, http://www.qai.narod.ru/ – Data obrashhenija 22.11.2014.
2. Iskusstvennyj intellekt [Jelektronnyj resurs] – Rezhim dostupa: svobodnyj, http://www.gotai.net/ – Data obrashhenija 01.12.2014.
3. Voronovskij G.K., Mahotilo K.V., Petrashev S.N., Sergeev S.A., Geneticheskie algoritmy, iskusstvennye nejronnye seti i problemy virtual'noj real'nosti, Har'kov, OSNOVA, 1997. – 112s.
4. Holland J. H. Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence.— London: Bradford book edition, 1994 —211 p.
5. De Jong K.A. An analysis of the behavior of a class of genetic adaptive systems. Unpublished PhD thesis. University of Michigan, Ann Arbor, 1975. (Also University Microfilms No. 76-9381).