Differentiell evolution

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 mars 2016; kontroller kräver 15 redigeringar .

Differential evolution ( eng. differential evolution ) - en metod för multidimensionell matematisk optimering , som tillhör klassen av stokastiska optimeringsalgoritmer (det vill säga den fungerar med slumptal) och använder vissa idéer om genetiska algoritmer , men kräver, till skillnad från dem, inte arbeta med variabler i binär kod.

Detta är en direkt optimeringsmetod, det vill säga den kräver bara förmågan att beräkna målfunktionens värden, men inte dess derivator. Metoden för differentiell evolution är utformad för att hitta det globala minimum (eller maximum) av icke-differentiera, icke-linjära, multimodala (möjligen med ett stort antal lokala extrema) funktioner för många variabler. Metoden är enkel att implementera och använda (innehåller få kontrollparametrar som kräver urval), och är lätt att parallellisera .

Metoden för differentiell evolution utvecklades av Rainer Storn och Kenneth Price, publicerades först av dem 1995 [1] och vidareutvecklades i deras senare arbete. [2] [3]

Algoritm

I sin grundform kan algoritmen beskrivas enligt följande. Initialt genereras någon uppsättning vektorer, kallad generation. Vektorer är punkter i det dimensionella utrymme där den objektiva funktionen är definierad , som ska minimeras. Vid varje iteration genererar algoritmen en ny generation av vektorer genom att slumpmässigt kombinera vektorer från den föregående generationen. Antalet vektorer i varje generation är detsamma och är en av parametrarna för metoden. $n$ $f(x)$

Den nya generationen av vektorer genereras enligt följande. För varje vektor från den gamla generationen väljs tre olika slumpmässiga vektorer , , ut bland vektorerna från den gamla generationen, med undantag för själva vektorn , och den så kallade mutantvektorn genereras med formeln: $x_{i}$ $v_{1}$ $v_{2}$ $v_{3}$ $x_{i}$

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

där är en av metodparametrarna, någon positiv reell konstant i intervallet [0, 2]. $F$

En crossover-operation utförs på mutantvektorn , som består i att ersätta några av dess koordinater med motsvarande koordinater från den ursprungliga vektorn (varje koordinat ersätts med en viss sannolikhet, vilket också är en av parametrarna för denna metod). Vektorn som erhålls efter korsning kallas en försöksvektor. Om det visar sig vara bättre än vektorn (det vill säga värdet på objektivfunktionen har blivit mindre), så ersätts vektorn i den nya generationen av en försöksvektor, annars förblir den . $v$ $x_{i}$ $x_{i}$ $x_{i}$ $x_{i}$

Exempel på praktiska tillämpningar

Yandex sökmotor använder differential evolution-metoden för att förbättra sina rankningsalgoritmer. [4] [5]

Anteckningar

↑ Storn, Rainer och Price, Kenneth . Differential Evolution - A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces, Arkiverad 24 april 2005 på Wayback Machine Technical Report TR- 95-012 , ICSI, mars 1995.
↑ Storn, Rainer och Price, Kenneth . Differential Evolution - En enkel och effektiv heuristik för global optimering över kontinuerliga utrymmen. Arkiverad 6 januari 2010 på Wayback Machine (1997)
↑ K. Price, R. Storn, J. Lampinen . Differential Evolution: A Practical Approach to Global Optimization. Springer, 2005.
↑ Intervju av A. Sadovsky till tidskriften IT SPEC, juli 2007. . Hämtad 3 oktober 2009. Arkiverad från originalet 13 maj 2013. (obestämd)
↑ A. Gulin et al. Yandex på ROMIP'2009. Optimering av rankningsalgoritmer genom maskininlärningsmetoder. . Hämtad 3 oktober 2009. Arkiverad från originalet 22 november 2009. (obestämd)

Externa länkar :

Beskrivning och implementering av metoden på webbplatsen för en av dess författare. Arkiverad 1 december 2005 på Wayback Machine
S. Luke . Essentials of Metaheuristics. Kapitel 3.4.

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powells metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering

Maskininlärning och datautvinning
Uppgifter	Klassificeringsproblem Lärande utan lärare Lärarassisterat lärande Regressionsanalys AutoML Föreningens regler Särdragsextraktion Egenskapsträning Ranking utbildning Grammatisk härledning Online lärande
Att lära sig med en lärare	k-närmaste granne metod Naiv Bayes klassificerare beslutsträd Stöd vektor maskin Linjär regression Logistisk tillbakagång perceptron Ensembler av modeller Säckväv förstärkning slumpmässig skog Relevant vektormetod
klusteranalys	k-betyder metod Fuzzy klustringsmetod Hierarkisk klustring EM algoritm BJÖRK BOTA DBSCAN OPTIK Genomsnittlig förskjutning
Dimensionalitetsreduktion	Faktoranalys Huvudkomponentmetoden CCA ICA LDA Icke-negativ matrisexpansion t-SNE
Strukturell prognos	Graph probabilistisk modell Bayesiskt nätverk Dold Markov-modell CRF
Anomali upptäckt	k-närmaste granne metod Lokal utsläppsnivå
Grafisk probabilistiska modeller	Bayesiskt nätverk Markov nätverk Dold Markov-modell
Neurala nätverk	Begränsad Boltzmann-maskin självorganiserande karta Aktiveringsfunktion Sigmoid softmax Radiell basfunktion Ryggförökningsmetod Djup lärning Flerskiktsperceptron Återkommande neurala nätverk långtidsminne Kontrollerat återkommande block Konvolutionellt neuralt nätverk U-Net Autokodare
Förstärkningsinlärning	Markov process Bellmans ekvation Girig algoritm Q-lärande SARSA Temporell skillnad (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beräkningslärandeteori Empirisk riskminimering Occam lär sig PAC-inlärning Statistisk inlärningsteori
Tidskrifter och konferenser	NeurIPS ICML ML JMLR ArXiv:cs.LG