O problema de otimização

Problemas de otimização são aqueles que visam determinar o pontos extremos de uma função, seja ele mínimo, e então os problemas serão de minimização, ou máximo, problemas de maximização. Otimização é algo extremamente comum em nosso cotidiano. Os exemplos vão desde os mais simples, como pegar um caminho mais curto para chegar no trabalho, escolher os produtos corretos no supermercado para diminuir o preço da compra; até problemas mais complexos, como minimizar custos de uma produção em uma fábrica, determinar o melhor conjunto de rotas para uma transportadora, dentre diversos outros.

A otimização abrange as mais diversas áreas do conhecimento, problemas de engenharia, de biologia, de economia/administração, etc, e seja qual for o problema e a área, o primeiro passo rumo a otimização do mesmo é a modelagem matemática. A otimização necessita de uma função matemática para atuar e muita das vezes, principalmente em sistemas dinâmicos, a modelagem não é tarefa simples, sendo uma esta uma área da engenharia. Este post não tem a intenção de discutir como modelar um sistema, portanto já partimos do princípio que o problema é modelado e sua função é conhecida.

A modelagem do sistema, no problema de otimização, é representado pela função objetivo, também conhecida como fitness ou aptidão. Essa é a função que desejamos minimizar ou maximizar. Essa função pode ser simples, como por exemplo uma função de duas dimensões (x,y) , até funções mais complexas com n dimensões, como mostra a Figura 1.

optmiztion

Figura 1: Funções obejtivos. (a) Duas dimensões (b) Mais de duas dimensões

 

Além disso, um dos grande desafios na otimização são as funções multimodais, que são aquelas que em sua curva possuem diversos mínimos e/ou máximos locais. Na Figura 2 é mostrado uma função multimodal 2D (a função é 2D para facilitar o exemplo). Perceba que a função possui diversas cristas e vales. Suponhamos que o nosso desejo é minimizar essa função, ou seja, encontrar em qual ponto dela o valor é mínimo. Bom, em nossa imagem ele esta demarcado com um ponto verde. Esse ponto é a solução ótima para o problema. Os demais pontos vermelhos são mínimos locais e eles dificultam algum algoritmo de otimização a encontrar a solução ótima. O mesmo se aplica para problemas de maximização.

 

multimodalfunction

Figura 2: uma função 2D multimodal

Dentro da grande área de otimização existem outras sub-áreas, de acordo com o tipo de problema. Existem problemas de otimização linear, que são os mais fáceis e é possível obter a solução ótima, e problemas não lineares, que são os mais difíceis e em muitos deles é complicado garantir uma solução ótima. Também podemos dividir os problemas de otimização em contínuos, aqueles que as variáveis são contínuas, e otimização inteira, no qual o objetivo é encontrar um variável inteira. Além disso, o problema pode ter restrições ou não. Problemas com restrições são aqueles em que o universo de busca, como por exemplo, nossas curvas das Figuras 1 e 2, são restritos. Significa que existem pontos em que o a solução não cabe no problema e isso é mais uma complicação para se obter o ótimo global.

Algoritmos de otimização

Existem diversos algoritmos de otimização, para os mais variados tipos de problemas. Dentre eles:

  • Simplex: utilizado para otimizar somente problemas lineares, com ou sem restrição. Garante a solução ótima para o problema, mas por outro lado, a maioria esmagadora dos problemas do mundo real é não linear.
  • PSO (particle swarm optimization): Algoritmo heurístico utilizado para otimizar qualquer tipo de função, com ou sem restrições (é preciso adaptar o algoritmo para isso). Não garante a solução ótima do problema, mas garante uma boa solução. Já fizemos um post sobre o PSO neste site.
  • Algoritmo Genético – GA: Segue o mesmo princípio do PSO. Também é heurístico, para qualquer tipo de problema e não garante o ótimo.
  • DE (differential evolution): Da mesma família que o GA e com as mesmas características. Também existe um post sobre o DE neste site.
  • Gradiente descendente: Algoritmo baseado em derivadas. Utilizado em otimizações não lineares. Possui um ponto fraco de cair em mínimos locais de maneira fácil.
  • Simulated anneling: Fundamentado na termodinâmica, também é uma heurística para problemas não lineareas.
  • Nelder-Mead: Também uma heurística utilizada para funções não lineares e principalmente quando as derivadas não podem ser computadas.

Esses são apenas alguns exemplos, existem diversos outros algoritmos de otimização e cada um tem suas próprias qualidades, deficiências e características.

Exemplo de função objetivo para otimização

Um exemplo de função objetivo não linear para otimização é mostrado abaixo:

function

 

Esta é uma função que pode ter dimensão n e é um benchmark para testar se um algoritmo de otimização é eficaz. Além disso, pode ser inclusas restrições, limitando o espaço de busca de x . Essa função é usada para minimização.

Por falar em minimização, caso você implemente um algoritmo de minimização, para converter o problema para otimização bastar utilizar o negativo da função objetivo, ou seja, min [f(x)] = max [-f(x)].

Exemplo de problema de otimização – O problema do caixeiro viajante

Um dos problemas clássicos na área de otimização é o problema do caixeiro viajante. Todo aluno iniciante na área de computação certamente já ouviu falar dele. A formulação do problema é simples, mas sua solução extremamente complexa de acordo com o que o número de cidades cresce.

Formulação do problema: Imagine que você seja um caixeiro que realiza entregas em N cidades. Para economizar no combustível e no tempo, seu objetivo é simples: encontrar a menor rota para visitar as N cidades, visitando uma única vez cada uma delas, e  retornar à cidade de origem.

Figura 3: O problema do caixeiro viajante

Este é um exemplo clássico de otimização, e a medida que as cidades crescem, encontrar a solução ótima é extremamente difícil. Sua modelagem é realizada por meio de grafos e este é um problema NP-hard.

Caso queira saber mais, assista este vídeo.

 

 

Gostou? Então compartilhe!