Рішення завдання одномірної упаковки з допомогою
паралельного генетичного алгоритму
І.В. Мухлаева
Вступ
У роботі представлений
паралельно генетичний алгоритм (Пага) для вирішення задачі одномірної
упаковки. В цілому це завдання є завданням розбиття множини об'єктів на
непересічні підмножини:
. [1]
У більшості задач розбиття
їх рішення пов'язане з певними обмеженнями накладаються, у противному
випадку рішення буде нелегальним. Ось чому елемент, як правило, не може
бути об'єднаний в одне підмножина з усіма можливими підмножинами залишаються
елементів. Мета розбиття полягає в оптимізації функції вартості, визначеної
на множині всіх легальних підмножин.
Завдання одномірної
упаковки є широко застосовується в якості моделі розподілу ресурсів
різного роду.
процесори, локація пам'яті, форматування таблиць і т.д. Браун [1] наводить
додатково програми завдання в індустрії та бізнесі.
Як відомо, завдання
одномірної упаковки є завданням комбінаторної оптимізації і відноситься до
класу NP-повних [2]. Тому для її вирішення розробляються різні
апроксимаційний, евристичні алгоритми, що дозволяють отримувати прийнятні за
якості результати за прийнятний час. Однак, відомі наближені алгоритми
одномірної упаковки дають рішення досить низької якості. Так, оцінка алгоритму
FF дорівнює
[2].
Подальші спроби
отримати наближені алгоритми з більш високими оцінками не призвели до
істотним результатами [3-7]. Не вдалося перевищити оцінку алгоритму RFF:
[3, 4].
Для підвищення якості
рішення слід використовувати методи комбінаторної оптимізації, що володіють
механізмами виходу з локальних оптимумів і здатні знаходити близькі до
оптимального рішення. Перспективними в цьому сенсі є алгоритми, засновані
на методі відпалу та генетичні алгоритми (ГА).
ГА дозволяють отримувати
близькі до оптимального рішення значно швидше, ніж метод відпалу [8]. Це
відбувається за рахунок поєднання в них елементів випадкового і спрямованого пошуку.
ГА працюють одночасно з декількома рішеннями і синтезують нові
субоптимальних рішення на основі властивостей досягнутих. ГА володіють механізмами
уникнення локальних оптимумом за рахунок елементів випадковості.
Розроблено кілька ГА
одномірної упаковки [9-11].
Розробка паралельних
ГА є перспективною, оскільки розпаралелювання процесу пошуку дозволяє
скоротити час рішення [12].
Відомі декілька
паралельних генетичних алгоритмів [12-14], призначених для вирішення
різних оптимізаційних задач.
У представленому
алгоритмі Пага за рахунок узгодження позицій точок Кросинговер здійснюється
кооперативний пошук в незалежних субпопуляція, що додатково знижує
часові витрати. Також розроблені три види спрямованої мутації, що підвищує
якість одержуваних рішень. Для посилення елементів спрямованості введені
захищені від деструкції фрагменти хромосом, оскільки у міру наближення
рішень до оптимуму зростає деструктивність генетичних операторів,
заснованих на принципі випадковості. Додатково для скорочення часу
рішення запропонована евристика, що скорочує обсяг даних для ГА.
Для дослідження
запропонованого алгоритму розроблено програмне забезпечення на мові С + + для IBM PC. Проведено
статистичні дослідження, що підтверджують ефективність Пагано.
1.
Паралельний генетичний алгоритм
1.1.
Постановка завдання
Розглянемо задачу
одномірної упаковки в такій постановці.
Дано: безліч
елементів E = (e1, e2, ... , En), що мають
розміри S (E) = (s (e1), s (e2), ... , S (en)), і
безліч блоків B = (b1, b2, ... , Bm), що мають
розміри S (B) = (s (b1), s (b2), ... , S (bm )}.
Мета: мати
елементи у наявні блоки, заповнюючи кожен з блоків до максимально можливого
рівня і мінімізуючи загальна кількість заповнених блоків.
1.2.
Функція вартості
Для роботи ГА необхідно
визначити функцію вартості, відповідно до якої будуть оцінюватися
рішення. Метою рішення визначена мінімізація площі, зайнятої розміщеними в
блоках елементами. Відповідно, необхідно знайти спосіб її оцінки. Будемо
вважати, що в ідеальному випадку (верхня оцінка) площа, зайнята елементами,
дорівнює сумі їх розмірів:
Площа, зайнята
елементами при кожному конкретному розміщення, визначається наступним чином:
PS = SB *
+ Sr,
де SB * --
сума розмірів блоків, зайнятих елементами, крім останнього зайнятого блоку, Sr
- Сума розмірів елементів в останньому блоці. Оцінкою рішення в такому разі
буде коефіцієнт 
Метою рішення задачі
стає максимізація коефіцієнта C.
1.3.
Кодування
Серед шести принципів створення
ефективних рішень (див. наприклад, [9]) фігурує принцип мінімальної
надмірності: кожен елемент області пошуку (у даному випадку області всіх
легальних підмножин) повинен бути представлений мінімальним (ідеально - однієї)
числом хромосом, щоб скоротити розмір області пошуку ГА. Областю пошуку в
випадку завдання одномірної упаковки є безліч всіх легальних (тобто не
допускають переповнення будь-якого блоку) розподілів елементів в блоки.
В алгоритмі використано
лінійне кодування, при якому хромосома представляє собою список
елементів, де позиція елемента в списку означає чергу його на розміщення в
блоках. Елемент розміщується в блок, якщо в блоці є достатня для цього
місце.
1.4.
Генетичні операції
1.4.1.
Оператори Кросинговер
На початку роботи ГА
створюється початкова популяція, розділена на три субпопуляції. Незалежна
еволюція в субпопуляція дозволяє зберігати різноманітність генетичного
Для цього кооперації
пошуку були розроблені оператори Кросинговер, застосування яких погоджено
при комунікації субпопуляцій. Кожен оператор Кросинговер передає нащадкам
максимально можливий фрагмент рішення, що отримав високу оцінку. Для цього
схема чинного Кросинговер вибирається в залежності від схеми
Кросинговер, який застосовувався на більш низькому рівні (у субпопуляції).
У першому субпопуляції
використовується упорядкований оператор Кросинговер (Order crossover, OX),
розроблений D. Davis в 1985р .. У другій субпопуляції використовується
модифікація OX, при якій зчитування генів здійснюється справа наліво.
Щоб відрізнити ці оператори позначені OXL і OXR
відповідно. У третин субпопуляції використовується двоточковим оператор
Кросинговер.
При комунікації 1 і 2
субпопуляції використовується OXL. У результаті
формуються два нащадка, які записуються один в 1 субпопуляцій, другий --
у другу. При комунікації 2 і 1 субпопуляцій використовується OXR.
Нащадки записуються один в 2 субпопуляцій, другий - в 1-у. При комунікації 1
і 3 субпопуляції використовується OXL. Нащадки записуються одна
в 1 субпопуляцій, другий - у 3-ю. При комунікації 3 і 1 субпопуляцій
використовується двоточковим Кросинговер. У результаті формуються два нащадка,
які записуються один в 3 субпопуляцій, другий - в 1-у. При комунікації 2
і 3 субпопуляції використовується OXR. Нащадки записуються одна
у 2 субпопуляцій, другий - у 3-ю. При комунікації 3 і 2 субпопуляцій
використовується двоточковим Кросинговер. Нащадки записуються один в 3 субпопуляцій,
другий - в 2-у.
1.4.2. Оператори мутації
В алгоритмі використані,
крім випадкової мутації, спеціально розроблені проблемно-орієнтовані
спрямована мутація. з пошуком 1-1 (підстановка об'єктом в подходяшую
за розміром незайняту позицію) і аправленная мутація. з пошуком 2-1 (обміну
позиціями елементів, один з яких дорівнює за розміром сумі величин другу
елемента і вільної позиції за ним).
1.4.3.
Інверсія
В алгоритмі використаний
також класичний оператор інверсії.
1.5.
Паралельний пошук
Пага працює таким
чином.
1о.Форміруется
початкова популяція, розділена на три субпопуляції ..
2о.В кожній
субпопуляції відбувається відповідний Кросинговер.
3О. У кожній
субпопуляції відбуваються випадкова і спрямовані мутації і інверсія.
4о.По
закінчення 10 поколінь відбувається Кросинговер між субпопуляціями
(відповідний для кожної).
5о. Закінчення
роботи при досягненні C = 1 або межі введеного користувачем числа поколінь.
Одним з мотивів
поділу ГА є потенційне зростання швидкодії завдяки використанню
процесора або багатопроцесорної системи для обробки окремої популяції.
Однак, найбільш важливим мотивом є те, що після деякого числа
поколінь хромосоми в окремій популяції стають дуже схожими.
Різноманітність генетичного матеріалу буде втрачено, і рекомбінація надалі
може бути неефективною. Одним із способів подолання цієї проблеми і
є незалежна обробка окремих популяцій. Так як ГА включають в себе
елементи випадкового пошуку, незалежна еволюція окремих популяцій буде
направляти процес в різні області простору рішень. Якщо
оптимізується в кожній субпопуляції функція одна й та ж, кожна субпопуляція
дасть конкурентоспроможне, але при цьому значно відрізняється за складом ГМ
рішення.
Число взаємодій
між популяціями може бути критичним фактором у визначенні ефективності
паралельного ГА. При наявності великої кількості взаємодій переваги
використання субпопуляцій виявляються втраченими, тому що гарні хромосоми
з однієї субпопуляції швидко потрапляють в інші субпопуляції, і еволюція недовго
залишається незалежною. Результати, отримані в дослідженнях [13,14]
підтверджують це положення.
При визначенні
ефективності Пага необхідно враховувати ефекти, вироблені на початкову
популяцію операторами Кросинговер, мутації та селекції.
Завдяки застосуванню
трьох типів кросинговеру в кожній з субпопуляцій формується окремий
якісний фрагмент упаковки. Синтез цих фрагментів здійснюється в
процесі комунікації між субпопуляціями, при якій в Кросинговер
беруть участь кращі хромосоми.
Таким чином, хороші
властивості субоптимальних рішень, отриманих у незалежних субпопуляція,
успадковуються у всій популяції і направляють процес пошуку.
Розглянемо ефект
вироблених генетичних операцій [8].
Ефект мутації.
Позначимо pm норму випадкової мутації, однакову для кожного
локального ГА. Тоді ймовірність того, що схема S порядку n (S) в усій
популяції піддасться випадкової мутації, буде рівна pmn (S). У
стандартному послідовному ГА ймовірність того, що схема виживе, дорівнює: 1 --
pmn (S). Таким чином, Пага у порівнянні з ГА не змінює ефект
випадкової мутації. Проте, враховуючи, що при випадковій мутації точки мутації
вибираються випадково, еволюція в окремих субпопуляція піде різними шляхами.
Зі зростанням норми мутації ефект, вироблений нею в різних популяціях, зближується,
але стане однаковим, лише якщо мутація здійснить повний перебір генів у
хромосомі, що не допускається.
Ефект Кросинговер.
Імовірність того, що вона піддасться
кросинговеру, дорівнює pc. Характеристики нащадків цієї хромосоми
залежать від того, яка хромосома буде обрана в якості другого з батьків. У
субпопуляції розміром N у всякого іншого
індивіда є 
шансів бути
обраним в якості другого з батьків.
Ефективність ГА
визначається нормою виживання схеми. Важливо визначити, який ефект на
виживаність схеми має вибір індивіда для Кросинговер. Імовірність вибору
індивіда в субпопуляції дорівнює pc, ймовірність вибору індивіда в
початкової популяції - pc. Тоді для локального ГА і Пага ймовірність
того, що схема S деякої довжини d (S) виживе після Кросинговер, дорівнює 
, де L - довжина схеми. Норма виживання схеми в Пага
відрізняється від норми виживання схеми в ГА, що визначається розподіленої
природою селекції і комунікацією генетичної інформації. Середній або поганий
по якості для однієї субпопуляції індивід може бути хорошим для іншої
субпопуляції.
2.
Статистичні дослідження
2.1.
План експериментів
З використанням
розробленого ПО досліджувалися наступні залежності. Залежність часу
роботи алгоритму від кількості елементів, динаміка якості рішень в
поколіннях і залежності цих показників від вагових розподілів елементів.
Дослідження проводилися з довірчої імовірністю 75%, розмір серії
експерименту 33, на IBM 486 DX/2 66.
Для дослідження
використовувалися набори даних по 20, 50, 100, 150, 200 елементів при чотирьох вагових
розподіли; вигляд вагових розподілів елементів представлений нижче.
Вид тестів на 200
елементів.
3.2.
Результати експериментів
Залежності часу від
числа елементів при різних типах даних (колір означає відповідне
кількість елементів).
Проведені дослідження
показали, що залежність часу від кількості елементів при всіх розподіли
не досягає квадратної ступеня при розмірах завдання до 200 елементів, що
доводить практичну цінність розробленого алгоритму.
Залежності якості від
числа поколінь на різних тестах: (в дужках вказані кількості елементів, колір
означає число поколінь).
Результати проведених
досліджень показують, що найбільш щільна упаковка при всіх кількостях
елементів досягається при четвертому типі вагового розподілу. Друге і
третього розподілу дають приблизно рівні результати.
3.3.
Порівняння з відомими результатами
Було проведено сравнеіе
розробленого Пага з простим ГА (ПГА). Результати порівняння зведені в таблицю.
Вони показують, що Пага на всіх тестах досяг оптимуму і, таким чином, має
значне перевищення якості рішення при незначному перевищенні
витраченого часу.
Алгоритм
Кількість
ел-тов
вагове
рапред.
розмір
попул.
кол-во
покол.
час
рішення
якість
ПГА
20
тест -1
20
25
660
0.8544
Пага
20
тест-1
20
11
517
1
ПГА
20
тест-2
20
25
660
0.8686
Пага
20
тест-2
20
9
407
1
ПГА
20
тест-3
20
25
412
0.8193
Пага
20
тест-3
20
6
264
1
ПГА
20
тест-4
20
25
412
0.8418
Пага
20
тест-4
20
9
410
1
Список
літератури
Brown
A.R. Optimal Packing and Depletion. American Elsevier, New York, 1971.
Гері М., Джонсон Д.
Обчислювальні машини і труднорешаемие задачі.-М.: Світ, 1982. - 416с.
Yao
A.C. New algorithms for bin packing. Report NoSTAN-CS-78-662. Computer Science
Dept., Stanford University, Stanford, CA, 1978.
Chi-Chin
Yao. A new algorithm for bin packing J. of the ACM, Vol.27, No.2, 1980.
Johnson
D.S., Demers A., Ullmans J.D. and oth. Worts-case performance bounds for simple
one-dimensional packing algorithms. SIAM J. Comput., Vol.3, No. 4, 1974.
Kao
C.-Y., Lin F.-T. A statistic approach for the one-dimensional bin-packing
problems. In Proceedings of the 1992 IEEE International Conference on Systems,
Man, and Cybernetics, vol. 2, 1545-1551. Chicago, IL, 1992.
Garey
M.R., Graham R.L., Johnson D.S., Yao A.C. Resource constrained scheduling as
generalized bin packing. J. Combinatorial Theory Ser. A21, pp. 257-298.
Goldberg
DE, Genetic Algorithms in Search, Optimization and Machine Larning.
Addison-Wesley Publishing Company, Inc. 1989. -354p.
Falkenauer
E., Delchambre A. A Genetic Algorithm for Bin Packing and Time Balancing. In:
Proc. of the IEEE 1992 International Conference on Robotics and Automation
(RA92), Nice, 1992.
Kroger
B. Genetic algorithms for bin packing problems. In Stender J. (Ed.) Parallel
Genetic Algorithms. IOS Press, Amsterdam, 1993.
Goodman
E.D., Tetelbaum A.Y., Kureichik V.M. Genetic Algorithm Approach to Compaction,
Bin Packing and Nesting Problems, Technical Report N # 940502, MSU, East
lansing, USA, 1994.
Muhlenbein H., Schomisen
M., Born J. The Parallel Genetic Algorithm as Function Optimizer. Proc. of the
Fourth International Conference on Genetic Algorithms. San Mateo. Morgan
Kaufman, 1991. -576p.
Muhlenbein H. Parallel
Genetic Algorithms, Population Genetics and Combinatorial Optimization. Proc.
of the Third International Conference on Genetic Algorithms. San Mateo. Morgan
Kaufmann, 1989. -576p.
Tanese
R. Distributed Genetic Algorithms. In J. D. Schaffer (Ed.) Proceedings of the
Third International Conference on Genetic Algorithms. Morgan Kaufmann, San
Mateo, CA, 1989.
Митропольський А.К.
Техніка статистичних досліджень .- М., «Наука», 1971. - 218с.
Застосування
математичних методів і ЕОМ. Планування і обробка результатів
експерименту: Учеб. посібник./Під заг. ред. Останина А.Н. - Минск.: Вышэйшая
школа., 1989. - 237с.
Адлер Ю.П. Планування
експерименту при пошуку оптимальних условій.-М.: Наука, 1971. - 283с.
