Genetski algoritam je adaptivni heuristički algoritam pretraživanja inspiriran 'Darwinovom teorijom evolucije u prirodi' .' Koristi se za rješavanje problema optimizacije u strojnom učenju. To je jedan od važnih algoritama jer pomaže u rješavanju složenih problema za čije bi rješavanje trebalo dosta vremena.

Genetski algoritmi naširoko se koriste u različitim aplikacijama u stvarnom svijetu, na primjer, Projektiranje elektroničkih sklopova, razbijanje šifri, obrada slike i umjetna kreativnost.

U ovoj temi detaljno ćemo objasniti genetski algoritam, uključujući osnovnu terminologiju koja se koristi u genetskom algoritmu, kako radi, prednosti i ograničenja genetskog algoritma itd.

c niz programskog niza

Što je genetski algoritam?

Prije razumijevanja genetskog algoritma, prvo shvatimo osnovnu terminologiju kako bismo bolje razumjeli ovaj algoritam:

Populacija:Populacija je podskup svih mogućih ili vjerojatnih rješenja, koja mogu riješiti dati problem.Kromosomi:Kromosom je jedno od rješenja u populaciji za navedeni problem, a zbirka gena generira kromosom.Gen:Kromosom je podijeljen na drugi gen, ili je element kromosoma.Aleli:Alel je vrijednost dana genu unutar određenog kromosoma.Fitnes funkcija:Funkcija fitnessa koristi se za određivanje razine fitnessa pojedinca u populaciji. To znači sposobnost pojedinca da se natječe s drugim pojedincima. U svakoj iteraciji pojedinci se ocjenjuju na temelju njihove funkcije fitnessa.Genetski operateri:U genetskom algoritmu, najbolji pojedinačni par za regeneraciju potomaka je bolji od roditelja. Ovdje genetski operateri igraju ulogu u promjeni genetskog sastava sljedeće generacije.Izbor

Nakon izračuna prikladnosti svakog postojećeg u populaciji, koristi se proces selekcije kako bi se odredilo koje će se individue u populaciji reproducirati i proizvesti sjeme koje će oblikovati nadolazeću generaciju.

Dostupne vrste stilova odabira

Izbor kotača ruleta Izbor događaja Izbor temeljen na rangu

Dakle, sada možemo definirati genetski algoritam kao heuristički algoritam pretraživanja za rješavanje problema optimizacije. To je podskup evolucijskih algoritama koji se koristi u računalstvu. Genetski algoritam koristi koncepte genetske i prirodne selekcije za rješavanje problema optimizacije.

Kako funkcionira genetski algoritam?

Genetski algoritam radi na evolucijskom generacijskom ciklusu za generiranje visokokvalitetnih rješenja. Ovi algoritmi koriste različite operacije koje ili poboljšavaju ili zamjenjuju populaciju kako bi dali poboljšano rješenje prilagodbe.

U osnovi uključuje pet faza za rješavanje složenih problema optimizacije, koji su navedeni u nastavku:

Inicijalizacija Fitnes zadatak Izbor Reprodukcija Raskid

1. Inicijalizacija

Proces genetskog algoritma počinje generiranjem skupa jedinki, koji se naziva populacija. Ovdje je svaki pojedinac rješenje za dati problem. Pojedinac sadrži ili je karakteriziran skupom parametara koji se nazivaju geni. Geni se spajaju u niz i stvaraju kromosome, što je rješenje problema. Jedna od najpopularnijih tehnika za inicijalizaciju je korištenje slučajnih binarnih nizova.

java zamah

2. Kondicijski zadatak

Funkcija kondicije koristi se za određivanje kondicije pojedinca? To znači sposobnost pojedinca da se natječe s drugim pojedincima. U svakoj iteraciji pojedinci se ocjenjuju na temelju njihove funkcije fitnessa. Funkcija fitnessa daje ocjenu fitnessa svakom pojedincu. Ovaj rezultat dalje određuje vjerojatnost odabira za reprodukciju. Što je viši rezultat fitnessa, veće su šanse da budete odabrani za reprodukciju.

3. Odabir

Faza odabira uključuje odabir jedinki za reprodukciju potomstva. Sve odabrane jedinke zatim se raspoređuju u par po dvije kako bi se povećala reprodukcija. Zatim ti pojedinci prenose svoje gene na sljedeću generaciju.

Dostupne su tri vrste metoda odabira, a to su:

• Izbor kotača ruleta
• Izbor turnira
• Odabir na temelju ranga

4. Razmnožavanje

Nakon procesa odabira, stvaranje djeteta događa se u koraku reprodukcije. U ovom koraku genetski algoritam koristi dva operatora varijacije koji se primjenjuju na matičnu populaciju. U nastavku su navedena dva operatera uključena u fazu reprodukcije:

Crossover:Križanje ima najznačajniju ulogu u fazi reprodukcije genetskog algoritma. U ovom procesu, točka križanja odabire se nasumično unutar gena. Zatim operater križanja zamjenjuje genetske informacije dvaju roditelja iz trenutne generacije kako bi proizveo novu jedinku koja predstavlja potomstvo.

Geni roditelja međusobno se izmjenjuju sve dok se ne postigne točka križanja. Ovi novonastali potomci dodaju se populaciji. Ovaj proces se također naziva ili crossover. Dostupne vrste crossover stilova:
• Crossover u jednoj točki
• Crossover u dvije točke
• Livrejski crossover
• Crossover nasljednih algoritama
Mutacija
Operator mutacije umeće nasumične gene u potomstvo (novo dijete) kako bi održao raznolikost u populaciji. To se može učiniti okretanjem nekih bitova u kromosomima.
Mutacija pomaže u rješavanju problema preuranjene konvergencije i povećava diverzifikaciju. Donja slika prikazuje proces mutacije:
Dostupne vrste stilova mutacije,

json iz java objekta

Flip bit mutacija Gaussova mutacija Razmjena/Swap mutacija

5. Raskid

Nakon faze reprodukcije primjenjuje se kriterij zaustavljanja kao osnova za prekid. Algoritam se završava nakon što se dosegne rješenje prilagođenosti praga. Identificirat će konačno rješenje kao najbolje rješenje u populaciji.

Opći tijek rada jednostavnog genetskog algoritma

Prednosti genetskog algoritma

• Paralelne mogućnosti genetskih algoritama su najbolje.
• Pomaže u optimiziranju raznih problema kao što su diskretne funkcije, problemi s više ciljeva i kontinuirane funkcije.
• Pruža rješenje za problem koje se s vremenom poboljšava.
• Genetski algoritam ne treba izvedene informacije.

Ograničenja genetskih algoritama

• Genetski algoritmi nisu učinkoviti algoritmi za rješavanje jednostavnih problema.
• Ne jamči kvalitetu konačnog rješenja problema.
• Ponavljajući izračun vrijednosti prikladnosti može stvoriti neke računalne izazove.

Razlika između genetskih algoritama i tradicionalnih algoritama

• Prostor pretraživanja je skup svih mogućih rješenja problema. U tradicionalnom algoritmu održava se samo jedan skup rješenja, dok se u genetskom algoritmu može koristiti nekoliko skupova rješenja u prostoru pretraživanja.
• Tradicionalni algoritmi trebaju više informacija kako bi izvršili pretraživanje, dok genetski algoritmi trebaju samo jednu objektivnu funkciju za izračunavanje sposobnosti pojedinca.
• Tradicionalni algoritmi ne mogu raditi paralelno, dok genetski algoritmi mogu raditi paralelno (izračunavanje prikladnosti individualnosti je neovisno).
• Jedna velika razlika u genetskim algoritmima je da umjesto izravnog rada na rezultatima tragača, nasljedni algoritmi rade na svojim reprezentacijama (ili prikazima), koji se često pripisuju kromosomima.
• Jedna od velikih razlika između tradicionalnog algoritma i genetskog algoritma je ta što ne djeluje izravno na rješenjima kandidata.
• Tradicionalni algoritmi mogu generirati samo jedan rezultat na kraju, dok Genetski algoritmi mogu generirati više optimalnih rezultata iz različitih generacija.
• Nije vjerojatnije da će tradicionalni algoritam generirati optimalne rezultate, dok genetski algoritmi ne jamče generiranje optimalnih globalnih rezultata, ali također postoji velika mogućnost dobivanja optimalnog rezultata za problem jer koristi genetske operatore kao što su Crossover i Mutation.
• Tradicionalni algoritmi su deterministički po prirodi, dok su genetski algoritmi probabilistički i stohastički po prirodi.