Упаковка - це класична проблема оптимізації. Припустимо, у нас є вантажівка, здатна перевозити будь-яку кількість ящиків, якщо їх загальна вага не перевищує W. На складі є необмежена кількість різних видів товарів. Кожен тип елемента i має вагу w i і значення v i. Ваша проблема полягає у визначенні, яка комбінація об’єктів досягне найвищого значення, не перевищуючи максимально дозволену загальну вагу. Наприклад, коли ваги та значення є
тоді вантажівка з максимальною вантажопідйомністю W = 200 може перевозити:
Найкраща стратегія - завантажити якомога більше ящиків апельсинів, а решту заповнити книгами. Розв’яжіть задачу для більшої кількості предметів із випадково визначеними значеннями та вагами за допомогою генетичного алгоритму, з обмеженою кількістю деяких елементів, придумайте власне уявлення про проблему та відповідні хромосоми, мутації та зшиті алгоритми . (Адаптовано з http://www.epcc.ed.ac.uk/epic/ga/intro.html)
(команду підготує Ян Маріок, [email protected] .uniba.sk)
Тема 2. Проблема планування
Проблема планування є інтенсивною в галузі оперативних досліджень протягом багатьох років. Одне із формулювань задачі полягає в припущенні, що ми маємо набір із N завдань t i, i = 1.N, кожна з яких вимагає деяких ресурсів r j протягом певного часу i, rj. Наше завдання - знайти найшвидший графік загального виконання цих завдань, тоді як ресурси можуть використовуватися одночасно, але кожен ресурс має інше завдання. Порядок ресурсів для завдання не має значення. Розв’яжіть задачу для більшої кількості завдань із випадково визначеними необхідними ресурсами та часом, використовуючи генетичний алгоритм, придумайте власне уявлення про проблему та відповідні хромосоми, мутації та схрещування, порівняйте свій алгоритм із канонічним генетичним. Використовуйте функцію покарання, якщо обмеження не досягнуто.
(команду підготує Ян Валл, [email protected])
Тема 3. Порівняння генетичного алгоритму із симплексним методом
Оптимізуйте функцію f (x, y) = cos 2 (n Pi x) exp (-r 2/s 2), r 2 = (x-0.5) 2 + (y-0.5) 2 для x, y О [0, 1], де n = 9 і s 2 = 0,15. Знайдіть загальний максимум цієї функції за допомогою генетичного алгоритму та симплекс-методу. Збільште розмір задачі до 3,4,5,6 розмірів та порівняйте ефективність GA із симплекс-методом (код, наприклад, http://www.techxhome.com/products/o ptsolve/або http: // www .ulib.org /webRoot/Books/Numerical_Recipes/bookcpdf.html
(команду підготує Міхаела Айова, [email protected])
Тема 4. Еволюція сортувальних мереж
(макс. придатність = 120)
- Приклад: для значень 1,3,5,4,2 отримати 1,2,3,4,5 або 5,4,3,2,1 як вихід: вертикальна лінія вказує обмін значеннями між горизонтальні лінії, коли перше значення вище/менше, ніж друге друге значення.
- Спробуйте: розмір популяції = 10, схрещування = 10%, мутації = 0%
- Спробуйте: розмір популяції = 10, схрещування = 10%, мутації = 1% (200 поколінь)
- Спробуйте: розмір популяції = 10, схрещування = 80%, мутації = 1% (150 поколінь)
- Спробуйте: розмір популяції = 50, схрещування = 90%, мутації = 1%
GA створює сортувальні мережі з 5 входами, що містять максимум 9 порівняльних обмінів. Існує 120 випадків фітнесу (всі 5! Перестановки послідовності 1,2,3,4,5), і правильна мережа упорядковує їх усі без помилок. Спробуйте коеволюцію для більш складних випадків, коли послідовності значень розвиваються незалежно одна від одної і оцінюються тим краще, чим більше мереж виходить з ладу на них.
Тема 5. Самоорганізація критичних умов у піщаних палях
Двовимірну та купу піску можна побудувати на основі дуже простих правил для простого стільникового автомата. Стан клітини характеризується кількістю піщинок, що містяться в ній. Правило відновлення говорить, що коли клітина має 4 і більше піщинок, вона втрачає 4 і отримує по одному зерну від кожної з сусідніх клітин з 4 і більше зернами. Отже, послідовність станів ударів може виглядати так
Всього до лавини було включено 6 клітин, які тривали 4 поновлення.
Ми можемо довести цю сітку до критичного стану, швидко додаючи пісок на стіл, поки швидкість насипання піску приблизно не дорівнює швидкості, з якою піщинки падають з країв столу. Еквівалентний підхід полягає в тому, щоб перевантажити стіл піском - додати довільну кількість 5-8 зерен на кожен квадрат - а потім розпочати оновлення (без додавання більше піску), поки стіл не досягне стабільного стану (відновлення не змінюється).
Цікавою особливістю цієї системи є те, що як тільки досягається критична дієта, додавання однієї піщинки може призвести до лавин усіх можливих розмірів, які можуть тривати майже довільно довго. Повторюючи цей процес багато разів, ми приходимо до висновку, що N (S)
1/S a, N (S) - кількість лавин розміром S (зачіпають S клітини решітки), а альфа - так званий критичний показник
- Яку найдовшу лавину ви можете побудувати на сітці 5х5? Початковий стан може мати максимум 3 зерна піску в сітці, а одне четверте зерно може бути додано в камеру для запуску лавини. Чи можна побудувати нескінченний цикл? Чому? (Або чому ні?)
- Експериментально визначте альфа-коефіцієнт (це найкраще зробити, створивши велику кількість лавин і зберігаючи їх розміри. Потім знайдіть кількість лавин для кожного розміру - для отримання гарних результатів потрібно багато розрахунків. Нарешті, відобразіть результати в журналі, нахил якого дорівнює мінус альфа.
- Якщо збільшити площу до всіх 8 сусідів і збільшити критичну кількість зерен до 8, цей показник збільшиться. Що спричиняє цю зміну?
Тема 6. Проблема загальної задоволеності (SAT), навіть якщо ми охоплюємо всі види логічних речень, а не лише сполучники та роз'єднання. Кожна задача складається з 20 булевих змінних (A0 - A19) та набору обмежень. Мета, звичайно, полягає в тому, щоб знайти правдиве присвоєння кожній змінній, щоб усі обмеження були дотримані. Найкращі рішення цих проблем є тривіальними для людей, але GA не має наших знань щодо логіки, і він повинен широко шукати. Накресліть графік сили (хв, макс. Та середнє) для кожного з пробігів ГА.
А) 5 сполучників, обмеження є
(A0 і A1 і A2 і A3)
(A4 та A5 та A6 та A7)
(A8 та A9 та A10 та A11)
(A12 та A13 та A14 та A15)
(A16 та A17 та A18 та A19)
- Опишіть своє уявлення та функцію сили. У вашому поданні, наскільки великий простір пошуку?
- Опишіть відмінності в поведінці ГА при використанні популяції 100 або 20. У кожному випадку використовуйте 50 поколінь, імовірність мутації (pmut) 0,01 на хромосому (не на ген) та ймовірність схрещування (pcross) 0,75 .
в) Використовуйте чисельність популяції 50, 50 поколінь, pmut = 0,01 та 3 різні ймовірності схрещування: 0,1, 0,3 та 0,8. Чим відрізняється поведінка алгоритму для заданих 3 прогонів?
Б) 10 сполучників, обмеження є
(A0 і A1) (A2 і A3)
(A4 та A5) (A6 та A7)
(A8 та A9) (A10 та A11)
(A12 та A13) (A14 та A15)
(A16 та A17) (A18 та A19)
e) Запустіть цю проблему за тих самих умов, що і a, з тією ж функцією фітнесу Які відмінності? Чому існують відмінності, навіть якщо обмеження логічно еквівалентні? Ви можете використовувати функцію фітнесу, яка використовується для пояснення різниці?
f) Виконайте цю задачу з популяцією 100, 100 поколінь, pcross = 0,8, з двома різними значеннями pmut: 0,1 та 0,01. Які відмінності? Ви можете пояснити, чому вони з’явилися?
g) Розробити нову функцію фітнесу, яка суттєво відрізняється від першої, і протестувати її на а) та е) з популяцією 100, 100 поколінь, pcross = 0,8, pmut: 0,01. Які результати порівняно з першою фітнес-функцією? Як змінювалася "поверхня"?
Б) 7 диз’юнкцій, 4 сполучники, обмеження є
(A0 або A1 або A2 або A3)
(не (A0) чи ні (A1))
(A4 та A5 та A6 та A7)
(A8 та A9 та A10 та A11)
(A12 та A13 та A14 та A15)
(A16 та A17 та A18 та A19)
h) Тест із популяцією 100, 100 поколінь, pcross = 0,8, pmut: 0,1. з обома із запропонованих вами фітнес-функцій поясніть відмінності в поведінці.
(команду підготує Павол Лупа, [email protected])
Тема 7. Використовуйте імітаційний відпал, щоб вирішити рух кота на дошці, де вам доведеться запустити всі інші поля з введеного поля, ввівши в кожне поле лише один раз. Як друга частина завдання, розв’яжіть ту ж проблему з умовою, що кіт повинен повернутися назад. Під час розв’язання використовуйте пертурбацію (мутацію), яка копіює початок послідовності полів у випадково вибрану кількість полів у нове рішення та генерує решту. Завдання також можна вирішити шляхом зворотного перегляду, але лише для невеликих випадків.
(команду підготує Томаш Пейл, [email protected])
Тема 8. Оцініть вплив стратегій відбору на оптимізацію, використовуючи визначення
для перерахунку сили пропорційно (див. формулу 4.11c в книзі «Еволюційні алгоритми») або на основі розташування відповідно до розміру (формула 4.12b) та власного вибору за допомогою рулетки, турніру, з використанням т.зв. з тохастичною універсальною вибіркою, місцевим відбором, відсіком, описаним у
Оцініть вплив стратегій відбору на оптимізацію наступних мультимодальних функцій (для n = 1-10)
f (x) = 418,9829 * n + сума (-x (i) * sin (sqrt (abs (x (i))))
f (x) = 10,0 * n + сума (x (i) ^ 2 - 10,0 * cos (2 * Pi * x (i)))
f (x) = 1/4000 * сума (x (i) -100) ^ 2 - prod ((x (i) -100)/sqrt (i)) + 1
Функції однієї змінної
f (x) = x ^ 4 - 12 * x ^ 3 + 15 * x ^ 2 + 56 * x - 60
мінімізація багатовимірних функцій
f (x1, x2, x3, x4, x5) = x1 * sin (x1) + 1.7 * x2 * sin (x1) - 1.5 * x3 - 0.1 * x4 * cos (x4 + x5-x1) + (0.2 * x5 ^ 2-x2) - 1
Функція "Nerd" - максимізація для 10 змінних
(x1 * x2 * x3 * x4 * x5)/(x6 * x7 * x8 * x9 * x10) де (x1.x10) = [1.10]
Тема 9. Оцініть вплив схрещування та оптимізації мутації на використання визначень
для перетину реальних значень: за допомогою лінійної комбінації, середніх, дискретних та двійкових значень: одноточкові, двоточкові, багатоточкові, рівномірні та мутації двійкових змінних та реальних змінних (з еволюційних стратегій 9 щодо функцій даних).
Тема 10. Генетичний алгоритм задачі Розбиття на число. Використовуйте обидва підходи для кодування подання p, як безпосередньо використовуючи N-кратки цілих чисел, так і використовуючи двійковий рядок (див. Вправу 7.1 у розділі Проблеми комбінаторної оптимізації). Порівняйте ефективність цих двох різних підходів.
(команду підготує Ян Хніла, [email protected])
Тема 11. Проблема планування завдань для процесорів
Ваше завдання полягає у використанні генетичного алгоритму для вирішення проблеми призначення завдання. Набір завдань повинен виконуватися на наборі процесорів. Кожне завдання визначається у два рази: час, необхідний для обчислення завдання, і час, необхідний для передачі результатів в основний процесор, p0. Всі процесори мають один або кілька каналів зв'язку, і лише один результат може бути надісланий на кожен канал одночасно, паралельний спільний доступ до каналів неможливий. Школи, що працюють на основному процесорі, споживають нульовий час спілкування. Якщо жоден канал зв'язку не є вільним, процесор повинен зачекати, щоб виконати частину зв'язку свого поточного завдання. Мета полягає в тому, щоб вказати розклад, тобто набір призначень процесору завдань, який мінімізував би час, коли всі завдання будуть виконані.
Використання GA для вирішення проблеми вимагає 2 основних елементів:
1. особа, яка представляє графіки та групи графіків
2 симулятор, який обчислює загальний час, коли графік завершено
Використовуйте свою програму для вирішення завдань з парами обчислювального часу та часу спілкування:
(7 16) (11 22) (12 40) (15 22) (17 23)
(17 23) (19 23) (20 28) (20 27) (26 27)
(28 31) (36 37) (31 29) (28 22) (23 19)
(22 18) (22 17) (29 16) (27 16) (35 15)
За словами Кідвелла (1993), мінімальний час для виконання завдань на 3 процесорах з одним каналом зв'язку становить 202 часових кроки. Спробуйте знайти це рішення за допомогою свого генетичного алгоритму, хоча важливо вибрати функцію фітнесу. Опишіть успіх, використовуючи графіки на основі значень ключових параметрів, таких як швидкість мутації та відсоток схрещування, кількість пунктів перетину, розмір популяції та механізм відбору. (Відповідно до http://www.idi.ntnu.no/
(команду підготує Олександр Моравчик, [email protected])
Тема 12. Мурашині алгоритми
як основу для вашого алгоритму, де для ймовірностей взяття і скидання вершини і
використовувати потужності, крім квадрата, і показувати графік результатів ефективності оптимізації залежно від цієї потужності.
(команду підготує Матуш Калаш, [email protected])
Тема 13. Перколяція
Коли у вас не вистачає молока або порізаєтесь і у вас починається кровотеча, це насправді схожий процес. Так звані золь-гелевий перехід, перетворення рідини в напівтвердий, що відбувається внаслідок випадкового зчеплення молекул. Цей процес, аналогічний людям у натовпі, які випадково беруться за руки, є характерною особливістю явища перколяції.
Перколяція пов'язана з ім'ям П.Г. де Генне, щоб носити Нобелівську премію з фізики 1991 року, яка отримала її за роботу з теоретичної фізики пошкоджених матеріалів. Він описав перколяційний перехід так: "Багато явищ відбувається через випадкові острови, і за певних обставин між цими островами виникає один макроскопічний континент".
Перколяція - відносно поширене явище в природі. Зустрічається в хімічних системах (полімерні реакції), біологічних системах (імунологічні реакції) та фізичних системах (критичні явища). Витоки, просочування - це фізична теорія, яка дозволяє зрозуміти такі явища, як утворення кластерів, витікання з одного середовища в інше, використовуючи цю теорію для оцінки виходу нафтових родовищ тощо.
Випадкове прокручування сайту (RSP)
RSP складається з m x m у великій випадковій булевій решітці. Отже, ця сітка містить місця, де є одиниці та нулі. Місця з одиницею представляють зайняте місце, місця з нулем порожні. Ймовірність p того, що клітина зайнята, не залежить від її сусідів. Кластер тоді визначається як група зайнятих найближчих сусідніх клітин. (найближчий сусід означає місця ліворуч, праворуч, знизу та вгору від камери.
Прикладом кластера розміру 5 є:
Якщо припустити, що p - це ймовірність зайняття кожної комірки (тобто оцінка 1), яка очікувана кількість кластерів розміру 3 у сітці? (Ігнорувати крайові ефекти для простоти).
У більшості випадків неможливо визначити критичну ймовірність появи нескінченного скупчення (тобто такого, що простягається від одного боку сітки до іншого). Для звичайної квадратної сітки 64x64 експериментально визначте критичну ймовірність, перевіривши, чи з’явився «нескінченний кластер» для p (ймовірність від 0 до 1). Це можна дізнатися, створюючи випадкові конфігурації протягом фіксованої кількості разів, щоб отримати частку випадків, коли з’явився нескінченний кластер, і повторити цю процедуру для різних p. Покажіть ймовірність знаходження нескінченного скупчення проти ймовірності p .
(Відповідно до http: //www.krl.caltech.edu/
Тема 14. Генетичне програмування для мурах, які шукають шлях
Генетичне програмування для створення "програми" для мурах з використанням набору правил. Мураха повинен збирати їжу, посіяну на не зовсім суцільній доріжці, розташованій на тороїдальній сітці, тоді як у неї є лише обмежені датчики (тому він бачить лише бічні клітини сітки). Мураха повинен зібрати якомога більше їжі за певний проміжок часу. Подробиці завдання можна отримати за адресою http://www2.informatik.uni-erlangen.de/
jacob/Evolvica/GP/Java/html/ant/ant.html). Завдання полягає в тому, щоб сформувати правила а) для власного довільно згенерованого треку з подібними властивостями, як Trail John Muir з вищенаведеної веб-сторінки. б) Спробуйте створити правила, які застосовувались би одночасно до кількох смуг.
(команду підготує Олександра Така, [email protected])
Розроблені "кейси" у школі.р. 2001/2002
Олександра Такачі: Генетичне програмування для мурахи, який шукає шлях (кейс pdf, імплементація exe.zip)
Олександр Моравчик: Проблема планування завдання (pdf-приклад, реалізація exe.zip)
Ондрей Яура: Самоорганізація словника в середовищі агентів (кейс pdf)
Пітер Бодік: Лисиці, зайці та інші (кейс pdf)