КОДИРОВАНИЕ ХРОМОСОМ

Кодирование хромосомы

В классическом варианте ГА используется двоичное представление хромосом. Двоичное кодирование основано на известном способе записи десятичных чисел  в двоичной системе. Однако есть и другие представления.

Рисунок 1. Двоичное представление хромосомы

Код Грея – характеризуется тем, что двоичные последовательности, соответствующие двум последовательным целым числам, отличаются только одним битом. Такой способ кодирования хромосом может оказаться оправданным при использовании операции мутации. [6]

Рисунок 2. Двоичное представление хромосомы

Логарифмическое кодирование – применяется в ГА для уменьшения длины хромосом. Оно используется в задачах многомерной оптимизации с большими пространствами поиска решений.

При логарифмическом кодировании первый бит  кодовой последовательности – это бит знака показательной санкции, второй бит  – бит знака степени этой функции, а остальные биты  представляют значение самой степени:  где  означает десятичное значение числа, закодированного в виде двоичной последовательности . [6]

Вещественное кодирование. Идея использовать в виде хромосомы вектор вещественных значений появилась у исследователей в области ГА при решении задач непрерывной оптимизации. Двоичное представление хромосом влечет за собой определенные трудности при выполнении поиска в непрерывных пространствах, которые связаны с большой размерностью пространства поиска.

Для кодирования признака, принимающего действительные значения в некотором диапазоне, в битовую строку, используется особый метод. Диапазон допустимых значений признака xi разделяют на участки с необходимой точностью. Для преобразования целочисленного значения гена  из множества в вещественное число  из интервала пользуются формулой: где N - количество разрядов для кодирования битовой строки. Традиционно используются значения N = 8; 16; 32. При увеличении N пространство поиска решений расширяется и становится огромным. [7, 8]

Методы кодирования для задач ортогональной упаковки

Прямая схема кодирования. При применении данного метода задается положение всех прямоугольников P_i, i=1,...,n с помощью вектора (x_i;y_i) угла с минимальными координатами. Последовательность векторов представляет прямую схему кодирования.

Кодирование перестановкой треугольников. Список V = (1(V), 2(V),…, i(V),…, n(V)), i(V) – номер прямоугольника, который занимаем в V позицию i. С помощью декодера вычисляют координаты (x_i;y_i) прямоугольника P_i и воссоздают схему упаковки. Длинна зависит от перестановки V и от используемого декодера.

Кодирование блок структурами. Пусть имеется контейнер CN. Проведем через правые стороны прямоугольников вертикальные линии, см. рис. 3.

Рисунок 3. Разделение CN на блоки

Линии разбивают CN на n вертикальных блоков одинаковой ширины и различной длинны х_i. Таким образом мы получаем блочную структуру, где каждому блоку соответствует список номеров прямоугольников, пересекающих указанный блок и длинна х_i. [9]

Координатное кодирование. В задаче ортогональной упаковки ящиков в полу бесконечный контейнер, я разработал и использовал "координатное" кодирование хромосомы. В этом случае в хромосоме хранятся структура данных, которая содержит координаты левого нижнего угла объекта(x, y), номер объекта(i),его ширина и высота(w, h). При данном представлении можно видеть где находится тот или иной ящик введенный в систему, необходимо всего 2 структуры "особь" и "хромосома", которые полностью описывающие структуру решения без дополнительных сущностей, кроме самого контейнера. В особи хранится массив хромосом в произвольной последовательности. Данный способ помогает сохранить объективность результирующего набора хромосом, их точное расположение и, при сохранении хода решения поставленной задачи, путь, который хромосома проделала до наилучшего решения. Так же при данном методе разработки легко учитывается правило «не пересечения» объектов в заданном пространстве.

Выводы

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

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

1. Попов В.А., Бердочник А.В. «Оптимизационные задачи на основе генетического поиска».
2. Д.И. Батищев, Е.А. Неймарк, Н.В. «Старостин Применение генетических алгоритмов к решению задач дискретной оптимизации».
3. Каширина И.Л. Генетический алгоритм решения многокритериальной задачи о назначениях/ И.Л. Каширина, Б.А. Семенов // Информационные технологии. — 2007. — № 5. — С. 62–68.
4. Оптимизация решения задачи ортогональной упаковки объектов [Электронный ресурс] / Чеканин, Чеканин // Прикладная информатика / Journal of Applied Informatics .— 2012 .— №4 .— С. 55-62 .— Режим доступа: https://rucont.ru/efd/453133.
5. Батищев Д.И. Оптимизация нестационарных задач комбинаторного типа с помощью генетических алгоритмов. [Электронный ресурс] / Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. — Режим доступа: http://lvk.cs.msu.su /index.php/articles/153.
6. Методы кодирования хромосом: двоичное, логарифмическое, Грея [Электронный ресурс] — Режим доступа: http://www.aiportal.ru/articles/genetic-algorithms/methods-coding.html.
7. Herrera F., Lozano M., Verdegay J.L. Tackling real-coded genetic algorithms: operators and tools for the behaviour analysis // Artificial Intelligence Review, Vol. 12, No. 4, 1998. - P. 265-319.
8. Michalewicz Z. Genetic Algorithms, Numerical Optimization and Constraints, Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, July 15-19, 1995. - P. 151-158.
9. Филипова А.С. «Конструирование ортогональной упаковки в полубесконечной полосе на базе декодеров блочной структуры» [Научная статья]-Вестник Башкирского университета №3 - 2006