Una función de aptitud es un tipo particular de función de pérdida que se utiliza para resumir mediante una cifra de mérito única, lo cerca que está una solución candidata dada de lograr los objetivos establecidos. Es un componente importante de los Algoritmo evolutivos (AE), como la programación genética, la estrategia evolutiva o el algoritmo genético. Es un proceso metaheurístico que reproduce los principios básicos de la evolución biológica como algoritmo para resolver problemas muy complejos de optimización o de planeamiento, al menos de forma aproximada. Para ello se generan muchas soluciones candidatas, que se evalúan mediante una función de aptitud para guiar el desarrollo evolutivo hacia el objetivo deseado. También se utilizan funciones de calidad similares en otras metaheurísticas, como en el caso de la optimización mediante el algoritmo de la colonia de hormigas o mediante la optimización por enjambre de partículas.
En el campo de los AE, cada solución candidata, también llamada individuo, 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 los n peores individuos y recombinar n nuevos individuos a partir de las mejores soluciones. Por lo tanto, a cada individuo se le debe asignar un número de calidad que indique cuánto se ha acercado a la especificación general, y esto se genera aplicando la función de aptitud a los resultados de la prueba o simulación obtenidos de esa solución candidata.
Existen dos clases principales de funciones de aptitud: una en la que la función de aptitud no cambia, como al optimizar una función fija o probar con un conjunto fijo de casos de prueba; y uno donde la función de aptitud es mutable, como en la diferenciación de nichos o al coevolucionar el conjunto de casos de prueba. Otra forma de ver las funciones de aptitud es en términos de un paisaje adaptativo, que muestra la aptitud de cada cromosoma posible. A continuación se parte del supuesto de que la aptitud se determina basándose en una evaluación que permanece inalterada 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, como en la selección por torneos o en 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 la optimización mediante algoritmos evolutivos (AE). Incorpora el principio darwiniano de la "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 mediante AE sería ciega y difícilmente distinguible del método de Montecarlo. Al establecer una función de aptitud, siempre se debe tener en cuenta que va más allá de simplemente describir el estado objetivo deseado. Más bien, la búsqueda evolutiva hacia el óptimo también debe recibir el mayor apoyo posible, si y en la medida en que esto no se realice ya mediante la función de aptitud. Si la función de aptitud está mal diseñada, el algoritmo convergerá en una solución inapropiada o tendrá dificultades para converger.
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 aptas producidas por un algoritmo evolutivo no son las deseadas. Los algoritmos genéticos interactivos abordan esta dificultad delegando la evaluación a agentes externos, normalmente humanos.
Eficiencia computacional La función de aptitud no solo debe estar estrechamente alineada con el objetivo del diseñador, sino también ser computacionalmente eficiente. La velocidad de ejecución es crucial, ya que un algoritmo evolutivo típico debe iterarse muchas veces para producir un resultado útil para un problema no trivial.
La aproximación de aptitud puede ser apropiada, especialmente en los siguientes casos:
El tiempo de cálculo de la aptitud de una sola solución es extremadamente alto. Falta un modelo preciso para el cálculo de la aptitud. La función de aptitud es incierta o contiene mucho ruido.
Alternativamente, o además de la aproximación de la aptitud, los cálculos de aptitud también pueden distribuirse a un sistema de ordenadores en paralelo para reducir los tiempos de ejecución. Dependiendo del modelo de población del AE utilizado, tanto el propio AE como los cálculos de aptitud de toda la descendencia de una generación pueden ejecutarse en paralelo.
Optimización multiobjetivo Las aplicaciones prácticas suelen tener como propósito optimizar múltiples objetivos, al menos parcialmente contradictorios. Para ello, se suelen utilizar dos enfoques fundamentalmente diferentes: la optimización de Pareto y la optimización basada en la aptitud calculada mediante sumas ponderadas.
Suma ponderada y funciones de penalización Al optimizar la función utilizando la suma ponderada, los valores individuales de los objetivos se normalizan primero para que puedan compararse. Esto puede hacerse con la ayuda de los costos o especificando valores objetivo y determinando el valor actual como el grado de cumplimiento. Los costos o grados de cumplimiento pueden compararse entre sí y, si es necesario, también pueden asignarse a una escala de aptitud uniforme. Sin pérdida de generalidad, se supone que la aptitud representa un valor a maximizar. A cada objetivo se le asigna un peso en forma de un valor porcentual para que la aptitud bruta general pueda calcularse como una suma ponderada:
Una violación de las restricciones puede incluirse en la aptitud determinada de esta manera en la forma funciones de penalización. Para este propósito, se puede definir una función para cada restricción que devuelve un valor entre y dependiendo 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 :
Este enfoque es simple y tiene la ventaja de poder combinar cualquier número de objetivos y restricciones. La desventaja es que diferentes objetivos pueden compensarse entre sí y que los pesos deben definirse antes de la optimización. Esto significa que las líneas de compromiso deben definirse antes de la optimización, razón por la cual la optimización con la suma ponderada también se denomina método a priori. Además, ciertas soluciones pueden no obtenerse.
Optimización de Pareto Una solución se denomina óptima de Pareto si la mejora de un objetivo solo es posible con el deterioro de al menos otro objetivo. El conjunto de todas las soluciones óptimas de Pareto, también llamado conjunto de Pareto, representa el conjunto de todos los compromisos óptimos entre los objetivos. La figura inferior derecha muestra un ejemplo del conjunto de Pareto de dos objetivos y que deben maximizarse. Los elementos del conjunto forman el frente de Pareto (línea verde). A partir de este conjunto, un responsable de la toma de decisiones debe seleccionar la solución de compromiso deseada. Las restricciones se incluyen en la optimización de Pareto, ya que las soluciones sin violaciones de restricciones son intrínsecamente mejores que aquellas con violaciones. Si dos soluciones que se comparan presentan violaciones de restricciones, la magnitud de dichas violaciones determina la solución óptima.
Se reconoció desde el principio que los AE con su conjunto de soluciones consideradas simultáneamente son muy adecuados para encontrar soluciones en una sola ejecución que cubran el frente de Pareto suficientemente bien. Por lo tanto, son muy adecuados como métodos a-posteriori para la optimización multiobjetivo, en la que la decisión final la toma un decisor humano después de la optimización y la determinación del frente de Pareto. Además del SPEA2, el NSGA-II y el NSGA-III 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 equivalentes en términos de los objetivos como 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. Si hay más de tres o cuatro objetivos, algunos deben combinarse utilizando la suma ponderada u otros métodos de agregación.
Comparación de ambos tipos de evaluación
Con la ayuda de la suma ponderada, se puede obtener el frente de Pareto total mediante una selección adecuada de pesos, siempre que sea convexa. 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 algoritmo evolutivo converja al óptimo. La dirección con la mayor ganancia de aptitud en el conjunto de soluciones se muestra mediante las flechas.
Sin embargo, en el caso de un frente no convexo, las secciones no convexas del frente 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 parcialmente utilizando una extensión de la suma ponderada, la suma ponderada en cascada.
Al comparar ambos enfoques de evaluación, el uso de la optimización de Pareto resulta ventajoso cuando se conoce poco sobre las posibles soluciones de una tarea y cuando el número de objetivos de optimización se puede reducir a tres, o 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 por determinar todo el frente de Pareto ya no se justifica. Esto también se aplica cuando no se desea o no es posible una decisión humana tras la optimización, como en los procesos de decisión automatizados.
Objetivos auxiliares
Además de los objetivos principales derivados de la tarea en sí, puede ser necesario incluir objetivos auxiliares en la evaluación para apoyar el logro de uno o más objetivos principales. Se utiliza un ejemplo de una tarea de programación a modo de ilustración. Los objetivos de optimización incluyen no solo un procesamiento rápido general de todos los pedidos, sino también el cumplimiento de un plazo máximo de finalización. Esto último es especialmente necesario para la programación de pedidos urgentes. El segundo objetivo no se logra con la programación inicial ejemplar, como se muestra en la figura adjunta. Una modificación posterior no cambia esto, pero programa el paso de trabajo d antes, lo cual es un paso intermedio necesario para un inicio más temprano del último paso de trabajo e del pedido. Sin embargo, mientras solo se evalúe el plazo máximo de finalización, la idoneidad de la programación modificada permanece inalterada, aunque representa un paso relevante hacia el objetivo de una finalización oportuna del pedido. Esto puede remediarse, por ejemplo, mediante una evaluación adicional del retraso de los pasos de trabajo. El nuevo objetivo es auxiliar, ya que se introdujo además de los objetivos de optimización propiamente dichos para facilitar su consecución. Una descripción más detallada de este enfoque y otro ejemplo se pueden encontrar en el libro de Wilfred Jakob Applying Evolutionary Algorithms Successfully: A Guide Gained from Real-world Applications.
Véase también Computación evolutiva Funciones de prueba para la optimización Función de pérdida
Enlaces externos Una buena introducción a la granulación adaptativa de aptitud difusa (AFFG) (PDF), Un enfoque prometedor para acelerar la tasa de convergencia de los algoritmos evolutivos. La cabaña cibernética de la Granulación de Aptitud Difusa Adaptativa (AFFG) Diseñada para acelerar la tasa de convergencia de los algoritmos evolutivos.