Anar al contingut

Funció d'aptitut

De L'Enciclopèdia, la wikipedia en valencià

Una funció d'aptitut és un tipo particular de funció de pèrdua que s'utilisa per a resumir per mig d'una sifra de mèrit única, lo prop que està una solució candidata donada de conseguir els objectius establits. És un component important dels Algoritme evolutius (AE), com la programació genètica, l'estratègia evolutiva o l'algoritme genètic. És un procés metaheurístico que reproduïx els principis bàsics de l'evolució biològica com algoritme per a resoldre problemes molt complexos d'optimisació o de planejament, a lo manco de forma aproximada. Per a això es generen moltes soluciones candidates, que s'evaluen per mig d'una funció d'aptitut per a guiar el desenroll evolutiu cap a l'objectiu desijat.[1] També s'utilisen funcions de calitat similars en atres metaheurísticas, com en el cas de l'optimisació per mig del algoritme de la colónia de formigues o per mig de l'optimisació per eixam de partícules.

En el camp dels AE, cada solució candidata, també cridada individu, es representa comunament com una cadena de números (denominada cromosoma). Despuix de cada ronda de prova o simulació, l'idea és eliminar els n pijors individus i recombinar n nous individus a partir de les millors solucions. Per lo tant, a cada individu se li deu assignar un número de calitat que indique quànt s'ha acostat a l'especificació general, i açò es genera aplicant la funció d'aptitut als resultats de la prova o simulació obtinguts d'eixa solució candidata.[2]

Existixen dos classes principals de funcions d'aptitut: una en la que la funció d'aptitut no canvia, com en optimisar una funció fixa o provar en un conjunt fix de casos de prova; i un a on la funció d'aptitut és mutable, com en la diferenciació de casetes o al coevolucionar el conjunt de casos de prova.[3][4] Una atra forma de vore les funcions d'aptitut és en térmens d'un paisage adaptatiu, que mostra l'aptitut de cada cromosoma possible. A continuació es partix del supòsit de que l'aptitut es determina basant-se en una evaluació que permaneix inalterada durant una eixecució d'optimisació.


Una funció d'aptitut no necessàriament té que poder calcular un valor absolut, ya que a voltes és suficient comparar candidats per a seleccionar el millor. Una indicació relativa d'aptitut (el candidat a és millor que b) és suficient en alguns casos,[5] com en la selecció per tornejos o en l'optimisació de Pareto.

Requisits d'evaluació i funció d'aptitut

La calitat de l'evaluació i el càlcul d'una funció d'aptitut és fonamental per a l'èxit de l'optimisació per mig d'algoritmes evolutius (AE). Incorpora el principi darwiniano de la "supervivència del més apte". Sense mecanismes de selecció basats en l'aptitut per a la selecció de parella i l'acceptació de la descendència, la busca per mig de AE seria cega i difícilment distinguible del método de Montecarlo. En establir una funció d'aptitut, sempre es deu tindre en conte que va més allà de simplement descriure l'estat objectiu desijat. Més be, la busca evolutiva cap a l'òptim també deu rebre el major respal possible, si i en la mida en que açò no es realise ya per mig de la funció d'aptitut. Si la funció d'aptitut està mal dissenyada, l'algoritme convergirà en una solució inapropiada o tindrà dificultats per a convergir.

La definició de la funció d'aptitut no és senzilla en molts casos i a sovint es realisa de forma iterativa si les solucions més aptes produïdes per un algoritme evolutiu no són les desijades. Els algoritmes genètics interactius aborden esta dificultat delegant l'evaluació a agents externs, normalment humans.

Eficiència computacional

La funció d'aptitut no solament deu estar estretament alineada en l'objectiu del dissenyador, sino també ser computacionalment eficient. La velocitat d'eixecució és crucial, ya que un algoritme evolutiu típic deu iterarse moltes voltes per a produir un resultat útil per a un problema no trivial.

l'aproximació d'aptitut[6][7] pot ser apropiada, especialment en els següents casos:

  • El temps de càlcul de l'aptitut d'una sola solució és extremadament alt. Falta un model precís per al càlcul de l'aptitut.
  • La funció d'aptitut és incerta o conté molt soroll.[8]


Alternativament, o ademés de l'aproximació de l'aptitut, els càlculs d'aptitut també poden distribuir-se a un sistema d'ordenadors en paralel per a reduir els temps d'eixecució. Depenent del model de població de el AE utilisat, tant el propi AE com els càlculs d'aptitut de tota la descendència d'una generació poden eixecutar-se en paralel.[9][10][11]

Vore també

Referències

  1. ↑ (2015) «Evaluation Function (Fitness Function)», Introduction to Evolutionary Computing, 2nd edició (en en), Berlin, Heidelberg: Springer, pp. 30. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.
  2. ↑ (2015) «What Is an Evolutionary Algorithm?», Introduction to Evolutionary Computing, Berlin, Heidelberg: Springer, pp. 25–48. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.
  3. ↑ «Handbook of Natural Computing».Springer.
    987–1033.doi:10.1007/978-3-540-92910-9_31.Consultat el 8 de giner de 2023.
  4. ↑ (2015) «Coevolutionary Systems», Introduction to Evolutionary Computing, Berlin, Heidelberg: Springer, pp. 223–230. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.
  5. ↑ (20 de novembre de 2000) Evolutionary Computation 2: Advanced Algorithms and Operators (en en), Taylor & Francis. doi:10.1201/9781420034349. ISBN 978-0-7503-0665-2.
  6. ↑ Jin, Y.. “A comprehensive survey of fitness approximation in evolutionary computation” (en). Soft Computing 9 (1): 3–12. doi:10.1007/s00500-003-0328-5. ISSN 1432-7643.
  7. ↑ “Data-Driven Evolutionary Optimization: An Overview and Case Studies” . IEEE Transactions on Evolutionary Computation 23 (3): 442–458. doi:10.1109/TEVC.2018.2869001. ISSN 1089-778X. Bibcode: 2019ITEC...23..442J.
  8. ↑ (2015) «Nonstationary and Noisy Function Optimisation», Introduction to Evolutionary Computing, 2nd edició, Berlin, Heidelberg: Springer, pp. 185–194. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.
  9. ↑ «Springer Handbook of Computational Intelligence».Springer.
    929–959.doi:10.1007/978-3-662-43505-2_46.Consultat el 27 de febrer de 2023.
  10. ↑ (2 de novembre de 2020) «A Generic Flexible and Scalable Framework for Hierarchical Parallelization of Population-Based Metaheuristics», Proceedings of the 12th International Conference on Management of Digital EcoSystems (en en), Virtual Event United Arab Emirates: ACM, pp. 124–131. doi:10.1145/3415958.3433041. ISBN 978-1-4503-8115-4.
  11. ↑ Jähne, Paul (2016). Overview of the current state of research on parallelisation of evolutionary algorithms on graphic cards (en en), Bonn: Gesellschaft für Informatik, FRG. OCLC 962381748. ISBN 978-3-88579-653-4.


Referències


Obtingut de «https://lenciclopedia.org/w/index.php?title=Funció_d%27aptitut&oldid=827775»