Algorisme genètic

Un algorisme genètic (GA, de l'anglès Genetic Algorithm) és una tècnica de cerca utilitzada en informàtica per a trobar solucions aproximades a problemes d'optimització i recerca. Els algorismes genètics són una classe particular d'algorismes evolutius que utilitzen tècniques inspirades per l'evolució biològica, com l'herència, la mutació, la selecció i l'encreuament (també anomenada recombinació genètica).

Els algorismes genètics s'implementen típicament com una simulació informàtica, en la qual una població de representacions abstractes (anomenades cromosomes) de solucions candidates (anomenades individus) a un problema d'optimització evoluciona cap a millors solucions. Tradicionalment, les solucions es representen com sèries binàries de 0 i 1, però les codificacions diferents són també possibles. L'evolució comença des d'una població d'individus completament fortuïts i passa a diferents generacions. En cada generació, l'aptitud de la població sencera s'avalua, se seleccionen múltiples individus de manera estocàstica de la població actual (basada en la seva aptitud o idoneïtat), i es modifiquen, mutant o recombinant, per formar una nova població. La nova població s'utilitza en la següent iteració de l'algorisme.

Història

Els algorismes genètics es van originar a partir dels estudis d'autòmats cel·lulars, dirigits per John Holland i els seus col·legues a la Universitat de Michigan. La recerca en GA romania en gran part teòrica fins als mitjans dels anys 1980, quan es va realitzar la 1a Conferència Internacional en Algorismes Genètics a la Universitat d'Illinois. Mentre l'interès acadèmic augmentava, l'augment dramàtic en potència computacional dels ordinadors personals va permetre l'aplicació pràctica de la nova tècnica. El 1989, l'escriptor del New York Times John Markoff escrivia sobre Evolver, el primer algorisme genètic comercialment disponible per a ordinadors personals. Les aplicacions informàtiques de consum començaven a emergir en una varietat ampla de camps, i aquests algorismes són ara utilitzats per una majoria de companyies de la llista Fortune 500 per a resoldre difícils tasques de planificació, aptitud de dades, mesurar tendències i problemes pressupostaris i, virtualment, qualsevol altre tipus de problema d'optimització combinatòria.

El 1999, per primer cop en la història, es va concedir una patent a un invent no realitzat directament per un ésser humà: es tracta d'una antena de forma estranya, però que funciona perfectament en les condicions a què estava destinada.

Elaboració

Un algorisme genètic típic és definit per dos termes:

1. Una representació genètica de les solucions, i
2. Una funció d'aptitud per a avaluar-les.

La representació estàndard és un vector de bits. Vectors d'altres tipus i estructures es poden utilitzar essencialment de la mateixa manera. La propietat principal que fa convenients aquestes representacions genètiques és que les seves parts s'alineen fàcilment a causa de la seva mida fixa, que facilita l'operació d'encreuament simple. També s'utilitzaven representacions de mida variables, però l'aplicació d'encreuament és més complexa en aquest cas. Representacions de tipus arbre són explorades en la programació genètica i les representacions de forma lliure s'exploren en algorismes genètics assistits per humans (HBGA, de l'anglès Human-based Genetic Algorithm).

La funció d'aptitud es defineix sobre la representació genètica i mesura la qualitat de la solució representada. La funció d'aptitud sempre depèn del problema a tractar. Per exemple, en el "problema de la motxilla" es pretén maximitzar el valor total dels objectes que podem posar en una motxilla d'una capacitat fixa. Una representació d'una solució podria ser un vector de bits, en què cada bit representa un objecte diferent, i el valor del bit (1 o 0) representa si l'objecte és o no a la motxilla. No qualsevol representació és vàlida, perquè la quantitat d'objectes pot excedir la capacitat de la motxilla. L'aptitud de la solució és la suma de valors de tots els objectes a la motxilla si la representació és vàlida, o altrament. En alguns problemes, és difícil o fins i tot impossible definir l'expressió d'aptitud; en aquests casos, s'utilitzen algorismes genètics interactius (IGA, de l'anglès Interactive Genetic Algorithm).

Una vegada s'obté la representació genètica i la funció d'aptitud definides, el GA procedeix a inicialitzar la població de solucions de manera aleatòria; llavors, la millora amb un procés repetitiu de mutació, encreuament i selecció.

Inicialització

Inicialment, moltes solucions individuals es generen fortuïtament per formar una població inicial. La mida de població depèn de la naturalesa del problema, però típicament conté uns quants centenars o milers de solucions possibles. Tradicionalment, la població es genera fortuïtament, cobrint la gamma sencera de solucions possibles (l'espai de recerca). Ocasionalment, les solucions es poden "sembrar" en àrees on és probable que es trobin solucions òptimes.

Selecció

A cada generació successiva, una proporció de la població existent se selecciona per a engendrar una nova generació. Se seleccionen solucions individuals mitjançant un procés basat en l'aptitud, en què les solucions més aptes (tal com mesura la funció d'aptitud) tenen típicament més possibilitats de ser elegides. Alguns mètodes de selecció avaluen l'aptitud de cada solució i seleccionen de manera preferent les millors solucions. Altres mètodes avaluen només una mostra estadística de la població, perquè aquest procés consumeix molt de temps.

La majoria de les funcions són estocàstiques i dissenyades de manera que se selecciona una proporció petita de solucions menys aptes. Això ajuda a mantenir de manera àmplia la diversitat de la població, i s'evita la convergència prematura en solucions pobres. Els mètodes de selecció populars i ben estudiats inclouen selecció de la ruleta i selecció per torneig.

Reproducció

El pas següent és crear una segona generació de la població de solucions a partir d'aquelles seleccionades amb els operadors genètics: encreuament (o recombinació) i mutació.

Per a cada solució nova que ha de ser produïda, se selecciona un parell de solucions "pare" per criar-les des del magatzem seleccionat prèviament. Produint una solució "fill" que utilitza els mètodes citats d'encreuament i mutació, es crea una solució nova que típicament comparteix moltes de les característiques dels seus "pares". Els pares nous se seleccionen per a cada fill, i el procés continua fins que es generi una població nova de solucions de mida apropiada.

Aquests processos creen la pròxima població de generació de cromosomes que és diferent de la generació inicial. Generalment, l'aptitud mitjana haurà augmentat per a la població, ja que només els millors organismes des de la primera generació se seleccionen per criar, junt amb una proporció petita de menys solucions aptes, per les raons abans esmentades.

Finalització

Aquest procés generacional es repeteix fins que s'arriba a una condició de finalització. Les condicions de finalització més comunes són:

• S'ha trobat una solució que satisfà un criteri mínim.
• S'ha arribat a un nombre de generacions fixat.
• S'acaba el pressupost (temps computacional/diners).
• La solució amb la millor aptitud ha arribat a un altiplà de tal manera que cada iteració successiva ja no produeix millors resultats.
• Inspecció manual.
• Combinacions dels anteriors.

Algorisme en pseudocodi

Escollir la població inicial.
Repetir o iterar.
Avaluar l'aptitud individual de certes proporcions de la població.
Seleccionar parells d'individuals segons la millor aptitud per a reproduir.
Generar una nova generació amb l'encreuament i la mutació.
Fins a la condició de finalització

Observacions

Existeixen diverses observacions sobre la generació de solucions amb algorismes genètics:

• En molts problemes amb complexitat suficient, els GA poden tenir una tendència a convergir cap a un òptim local més que a l'òptim global del problema. La probabilitat que això passi depèn de la forma del paisatge d'aptitud: certs problemes poden proporcionar una pujada fàcil cap a un global òptim; d'altres poden fer més fàcil que la funció trobi l'òptim local. Aquest problema es pot alleujar utilitzant una funció d'aptitud diferent, o utilitzant tècniques per a mantenir una població diversa de solucions.

• Operar conjunts de dades dinàmics és difícil, perquè els genomes comencen a convergir de bon principi cap a solucions que ja no poden ser vàlides per a dades posteriors. Uns quants mètodes s'han proposat per corregir aquest problema augmentant la diversitat genètica d'alguna manera i evitant la primera convergència; qualsevol augment de la probabilitat de mutació es pot donar quan la qualitat de solució baixa (anomenada hipermutació provocada), o ocasionalment introduint elements totalment nous, generats aleatòriament en la selecció de gens (anomenats immigrants fortuïts). La recerca recent també ha mostrat els beneficis d'utilitzar la preadaptació biològica per a resoldre aquest problema.

• La selecció és clarament un operador genètic important, però l'opinió està dividida sobre la importància de l'encreuament contra la mutació. Alguns sostenen que l'encreuament és el més important, mentre que la mutació és només necessària per a assegurar que les solucions potencials no es perdin. D'altres discuteixen que l'encreuament en una població en gran part uniforme només serveix per a propagar innovacions originalment trobades per mutació, i en una població no uniforme l'encreuament és gairebé sempre equivalent a una mutació molt gran (que és probable que sigui catastròfica).

• Sovint els GA poden localitzar ràpidament bones solucions, fins i tot per a espais de recerca difícils.

• Per a problemes d'optimització específics i instanciacions de problema, els algorismes d'optimització més simples poden trobar millors solucions que els algorismes genètics (i necessiten la mateixa quantitat de temps de càlcul). Els algorismes alternatius i complementaris inclouen la recuita simulada, l'escalada de turons i l'optimització d'eixam de partícula.

• Com amb tots els problemes d'aprenentatge de màquines actuals, és bona idea sintonitzar el valor dels paràmetres com la probabilitat de mutació, probabilitat de recombinació i dimensió de la població per trobar escenes raonables per a la classe de problema en què treballem. Una proporció de mutació molt petita pot conduir a una deriva genètica (que no és ergòdica per naturalesa) o convergència prematura de l'algorisme genètic dins un òptim local. Una proporció de mutació massa alta pot conduir a la pèrdua de bones solucions. Hi ha fites inferiors i superiors teòriques per a aquests paràmetres, encara que no pràctiques, que poden ajudar a selecciónar un valor.

• L'aplicació i avaluació de la funció d'aptitud és un factor important en la velocitat i eficiència de l'algorisme.

Variants

L'algorisme més simple representa cada cromosoma com una cadena de bits. Típicament, els paràmetres numèrics poden ser representats per enters, encara que és possible utilitzar representacions de punt flotant. L'algorisme bàsic realitza encreuament i mutació en el nivell de bits. Unes altres variants tracten el cromosoma com una llista de números que són índexs en una taula d'instrucció, hashes, nodes en una llista connectada, objectes, o qualsevol altra estructura de dades imaginable. L'encreuament i mutació es realitzen respectant els límits de cada element. Per a la majoria dels tipus de dades, es poden dissenyar operadors de variació específics. Els tipus de dades cromosòmiques diferents poden treballar millor o pitjor per a diferents dominis de problema.

Quan s'utilitzen representacions de cadenes de bits d'enters, s'empra sovint la codificació grisa. D'aquesta manera, els canvis petits en l'enter es poden immediatament efectuar amb mutacions o encreuaments. S'ha trobat que això ajuda a evitar convergència prematura en les anomenades Hamming walls, en les quals moltes mutacions simultànies (o esdeveniments d'encreuament) han d'ocórrer en ordre per a convertir el cromosoma en una millor solució.

Altres enfocaments impliquen utilitzar vectors de nombres reals en comptes de cadenes de bits per a representar cromosomes. Teòricament, com més petit sigui l'alfabet, millor en serà el rendiment; però, paradoxalment, els millors resultats s'han obtingut en utilitzar cromosomes amb vectors de nombres reals.

Una petita variant, però molt reeixida, del procés general de construir una població nova és permetre a alguns dels millors organismes d'una generació passar-ne a la pròxima, de forma inalterada. Aquesta estratègia es coneix com a selecció elitista.

Les implementacions paral·leles d'algorismes genètics venen en dos tipus. Els algorismes genètics paral·lels de gradació gruixuda assumeixen una població en cada un dels nodes, i migració d'individus entre els nodes. Els algorismes genètics paral·lels de gradació fina assumeixen un individu en cada node de processadors que s'utilitza amb individus veïns per a la selecció i reproducció. Unes altres variants, com algorismes genètics per a problemes d'optimització en línia, introdueixen dependència de temps o soroll en la funció d'aptitud.

Domini dels problemes

Els problemes que semblen especialment apropiats per a solucionar algorismes genètics inclouen l'edició d'horaris i la planificació de problemes, i molts paquets de programes de planificació de tasques es basen en GA. Els GA també s'han aplicat en enginyeria. Els algorismes genètics s'apliquen sovint com a aproximació per resoldre problemes d'optimització globals.

Com a regla general, els algorismes genètics podrien ser útils en dominis de problemes que tenen un paisatge d'aptitud complex, perquè la recombinació està dissenyada per moure la població fora de l'òptim local, que en un tradicional algorisme d'escalada de turons es podria quedar aturat.

Aplicacions

• Disseny automatitzat, incloent-hi recerca en disseny de materials i disseny multiobjectiu de components automobilístics: millor comportament davant xocs, estalvis de pes, millora d'aerodinàmica, etc.
• Disseny automatitzat d'equipament industrial.
• Disseny automatitzat de sistemes de comerç en el sector financer.
• Construcció d'arbres filogenètics.
• Disseny de sistemes de distribució d'aigües.
• Disseny de topologies de circuits impresos.
• Disseny de topologies de xarxes computacionals.
• En teoria de jocs, resolució d'equilibris.
• Anàlisi d'expressió de gens.
• Aprenentatge de comportament de robots.
• Aprenentatge de regles de lògica difusa.
• Anàlisi lingüística, incloent-hi inducció gramàtica, i altres aspectes del processament del llenguatge natural, com ara eliminació d'ambigüitat de sentit.
• Infraestructura de xarxes de comunicacions mòbils.
• Optimització d'estructures moleculars.
• Planificació de producció multicriteri.
• Predicció.
• Aplicació d'algorismes genètics al dilema del presoner iterador
• Optimització de sistemes de compressió de dades, per exemple, usant ondetes.
• Predicció de plegament de proteïnes.
• Optimització de Layout.
• Predicció d'estructura d'ARN.
• En bioinformàtica, alineament múltiple de seqüències.
• Aplicacions en planificació de processos industrials, incloent-hi planificació treball-botiga.
• Selecció òptima de models matemàtics per a la descripció de sistemes biològics.
• Maneig de residus sòlids.
• Enginyeria de programari.
• Construcció d'horaris en grans universitats, evitant conflictes de classes.
• Problema del viatjant.
• Troballa d'errors en programes.
• Optimització de producció i distribució d'energia elèctrica.
• Disseny de xarxes geodèsiques (problemes de disseny).
• Calibratge i detecció de danys en estructures civils.

Enllaços externs

• DigitalBiology.NET Arxivat 2015-08-01 a Wayback Machine..
• Genetic Algorithms Index Arxivat 2016-03-03 a Wayback Machine..
• http://geneura.ugr.es/~jmerelo/ie/ags.htm Arxivat 2005-10-28 a Wayback Machine..
• http://cs.felk.cvut.cz/~xobitko/ga/ Arxivat 2005-09-03 a Wayback Machine. - Una introducció en línia als algoritmes genètics amb miniaplicacions de Java.
• Genetic Algorithm Solves the Toads and Frogs Puzzle en Cut-the-knot.

Viccionari