On the Pareto Compliance of the Averaged Hausdorff Distance as a Performance Indicator

Sobre el cumplimiento de Pareto de la distancia de Hausdorff promediada como indicador de rendimiento

^​La distancia de Hausdorff promediada ∆_p es una inframétrica, recientemente introducida en la optimización evolutiva multiobjetivo (EMO) como herramienta para medir la optimalidad de aproximaciones de tamaño finito al frente de Pareto asociado a un problema de optimización multiobjetivo (MOP). Este tipo de herramientas se denominan indicadores de rendimiento, y su calidad depende de los criterios útiles que proporcionan para evaluar la idoneidad de diferentes soluciones candidatas a un determinado MOP.

Presentamos aquí un estudio puramente teórico de la conformidad del indicador ∆_p con la noción de optimalidad de Pareto. Dado que ∆_p se define en términos de una versión modificada de otros indicadores bien conocidos, a saber, la distancia generacional GD_p, y la distancia generacional invertida IGD_p, se discuten en detalle los criterios específicos para el cumplimiento de Pareto de cada uno de ellos. Para ello, se revisan algunos conocimientos previamente disponibles sobre el comportamiento de estos indicadores, corrigiendo imprecisiones encontradas en la literatura, y se establecen nuevos y más generales resultados, incluyendo pruebas detalladas y ejemplos de situaciones ilustrativas.

INTRODUCCIÓN

Una tarea fundamental en la optimización evolutiva multiobjetivo (EMO) consiste en el cálculo explícito del conjunto de soluciones (conocido como el conjunto de Pareto) y sus imágenes (el frente de Pareto) correspondientes al problema de optimización simultánea de múltiples funciones objetivo, o problema de optimización multiobjetivo (MOP), para abreviar. Es un hecho importante (véase, por ejemplo, [7]) que todo MOP no trivial admite más de una solución, es decir, no existe un único punto que optimice simultáneamente todas las funciones objetivo. Una solución se llama óptima de Pareto si no hay ninguna función objetivo que pueda ser mejorada sin degradar el resto. Aunque el conjunto de Pareto P de un MOP, formado por el conjunto de todas las soluciones óptimas, resulta ser un subconjunto compacto de Rⁿ en situaciones comunes, generalmente no puede calcularse de forma puramente analítica, y el uso de algoritmos numéricos se hace imprescindible.

A menudo es deseable (e incluso necesario) aproximar P con un subconjunto A⊂ Rⁿ, llamado archivo, que se asemeje lo más posible a P y a sus propiedades. Se suele suponer que los archivos están formados por un número finito de puntos que se pueden encontrar numéricamente, y los algoritmos EMO son una herramienta importante empleada para lograr ese objetivo. Para medir su precisión, la distancia entre un archivo de resultados A y el conjunto de Pareto original P debe definirse en un sentido apropiado, pero pueden considerarse varias nociones de distancia no equivalentes, y sus valores no se alcanzan necesariamente de manera única. Esto significa que el conjunto de aproximaciones candidatas no suele ser único.

Una noción de distancia entre conjuntos fácilmente disponible que puede utilizarse en este entorno es la distancia de Hausdorff (véase, por ejemplo, [4]), pero debido a su definición, permite ambigüedades indeseables y castiga fuertemente las soluciones únicas.