Función de fitness

Función objetivo del algoritmo evolutivo

Una función de aptitud es un tipo particular de función objetivo que se utiliza para resumir, como una única cifra de mérito , lo cerca que está una solución de diseño determinada de lograr los objetivos establecidos. Las funciones de aptitud se utilizan en la arquitectura de software y en algoritmos evolutivos (EA) , como la programación genética y los algoritmos genéticos, para guiar las simulaciones hacia soluciones de diseño óptimas. ^[1]

Los programadores de software saben que no deben publicar código incorrecto, pero esa prioridad compite con muchas otras prioridades de los desarrolladores ocupados. Por eso deberían usar funciones de aptitud para mantener su software bajo control. ^[2]

En el campo de los EA, cada solución de diseño se representa comúnmente como una cadena de números (denominada cromosoma ). Después de cada ronda de prueba o simulación, la idea es eliminar las n peores soluciones de diseño y generar n nuevas a partir de las mejores soluciones de diseño. Por lo tanto, cada solución de diseño debe recibir una cifra de mérito, para indicar qué tan cerca estuvo de cumplir con la especificación general, y esto se genera aplicando la función de aptitud a los resultados de la prueba o simulación obtenidos a partir de esa solución. ^[3]

Existen dos clases principales de funciones de aptitud: una en la que la función de aptitud no cambia, como en la optimización de una función fija o la prueba con un conjunto fijo de casos de prueba; y otra en la que la función de aptitud es mutable, como en la diferenciación de nicho o la coevolución del conjunto de casos de prueba. ^{[4] [5]} Otra forma de ver las funciones de aptitud es en términos de un paisaje de aptitud , que muestra la aptitud para cada cromosoma posible. A continuación, se supone que la aptitud se determina en función de una evaluación que permanece sin cambios durante una ejecución de optimización.

Una función de aptitud no necesariamente tiene que poder calcular un valor absoluto, ya que a veces es suficiente comparar candidatos para seleccionar el mejor. Una indicación relativa de aptitud (el candidato a es mejor que b) es suficiente en algunos casos ^[6] , como la selección en torneos o la optimización de Pareto .

Requisitos de evaluación y función de aptitud

La calidad de la evaluación y el cálculo de una función de aptitud es fundamental para el éxito de una optimización EA. Implementa el principio de Darwin de "supervivencia del más apto". Sin mecanismos de selección basados ​​en la aptitud para la selección de pareja y la aceptación de la descendencia, la búsqueda EA sería ciega y difícilmente distinguible del método de Monte Carlo . Al establecer una función de aptitud, uno siempre debe ser consciente de que se trata de algo más que simplemente describir el estado objetivo deseado. Más bien, la búsqueda evolutiva en el camino hacia el óptimo también debe ser apoyada tanto como sea posible (ver también la sección sobre objetivos auxiliares), siempre y cuando esto no sea ya realizado por la función de aptitud por sí sola. Si la función de aptitud está mal diseñada, el algoritmo convergerá en una solución inadecuada o tendrá dificultades para converger en absoluto.

La definición de la función de aptitud no es sencilla en muchos casos y, a menudo, se realiza de forma iterativa si las soluciones más adecuadas producidas por un EA no son las deseadas. Los algoritmos genéticos interactivos abordan esta dificultad subcontratando la evaluación a agentes externos que, normalmente, son humanos.

Eficiencia computacional

La función de aptitud no solo debe estar estrechamente relacionada con el objetivo del diseñador, sino que también debe ser eficiente desde el punto de vista computacional. La velocidad de ejecución es muy importante, ya que un algoritmo genético típico debe repetirse muchas veces para producir un resultado utilizable para un problema no trivial.

La aproximación de aptitud ^{[7] [8]} puede ser apropiada, especialmente en los siguientes casos:

• El tiempo de cálculo de aptitud de una única solución es extremadamente alto
• Falta un modelo preciso para el cálculo de la aptitud
• La función de aptitud es incierta o ruidosa. ^[9]

Como alternativa o además de la aproximación de aptitud, los cálculos de aptitud también se pueden distribuir a un ordenador paralelo para reducir los tiempos de ejecución. Dependiendo del modelo de población del EA utilizado, tanto el EA en sí como los cálculos de aptitud de todos los descendientes de una generación se pueden ejecutar en paralelo. ^{[10] [11] [12]}

Optimización multiobjetivo

Las aplicaciones prácticas suelen tener como objetivo optimizar objetivos múltiples y al menos parcialmente conflictivos. Para ello se suelen utilizar dos enfoques fundamentalmente diferentes: la optimización de Pareto y la optimización basada en la aptitud calculada mediante la suma ponderada . ^[13]

Funciones de suma ponderada y penalización

En la optimización con suma ponderada, primero se normalizan los valores individuales de los objetivos para poder compararlos. Esto se puede hacer con la ayuda de los costes o especificando valores objetivo y determinando el valor actual como grado de cumplimiento. A continuación, los costes o grados de cumplimiento se pueden comparar entre sí y, si es necesario, también se pueden asignar a una escala de aptitud uniforme. Sin pérdida de generalidad , se supone que la aptitud representa un valor que se debe maximizar. A cada objetivo se le asigna un peso en forma de valor porcentual para que la aptitud bruta general se pueda calcular como una suma ponderada: ${\displaystyle O}$ ${\displaystyle o_{i}}$ ${\displaystyle w_{i}}$ ${\displaystyle f_{raw}}$

${\displaystyle f_{raw}=\sum _{i=1}^{O}{o_{i}\cdot w_{i}}\quad {\mathsf {with}}\quad \sum _{i=1}^{O}{w_{i}}=1}$

Una violación de las restricciones puede incluirse en la aptitud determinada de esta manera en forma de funciones de penalización . Para ello, se puede definir una función para cada restricción que devuelva un valor entre y en función del grado de violación, siendo el resultado si no hay violación. La aptitud bruta previamente determinada se multiplica por la(s) función(es) de penalización y el resultado es entonces la aptitud final : ^[14] ${\displaystyle R}$ ${\displaystyle r_{j}}$ ${\displaystyle pf_{j}(r_{j})}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle f_{final}}$

${\displaystyle f_{final}=f_{raw}\cdot \prod _{j=1}^{R}{pf_{j}(r_{j})}=\sum _{i=1}^{O}{(o_{i}\cdot w_{i})}\cdot \prod _{j=1}^{R}{pf_{j}(r_{j})}}$

Este enfoque es sencillo y tiene la ventaja de poder combinar cualquier número de objetivos y restricciones. La desventaja es que los diferentes objetivos pueden compensarse entre sí y que los pesos deben definirse antes de la optimización. ^[13] Además, es posible que no se obtengan determinadas soluciones, véase el apartado sobre la comparación de ambos tipos de optimización .

Optimización de Pareto

Una solución se denomina óptima en el sentido de Pareto si la mejora de un objetivo solo es posible con un deterioro de al menos otro objetivo. El conjunto de todas las soluciones óptimas en el sentido de Pareto, también llamado conjunto de Pareto, representa el conjunto de todos los compromisos óptimos entre los objetivos. La figura de abajo a la derecha muestra un ejemplo del conjunto de Pareto de dos objetivos que se deben maximizar. Los elementos del conjunto forman el frente de Pareto (línea verde). A partir de este conjunto, un tomador de decisiones humano debe seleccionar posteriormente la solución de compromiso deseada. ^[13] Las restricciones se incluyen en la optimización de Pareto en el sentido de que las soluciones sin violaciones de restricciones son per se mejores que aquellas con violaciones. Si dos soluciones que se van a comparar tienen cada una violaciones de restricciones, el grado respectivo de las violaciones es decisivo. ^[15] ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$

Se reconoció desde el principio que los EA con su conjunto de soluciones consideradas simultáneamente son muy adecuados para encontrar soluciones en una ejecución que cubran suficientemente bien el frente de Pareto. ^{[15] [16]} Además del SPEA2, ^[17] el NSGA-II ^[18] y el NSGA-III ^{[19] [20]} se han establecido como métodos estándar.

La ventaja de la optimización de Pareto es que, a diferencia de la suma ponderada, proporciona todas las alternativas que son equivalentes en términos de los objetivos como una solución global. La desventaja es que la visualización de las alternativas se vuelve problemática o incluso imposible a partir de cuatro objetivos. Además, el esfuerzo aumenta exponencialmente con el número de objetivos. ^[14] Si hay más de tres o cuatro objetivos, algunos deben combinarse utilizando la suma ponderada u otros métodos de agregación. ^[13]

Comparación de ambos tipos de evaluación

Relación entre el frente de Pareto y la suma ponderada. El conjunto de soluciones factibles está parcialmente acotado por el frente de Pareto (verde). ^[14] ${\displaystyle Z}$

Ejemplo de un frente de Pareto no convexo ^[14]

Con la ayuda de la suma ponderada, el frente de Pareto total se puede obtener mediante una elección adecuada de pesos, siempre que sea convexo . ^[21] Esto se ilustra en la imagen adyacente a la izquierda. El punto en el frente de Pareto verde se alcanza con los pesos y , siempre que el EA converja al óptimo. La dirección con la mayor ganancia de aptitud en el conjunto de soluciones se muestra con las flechas dibujadas. ${\displaystyle {\mathsf {P}}}$ ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle Z}$

Sin embargo, en el caso de un frente no convexo, las secciones frontales no convexas no son alcanzables mediante la suma ponderada. En la imagen adyacente a la derecha, esta es la sección entre los puntos y . Esto se puede remediar en cierta medida utilizando una extensión de la suma ponderada, la suma ponderada en cascada . ^[14] ${\displaystyle {\mathsf {A}}}$ ${\displaystyle {\mathsf {B}}}$

Comparando ambos enfoques de evaluación, el uso de la optimización de Pareto es ciertamente ventajoso cuando se sabe poco sobre las posibles soluciones de una tarea y cuando el número de objetivos de optimización se puede reducir a tres, como máximo cuatro. Sin embargo, en el caso de la optimización repetida de variaciones de una misma tarea, las líneas de compromiso deseadas suelen ser conocidas y el esfuerzo para determinar todo el frente de Pareto ya no está justificado. Esto también es cierto cuando no se desea o no es posible una decisión humana después de la optimización, como en los procesos de decisión automatizados. ^[14]

Objetivos auxiliares

Ejemplo de dos cronogramas de una orden que consta de los cinco pasos de trabajo a a e que deben cumplir con un plazo de finalización máximo ^[22]

Además de los objetivos primarios que resultan de la propia tarea, puede ser necesario incluir en la evaluación objetivos auxiliares para apoyar la consecución de uno o más objetivos primarios. A modo de ilustración, se utiliza un ejemplo de una tarea de programación. Los objetivos de optimización incluyen no sólo un procesamiento rápido general de todos los pedidos, sino también el cumplimiento de un plazo de finalización tardío. Esto último es especialmente necesario para la programación de pedidos urgentes. El segundo objetivo no se consigue con el cronograma inicial ejemplar, como se muestra en la figura adyacente. Una mutación posterior no cambia esto, sino que programa antes el paso de trabajo d , que es un paso intermedio necesario para un inicio más temprano del último paso de trabajo e del pedido. Sin embargo, mientras sólo se evalúe el plazo de finalización tardío, la adecuación del cronograma mutado permanece inalterada, aunque represente un paso relevante hacia el objetivo de una finalización oportuna del pedido. Esto se puede remediar, por ejemplo, mediante una evaluación adicional del retraso de los pasos de trabajo. El nuevo objetivo es un objetivo auxiliar, ya que se introdujo además de los objetivos de optimización reales para apoyar su consecución. Se puede encontrar una descripción más detallada de este enfoque y otro ejemplo en ^{[22] .}

Véase también

• Computación evolutiva
• Programación inferencial
• Funciones de prueba para optimización
• Función de pérdida

Enlaces externos

• Una buena introducción a la granulación de aptitud difusa adaptativa (AFFG) ( PDF ), un enfoque prometedor para acelerar la tasa de convergencia de los EA.
• La cibercabaña de granulación de aptitud difusa adaptativa (AFFG) que está diseñada para acelerar la tasa de convergencia de los EA.
• Funciones de aptitud en la robótica evolutiva: una encuesta y análisis (AFFG) ( PDF ), Una revisión de las funciones de aptitud utilizadas en la robótica evolutiva .
• Ford, Neal; Richards, Mark; Sadalage, Pramod; Dehghani, Zhamak. (2021) Arquitectura de software: las partes difíciles O'Reilly Media, Inc. ISBN  9781492086895 .

Referencias

1. Eiben, AE; Smith, JE (2015). "Función de evaluación (función de aptitud)". Introducción a la computación evolutiva. Serie de computación natural (2.ª ed.). Berlín, Heidelberg: Springer. p. 30. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.S2CID20912932  .​
2. Fundamentos de la arquitectura de software: un enfoque de ingeniería . O'Reilly Media. 2020. ISBN 978-1492043454.
3. Eiben, AE; Smith, JE (2015). "¿Qué es un algoritmo evolutivo?". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 25–48. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.S2CID20912932  .​
4. Popovici, Elena; Bucci, Anthony; Wiegand, R. Paul; De Jong, Edwin D. (2012), Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (eds.), "Principios coevolutivos", Handbook of Natural Computing , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 987–1033, doi :10.1007/978-3-540-92910-9_31, ISBN 978-3-540-92909-3, consultado el 8 de enero de 2023
5. Eiben, AE; Smith, JE (2015). "Sistemas coevolutivos". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 223–230. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.S2CID20912932  .​
6. Bäck, Thomas; Fogel, David; Michalewicz, Zbigniew, eds. (20 de noviembre de 2000). Computación evolutiva 2: algoritmos y operadores avanzados. Taylor & Francis. doi :10.1201/9781420034349. ISBN 978-0-7503-0665-2.
7. Jin, Y. (enero de 2005). "Un estudio exhaustivo de la aproximación de la aptitud en la computación evolutiva". Soft Computing . 9 (1): 3–12. doi :10.1007/s00500-003-0328-5. ISSN  1432-7643. S2CID  7626092.
8. Jin, Yaochu; Wang, Handing; Chugh, Tinkle; Miettinen, Kaisa (junio de 2019). "Optimización evolutiva basada en datos: descripción general y estudios de casos". IEEE Transactions on Evolutionary Computation . 23 (3): 442–458. doi :10.1109/TEVC.2018.2869001. hdl : 10871/34011 . ISSN  1089-778X. S2CID  55809527.
9. Eiben, AE; Smith, JE (2015). "Optimización de funciones no estacionarias y ruidosas". Introducción a la computación evolutiva. Serie de computación natural (2.ª ed.). Berlín, Heidelberg: Springer. págs. 185–194. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.S2CID20912932  .​
10. Sudholt, Dirk (2015), Kacprzyk, Janusz; Pedrycz, Witold (eds.), "Algoritmos evolutivos paralelos", Springer Handbook of Computational Intelligence , Berlín, Heidelberg: Springer, págs. 929–959, doi :10.1007/978-3-662-43505-2_46, ISBN 978-3-662-43504-5, consultado el 27 de febrero de 2023
11. Khalloof, Hatem; Mohammad, Mohammad; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit (2020-11-02). "Un marco genérico flexible y escalable para la paralelización jerárquica de metaheurísticas basadas en la población". Actas de la 12.ª Conferencia internacional sobre gestión de ecosistemas digitales . Evento virtual Emiratos Árabes Unidos: ACM. págs. 124–131. doi :10.1145/3415958.3433041. ISBN 978-1-4503-8115-4. Número de identificación del sujeto  227179748.
12. Jähne, Paul (2016). Mayr, Heinrich Christian; Pinzger, Martín (eds.). Descripción general del estado actual de la investigación sobre paralelización de algoritmos evolutivos en tarjetas gráficas (PDF) . Bonn: Gesellschaft für Informatik, RFA. ISBN 978-3-88579-653-4.OCLC 962381748  . {{cite book}}: |work=ignorado ( ayuda )
13. Miettinen, Kaisa (2008). "Introducción a la optimización multiobjetivo: enfoques no interactivos". En Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (eds.). Optimización multiobjetivo: enfoques interactivos y evolutivos. Apuntes de clase en informática. Vol. 5252. Berlín, Heidelberg: Springer. págs. 1–26. doi :10.1007/978-3-540-88908-3. ISBN 978-3-540-88907-6.S2CID15375227  .​
14. Jakob, Wilfried; Blume, Christian (21 de marzo de 2014). "Optimización de Pareto o suma ponderada en cascada: una comparación de conceptos". Algoritmos . 7 (1): 166–185. arXiv : 2203.02697 . doi : 10.3390/a7010166 . ISSN  1999-4893.
15. Deb, Kalyanmoy (2008). "Introducción a la optimización multiobjetivo evolutiva". En Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (eds.). Optimización multiobjetivo: enfoques interactivos y evolutivos. Apuntes de clase en informática. Vol. 5252. Berlín, Heidelberg: Springer. págs. 58–96. doi :10.1007/978-3-540-88908-3. ISBN 978-3-540-88907-6.S2CID15375227  .​
16. Fonseca, Carlos M.; Fleming, Peter J. (1995). "Una visión general de los algoritmos evolutivos en la optimización multiobjetivo". Computación evolutiva . 3 (1): 1–16. doi :10.1162/evco.1995.3.1.1. ISSN  1063-6560. S2CID  8530790.
17. Eckart, Zitzler; Marco, Laumanns; Lothar, Thiele (2001). "SPEA2: Mejorando el algoritmo evolutivo de Pareto de fuerza". Informe técnico, Nr. 103. Laboratorio de Ingeniería Informática y Redes (TIK) . ETH Zürich 2001. doi :10.3929/ethz-a-004284029. S2CID  16584254.
18. Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. (2002). "Un algoritmo genético multiobjetivo rápido y elitista: NSGA-II". IEEE Transactions on Evolutionary Computation . 6 (2): 182–197. doi :10.1109/4235.996017. S2CID  9914171.
19. Deb, Kalyanmoy; Jain, Himanshu (2014). "Un algoritmo de optimización evolutivo de múltiples objetivos que utiliza un enfoque de ordenamiento no dominado basado en puntos de referencia, parte I: resolución de problemas con restricciones de caja". IEEE Transactions on Evolutionary Computation . 18 (4): 577–601. doi :10.1109/TEVC.2013.2281535. ISSN  1089-778X. S2CID  206682597.
20. Jain, Himanshu; Deb, Kalyanmoy (2014). "Un algoritmo de optimización evolutivo de múltiples objetivos que utiliza un enfoque de ordenamiento no dominado basado en puntos de referencia, parte II: manejo de restricciones y extensión a un enfoque adaptativo". IEEE Transactions on Evolutionary Computation . 18 (4): 602–622. doi :10.1109/TEVC.2013.2281534. ISSN  1089-778X. S2CID  16426862.
21. Miettinen, Kaisa (1998). Optimización multiobjetivo no lineal. Serie internacional en investigación de operaciones y ciencia de la gestión. Vol. 12. Boston, MA: Springer US. doi :10.1007/978-1-4615-5563-6. ISBN 978-1-4613-7544-9.
22. Jakob, Wilfried (2021), Aplicación exitosa de algoritmos evolutivos: una guía obtenida de aplicaciones del mundo real (KIT Scientific Working Papers, vol. 170), Karlsruhe, Alemania: Instituto Tecnológico de Karlsruhe (KIT), arXiv : 2107.11300 , doi : 10.5445/ir/1000135763, S2CID  236318422