[CZ] Spojitá optimalizace II - diferenciální evoluce

Na minulých cvičeních jsme se začali zabývat spojitou optimalizací a řekli jsme si, že některé vlastnosti optimalizovaných funkcí způsobují, že jednoduché genetické operátory nefungují při jejich optimalizaci moc dobře. Mezi tyto vlastnosti patří především vysoká podmíněnost a neseparabilita.

Diferenciální evoluce se snaží řešit tento problém relativně jednoduchým způsobem. Zavádí mutaci, která k danému jedinci přičítá rozdíl jiných dvou jedinců náhodně vybraných z populace vynásobený parametrem F. Jestliže je tedy funkce protažená nějakým směrem v prohledávaném prostoru, měla by stejným směrem být (díky selekci) protažena i populace evolučního algoritmu. Rozdíl dvou náhodných jedinců tedy bude vektor, který pravděpodobně ukazuje tím samým směrem a přičtení jeho části povede k tomu, že se jedinec změní nejčastěji právě ve směru, kde je potřeba dělat největší změny. Díky tomuto způsobu mutace je také diferenciální evoluce invariantní vzhledem k rotacím prohledávaného prostoru a vzhledem ke škálování os.

Diferenciální evoluce také používá křížení. To funguje tak, že se vybere další náhodný jedinec (rodič) z populace, ten se prochází zároveň s výsledkem mutace a s pravděpodobností 1-CR se do zmutovaného jedince přenese číslo ze stejné pozice v rodiči. (CR je pravděpodobnost, že se pozice ve zmutovaném jedinci nezmění). Vždy se přenese alespoň jedna hodnota.

Nakonec má diferenciální evoluce i vlastní selekci, při té se porovná původní jedinec (před mutací) s jedincem, který vznikne po křížení a lepší z těchto dvou přežívá do další generace.

Nastavení parametrů F a CR má velký vliv na úspěšnost diferenciální evoluce. Typické hodnoty jsou F=0.8 a CR=0.9. Pro separabilní funkce se zdá lepší nižší hodnota CR=0.2. Potom většina pozic v jedinci má hodnotu z posledního rodiče. Je také možné (a pomáhá) volit hodnotu F náhodně z intervalu [0.5, 1.0].

Někdy se místo celé diferenciální evoluce z ní použije jen mutace a ostatní operátory a selekce se použijí jiné.

Last modified: Monday, 19 November 2018, 10:37 AM