Algorisme genètic

De Viquipèdia
Dreceres ràpides: navegació, cerca

Un algorisme genètic (GA de l'anglès Genetic Algorithm) és una tècnica de cerca utilitzada en informàtica per trobar solucions aproximades a problemes d'optimització i cerca. 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 el creuament (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 0s i 1s, però les codificacions diferents són també possibles. L'evolució comença des d'una població d'individus completament fortuïts i passa en 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[modifica | modifica el codi]

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 GAs romania en gran part teòrica fins al mitjans dels anys 1980, quan 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 resoldre difícils tasques de planificació, aptitud de dades, mesurar tendències i problemes pressupostaris i, virtualment, qualsevol altre tipus de problema d'optimització combinatoria.

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

Elaboració[modifica | modifica el codi]

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 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ó de creuament simple. També s'utilitzaven representacions de mida variables, però l'aplicació de creuament é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, on 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 aleatoria, llavors la millora a través d'un procés repetitiu de mutació, creuament i selecció.

Inicialització[modifica | modifica el codi]

Inicialment moltes solucions individuals es generen fortuïtament per formar una població inicial. La mida de població depèn de la natura 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ó[modifica | modifica el codi]

A cada generació successiva, una proporció de la població existent se selecciona per a engendrar una nova generació. Se seleccionen solucions individuals a través de un procés basat en l'aptitud, on 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 forma preferent les millors solucions. D'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 una proporció petita de solucions menys aptes són seleccionades. Això ajuda a mantenir gran la diversitat de la població, evitant 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ó[modifica | modifica el codi]

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

Per a cada solució nova que ha de ser produïda, un parell de solucions "pare" se selecciona per criar des del magatzem seleccionat prèviament. Produint una solució "fill" que utilitza els mètodes citats de creuament 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 una població nova de solucions de mida apropiada es generi.

Aquests processos generen 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 raons abans esmentades.

Finalització[modifica | modifica el codi]

Aquest procés generacional es repeteix fins que s'arriba a una condició de finalització. 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 fixats.
  • 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 pseudo-codi[modifica | modifica el codi]

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

Observacions[modifica | modifica el codi]

Existeixen diverses observacions sobre la generació de solucios a través d'algorismes genètics:

  • En molts problemes amb complexitat suficient, els GAs poden tenir una tendència de convergir cap a un òptim local més que al ò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, 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 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 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ó quan la qualitat de solució baixa (anomenada hipermutació provocada), o ocasionalment introduint elements totalment nous, generats aleatòriament a la selecció de gens (anomenats immigrants fortuïts). La recerca recent també ha mostrat els beneficis d'utilitzar la preadaptació biològica per resoldre aquest problema.
  • La selecció és clarament un operador genètic important, però l'opinió està dividida sobre la importància de creuament contra mutació. Alguns sostenen que el creuament és el més important, mentre que la mutació és només necessària per assegurar que les solucions potencials no es perdin. Altres discuteixen que el creuament en una població en gran part uniforme només serveix per propagar innovacions originalment trobades per mutació, i en una població no uniforme el creuament és gairebé sempre equivalent a una mutació molt gran (que és probable que sigui catastròfica).
  • Sovint els GAs 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 (necessitant 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[modifica | modifica el codi]

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 creuament i mutació en el nivell de bits. Unes altres variants tracten el cromosoma com una llista de números que són índexs a una taula d'instrucció, hashes, nodes en una llista connectada, objectes, o qualsevol altra estructura de dades imaginable. El creuament 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òmics 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 codificació grisa. D'aquesta manera, els canvis petits a l'enter es poden immediatament efectuar a través de mutacions o creuaments. 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 de creuament) han d'ocórrer en ordre per convertir el cromosoma en una millor solució.

Altres enfocs impliquen utilitzar vectors de nombres reals en comptes de cadenes de bits per representar cromosomes. Teòricament, a més petit l'alfabet, millor rendiment, però paradoxalment, els millors resultats s'han obtingut d'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 a la pròxima, de forma inalterada. Aquesta estratègia es coneix com selecció elitista.

Les implementacions paral·leles d'algorismes genètics vénen en dos tipus. Els algorismes genètics paral·lels 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 a 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 a la funció d'aptitud.

Domini dels problemes[modifica | modifica el codi]

Els problemes que semblen ser especialment apropiats per a solucionar amb 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 GAs. Els GAs també s'han aplicat a 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 problema que tenen un paisatge de d'aptitud complex perque la recombinació està dissenyada per moure la població fora de l'òptim local que en el que un tradicional algorisme d'escalada de turons es podria quedar aturat.

Aplicacions[modifica | modifica el codi]

  • Disseny automatitzat, incloent 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 inducció gramàtica, i altres aspectes de Processament de 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 de l'Presoner Iterador
  • Optimització de sistemes de compressió de dades, per exemple, usant wavelets.
  • Predicció de Plegament de proteïnes.
  • Optimització de Layout.
  • Predicció d'estructura de ARN.
  • En bioinformàtica, Alineament múltiple de seqüències.
  • Aplicacions en planificació de processos industrials, incloent planificació job-shop.
  • 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[modifica | modifica el codi]