Genetinis algoritmas yra prisitaikantis euristinės paieškos algoritmas, įkvėptas Darvino gamtos evoliucijos teorijos. .' Jis naudojamas mašininio mokymosi optimizavimo problemoms spręsti. Tai vienas iš svarbiausių algoritmų, nes padeda išspręsti sudėtingas problemas, kurių sprendimas užtruktų ilgai.

Genetiniai algoritmai plačiai naudojami įvairiose realaus pasaulio programose, pavyzdžiui, Elektroninių grandinių projektavimas, kodų laužymas, vaizdo apdorojimas ir dirbtinis kūrybiškumas.

Šioje temoje mes išsamiai paaiškinsime genetinį algoritmą, įskaitant pagrindinius terminus, naudojamus genetiniame algoritme, kaip jis veikia, genetinio algoritmo pranašumus ir apribojimus ir kt.

Kas yra genetinis algoritmas?

Prieš suprasdami genetinį algoritmą, pirmiausia supraskime pagrindinius terminus, kad geriau suprastume šį algoritmą:

Gyventojų skaičius:Populiacija yra visų galimų arba tikėtinų sprendimų poaibis, galintis išspręsti nurodytą problemą.Chromosomos:Chromosoma yra vienas iš šios problemos sprendimų populiacijoje, o genų kolekcija sukuria chromosomą.Genas:Chromosoma yra padalinta į kitą geną arba yra chromosomos elementas.Aleliai:Alelis yra reikšmė, suteikta genui tam tikroje chromosomoje.Fitneso funkcija:Fitneso funkcija naudojama nustatyti individo tinkamumo lygį populiacijoje. Tai reiškia individo gebėjimą konkuruoti su kitais asmenimis. Kiekvienoje iteracijoje asmenys vertinami pagal jų tinkamumo funkciją.Genetiniai operatoriai:Pagal genetinį algoritmą geriausias individas poruojasi, kad atgautų palikuonis geriau nei tėvai. Čia genetiniai operatoriai vaidina svarbų vaidmenį keičiant naujos kartos genetinę sudėtį.Pasirinkimas

Apskaičiavus kiekvieno populiacijos egzistavimo tinkamumą, atrankos procesas atliekamas siekiant nustatyti, kuri iš populiacijos individualybių gaus daugintis ir išaugins sėklą, kuri suformuos ateinančią kartą.

Galimi pasirinkimo stilių tipai

Ruletės rato pasirinkimas Renginio pasirinkimas Rankomis pagrįstas pasirinkimas

Taigi, dabar galime apibrėžti genetinį algoritmą kaip euristinės paieškos algoritmą optimizavimo problemoms spręsti. Tai yra evoliucinių algoritmų poaibis, naudojamas skaičiavimuose. Genetinis algoritmas optimizavimo problemoms spręsti naudoja genetinės ir natūralios atrankos koncepcijas.

Kaip veikia genetinis algoritmas?

Genetinis algoritmas veikia evoliuciniame kartų cikle, kad sukurtų aukštos kokybės sprendimus. Šie algoritmai naudoja skirtingas operacijas, kurios padidina arba pakeičia populiaciją, kad būtų patobulintas tinkamas sprendimas.

Iš esmės tai apima penkis etapus, skirtus sudėtingoms optimizavimo problemoms išspręsti, kurios pateikiamos taip:

Inicijavimas Fitneso užduotis Pasirinkimas Reprodukcija Nutraukimas

1. Inicializavimas

Genetinio algoritmo procesas prasideda generuojant individų rinkinį, vadinamą populiacija. Čia kiekvienas yra konkrečios problemos sprendimas. Asmenyje yra arba jam būdingas parametrų rinkinys, vadinamas genais. Genai sujungiami į eilutę ir sukuria chromosomas, o tai yra problemos sprendimas. Vienas iš populiariausių inicijavimo būdų yra atsitiktinių dvejetainių eilučių naudojimas.

2. Fitneso užduotis

Fitneso funkcija naudojama norint nustatyti, koks asmuo yra tinkamas? Tai reiškia individo gebėjimą konkuruoti su kitais asmenimis. Kiekvienoje iteracijoje asmenys vertinami pagal jų tinkamumo funkciją. Fitneso funkcija kiekvienam asmeniui pateikia fitneso balą. Šis balas dar labiau lemia tikimybę būti atrinktam reprodukcijai. Kuo aukštas fitneso balas, tuo didesnė tikimybė būti atrinktam reprodukcijai.

3. Atranka

Atrankos fazė apima individų atranką palikuonių reprodukcijai. Tada visi atrinkti individai suskirstomi į porą, kad padidėtų reprodukcija. Tada šie asmenys perduoda savo genus kitai kartai.

Yra trijų tipų atrankos metodai, kurie yra:

• Ruletės rato pasirinkimas
• Turnyro pasirinkimas
• Pasirinkimas pagal reitingą

4. Dauginimasis

Po atrankos vaikas sukuriamas reprodukcijos etape. Šiame žingsnyje genetinis algoritmas naudoja du variacijų operatorius, kurie taikomi pirminei populiacijai. Toliau pateikiami du reprodukcijos etape dalyvaujantys operatoriai:

Kryžminis:Kryžminimas atlieka svarbiausią vaidmenį genetinio algoritmo reprodukcijos fazėje. Šiame procese genuose atsitiktinai parenkamas kryžminimo taškas. Tada kryžminimo operatorius sukeičia dviejų dabartinės kartos tėvų genetinę informaciją, kad sukurtų naują individą, atstovaujantį palikuoniui.

Tėvų genai tarpusavyje keičiasi tol, kol pasiekiamas kryžminimo taškas. Šie naujai susilaukę palikuonys pridedami prie populiacijos. Šis procesas taip pat vadinamas kryžminiu. Galimi krosoverių stilių tipai:
• Vieno taško krosoveris
• Dviejų taškų krosoveris
• Livery crossover
• Paveldimų algoritmų kryžminis
Mutacija
Mutacijos operatorius į palikuonį (naujas vaikas) įterpia atsitiktinius genus, kad išlaikytų populiacijos įvairovę. Tai galima padaryti apverčiant kai kuriuos chromosomų bitus.
Mutacija padeda išspręsti ankstyvos konvergencijos problemą ir padidina diversifikaciją. Žemiau pateiktame paveikslėlyje parodytas mutacijos procesas:
Galimi mutacijų stilių tipai,

js pakeitimas

Flip bitų mutacija Gauso mutacija Mainų/Swap mutacija

5. Nutraukimas

Pasibaigus reprodukcijos fazei, nutraukimo pagrindas taikomas stabdymo kriterijus. Algoritmas baigiasi, kai pasiekiamas slenkstinis tinkamumo sprendimas. Jis nustatys galutinį sprendimą kaip geriausią sprendimą populiacijoje.

Bendra paprasto genetinio algoritmo darbo eiga

Genetinio algoritmo privalumai

• Lygiagrečios genetinių algoritmų galimybės yra geriausios.
• Tai padeda optimizuoti įvairias problemas, tokias kaip atskiros funkcijos, kelių tikslų problemos ir nuolatinės funkcijos.
• Tai padeda išspręsti problemą, kuri laikui bėgant gerėja.
• Genetiniam algoritmui nereikia išvestinės informacijos.

Genetinių algoritmų apribojimai

• Genetiniai algoritmai nėra veiksmingi paprastų problemų sprendimo algoritmai.
• Tai negarantuoja galutinio problemos sprendimo kokybės.
• Pasikartojantis tinkamumo verčių skaičiavimas gali sukelti tam tikrų skaičiavimo iššūkių.

Skirtumas tarp genetinių algoritmų ir tradicinių algoritmų

• Paieškos erdvė yra visų galimų problemos sprendimų rinkinys. Tradiciniame algoritme palaikomas tik vienas sprendimų rinkinys, o genetiniame algoritme gali būti naudojami keli sprendimų rinkiniai paieškos erdvėje.
• Tradiciniams algoritmams reikia daugiau informacijos, kad būtų galima atlikti paiešką, o genetiniams algoritmams reikia tik vienos objektyvios funkcijos, kad būtų galima apskaičiuoti asmens tinkamumą.
• Tradiciniai algoritmai negali veikti lygiagrečiai, o genetiniai algoritmai gali veikti lygiagrečiai (individualybių tinkamumo skaičiavimas yra nepriklausomas).
• Vienas didelis genetinių algoritmų skirtumas yra tas, kad paveldimi algoritmai veikia tiesiogiai pagal ieškotojo rezultatus, o pagal jų atvaizdavimą (arba atvaizdavimą), dažnai priskiriamą chromosomoms.
• Vienas iš didelių skirtumų tarp tradicinio algoritmo ir genetinio algoritmo yra tas, kad jis tiesiogiai neveikia su kandidatais.
• Tradiciniai algoritmai gali sukurti tik vieną rezultatą, o genetiniai algoritmai gali generuoti kelis optimalius skirtingų kartų rezultatus.
• Tradicinis algoritmas greičiausiai nesukurs optimalių rezultatų, tuo tarpu genetiniai algoritmai negarantuoja optimalių visuotinių rezultatų, tačiau taip pat yra didelė galimybė gauti optimalų problemos rezultatą, nes jame naudojami genetiniai operatoriai, tokie kaip Crossover ir Mutation.
• Tradiciniai algoritmai yra deterministinio pobūdžio, o genetiniai algoritmai yra tikimybinio ir stochastinio pobūdžio.