algoritmi genetici

Algoritmi genetici (GA) - este stocastică, metode de optimizare euristice, propusă de John Holland în 1975. Ele se bazează pe ideea evoluției prin selecție naturală. În plus, pentru a găsi mai rapid extremelor, la proprietățile pozitive ale algoritmilor genetici pot fi atribuite, și de a găsi un extremum „global“. În probleme în cazul în care funcția obiectiv are un număr semnificativ de Extrema locale, în contrast cu metoda gradientului, algoritmi genetici nu sunt „blocat“, într-un punct extrem local și ne permit să găsim un minim „global“.

algoritmi genetici lucrează cu o colecție de indivizi - populație. în care fiecare individ reprezintă o posibilă soluție la această problemă. Se estimează măsura ei „de fitness“, în funcție de modul în care „bun“ soluție corespunzătoare a problemei. În natură, aceasta este echivalentă cu o evaluare a modului eficient organismul de concurență pentru resurse. Fittest persoane au posibilitatea de a „juca“ descendenților prin intermediul „încrucișarea“ cu alți indivizi dintr-o populație. Acest lucru duce la apariția unor noi specii, care combină unele dintre caracteristicile moștenite de la părinții lor. Persoanele cel mai puțin adaptate sunt mai puțin susceptibile de a fi capabil de a reproduce urmași, astfel încât acele proprietăți pe care le posedă, vor dispărea treptat din populație în procesul de evoluție. Uneori există mutații sau modificări spontane ale genelor.

Astfel, din generație în generație, bune caracteristici sunt distribuite în întreaga populație. Hibridizarea celui mai adaptat conduce la faptul că a moștenit cele mai promițătoare domenii ale spațiului de căutare. În cele din urmă populația va converge la o soluție optimă. GA are avantajul că este vorba despre cele mai bune soluții într-un timp relativ scurt.
GA funcționează terminologia următoare:

• Cromozomul - rezolvarea problemelor purtătoare de informații genetice. Setul de cromozomi (valorile parametrilor funcției obiectiv) caracterizează individuală. Un cromozom este format din gene.
• Genele - codificare elemente de informații genetice (parametrii funcției obiectiv). Ca o genă efectuează adesea de codificare de biți de informație.
• Specii - cromozom set (parametrul set pentru care se solicită funcția obiectiv).
• Fittest - valoarea obiectivă funcție pentru un anumit set de parametri în raport cu valoarea dorită.

GA produce următoarele acțiuni asupra indivizilor

• Generarea unei populații inițiale de cromozomi - valorile parametrilor alese aleatoriu ale valorilor funcției obiective pentru acești parametri este valoarea funcției obiectiv.
• Selecția - Selectați persoane de cea mai bună adaptabilitate pentru reproducere (prin sortarea valoarea funcției obiectiv). Mai bună adaptare a individului, cele mai mari șansele sale de trecere și moștenirea genei sale de generație următoare.
• Crossover - crossover. Aleatoriu selectat punctul de discontinuitate - porțiunea dintre biți adiacente într-un rând. Ambele structuri mamă sunt rupte în două segmente prin punct. Apoi, segmentele corespunzătoare ale diferitelor părinți sunt lipite și a obținut două genotipuri ale descendenților.
  
  
• Mutația - o variație aleatorie a genelor. Aleatoriu gena selectată este schimbată cu o anumită probabilitate la alta.
  
• Inversion - schimbarea ordinii părților din cod. Aleatoriu selectat punctul de discontinuitate - porțiunea dintre biți adiacente într-un rând. Ambele părți ale structurii de bază, repartizate pe acest punct sunt interschimbate, apoi lipite împreună.
  

Inițial funcția HA generează un anumit număr de soluții posibile (exemplare), iar apoi se calculează pentru fiecare dispozitiv - apropierea de adevăr. Aceste soluții produc descendenți (operație de crossover produs). Mai multe soluții adaptate au o șansă mai mare de a se reproduce, și indivizii „slab“ treptat „muri“. Astfel, procesul de evoluție. În anumite etape ale procesului apar modificări ale genei spontane (mutații și inversiuni). Modificările utile care conduc la o creștere a persoanelor de fitness da descendenți ai acestora, în timp ce „inutil“ schimbare „muri“. După trecere, mutații și inversiuni de fitness a unei noi generații de indivizi este determinat din nou. Procesul se repetă atâta timp cât nu este găsită o soluție sau nu o aproximare suficientă la aceasta.

Ca un exemplu al unui algoritm genetic, ia în considerare problema de soluții de căutare numerice discutate în acest articol.

Funcția obiectiv va avea forma

Ca o funcție de crossover va folosi operarea de a găsi media aritmetică a celor două puncte luate în considerare. Pentru unele puncte de împerechere selectate cu cea mai bună soluție (cu valoarea functiei obiectiv cel mai apropiat de zero).

Mutația va fi exploatarea de generare a unui nou număr aleatoriu al populației în cauză.

Valoarea inversiune se va schimba pe cromozomul unele mici valoare, realizând astfel căutarea în jurul punctului cu cea mai bună soluție.
Implementarea în C ++

Aplicarea algoritmi genetici nu produc întotdeauna cele mai bune rezultate în comparație cu alte metode. Cu toate acestea, această metodă are avantajul de necontestat la rezolvarea problemelor multidimensionale ale căutării pentru extremelor la nivel mondial, care conține o cantitate semnificativă de extremelor locale.