🤖 AI

A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures

Este artículo propone un enfoque novedoso para caracterizar problemas de optimización mediante el cálculo del volumen y la entropía de Halstead de sus implementaciones programáticas, demostrando que estas medidas de complejidad basadas en código sirven como meta-características predictivas efectivas y libres de muestreo para la selección de algoritmos.

Autores originales: Marcus Gallagher, Katherine M. Malan

Publicado 2026-08-11

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Marcus Gallagher, Katherine M. Malan

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás tratando de enseñarle a un robot a resolver un laberinto. A veces el laberinto es un pasillo simple y recto; otras veces es un laberinto sinuoso y giratorio con callejones sin salida y trampas. En el mundo de la informática, esto se llama optimización: encontrar la mejor solución posible para un problema. Pero aquí está lo complicado: no todos los laberintos son iguales. Algunos son fáciles de resolver para un robot, mientras que otros hacen que incluso los algoritmos más inteligentes se pierdan.

Para ayudar a los robots a elegir la estrategia adecuada, los científicos intentan "caracterizar" o describir estos laberintos antes de que el robot empiece a correr. Buscan pistas, como qué tan accidentado es el terreno o cuántos callejones sin salida existen. Por lo general, para encontrar estas pistas, el robot tiene que dar unos pocos pasos, mirar a su alrededor y medir el terreno. Esto es como enviar a un explorador a la oscuridad para mapear la cueva. Pero, ¿y si el robot pudiera simplemente mirar el plano del laberinto y adivinar qué tan difícil sería de resolver, sin siquiera poner un pie dentro? Esa es la gran pregunta que plantea este artículo. Sugiere que la forma en que un problema está escrito en código de computadora podría contener el secreto de qué tan difícil es de resolver, tal como la complejidad de una receta puede dar pistas sobre qué tan difícil será cocinar.

El código como bola de cristal

En este artículo, Marcus Gallagher y Katherine Malan proponen una forma fresca y ligeramente mágica de mirar estos problemas difíciles. En lugar de enviar a un explorador a medir el paisaje, sugieren que simplemente leamos la "receta" que la computadora utiliza para crear el problema.

Piensa en un problema de optimización como un nivel de un videojuego. Para construir el nivel, un programador escribe código. Algunos niveles son simples: "Avanzar, saltar sobre un foso, recoger la moneda". El código para esto es corto y utiliza comandos básicos. Otros niveles son caóticos: "Si el cielo es azul, multiplica tu velocidad por el número de estrellas, luego resta la raíz cuadrada de tu salud, pero solo si llevas puesto un sombrero". El código para esto es largo, desordenado y utiliza una enorme variedad de comandos.

La gran idea de los autores es esta: Cuanto más desordenado y complejo sea el código, más difícil será para un algoritmo resolver el problema.

Ellos toman dos herramientas del mundo de la ingeniería de software para medir este "desorden".

Volumen de Halstead: Imagina contar cada palabra y símbolo en un párrafo. Si tienes un cuento corto con palabras sencillas, el conteo es bajo. Si tienes una novela con un vocabulario complejo y frases largas, el conteo es alto. Esta medida cuenta los "operadores" (como símbolos matemáticos) y los "operandos" (como números y variables) en el código.
Entropía de Shannon: Esto es un poco como medir el factor de sorpresa. Si un párrafo utiliza las mismas cinco palabras una y otra vez, es predecible (entropía baja). Si utiliza una gran variedad de palabras únicas en un orden aleatorio, es impredecible (entropía alta).

El experimento: De círculos simples a picos caóticos

Para probar su teoría, los autores tomaron un conjunto famoso de 24 problemas de prueba utilizados por científicos de todo el mundo (conocido como la suite BBOB). Estos van desde la función "Sphere" (una colina perfectamente suave y redonda que es fácil de rodar hacia abajo) hasta la función "Lunacek bi-Rastrigin" (un paisaje dentado y rocoso con miles de diminutos picos y valles).

Escribieron el código de computadora para cada uno de estos 24 problemas y ejecutaron sus calculadoras de "desorden" en ellos. Los resultados fueron exactamente lo que esperaban:

La función Sphere, simple y suave, tuvo las puntuaciones de complejidad más bajas.
La función Lunacek, dentada y difícil, tuvo las puntuaciones de complejidad más altas.
De hecho, la función Lunacek era aproximadamente 9.3 veces más compleja en su estructura de código que la función Sphere.

Incluso probaron esto en un tipo diferente de problema: entrenar una red neuronal (un tipo de cerebro de IA). Descubrieron que el código para una red que utiliza una función de activación "Tanh" era ligeramente más complejo que uno que usa "ReLU", y esto coincidía con la idea de que la versión Tanh es un rompecabezas ligeramente más difícil de resolver.

La conexión mágica: La complejidad del código predice el rendimiento

La verdadera magia ocurre cuando comparan estas puntuaciones de código con qué tan bien funcionaron realmente los diferentes algoritmos. Observaron los datos de cinco algoritmos diferentes de tipo "robot" intentando resolver estos 24 problemas.

Encontraron un patrón claro: Cuanto más complejo es el código, peor es el rendimiento de los robots.

Es una relación negativa. Cuando el código era simple (bajo volumen de Halstead), los robots resolvían el problema de forma rápida y fácil. Cuando el código era complejo (alto volumen de Halstead), los robots tenían dificultades, tardaban más o se quedaban atascados. Por ejemplo, en problemas de 5 dimensiones, la conexión entre la complejidad del código y el mal rendimiento fue bastante fuerte.

Sin embargo, los autores tienen cuidado en señalar que esto no es una bola de cristal perfecta. Hubo algunos problemas "atípicos" donde el código era muy complejo, pero los robots no funcionaron tan mal como el código sugería. Esto sugiere que, si bien la complejidad del código es una gran pista, no es lo único que importa.

Por qué esto es importante

La belleza de este enfoque es que es increíblemente rápido y no requiere trabajo adicional. Los métodos tradicionales para entender un problema a menudo implican ejecutar el algoritmo miles de veces solo para ver cómo es el paisaje. Esto es como enviar a un explorador a caminar por todo el laberinto solo para dibujar un mapa.

En contraste, el método de los autores es como mirar el plano del laberinto. Puedes calcular la complejidad del código en una fracción de segundo, sin ejecutar el problema ni una sola vez. No le importa el tamaño del problema ni cuántas dimensiones tiene; simplemente observa la estructura de las instrucciones.

Los autores sugieren que esta nueva medida de "complejidad de código" podría ser una ayuda útil en el conjunto de herramientas de los científicos que diseñan algoritmos. No reemplaza las viejas formas de observar los problemas, sino que añade una nueva forma súper rápida de adivinar qué tan difícil será un problema antes de siquiera empezar a resolverlo. Es un paso prometedor para ayudar a las computadoras a elegir la herramienta adecuada para el trabajo, simplemente leyendo las instrucciones.

Resumen Técnico: Caracterización de Problemas de Optimización mediante la Representación Programática

Planteamiento del Problema
La caracterización de instancias de problemas de optimización es fundamental para comprender el comportamiento de los algoritmos, facilitar la selección de algoritmos y configurar optimizadores. Los enfoques existentes, como el Análisis de Paisaje Exploratorio (ELA, por sus siglas en inglés), dependen del muestreo del espacio de búsqueda para extraer características. Sin embargo, estos métodos enfrentan limitaciones prácticas: consumen costosas evaluaciones de la función objetivo, son sensibles al tamaño y la estrategia de la muestra, y pueden no proporcionar representaciones robustas de paisajes complejos. Además, diferentes conjuntos de características suelen proporcionar información complementaria en lugar de superpuesta, lo que sugiere la necesidad de enfoques de caracterización diversos.

Metodología
Los autores proponen un enfoque novedoso que caracteriza los problemas de optimización basándose en la representación programática de sus funciones objetivo, en lugar de muestrear el espacio de búsqueda. La intuición central es que la complejidad del código requerido para implementar una función objetivo se correlaciona con la complejidad del paisaje de búsqueda resultante. Las estructuras matemáticas simples producen código simple y paisajes suaves, mientras que las funciones complejas requieren un código más largo y con mayor densidad de operadores, manifestándose como paisajes irregulares.

El estudio utiliza dos medidas específicas de complejidad de programas derivadas de la ingeniería de software y la teoría de la información:

Volumen de Halstead ( $V_H$ ): Una medida del tamaño y la complejidad del programa definida como $V_H = (N_1 + N_2) \log_2(\eta_1 + \eta_2)$ , donde $N$ representa el número total de operadores/operandos y $\eta$ representa el número de operadores/operandos distintos.
Entropía de Shannon ( $H$ ): Una medida del contenido de información por token, escalada por el número total de tokens ( $N$ ). Los autores señalan que, bajo supuestos de probabilidad uniforme, $H$ aproxima a $V_H$ .

Estas métricas se calculan estáticamente a partir del código fuente (específicamente implementaciones en C) de las funciones objetivo. El estudio evalúa estas medidas en:

La suite de pruebas sin ruido BBOB (Black-Box Optimisation Benchmarking) (24 funciones).
Tareas de optimización de pesos de redes neuronales (entrenamiento de redes feed-forward con funciones de activación ReLU y Tanh).

Contribuciones Clave y Resultados

Caracterización Estática y Libre de Muestreo: El método propuesto no requiere muestreo del espacio de búsqueda ni evaluaciones de la función objetivo. Es invariante a las transformaciones (p. ej., rotación, condicionamiento) y a la dimensionalidad del problema (ya que la dimensionalidad se trata como un conteo de bucles o un operando único en la estructura del código).
Correlación con el Rendimiento de los Algoritmos: Al aplicarse a la suite BBOB, se encontró que el volumen de Halstead y la entropía tienen una correlación negativa con el rendimiento de los algoritmos (medido por el área bajo la curva normalizada de la función de distribución acumulativa empírica).
- Valores de complejidad más altos (p. ej., para $f_{24}$ , Lunacek bi-Rastrigin) correspondieron a un menor rendimiento de los algoritmos.
- Valores de complejidad más bajos (p. ej., para $f_1$ , Sphere) correspondieron a un mayor rendimiento.
- Los coeficientes de correlación de rango de Spearman fueron negativos en todos los algoritmos probados (dCMA, COBYLA, DE, mCMA, L-SHADE) y dimensiones (2D y 5D), aunque la fuerza de la correlación varió (desde débil a moderada).
Diferenciación de Tipos de Problemas: Las medidas distinguieron con éxito entre clases de problemas. Por ejemplo, en el entrenamiento de redes neuronales, las métricas de complejidad diferenciaron entre redes que utilizan funciones de activación ReLU frente a Tanh, alineándose con hallazgos previos que indican que las funciones de activación son diferenciadores clave en las características del paisaje, independientemente de la tarea de regresión específica o el tamaño de la red.
Limitaciones Observadas: Las métricas no capturaron parámetros específicos del problema que no alteran significativamente la estructura del código, como el número de picos en las funciones de Gallagher ( $f_{21}, f_{22}$ ) o la dimensionalidad del problema. Además, los valores atípicos con valores de $V_H$ muy altos (p. ej., $f_7, f_{21}, f_{22}, f_{24}$ ) mostraron una tendencia menos clara en los diagramas de dispersión de complejidad vs. rendimiento.

Significancia y Reivindicaciones
El artículo posiciona estas medidas de complejidad programática como complementarias a los enfoques de análisis de paisaje existentes, en lugar de un reemplazo. Los autores afirman que el enfoque ofrece ventajas distintivas:

Eficiencia: Es muy rápido de calcular automáticamente.
Invariancia: Es invariante a las transformaciones del espacio de búsqueda y no depende de estrategias de muestreo.
Potencial Predictivo: La correlación negativa con el rendimiento de los algoritmos sugiere que estas medidas tienen potencial como meta-características predictivas para la selección y configuración de algoritmos.

Los autores concluyen que, si bien la representación programática no puede capturar todas las propiedades de un paisaje de problemas relevantes para el rendimiento, proporciona una perspectiva estática única que evita la sobrecarga computacional del muestreo. Sugieren que trabajos futuros deberían explorar estas medidas en problemas del mundo real que involucren una ejecución de código extensa (p. ej., simulaciones numéricas) e investigar su utilidad para mejorar los "asistentes" (wizards) de selección de algoritmos.

El código como bola de cristal

El experimento: De círculos simples a picos caóticos

La conexión mágica: La complejidad del código predice el rendimiento

Por qué esto es importante

Más como este