Ülevaade geneetilisest algoritmist
Optimeerimismeetodid on tehnikad, mida kasutatakse olemasolevate piirangutega pakutavate võimalike lahenduste hulgast parima lahenduse leidmiseks. Nii et geneetiline algoritm on üks selline optimeerimise algoritm, mis on üles ehitatud meie olemuse loomuliku evolutsiooniprotsessi põhjal. Siin kasutatakse loodusliku valiku ja geneetilise pärimise ideed. See kasutab erinevalt teistest algoritmidest juhitud juhuslikku otsingut, st optimaalse lahenduse leidmiseks, alustades juhusliku algkulu funktsioonist ja otsides seejärel ainult ruumist, mis oli kõige vähem kulutatud (suunatavas suunas). Sobib, kui töötate tohutute ja keerukate andmekogumitega.
Mis on geneetiline algoritm?
Geneetiline algoritm põhineb populatsiooni kromosoomi geneetilisel struktuuril ja käitumisel. Geneetiliste algoritmide aluseks on järgmised asjad.
- Iga kromosoom tähistab võimalikku lahendust. Seega on populatsioon kromosoomide kogum.
- Igat elanikkonna elanikkonda iseloomustab treeningfunktsioon. Suurem sobivus on parem lahendus.
- Populatsioonis saadaolevatest isenditest kasutatakse parimat isendit järgmise põlvkonna järglaste paljundamiseks.
- Toodetud järglastel on mõlema vanema tunnused ja see on mutatsiooni tulemus. Mutatsioon on geeni struktuuri väike muutus.
Geneetilise algoritmi faasid
Allpool on toodud geneetilise algoritmi erinevad faasid:
1. Rahvastiku lähtestamine (kodeerimine)
- Iga geen esindab lahuses parameetrit (muutujaid). See parameetri kogum, mis moodustab lahenduse, on kromosoom. Populatsioon on kromosoomide kogu.
- Geenide järjekord kromosoomis on oluline.
- Enamasti on kromosoomid kujutatud binaarselt 0 ja 1, kuid on ka teisi kodeeringuid.
2. Fitnessifunktsioon
- Kättesaadavate kromosoomide hulgast peame valima järglaste paljundamiseks parimad, seega antakse igale kromosoomile sobivusväärtus.
- Sobivuse skoor aitab valida isendeid, keda paljunemiseks kasutatakse.
3. Valik
- Selle etapi peamine eesmärk on leida piirkond, kus võimalused parema lahenduse leidmiseks on suuremad.
- Inspiratsioon selleks on kõige tugevama ellujäämisest.
- See peaks olema tasakaal otsinguruumi uurimise ja kasutamise vahel.
- GA proovib genotüüpi otsinguruumis kõrgemale sobivusele viia.
- Liiga tugev treeningvaliku kallutus võib viia optimaalsemate lahendusteni.
- Liiga vähe sobivuse eelarvamuste valikut põhjustab sihitu otsingu.
- Seega kasutatakse sobivuse proportsionaalset valikut, mida nimetatakse ka ruletiratta valimiseks, see on geneetiline operaator, mida kasutatakse geneetilistes algoritmides rekombinatsiooniks potentsiaalselt kasulike lahenduste valimiseks.
4. Paljundamine
Järglaste genereerimine toimub kahel viisil:
- Crossover
- Mutatsioon
a) Crossover
Crossover on geneetilise algoritmi kõige olulisem etapp. Ristamise ajal valitakse juhuslik punkt, paaritades paar vanemate järglaste saamiseks.
Seal on 3 peamist tüüpi ristandit.
- Ühesuunaline ristumispunkt : Mõlema vanema kromosoomis olev punkt valitakse juhuslikult ja seda nimetatakse „ristumispunktiks”. Sellest punktist paremal asuvad bitid vahetatakse kahe vanema kromosoomi vahel.
- Kahepunktiline ristumine: Kaks ristumispunkti valitakse juhuslikult vanemate kromosoomide hulgast. Kahe punkti vahelised bitid vahetatakse emaorganismide vahel.
- Ühtne ristside: Tavaliselt valitakse iga bitt võrdse tõenäosusega kummagi vanema hulgast.
Uusi järglasi lisandub elanikkonda.
b) Mutatsioon
Mõne uue moodustatud järglase korral saab osa nende geenidest muteeruda väikese juhusliku tõenäosusega. See näitab, et mõnda bitikromosoomi bitti saab pöörata. Mutatsiooni eesmärk on hoolitseda elanikkonna mitmekesisuse eest ja peatada enneaegne lähenemine.
5. Lähenemine (millal peatuda)
Vähesed reeglid, mida järgitakse, millal peatuda, on järgmised:
- Kui pärast teatud arvu põlvkondade täitmist ei ole lahenduse kvaliteet paranenud.
- Kui jõuab raske ja kiire põlvkondade ja ajavahemik.
- Kuni saadakse vastuvõetav lahendus.
Geneetilise algoritmi rakendamine
Selles osas käsitleme mõnda valdkonda, milles geneetilist algoritmi sageli rakendatakse.
1. Reisimine ja saadetiste marsruutimine
Reisimüüja probleem on geneetilise algoritmi üks peamisi rakendusi. Näiteks kui reisiplaneerijal palutakse reisi planeerida, võtab ta appi geneetilise algoritmi, mis mitte ainult ei vähenda reisi üldkulusid, vaid vähendab ka aega.GE kasutatakse ka kohaletoimetamise kavandamisel. toodete tõhusat kasutamist ühest kohast teise.
2. Robootika
Geneetilist algoritmi kasutatakse robootika valdkonnas laialdaselt. Robotid erinevad üksteisest otstarbe järgi, milleks nad on ehitatud. Näiteks on vähesed ehitatud toiduvalmistamise ülesande jaoks, vähesed on ehitatud õppeülesannete jaoks jne.
- Antud andmekogumis oluliste omaduste valik.
- Traditsioonilises meetodis valitakse andmekogumi olulised omadused järgmise meetodi abil. St vaatate selle mudeli olulisust, siis seate funktsioonide läviväärtuse ja kui funktsiooni olulisusväärtus on suurem kui lävi, võetakse see arvesse.
- Kuid siin kasutame meetodit, mida nimetatakse seljakotiprobleemiks.
- Alustame jällegi kromosoomi populatsioonist, kus iga kromosoom on binaarne string. 1 tähistab funktsiooni “kaasamist” mudelis ja 0 tähistab funktsiooni “välistamist” mudelis.
- Siinne sobivusfunktsioon on meie võistluste täpsusmõõdik. Mida täpsem on meie kromosoomikomplekt väärtuse ennustamisel, seda sobivam see on.
- Geneetiliste algoritmide jaoks on palju muid rakendusi, näiteks DNA analüüs, ajakavarakendused, tehniline disain.
Järeldus
Praeguse stsenaariumi korral kasutatakse GE aja- ja ressursikasutuse optimeerimiseks suurtes tootmisettevõtetes, näiteks lennukites jne. Edasised teadlased töötavad selle nimel, et leida uusi võimalusi geneetiliste algoritmide ühendamiseks teiste optimeerimismeetoditega.
Soovitatavad artiklid
See on juhend küsimusele Mis on geneetiline algoritm? Siin käsitleme geneetilise algoritmi sissejuhatust, etappe ja rakendusi. Võite vaadata ka meie teisi soovitatud artikleid -
- Marsruutimisalgoritmid
- Algoritmide tüübid
- Neuraalvõrgu algoritmid
- Andmete kaevandamise algoritmid
- C ++ algoritmi näidete juhend