Pregled genetskog algoritma

Tehnike optimizacije su tehnike koje se koriste za otkrivanje najboljeg rješenja iz svih mogućih rješenja koja postoje pod ograničenjima koja su prisutna. Dakle, Genetski algoritam je jedan takav algoritam optimizacije koji je izgrađen na temelju prirodnog evolucijskog procesa naše prirode. Ovdje se koristi ideja prirodne selekcije i genetskog nasljeđivanja. Koristi vođeno slučajno pretraživanje, za razliku od drugih algoritama, tj. Pronalaženje optimalnog rješenja počevši s funkcijom slučajnih početnih troškova, a zatim pretražujući samo u prostoru koji ima najmanje troškove (u vođenom smjeru). Prikladno za rad s ogromnim i složenim skupovima podataka.

Što je genetski algoritam?

Genetski algoritam temelji se na genetskoj strukturi i ponašanju kromosoma populacije. Sljedeće stvari su temelj genetskih algoritama.

  • Svaki kromosom označava moguće rješenje. Tako je populacija zbirka kromosoma.
  • Svakog pojedinca u populaciji odlikuje fitnes funkcija. Bolje kondicija bolja je rješenje.
  • Od raspoloživih jedinki u populaciji, najbolje se koriste za reprodukciju potomstva sljedeće generacije.
  • Proizvedeno potomstvo imat će osobine oba roditelja i rezultat je mutacije. Mutacija je mala promjena u strukturi gena.

Faze genetskog algoritma

Ispod su različite faze genetskog algoritma:

1. Inicijalizacija stanovništva (kodiranje)

  • Svaki gen predstavlja parametar (varijable) u otopini. Ova zbirka parametara koja tvori otopinu je kromosom. Populacija je skup kromosoma.
  • Redoslijed gena u pitanjima kromosoma.
  • Većina vremenskih kromosoma prikazana je u binarnim formatima kao 0 i 1, ali moguća su i druga mjesta.

2. Funkcija fitnesa

  • Od dostupnih kromosoma moramo odabrati one najbolje za reprodukciju potomaka, tako da svaki kromosom dobiva kondicijsku vrijednost.
  • Fitness rezultat pomaže u odabiru pojedinaca koji će se koristiti za reprodukciju.

3. Odabir

  • Glavni cilj ove faze je pronaći regiju u kojoj su šanse za najbolje rješenje veće.
  • Inspiracija za to je iz preživljavanja najboljih.
  • To bi trebao biti balans između istraživanja i iskorištavanja prostora za pretraživanje.
  • GA pokušava pomaknuti genotip u višu kondiciju u pretraživačkom prostoru.
  • Prevelika pristranost odabira fitnessa može dovesti do optimalnih rješenja.
  • Premali odabir pristranosti fitnessa rezultira nefokusiranom pretragom.
  • Tako se koristi proporcionalna selekcija fitnesa, koja je poznata i kao odabir kotača na ruletu, genetski operator koji se koristi u genetskim algoritmima za odabir potencijalno korisnih rješenja za rekombinaciju.

4. Reprodukcija

Generacija potomaka se događa na 2 načina:

  • crossover
  • Mutacija

a) Crossover

Crossover je najvažnija faza u genetskom algoritmu. Tijekom crossovera, odabire se slučajna točka dok pare par roditelja kako bi se stvorilo potomstvo.

Postoje 3 glavne vrste crossovera.

  • Cross point crossover: Točka na kromosomima oba roditelja odabrana je nasumično i označena je kao "crossover point". Bitovi desno od te točke izmjenjuju se između dva matična kromosoma.
  • Crossover u dvije točke : Dvije presječne točke nasumično su odabrane iz matičnih kromosoma. Bitovi između dviju točaka izmjenjuju se između matičnih organizama.
  • Uniformni crossover: U uniformnom crossoveru, obično se svaki bit bira iz bilo kojeg roditelja s jednakom vjerojatnošću.

Novo potomstvo se dodaje stanovništvu.

b) Mutacija

U nekoliko formiranih novih potomaka, neki se njihovi geni mogu podvrgnuti mutaciji uz malu slučajnu vjerojatnost. To ukazuje na to da se neki dijelovi u bitnom kromosomu mogu okretati. Mutacije se događaju kako bi se osigurala raznolikost stanovništva i zaustavila preuranjena konvergencija.

5. Konvergencija (kada prestati)

Nekoliko pravila koja slijede i koja govore kada treba zaustaviti je sljedeća:

  • Kad ne dođe do poboljšanja kvalitete otopine nakon završetka određenog broja generacija koje su postavljene pred ruku.
  • Kad se postigne težak i brz raspon generacija i vremena.
  • Dok se ne dobije prihvatljivo rješenje.

Primjena genetskog algoritma

U ovom ćemo odjeljku raspravljati o nekim područjima u kojima se genetski algoritam često primjenjuje.

1. Usmjeravanje putovanja i otpreme

Problem prodavača putovanja jedna je od glavnih primjena genetskog algoritma. Na primjer, kada se od planera putovanja zatraži da planira putovanje, on će upotrijebiti genetski algoritam koji ne samo da pomaže u smanjenju ukupnih troškova putovanja, već i u skraćivanju vremena.GE se koristi i za planiranje isporuke proizvoda od mjesta do mjesta na najučinkovitiji način.

2. Robotika

Genetski algoritam široko se koristi u području robotike. Roboti se međusobno razlikuju prema svrsi za koju su izgrađeni. Na primjer, nekolicina je izgrađena za kuharski zadatak, malo ih je izgrađeno za nastavne zadatke itd.

  • Odabir važnih značajki u datom skupu podataka.
  • U tradicionalnoj se metodi bitne značajke u skupu podataka odabiru sljedećom metodom. tj. Pogledate važnost tog modela, postavit ćete vrijednost praga za značajke, a ako značajka ima važnost veću od praga, smatra se.
  • Ali ovdje koristimo metodu koja se zove problem s ruksakom.
  • Ponovno ćemo započeti s populacijom kromosoma, gdje će svaki kromosom biti binarni niz. 1 će označiti "uključivanje" značajke u modelu, a 0 će označiti "isključenje" značajke u modelu.
  • Fitness funkcija ovdje će biti naša točnost pokazatelj natjecanja. Što je precizniji naš kromosom u predviđanju vrijednosti, to će mu više odgovarati.
  • Postoje mnoge druge primjene genetskih algoritama poput DNK analize, aplikacija za zakazivanje, inženjerskog dizajna.

Zaključak

U trenutnom scenariju, GE se koristi u velikim proizvodnim tvrtkama poput aviona itd. Kako bi se optimiziralo korištenje vremena i resursa. Daljnji znanstvenici rade na pronalaženju novih načina kombiniranja genetskih algoritama s drugim tehnikama optimizacije.

Preporučeni članci

Ovo je vodič Što je genetski algoritam? Ovdje razgovaramo o uvođenju, fazama i primjeni genetskog algoritma. Možete i pregledati naše druge predložene članke -

  1. Algoritmi usmjeravanja
  2. Vrste algoritama
  3. Algoritmi neuronske mreže
  4. Algoritmi vađenja podataka
  5. vodič za primjere algoritama C ++

Kategorija:

Veliki podaci