În domeniul inteligenței artificiale, un algoritm evolutiv (EA) este un subset al calculelor populației totale bazate pe optimizarea metaeuristică. EA folosește mecanisme inspirate de dezvoltarea biologică, cum ar fi reproducerea, mutația, recombinarea și selecția. Soluția candidată în problema algoritmilor de optimizare evolutivă joacă rolul indivizilor din populație. Și, de asemenea, funcția de fitness determină calitatea răspunsurilor.
Algoritmii evoluționari aproximează adesea bine soluțiile pentru toate tipurile de probleme. Pentru că, în mod ideal, ei nu fac nicio presupunere cu privire la peisajul fitness-ului de bază. Metodele utilizate pentru modelarea evolutivă și algoritmii genetici sunt de obicei limitate la studii ale proceselor microevolutive și modele de planificare bazate pe etapele celulare. În majoritatea aplicațiilor EA reale, complexitatea de calcul este un factor prohibitiv.
De faptaceastă problemă este legată de estimarea funcției de fitness. Aproximarea fitness este o soluție pentru a depăși această dificultate. Cu toate acestea, un EA aparent simplu poate rezolva probleme adesea complexe. Prin urmare, nu poate exista o relație directă între complexitatea secvenței și problemă. Mai multe detalii pot fi găsite în cărțile „Algoritmi evoluționari”.
Implementare
Pasul unu este de a crea o populație inițială de indivizi la întâmplare.
Pasul doi este de a evalua caracterul adecvat al fiecărui individ din acest grup (limită de timp, pregătire suficientă etc.).
Pasul trei - repetați următorii pași de regenerare până la finalizare:
- Selectați cei mai potriviti oameni pentru reproducere (părinți).
- Aduceți noi indivizi care au trecut de algoritmul evolutiv folosind încrucișarea și mutația pentru a obține descendenți.
- Evaluați condiția fizică individuală a oamenilor noi.
- Înlocuiți populația cea mai puțin potrivită cu acestea.
Tipuri
Algoritmul genetic este o secvență evolutivă, cel mai popular tip de consilier expert. Se caută o soluție a problemei sub formă de șiruri de numere (în mod tradițional binare, deși cele mai bune reprezentări sunt de obicei cele care reflectă mai mult în problema rezolvată) prin aplicarea de operatori precum recombinarea și mutația (uneori unul, în unele cazuri ambii).). Acest tip de Expert Advisor este adesea folosit în probleme de optimizare. Un alt nume pentru aceasta este fetura (din latină pentru „naștere”):
- Programare genetică. Prezintă soluții ca coduri de calculator, iar adecvarea lor este determinată de capacitatea lor de a efectua sarcini de calcul.
- Programare evolutivă. Similar cu algoritmul genetic evolutiv, dar structura este fixă, iar parametrii săi numerici se pot schimba.
- Programarea expresiei genelor. Dezvolta aplicații pentru computer, dar explorează sistemul genotip-fenotip, în care proiecte de diferite dimensiuni sunt codificate pe cromozomi liniari cu lungime fixă.
- Strategie. Funcționează cu vectori de numere reale ca reprezentări ale soluțiilor. Utilizează de obicei algoritmi auto-adaptabili pentru rata mutațiilor evolutive.
- Dezvoltare diferențială. Bazat pe diferențe vectoriale și, prin urmare, potrivit în primul rând pentru probleme de optimizare numerică.
- Neuroevoluție. Similar cu programarea evolutivă și algoritmii genetici. Dar acestea din urmă sunt rețele neuronale artificiale, care descriu structura și greutatea conexiunilor. Codificarea genomului poate fi directă sau indirectă.
Comparație cu procesele biologice
O posibilă limitare a multor algoritmi evolutivi este lipsa unei distincții clare între genotip și fenotip. În natură, un ovul fertilizat trece printr-un proces complex cunoscut sub numele de embriogeneză pentru a deveni matur. Se crede că această codificare indirectă face căutările genetice mai fiabile (adică, mai puțin probabil să provoace mutații fatale) și, de asemenea, poate îmbunătăți capacitatea organismului de a se dezvolta. O astfel de indirectă (cu alte cuvinte,codificări generative sau de dezvoltare) permit, de asemenea, evoluției să exploateze regularitatea în mediu.
Lucrările recente în embriogeneza artificială sau sistemele de dezvoltare încearcă să abordeze aceste probleme. Când se programează expresia genelor, regiunea genotip-fenotip este explorată cu succes, unde prima constă din cromozomi multigene liniari de lungime fixă, iar al doilea dintre mulți arbori de expresie sau programe de calculator de diferite dimensiuni și forme.
Tehnici similare
Algoritmii includ:
- Optimizare colonie de furnici. Se bazează pe ideea că insectele caută hrană conectându-se cu feromonii pentru a forma căi. Potrivit în primul rând pentru optimizarea combinatorie și problemele grafice.
- Algoritm de glisare rădăcină. Creatorul a fost inspirat de funcția rădăcinilor plantelor din natură.
- Algoritm pentru coloniile de albine artificiale. Pe baza comportamentului albinelor melifere. Este propus în primul rând pentru optimizarea numerică și extins pentru a rezolva probleme combinatorii, mărginite și multiobiective. Algoritmul albinelor se bazează pe comportamentul de hrană al insectelor. A fost aplicat în multe aplicații, cum ar fi rutarea și programarea.
- Optimizarea roiului de particule - pe baza ideilor de comportament al turmei de animale. Și, de asemenea, potrivit în primul rând pentru sarcini de proces numeric.
Alte metode metaeuristice populare
- Căutare de vânătoare. O metodă bazată pe prinderea în grup a anumitor animale, cum ar fi lupii, de exemplu, caredistribuie îndatoririle lor pentru a înconjura prada. Fiecare dintre membrii algoritmului evolutiv se raportează la ceilalți într-un fel. Acest lucru este valabil mai ales pentru lider. Aceasta este o metodă de optimizare continuă adaptată ca metodă de proces combinatorie.
- Căutați după măsurători. Spre deosebire de metodele metaeuristice bazate pe natură, algoritmul procesului adaptiv nu folosește metafora ca principiu principal. Mai degrabă, utilizează o metodă simplă, orientată spre performanță, bazată pe actualizarea parametrului raportului dimensiunii de căutare la fiecare iterație. Algoritmul Firefly este inspirat de modul în care licuricii se atrag unul pe altul cu lumina lor intermitentă. Acest lucru este util în special pentru optimizarea multimodală.
- Căutați armonie. Pe baza ideilor de comportament al muzicienilor. În acest caz, algoritmii evolutivi sunt calea de urmat pentru optimizarea combinatorie.
- Adaptare gaussiana. Bazat pe teoria informației. Folosit pentru a maximiza performanța și disponibilitatea medie. Un exemplu de algoritmi evolutivi în această situație: entropia în termodinamică și teoria informației.
Memetic
O metodă hibridă bazată pe ideea de meme a lui Richard Dawkins. De obicei, acesta ia forma unui algoritm bazat pe populație combinat cu proceduri individuale de învățare capabile să efectueze perfecționări locale. Subliniază utilizarea cunoștințelor specifice problemei și încearcă să organizeze căutări detaliate și globale într-un mod sinergic.
Evoluționaralgoritmii sunt o abordare euristică a problemelor care nu pot fi rezolvate cu ușurință în timp polinomial, cum ar fi problemele clasice NP-hard și orice altceva care ar dura prea mult pentru a fi procesat exhaustiv. Când sunt utilizate independent, sunt de obicei folosite pentru probleme combinatorii. Cu toate acestea, algoritmii genetici sunt adesea folosiți în tandem cu alte metode, acționând ca o modalitate rapidă de a găsi mai multe locuri de pornire optime cu care să lucrați.
Premisa algoritmului evolutiv (cunoscut sub numele de consilier) este destul de simplă, având în vedere că ești familiarizat cu procesul selecției naturale. Conține patru pași principali:
- inițializare;
- choice;
- operatori genetici;
- end.
Fiecare dintre acești pași corespunde aproximativ unui anumit aspect al selecției naturale și oferă modalități simple de modularizare a acelei categorii de algoritmi. Pur și simplu, în EA, cei mai apți membri vor supraviețui și se vor reproduce, în timp ce membrii nepotriviți vor muri și nu vor contribui la bazinul genetic al următoarei generații.
Inițializare
Pentru a porni algoritmul, trebuie mai întâi să creați un set de soluții. Populația va conține un număr arbitrar de posibile enunțuri de problemă, adesea denumite membri. Ele sunt adesea generate aleatoriu (în limita constrângerilor sarcinii) sau, dacă se cunosc anumite cunoștințe anterioare, centrate provizoriu în jurul a ceea ce este considerat ideal. Este important ca populația să acopere o gamă largă de soluții,deoarece este în esență un bazin genetic. Prin urmare, dacă cineva dorește să exploreze multe posibilități diferite în cadrul unui algoritm, ar trebui să se străduiască să aibă multe gene diferite.
Alegere
Odată ce populația a fost creată, membrii acesteia trebuie acum evaluați în funcție de funcția de fitness. Funcția de fitness preia caracteristicile unui membru și oferă o reprezentare numerică a cât de potrivit este membrul. Crearea acestora poate fi adesea foarte dificilă. Este important să găsiți un sistem bun care să reprezinte cu acuratețe datele. Acest lucru este foarte specific problemei. Acum este necesar să se calculeze potrivirea tuturor participanților și să se selecteze unii dintre cei mai buni membri.
Funcții cu obiective multiple
EA pot fi, de asemenea, extinse pentru a utiliza aceste sisteme. Acest lucru complică oarecum procesul, deoarece în loc să se identifice un punct optim, se obține un set la utilizarea lor. Setul de soluții se numește frontiera Pareto și conține elemente care sunt la fel de potrivite, în sensul că niciuna dintre ele nu o domină pe alta.
Operatori genetici
Acest pas include doi subpași: încrucișare și mutație. După selectarea celor mai buni termeni (de obicei primii 2, dar acest număr poate varia), aceștia sunt acum utilizați pentru a crea următoarea generație în algoritm. Prin aplicarea caracteristicilor părinților aleși se creează noi copii care sunt un amestec de calități. Acest lucru poate fi adesea dificil în funcție de tipul de date, dar de obicei în probleme combinatoriieste foarte posibil să amestecați și să scoateți combinații valide.
Acum este necesar să se introducă material genetic nou în generație. Dacă acest pas important nu este făcut, omul de știință va rămâne foarte repede blocat în extreme locale și nu va obține rezultate optime. Acest pas este o mutație și se face destul de simplu, schimbând o mică parte a copiilor în așa fel încât aceștia să nu reflecte în mod predominant subseturi de gene ale părinților. Mutația are loc de obicei în mod probabilistic, deoarece probabilitatea ca un copil să o primească, precum și severitatea acesteia, sunt determinate de distribuție.
Rezilierea
În final, algoritmul trebuie să se termine. Acest lucru se întâmplă de obicei în două cazuri: fie a atins un anumit timp maxim de execuție, fie a atins un prag de performanță. În acest moment, soluția finală este selectată și returnată.
Exemplu de algoritmi evolutivi
Acum, pentru a ilustra rezultatul acestui proces, trebuie să-l vedeți pe consilier în acțiune. Pentru a face acest lucru, ne putem aminti cum mai multe generații de dinozauri au învățat să meargă (stăpânind treptat pământul), optimizând structura corpului lor și aplicând forța musculară. Chiar dacă reptilele din generația timpurie nu puteau merge, consilierul a reușit să le evolueze în timp prin mutații și încrucișări într-o formă care ar putea merge.
Acești algoritmi devin din ce în ce mai relevanți în lumea modernă, deoarece soluțiile bazate pe aceștia sunt din ce în ce mai utilizate în industrii precum marketingul digital, finanțele șiasistență medicală.
Unde se folosesc EA?
Mai larg, algoritmii evolutivi sunt utilizați într-o mare varietate de aplicații, cum ar fi procesarea imaginilor, rutarea vehiculelor, optimizarea comunicațiilor mobile, dezvoltarea de software și chiar antrenamentul rețelelor neuronale artificiale. Aceste instrumente se află în centrul multor aplicații și site-uri web pe care oamenii le folosesc zilnic, inclusiv Google Maps și chiar jocuri precum The Sims. În plus, domeniul medical folosește EA pentru a ajuta la luarea deciziilor clinice cu privire la tratamentul cancerului. De fapt, algoritmii evolutivi sunt atât de robusti încât pot fi utilizați pentru a rezolva aproape orice problemă de optimizare.
Legea lui Moore
Prevalența în creștere a EO este determinată de doi factori principali: puterea de calcul disponibilă și acumularea de seturi mari de date. Prima poate fi descrisă de Legea lui Moore, care afirmă în esență că puterea de calcul dintr-un computer se dublează aproximativ la fiecare doi ani. Această predicție ține de zeci de ani. Al doilea factor se referă la dependența tot mai mare de tehnologie, care permite instituțiilor să colecteze o cantitate incredibil de mare de date, ceea ce le permite să analizeze tendințele și să optimizeze produsele.
Cum pot algoritmii evolutivi să-i ajute pe marketeri?
Condițiile pieței se schimbă rapid și sunt foarte competitive. Acest lucru i-a forțat pe managerii de marketing să concureze pentru a lua decizii mai bune. Creșterea disponibilitățiiputerea de calcul a determinat lucrătorii să folosească EA pentru rezolvarea problemelor.
Optimizarea conversiilor
Unul dintre obiectivele principale este creșterea ratei de vizitatori ai site-ului. Această problemă se rezumă la optimizarea numărului de utilizatori care fac ceea ce vrea marketerul. De exemplu, dacă o companie vinde laptopuri, idealul este să crească numărul de vizitatori ai site-ului care ajung să cumpere produsul. Aceasta este esența optimizării ratei de conversie.
Unul dintre aspectele surprinzător de importante este alegerea interfeței cu utilizatorul. Daca web design-ul nu este foarte user friendly, sunt cei care ajung sa nu cumpere produsul dintr-un motiv sau altul. Scopul este de a reduce numărul de utilizatori care ajung să nu efectueze conversii, ceea ce crește profitul total.
