Differentiaalinen evoluutio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 27. maaliskuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 15 muokkausta .

Differentiaalinen evoluutio ( eng. differential evolution ) - moniulotteisen matemaattisen optimoinnin menetelmä , joka kuuluu stokastisten optimointialgoritmien luokkaan (eli toimii satunnaislukujen avulla) ja käyttää joitain geneettisten algoritmien ideoita , mutta toisin kuin ne, ei vaadi Työskentely muuttujien kanssa binäärikoodissa.

Tämä on suora optimointimenetelmä, eli se vaatii vain kykyä laskea tavoitefunktion arvot, mutta ei sen johdannaisia. Differentiaalinen evoluutiomenetelmä on suunniteltu löytämään globaali minimi (tai maksimi) monien muuttujien ei-differentoiville, epälineaarisille, multimodaalisille (joissa on mahdollisesti suuri määrä paikallisia äärimmäisiä) funktioita. Menetelmä on helppo toteuttaa ja käyttää (sisältää muutamia valintaa vaativia ohjausparametreja) ja se on helposti rinnastettavissa .

Rainer Storn ja Kenneth Price kehittivät differentiaalisen evoluution menetelmän, jonka he julkaisivat ensimmäisen kerran vuonna 1995 [1] ja kehittivät edelleen myöhemmässä työssään. [2] [3]

Algoritmi

Perusmuodossaan algoritmi voidaan kuvata seuraavasti. Aluksi generoidaan jokin joukko vektoreita, joita kutsutaan sukupolveksi. Vektorit ovat -ulotteisen avaruuden pisteitä, joissa tavoitefunktio määritellään , mikä tulee minimoida. Jokaisessa iteraatiossa algoritmi luo uuden sukupolven vektoreita yhdistämällä satunnaisesti edellisen sukupolven vektoreita. Vektorien lukumäärä kussakin sukupolvessa on sama ja se on yksi menetelmän parametreista. $n$ $f(x)$

Uusi vektorien sukupolvi generoidaan seuraavasti. Jokaiselle vanhan sukupolven vektorille valitaan vanhan sukupolven vektoreista kolme erilaista satunnaisvektoria , paitsi itse vektori , ja ns. mutanttivektori generoidaan kaavalla: $x_{i}$ $v_{1}$ $v_{2}$ $v_{3}$ $x_{i}$

v=v_{1}+F\cpiste(v_{2}-v_{3}),

jossa on yksi menetelmäparametreista, jokin positiivinen reaalivakio välillä [0, 2]. $F$

Mutanttivektorille suoritetaan risteysoperaatio, jossa jotkin sen koordinaatit korvataan vastaavilla alkuperäisen vektorin koordinaatteilla (jokainen koordinaatti korvataan tietyllä todennäköisyydellä, mikä on myös yksi tämän menetelmän parametreista). Risteyksen jälkeen saatua vektoria kutsutaan koevektoriksi . Jos se osoittautuu paremmaksi kuin vektori (eli tavoitefunktion arvo on pienentynyt), niin uudessa sukupolvessa vektori korvataan koevektorilla, muuten se jää . $v$ $x_{i}$ $x_{i}$ $x_{i}$ $x_{i}$

Esimerkkejä käytännön sovelluksista

Yandex - hakukone käyttää differentiaalisen evoluution menetelmää parantaakseen sijoitusalgoritmejaan. [4] [5]

Muistiinpanot

↑ Storn, Rainer ja Price, Kenneth . Differentiaalikehitys – Yksinkertainen ja tehokas mukautuva järjestelmä globaaliin optimointiin jatkuvissa tiloissa, arkistoitu 24. huhtikuuta 2005 Wayback Machinen teknisessä raportissa TR -95-012 , ICSI, maaliskuu 1995.
↑ Storn, Rainer ja Price, Kenneth . Differentiaalinen evoluutio – Yksinkertainen ja tehokas heuristinen globaali optimointi jatkuvissa tiloissa. Arkistoitu 6. tammikuuta 2010 Wayback Machinessa (1997)
↑ K. Price, R. Storn, J. Lampinen . Differentiaalinen evoluutio: Käytännön lähestymistapa globaaliin optimointiin. Springer, 2005.
↑ A. Sadovskyn haastattelu IT SPEC -lehdelle, heinäkuu 2007. . Haettu 3. lokakuuta 2009. Arkistoitu alkuperäisestä 13. toukokuuta 2013. (määrätön)
↑ A. Gulin ym. Yandex at ROMIP'2009. Ranking-algoritmien optimointi koneoppimismenetelmillä. . Haettu 3. lokakuuta 2009. Arkistoitu alkuperäisestä 22. marraskuuta 2009. (määrätön)

Ulkoiset linkit :

Menetelmän kuvaus ja toteutus yhden sen kirjoittajan sivustolla. Arkistoitu 1. joulukuuta 2005 Wayback Machinessa
S. Luke . Metaheuristics Essentials. Luku 3.4.

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi

Koneoppiminen ja tiedon louhinta
Tehtävät	Luokittelu ongelma Oppiminen ilman opettajaa Opettajan avustama oppiminen Taantumisanalyysi AutoML Yhdistyksen säännöt Ominaisuuksien erottaminen Ominaisuuksien koulutus Ranking koulutus Kieliopillinen johtaminen Verkko-oppiminen
Opettajan kanssa oppimista	k-lähimmän naapurin menetelmä Naiivi Bayesin luokitin päätöspuu Tuki vektorikonetta Lineaarinen regressio Logistinen regressio perceptron Mallien kokoonpanot Pussittaminen tehostaa satunnainen metsä Asiaankuuluva vektorimenetelmä
ryhmäanalyysi	k-keinomenetelmä Sumea klusterointimenetelmä Hierarkkinen klusterointi EM-algoritmi KOIVU PARANTAA DBSCAN OPTIIKKA Keskimääräinen siirto
Mittasuhteiden vähentäminen	Tekijäanalyysi Pääkomponenttimenetelmä CCA ICA LDA Ei-negatiivinen matriisin laajennus t-SNE
Rakenteellinen ennustaminen	Graafinen todennäköisyysmalli Bayesin verkko Piilotettu Markovin malli CRF
Anomalian havaitseminen	k-lähimmän naapurin menetelmä Paikallinen päästötaso
Piirrä todennäköisyysmallit	Bayesin verkko Markovin verkko Piilotettu Markovin malli
Neuroverkot	Rajoitettu Boltzmann-kone itseorganisoituva kartta Aktivointitoiminto Sigmoidi softmax Radiaalinen kantafunktio Takaisin lisäysmenetelmä Syväoppiminen Monikerroksinen perceptroni Toistuva neuroverkko pitkä lyhytaikainen muisti Hallittu toistuva esto Konvoluutiohermoverkko U-verkko Autoenkooderi
Vahvistusoppiminen	Markovin prosessi Bellmanin yhtälö Ahne algoritmi Q-oppiminen SARSA Aikaero (TD)
Teoria	Vapnik-Chervonenkis teoria Bias-dispersion dilemma Laskennallinen oppimisteoria Empiirinen riskin minimointi Occam oppii PAC-oppiminen Tilastollinen oppimisteoria
Lehdet ja konferenssit	NeurIPS ICML ML JMLR ArXiv:cs.LG