Diferenciální evoluce ( angl. Differential evolution ) - metoda vícerozměrné matematické optimalizace , patřící do třídy stochastických optimalizačních algoritmů (tj. pracuje s náhodnými čísly) a využívá některé myšlenky genetických algoritmů , ale na rozdíl od nich nevyžaduje práce s proměnnými v binárním kódu.
Jedná se o přímou optimalizační metodu, to znamená, že vyžaduje pouze schopnost vypočítat hodnoty účelové funkce, ale ne její deriváty. Metoda diferenciální evoluce je navržena tak, aby nalezla globální minimum (nebo maximum) nediferencovatelných, nelineárních, multimodálních (možná s velkým počtem lokálních extrémů) funkcí mnoha proměnných. Metoda se snadno implementuje a používá (obsahuje několik řídicích parametrů, které vyžadují výběr) a lze ji snadno paralelizovat .
Metodu diferenciální evoluce vyvinuli Rainer Storn a Kenneth Price, poprvé ji publikovali v roce 1995 [1] a dále ji rozvinuli ve své pozdější práci. [2] [3]
Ve své základní podobě lze algoritmus popsat následovně. Zpočátku se vygeneruje nějaká sada vektorů, nazývaná generace. Vektory jsou body -rozměrného prostoru, ve kterém je definována účelová funkce , která má být minimalizována. Při každé iteraci generuje algoritmus novou generaci vektorů náhodným kombinováním vektorů z předchozí generace. Počet vektorů v každé generaci je stejný a je jedním z parametrů metody.
Nová generace vektorů se generuje následovně. Pro každý vektor ze staré generace jsou mezi vektory staré generace vybrány tři různé náhodné vektory , , s výjimkou samotného vektoru , a takzvaný mutantní vektor je generován podle vzorce:
kde je jeden z parametrů metody, nějaká kladná reálná konstanta v intervalu [0, 2].
Na mutantním vektoru je provedena operace křížení , která spočívá v nahrazení některých jeho souřadnic odpovídajícími souřadnicemi z původního vektoru (každá souřadnice je nahrazena s určitou pravděpodobností, což je také jeden z parametrů této metody). Vektor získaný po křížení se nazývá zkušební vektor. Pokud se ukáže, že je lepší než vektor (to znamená, že hodnota účelové funkce se zmenšila), pak je v nové generaci vektor nahrazen zkušebním vektorem, jinak zůstává .
Vyhledávač Yandex používá metodu diferenciální evoluce ke zlepšení svých hodnotících algoritmů. [4] [5]
Externí odkazy :
Optimalizační metody | |
---|---|
Jednorozměrný |
|
Nulové pořadí | |
První objednávka | |
druhá objednávka | |
Stochastické | |
Metody lineárního programování | |
Metody nelineárního programování |
Strojové učení a dolování dat | |
---|---|
Úkoly | |
Učení s učitelem | |
shluková analýza | |
Redukce rozměrů | |
Strukturální prognózy | |
Detekce anomálií | |
Grafové pravděpodobnostní modely | |
Neuronové sítě | |
Posílení učení |
|
Teorie | |
Časopisy a konference |
|