Vés al contingut

Algorisme evolutiu

De la Viquipèdia, l'enciclopèdia lliure

En intel·ligència computacional (CI), un algorisme evolutiu (EA) és un subconjunt de la computació evolutiva,[1] un algorisme genèric d'optimització metaheurística basat en poblacions. Un EA utilitza mecanismes inspirats en l'evolució biològica, com ara la reproducció, la mutació, la recombinació i la selecció. Les solucions candidates al problema d'optimització juguen el paper dels individus d'una població, i la funció d'aptitud determina la qualitat de les solucions (vegeu també la funció de pèrdua). L'evolució de la població té lloc després de l'aplicació repetida dels operadors anteriors.

Els algorismes evolutius sovint funcionen bé aproximant solucions a tot tipus de problemes perquè idealment no fan cap suposició sobre el panorama de fitness subjacent. Les tècniques d'algorismes evolutius aplicats a la modelització de l'evolució biològica es limiten generalment a exploracions de processos microevolutius i models de planificació basats en processos cel·lulars. En la majoria de les aplicacions reals dels EA, la complexitat computacional és un factor prohibitiu.[2] De fet, aquesta complexitat computacional es deu a l'avaluació de la funció de fitness. L'aproximació de la forma física és una de les solucions per superar aquesta dificultat. Tanmateix, un EA aparentment simple pot resoldre problemes sovint complexos; [3][4][5] per tant, pot ser que no hi hagi cap enllaç directe entre la complexitat de l'algorisme i la complexitat del problema.

Implementació

[modifica]

El següent és un exemple d'algorisme genèric d'un sol objectiu.

Primer pas: generar la població inicial d'individus aleatòriament. (Primera generació)

Segon pas: repetiu els passos de regeneració següents fins a la finalització:

  1. Avaluar la condició física de cada individu de la població (límit de temps, condició física suficient aconseguida, etc.)
  2. Seleccioneu els individus més aptes per a la reproducció. (Pares)
  3. Cria nous individus mitjançant operacions d'encreuament i mutació per donar a llum descendència.
  4. Substituir els individus menys aptes de la població per individus nous.

Tipus

[modifica]

Tècniques similars difereixen en la representació genètica i altres detalls d'implementació, i la naturalesa del problema aplicat particular.

  • Algorisme genètic: aquest és el tipus d'EA més popular. Es busca la solució d'un problema en forma de cadenes de nombres (tradicionalment binaris, encara que les millors representacions solen ser aquelles que reflecteixen alguna cosa sobre el problema que es resol), aplicant operadors com la recombinació i la mutació (de vegades un, de vegades ambdues). Aquest tipus d'EA s'utilitza sovint en problemes d'optimització.
  • Programació genètica: aquí les solucions són en forma de programes informàtics, i la seva aptitud està determinada per la seva capacitat per resoldre un problema computacional. Hi ha moltes variants de la programació genètica, inclosa la programació genètica cartesiana, la programació d'expressió gènica, l'evolució gramatical, la programació genètica lineal, la programació de múltiples expressions, etc.
  • Programació evolutiva: semblant a la programació genètica, però l'estructura del programa és fixa i els seus paràmetres numèrics poden evolucionar.
  • Estratègia d'evolució: funciona amb vectors de nombres reals com a representacions de solucions, i normalment utilitza taxes de mutació autoadaptatives. El mètode s'utilitza principalment per a l'optimització numèrica, encara que també hi ha variants per a tasques combinatòries.
  • Evolució diferencial: es basa en diferències vectorials i, per tant, s'adapta principalment a problemes d'optimització numèrica.
  • Algorisme coevolucionari: semblant als algorismes genètics i les estratègies d'evolució, però les solucions creades es comparen en funció dels seus resultats de les interaccions amb altres solucions. Les solucions poden competir o cooperar durant el procés de cerca. Els algorismes coevolucionaris s'utilitzen sovint en escenaris on el panorama de fitness és dinàmic, complex o implica interaccions competitives.
  • Neuroevolució: semblant a la programació genètica, però els genomes representen xarxes neuronals artificials descrivint l'estructura i els pesos de connexió. La codificació del genoma pot ser directa o indirecta.
  • Sistema de classificació d'aprenentatge: aquí la solució és un conjunt de classificadors (regles o condicions). Un Michigan-LCS evoluciona a nivell de classificadors individuals, mentre que un Pittsburgh-LCS utilitza poblacions de conjunts de classificadors. Inicialment, els classificadors només eren binaris, però ara inclouen tipus reals, de xarxa neuronal o d'expressió S. La condició física normalment es determina amb un aprenentatge de reforç basat en la força o la precisió o amb un enfocament d'aprenentatge supervisat.
  • Algorismes de qualitat i diversitat: els algorismes de QD tenen com a objectiu solucions diverses i d'alta qualitat. A diferència dels algorismes d'optimització tradicionals que només se centren a trobar la millor solució a un problema, els algorismes de QD exploren una gran varietat de solucions en un espai de problemes i mantenen aquelles que no només tenen un alt rendiment, sinó també diverses i úniques.

Aplicacions

[modifica]

Les àrees en què els algorismes evolutius s'utilitzen pràcticament són gairebé il·limitades [6] i van des de la indústria,[7][8] enginyeria,[9][10][11] programació complexa,[12][13][14] agricultura,[15] planificació del moviment del robot i finançament [16][17] per investigar.[18][19] L'aplicació d'un algorisme evolutiu requereix un replantejament per part de l'usuari sense experiència, ja que l'enfocament d'una tasca utilitzant un EA és diferent dels mètodes exactes convencionals i normalment no forma part del pla d'estudis dels enginyers o d'altres disciplines. Per exemple, el càlcul de la condició física no només ha de formular l'objectiu, sinó que també ha de donar suport al procés de cerca evolutiva cap a aquest, per exemple, premiant les millores que encara no condueixen a una millor avaluació dels criteris de qualitat originals. Per exemple, si s'ha d'evitar l'ús màxim de recursos com el desplegament de personal o el consum d'energia en una tasca de programació, no n'hi ha prou amb avaluar la màxima utilització. Més aviat, també s'hauria de registrar el nombre i la durada de les excedències d'un nivell encara acceptable per tal de recompensar les reduccions per sota del valor màxim real. Hi ha, per tant, algunes publicacions que estan adreçades al principiant i volen ajudar a evitar els errors del principiant així com a portar un projecte d'aplicació cap a l'èxit.[20][21] Això inclou aclarir la qüestió fonamental de quan s'ha d'utilitzar un EA per resoldre un problema i quan és millor no fer-ho.

Galeria

[modifica]

Referències

[modifica]
  1. ↑ Vikhar, P. A.. «Evolutionary algorithms: A critical review and its future prospects». A: 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC) (en anglès), 2016, p. 261–265. DOI 10.1109/ICGTSPICC.2016.7955308. ISBN 978-1-5090-0467-6. 
  2. ↑ Cohoon, J. Evolutionary algorithms for the physical design of VLSI circuits (en anglès). Springer, pp. 683-712, 2003, 2002-11-26. ISBN 978-3-540-43330-9. 
  3. ↑ Slowik, Adam; Kwasnicka, Halina (en anglès) Neural Computing and Applications, 32, 16, 2020, pàg. 12363–12379. DOI: 10.1007/s00521-020-04832-8. ISSN: 0941-0643 [Consulta: free].
  4. ↑ Mika, Marek; Waligóra, Grzegorz; Węglarz, Jan (en anglès) Journal of Scheduling, 14, 3, 2011, pàg. 291–306. DOI: 10.1007/s10951-009-0158-0. ISSN: 1094-6136.
  5. ↑ «International Conference on the Applications of Evolutionary Computation» (en anglès). The conference is part of the Evo* series. The conference proceedings are published by Springer. [Consulta: 23 desembre 2022].
  6. ↑ «International Conference on the Applications of Evolutionary Computation» (en anglès). The conference is part of the Evo* series. The conference proceedings are published by Springer. [Consulta: 23 desembre 2022].
  7. ↑ Sanchez, Ernesto. Industrial Applications of Evolutionary Algorithms (en anglès). 34. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012 (Intelligent Systems Reference Library). DOI 10.1007/978-3-642-27467-1. ISBN 978-3-642-27466-4. 
  8. ↑ Miettinen, Kaisa. Evolutionary algorithms in engineering and computer science : recent advances in genetic algorithms, evolution strategies, evolutionary programming, genetic programming, and industrial applications (en anglès). Chichester: Wiley and Sons, 1999. ISBN 0-585-29445-3. OCLC 45728460. 
  9. ↑ Cohoon, J. Evolutionary algorithms for the physical design of VLSI circuits (en anglès). Springer, pp. 683-712, 2003, 2002-11-26. ISBN 978-3-540-43330-9. 
  10. ↑ Slowik, Adam; Kwasnicka, Halina (en anglès) Neural Computing and Applications, 32, 16, 2020, pàg. 12363–12379. DOI: 10.1007/s00521-020-04832-8. ISSN: 0941-0643 [Consulta: free].
  11. ↑ Gen, Mitsuo. Genetic Algorithms and Engineering Optimization (en anglès). Hoboken, NJ, USA: John Wiley & Sons, Inc., 1999-12-17 (Wiley Series in Engineering Design and Automation). DOI 10.1002/9780470172261. ISBN 978-0-470-17226-1. 
  12. ↑ Mika, Marek; Waligóra, Grzegorz; Węglarz, Jan (en anglès) Journal of Scheduling, 14, 3, 2011, pàg. 291–306. DOI: 10.1007/s10951-009-0158-0. ISSN: 1094-6136.
  13. ↑ Dahal, Keshav P. Evolutionary scheduling (en anglès). Berlín: Springer, 2007. DOI 10.1007/978-3-540-48584-1. ISBN 978-3-540-48584-1. OCLC 184984689. 
  14. ↑ Jakob, Wilfried; Strack, Sylvia; Quinte, Alexander; Bengel, Günther; Stucky, Karl-Uwe (en anglès) Algorithms, 6, 2, 22-04-2013, pàg. 245–277. DOI: 10.3390/a6020245. ISSN: 1999-4893 [Consulta: free].
  15. ↑ Mayer, David G. Evolutionary Algorithms and Agricultural Systems (en anglès). Boston, MA: Springer US, 2002. DOI 10.1007/978-1-4615-1717-7. ISBN 978-1-4613-5693-6. 
  16. ↑ . DOI 10.1007/978-3-540-89378-3_52. ISBN 978-3-540-89377-6 [Consulta: 23 desembre 2022]. 
  17. ↑ Chen. Evolutionary Computation in Economics and Finance. 100. Heidelberg: Physica-Verlag HD, 2002 (Studies in Fuzziness and Soft Computing). DOI 10.1007/978-3-7908-1784-3. ISBN 978-3-7908-2512-1. 
  18. ↑ Lohn, J.D.. «Evolutionary design of an X-band antenna for NASA's Space Technology 5 mission». A: IEEE Antennas and Propagation Society Symposium, 2004 (en anglès). 3, juny 2004, p. 2313–2316 Vol.3. DOI 10.1109/APS.2004.1331834. ISBN 0-7803-8302-8. 
  19. ↑ Fogel, Gary. Evolutionary Computation in Bioinformatics (en anglès). Elsevier, 2003. DOI 10.1016/b978-1-55860-797-2.x5000-8. ISBN 978-1-55860-797-2. 
  20. ↑ Whitley, Darrell (en anglès) Information and Software Technology, 43, 14, 2001, pàg. 817–831. DOI: 10.1016/S0950-5849(01)00188-4.
  21. ↑ Eiben, A.E.. «Working with Evolutionary Algorithms». A: Introduction to Evolutionary Computing (en anglès). 2a edició. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015, p. 147–163 (Natural Computing Series). DOI 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. 
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Algorisme_evolutiu&oldid=34123105»