Опаковането е класически проблем за оптимизация. Да предположим, че разполагаме с камион, способен да превозва произволен брой кутии, стига общото им тегло да не надвишава W. Имате неограничен брой различни видове стоки в склада. Всеки тип елемент i има тегло w i и стойност v i. Вашият проблем е да определите коя комбинация от обекти ще постигне най-висока стойност, без да надвишава максимално допустимото общо тегло. Например, когато теглото и стойностите са
тогава камион с максимална товароносимост W = 200 може да превозва:
Най-добрата стратегия е да заредите колкото се може повече кутии портокали, а останалите да напълните с книги. Решете проблема за по-голям брой елементи с произволно дефинирани стойности и тегла с помощта на генетичен алгоритъм, с ограничен брой някои елементи, измислете вашето собствено представяне на проблема и съответните хромозоми, мутации и омрежени алгоритми . (Адаптиран от http://www.epcc.ed.ac.uk/epic/ga/intro.html)
.
Тема 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 клетките на решетката), а алфа е т.нар. критичен експонент
- Коя е най-дългата лавина, която можете да изградите върху решетка 5x5? Първоначалното състояние може да има максимум 3 зърна пясък върху решетката и едно четвърто зърно може да бъде добавено към клетката, за да стартира лавината. Възможно ли е да се изгради безкраен цикъл? Защо? (Или защо не?)
- Експериментално определете алфа коефициента (това се прави най-добре чрез създаване на голям брой лавини и запазване на размерите им. След това намерете броя на лавините за всеки размер - необходими са много изчисления за добри резултати. И накрая, покажете резултатите в дневник, чийто наклон е равно на минус алфа.
- Ако увеличите площта до всички 8 съседи и увеличите критичния брой зърна до 8, тази степен ще се увеличи. Което причинява тази промяна?
Тема 6. Проблемът за общата удовлетворимост (SAT), дори ако обхващаме всякакви логически клаузи, а не само конюнкции и дизюнкции. Всеки проблем се състои от 20 булеви променливи (A0 - A19) и набор от ограничения. Целта, разбира се, е да се намери вярно присвояване на всяка променлива, така че всички ограничения да бъдат изпълнени. Най-добрите решения на тези проблеми са тривиални за хората, но GA не разполага с нашите познания по логика и трябва да търси широко. Начертайте графика на сила (мин., Макс. И средна стойност) за всеки от пробезите на GA.
А) 5 връзки, ограниченията са
(A0 и A1 и A2 и A3)
(A4 и A5 и A6 и A7)
(A8 и A9 и A10 и A11)
(A12 и A13 и A14 и A15)
(A16 и A17 и A18 и A19)
- Опишете вашето представяне и функцията на сила. Във вашето представяне колко голямо е пространството за търсене?
- Опишете разликите в поведението на GA при използване на популация от 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)
д) Изпълнете този проблем при същите условия като a, със същата фитнес функция. Какви са разликите? Защо има разлики, дори ако ограниченията са логически еквивалентни? Можете да използвате функцията за фитнес, използвана за обяснение на разликата?
е) Изпълнете този проблем с население от 100, 100 поколения, pcross = 0,8, с две различни стойности на pmut: 0,1 и 0,01. Какви са разликите? Можете да обясните защо са се появили?
ж) Проектирайте нова фитнес функция, значително различна от първата, и я тествайте за а) и д) с население от 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)
з) Тест с популация с размер 100, 100 поколения, pcross = 0,8, pmut: 0,1. и с двете от предложените ви фитнес функции обяснете разликите в поведението.
(екипът ще бъде подготвен от Pavol Љupa, [email protected])
Тема 7. Използвайте симулирано отгряване, за да решите движението на котка на шахматна дъска, където трябва да изпълните всички останали полета от въведеното поле, като едновременно влизате във всяко поле. Като втората част на задачата решете същия проблем с условието, че котката трябва да се върне. Когато решавате, използвайте смущение (мутация) от вида, който копирате началото на последователността от полета в произволно избран брой полета в ново решение и генерирайте останалите. Задачата може да бъде решена и с обратното сърфиране, но само за малки случаи.
(екипът ще бъде подготвен от Tomáš Pail, [email protected])
Тема 8. Оценете въздействието на стратегиите за подбор върху оптимизацията, като използвате дефинициите на
за преизчисляване на силата пропорционално (виж формула 4.11в в книгата „Еволюционни алгоритми“) или въз основа на подреждането според размера (формула 4.12б) и собствен избор по рулетка, турнир, като се използва т.нар. с тохастично универсално вземане на проби, локален подбор, подсичане, описано в
Оценете въздействието на стратегиите за подбор върху оптимизацията на следните мултимодални функции (за 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)
Според Kidwell (1993) минималното време за изпълнение на задачи на 3 процесора с един комуникационен канал е 202 времеви стъпки. Опитайте се да намерите това решение с вашия генетичен алгоритъм, докато е важно да изберете вашата фитнес функция. Опишете успеха с помощта на графики, базирани на стойности на ключови параметри като степен на мутация и процент на преминаване, брой точки на преминаване, размер на популацията и механизъм за подбор. (Според http://www.idi.ntnu.no/
(екипът ще бъде подготвен от Александър Моравчик, [email protected])
Тема 12. Алгоритми на мравки
като основа за вашия алгоритъм, където за вероятностите за вземане и изпускане на върха и
използвайте мощности, различни от квадрата и покажете графиката на резултатите от ефективността на оптимизацията в зависимост от тази мощност.
(екипът ще бъде подготвен от Matúš Kalaš, [email protected])
Тема 13. Перколация
Когато останете без мляко или се режете и започнете да кървите, това всъщност е подобен процес. Така нареченият зол-гел преход, превръщането на течност в полутвърдо вещество, което е резултат от произволно свързване на молекули. Този процес, който е аналогичен на хората в тълпата, които се включват на случаен принцип, е характерна черта на феномена на просмукване.
Перколацията е свързана с името P.G. де Генес, за да получи Нобелова награда за физика през 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). Задачата е да генерирате правила а) за вашата собствена произволно генерирана писта със сходни свойства като John Muir Trail от горната уеб страница. б) Опитайте да генерирате правила, които да се прилагат едновременно за множество ленти.
(екипът ще бъде подготвен от Aleksandra Taká, [email protected])
Разработени „казуси“ в šk.r. 2001/2002
Александра Такачи: Генетично програмиране за мравка, която търси начин (казус pdf, изпълнение exe.zip)
Александър Моравчик: Проблем с планирането на задачите (пример за pdf, изпълнение exe.zip)
Ondrej Jaura: Самоорганизация на речник в общността на агентите (казус pdf)
Питър Бодик: Лисици, зайци и други (казус pdf)