Algoritmos de otimização

Todo problema solucionável apresenta pelo menos uma solução ótima. Imagine por exemplo que você precisa transportar algumas caixas usando um automóvel, que essas caixas têm tamanhos e formatos variados, e que elas não cabem todas no porta-malas do veículo. O problema, nesse caso, consiste em realizar a tarefa em questão, as soluções possíveis consistem no arranjo das caixas dentro do porta-malas, e a solução ótima pode ser descrita tanto em termos de maximizar o espaço utilizado no porta-malas em cada viagem, quanto em minimizar o número de viagens. Neste artigo, vamos usar esse problema como exemplo para apresentar os conceitos relacionados ao tópico.

Em termos mais genéricos, portanto, um problema de otimização trata da busca de uma solução que minimize ou maximize uma métrica relacionada ao problema. Algoritmos de otimização, por sua vez, são ferramentas matemáticas que são executadas de forma iterativa, comparando várias soluções possíveis, até que uma solução ótima, ou pelo menos satisfatória, seja encontrada. Com o aumento do poder computacional nos últimos anos, esses algoritmos se tornaram parte essencial do arsenal de várias atividades de design, seja de produto, seja de processo.

Para sua implementação, os algoritmos de otimização dependem de quatro elementos relacionados ao problema, conforme descritos a seguir.

Variáveis de design: São as variáveis para as quais estamos buscando uma solução. No caso da tarefa de transporte exemplificada, essas variáveis incluem a presença ou ausência de uma caixa em determinada corrida, assim como sua localização dentro do porta-malas.

Limitantes: São valores inerentes ao problema que relacionam as variáveis de design com certas características físicas e limitações de recursos. O formato e o tamanho do porta-malas é o limitante mais óbvio no problema que estamos tratando, pois esses valores determinam quais soluções são a priori possíveis e quais não são.

Função objetivo: É a função que vamos tentar minimizar ou maximizar. Como usamos métodos numéricos para o cálculo de otimização, é importante que esta função seja de fato escrita numa forma matemática. No exemplo, podemos tratar a tarefa tanto como um problema de maximização do espaço utilizado do porta-malas (onde esse valor é igual à soma dos volumes das caixas transportadas em uma corrida), ou de minimização do número de corridas (cujo valor é igual ao volume total das caixas, dividido pelo volume médio transportado em cada corrida).

Limites das variáveis: As próprias variáveis de design podem ter alguns limites intrínsecos, o que restringe o espaço de soluções possíveis. Imagine, por exemplo, que algumas caixas devem ser transportadas necessariamente em pé, ou que produtos frágeis devem ser transportados sempre em cima de produtos não-frágeis. Isso quer dizer que a solução ótima deve necessariamente estar limitada a essas restrições.

A seguir apresentamos alguns dos principais algoritmos de otimização.

Algoritmos evolucionários

São inspirados no fenômeno da evolução das espécies, utilizando conceitos como indivíduo, população, mutação, crossover, seleção natural e sobrevivência do mais apto para melhorar um junto de soluções possíveis de forma iterativa. Seguindo Darwin, a teoria da evolução é fundamentada pelas seguintes observações:

• Os indivíduos de uma espécie são capazes de produzir descendentes.
• Sem a incidência de influências externas, o tamanho da população e a quantidade de recursos de que essa população depende tendem a permanecer constantes.
• Há competição pelos recursos disponíveis.
• Os indivíduos da população são distintos entre si, e algumas dessas diferenças têm impacto na sua habilidade de competir por recursos.
• Algumas das variações entre os indivíduos são hereditárias.
• Indivíduos com maior capacidade de sobrevivência também têm maior probabilidade de produzir descentes, que herdarão algumas dessas características vantajosas.
• Há uma pressão para que a espécie se torne cada vez mais adaptada às pressões ambientais que lhe impactam.

Os algoritmos evolucionários funcionam de forma análoga. Cada solução possível é tratada como um indivíduo, e um universo de soluções é a população. A tratativa começa com um universo limitado de soluções, que em termos práticos podem ser geradas aleatoriamente, e caracterizam a primeira geração. Os indivíduos são ranqueados em função de conduzirem a uma melhor solução (de acordo com a função objetivo). Uma próxima geração é produzida, seguindo a seguinte heurística: primeiro, todos os indivíduos da geração atual podem ter algumas de suas variáveis de design alteradas, com baixa probabilidade, simulando o efeito de mutações; segundo, os indivíduos geram descendentes trocando soluções entre si, simulando o processo de crossover genético, sendo que os melhores indivíduos são selecionados para reprodução com maior probabilidade. A nova geração contém o mesmo número de indivíduos da geração anterior (ou seja, cada dois indivíduos geram dois novos indivíduos), mas pelo procedimento estabelecido, ela tende a ter indivíduos “melhor adaptados” ao “ambiente”, ou seja, tendem a ser melhores soluções ao problema que se busca resolver. O processo é repetido por um número de gerações estabelecido, ou até que a melhor solução produzida seja considerada aceitável.

A figura abaixo ilustra o processo.

Os algoritmos genéticos são um tipo de algoritmo evolucionário onde as variáveis de design são binárias. Se estivéssemos limitando o problema de transporte das caixas para que as variáveis que descrevem cada caixa fossem somente da forma “levar/não-levar” (fixando sua possível posição no porta-malas, por exemplo), então poderíamos tentar resolvê-lo usando um algoritmo genético.

Sistemas de aprendizado classificador

Estes algoritmos combinam um componente de exploração (tipicamente na forma de um algoritmo genético) com um componente de aprendizado (supervisado, não-supervisionado ou por reforço). Um dos sistemas de aprendizado classificador mais comuns é o de estilo Michigan. Este sistema é conectado ao ambiente através de detectores, que captam informação, e efetores, que conduzem a ações. Os detectores passam a informação a uma lista de mensagens, que interage com uma base de regras, onde residem regras do tipo se-então (neste contexto chamadas de classificadores), para definir a ação que deve ser tomada, a qual é passada aos efetores. O impacto das ações é mensurado através de um sistema de provisionamento de créditos, que pode aplicar recompensas ou penalidades se as ações se aproximarem ou se distanciarem da solução ideal, respectivamente. Além disso tudo, um sistema de descoberta de regras é responsável por encontrar novas regras e adicioná-las à população de classificadores.

As interações entre esses agentes são ilustradas na figura abaixo.

Considerando o problema de transporte de caixas, podemos dizer que o ambiente é o porta-malas, e a visualização das caixas colocadas age como detector. A lista de mensagens pode ser um vetor indicando quais caixas estão ausentes ou presentes. A base de regras pode conter uma regra do tipo SE parte inferior do porta-malas ENTÃO colocar produto não-frágil. No caso de uma caixa com produto frágil ser detectada na parte inferior, o efetor solicita sua retirada ou realocação para a parte superior. Se o arranjo alcançado estiver convergindo para a ocupação máxima do porta-malas (por exemplo, se todas as caixas estiverem bem posicionadas), então a solução é recompensada; em caso contrário (se uma caixa grande for colocada desalinhada, por exemplo), a solução é punida. Novas regras podem ser descobertas através do componente de exploração do sistema, que pode por exemplo eventualmente descobrir que uma regra do tipo SE caixa X na posição 1 e caixa Y na posição 2 ENTÃO caixa Z na posição 3 representa uma solução local e tende a conduzir à solução global ideal.

Subida da encosta

Pode ser considerado uma simplificação do algoritmo genético, onde o tamanho da população é definido como 1. Neste caso, o único indivíduo presente gera um descendente através de mutação; se o descendente tiver melhor performance que seu gerador, então ele o substitui, caso contrário é ignorado. O processo é repetido até que algum critério de parada seja atingido. Sendo um algoritmo de fácil interpretação e implementação, a subida da encosta costuma ser aplicada como uma primeira opção. Entretanto, para problemas não-convexos (ou seja, aqueles com mais de um ótimo local), ele tem a tendência de convergir prematuramente, ficando preso em um dos ótimos locais, já que sempre parte da melhor solução conhecida até então para explorar novas soluções. Para problemas onde o tempo de solução é limitado, como aqueles que devem ser solucionados em tempo real, este algoritmo ainda encontra aplicação, desde que as soluções ótimas locais sejam suficientes.

Têmpera simulada

Esta é uma técnica utilizada para aproximar a solução ótima global usando probabilidades, sendo preferida quando esta aproximação é mais importante do que uma solução ótima local precisa. O algoritmo inicia com uma solução arbitrária e, a cada passo, propõe uma alteração nesta solução. A cada alteração, ele checa se houve melhora ou piora do resultado da função objetivo. Se o resultado for melhor, então o algoritmo adota a nova solução. Caso contrário, ele gera um valor de probabilidade que é calculado em função da diferença no resultado da função objetivo, de forma que diferenças maiores tenham um valor de probabilidade menor. Então, ele decide se vai adotar a nova solução com base nesta probabilidade. Com esta heurística, o algoritmo consegue garantir que está convergindo para a solução ótima global, sempre selecionando soluções melhores, ao mesmo tempo em que evita ficar preso em soluções ótimas locais ao selecionar soluções piores em função de uma certa probabilidade. A animação abaixo mostra as iterações que o algoritmo realiza até encontrar a solução ótima global de uma função descrita pelo gráfico.

Neste artigo, apresentamos o conceito de algoritmos de otimização, descrevemos seus componentes, e explicitamos os algoritmos do tipo mais comuns.