Projekt 2
Paralelní genetický algoritmus
Simulujte v Transimu výpočet vybraného typu paralelního genetického
algoritmu na některé z uvedených paralelních architektur.
- Migrační GA
- řetěz
- kruh
- mřížka
- 2D-torus
- hyperkostka
- plné propojení
- křížový přepínač
- Difuzní GA
- řetěz
- kruh
- mřížka
- 2D-torus
- hyperkostka
- plné propojení
Popis genetického algoritmu
Výpočet GA probíhá nad populací chromozómů (řetězce bytů). V každé
generaci jsou vygenerováni noví jedinci (chromozómy), kteří nahrazují starší
jedince v současné populaci. Pro výběr jedinců do další generace je každému
jedinci přiřazena jeho zdatnost (funkce fitness), která se vyhodnocuje pro každého
nového jedince.
Noví jedinci se obvykle vytvářejí ze současných jedinců křížením
dvojic chromozómů. Dále se s jedinci provádějí mutace (drobné náhodné
změny chromozómů).
Migrační genetický algoritmus
Tento typ GA pracuje s několika subpopulacemi, které se vyvíjejí relativně
samostatně. Každou populaci si spravuje jeden procesor. Pokaždé po provedení
několika generací si procesory mezi sebou vymění několik zdatných jedinců,
aby se umožnilo vzájemné křížení perspektivních jedinců z různých
subpopulací. Obvykle si takto vyměňují jedince procesory, které jsou si v
dané topologii blízké nebo spolu přímo sousedí (jsou propojeny komunikačním
kanálem).
Difuzní genetický algoritmus
V případě difuzního GA vlastní jednotlivé procesory pouze po jednom
jedinci. V každé generaci provede každý z procesorů tyto kroky:
- pošle všem svým sousedům vlastního jedince
- z přijatých jedinců a ze svého vybere vhodné rodiče pro křížení
- provede křížení a mutaci
- ponechá si pouze nově vytvořeného jedince
Řešení
Odlaďte program a zjistěte jeho zrychlení (využití procesorů) S = S(P) a E
= E(P) = S(P)/P pro různý počet procesorů. Zvolte vhodné parametry
algoritmu jako délka chromozómu, doba výpočtu fitness (např. lineární závislost
na délce chromozómu), doba výpočtu křížení a mutace, počet generací
(konstatní, např. 100).
Přihlašování
Na každé zadání se mohou přihlásit maximálně 2 lidé, kteří je budou
vypracovávat samostatně. Přihlašování bude probíhat stejným způsobem,
jako u prvního projektu, ale tentokrát na adresu staroba@fit.vutbr.cz.
Jako předmět dopisu použijte "PPP projekt 2"
Body
Za projekt lze získat až 7 bodů.
Odevzdání
Projekt se bude odevzdávat jako příloha dopisu s předmětem "PPP
projekt 2" na adresu staroba@fit.vutbr.cz
. Odevzdává se kód programu v Transimu a graf S(P) a E(P).
Poslední změna: 24. 03. 2003