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.
  1. Migrační GA
    1. řetěz
    2. kruh
    3. mřížka
    4. 2D-torus
    5. hyperkostka
    6. plné propojení
    7. křížový přepínač
  2. Difuzní GA
    1. řetěz
    2. kruh
    3. mřížka
    4. 2D-torus
    5. hyperkostka
    6. 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:

Ř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