[HOME PAGE] [STORES] [CLASSICISTRANIERI.COM] [FOTO] [YOUTUBE CHANNEL]

Algorisme genètic - Viquipèdia

Algorisme genètic

De Viquipèdia

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 la 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, es 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.

Taula de continguts

[edita] 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 GAs romania en gran part teòrica fins al mitjans dels anys 1980, quan la 1a Conferència Internacional en Algoritmes 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 àmplia 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.

[edita] Procediment d'un GA

Un algorisme genètic típic es 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ó de aptitud sempre depèn del problema a tractar. Per exemple, en el "problema de la motxilla" es preten 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, perque 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ó.

[edita] Inicialització

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.

[edita] Selecció

A cada generació successiva, una proporció de la població existent es selecciona per a engendrar una nova generació. Es seleccionen solucions individuals a través de un procés basat en l'aptitud, on les solucions més aptes (tal i 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 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.

[edita] Reproducció

El següent pas es 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" es 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 .

[edita] Finalització

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 número 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ó succesiva ja no produeix millors resultats.
  • Inspecció manual.
  • Combinacions dels anteriors.

[edita] Algorisme en pseudo-codi

Escollir la població inicial.
Repetir o iterar.
 Evaluar 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 la condició de finalització

[edita] Observacions

Existeixen diverses observacions sobre la generació de solucios a través de 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 de 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ó de 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 aleatoriament 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 es 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 algoritmes d'optimització més simples poden trobar millors solucions que els algoritmes genètics (necessitant la mateixa quantitat de temps de càlcul). Els algoritmes 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 que 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'algoritme.

[edita] 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 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 números 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 números 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 algoritmes genètics per a problemes d'optimització en línia, introdueixen dependència de temps o soroll a la funció d'aptitud.

[edita] Domini dels problemes

Els problemes que semblen ser especialment apropiats per a solucionar amb algoritmes genètics inclouen la 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 algoritmes genètics s'apliquen sovint com a aproximació per resoldre problemes d'optimització globals.

Com a regla general els algoritmes 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 del optim local que en el que un tradicional algoritme d'escalada de turons es podria quedar aturat.

[edita] Enllaços externs en anglès