Evolutie diferentiala

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 27 martie 2016; verificările necesită 15 modificări .

Evoluție diferențială ( ing. evoluție diferențială ) - o metodă de optimizare matematică multidimensională , aparținând clasei de algoritmi de optimizare stocastică (adică funcționează folosind numere aleatoare) și folosește unele idei de algoritmi genetici , dar, spre deosebire de acestea, nu necesită lucrul cu variabile în cod binar.

Aceasta este o metodă de optimizare directă, adică necesită doar capacitatea de a calcula valorile funcției obiectiv, dar nu și derivatele acesteia. Metoda evoluției diferențiale este concepută pentru a găsi minimul (sau maximul) global al funcțiilor nediferențiabile, neliniare, multimodale (posibil având un număr mare de extreme locale) ale multor variabile. Metoda este ușor de implementat și utilizat (conține puțini parametri de control care necesită selecție) și este ușor de paralelizat .

Metoda evoluției diferențiale a fost dezvoltată de Rainer Storn și Kenneth Price, publicată pentru prima dată de aceștia în 1995 [1] și dezvoltată în continuare în lucrările lor ulterioare. [2] [3]

Algoritm

În forma sa de bază, algoritmul poate fi descris după cum urmează. Inițial, un set de vectori, numit generație, este generat. Vectorii sunt puncte ale spațiului -dimensional în care este definită funcția obiectiv , care trebuie minimizată. La fiecare iterație, algoritmul generează o nouă generație de vectori prin combinarea aleatorie a vectorilor din generația anterioară. Numărul de vectori din fiecare generație este același și este unul dintre parametrii metodei. $n$ $f(x)$

Noua generație de vectori este generată după cum urmează. Pentru fiecare vector din vechea generație, trei vectori aleatori diferiți , , sunt selectați dintre vectorii vechei generații, cu excepția vectorului însuși , iar așa-numitul vector mutant este generat prin formula: $x_{i}$ $v_{1}$ $v_{2}$ $v_{3}$ $x_{i}$

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

unde este unul dintre parametrii metodei, o constantă reală pozitivă în intervalul [0, 2]. $F$

Pe vectorul mutant se efectuează o operație de încrucișare , care constă în înlocuirea unora dintre coordonatele acestuia cu coordonatele corespunzătoare din vectorul original (fiecare coordonată este înlocuită cu o anumită probabilitate, care este și unul dintre parametrii acestei metode). Vectorul obținut după încrucișare se numește vector de probă. Dacă se dovedește a fi mai bun decât vectorul (adică valoarea funcției obiectiv a devenit mai mică), atunci în noua generație vectorul este înlocuit cu un vector de probă, altfel rămâne . $v$ $x_{i}$ $x_{i}$ $x_{i}$ $x_{i}$

Exemple de aplicații practice

Motorul de căutare Yandex folosește metoda evoluției diferențiale pentru a-și îmbunătăți algoritmii de clasare. [4] [5]

Note

↑ Storn, Rainer și Price, Kenneth . Evoluție diferențială - O schemă adaptivă simplă și eficientă pentru optimizarea globală pe spații continue, arhivată la 24 aprilie 2005 în Raportul tehnic Wayback Machine TR -95-012 , ICSI, martie 1995.
↑ Storn, Rainer și Price, Kenneth . Evoluție diferențială - O euristică simplă și eficientă pentru optimizarea globală pe spații continue. Arhivat pe 6 ianuarie 2010 la Wayback Machine (1997)
↑ K. Price, R. Storn, J. Lampinen . Evoluție diferențială: o abordare practică a optimizării globale. Springer, 2005.
↑ Interviul lui A. Sadovsky pentru revista IT SPEC, iulie 2007. . Consultat la 3 octombrie 2009. Arhivat din original la 13 mai 2013. (nedefinit)
↑ A. Gulin și colaboratorii Yandex la ROMIP'2009. Optimizarea algoritmilor de clasare prin metode de învățare automată. . Consultat la 3 octombrie 2009. Arhivat din original pe 22 noiembrie 2009. (nedefinit)

Link-uri externe :

Descrierea și implementarea metodei pe site-ul unuia dintre autorii săi. Arhivat la 1 decembrie 2005 la Wayback Machine
S. Luca . Esențiale ale metaeuristicii. Capitolul 3.4.

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbare medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG