Телефон: +7 (383)-202-16-86

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

Рубрика журнала: Информационные технологии

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

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

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

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

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

РФ, г. Москва

При разработке программы для решения задач упаковки прямоугольников в полубесконечный контейнер с использованием генетического алгоритма (ГА) можно прибегнуть к использованию разных вариантов кодирования хромосом (двоичное представление хромосом, код Грея, логарифмическое кодирование, вещественное кодирование) [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).

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

Форма обратной связи о взаимодействии с сайтом