Prezentare generală a algoritmului genetic

Tehnicile de optimizare sunt tehnicile utilizate pentru a descoperi cea mai bună soluție din toate soluțiile posibile disponibile în conformitate cu constrângerile prezente. Deci, algoritmul genetic este unul dintre astfel de algoritmi de optimizare care este construit pe baza procesului evolutiv natural al naturii noastre. Ideea de selecție naturală și moștenire genetică este folosită aici. Folosește căutarea ghidată aleatorie, spre deosebire de alți algoritmi, adică găsind soluția optimă începând cu o funcție de cost inițial aleatorie și apoi căutând doar în spațiul care a avut cel mai puțin cost (în direcția ghidată). Potrivit când lucrați cu seturi de date uriașe și complexe.

Ce este un algoritm genetic?

Algoritmul genetic se bazează pe structura genetică și comportamentul cromozomului populației. Următoarele lucruri sunt fundamentul algoritmilor genetici.

  • Fiecare cromozom indică o posibilă soluție. Astfel, populația este o colecție de cromozomi.
  • Fiecare individ din populație este caracterizat de o funcție de fitness. O soluție de fitness mai bună este soluția.
  • Dintre indivizii disponibili din populație, cei mai buni indivizi sunt folosiți pentru reproducerea urmelor generații.
  • Procesul produs va avea caracteristici ale ambilor părinți și este rezultatul mutației. O mutație este o modificare mică în structura genei.

Fazele algoritmului genetic

Mai jos sunt diferite faze ale algoritmului genetic:

1. Initializarea populatiei (codare)

  • Fiecare genă reprezintă un parametru (variabile) în soluție. Această colecție de parametri care formează soluția este cromozomul. Populația este o colecție de cromozomi.
  • Ordinea genelor privind problemele cromozomiale.
  • De cele mai multe ori cromozomii sunt descriși în mod binar ca 0 și 1, dar există și alte codificări posibile.

2. Funcția de fitness

  • Din cromozomii disponibili, trebuie să-i selectăm pe cei mai buni pentru reproducerea descendenților, astfel încât fiecărui cromozom i se oferă o valoare de fitness.
  • Scorul de fitness ajută la selectarea persoanelor care vor fi utilizate pentru reproducere.

3. Selectarea

  • Scopul principal al acestei faze este de a găsi regiunea în care șansele de a obține cea mai bună soluție sunt mai mari.
  • Inspirația pentru aceasta este din supraviețuirea celui mai potrivit.
  • Ar trebui să fie un echilibru între explorarea și exploatarea spațiului de căutare.
  • GA încearcă să mute genotipul la o formă mai bună de fitness în spațiul de căutare.
  • Pregătirea prea puternică a selecției de fitness poate duce la soluții sub-optime.
  • Prea mică selecție a prejudecăților de fitness are ca rezultat o căutare nefocalizată.
  • Astfel se utilizează selecția proporțională Fitness, care este cunoscută și sub denumirea de selecția roților de ruletă, este un operator genetic utilizat în algoritmi genetici pentru selectarea soluțiilor potențial utile pentru recombinare.

4. Reproducerea

Generarea de urmași se întâmplă în 2 moduri:

  • Crossover
  • Mutaţie

a) Crossover

Crossover este etapa cea mai vitală în algoritmul genetic. În timpul încrucișării, un punct aleatoriu este selectat în timp ce împerechează o pereche de părinți pentru a genera urmași.

Există 3 tipuri majore de crossover.

  • Crossover de un singur punct: Un punct pe cromozomii ambilor părinți este ales la întâmplare și desemnat „punct de încrucișare”. Mușcăturile din dreapta acelui punct sunt schimbate între cei doi cromozomi părinți.
  • Crossover în două puncte : Două puncte de încrucișare sunt selectate aleatoriu din cromozomii părinți. Biții dintre cele două puncte sunt schimbați între organismele părinte.
  • Crossover uniformă: într-un crossover uniform, de obicei, fiecare bit este ales dintre oricare dintre părinți cu probabilitate egală.

Noii urmași se adaugă populației.

b) mutație

În câteva noi descendențe formate, unele dintre genele lor pot fi supuse unei mutații cu o probabilitate scăzută aleatorie. Acest lucru indică faptul că unele dintre biții din cromozomul bit pot fi învârtite. Mutația se întâmplă să aibă grijă de diversitatea în rândul populației și să oprească convergența prematură.

5. Convergență (când se va opri)

Puține reguli care sunt respectate care spun când trebuie să se oprească sunt următoarele:

  • Când nu există nicio îmbunătățire a calității soluției după finalizarea unui anumit număr de generații setate înainte.
  • Când se ajunge la o gamă grea și rapidă de generații și timp.
  • Se obține o soluție acceptabilă.

Aplicarea algoritmului genetic

În această secțiune, vom discuta unele dintre domeniile în care este aplicat frecvent algoritmul genetic.

1. Călătorie și transport rutier

Problema vânzătorului de călătorie este una dintre aplicațiile majore ale algoritmului genetic. De exemplu, atunci când unui planificator de călătorie i se cere să planifice o călătorie, el ar lua ajutorul unui algoritm genetic care nu numai că ajută la reducerea costurilor generale ale călătoriei, dar și la reducerea timpului.GE este utilizat și pentru planificarea livrării. a produselor din loc în loc în cel mai bun mod eficient.

2. Robotică

Algoritmul genetic este utilizat pe scară largă în domeniul roboticii. Roboții diferă unul de altul prin scopul pentru care sunt construiți. De exemplu, puține sunt construite pentru o sarcină de gătit, puține sunt construite pentru sarcini de predare etc.

  • Selectarea funcțiilor importante din setul de date dat.
  • În metoda tradițională, caracteristicile importante din setul de date sunt selectate folosind următoarea metodă. adică, priviți importanța acelui model, apoi veți seta o valoare de prag pentru funcții, iar dacă funcția are o valoare de importanță mai mare decât un prag, este luată în considerare.
  • Dar aici folosim o metodă numită problemă de rucsac.
  • Vom începe din nou cu populația unui cromozom, unde fiecare cromozom va fi șir binar. 1 va indica „includerea” caracteristicii în model și 0 va indica „excluderea” caracteristicii din model.
  • Funcția de fitness aici va fi metoda noastră de precizie a competiției. Cu cât este mai exact setul nostru de cromozomi în ceea ce privește predicția valorii, cu atât va fi mai potrivit.
  • Există multe alte aplicații de algoritmi genetici, cum ar fi analiza ADN-ului, aplicații de planificare, proiectarea ingineriei.

Concluzie

În scenariul actual, GE este utilizat în companii mari producătoare, cum ar fi aeronavele, etc pentru a optimiza utilizarea timpului și a resurselor. Mai mulți oameni de știință lucrează la găsirea de noi modalități de a combina algoritmi genetici cu alte tehnici de optimizare.

Articole recomandate

Acesta este un ghid pentru Ce este algoritmul genetic? Aici discutăm introducerea, etapele și aplicațiile algoritmului genetic. De asemenea, puteți parcurge și alte articole sugerate -

  1. Algoritmi de rutare
  2. Tipuri de algoritmi
  3. Algoritmi de rețea neuronală
  4. Algoritmi de extragere a datelor
  5. ghid pentru exemple de algoritm C ++

Categorie:

Date mare