Diferenciální evoluce

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 27. března 2016; kontroly vyžadují 15 úprav .

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]

Algoritmus

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á .

Příklady praktických aplikací

Vyhledávač Yandex používá metodu diferenciální evoluce ke zlepšení svých hodnotících algoritmů. [4] [5]

Poznámky

  1. Storn, Rainer a Price, Kenneth . Diferenciální evoluce – jednoduché a efektivní adaptivní schéma pro globální optimalizaci přes spojité prostory, archivováno 24. dubna 2005 v technické zprávě Wayback Machine TR -95-012 , ICSI, březen 1995.
  2. Storn, Rainer a Price, Kenneth . Diferenciální evoluce – jednoduchá a účinná heuristika pro globální optimalizaci přes spojité prostory. Archivováno 6. ledna 2010 na Wayback Machine (1997)
  3. K. Price, R. Storn, J. Lampinen . Diferenciální evoluce: Praktický přístup ke globální optimalizaci. Springer, 2005.
  4. Rozhovor A. Sadovského pro časopis IT SPEC, červenec 2007. . Získáno 3. října 2009. Archivováno z originálu 13. května 2013.
  5. A. Gulin a kol. , Yandex na ROMIP'2009. Optimalizace hodnotících algoritmů metodami strojového učení. . Získáno 3. října 2009. Archivováno z originálu 22. listopadu 2009.

Externí odkazy :