Статья опубликована в рамках: Научного журнала «Студенческий» № 10(96)
Рубрика журнала: Технические науки
Секция: Моделирование
Скачать книгу(-и): скачать журнал часть 1, скачать журнал часть 2
ТЕСТИРОВАНИЕ ПРОГРАММЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОЙ УПАКОВКИ В ПОЛУБЕСКОНЕЧНЫЙ КОНТЕЙНЕР С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА
Введение
При изучении разнообразных систем и процессов исследователи встречают проблему сложности реализации задачи с помощью некоторых методов. В связи с трудоемкостью, реализация становится не оптимальной во временных ресурсах. Часто это случается из-за использования «нечетких» методов достижения результата. В данной статье представлены причины и численные результаты эксперимента, с использованием «нечеткого» метода ортогональной сортировки объектов в полубесконечный контейнер.
Метод
В ходе работы был разработан генетический алгоритм упаковки прямоугольников в полу бесконечный контейнер путем подбора с выделением наилучших особей. Хромосома представлена координатой левого нижнего угла прямоугольника и его высотой, и шириной.
public class Box//Хромосома, ящик
{
int i;//Номер хромосомы
public int w,h;//Длина, ширина
public int x0, y0;//Координаты левого нижнего угла
}
В ходе упаковки ящики сначала располагаются хаотично, не нарушая правил пересечения объектов в пространстве. Далее путем многочисленных итераций происходят операции пересечения, смещения, переворачивания прямоугольников. Инициатором возникновения операций является случайность, прямоугольники для операций выбираются так же случайно.
int Angle = rnd.Next(0, 9);//Случайным номер мутации
switch (Angle)
{
case 0://Слева от соседа
{
newX0 = chromo[NeirChormo].x0 + chromo[NeirChormo].w + 1;
newY0 = chromo[NeirChormo].y0;
break;
}
case 1://Сверху от соседа
{
newX0 = chromo[NeirChormo].x0;
newY0 = chromo[NeirChormo].y0 + chromo[NeirChormo].h + 1;
break;
}
case 2://Справа от соседа
{
newX0 = chromo[NeirChormo].x0-chromo[RandomChormo].w-1;
newY0 = chromo[NeirChormo].y0;
break;
}
case 3://Сверху от соседа, но правее
{
newX0 = chromo[NeirChormo].x0+ chromo[NeirChormo].w-chromo[RandomChormo].w;
newY0 = chromo[NeirChormo].y0+chromo[NeirChormo].h+1;
break;
}
case 4://Левый угол упаковки
{
newX0 = 0+W- chromo[RandomChormo].w-1;
newY0 = 0+1;
break;
}
case 5://Сдвиг по вертикали к ящику
{
newX0 = chromo[RandomChormo].x0;
newY0 = chromo[NeirChormo].y0+ chromo[NeirChormo].h+1;
break;
}
case 6://Поворот на 90 градусов
{
newX0 = chromo[RandomChormo].x0;
newY0 = chromo[RandomChormo].y0;
newW = chromo[RandomChormo].h;
newH = chromo[RandomChormo].w;
break;
}
case 7://Перестановка ящиков
{
if (RandomChormo != NeirChormo) ReplaceChromo(RandomChormo, NeirChormo);
return;
}
case 8://Радикальная мутация
{
GenerateXYBoxes2(ref chromo, W);
return;
}
После выполнения каждой итерации выявляются наиболее сильные особи, по которым можно отслеживать прогресс выполнения генетического алгоритма. Наилучший результат достигается путем многочисленных итераций
Рисунок 1. Описание работы программы
Тестирование
Тестирование проходило на примерах предложенных O.Berkey и P. Wang [1], а так же задачи классов С7 – С8, предложенные S. Martello и D. Vigo [2]. Число объектов в каждой задаче 20 – 100. Для тестирования были выставлены следующие параметры: число особей 15, количество итераций 10 000.
Задачи решались с помощью разработанного прикладного программного решения Gen_Pack, основанного на алгоритмах, освещенных выше и «координатном» способе кодирования хромосом [3]. Для оценки качества сортировки размещения прямоугольников использовалось отклонение от нижней границы решения задач, которое рассчитывается по формуле, % 
, где L0 – теоретически нижняя граница решения задачи. Чем плотнее расположение объектов, тем меньше.
Таблица 1.
Результаты тестирования
|
Класс задач |
Теоретически нижняя граница L0 |
Среднее решение L |
|
|
C1 |
187,18 |
198,38 |
5,64 |
|
C2 |
60,52 |
74,42 |
18,67 |
|
C3 |
504,12 |
582,54 |
13,46 |
|
C4 |
193,50 |
250,48 |
22,74 |
|
C5 |
1613,16 |
1799,86 |
10,37 |
|
C6 |
506,40 |
677,06 |
25,20 |
|
C7 |
1577,82 |
1687,58 |
6,50 |
|
C8 |
3343,10 |
1629.2 |
14,19 |
, %
Рассматривая результаты, наблюдается тенденция ухудшения результатов в связи с увеличением объектов и увеличением возможных вариантов и исходов для них, что отдаляет оптимальный результат, при использовании данного метода сортировки.
Так же на результаты сильно влияет количество особей при исполнении генетического лагоритма. Большее количество особей обеспечивает большую вариативность путей эволюции.
Таблица 2.
Зависимость результатов от количества особей
|
Номер задачи |
Кол-во объектов |
Высота полученной конструкции |
||
|
1 особь, N1 |
10 особей, N10 |
15 особей, N15 |
||
|
1.1 |
20 |
101 |
70 |
69 |
|
1.2 |
20 |
69 |
51 |
49 |
|
1.3 |
20 |
100 |
74 |
74 |
|
1.4 |
20 |
68 |
53 |
52 |
|
1.5 |
20 |
73 |
59 |
58 |
|
1.6 |
20 |
99 |
86 |
86 |
|
1.7 |
20 |
87 |
58 |
58 |
|
1.8 |
20 |
78 |
59 |
58 |
|
1.9 |
20 |
83 |
69 |
68 |
|
1.10 |
20 |
89 |
77 |
77 |
|
1.11 |
40 |
137 |
104 |
102 |
|
1.12 |
40 |
149 |
120 |
119 |
|
1.13 |
40 |
167 |
155 |
152 |
|
1.14 |
40 |
154 |
143 |
141 |
|
1.15 |
40 |
158 |
149 |
148 |
|
1.16 |
40 |
133 |
123 |
119 |
|
1.17 |
40 |
128 |
120 |
119 |
|
1.18 |
40 |
191 |
162 |
162 |
|
1.19 |
40 |
131 |
116 |
114 |
|
1.20 |
40 |
144 |
120 |
116 |
|
Сумма: |
2339 |
1968 |
1941 |
|
Таблица 3.
Процентное соотношение
|
N1, % |
N10, % |
N15, % |
|
100 |
84,13 |
82,98 |
Вывод
Эвристические методы имеют ограниченный набор возможных вариантов действий алгоритма, направленных на достижение определенного результата. А представленный в данной статье «неточный» метод так же имеет ограниченный набор действий, но они не имеют цели улучшить результат или достичь определенных границ, тем самым при каждой итерации увеличивая «энтропию» в отношении принятие «положительного» действия, а механизмом улучшения результата является механизм отсеивания результата.
Список литературы:
- Berkey O., Wang P. Two-dimensional finite bin-packing algorithms // Journal of the Operational Research Society. 1987. Vol. 38, №. 5. P. 423-429.
- Martello S., Vigo D. Exact colution of the two-dimensional finite bin packing problem // Management Science. 1998. Vol. 4. P. 388-399.
- Горюнов А.Д. «Кодирование хромосом» // Студенческий: электрон. Научн. Журн. 2020. № 2(88). URL: https://sibac.info/journal/student/88/166583.
Оставить комментарий