Пояснения к задаче.
Постановка задачи
выглядит следующим образом (1):
, (1)
Где
– ширина i -го прямоугольника,
– высота i -го прямоугольника,
W – длина полосы, на которой осуществляется упаковка (максимальная ширина упаковки),
H – высота полосы, на которой осуществляется упаковка (не ограничена),
- плотность упаковки (целевая функция),
ai – коэффициент, показывающий входит ли i -й прямоугольник в число тех, которые определяют ширину упаковки (1 – если входит, 0 – если нет),
bi – коэффициент, показывающий входит ли i -й прямоугольник в число тех, которые определяют высоту упаковки (1 – если входит, 0 – если нет),
n – число прямоугольников.
Под плотностью упаковки будем понимать величину от 0 до 1, представляющую собой отношение площади, занимаемой прямоугольниками, к общей площади упаковки. При этом высоту упаковки ограничивать не будем, однако для вычисления плотности упаковки будем использовать максимальную высоту, которую заняли прямоугольники.Для вычисления общей площади упаковки в качестве ширины упаковки будем использовать W – ширину полосы.
Имеем следующие константные входные данные:
n – количество прямоугольников (их w, h, isOrient)
W
M – число поколений (число итераций генетического алгоритма) – критерий останова алгоритма;
Варьируемые пользователем входные данные (влияющие на результат):
N – размер популяции (мощность начальной популяции)
Тип декодера
Тип селекции
Тип скрещивания
Kgen – коэффициент формирования нового поколения (сколько особей берем из потомков)
На выходе имеем плотность упаковки.
Кодирование решения задачи двумерной упаковки.
Кодированное решение будет представлять собой вектор, элементы которого будут иметь комбинированный тип. По сути это будет приоритетный список PL вида 
, где n – количество прямоугольников для упаковки. PL – порядок укладки прямоугольников на полосу. То есть первым кладется прямоугольник 
, затем 
, и так далее. Каждый элемент pi хранит параметры прямоугольников:
pi={wi, hi, isOrienti, orienti, xi, yi }
где wi, hi, xi, yi описаны выше (1), а
(2)
isOrienti - true/false – можем ли мы менять ориентацию прямоугольника
orienti – ориентация (горизонтальная или вертикальная)
Отметим, что за координаты прямоугольника будем принимать координаты его нижней левой точки.
Переход от PL к графическому представлению решения (декодирование).
Для вычисления целевой функции и получения графического представления решения задачи упаковки используем декодеры. Это алгоритмы, реализующие способ укладки прямоугольников на основе приоритетного списка. Они помогают вычислить координаты прямоугольников, а значит и целевую функцию.
В качестве примера рассмотрим декодирование приоритетного списка вида {1,2,3,4} двумя видами декодеров.
1. Декодер «Нижний левый» (Bottom Left, BL).
Шаг 1: поместить первый прямоугольник из PL в левый нижний угол полосы.
Шаг i: Последовательно передвинуть прямоугольник i из PL 
, начиная от верхнего правого угла упакованной площади полосы вниз настолько, насколько это возможно, а затем влево, снова вниз, влево, и т.д., до тех пор, пока он не сможет быть сдвинутым влево или вниз. Преимущество здесь имеет движение влево. Пример декодера «Нижний левый» для рассматриваемого примера показан на рис.1.
Рис. 1. Декодер «Нижний левый»
2. Декодер «Усовершенствованный нижний левый» (Improved Bottom Left, IBL).
Данный алгоритм отличается от предыдущего стратегией размещения очередного i -го прямоугольника.
Шаг i: Последовательно передвинуть прямоугольник i из PL, , начиная от верхнего правого угла упакованной площади полосы вниз настолько, насколько это возможно, а затем влево, снова вниз, влево, и т.д., до тех пор, пока он не сможет быть сдвинутым влево или вниз. Причем, передвижение вниз имеет преимущество. Пример декодера «Нижний левый» показан на рис.2
Рис. 2. Декодер «Усовершенствованный нижний левый»
Генетический алгоритм
Блок-схема алгоритма представлена на рис. 3.
Рис. 3. Блок-схема генетического алгоритма
Основными шагами генетического алгоритма являются следующие:
Шаг 1: Формирование начальной популяции (некоторого набора приоритетных списков).
Шаг 2: Декодирование PL, вычисление целевой функции (функции пригодности) для каждого решения.
Шаг 3: Отбор особей для скрещивания (селекция).
Шаг 4: Скрещивание.
Шаг 5: Мутация.
Шаг 6: Формирование нового поколения, переход на шаг 2.
Остановку алгоритма будем совершать если:
- популяция исчерпала свой жизненный цикл, т.е. количество полученных поколений достигло заданного значения М;
- все родительские особи имеют идентичный хромосомный набор;
- родительские особи в k-м поколении равны родительским особям в (k-1)–м поколении.
Селекция
Селекция – оператор случайного выбора одного индивида из популяции для использования его в операторе скрещивания.
Реализовать 3 вида селекции:
1. Пропорциональная селекция. Вероятность выбора элемента пропорциональна значению пригодности индивида. Данный вид селекции нам подходит, поскольку может работать только с неотрицательными значениями пригодности.
2. Ранговая селекция. Работает не с массивом пригодностей напрямую, а с массивом нормированных рангов, присваиваемых индивидам на основе значений пригодности. Используется функция, которая проставляет ранги для элементов несортированного массива пригодностей, то есть номера, начиная с 1, в отсортированном массиве. Если в массиве есть несколько одинаковых элементов, то ранги им присуждаются как среднеарифметические ранги этих элементов в отсортированном массиве. Если это не сделать, то вероятность выбора индивидов одинаковых по функции пригодности будет не равна друг другу, что противоречит идее оператора селекции. Далее для выбора индивидов используется пропорциональная селекция, работающая с массивом рангов.
3. Турнирная селекция. Из популяции с равной вероятностью выбираются индивиды в количестве 𝑇 (размер турнира), где 2≤𝑇≤𝑁. При этом каждый индивид может попасть в группу (турнир) только один раз (турнирная селекция без возращения). Из данной группы выбирается индивид с наибольшей пригодностью. Если при выполнении селекции сравниваются два разных индивида с одинаковыми значениями функций пригодности, то выбирается первый из них. Турнирная селекция является единственным типом данного оператора, который добавляет дополнительный параметр – размер турнира 𝑇. Обычно выбирают значение этого параметра равное двум.
Скрещивание
Скрещивание (кроссовер) – оператор случайного формирования нового индивида из двух выбранных родителей с сохранением признаков обоих родителей.
Реализовать 2 типа скрещивания:
1. Одноточечное скрещивание. Пусть имеется два родителя (два приоритетных списка) PL1 и PL2.
В случайном месте произведем разрыв между двумя позициями генов в обеих хромосомах. После этого перепишем в хромосому потомка первую часть первого родителя. А затем допишем недостающие гены в том порядке, в котором они встречаются у второго родителя. Аналогично получаем и второго потомка. Из них выбирается случайно один потомок, который и передается в качестве результата оператора скрещивания (рис. 4).
Рис.4. Одноточечное скрещивание
2. Двухточечное скрещивание. Пусть имеется два родителя (два приоритетных списка) PL1 и PL2. В двух случайных местах происходят разрывы между двумя позициями генов в обеих хромосомах. После этого перепишем в хромосому первого потомка выбранную в результате разрыва область. Остальные гены заполним в соответствии с тем, как они следуют в хромосоме второго родителя. Аналогично получается второй потомок. Из них выбирается случайно один потомок, который и передается в качестве результата оператора скрещивания (Рис. 5).
Рис.5. Двухточечное скрещивание
Мутация
Мутация – оператор случайного изменения всех потомков из популяции. Цель данного оператора не получить более оптимальное решение, а расширить многообразие рассматриваемых индивидов. Обычно мутация предполагает незначительное изменение потомков.
Мутация выполняется в 2 этапа:
1. Меняем местами прямоугольники в приоритетном списке.
2. У случайно выбранного прямоугольника меняем ориентацию (делать проверку на возможность вращения).
Вероятность мутации выбрать от 2-8%.
!!!Примечание. В результате скрещивания и мутации могут получаться приоритетные списки, не удовлетворяющие нашей задаче (например, будут содержать одинаковые элементы или же не содержать каких-либо элементов). Такие решения надо отбрасывать или корректировать.