WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

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

Прямоугольники №1, №2 и №3 последовательно добавляются в 1-й вертикальный блок. Далее во 2-й блок подходит прямоугольник №7 из приоритетного списка sort. Прямоугольники, упакованные по списку sort обозначены штриховкой. Затем остаток 3-го блока по высоте лучше всего замещает прямоугольник №8. Далее в 4 блок – прямоугольники №4 и №5.

Последним упаковывается прямоугольник №6, он взят из приоритетного списка, т.к. пустой остаток, куда он упаковывается является самым верхним в блоке.

Затем прямоугольник №6 сдвигается к верхней границе полосы, образуя тем самым более широкий остаток снизу.

Рассмотрим еще один пример, где будет более наглядно видно преимущество такого сдвига (рис 4,а и 4,б).

3 3 2 7 4 9 2 7 8 1 6 а б Рис. 4. Пример работы Greedy Sub:

а – сдвиг прямоугольника №5 освобождает место для прямоугольника №9;

б – получена лучшая упаковка Схема алгоритма:

1. (Инициализация) Входные данные Текущий вертикальный блок С=2. (Итерации) Пока не упакованы все прямоугольники выполнять 2.1 – 2. 2.1. Цикл по пустым участкам в вертикальном блоке C (снизу вверх) 2.1.1. Если пустой участок (его высота H) самый верхний в блоке, то Находим в списке по порядку прямоугольник R, удовл.

условию wRH Иначе а) Находим в списке sort по порядку прямоугольник R, удовл.

условию wRH б) Если разрешены повороты, то находим в списке sort по порядку прямоугольник R2, удовл. условию lR2H;

в) Если lR2> wR, то R=R 2.1.2. Если нашли, то Вставляем прямоугольник R Вычисляем длину lmin самого короткого прямоугольника в блоке С.

Модифицируем блочную структуру, так что длина блока С равна lmin 2.2. Конец цикла 2.3. C=C+3. Вывод найденного решения Сложность декодера GreedySub O(m3).

Третья глава посвящена эволюционным методам решения задач упаковки. Предложна модификация генетического алгоритма с использованием разработанного блочного декодера Greedy Sub.

Эволюционный алгоритм (1+1) Эволюционные алгоритмы (ЭА) – это обобщенный термин, применяемый для описания вычислительных методов, использующих модели эволюционных процессов. Основой всех эволюционных алгоритмов является имитация эволюции индивидуальных структур через процессы отбора, мутации и воспроизведения. ЭА рассматривают популяции структур, развивающиеся путем мутаций и воспроизведения согласно правилам отбора. Отбор происходит по критериям соответствия структуры условиям внешней среды.

ЭА достаточно широко используются при решении задач многопараметрической оптимизации.

Генетические методы являются одной из разновидностей эволюционных алгоритмов. Они максимально приближены к реальным эволюционным процессам живой природы. Но существуют и более простые ЭА. В частности, к таким относится и эволюционный алгоритм (1+1). Схема его работы строится на следующем подходе:

Имеется одно закодированное решение (хромосома), которое является родителем. На каждой итерации с помощью модификации этой родительской хромосомы получается потомок. Модификация представляет собой мутацию. В случае, если целевая функция потомка достигает лучшего значения, он заменяет родителя. Доказано, что, если оператор мутации обладает свойством монотонности, то алгоритм (1+1)-EA является оптимальной стратегией поиска среди различных ЭА. Для операторов мутации применяемых в среде задач раскроя-упаковки, свойство монотонности мутации пока не доказано.

Отличия ЭА (1+1) от генетического алгоритма:

1. В (1+1)-ЕА отсутствует понятие популяции. Если в генетических алгоритмах все операции выполняются над множеством закодированных решений (хромосом), то в предложенном эволюционном алгоритме имеется только одна особь.

2. В (1+1) не применяется оператор скрещивания. На каждой итерации алгоритм работает только с одной особью. И единственным оператором, который к ней применим, является мутация, работающая с приоритетным списком.

Как и для генетического алгоритма, в ЭА (1+1) в качестве хромосом выступают приоритетные списки и мутации подвергаются именно они.

Мутация будет представлять собой случайную перестановку элементов внутри приоритетного списка. Но если в классическом генетическом алгоритме мутация заключалась в случайном выборе одной пары генов для обмена, то для ЭА (1+1) предлагается в процессе мутации выбирать несколько таких пар.

«Жадный» генетический алгоритм с декодером Greedy Sub Работа генетического алгоритма заключается в случайном формировании множества хромосом (перестановок прямоугольников) и выбора из них наилучшего, т.е. того списка, который находится по заданному критерию ближе к оптимальному решению. Основными процедурами работы генетического алгоритма являются процедуры скрещивания, отбора и мутации.

На этапе скрещивания происходит формирование новых особей (перестановок прямоугольников) на основе уже существующих. При этом в новом особе-потомке находят свое отражение черты обоих родителей.

Существенную роль в общем процессе нахождения решения играет декодер, получающий карту размещения по перестановке прямоугольников: от того, насколько плотно будут расположены прямоугольники декодером, зависит значение целевой функции. В данном случае используется декодер Greedy Sub Схема алгоритма Genetic Greedy Sub:

1. (Инициализация) Ввод данных , K, где K – число итераций k=1, где k – номер итерации Генерирование первоначальной хромосомы Запуск для декодера Greedy Sub 2. (Итерации) Пока k

2.4. Если CC(PL) удовлетворяет попаданию в популяцию, то добавляем PL в популяцию удаляем хромосому с наименьшим значением CC из популяции 2.5. k=k+3. Вывод решения, соответствующего хромосоме с наибольшим CC Решение задачи прямоугольной упаковки на листы Решение задачи упаковки на прямоугольные листы в данной реализации отличается от задачи упаковки в прямоугольную полосу лишь введением одного дополнительного ограничения, это ограничение – ширина листа L, в случае упаковки в полубесконечную полосу L=. Длина листа L учитывается в декодере, когда тот добавляет очередной прямоугольник в блок.

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

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

Решение задач размещения на полосу на примерах А.Бортфельда (библиотека OR-library) Сравнение результатов работы проводилось для следующих алгоритмов и декодеров:

•Генетический алгоритм Бортфельда;

•Генетический алгоритм с декодером замещения (Смагина М.А.) GSM;

•Генетический блочный алгоритм GBA (Мухачева А.С., Чиглинцев А.В.);

•Наивный эволюционный алгоритм с декодером Greedy Sub;

• «Жадный» генетический алгоритм Genetic Greedy Sub.

Отклонение от нижней границы считалось по формуле:

L - LGAP = 100%, где L – длина упаковки, L0 – нижняя граница.

L В эксперименте указаны не только алгоритмы, но и декодеры, чтобы показать насколько эффективным в алгоритме является именно выбор декодера. Декодер Greedy Sub показал результаты лучше чем у большинства других алгоритмов.

Как видно из таблицы, наименьшее среднее отклонение от нижней границы по всем классам дает «жадный» генетический, Genetic Greedy Sub. классов задач из 10 решены алгоритмом GGSub лучше других.

Таблица 1.

Результаты эксперимента. Отклонения от нижней границы GAP.

Средние значения для каждого класса.

Класс Bortfeld GSM GBA GSUB GGSUB C1 0,75 0,96 0,89 0,65 0,C2 0,84 0,79 1,21 1,35 1,C3 2,52 1,92 2,75 2,08 1,C4 3,08 4,68 3,17 3,49 3,C5 2,53 1,94 2,77 2,13 2,C6 4,67 6,05 4,56 4,52 4,среднее C1-C6 2,40 2,72 2,56 2,37 2,C7 1,22 0,95 1,35 1,13 1,C8 3,66 5,80 4,81 3,97 3,C9 0,12 0,09 0,07 0,07 0,C10 3,04 4,20 3,92 3,66 3,среднее C7-C10 2,01 2,76 2,54 2,21 2,среднее С1-С10 2,21 2,74 2,55 2,29 2, Исследование эффективности алгоритмов декодеров при использовании генетических алгоритмов Целью эксперимента является исследование эффективности предложенных в работе жадного блочного декодера и декодеров (в том числе блочных) других авторов. Для проведения эксперимента использовалась классическая реализация генетического алгоритма, в которой на стадии декодирования упаковки из приоритетного списка использовались декодеры:

•IBL – улучшенный нижний левый, D.Liu & H.Teng, •SubRec – декодер замещения с перестройкой, А.С. Мухачева, •IBD – улучшенный блочный декодер, А.В. Чиглинцев, •Greedy Sub – «жадный» блочный декодер Сравнение производилось на классе задач с набором предметов различных размеров от малых 5% до 95% ширины полосы. Количество прямоугольников 40, 80, 120. Примеры были сгенерированы в соответствии с методикой профессора Г.Вэшера.

m 84 85 86 87 88 89 90 91 92 SubRec IBL IBD Greedy Sub CC, % Верхнее и нижнее ограничение по ширине прямоугольников равны v1=0,05 и v2=0,95 соответственно. Верхнее и нижнее ограничение по длине прямоугольников равны w1=0,30 и w2=0,70 соответственно. В каждом классе задач было сгенерировано и просчитано по 10 задач.

В качестве критерия эффективности упаковки применяется «коэффициент раскроя» (Cutting Coefficient, CC) равный отношению полезной площади ко всей затраченной. Для безотходной упаковки СС=100%.

Наилучшие результаты у «жадного» блочного декодера GreedySub, за ним с небольшим отставанием следует IBD.

Исследование эффективности генетического гибридного алгоритма Genetic Greedy Sub. Сравнительный эксперимент с метаэвристическими алгоритмами Целью эксперимента является исследование эффективности разработанного генетического гибридного алгоритма с декодером «жадного замещения». Для сравнения были выбраны пять алгоритмов, реализации которых были разработаны на кафедре ВМиК УГАТУ:

• Genectic Greedy Sub – генетический алгоритм с декодером «жадного замещения»;

• GBA – генетический блочный алгоритм, А.С.Мухачева, А.В.Чиглинцев, 2000;

• GIBL - классический генетический алгоритм, D.Liu & H.Teng, (программная реализация М.А. Смагина);

• GMM – генетический мультиметодный алгоритм, И.П. Норенков, (программная реализация Л. Ильясова);

• ACSP – алгоритм муравьиной колонии, А.Ф. Валеева, М.Н. Аглиуллин, 2003 (программная реализация М.Н. Аглиуллин);

• NDLS – алгоритм наивного поиска двойственной блок-структуры, А.С.

Мухачева, Р.Р. Ширгазин, 2002;

Сравнение производилось на классе сложных задач (триплеты) v1=0,3;

v2=0,4; w1=0,35; w2=0,45. Ранее было замечено, что характеристики по длине мало влияют на результативность, при решении задачи на полосу с запретом поворотов, поэтому решение задач выполнялось с поворотами.

m 80 81 82 83 84 85 86 87 88 89 90 ACSP GIBL NDLS CC, % GBA GMM Genetic Greedy Sub Среди генетических алгоритмов лидирует Genetic Greedy Sub, далее идут «блочный генетический» и «мультиметодный генетический» алгоритмы.

Решение задач размещения на листы на примерах С.П. Фекете и Я.Шеперс Данный эксперимент выполнялся для оценки эффективности различных алгоритмов решения задач размещения на листы. Использовались примеры задач S.P. Fekete и J. Schepers. Критерием сравнения результатов также являлось отклонение от нижней границы, рассчитанной алгоритмом этих же авторов. Примеры тестовых задач взяты из библиотеки OR-library.

Площадь листа во всех задачах равна 100100. Для каждой задачи размерности n=40,50,100,150,250,500,1000 было решено по 10 примеров.

Таблица 2.

Результаты эксперимента с примерами С.П.Фекете и Я. Шеперс.

Отклонение от нижней границы, % Наивный Алгоритм Наивный Класс перебор (1+1) – муравьиной колонии перебор задач ЕА (ACP) (Greedy Sub) 1 2,93 2,88 1,2 2,33 2,23 1,3 1,73 1,59 0, Отклонение от нижней границы результатов полученных декодером Greedy Sub на всех классах задач меньше по сравнению с результатами других авторов. Кроме хороших результатов, полученных декодером Greedy Sub, он еще оставляет возможность улучшения своих показателей, путем встраивания его в другие эвристические алгоритмы раскроя-упаковки, как это было сделано в «жадном» генетическом алгоритме Genetic Greedy Sub, реализованном в рамках данной диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ 1. Представлена обобщенная модель задач прямоугольной упаковки, которая позволила реализовать новые эффективные методы решения задачи прямоугольного раскроя и упаковки 2. Модифицированы однопроходные эвристические методы конструирования упаковок: следующий подходящий, NF; первый подходящий FF; лучший подходящий, BF; с использованием блок-структур; на базе этих алгоритмов разработаны высокопроизводительные варианты метода замещения, обеспечивающие эффективное конструирование рациональных упаковок.

3. Разработан новый декодер «жадного» замещения Greedy Sub на базе блочной структуры и его модификации. Впервые в работе декодера стратегия жадности реализована в разных направлениях, используя несколько приоритетных списков прямоугольников. Его эффективность превосходит аналогичные показатели других алгоритмов.

4. Разработан «наивный» эволюционный алгоритм (1+1)-ЕА с различными операторами мутации и декодерами. Показана его высокая качественная и временная эффективность с декодером «первый подходящий» и «наивным» оператором мутации.

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

Это позволило осуществить гибридизацию алгоритма с другими эвристиками блочной структуры и выбрать наиболее подходящую из них – жадный декодер замещения 6. Создано программное обеспечение, реализующее разработанные алгоритмы и декодеры и предназначенное для проведения вычислительных экспериментов.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»