методов: метод ветвей и границ и метод генетических алгоритмов.
Задача коммивояжёра есть NP-полная задача. Часто на ней проводят обкатку
новых подходов к эвристическому сокращению полного перебора.
В основе метода ветвей и границ лежит простое наблюдение, что если нижняя
граница для подобласти A дерева поиска больше, чем верхняя граница
какой-либо ранее просмотренной подобласти B, то A может быть исключена из
дальнейшего рассмотрения. Это обычно выполняется с помощью глобальной
переменной m, в которой запоминается минимальная верхняя граница,
полученная для всех просмотренных до настоящего времени вариантах; любая
вершина дерева поиска, нижняя граница которой больше m, может быть
исключена из дальнейшего рассмотрения.
В следующем разделе мы перейдём к рассмотрению генетических алгоритмов.
2. Генетические алгоритмы. Общее описание. Математический аппарат.
Генетические алгоритмы предназначены для решения задач оптимизации.
Примером подобной задачи может служить обучение нейросети, то есть подбора
таких значений весов, при которых достигается минимальная ошибка. При этом
в основе генетического алгоритма лежит метод случайного поиска. Основным
недостатком случайного поиска является то, что нам неизвестно, сколько
понадобится времени для решения задачи. Для того чтобы избежать таких
расходов времени при решении задачи, применяются методы, проявившиеся в
биологии. При этом используются методы открытые при изучении эволюции и
происхождения видов. Как известно, в процессе эволюции выживают наиболее
приспособленные особи. Это приводит к тому, что приспособленность
популяции возрастает, позволяя ей лучше выживать в изменяющихся условиях.
Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John
Holland) в Мичиганском университете. Он получил название «репродуктивный
план Холланда» и лег в основу практически всех вариантов генетических
алгоритмов. Однако, перед тем как мы его рассмотрим подробнее, необходимо
остановится на том, каким образом объекты реального мира могут быть
закодированы для использования в генетических алгоритмах.
Представление объектов.
Из биологии мы знаем, что любой организм может быть представлен своим
фенотипом, который фактически определяет, чем является объект в реальном
мире, и генотипом, который содержит всю информацию об объекте на уровне
хромосомного набора. При этом каждый ген, то есть элемент информации
генотипа, имеет свое отражение в фенотипе. Таким образом, для решения
задач нам необходимо представить каждый признак объекта в форме,
подходящей для использования в генетическом алгоритме. Все дальнейшее
функционирование механизмов генетического алгоритма производится на уровне
генотипа, позволяя обойтись без информации о внутренней структуре объекта,
что и обуславливает его широкое применение в самых разных задачах.
В наиболее часто встречающейся разновидности генетического алгоритма для
представления генотипа объекта применяются битовые строки. При этом
каждому атрибуту объекта в фенотипе соответствует один ген в генотипе
объекта. Ген представляет собой битовую строку, чаще всего фиксированной
длины, которая представляет собой значение этого признака.
Кодирование признаков, представленных целыми числами
Для кодирования таких признаков можно использовать самый простой вариант -
битовое значение этого признака. Тогда нам будет весьма просто
использовать ген определенной длины, достаточной для представления всех
возможных значений такого признака. Но, к сожалению, такое кодирование не
лишено недостатков. Основной недостаток заключается в том, что соседние
числа отличаются в значениях нескольких битов, так например числа 7 и 8 в
битовом представлении различаются в 4-х позициях, что затрудняет
функционирование генетического алгоритма и увеличивает время, необходимое
для его сходимости. Для того, чтобы избежать эту проблему лучше
использовать кодирование, при котором соседние числа отличаются меньшим
количеством позиций, в идеале значением одного бита. Таким кодом является
код Грея, который целесообразно использовать в реализации генетического
алгоритма. Значения кодов Грея рассмотрены в таблице ниже:
+---------------------------------------------------------------------------------------+
| Двоичное кодирование | Кодирование по коду Грея |
|-------------------------------------------+-------------------------------------------|
| Десятичный | Двоичное | Шестнадцатеричное | Десятичный | Двоичное | Шестнадцатеричное |
| код | значение | значение | код | значение | значение |
|------------+----------+-------------------+------------+----------+-------------------|
| 0 | 0000 | 0h | 0 | 0000 | 0h |
|------------+----------+-------------------+------------+----------+-------------------|
| 1 | 0001 | 1h | 1 | 0001 | 1h |
|------------+----------+-------------------+------------+----------+-------------------|
| 2 | 0010 | 2h | 3 | 0011 | 3h |
|------------+----------+-------------------+------------+----------+-------------------|
| 3 | 0011 | 3h | 2 | 0010 | 2h |
|------------+----------+-------------------+------------+----------+-------------------|
| 4 | 0100 | 4h | 6 | 0110 | 6h |
|------------+----------+-------------------+------------+----------+-------------------|
| 5 | 0101 | 5h | 7 | 0111 | 7h |
|------------+----------+-------------------+------------+----------+-------------------|
| 6 | 0110 | 6h | 5 | 0101 | 5h |
|------------+----------+-------------------+------------+----------+-------------------|
| 7 | 0111 | 7h | 4 | 0100 | 4h |
|------------+----------+-------------------+------------+----------+-------------------|
| 8 | 1000 | 8h | 12 | 1100 | Ch |
|------------+----------+-------------------+------------+----------+-------------------|
| 9 | 1001 | 9h | 13 | 1101 | Dh |
|------------+----------+-------------------+------------+----------+-------------------|
| 10 | 1010 | Ah | 15 | 1111 | Fh |
|------------+----------+-------------------+------------+----------+-------------------|
| 11 | 1011 | Bh | 14 | 1110 | Eh |
|------------+----------+-------------------+------------+----------+-------------------|
| 12 | 1100 | Ch | 10 | 1010 | Ah |
|------------+----------+-------------------+------------+----------+-------------------|
| 13 | 1101 | Dh | 11 | 1011 | Bh |
|------------+----------+-------------------+------------+----------+-------------------|
| 14 | 1110 | Eh | 9 | 1001 | 9h |
|------------+----------+-------------------+------------+----------+-------------------|
| 15 | 1111 | Fh | 8 | 1000 | 8h |
+---------------------------------------------------------------------------------------+
Таблица 1. Соответствие десятичных кодов и кодов Грея.
Таким образом, при кодировании целочисленного признака мы разбиваем его на
тетрады и каждую тетраду преобразуем по коду Грея.
В практических реализациях генетических алгоритмов обычно не возникает
необходимости преобразовывать значения признака в значение гена. На
практике имеет место обратная задача, когда по значению гена необходимо
определить значение соответствующего ему признака.
Таким образом, задача декодирования значения генов, которым соответствуют
целочисленные признаки, тривиальна.
Кодирование признаков, которым соответствуют числа с плавающей точкой
Самый простой способ кодирования, который лежит на поверхности -
использовать битовое представление. Хотя такой вариант имеет те же
недостатки, что и для целых чисел. Поэтому на практике обычно применяют
следующую последовательность действий:
1. Разбивают весь интервал допустимых значений признака на участки с
требуемой точностью.
2. Принимают значение гена как целочисленное число, определяющее номер
интервала (используя код Грея).
3. В качестве значения параметра принимают число, являющиеся серединой
этого интервала.
Рассмотрим вышеописанную последовательность действий на примере:
Допустим, что значения признака лежат в интервале [0,1]. При кодировании
использовалось разбиение участка на 256 интервалов. Для кодирования их
номера нам потребуется таким образом 8 бит. Допустим значение гена:
00100101bG (заглавная буква G показывает, что используется кодирование по
коду Грея). Для начала, используя код Грея, найдем соответствующий ему
номер интервала: 0x01 graphic
. Теперь посмотрим, какой интервал ему соответствует… После несложных
подсчетов получаем интервал 0x01 graphic
. Значит значение нашего параметра будет 0x01 graphic
.
Основные генетические операторы
Как известно в теории эволюции важную роль играет то, каким образом
признаки родителей передаются потомкам. В генетических алгоритмах за
передачу признаков родителей потомкам отвечает оператор, который
называется скрещивание (его также называют кроссовер или кроссинговер).
Этот оператор определяет передачу признаков родителей потомкам. Действует
