Модифицированные эволюционные алгоритмы и программные решения задачи ортогональной упаковки объектов (1095065), страница 3
Текст из файла (страница 3)
Выбор глубины поиска субоптимального решениязадачи осуществляется путем одновременного анализа динамики изменениялучшего найденного решения и динамики изменения популяции решений вцелом. Действия эволюционного алгоритма при попадании популяции решенийв локальный оптимум целевой функции приведены в табл. 1.Таблица 1.Действия эволюционного алгоритма при различных значенияхпараметра останова K( )ПостоянныйпараметрЧисло пройденных эпох после обновленияпопуляцииK2K3KЛучшее решениев текущей популяцииобновлениепопуляцииостановпоиска–––––Лучшее найденноерешение–––––обновлениепопуляцииостановпоискаПроведенныевычислительныеэкспериментыпоказали,чтопредложенный параметр останова поиска имеет следующие особенности:• значение параметра останова не зависит от числа пройденных эпох;• время поиска решения прямо пропорционально значению параметраостанова поиска (см.
рис. 5);• предложенный параметр останова позволяет регулировать глубинупоиска решения однозначным образом.Рассмотрены и исследованы следующие эволюционные алгоритмы:алгоритм отжига, генетический алгоритм, а также комбинированный131.2010.6010.5010.4010.3010.2010.1010.009.901.000.800.600.400.200.00Среднее значениецелевой функцииВремя решения, сгенетический алгоритм.
Выбраны параметры эволюционных алгоритмов,обеспечивающие их эффективную работу. Вероятность выполнения операторакроссинговера выбрана равной 0.9, инверсии – 0.7, мутации – 0.1. Проведенныеисследования показали, что среди рассмотренных эволюционных алгоритмовнаиболее эффективным является генетический алгоритм.2 4 6 8 10 12 14 16 18 20 22 24 26 28 30Значение параметра остановаВремя решенияЦелевая функцияРис. 5. Графики зависимости решений от значения параметра остановаРеализована мультиметодная технология, предложенная профессоромИ.П. Норенковым, в основу которой положена идея кодирования решениязадачи упаковки в виде последовательности эвристик.Для мультиметодного генетического алгоритма применительно к модели«виртуальные объекты» разработаны новые эффективные эвристикиразмещения ортогональных объектов:1) присоединение к узлу j текущего контейнера наиболее подходящегообъекта i вдоль выбранного направления упаковки l :(plj − wil )→ min, wid ≤ p dj ∀d = 1,K, D ;(7)2) присоединение к узлу j текущего контейнера первого подходящегообъекта i с максимальным объемом: D d D d ∏ p j − ∏ wi → min, wid ≤ pid ∀d = 1,K, D ;d =1 d =1(8)3) присоединение первого объекта i из списка π w упорядоченных поширине неразмещенных объектов к ближайшему свободному узлу jтекущего контейнера:14∀h < j ∃ d : p dj < wid , wid ≤ p dj ∀d = 1,K, D .(9)4) присоединение первого объекта i из списка π s упорядоченных пообъему неразмещенных объектов к ближайшему свободному узлу jтекущего контейнера при выполнении условия (9).Первые две эвристики осуществляют выбор наиболее подходящегообъекта для его присоединения к определенному узлу контейнера.
Третья ичетвертая эвристики работают по обратному принципу – осуществляет поисктакой области контейнера, в которой присоединение определенного объектаоптимально. Все рассмотренные эвристики совместно обеспечиваютоптимизацию как последовательности размещения объектов, так иоптимизацию использования свободного пространства контейнеров.Проведенные вычислительные эксперименты показали, что невозможновыделить эвристику, которая наилучшим образом обеспечивает размещениеобъектов при решении различных классов задач ортогональной упаковки.Поэтому начальная популяция решений в реализованном мультиметодномгенетическом алгоритме Packer MGA содержит равновероятный наборэвристик, а их наилучшее соотношение выбирается в ходе эволюционногопоиска оптимального решения.Описан алгоритм быстрого размещения объектов Packer FIT, конечнымрешением которого является лучшая из используемых эвристик.
Проведенныевычислительные эксперименты показали, что мультиметодный генетическийалгоритм является самым эффективным среди рассмотренных алгоритмовоптимизации решения задачи ортогональной упаковки.В четвертой главе приведено описание разработанной унифицированнойбиблиотеки классов задач упаковки «UniPacker»; приведены результатыпроведенныхвычислительныхэкспериментовнадразработаннымиалгоритмами и методами.Разработана информационная модель в виде библиотеки классов,обеспечивающая унифицированный подход к решению задач упаковкипроизвольной размерности. Диаграмма UML унифицированной библиотекиклассов задач упаковки приведена на рис.
6.Разработанная унифицированная библиотека классов может бытьиспользована при решении следующих задач:• задач упаковки различных видов объектов;• задач многомерной упаковки (одномерной, двухмерной, трёхмерной ибольшей размерности);• задач упаковки на основе различных эвристических алгоритмов.Унификация библиотеки классов достигается благодаря инвариантностиалгоритмов получения субоптимального решения для различных видовобъектов и инвариантности схем размещения объектов различной размерностив контейнерах. Приведены области эффективного применения разработаннойбиблиотеки классов.
Перечислены преимущества предлагаемого комплексногоподхода к решению задач многомерной упаковки объектов.15Рис. 6. Диаграмма классов разработанной библиотеки задач упаковкиОписана программная реализация разработанных алгоритмов и методов ввиде прикладного программного обеспечения для решения задач ортогональнойупаковки, созданного на основе разработанной унифицированной библиотекиклассов задач упаковки «UniPacker». Разработанные алгоритмы реализованына платформе Microsoft Win 32 с использованием языка программированияC++. Результаты проведенных вычислительных экспериментов показаливысокую эффективность разработанных алгоритмов решения задачортогональной упаковки объектов.16Эксперимент 1.
Решение задачи двухмерной упаковки на листыЭффективность применения разработанных алгоритмов и методов длярешения задач двухмерной контейнерной ортогональной упаковки объектовисследована на эталонных примерах из библиотеки OR-library, размещенной насайте http://people.brunel.ac.uk/~mastjjb/jeb/info.html, для наборов объектов,взятых из тестовых задач, сформулированных S.P. Fekete и J. Schepers, длякоторых известны точные нижние границы решений. Во всех задачах габаритыконтейнеров одинаковые и равны 100 × 100 .
В ходе вычислительногоэксперимента были решены задачи двухмерной прямоугольной упаковкиразмерности m = 40 , 50, 100, 150, 250, 500, 1000. Для каждой задачи былапроведена серия из 100 экспериментов. Показателем качества размещенияявляется относительное отклонение µ от нижней границы, котороерассчитывается по формуле:N − Λ*µ(% ) = t100% ,(10)mгдеNt –целеваяфункциярешения(числозаполненныхобъектамиконтейнеров), Λ * – точная нижняя граница задачи.Решения, полученные на основе алгоритмов Packer MGA и Packer FIT(выбор лучшей из разработанных эвристик без последующей оптимизации),сравнивались с решениями, полученными на основе следующих эволюционныхалгоритмов:• генетический блочный алгоритм Норенкова И.П.
GMA;• жадный генетический алгоритм Genetic Greedy Sub (GGSub).Полученные результаты сведены в таблицу 2.Таблица 2.Результаты эксперимента 1 с задачами упаковки на листыОтклонение от нижней границы µ, %Типы задачGMAGGSubPacker FITPacker MGAngcutfs_1ngcutfs_2ngcutfs_32.391.760.881.871.370.882.031.561.021.631.060.78Мультиметодный генетический алгоритм Packer MGA с разработаннымиэвристиками и унифицированным декодером Packer обеспечивает наилучшееразмещение объектов на всех классах решаемых задач двухмернойконтейнерной упаковки на листы.Эксперимент 2.
Решение задачи двухмерной упаковки наполубесконечную полосуЧисленный эксперимент проводился при решении эталонных тестовыхзадач рулонного раскроя из статей Berkey и Wang (классы задач С1-С6), а также17из статей Martello и Vigo (классы задач С7-С10). В ходе эксперимента былорешено 500 задач раскроя прямоугольных объектов на полубесконечнойполосе. Число прямоугольников в каждом классе – от 20 до 100. Показателемэффективности рулонного раскроя служит отклонение от нижней границы,которое рассчитывается по следующей формуле:η(% ) =L − L0100% ,L(11)где L – длина занятой части полосы, L0 – теоретическая нижняя границазадачи.Результаты проведенного эксперимента приведены в табл.
3. Сравнениерезультатов размещения объектов проводилось для следующих алгоритмов:• генетический алгоритм Бортфельдта А. SPGAL;• жадный генетический алгоритм GGSub;• генетический блочный алгоритм GBA;• алгоритм поиска с запретами Ермаченко А.И. TS;• генетический блочный алгоритм Норенкова И.П.
GMA;• реализованныймультиметодныйгенетическийалгоритмсразработанными эвристиками Packer MGA.Таблица 3.Результаты эксперимента 2 с задачами двухмерной упаковки наполубесконечную полосуОтклонение от нижней границы η, %Класс задачSPGALGGSubGBATSGMAC1C2C3C4C5C6C7C8C9C10Среднее C1-C100.750.842.523.082.534.671.223.660.123.042.200.591.231.993.222.084.441.133.600.073.192.130.891.212.753.172.774.561.354.810.073.922.550.580.801.713.332.064.241.123.350.072.821.981.211.243.233.613.254.971.405.540.074.602.91PackerMGA0.700.781.454.042.045.791.175.650.112.792.45Алгоритм Packer MGA с разработанными эвристиками и декодеромPacker обеспечивает на четырёх из десяти классов задач двухмерной упаковкина полубесконечную полосу получение решений с наименьшим отклонением оттеоретической нижней границы задачи.18Показана эффективность применения классического генетическогоалгоритма с унифицированным декодером Packer при решении задачтрёхмерной ортогональной упаковки объектов.
Применение генетическихалгоритмов при решении задач трёхмерной ортогональной упаковки объектовпозволяет более чем на 16% повысить среднее значение целевой функцииконечного решения, что говорит о целесообразности их применения.Основные выводы и результаты работыВ результате проведенных исследований получены следующие новыенаучные и практические результаты:1. Решена актуальная научная задача, заключающаяся в эффективнойупаковке ортогональных объектов и имеющая существенное значениепри создании моделей и программных решений для различныхотраслей народного хозяйства.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
