Anar al contingut

Cromosoma (computació evolutiva)

De L'Enciclopèdia, la wikipedia en valencià
Per a més informació sobre els cromosomes en biologia, vore cromosoma.

En l'àmbit dels algoritmes genètics (AG) i, de manera més general, en els algoritmes evolutius (AE), el terme “cromosoma” (també conegut com “genotip”) es referix a un conjunt de paràmetros que definixen una proposta de solució al problema que l'algoritme evolutiu intenta resoldre. Este conjunt de solucions, seguint el model biològic, es denomina “població”.[1][2]

El genoma d'un individu està compost per un o, en casos menys freqüents, varis cromosomes.[3][4] Este genoma representa la codificació genètica de la tasca a resoldre. Un cromosoma està constituït per un conjunt de gens, a on cada gen consistix en un o més paràmetros semánticamente conectats, comunament denominats “variables de decisió”. Estos gens determinen o influïxen en una o més característiques fenotípicas de l'individu.[2]


En la forma bàsica dels algoritmes genètics, els cromosomes es representen com cadenes binarias.[5] No obstant, en variants posteriors[6][7] i en els algoritmes evolutius en general, s'ampra una àmplia varietat de atres estructures de senyes per a representar els cromosomes.[8][9][10]

Disseny cromosòmic

[editar | editar còdic]

En dissenyar la representació genètica d'una tasca, és fonamental determinar qué variables de decisió i atres graus de llibertat deuen ser optimisats per l'Algoritme Evolutiu (AE) i possibles heurístics adicionals. Ademés, és crucial definir cóm deu realisar-se el mapage entre el genotip i el fenotip. El disseny d'un cromosoma traduïx estes consideracions en estructures de senyes concretes, per a les quals es deu seleccionar, configurar, ampliar o, en el pijor dels casos, crear un AE específic.

Trobar una representació adequada del domini del problema per a un cromosoma és una consideració essencial, ya que una bona representació facilita la busca en llimitar l'espai de busca. Pel contrari, una representació inadequada pot ampliar innecessàriament l'espai de busca.[11] En este context, també és necessari definir o redissenyar operadors de mutació i recombinació que s'ajusten al disseny del cromosoma elegit.[2] Un requisit important per a estos operadors és que no solament permeten alcançar, en principi, tots els punts de l'espai de busca, sino que també faciliten esta tasca al màxim.[12][13]

Un cromosoma ben adaptat deu complir els següents requisits:

  • Deu permetre l'accessibilitat a tots els punts admissibles en l'espai de busca.
  • El disseny del cromosoma deu cobrir únicament l'espai de busca rellevant, evitant zones adicionals innecessàries.
  • Deu minimisar la redundància en la mida de lo possible.
  • Menuts canvis en el cromosoma deuen provocar solament menuts canvis en el fenotip,[14] lo que també es coneix com a localitat de la relació entre l'espai de busca i l'espai del problema.
  • El disseny del cromosoma deu excloure per complet, o en la major mida possible, les regions prohibides en l'espai de busca.

Encara que el primer requisit és indispensable, depenent de l'aplicació i de el AE utilisat, generalment es deu aspirar a complir el restant dels requisits en la major mida possible. No obstant, és important tindre en conte que la busca evolutiva es veu recolzada i possiblement accelerada considerablement per un compliment lo més complet possible d'estos requisits.

Eixemples de cromosomes

[editar | editar còdic]

Cromosomes per a codificació binarias

[editar | editar còdic]

En la seua forma clàssica, els Algoritmes Genètics (AG) utilisen cadenes de bits per a representar les variables de decisió que es desigen optimisar. A continuació, es presenta un eixemple en una variable booleana i tres variables sanceres en els següents rancs de valors 0≤D1≤60,28≤D2≤30 i −12≤D3≤14 que pot ilustrar açò:

Eixemple de representació de quatre variables de decisió en una cadena de bits
variable de decisió: D1=22 D2=29 D3=−4 D4=0
bits: 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 0 0
posició: 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Tinga en conte que ací el número negatiu es dona en complement a dos. Esta representació directa utilisa cinc bits per a representar els tres valors de D2, encara que bastaria en dos bits. Es tracta d'una redundància important. Una alternativa millorada, en la que s'afigga 28 per a la correspondència genotip-fenotip, podria ser la següent:

Eixemple de representació millorada de les quatre variables de decisió
variable de decisió: D1=22 D'2=1 D3=−4 D4=0
bits: 0 1 0 1 1 0 0 1 1 1 1 0 0 0
posició: 14 13 12 11 10 9 8 7 6 5 4 3 2 1

a on D2=28+D'2=29

Cromosomes en gens de valor real o sancer

[editar | editar còdic]

Per al processament de tasques que involucren variables de decisió en valors reals o sancers mixts, es recomana l'us d'Algoritmes Evolutius (EA) com l'estratègia evolutiva,[15] o Algoritmes Genètics (AG) de codificació real.[16][17][18] En el cas de variables en valors sancers mixts, a sovint es recorre al grosseig, encara que açò pot violar el requisit de no redundància. Si les precisió necessàries dels valors reals poden reduir-se de manera raonable, esta violació pot ser mitigada utilisant AG codificats per sancers.[19][20]

Per a conseguir açò, els dígits significatius dels valors reals es convertixen en sancers per mig de la multiplicació per un factor adequat. Per eixemple, el valor 12,380 es convertix en l'número entero 12380 en multiplicar-ho per 1000. És important tindre en conte este factor en el mapage genotip-fenotip per a l'evaluació i presentació de resultats. Una forma comuna de representar açò és per mig d'un cromosoma compost per una llista o matriu de valors sancers o reals.

Cromosomes per a permutació

[editar | editar còdic]

Els problemes combinatoris se centren principalment en l'identificació d'una seqüència òptima dins d'un conjunt d'elements bàsics. Un eixemple clàssic d'este tipo de problema és el del viajante de comerç, qui deu visitar un número determinat de ciutats exactament una volta, seguint la ruta més curta possible.

La forma més senzilla i directa d'assignar esta tasca a un cromosoma consistix en numerar les ciutats de manera consecutiva, interpretar la seqüència resultant com una permutació i almagasenar-la directament en un cromosoma. En este context, cada gen del cromosoma correspon al número ordinal d'una ciutat específica.[13]


És important destacar que els operadors de variació en este model solament poden alterar l'orde dels gens, sense eliminar ni duplicar cap d'ells.[21] D'esta manera, el cromosoma representa la ruta d'un possible recorregut per les ciutats. Per eixemple, considerem la seqüència3,5,7,1,4,2,9,6,8 per a un conjunt de nou ciutats. Esta seqüència es traduïx en el següent cromosoma:

3 5 7 1 4 2 9 6 8

Ademés d'esta codificació, freqüentment denominada representació del camí, existixen atres formes de representar una permutació, com la representació ordinal o la representació matricial.[21][22]

Cromosomes per a la coevolución

[editar | editar còdic]

La coevolución es referix a un procés en el qual una representació genètica inclou, ademés de les variables de decisió, informació adicional que influïx tant en l'evolució com en el mapage del genotip al fenotip. Esta informació adicional també està subjecta a evolució. Un eixemple clàssic d'este fenomen és l'Estratègia Evolutiva (ES), que incorpora un o més tamanys de pas de mutació com a paràmetros estratègics en cada cromosoma.[15]

Un atre eixemple de coevolución és l'inclusió d'un gen adicional que regula una heurística de selecció per a l'assignació de recursos en una tasca de programació.[23] Este enfocament es fonamenta en la premissa de que les solucions òptimes depenen d'una selecció adequada dels paràmetros estratègics o de gens de control que influïxen en el mapage genotip-fenotip. L'èxit observat en l'aplicació de les Estratègies Evolutives (ES) respala esta hipòtesis.

Cromosomes per a representacions complexes

[editar | editar còdic]

Els cromosomes descrits anteriorment són altament adequats per a abordar tasques d'optimisació contínua, mixta sancera, sancera pura o combinatoria. No obstant, quan es tracta d'una combinació d'estes àrees d'optimisació, es torna cada volta més complex mapearlas a simples cadenes de valors, depenent de la tasca específica. Per a abordar esta complexitat, l'Algoritme Evolutiu d'Aprenentage General (GLEAM, per les seues sigles en anglés) propon una extensió del concepte de gen.[24]


En este context, un gen es definix com la descripció d'un element o traça elemental del fenotip, el qual pot tindre múltiples paràmetros. Per a això, s'establixen tipos de gens que contenen tants paràmetros del tipo de senyes apropiat com siguen necessaris per a descriure l'element concret del fenotip. Un cromosoma, per lo tant, es compon de gens que actuen com a objectes de senyes dels tipos de gens definits. Depenent de l'aplicació, cada tipo de gen pot aparéixer exactament una volta com a gen o pot estar contingut en el cromosoma en múltiples ocasions. Esta flexibilitat dona lloc a cromosomes de llongitut dinàmica, necessaris per a resoldre certs problemes.[25][26]

Les definicions dels tipos de gens també inclouen informació sobre els rancs de valors permesos per als paràmetros dels gens. Estos rancs es respecten tant durant la generació del cromosoma com durant les mutacions corresponents, evitant aixina mutacions letals. Per a les tasques que inclouen una part combinatòria, existixen operadors genètics adequats que poden moure o reposicionar els gens en la seua totalitat, és dir, junt en els seus paràmetros.

Erro al crear miniatura:
Tres gens eixemplars que coincidixen en les definicions de tipo de gen adjacent en un cromosoma organisat com una llista.
Erro al crear miniatura:
Tres gens eixemplars que coincidixen en les definicions de tipo de gen adjacent en un cromosoma organisat com una llista.

Com a eixemple, considerem una tasca de programació en la que deuen dissenyar-se fluix de treball que requerixen distints números de recursos heterogéneus. Un fluix de treball especifica qué passos poden processar-se en paralel i quins deuen eixecutar-se secuencialmente. En este context, els recursos heterogéneus impliquen temps de processament diferents, costs variats i capacitats de processament distintes.[23] Per lo tant, cada operació de programació requerix un o més paràmetros que determinen la selecció de recursos, a on els rancs de valors dels paràmetros depenen del número de recursos alternatius disponibles per a cada pas de treball.

Un cromosoma adequat proporciona un tipo de gen per cada pas de treball i, en este cas, un gen corresponent que té un paràmetro per a cada recurs requerit. L'orde dels gens determina l'orde de les operacions de programació i, per tant, la precedència en cas de conflictes d'assignació. Per eixemple, la definició del tipo de gen per al pas de treball 15, que requerix dos recursos en quatre i sèt alternatives respectivament, es voria com es mostra en l'image de l'esquerra. Ya que els paràmetros representen índexs en llistes de recursos disponibles per al respectiu pas de treball, el seu ranc de valors comença en 0. L'image de la dreta mostra un eixemple de tres gens d'un cromosoma pertanyents als tipos de gens en representació de llista.

Erro al crear miniatura:
Arbre sintàctic d'una fòrmula d'eixemple

Cromosomes per a representacions en arbre

[editar | editar còdic]

Les representacions en forma d'arbre d'un cromosoma són amprades en la programació genètica, una branca dels algoritmes evolutius (EA), per a la generació de programes o circuits informàtics. Estos arbres corresponen als arbres sintàctics generats per un compilador, els quals actuen com una representació interna durant el procés de traducció d'un programa informàtic.

En la figura adjacent es presenta, a modo d'eixemple, l'arbre sintàctic d'una expressió matemàtica. Els operadors de mutació tenen la capacitat de reordenar, modificar o eliminar subárboles, basant-se en l'estructura sintàctica representada. La recombinació, per la seua banda, es porta a terme per mig de l'intercanvi de subárboles adequats, permetent aixina la combinació de diferents parts dels arbres per a generar noves solucions.

Bibliografia

[editar | editar còdic]
  • Thomas Bäck (1996): Algoritmes Evolutius en Teoria i Pràctica: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press. ISBN 978-0-19-509971-3.
  • Wolfgang Banzhaf, P. Nordin, R. Keller, F. Francone (1998): Genetic Programming - An Introduction. Morgan Kaufmann, Sant Francisco. ISBN 1-55860-510-X.
  • Kenneth A. de Jong (2006): Evolutionary Computation: A Unified Approach. MIT Press, Cambridge, MA. ISBN 0-262-04194-4.
  • Melanie Mitchell (1996): An Introduction to Genetic Algorithms (Introducció als algoritmes genètics). MIT Press, Cambridge, MA. ISBN 978-0-262-63185-3.
  • Hans-Paul Schwefel (1995): Evolution and Optimum Seeking. Wiley & Sons, Nova York. ISBN 0-471-57148-2.

Referències

[editar | editar còdic]
  1. ↑ «Genetic Algorithm Description - Introduction to Genetic Algorithms - Tutorial with Interactive Java Applets». www.obitko.com. Consultat el 2024-07-22.
  2. ↑ 2,0 2,1 2,2 Introduction to Evolutionary Computing (en en). doi:10.1007/978-3-662-44874-8.
  3. ↑ NAFIPS 2008 - 2008 Annual Meeting of the North American Fuzzy Information Processing Society.IEEE.doi:10.1109/nafips.2008.4531273.Consultat el 2024-07-22.
  4. ↑ 2010 3rd International Conference on Information Management, Innovation Management and Industrial Engineering.IEEE.doi:10.1109/iciii.2010.128.Consultat el 2024-07-22.
  5. ↑ «Adaptation in natural and artificial systems : an introductory analysis with applications to biology, control, and artificial intelligence | WorldCat.org» (en és). search.worldcat.org. Consultat el 2024-07-22.
  6. ↑ «Proceedings of the fourth international conference on Genetic algorithms». www.semanticscholar.org. Consultat el 2024-07-22.
  7. ↑ Statistics and Computing.4(2)
    65–85.ISSN 1573-1375.doi:10.1007/BF00175354.Consultat el 2024-07-22.
  8. ↑ Information and Software Technology.43(14)
    817–831.ISSN 0950-5849.doi:10.1016/S0950-5849(01)00188-4.Consultat el 2024-07-22.
  9. ↑ Consultat el 2024-07-22.
  10. ↑ «Genetic programming : on the programming of computers by means of natural selection | WorldCat.org» (en és). search.worldcat.org. Consultat el 2024-07-22.
  11. ↑ «Genetic algorithms». web.archive.org. Consultat el 2024-07-22.
  12. ↑ Representations for Genetic and Evolutionary Algorithms (en en). doi:10.1007/978-3-642-88094-0.
  13. ↑ 13,0 13,1 Introduction to Evolutionary Computing (en en). doi:10.1007/978-3-662-44874-8.
  14. ↑ Proceedings of the 12th annual conference on Genetic and evolutionary computation.Association for Computing Machinery.
    901–908.doi:10.1145/1830483.1830646.Consultat el 2024-07-22.
  15. ↑ 15,0 15,1 «Evolution and optimum seeking | WorldCat.org» (en és). search.worldcat.org. Consultat el 2024-07-22.
  16. ↑ Eshelman, Larry J.; Schaffer, J. David (1993-01-01). Real-Coded Genetic Algorithms and Interval-Schemata, Elsevier, pp. 187–202. doi:10.1016/b978-0-08-094832-4.50018-0.
  17. ↑ «Genetic Algorithms + Data Structures = Evolution Programs | WorldCat.org» (en és). search.worldcat.org. Consultat el 2024-07-22.
  18. ↑ Applied Mathematics and Computation.212(2)
    505–518.ISSN 0096-3003.doi:10.1016/j.amc.2009.02.044.Consultat el 2024-07-22.
  19. ↑ Information Computing and Applications.Springer.
    359–366.doi:10.1007/978-3-642-25255-6_46.Consultat el 2024-07-22.
  20. ↑ «Integer Encoding Genetic Algorithm for Optimizing Redundancy Allocation of Series-parallel Systems». www.semanticscholar.org. Consultat el 2024-07-22.
  21. ↑ 21,0 21,1 Artificial Intelligence Review.13(2)
    129–170.ISSN 1573-7462.doi:10.1023/A:1006529012972.Consultat el 2024-07-22.
  22. ↑ «Evolutionary computation. Vol. 1, Basic algorithms and operators | WorldCat.org» (en és). search.worldcat.org. Consultat el 2024-07-22.
  23. ↑ 23,0 23,1 Algorithms.6(2)
    245–277.ISSN 1999-4893.doi:10.3390/a6020245.Consultat el 2024-07-22.
  24. ↑ Consultat el 2024-07-22.
  25. ↑ International Journal of Automation and Computing.12(3)
    337–342.ISSN 1751-8520.doi:10.1007/s11633-014-0870-x.Consultat el 2024-07-22.
  26. ↑ Real-World Applications of Evolutionary Computing.Springer.
    330–341.doi:10.1007/3-540-45561-2_32.Consultat el 2024-07-22.


Obtingut de «https://www.lenciclopedia.org/w/index.php?title=Cromosoma_(computació_evolutiva)&oldid=821330»