En el camp de la intel·ligència artificial, un algorisme evolutiu (EA) és un subconjunt de càlculs de població total basats en l'optimització metaheurística. L'EA utilitza mecanismes inspirats en el desenvolupament biològic com ara la reproducció, la mutació, la recombinació i la selecció. La solució candidata al problema dels algorismes d'optimització evolutiva juga el paper dels individus de la població. I també la funció de fitness determina la qualitat de les respostes.
Els algorismes evolutius sovint aproximen bé les solucions a tot tipus de problemes. Perquè idealment no fan cap suposició sobre el panorama de la condició física subjacent. Els mètodes utilitzats per a la modelització evolutiva i els algorismes genètics solen limitar-se a estudis de processos microevolutius i models de planificació basats en etapes cel·lulars. A la majoria d'aplicacions d'EA reals, la complexitat computacional és un factor prohibitiu.
En realitataquest problema està relacionat amb l'estimació de la funció de fitness. L'aproximació de la condició física és una solució per superar aquesta dificultat. Tanmateix, un EA aparentment simple pot resoldre problemes sovint complexos. Per tant, no hi pot haver una relació directa entre la complexitat de la seqüència i el problema. Trobareu més detalls als llibres "Algoritmes evolutius".
Implementació
El primer pas és crear una població inicial d'individus a l'atzar.
El segon pas consisteix a avaluar la idoneïtat de cada individu d'aquest grup (límit de temps, suficient preparació, etc.).
Pas tres: repetiu els passos de regeneració següents fins a completar-los:
- Seleccioneu les persones més adequades per a la cria (pares).
- Porteu persones noves que hagin superat l'algoritme evolutiu mitjançant l'encreuament i la mutació per obtenir descendència.
- Avaluar l'aptitud individual de la gent nova.
- Substituïu la població menys ajustada per ells.
Tipus
L'algoritme genètic és una seqüència evolutiva, el tipus d'assessor expert més popular. Es busca una solució al problema en forma de cadenes de nombres (tradicionalment binaris, encara que les millors representacions solen ser les que reflecteixen més en el problema que es resol) aplicant operadors com la recombinació i la mutació (de vegades un, en alguns casos ambdós).). Aquest tipus d'assessor expert s'utilitza sovint en problemes d'optimització. Un altre nom per a això és fetura (del llatí per "naixement"):
- Programació genètica. Presenta solucions com a codis informàtics, i la seva idoneïtat ve determinada per la seva capacitat per realitzar tasques computacionals.
- Programació evolutiva. Similar a l'algorisme genètic evolutiu, però l'estructura és fixa i els seus paràmetres numèrics poden canviar.
- Programació de l'expressió gènica. Desenvolupa aplicacions informàtiques, però explora el sistema genotip-fenotip, on projectes de diferents mides es codifiquen en cromosomes lineals de longitud fixa.
- Estratègia. Treballa amb vectors de nombres reals com a representacions de solucions. Normalment utilitza algorismes de taxa de mutació evolutiva autoadaptativa.
- Desenvolupament diferencial. Basat en diferències vectorials i, per tant, principalment adequat per a problemes d'optimització numèrica.
- Neuroevolució. Similar a la programació evolutiva i als algorismes genètics. Però aquestes últimes són xarxes neuronals artificials, que descriuen l'estructura i el pes de les connexions. La codificació del genoma pot ser directa o indirecta.
Comparació amb processos biològics
Una possible limitació de molts algorismes evolutius és la manca d'una distinció clara entre genotip i fenotip. A la natura, un òvul fecundat passa per un procés complex conegut com a embriogènesi per arribar a la maduresa. Es creu que aquesta codificació indirecta fa que les cerques genètiques siguin més fiables (és a dir, menys propenses a causar mutacions mortals) i també pot millorar la capacitat de desenvolupament de l'organisme. Aquests indirectes (en altres paraules,les codificacions generatives o de desenvolupament) també permeten que l'evolució aprofiti la regularitat de l'entorn.
El treball recent en embriogènesi artificial o sistemes de desenvolupament pretén abordar aquests problemes. Quan es programa l'expressió gènica, s'explora amb èxit la regió genotip-fenotip, on la primera consisteix en cromosomes multigènics lineals de longitud fixa, i la segona de molts arbres d'expressió o programes informàtics de diferents mides i formes.
Tècniques relacionades
Els algorismes inclouen:
- Optimització de colònies de formigues. Es basa en la idea que els insectes busquen aliment connectant-se amb feromones per formar camins. Adequat principalment per a problemes d'optimització combinatòria i gràfics.
- Algorisme de control lliscant arrel. El creador es va inspirar en la funció de les arrels de les plantes a la natura.
- Algorisme per a colònies d'abelles artificials. Basat en el comportament de les abelles de mel. Es proposa principalment per a l'optimització numèrica i s'estén per resoldre problemes combinatoris, acotats i multiobjectiu. L'algoritme de les abelles es basa en el comportament d'alimentació dels insectes. S'ha aplicat en moltes aplicacions, com ara l'encaminament i la programació.
- Optimització de l'eixam de partícules: basat en idees de comportament dels ramats d'animals. I també és adequat principalment per a tasques de procés numèric.
Altres mètodes metaheurístics populars
- Cerca de caça. Un mètode basat en la captura grupal de determinats animals, com els llops, per exemple, quedistribueixen els seus deures per envoltar la presa. Cadascun dels membres de l'algorisme evolutiu es relaciona amb els altres d'alguna manera. Això és especialment cert per al líder. Aquest és un mètode d'optimització contínua adaptat com a mètode de procés combinatori.
- Cerca per mesures. A diferència dels mètodes metaheurístics basats en la naturalesa, l'algoritme de procés adaptatiu no utilitza la metàfora com a principi principal. Més aviat, utilitza un mètode senzill orientat al rendiment basat en l'actualització del paràmetre de relació de dimensió de cerca a cada iteració. L'algorisme de Firefly s'inspira en com s'atrauen les cuques amb la seva llum intermitent. Això és especialment útil per a l'optimització multimodal.
- Cerca l'harmonia. A partir de les idees del comportament dels músics. En aquest cas, els algorismes evolutius són el camí a seguir per a l'optimització combinatòria.
- Adaptació gaussiana. Basat en la teoria de la informació. S'utilitza per maximitzar el rendiment i la disponibilitat mitjana. Un exemple d'algorismes evolutius en aquesta situació: entropia en termodinàmica i teoria de la informació.
Memetic
Un mètode híbrid basat en la idea d'un meme de Richard Dawkins. Normalment pren la forma d'un algorisme basat en la població combinat amb procediments d'aprenentatge individuals capaços de realitzar perfeccionaments locals. Destaca l'ús del coneixement específic del problema i intenta organitzar cerques globals i detallades de manera sinèrgica.
EvolucionariEls algorismes són un enfocament heurístic de problemes que no es poden resoldre fàcilment en temps polinomial, com ara els problemes clàssics NP-hard i qualsevol altra cosa que trigaria massa a processar-se exhaustivament. Quan s'utilitzen de manera independent, s'utilitzen generalment per a problemes combinatoris. Tanmateix, els algorismes genètics s'utilitzen sovint juntament amb altres mètodes, i actuen com una forma ràpida de trobar diversos llocs de partida òptims per treballar.
La premissa de l'algorisme evolutiu (conegut com a assessor) és bastant simple atès que esteu familiaritzat amb el procés de selecció natural. Conté quatre passos principals:
- inicialització;
- elecció;
- operadors genètics;
- final.
Cada un d'aquests passos correspon aproximadament a un aspecte determinat de la selecció natural i ofereix maneres senzilles de modular aquesta categoria d'algorismes. En poques paraules, a EA, els membres més aptes sobreviuran i es reproduiran, mentre que els membres no aptes moriran i no contribuiran a la reserva genètica de la propera generació.
Inicialització
Per iniciar l'algorisme, primer heu de crear un conjunt de solucions. La població contindrà un nombre arbitrari de possibles enunciats de problemes, sovint anomenats membres. Sovint es generen aleatòriament (dins de les limitacions de la tasca) o, si es coneix algun coneixement previ, es centren provisionalment al voltant del que es considera ideal. És important que la població cobreixi un ampli ventall de solucions,perquè és essencialment un pool genètic. Per tant, si un vol explorar moltes possibilitats diferents dins d'un algorisme, s'ha d'esforçar per tenir molts gens diferents.
Elecció
Un cop creada la població, ara s'ha d'avaluar els seus membres segons la funció de fitness. La funció d'aptitud pren les característiques d'un membre i dóna una representació numèrica de la forma en què està el membre. Crear-los sovint pot ser molt difícil. És important trobar un bon sistema que representi les dades amb precisió. Això és molt específic del problema. Ara cal calcular la idoneïtat de tots els participants i seleccionar alguns dels millors membres.
Múltiples funcions d'objectiu
Els EA també es poden ampliar per utilitzar aquests sistemes. Això complica una mica el procés, perquè en comptes d'identificar un punt òptim, s'obté un conjunt en utilitzar-los. El conjunt de solucions s'anomena frontera de Pareto i conté elements igualment adequats en el sentit que cap d'ells en domina cap altre.
Operadors genètics
Aquest pas inclou dos subpassos: encreuament i mutació. Després de seleccionar els millors termes (normalment els 2 principals, però aquest nombre pot variar), ara s'utilitzen per crear la següent generació de l'algorisme. Aplicant les característiques dels pares escollits, es creen nous fills que són una barreja de qualitats. Això sovint pot ser difícil depenent del tipus de dades, però normalment en problemes combinatorisés molt possible barrejar i generar combinacions vàlides.
Ara cal introduir nou material genètic a la generació. Si no es fa aquest pas important, el científic es quedarà atrapat molt ràpidament en extrems locals i no obtindrà resultats òptims. Aquest pas és una mutació, i es fa de manera senzilla, canviant una petita part dels fills de tal manera que no reflecteixen predominantment subconjunts dels gens dels pares. La mutació sol produir-se de manera probabilística, ja que la probabilitat que un nen la tingui, així com la seva gravetat, es determina per la distribució.
Terminació
Al final, l'algorisme ha d'acabar. Això sol passar en dos casos: o bé s'ha arribat a un temps màxim d'execució o ha arribat a un llindar de rendiment. En aquest punt, es selecciona la solució final i es retorna.
Exemple d'algorismes evolutius
Ara, per il·lustrar el resultat d'aquest procés, heu de veure l'assessor en acció. Per fer-ho, podem recordar com diverses generacions de dinosaures van aprendre a caminar (dominant progressivament la terra), optimitzant l'estructura del seu cos i aplicant força muscular. Tot i que els rèptils de les primeres generacions no podien caminar, l'assessor va ser capaç d'evolucionar-los amb el temps mitjançant la mutació i l'encreuament cap a una forma que pogués caminar.
Aquests algorismes són cada cop més rellevants al món modern, ja que les solucions basades en ells s'utilitzen cada cop més en indústries com el màrqueting digital, les finances iassistència sanitària.
On s'utilitzen els EA?
En termes més generals, els algorismes evolutius s'utilitzen en una gran varietat d'aplicacions com ara el processament d'imatges, l'encaminament de vehicles, l'optimització de comunicacions mòbils, el desenvolupament de programari i fins i tot l'entrenament de xarxes neuronals artificials. Aquestes eines es troben al cor de moltes de les aplicacions i llocs web que la gent utilitza diàriament, com ara Google Maps i fins i tot jocs com Els Sims. A més, l'àmbit mèdic utilitza EA per ajudar a prendre decisions clíniques pel que fa al tractament del càncer. De fet, els algorismes evolutius són tan robusts que es poden utilitzar per resoldre gairebé qualsevol problema d'optimització.
Llei de Moore
La creixent prevalença de l'EO està impulsada per dos factors principals: la potència de càlcul disponible i l'acumulació de grans conjunts de dades. El primer pot ser descrit per la Llei de Moore, que bàsicament estableix que la quantitat de potència de càlcul en un ordinador es duplica aproximadament cada dos anys. Aquesta predicció s'ha mantingut durant dècades. El segon factor es relaciona amb la creixent dependència de la tecnologia, que permet a les institucions recollir una quantitat increïblement gran de dades, que els permet analitzar tendències i optimitzar els productes.
Com poden ajudar els algorismes evolutius els venedors?
Les condicions del mercat canvien ràpidament i són molt competitives. Això ha obligat els responsables de màrqueting a competir per prendre millors decisions. Augment de la disponibilitatLa potència informàtica ha fet que els treballadors utilitzin EA per resoldre problemes.
Optimització de conversions
Un dels principals objectius és augmentar la taxa de visitants al lloc. Aquest problema es redueix a optimitzar el nombre d'usuaris que fan el que vol el venedor. Per exemple, si una empresa ven ordinadors portàtils, l'ideal és augmentar el nombre de visitants del lloc que acaben comprant el producte. Aquesta és l'essència de l'optimització del percentatge de conversions.
Un dels aspectes sorprenentment importants és l'elecció de la interfície d'usuari. Si el disseny web no és molt fàcil d'usar, hi ha qui acaba no comprant el producte per un motiu o un altre. Aleshores, l'objectiu és reduir el nombre d'usuaris que acaben sense convertir, la qual cosa augmenta el benefici global.
