Хромосома (генетический алгоритм)

В генетических алгоритмах , хромосома (также иногда называется генотипом ) представляет собой набор параметров , которые определяют планируемое решение проблемы , что генетический алгоритм пытается решить. Набор всех решений известен как популяция . ^[1] Хромосома часто представляется в виде двоичной строки , хотя также используется множество других структур данных .

Хромосомный дизайн [ править ]

Конструкция хромосомы и ее параметры по необходимости зависят от решаемой проблемы. Традиционно хромосомы представлены в двоичном формате в виде строк из нулей и единиц, однако возможны и другие кодировки; ^{[2] можно использовать} практически любое представление, которое позволяет представить решение в виде строки конечной длины. ^[3] Нахождение подходящего представления проблемной области для хромосомы является важным соображением, поскольку хорошее представление облегчит поиск, ограничив пространство поиска; аналогично, более плохое представление позволит расширить пространство поиска. ^[4] мутация оператор и кроссовер Оператор, используемый генетическим алгоритмом, также должен учитывать дизайн хромосомы.

Пример 1: двоичное представление [ править ]

Предположим, проблема состоит в том, чтобы найти целое число от 0 до 255, которое обеспечивает максимальный результат для . Возможные решения этой проблемы - это целые числа от 0 до 255, которые могут быть представлены в виде 8-значных двоичных строк. Таким образом, мы можем использовать 8-значную двоичную строку в качестве нашей хромосомы. Если данная хромосома в популяции представляет собой значение 155, ее хромосома будет иметь значение .${\ displaystyle x}$${\ Displaystyle е (х) = х ^ {2}}$10011011

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

Пример 2: строковое представление [ править ]

Более реальная проблема, которую мы могли бы решить, - это проблема коммивояжера . В этой задаче мы ищем упорядоченный список городов, который обеспечивает самый короткий путь для продавца. Предположим, есть шесть городов, которые мы назовем A, B, C, D, E и F. Хорошим дизайном для нашей хромосомы может быть упорядоченный список, который мы хотим попробовать. Примером хромосомы, с которым мы можем столкнуться в популяции, может быть DFABEC.

Отбор, кроссовер и мутация [ править ]

В каждом поколении генетического алгоритма две родительские хромосомы выбираются на основе их значений пригодности; эти хромосомы используются операторами мутации и кроссовера для создания двух хромосом потомства для новой популяции. ^[3]

Ссылки [ править ]