🤖 AI

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

Este artigo propõe uma abordagem inovadora para caracterizar problemas de otimização através do cálculo do volume de Halstead e da entropia de suas implementações programáticas, demonstrando que essas medidas de complexidade baseadas em código servem como meta-características preditivas eficazes e livres de amostragem para a seleção de algoritmos.

Autores originais: Marcus Gallagher, Katherine M. Malan

Publicado 2026-08-11

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Marcus Gallagher, Katherine M. Malan

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando ensinar um robô a resolver um labirinto. Às vezes o labirinto é um corredor simples e reto; outras vezes é um labirinto sinuoso e retorcido, com becos sem saída e armadilhas. No mundo da ciência da computação, isso é chamado de otimização: encontrar a melhor solução possível para um problema. Mas aqui está a parte difícil: nem todos os labirintos são iguais. Alguns são fáceis de serem resolvidos por um robô, enquanto outros fazem até os algoritmos mais inteligentes se perderem.

Para ajudar os robôs a escolherem a estratégia certa, os cientistas tentam "caracterizar" ou descrever esses labirintos antes mesmo de o robô começar a correr. Eles procuram por pistas, como o quão acidentado é o terreno ou quantos becos sem saída existem. Geralmente, para encontrar essas pistas, o robô precisa dar alguns passos, olhar ao redor e medir o terreno. Isso é como enviar um batedor para a escuridão para mapear a caverna. Mas e se o robô pudesse apenas olhar para a planta baixa do labirinto e adivinhar o quão difícil seria resolvê-lo, sem nunca colocar os pés dentro dele? Essa é a grande questão que este artigo levanta. Ele sugere que a maneira como um problema é escrito em código de computador pode conter o segredo de quão difícil ele é de resolver, assim como a complexidade de uma receita pode sugerir o quão difícil será o cozimento.

O Código como uma Bola de Cristal

Neste artigo, Marcus Gallagher e Katherine Malan propõem uma forma nova e ligeiramente mágica de olhar para esses problemas difíceis. Em vez de enviar um batedor para medir a paisagem, eles sugerem que apenas leamos a "receita" que o computador usa para criar o problema.

Pense em um problema de otimização como um nível de videogame. Para construir o nível, um programador escreve o código. Alguns níveis são simples: "Mova para frente, pule sobre um buraco, colete a moeda". O código para isso é curto e usa comandos básicos. Outros níveis são caóticos: "Se o céu estiver azul, multiplique sua velocidade pelo número de estrelas, depois subtraia a raiz quadrada da sua vida, mas apenas se você estiver usando um chapéu". O código para isso é longo, bagunçado e usa uma enorme variedade de comandos.

A grande ideia dos autores é esta: Quanto mais bagunçado e complexo for o código, mais difícil será o problema para um algoritmo resolver.

Eles pegaram emprestadas duas ferramentas do mundo da engenharia de software para medir essa "bagunça".

Volume de Halstead: Imagine contar cada palavra e símbolo em um parágrafo. Se você tem um conto curto com palavras simples, a contagem é baixa. Se você tem um romance com vocabulário complexo e frases longas, a contagem é alta. Esta medida conta os "operadores" (como símbolos matemáticos) e "operandos" (como números e variáveis) no código.
Entropia de Shannon: Isto é um pouco como medir o fator surpresa. Se um parágrafo usa as mesmas cinco palavras repetidamente, é previsível (baixa entropia). Se utiliza uma enorme variedade de palavras únicas em uma ordem aleatória, é imprevisível (alta entropia).

O Experimento: De Círculos Simples a Picos Caóticos

Para testar sua teoria, os autores utilizaram um conjunto famoso de 24 problemas de teste usados por cientistas em todo o mundo (conhecido como suíte BBOB). Eles variam desde a função "Esfera" (uma colina perfeitamente lisa e arredondada que é fácil de descer rolando) até a função "Lunacek bi-Rastrigin" (uma paisagem irregular e rochosa com milhares de pequenos picos e vales).

Eles escreveram o código do computador para cada um desses 24 problemas e rodaram seus calculadores de "bagunça" neles. Os resultados foram exatamente o que esperavam:

A função Esfera, simples e suave, teve as pontuações de complexidade mais baixas.
A função Lunacek, irregular e difícil, teve as pontuações de complexidade mais altas.
De fato, a função Lunacek era cerca de 9,3 vezes mais complexa em sua estrutura de código do que a função Esfera.

Eles até testaram isso em um tipo diferente de problema: o treinamento de uma rede neural (um tipo de cérebro de IA). Descobriram que o código para uma rede que usa uma função de ativação "Tanh" era ligeiramente mais complexo do que um usando "ReLU", e isso coincidia com a ideia de que a versão Tanh é um quebra-cabeça um pouco mais difícil de resolver.

A Conexão Mágica: A Complexidade do Código Prediz o Desempenho

A verdadeira magia acontece quando eles comparam esses scores de código com o quão bem diferentes algoritmos realmente performaram. Eles analisaram dados de cinco algoritmos "robôs" diferentes tentando resolver esses 24 problemas.

Eles encontraram um padrão claro: Quanto mais complexo o código, pior foi o desempenho dos robôs.

É uma relação negativa. Quando o código era simples (baixo volume de Halstead), os robôs resolviam o problema de forma rápida e fácil. Quando o código era complexo (alto volume de Halstead), os robôs tinham dificuldades, levavam mais tempo ou ficavam presos. Por exemplo, em problemas de 5 dimensões, a conexão entre a complexidade do código e o mau desempenho foi bastante forte.

No entanto, os autores são cuidadosos ao notar que isso não é uma bola de cristal perfeita. Houve alguns problemas "outliers" (fora da curva) onde o código era muito complexo, mas os robôs não performaram tão mal quanto o código sugeria. Isso sugere que, embora a complexidade do código seja uma ótima dica, não é a única coisa que importa.

Por Que Isso Importa

A beleza desta abordagem é que ela é incrivelmente rápida e não requer trabalho extra. Os métodos tradicionais para entender um problema geralmente envolvem rodar o algoritmo milhares de vezes apenas para ver como é a paisagem. Isso é como enviar um batedor para percorrer todo o labirinto apenas para desenhar um mapa.

Em contraste, o método dos autores é como olhar para a planta baixa do labirinto. Você pode calcular a complexidade do código em uma fração de segundo, sem rodar o problema uma única vez. Não importa o tamanho do problema ou quantas dimensões ele possui; o método apenas olha para a estrutura das instruções.

Os autores sugerem que esta nova medida de "complexidade de código" pode ser uma adição útil à caixa de ferramentas dos cientistas que projetam algoritmos. Ela não substitui as velhas formas de olhar para os problemas, mas adiciona uma nova forma super rápida de adivinhar o quão difícil um problema será antes mesmo de começar a resolvê-lo. É um passo promissor para ajudar os computadores a escolherem a ferramenta certa para o trabalho, simplesmente lendo as instruções.

Resumo Técnico: Caracterização de Problemas de Otimização Utilizando Representação Programática

Enunciado do Problema
A caracterização de instâncias de problemas de otimização é fundamental para compreender o comportamento de algoritmos, facilitar a seleção de algoritmos e configurar otimizadores. As abordagens existentes, como a Análise de Paisagem Exploratória (ELA - Exploratory Landscape Analysis), baseiam-se na amostragem do espaço de busca para extrair características. No entanto, esses métodos enfrentam limitações práticas: consomem avaliações caras da função objetivo, são sensíveis ao tamanho e à estratégia de amostragem e podem falhar em fornecer representações robustas de paisagens complexas. Além disso, diferentes conjuntos de características costumam fornecer informações complementares em vez de sobrepostas, sugerindo a necessidade de abordagens de caracterização diversas.

Metodologia
Os autores propõem uma abordagem inovadora que caracteriza problemas de otimização com base na representação programática de suas funções objetivo, em vez de amostrar o espaço de busca. A intuição central é que a complexidade do código necessário para implementar uma função objetivo correlaciona-se com a complexidade da paisagem de busca resultante. Estruturas matemáticas simples geram códigos simples e paisagens suaves, enquanto funções complexas exigem códigos mais longos e densos em operadores e manifestam-se como paisagens irregulares.

O estudo utiliza duas medidas específicas de complexidade de programa derivadas da engenharia de software e da teoria da informação:

Volume de Halstead ( $V_H$ ): Uma medida de tamanho e complexidade de programa definida como $V_H = (N_1 + N_2) \log_2(\eta_1 + \eta_2)$ , onde $N$ representa o número total de operadores/operandos e $\eta$ representa o número de operadores/operandos distintos.
Entropia de Shannon ( $H$ ): Uma medida do conteúdo de informação por token, escalonada pelo número total de tokens ( $N$ ). Os autores observam que, sob suposições de probabilidade uniforme, $H$ aproxima-se de $V_H$ .

Estas métricas são calculadas estaticamente a partir do código-fonte (especificamente implementações em C) das funções objetivo. O estudo avalia estas medidas no:

Conjunto de testes BBOB (Black-Box Optimisation Benchmarking) sem ruído (24 funções).
Tarefas de otimização de pesos de redes neurais (treino de redes feed-forward com funções de ativação ReLU e Tanh).

Principais Contribuições e Resultados

Caracterização Estática e Sem Amostragem: O método proposto não requer amostragem do espaço de busca nem avaliações da função objetivo. É invariante a transformações (ex: rotação, condicionamento) e à dimensionalidade do problema (visto que a dimensionalidade é tratada como um contador de laço ou um operando único na estrutura do código).
Correlação com o Desempenho do Algoritmo: Quando aplicado ao conjunto BBOB, o volume de Halstead e a entropia mostraram-se negativamente correlacionados com o desempenho do algoritmo (medido pela Área Sob a Curva normalizada da função de distribuição cumulativa empírica).
- Valores de complexidade mais elevados (ex: $f_{24}$ , Lunacek bi-Rastrigin) corresponderam a um menor desempenho do algoritmo.
- Valores de complexidade mais baixos (ex: $f_1$ , Sphere) corresponderam a um maior desempenho.
- Os coeficientes de correlação de postos de Spearman foram negativos em todos os algoritmos testados (dCMA, COBYLA, DE, mCMA, L-SHADE) e dimensões (2D e 5D), embora a força da correlação tenha variado (variando de fraca a moderada).
Diferenciação de Tipos de Problemas: As medidas distinguiram com sucesso classes de problemas. Por exemplo, no treino de redes neurais, as métricas de complexidade diferenciaram redes que utilizam funções de ativação ReLU versus Tanh, alinhando-se com descobertas anteriores de que as funções de ativação são diferenciadores fundamentais em características de paisagem, independentemente da tarefa de regressão específica ou do tamanho da rede.
Limitações Observadas: As métricas não capturaram parâmetros específicos do problema que não alteram significativamente a estrutura do código, como o número de picos nas funções Gallagher ( $f_{21}, f_{22}$ ) ou a dimensionalidade do problema. Adicionalmente, outliers com valores de $V_H$ muito elevados (ex: $f_7, f_{21}, f_{22}, f_{24}$ ) apresentaram uma tendência menos clara nos gráficos de dispersão de complexidade vs. desempenho.

Significância e Alegações
O artigo posiciona estas medidas de complexidade programática como complementares às abordagens existentes de análise de paisagem, em vez de uma substituição. Os autores alegam que a abordagem oferece vantagens distintas:

Eficiência: É muito rápida de calcular automaticamente.
Invariância: É invariante a transformações do espaço de busca e não depende de estratégias de amostragem.
Potencial Preditivo: A correlação negativa com o desempenho do algoritmo sugere que estas medidas têm potencial como meta-características preditivas para a seleção e configuração de algoritmos.

Os autores concluem que, embora a representação programática não consiga capturar todas as propriedades de uma paisagem de problema relevantes para o desempenho, ela fornece uma perspectiva estática única que evita o custo computacional da amostragem. Sugerem que trabalhos futuros explorem estas medidas em problemas do mundo real que envolvam execução extensa de código (ex: simulações numéricas) e investiguem a sua utilidade na melhoria de "assistentes" (wizards) de seleção de algoritmos.

O Código como uma Bola de Cristal

O Experimento: De Círculos Simples a Picos Caóticos

A Conexão Mágica: A Complexidade do Código Prediz o Desempenho

Por Que Isso Importa

Mais como este