1. Uvod

Diferencijska evolucija (DE) je stohastički, populacijski, optimizacijski evolucijski algoritam koji su uveli Storn i Price 1996. godine. Napravljen je za optimiziranje funkcija s realnim varijablama (eng. real valued functions).
Po svojim značajkama, DE je najbliža evolucijskoj strategiji (tip (μ/ρ + λ) - ES). Njihova glavna razlika leži u mutaciji. Dok kod ES mutacija djeluje na samo jednu jedinku, kod DE mutacija djeluje na sve jedinke (vektore) u populaciji. Slučajno se odaberu 3 vektora, te napravi zbrajanje jednog vektora s težinskom razlikom druga dva vektora. Prema toj razlici (diferencija), DE je dobio ime. Rekombinacija DE je križanje u D točaka jer ovisi o slučajno odabranim realnim brojevima iz intervala [0,1]. [4]

Formulacija općenitog problema optimizacije glasi:
Za funkciju dobrote

(1.1)

gdje skup svih mogućih rješenja optimizacijskog problema X (eng. feasible region) nije prazan.
Minimizacijski problem je pronalazak:

(1.2)

Funkcija dobrote (eng. objective function) se ponekad naziva funkcija cijene (eng. cost function).

2. Opis algoritma

2.1 Pseudokod

Slika 2.1. Pseudokod

2.2 Notacija i algoritam ukratko

Traži se optimizacija funkcije f s D realnih parametara. Odabere se veličina populacije Np (koja mora biti veća od 3). Parametri vektora (eng. parameter vectors) su oblika:

(2.1)

gdje je G broj generacije. Koriste se 3 vektora:

Ciljni vektor (eng. target vector)

Donorski vektor (eng. donor vector)

Probni vektor (eng. trial vector)

Donorski vektor nastaje slučajnim odabirom 3 ciljna vektora , kada se napravi zbrajanje jednog vektora s težinskom razlikom druga dva vektora (mutacija). Probni vektor nastaje od elemenata ciljnog vektora i elemenata donorskog vektora (rekombinacija). Ciljni vektor nastaje selekcijom između probnog vektora i ciljnog vektora (selekcija).

2.3 Inicijalizacija

Definiranje gornje i donje granice za svaki parametar j :

(2.2)

Slučajnim odabirom inicijaliziraju se vrijednosti parametara uniformno na intervalu .
Svaki od Np parametara vektora prolazi kroz mutaciju, rekombinaciju i selekciju kao što je vidljivo na slici 2.1.

2.4 Mutacija

Mutacija proširuje prostor potrage rješenja (eng. search space). Za dani parametar vektora slučajno se odaberu tri vektora , , s međusobno različitim indeksima.
Izračuna se:

(2.3)

je donorski vektor (eng. donor vector).
Mutacijski faktor F je konstanta na intervalu [0,2]. On kontrolira brzinu i robusnost potrage rješenja.
Tj. manja vrijednost povećava vjerojatnost konvergencije, ali povećava i rizik zaustavljanja u lokalnom ekstremu.

2.4.1 Varijacije mutacije

Umjesto slučajno odabranog odabere se najbolji. [2] Umjesto jednog oduzimanja, odabere se više vektora radi bolje varijacije:

(2.4)

2.5 Rekombinacija

Uključuje uspješna rješenja od prijašnje generacije. Probni vektor (eng. trial vector) nastaje od elemenata ciljnog vektora (eng. target vector) i elemenata donorskog vektora .
predstavlja slučajno odabran broj iz intervala [1,2,...,D]. Vjerojatnost križanja (eng. crossover) CR je konstanta na intervalu [0, 1]. Parametar vektora s indeksom j = će biti jednak . uvijek osigurava različitost i (tj. ) i onda kada je CR jednak nuli. Elementi donorskog vektora ulaze u probni vektor s vjerojatnošću CR.

(2.5)

gdje su:

2.6 Selekcija

Ciljni vektor se uspoređuje s probnim vektorom , te onaj s većom dobrotom (tj. manjom funkcijskom vrijednosti) prolazi u slijedeću generaciju

(2.6)

Budući da se prosječna funkcijska vrijednost nikad neće pogoršati, selekcija je elitizam.
Mutiranje, rekombinacija i selekcija se nastavljaju sve dok nije zadovoljen neki uvjet zaustavljanja, koji je najčešće broj odrađenih generacija ili dovoljno dobra vrijednost funkcije cijene. U uvjetu zaustavljanja algoritma zadaje se potrebna točnost rezultata ili sigurnost ispravnosti rezultata. Npr. veći broj odrađenih generacija poboljšava ispravnost rezultata, ali potrebno vrijeme izvršavanja algoritma se produljuje.

3. Primjene algoritma

Globalna optimizacija je potrebna u raznim poljima, poput inženjerstva, statistike i financija. Mnogi praktični problemi imaju funkcije dobrote koje nisu diferencijalne, kontinuirane, linearne ni predvidljive. Takve funkcije su često i višedimenzionalne, te imaju šumove i mnogo lokalnih ekstrema i ograničenja. Takvi problemi se mogu teško ili nikako riješiti analitički. DE se može upotrijebiti radi pronalaska približnog rješenja za takve probleme. [1]

4. Zaključak

Ne postoji dokaz konvergencije DE, ali u praksi je djelotvoran za mnoge optimizacijske probleme. Storn i Price (1997) su usporedbom pokazali da je učinkovitiji od simuliranog kaljenja i genetskih algoritama. Ali i Torn (2004) su otkrili da je DE točniji i učinkovitiji od kontrolirane slučajne potrage i drugog genetskog algoritma. 2004. godine Lampinen i Storn su pokazali da je DE točniji (eng. accurate) od nekoliko drugih optimizacijskih metoda uključujući genetske algoritme, simulirano kaljenje i evolucijsko programiranje. [1]

4.1 Prednosti

dostupnost za praktične aplikacije

jednostavna struktura

lakoća uporabe

brzina dolaska do rješenja

otpornost na manja odstupanja (robusnost)

4.2 Nedostaci

Manji problemi nastaju kod:

nediferencijabilnih funkcija u nekim točkama

funkcija s mnogo lokalnih ekstrema, koje su djelomično okružene ravnom plohom

U takvim slučajevima, najbolje rješenje ostaje izvan prostora potrage rješenja.

5. Literatura

[1] Kelly Fleetwood – An Introduction to Differential Evolution, http://www.maths.uq.edu.au/MASCOS/Multi-Agent04/Fleetwood.pdf, 25.10.2008
[2] David Craft – Differential Evolution: a stochastic nonlinear optimization algorithm by Storn and Price, http://www.technorati.com/search/ses2_storn_price.pdf, 25.10.2008
[3] http://www.icsi.berkeley.edu/~storn/code.html, 25.10.2008
[4] Projekt 2007/2008: Evolucijski algoritmi – Evolucijske strategije, http://www.zemris.fer.hr/~golub/ga/studenti/projekt2007/es.html, 25.10.2008
[5] Napapan Piyasatian – Differential Evolution: A Simple Evolution Strategy for Fast Optimization, http://www-personal.une.edu.au/~jvanderw/DE_1.pdf, 25.10.2008