Funció d'aptitud (algorisme genètic)
Una funció de d'aptitud (fitness en anglès) és un tipus particular d'objectiu o funció de cost que s'utilitza per resumir, com una única xifra de mèrit, com de prop està una solució candidata determinada d'assolir els objectius establerts. És un component important dels algoritmes evolutius (EA), com ara la programació genètica, les estratègies d'evolució o els algoritmes genètics. Un EA és una metaheurística que reprodueix els principis bàsics de l'evolució biològica com un algoritme informàtic per tal de resoldre tasques d'optimització o planificació desafiadores, almenys aproximadament. Per a aquest propòsit, es generen moltes solucions candidates, que s'avaluen mitjançant una funció d'aptitud per tal de guiar el desenvolupament evolutiu cap a l'objectiu desitjat.[1] Funcions de qualitat similars també s'utilitzen en altres metaheurístiques, com ara l'optimització de colònies de formigues o l'optimització d'eixams de partícules.
En el camp dels EA, cada solució candidata, també anomenada individu, es representa habitualment com una cadena de nombres (anomenada cromosoma). Després de cada ronda de proves o simulacions, la idea és eliminar els n pitjors individus i generar-ne n de nous a partir de les millors solucions. Per tant, a cada individu se li ha d'assignar un número de qualitat que indiqui com de prop s'ha acostat a l'especificació general, i això es genera aplicant la funció d'aptitud als resultats de la prova o simulació obtinguts d'aquesta solució candidata.[2]
Existeixen dues classes principals de funcions d'aptitud: una on la funció d'aptitud no canvia, com en l'optimització d'una funció fixa o les proves amb un conjunt fix de casos de prova; i una on la funció d'aptitud és mutable, com en la diferenciació de nínxols o la coevolució del conjunt de casos de prova.[3][4] Una altra manera de veure les funcions d'aptitud és en termes d'un paisatge d'aptitud, que mostra l'aptitud per a cada possible cromosoma. A continuació, se suposa que l'aptitud es determina a partir d'una avaluació que roman sense canvis durant una execució d'optimització.
Una funció de d'aptitud ideal es relaciona de prop amb l'objectiu de l'algorisme, i tanmateix es pot computar de pressa. La velocitat d'execució és molt important, ja que algorisme genètic típic ha de ser iterat moltíssimes vegades per a produir un resultat útil per a un problema no trivial.
La definició de la funció d'adequació no és directa en gaires casos i sovint es realitza iterativament si les solucions més aptes produïdes per l'algorisme no són el que es desitja. En alguns casos, és molt difícil o impossible de proposar fins i tot una suposició de quina definició de funció d'adequació podria ser l'adequada. Els algorismes genètics interactius tracten aquesta dificultat amb avaluació de subcontractació a agents externs (normalment humans).
Referències
[modifica]- ↑ Eiben, A.E.. «Evaluation Function (Fitness Function)». A: Introduction to Evolutionary Computing (en anglès). 2nd. Berlin, Heidelberg: Springer, 2015, p. 30 (Natural Computing Series). DOI 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.
- ↑ Eiben, A.E.. «What Is an Evolutionary Algorithm?». A: Introduction to Evolutionary Computing. Berlin, Heidelberg: Springer, 2015, p. 25–48 (Natural Computing Series). DOI 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.
- ↑ , ISBN 978-3-540-92909-3, doi:10.1007/978-3-540-92910-9_31, <http://link.springer.com/10.1007/978-3-540-92910-9_31>. Consulta: 8 gener 2023
- ↑ Eiben, A.E.. «Coevolutionary Systems». A: Introduction to Evolutionary Computing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015, p. 223–230 (Natural Computing Series). DOI 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.