Ģenētiskais algoritms ir adaptīvs heiristisks meklēšanas algoritms, ko iedvesmojusi Darvina dabas evolūcijas teorija. .' To izmanto, lai atrisinātu optimizācijas problēmas mašīnmācībā. Tas ir viens no svarīgākajiem algoritmiem, jo ​​palīdz atrisināt sarežģītas problēmas, kuru atrisināšana prasīs ilgu laiku.

Ģenētiskie algoritmi tiek plaši izmantoti dažādās reālās pasaules lietojumprogrammās, piemēram, Elektronisko shēmu projektēšana, kodu laušana, attēlu apstrāde un mākslīgā jaunrade.

Šajā tēmā mēs detalizēti izskaidrosim ģenētisko algoritmu, tostarp ģenētiskajā algoritmā izmantotos pamata terminus, kā tas darbojas, ģenētiskā algoritma priekšrocības un ierobežojumus utt.

sapludināšanas algoritms

Kas ir ģenētiskais algoritms?

Pirms ģenētiskā algoritma izpratnes, vispirms sapratīsim pamata terminoloģiju, lai labāk izprastu šo algoritmu:

Populācija:Populācija ir visu iespējamo vai iespējamo risinājumu apakškopa, kas var atrisināt doto problēmu.Hromosomas:Hromosoma ir viens no šīs problēmas risinājumiem, un gēnu kolekcija ģenerē hromosomu.Gēns:Hromosoma ir sadalīta citā gēnā, vai arī tā ir hromosomas elements.Alēles:Alēle ir vērtība, kas tiek nodrošināta gēnam noteiktā hromosomā.Fitnesa funkcija:Fitnesa funkciju izmanto, lai noteiktu indivīda fitnesa līmeni populācijā. Tas nozīmē indivīda spēju konkurēt ar citiem indivīdiem. Katrā iterācijā indivīdi tiek novērtēti, pamatojoties uz viņu fitnesa funkcijām.Ģenētiskie operatori:Ģenētiskā algoritmā vislabākais indivīds pāro pēcnācējus labāk nekā vecāki. Šeit ģenētiskajiem operatoriem ir nozīme nākamās paaudzes ģenētiskā sastāva maiņā.Izlase

Pēc katra populācijas eksistences piemērotības aprēķināšanas tiek izmantots atlases process, lai noteiktu, kura no populācijas individualitātēm varēs vairoties un ražot sēklu, kas veidos nākamo paaudzi.

Pieejamie atlases stilu veidi

Ruletes rata izvēle Pasākuma atlase Ranga iezemēta atlase

Tātad, tagad mēs varam definēt ģenētisko algoritmu kā heiristisko meklēšanas algoritmu, lai atrisinātu optimizācijas problēmas. Tā ir evolūcijas algoritmu apakškopa, ko izmanto skaitļošanā. Ģenētiskais algoritms optimizācijas problēmu risināšanai izmanto ģenētiskās un dabiskās atlases koncepcijas.

Kā darbojas ģenētiskais algoritms?

Ģenētiskais algoritms darbojas evolūcijas paaudžu ciklā, lai radītu augstas kvalitātes risinājumus. Šie algoritmi izmanto dažādas darbības, kas uzlabo vai aizstāj populāciju, lai nodrošinātu uzlabotu piemērotības risinājumu.

Tas būtībā ietver piecas fāzes, lai atrisinātu sarežģītās optimizācijas problēmas, kas ir norādītas šādi:

Inicializācija Fitnesa uzdevums Atlase Pavairošana Izbeigšana

1. Inicializācija

Ģenētiskā algoritma process sākas ar indivīdu kopas ģenerēšanu, ko sauc par populāciju. Šeit katrs indivīds ir konkrētās problēmas risinājums. Indivīds satur vai to raksturo parametru kopums, ko sauc par gēniem. Gēni tiek apvienoti virknē un ģenerē hromosomas, kas ir problēmas risinājums. Viena no populārākajām inicializācijas metodēm ir nejaušu bināro virkņu izmantošana.

izpildlaika kļūda

2. Fitnesa uzdevums

Fitnesa funkcija tiek izmantota, lai noteiktu, cik fiziska persona ir? Tas nozīmē indivīda spēju konkurēt ar citiem indivīdiem. Katrā iterācijā indivīdi tiek novērtēti, pamatojoties uz viņu fitnesa funkcijām. Fitnesa funkcija nodrošina fitnesa rezultātu katram indivīdam. Šis rādītājs vēl vairāk nosaka varbūtību, ka tiks izvēlēts reprodukcijai. Jo augstāks ir fitnesa rādītājs, jo lielāka iespēja tikt izvēlētam reprodukcijai.

3. Atlase

Atlases fāze ietver īpatņu atlasi pēcnācēju pavairošanai. Pēc tam visi atlasītie indivīdi tiek sakārtoti pa diviem, lai palielinātu vairošanos. Tad šie indivīdi nodod savus gēnus nākamajai paaudzei.

Ir pieejamas trīs veidu atlases metodes, kas ir:

• Ruletes rata izvēle
• Turnīra atlase
• Atlase, pamatojoties uz rangu

4. Pavairošana

Pēc atlases procesa pavairošanas posmā notiek bērna radīšana. Šajā solī ģenētiskais algoritms izmanto divus variāciju operatorus, kas tiek piemēroti vecāku populācijai. Tālāk ir norādīti divi reproducēšanas fāzē iesaistītie operatori:

Crossover:Krosoveram ir visnozīmīgākā loma ģenētiskā algoritma reprodukcijas fāzē. Šajā procesā gēnos nejauši tiek izvēlēts krustošanas punkts. Pēc tam krosovera operators apmaina divu vecāku ģenētisko informāciju no pašreizējās paaudzes, lai iegūtu jaunu indivīdu, kas pārstāv pēcnācējus.

Vecāku gēni tiek apmainīti savā starpā, līdz tiek sasniegts krustošanās punkts. Šie jaundzimušie pēcnācēji tiek pievienoti populācijai. Šo procesu sauc arī par krustojumu. Pieejamie krosoveru stilu veidi:
• Viena punkta krosovers
• Divpunktu krosovers
• Livra krosovers
• Pārmantojamu algoritmu krustojums
Mutācija
Mutācijas operators pēcnācējam (jaunajam bērnam) ievieto nejaušus gēnus, lai saglabātu populācijas daudzveidību. To var izdarīt, pagriežot dažus bitus hromosomās.
Mutācija palīdz atrisināt priekšlaicīgas konverģences problēmu un uzlabo diversifikāciju. Zemāk redzamais attēls parāda mutācijas procesu:
Pieejamie mutāciju stilu veidi,

SIM karte ir ievietota, bet nav android pakalpojuma

Flip bitu mutācija Gausa mutācija Apmaiņas/swap mutācija

5. Izbeigšana

Pēc pavairošanas fāzes kā pārtraukšanas pamatu izmanto apturēšanas kritēriju. Algoritms beidzas pēc tam, kad ir sasniegts fitnesa sliekšņa risinājums. Tā noteiks gala risinājumu kā labāko risinājumu iedzīvotāju vidū.

Vienkārša ģenētiskā algoritma vispārīgā darbplūsma

Ģenētiskā algoritma priekšrocības

• Vislabākās ir ģenētisko algoritmu paralēlās iespējas.
• Tas palīdz optimizēt dažādas problēmas, piemēram, diskrētas funkcijas, vairāku mērķu problēmas un nepārtrauktas funkcijas.
• Tas nodrošina risinājumu problēmai, kas laika gaitā uzlabojas.
• Ģenētiskajam algoritmam nav nepieciešama atvasināta informācija.

Ģenētisko algoritmu ierobežojumi

• Ģenētiskie algoritmi nav efektīvi algoritmi vienkāršu problēmu risināšanai.
• Tas negarantē problēmas gala risinājuma kvalitāti.
• Atkārtota piemērotības vērtību aprēķināšana var radīt dažas skaitļošanas problēmas.

Atšķirība starp ģenētiskajiem algoritmiem un tradicionālajiem algoritmiem

• Meklēšanas telpa ir visu iespējamo problēmas risinājumu kopums. Tradicionālajā algoritmā tiek uzturēta tikai viena risinājumu kopa, savukārt ģenētiskajā algoritmā var izmantot vairākas risinājumu kopas meklēšanas telpā.
• Tradicionālajiem algoritmiem ir nepieciešama vairāk informācijas, lai veiktu meklēšanu, savukārt ģenētiskajiem algoritmiem ir nepieciešama tikai viena objektīva funkcija, lai aprēķinātu indivīda piemērotību.
• Tradicionālie algoritmi nevar darboties paralēli, savukārt ģenētiskie algoritmi var darboties paralēli (individualitāšu piemērotības aprēķināšana ir neatkarīga).
• Viena liela atšķirība ģenētiskajos algoritmos ir tā, ka pārmantojamie algoritmi darbojas tieši uz meklētāja rezultātiem, bet darbojas uz to attēlojumiem (vai renderēšanas), kas bieži tiek uzskatīti par hromosomām.
• Viena no lielajām atšķirībām starp tradicionālo algoritmu un ģenētisko algoritmu ir tā, ka tas tieši nedarbojas ar kandidātu risinājumiem.
• Tradicionālie algoritmi galu galā var radīt tikai vienu rezultātu, savukārt ģenētiskie algoritmi var radīt vairākus optimālus rezultātus no dažādām paaudzēm.
• Tradicionālais algoritms, visticamāk, neradīs optimālus rezultātus, turpretim ģenētiskie algoritmi negarantē optimālu globālo rezultātu ģenerēšanu, taču pastāv arī liela iespēja iegūt optimālo rezultātu problēmai, jo tas izmanto ģenētiskos operatorus, piemēram, Crossover un Mutation.
• Tradicionālie algoritmi pēc būtības ir deterministiski, savukārt ģenētiskie algoritmi pēc būtības ir varbūtiski un stohastiski.