Genetikai algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 20-án felülvizsgált verziótól ; az ellenőrzések 17 szerkesztést igényelnek .

A genetikai algoritmus egy heurisztikus keresési algoritmus , amelyet  optimalizálási és modellezési problémák megoldására használnak a kívánt paraméterek véletlenszerű kiválasztásával, kombinálásával és variálásával, a természetben előforduló természetes szelekcióhoz hasonló mechanizmusok segítségével . Ez az evolúciós számítások egy olyan fajtája, amely az optimalizálási problémákat természetes evolúciós módszerekkel oldja meg, mint például az öröklődés , a mutáció , a szelekció és a keresztezés . A genetikai algoritmus megkülönböztető jellemzője a „keresztező” operátor használatának hangsúlyozása, amely a jelölt megoldások rekombinációjának műveletét hajtja végre, amelynek szerepe hasonló a természetben játszott keresztezés szerepéhez.

Történelem

Az evolúció szimulációjával kapcsolatos első munkát Nils Baricelli végezte 1954-ben a Princetoni Egyetem Advanced Study Intézetében telepített számítógépen. [1] [2] Ugyanebben az évben megjelent munkája széles körű közfigyelmet keltett. Ez az áttörés lehetővé tette, hogy az evolúciós folyamatok számítógépes szimulációja, valamint a Fraser és Barnell (1970) [4] és Crosby (1973) [5] könyveiben leírt módszerek a 60-as évektől általánosabb tevékenységgé váljanak a biológusok körében. Fraser szimulációi a modern genetikai algoritmusok minden lényeges elemét tartalmazták. Bremermann kutatásai a modern genetikai algoritmusok elemeit is magukba foglalták. [6] További úttörők közé tartozik Richard Friedberg, George Friedman és Michael Conrad. David B. Vogel (1998) sok korai művet újra kiadott . [7]

Bár Baricelli 1963-as cikkében egy gép egyszerű játékra való képességét szimulálta, [8] a mesterséges evolúció elfogadott optimalizálási technikává vált Ingo Rechenberg és Hans-Paul Schwefel munkája nyomán az 1960-as években és a XX. hetvenes évek elején. században – Rechenberg csoportja képes volt evolúciós stratégiák szerint összetett mérnöki problémákat megoldani . [9] [10] [11] [12] Egy másik megközelítés Lawrence J. Vogel evolúciós programozási technikája volt , amelyet mesterséges intelligencia létrehozására javasoltak. Az evolúciós programozás eredetileg állapotgépeket használt a körülmények előrejelzésére, a diverzitást és szelekciót pedig az előrejelzés logikájának optimalizálására. A genetikus algoritmusok különösen népszerűvé váltak John Holland 70-es évek elején végzett munkájának és Adaptation in Natural and Artificial Systems (1975) [13] című könyvének köszönhetően . Vogel kutatása Holland sejtautomatákkal végzett kísérletein és (Hollandia) a Michigani Egyetemen írt írásain alapult . A genetikai algoritmusokkal kapcsolatos kutatások nagyrészt elméleti jellegűek maradtak egészen az 1980-as évek közepéig, amikor is a Pennsylvania állambeli Pittsburgh-ben (USA) végül megtartották az Első Nemzetközi Genetikai Algoritmuskonferenciát .

A kutatási érdeklődés növekedésével az asztali számítógépek számítási teljesítménye is jelentősen nőtt, ami lehetővé tette az új számítástechnika gyakorlati alkalmazását. A 80-as évek végén a General Electric elkezdte árulni a világ első genetikai algoritmus termékét. Ipari számítástechnikai eszközök készletévé váltak. 1989-ben egy másik cég, az Axcelis, Inc. kiadta az Evolvert  , a világ első, asztali számítógépekhez készült, kereskedelmi forgalomba kerülő genetikai algoritmus termékét. A New York Times technológiai újságírója, John Markoff 1990-ben írt [14] az Evolverről.

Az algoritmus leírása

A probléma úgy van formalizálva, hogy a megoldása gének vektoraként („ genotípusa ”) kódolható, ahol minden gén lehet bit , szám vagy más objektum. A genetikai algoritmus (GA) klasszikus megvalósításaiban feltételezik, hogy a genotípus fix hosszúságú. Vannak azonban a GA-nak olyan változatai, amelyek mentesek ettől a korlátozástól.

Bizonyos, általában véletlenszerű módon a kezdeti populáció számos genotípusa jön létre. Ezeket egy „ fitness függvény ” segítségével értékelik, ahol minden genotípushoz egy bizonyos érték („fitness”) társul, amely meghatározza, hogy az általa leírt fenotípus mennyire oldja meg a problémát.

A „ fitneszfunkció ” (vagy az angol szakirodalomban fitness függvény) kiválasztásakor fontos ügyelni arra, hogy a „könnyítés” „sima” legyen.

Az eredményül kapott megoldáshalmazból („generációk”) a „fitness” értékét figyelembe véve olyan megoldásokat választanak ki (általában nagyobb a valószínűsége a legjobb egyedek kiválasztásának), amelyekre „genetikai operátorokat” alkalmaznak (a legtöbb esetben esetekben a „ crossover ” - crossover és a „ mutation ” - mutation ), ami új megoldásokat eredményez. Számukra is kiszámolják az edzettségi értéket, majd elvégzik a következő generáció számára a legjobb megoldások kiválasztását („kiválasztását”).

Ez a műveletsor iteratív módon ismétlődik, így modellezve egy "evolúciós folyamatot", amely több életcikluson ( generációig ) tart, amíg az algoritmus leállási kritériuma teljesül. Ez a kritérium lehet:

A genetikus algoritmusok elsősorban többdimenziós keresési terekben való megoldáskeresésre szolgálnak.

Így a genetikai algoritmus következő szakaszai különböztethetők meg:

  1. Állítsa be a célfüggvényt (fitness) a populáció egyedei számára
  2. Hozzon létre kezdeti populációt
  1. Szaporodás (keresztezés)
  2. Mutáció
  3. Számítsa ki a célfüggvény értékét minden egyedre!
  4. Új generáció kialakulása (válogatás)
  5. Ha a leállítási feltételek teljesülnek, akkor (a ciklus vége), ellenkező esetben (a ciklus eleje).

A kezdeti sokaság létrehozása

Az első lépés előtt véletlenszerűen létre kell hoznia egy kezdeti sokaságot; még ha kiderül is, hogy teljesen versenyképtelen, valószínű, hogy a genetikai algoritmus akkor is gyorsan életképes populációba juttatja. Így első lépésben nem lehet különösebben törekedni az egyedek túl fittté tételére, elég, ha megfelelnek a populáció egyedeinek formátumának, és ki lehet számolni rájuk az alkalmassági függvényt. Az első lépés eredménye a H populáció, amely N egyedből áll.

Kiválasztás (kiválasztás)

A kiválasztási szakaszban ki kell választani a teljes népesség egy bizonyos hányadát, amely az evolúció ezen szakaszában "életben" marad. Különféle módon lehet kiválasztani. Egy egyed h túlélési valószínűségének a Fitness(h) fittségi függvény értékétől kell függnie. Maga az s túlélési arány általában a genetikai algoritmus paramétere, és egyszerűen előre megadva. A szelekció eredményeként a H populáció N egyedéből sN egyedeknek kell maradniuk, amelyek bekerülnek a végső H' populációba. A többi egyed meghal.

Parents' Choice

A genetikai algoritmusokban történő szaporodáshoz több szülőre van szükség, általában kettőre, hogy utódokat hozzanak létre.

Számos szülőválasztási operátor létezik:

  1. Panmixia - mindkét szülőt véletlenszerűen választják ki, a populáció minden egyedének egyenlő esélye van a kiválasztásra
  2. Beltenyésztés - az első szülőt véletlenszerűen választják ki, a másodikat pedig úgy választják ki, amelyik leginkább hasonlít az első szülőhöz
  3. Outbreeding - az első szülő véletlenszerűen kerül kiválasztásra, és a második szülő kerül kiválasztásra, amely a legkevésbé hasonlít az első szülőhöz

A beltenyésztésnek és a kitenyésztésnek két formája van: fenotípusos és genotípusos. A fenotípusos forma esetében a hasonlóságot a fitnesz függvény értékétől függően mérjük (minél közelebb vannak a célfüggvény értékei, annál hasonlóbbak az egyedek), a genotípusos forma esetében pedig a hasonlóságot mérjük. a genotípus reprezentációjától függően (minél kevesebb különbség van az egyedek genotípusai között, annál hasonlóbbak az egyedek).

Reprodukció (Crossing)

A reprodukálás a különböző algoritmusokban eltérően van definiálva – ez természetesen az adatábrázolástól függ. A szaporodás fő követelménye, hogy az utódnak vagy utódoknak lehetősége legyen mindkét szülő tulajdonságait átörökíteni, azokat valamilyen módon "keverni".

Miért általában a teljes H populációból választják ki a szaporodásra szánt egyedeket, és nem a H' első lépésben fennmaradt elemei közül (bár ez utóbbi lehetőségnek is van létjogosultsága)? A tény az, hogy számos genetikai algoritmus fő hátránya az egyedek sokféleségének hiánya. Elég gyorsan kiemelkedik egyetlen genotípus, ami egy lokális maximum, majd a populáció minden eleme elveszíti a szelekciót, és az egész populáció „eltömődik” ennek az egyednek a másolataival. Az ilyen nemkívánatos hatások kezelésének különböző módjai vannak; ezek egyike a nem a leginkább alkalmazkodó, hanem általában az összes egyed reprodukciós választása. Ez a megközelítés azonban arra kényszerít bennünket, hogy eltároljuk az összes már létező egyedet, ami növeli a probléma számítási bonyolultságát. Ezért az egyedek keresztezésre való kiválasztásának módszereit gyakran úgy alkalmazzák, hogy nemcsak a leginkább alkalmazkodtak, hanem más, rossz kondíciójú egyedek is „szaporodnak”. Ezzel a megközelítéssel megnő a mutációk szerepe a genotípus sokféleségében.

Mutációk

A mutációkra ugyanaz vonatkozik, mint a szaporodásra: van egy bizonyos arányban m mutáns, ami a genetikai algoritmus paramétere, és a mutáció lépésében mN egyedeket kell kiválasztani, majd az előre meghatározott mutációs műveleteknek megfelelően módosítani. .

Kritika

Számos oka van a kritikának egy genetikai algoritmus más optimalizálási módszerekkel való összehasonlításával kapcsolatban:

Sok szkeptikus van a genetikai algoritmusok alkalmazásának megvalósíthatóságával kapcsolatban.

Én személy szerint soha nem találkoztam olyan problémával, amelyre a genetikai algoritmusok lennének a legalkalmasabbak. Sőt, soha nem találkoztam olyan genetikai algoritmusokkal nyert számítási eredménnyel, amely pozitív benyomást tenne rám.

Genetikai algoritmusok alkalmazásai

A genetikai algoritmusokat a következő problémák megoldására használják:

  1. Funkcióoptimalizálás
  2. Adatbázis lekérdezés optimalizálás
  3. Különféle problémák a grafikonokon ( utazó eladó probléma , színezés, egyezés keresése)
  4. Mesterséges neurális hálózat felállítása és betanítása
  5. Építési feladatok
  6. Ütemezés
  7. Játékstratégiák
  8. Közelítés elmélet
  9. mesterséges élet
  10. Bioinformatika ( fehérjehajtogatás )
  11. Véges automaták szintézise
  12. PID szabályzók hangolása

Példa egy egyszerű C++ implementációra

Keresés egydimenziós térben, keresztezés nélkül.

#include <cstdlib> #include <ctime> #include <algoritmus> #include <iostream> #include <szám> int main () { srand (( unsigned int ) time ( NULL )); const size_t N = 1000 ; int a [ N ] = { 0 }; számára ( ;; ) _ { //mutáció az egyes elemek véletlenszerű oldalára: for ( méret_t i = 0 ; i < N ; ++ i ) a [ i ] += (( rand () % 2 == 1 ) ? 1 : -1 ); //most válassza ki a legjobbat, növekvő sorrendben std :: sort ( a , a + N ); //és akkor a legjobbak a tömb második felében lesznek. //másolja a legjobbakat az első felére, ahol hagyták az utódot, és az elsők meghaltak: std :: másolás ( a + N / 2 , a + N , a ); //most nézd meg a lakosság átlagos állapotát. Amint látja, egyre jobb és jobb. std :: cout << std :: felhalmoz ( a , a + N , 0 ) / N << std :: endl ; } }

Példa egy egyszerű megvalósításra a Delphiben

Keresés egydimenziós térben a túlélés valószínűségével, keresztezés nélkül. (Delphi XE-n tesztelve)

program Program1 ; {$APPTYPE CONSOLE} {$R *.res} rendszert használja . generikumok . Alapértelmezések , Rendszer . Gyűjtemények , Rendszer . Sysutils ; Nh = N div2 ; _ MaxPopulation = Magas ( egész szám ) ; var A : egész szám [ 1 .. N ] tömbje ; I , R , C , Pontok , Születési arány : Egész ; Iptr : ^ Integer ; Kezdje Véletlenszerűvé ; // Részleges populáció I := 1 - től N do A -ig [ I ] := Véletlenszerű ( 2 ) ; ismétlés // Mutáció az I := 1 -től N - ig A [ I ] := A [ I ] + ( - Véletlenszerű ( 2 ) vagy 1 ) ; // Válogatás, a legjobbak a TArray végén . // Előre beállított Iptr := Addr ( A [ Nh + 1 ]) ; Pontok := 0 ; Születési arány := 0 ; // Keresztezési eredmények a következőre: I := 1 - Nh do begin Inc ( Pontok , Iptr ^ ) ; // Véletlenszerű keresztezési siker R := Random ( 2 ) ; Inc ( BirthRate , R ) ; A [ I ] := Iptr ^ * R ; Inc ( Iptr , 1 ) ; vége ; // Részösszeg Inc ( C ) ; Writeln ( Formátum ( 'Népesség %d (ráta:%f) pontszám:%f' , [ C , Születési arány / Nh , Pontok / N ])) ; vége .

A kultúrában

  • Az 1995-ös Virtuozitás című filmben a főgonosz agyát egy genetikai algoritmus növeszti, felhasználva a bűnözők emlékeit és viselkedési vonásait.

Jegyzetek

  1. ↑ Barricelli, Nils AallEsempi numerici di processi di evoluzione  (neopr.)  // Methodos. - 1954. - S. 45-68 .
  2. ↑ Barricelli, Nils AallMesterséges módszerekkel megvalósított szimbiogenetikus evolúciós folyamatok  (angol)  // Methodos : Journal. - 1957. - P. 143-182 .
  3. ↑ Fraser, AlexGenetikai rendszerek szimulációja automatikus digitális számítógépekkel. I. Bevezetés  (angol)  // Aust. J Biol. sci. : folyóirat. - 1957. - 1. évf. 10 . - P. 484-491 .
  4. ↑ Fraser, Alex; Donald Burnell. Számítógépes modellek a genetikában  (neopr.) . - New York: McGraw-Hill Education , 1970. - ISBN 0-07-021904-4 .
  5. ↑ Crosby, Jack L. Számítógépes szimuláció a genetikában  (határozatlan) . - London: John Wiley & Sons , 1973. - ISBN 0-471-18880-8 .
  6. ↑ 96. 02. 27. – 69 éves korában elhunyt Hans Bremermann, a Berkeley Egyetem professzora, a matematikai biológia emeritusa és úttörője .
  7. ↑ Fogel, David B. (szerkesztő). Evolutionary Computation: The Fossil Record  (angol) .
  8. ↑ Barricelli, Nils Aall. Az evolúciós elméletek numerikus tesztelése. rész II. A teljesítmény, a szimbiogenezis és a földi élet előzetes tesztjei  (angol)  // Acta Biotheoretica : folyóirat. - 1963. - Nem. 16 . - P. 99-126 .
  9. ↑ Rechenberg, Ingo. Evolúciós  stratégia (neopr.) .
  10. ↑ Schwefel, Hans-Paul. – 1974.
  11. ↑ Schwefel, Hans-Paul. Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie  (német) . – Bázel; Stuttgart: Birkhauser, 1977. - ISBN 3-7643-0876-1 .
  12. ↑ Schwefel, Hans-Paul. Számítógépes modellek numerikus optimalizálása (Az 1977-es Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie fordítása  (angol) . - Chichester; New York: Wiley, 1981. - ISBN 0-471-09988-0 .
  13. ↑ JH Holland. Alkalmazkodás természetes és mesterséges rendszerekben. University of Michigan Press, Ann Arbor, 1975.
  14. ↑ Markoff, John . Mi a legjobb válasz? Az eredetiből archiválva: 2010. december 2. Letöltve: 2009. augusztus 9.
  15. ↑ Melanie Mitchell. Bevezetés a genetikai algoritmusokba . - MIT Press, 1998. - S. 167. - 226 p. — ISBN 9780262631853 . Archiválva : 2018. november 1. a Wayback Machine -nél
  16. ↑ Wolpert, DH, Macready, WG, 1995. No Free Lunch Theorems for Optimization. Santa Fe Institute, SFI-TR-05-010, Santa Fe.
  17. Az algoritmus tervezési kézikönyve. második kiadás. Springer, 2008.

Könyvek

  • Simon D. Algoritmusok evolúciós optimalizáláshoz. — M. : DMK Press, 2020. — 940 p. - ISBN 978-5-97060-812-8 .
  • Emelyanov VV, Kureichik VV, Kureichik VM Az evolúciós modellezés elmélete és gyakorlata. - M. : Fizmatlit, 2003. - 432 p. — ISBN 5-9221-0337-7 .
  • Kureichik V. M., Lebedev B. K., Lebedev O. K. Keresési adaptáció: elmélet és gyakorlat. - M. : Fizmatlit, 2006. - 272 p. — ISBN 5-9221-0749-6 .
  • Gladkov L. A., Kureichik V. V., Kureichik V. M. Genetic Algorithms: Textbook. - 2. kiadás - M. : Fizmatlit, 2006. - 320 p. - ISBN 5-9221-0510-8 .
  • Gladkov L.A., Kureichik V.V., Kureichik V.M. és munkatársai Bioinspirált módszerek az optimalizálásban: monográfia. - M. : Fizmatlit, 2009. - 384 p. - ISBN 978-5-9221-1101-0 .
  • Rutkowska D., Pilinsky M., Rutkowski L. Neurális hálózatok, genetikai algoritmusok és fuzzy rendszerek = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. - 2. kiadás - M . : Hot line-Telecom, 2008. - 452 p. — ISBN 5-93517-103-1 .
  • Skobtsov Yu. A. Az evolúciós számítástechnika alapjai. - Donyeck: DonNTU, 2008. - 326 p.

Linkek

  Ugrás a Wikidata elemre  Szótárak és enciklopédiák