A genetikai algoritmus áttekintése
Az optimalizálási technikák azok a technikák, amelyek segítségével a rendelkezésre álló lehetséges megoldások közül a lehető legjobb megoldást fedezhetik fel a jelenlegi korlátozások mellett. Tehát a genetikai algoritmus az egyik ilyen optimalizálási algoritmus, mely a természetünk természetes evolúciós folyamata alapján épül fel. A természetes szelekció és a genetikai öröklődés ötletét használjuk itt. Más algoritmusokkal ellentétben irányított véletlenszerű keresést használ, azaz úgy találja meg az optimális megoldást, hogy egy véletlenszerű kezdeti költségfüggvényből indul, majd csak azon a helyen keres, amelyben a legkevesebb a költség (az irányított irányban). Alkalmas ha hatalmas és összetett adatkészletekkel dolgozik.
Mi az a genetikai algoritmus?
A genetikai algoritmus a populáció kromoszómájának genetikai felépítésén és viselkedésén alapszik. A genetikai algoritmusok alapját a következő dolgok képezik.
- Minden kromoszóma jelzi a lehetséges megoldást. Így a populáció a kromoszómák gyűjteménye.
- A populáció minden egyes egyénét fitnesz funkció jellemzi. A jobb fitnesz a jobb megoldás.
- A populációban rendelkezésre álló egyének közül a legjobb egyedeket használják a következő generációs utódok szaporodására.
- Az előállított utódok mindkét szülő tulajdonságaival rendelkeznek, és a mutáció eredménye. A mutáció a génszerkezet kis változása.
A genetikai algoritmus fázisai
Az alábbiakban bemutatjuk a genetikai algoritmus különféle fázisait:
1. A népesség inicializálása (kódolás)
- Minden gén egy paramétert (változókat) képvisel a megoldásban. A megoldást alkotó paraméterek ez a gyűjteménye a kromoszóma. A populáció a kromoszómák gyűjteménye.
- A gének rendje a kromoszómában.
- A legtöbb kromoszómát binárisan jelenítik meg, mint 0 és 1, de vannak más kódolások is.
2. Fitness funkció
- A rendelkezésre álló kromoszómák közül ki kell választani a legjobbat az utódok szaporodására, így minden egyes kromoszómához fitnesz értéket kapunk.
- A fitnesz pontszám segít kiválasztani azokat a személyeket, akiket szaporodásra használnak.
3. Kiválasztás
- Ennek a szakasznak a fő célja annak a régiónak a megkeresése, ahol nagyobb eséllyel lehet a legjobb megoldást elérni.
- Az inspiráció a legmegfelelőbb túléléséből származik.
- Egyensúlynak kell lennie a kutatási tér feltárása és kiaknázása között.
- A GA megpróbálja mozgatni a genotípust a fitnesz magasabb szintjére.
- A túl erős fitnesz-választási torzítás nem optimális megoldásokat eredményezhet.
- A túl kevés fitnesz-torzítás kiválasztása céltalan keresést eredményez.
- Így a fitnesz arányos szelekcióját, amely más néven rulettkerék-választásként is ismert, genetikai algoritmusokban alkalmazott genetikai operátor a rekombinációhoz potenciálisan hasznos megoldások kiválasztására.
4. Reprodukció
Az utódok generálása 2 módon történik:
- Crossover
- Mutáció
a) Crossover
A crossover a genetikai algoritmus legfontosabb szakasza. A keresztezés során véletlenszerű pontot választanak, miközben párosulnak a szülők, hogy utódokat hozzanak létre.
3 fő típusú crossover létezik.
- Egypontos keresztezés : Mindkét szülő kromoszómáján egy pont véletlenszerűen kerül kiválasztásra, és azt egy „keresztezési pontnak” nevezik. Az adott ponttól jobbra lévő bitek kicserélődnek a két szülő kromoszóma között.
- Kétpontos keresztezés : Két keresztezési pontot véletlenszerűen választanak ki a szülő kromoszómákból. A két pont között lévő biteket felcseréljük a szülő organizmusok között.
- Egységes keresztezés : Egységes kereszteződés során általában minden bit kiválasztásra kerül bármelyik szülő közül azonos valószínűséggel.
Az új utódokat hozzákapcsolják a lakossághoz.
b) mutáció
Néhány kialakult új utódban néhány génjének kis véletlenszerű valószínűséggel lehet mutációja. Ez azt jelzi, hogy a bit kromoszóma egyes bitjei megfordíthatók. A mutáció a lakosság sokszínűségének gondozására és az idő előtti konvergencia megállítására irányul.
5. Konvergencia (mikor kell megállni)
Néhány betartott szabály, amely megmondja, mikor kell megállni, a következő:
- Ha egy bizonyos számú generáció elõkészítése után a megoldás minõsége nem javul.
- Amikor elérkezik egy nehéz és gyors generációs és időtartomány.
- Amíg elfogadható oldatot kapunk.
A genetikai algoritmus alkalmazása
Ebben a szakaszban néhány olyan területet fogunk megvitatni, ahol a genetikai algoritmust gyakran alkalmazzák.
1. Utazás és szállítás útvonala
Az utazó eladó probléma a genetikai algoritmus egyik legfontosabb alkalmazása. Például, amikor az utazásszervezőt felkérik az utazás megtervezésére, egy genetikai algoritmus segítségével segítséget fog kérni, amely nem csak az utazás általános költségének csökkentésére, hanem az idő csökkentésére is hozzájárul. termékek helyett a leghatékonyabb módon.
2. Robotika
A genetikai algoritmust széles körben használják a robotika területén. A robotok céljaitól függően különböznek egymástól. Például kevés épül fel főzési feladatokra, kevés épül oktatási feladatokra stb.
- Fontos tulajdonságok kiválasztása az adott adatkészletben.
- A hagyományos módszernél az adatkészlet fontos tulajdonságait a következő módszerrel választják ki. Vagyis megvizsgálja a modell fontosságát, akkor beállít egy küszöbértéket a szolgáltatások számára, és ha a szolgáltatás fontossági értéke nagyobb, mint egy küszöbérték, akkor figyelembe veszik.
- De itt egy hátizsák-probléma néven ismert módszert használunk.
- Újra kezdjük egy kromoszóma populációjával, ahol minden kromoszóma bináris húr lesz. Az 1 jelöli a szolgáltatás „beillesztését” a modellbe, és a 0 jelöli a szolgáltatás „kizárását” a modellben.
- A fitnesz funkció itt lesz a verseny pontossági mutatója. Minél pontosabb a kromoszómakészlet az érték előrejelzésében, annál megfelelőbb lesz.
- A genetikai algoritmusoknak sok más alkalmazása is van, például a DNS-elemzés, az ütemezési alkalmazások, a mérnöki tervezés.
Következtetés
A jelenlegi forgatókönyv szerint a GE-t nagy gyártó vállalatoknál, például repülőgépeknél stb. Használják az idő és az erőforrások felhasználásának optimalizálása érdekében. További tudósok azon dolgoznak, hogy új módszereket találjanak a genetikai algoritmusok más optimalizálási technikákkal való kombinálására.
Ajánlott cikkek
Ez egy útmutató a Mi a genetikai algoritmus? Itt tárgyaljuk a genetikai algoritmus bevezetését, szakaszát és alkalmazását. Megnézheti más javasolt cikkeinket -
- Útválasztási algoritmusok
- Algoritmusok típusai
- Neurális hálózati algoritmusok
- Adatbányászati algoritmusok
- útmutató a C ++ algoritmus példákhoz