Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: Научного журнала «Студенческий» № 10(96)

Рубрика журнала: Технические науки

Секция: Моделирование

Скачать книгу(-и): скачать журнал часть 1, скачать журнал часть 2

Библиографическое описание:
Горюнов А.Д. ТЕСТИРОВАНИЕ ПРОГРАММЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОЙ УПАКОВКИ В ПОЛУБЕСКОНЕЧНЫЙ КОНТЕЙНЕР С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА // Студенческий: электрон. научн. журн. 2020. № 10(96). URL: https://sibac.info/journal/student/96/172269 (дата обращения: 29.03.2024).

ТЕСТИРОВАНИЕ ПРОГРАММЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОРТОГОНАЛЬНОЙ УПАКОВКИ В ПОЛУБЕСКОНЕЧНЫЙ КОНТЕЙНЕР С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Горюнов Антон Дмитриевич

магистрант группы ИДМ-18-06 кафедра управления и информатики в технических системах Институт информационных систем и технологий Московский государственный технологический университет «СТАНКИН»,

РФ, Москва

Введение

При изучении разнообразных систем и процессов исследователи встречают проблему сложности реализации задачи с помощью некоторых методов. В связи с трудоемкостью, реализация становится не оптимальной во временных ресурсах. Часто это случается из-за использования «нечетких» методов достижения результата. В данной статье представлены причины и численные результаты эксперимента, с использованием «нечеткого» метода ортогональной сортировки объектов в полубесконечный контейнер.

Метод

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

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

 

Вывод

Эвристические методы имеют ограниченный набор возможных вариантов действий алгоритма, направленных на достижение определенного результата. А представленный в данной статье «неточный» метод так же имеет ограниченный набор действий, но они не имеют цели улучшить результат или достичь определенных границ, тем самым при каждой итерации увеличивая «энтропию» в отношении принятие «положительного» действия, а механизмом улучшения результата является механизм отсеивания результата.

 

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

  1. Berkey O., Wang P. Two-dimensional finite bin-packing algorithms // Journal of the Operational Research Society. 1987. Vol. 38, №. 5. P. 423-429.
  2. Martello S., Vigo D. Exact colution of the two-dimensional finite bin packing problem // Management Science. 1998. Vol. 4. P. 388-399.
  3. Горюнов А.Д. «Кодирование хромосом» // Студенческий: электрон. Научн. Журн. 2020. № 2(88). URL: https://sibac.info/journal/student/88/166583.

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.