Differentiel evolution

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. marts 2016; checks kræver 15 redigeringer .

Differential evolution ( eng. differential evolution ) - en metode til multidimensionel matematisk optimering , der tilhører klassen af stokastiske optimeringsalgoritmer (det vil sige, den virker ved hjælp af tilfældige tal) og bruger nogle ideer om genetiske algoritmer , men kræver i modsætning til dem ikke arbejde med variable i binær kode.

Dette er en direkte optimeringsmetode, det vil sige, den kræver kun evnen til at beregne værdierne af den objektive funktion, men ikke dens derivater. Metoden med differentiel evolution er designet til at finde det globale minimum (eller maksimum) af ikke-differentierbare, ikke-lineære, multimodale (muligvis have et stort antal lokale ekstrema) funktioner af mange variable. Metoden er nem at implementere og bruge (indeholder få kontrolparametre, der kræver udvælgelse), og er let paralleliseret .

Den differentielle evolution metode blev udviklet af Rainer Storn og Kenneth Price, først udgivet af dem i 1995 [1] og videreudviklet i deres senere arbejde. [2] [3]

Algoritme

Algoritmen kan i sin grundform beskrives som følger. Til at begynde med genereres et sæt vektorer, kaldet en generation. Vektorer er punkter i det dimensionelle rum, hvori den objektive funktion er defineret , som skal minimeres. Ved hver iteration genererer algoritmen en ny generation af vektorer ved tilfældigt at kombinere vektorer fra den forrige generation. Antallet af vektorer i hver generation er det samme og er en af metodens parametre. $n$ $f(x)$

Den nye generation af vektorer genereres som følger. For hver vektor fra den gamle generation vælges tre forskellige tilfældige vektorer , , blandt vektorerne fra den gamle generation, med undtagelse af selve vektoren , og den såkaldte mutantvektor genereres af formlen: $x_{i}$ $v_{1}$ $v_{2}$ $v_{3}$ $x_{i}$

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

hvor er en af metodeparametrene, en eller anden positiv reel konstant i intervallet [0, 2]. $F$

En crossover-operation udføres på mutantvektoren , som består i at erstatte nogle af dens koordinater med de tilsvarende koordinater fra den oprindelige vektor (hver koordinat er erstattet med en vis sandsynlighed, hvilket også er en af parametrene for denne metode). Vektoren opnået efter krydsning kaldes en forsøgsvektor. Hvis det viser sig at være bedre end vektoren (det vil sige, at værdien af den objektive funktion er blevet mindre), så er vektoren i den nye generation erstattet af en prøvevektor, ellers forbliver den . $v$ $x_{i}$ $x_{i}$ $x_{i}$ $x_{i}$

Eksempler på praktiske anvendelser

Yandex -søgemaskinen bruger differential evolution-metoden til at forbedre sine rangeringsalgoritmer. [4] [5]

Noter

↑ Storn, Rainer og Price, Kenneth . Differential Evolution - A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces, Arkiveret 24. april 2005 på Wayback Machine Technical Report TR -95-012 , ICSI, marts 1995.
↑ Storn, Rainer og Price, Kenneth . Differentiel evolution - en enkel og effektiv heuristik til global optimering over kontinuerlige rum. Arkiveret 6. januar 2010 på Wayback Machine (1997)
↑ K. Price, R. Storn, J. Lampinen . Differentiel udvikling: En praktisk tilgang til global optimering. Springer, 2005.
↑ Interview af A. Sadovsky til IT SPEC magazine, juli 2007. . Hentet 3. oktober 2009. Arkiveret fra originalen 13. maj 2013. (ubestemt)
↑ A. Gulin et al. Yandex på ROMIP'2009. Optimering af rangeringsalgoritmer ved maskinlæringsmetoder. . Hentet 3. oktober 2009. Arkiveret fra originalen 22. november 2009. (ubestemt)

Eksterne links :

Beskrivelse og implementering af metoden på en af dens forfatteres websted. Arkiveret 1. december 2005 på Wayback Machine
S. Luke . Essentials af metaheuristik. Kapitel 3.4.

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering

Machine learning og data mining
Opgaver	Klassificeringsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG