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

При разработке программы для решения задач упаковки прямоугольников в полубесконечный контейнер с использованием генетического алгоритма (ГА) можно прибегнуть к использованию разных вариантов кодирования хромосом (двоичное представление хромосом, код Грея, логарифмическое кодирование, вещественное кодирование) [1], построения классов и их связей друг с другом.

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

Схема 1. UML – схема структуры программы

Основным классом всей структуры является Коробка (Box). В этом классе используется принцип координатного кодирования [1]. В экземпляре класса хранится координаты левого нижнего угла ящика, а также остальные основные геометрические параметры – высота и ширина. С помощью этих данных можно полностью воссоздать размеры ящика и его положение в полубесконечном контейнере, что поможет в дальнейшем для определения пересечения с другими ящиками или контейнером. Среди функций этого класса – это:

• Конструктор
• CrossBox – функция проверки на пресечение ящиком между собой
• NotCrossBorder - функция проверки на пресечение ящиков с контейнером

Далее класс Индивид (Individ), который агрегирует массив класса Коробка (Box). Этот класс группирует ящики и описывает их количество и номер индивида в популяции. К функциям данного класса относятся:

• Конструктор
• MaxHeight – функция для определения максимальной ординаты верхнего угла ящика
• MaxWidth – функция для определения наибольшей абсцисс правого угла ящиков
• SquareBoxes – функция для определения суммарной площади ящиков
• SurvivalFunction – функция выживаемости, с помощью которой можно найти наиболее приспособленную особь
• Eqv – функция сравнения особей по их приспособленности
• Mutation – функция, содержащая в себе набор мутаций
• ReplaceChromo – функция обмена местами двух хромосом

Класс Форма (Form) объединяет массив индивидов в популяцию. Он необходим в первую очередь для представления результатов в письменном и графическом виде. В данном классе хранится экземпляр класса ящик, для скрещивания и перестановок прямоугольников, число индивидов, число хромосом в индивиде, координаты левого нижнего угла контейнера. К функциям класса Форма (Form) относятся:

• Конструктор
• LoadFromFile – функция, осуществляющая загрузку из файла всей начальной информации о ящиках, ширине контейнера
• GenerateXYBoxes – функция для создания начальной популяции
• GenerateXYBoxes2 – функция для генерации следующей популяции
• SortPopulation – функция для сортировки полученной популяции от лучшей особи к худшей
• CrossOver – функция скрещивания двух особей (кроссинговер)
• NextPopulation – функция для генерации следующего поколения
• ShowIndivid – функция отрисовки особи
• ShowConteiner – функция отрисовки контейнера

Вывод

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

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

1. Горюнов А.Д. КОДИРОВАНИЕ ХРОМОСОМ // Студенческий: электрон. научн. журн. 2020. № 2(88). URL: https://sibac.info/journal/student/88/166583 (дата обращения: 19.03.2020).