Características das principais técnicas de otimização disponíveis no

Características das principais técnicas de
otimização disponíveis no mercado.
Introdução
A otimização é o processo de encontrar a melhor solução (ou solução ótima) de um conjunto de soluções
para um problema. Existe um conjunto particular de problemas para os quais é decisiva a aplicação de um
procedimento de otimização, sendo que muitos processos podem se beneficiar de uma alocação otimizada de
recursos. Esses recursos, que podem incluir capital, equipamentos, tarefas, tempo, ou até mesmo largura de
banda, devem ser cuidadosamente alocados nas quantidades corretas, nos tempos corretos, e na seqüência
correta para a obtenção do melhor resultado possível. São problemas complexos, muitas vezes de difícil
solução, e que envolvem significativas reduções de custos, melhorias de tempos de processos, ou uma
melhor alocação de recursos em atividades.
As técnicas de otimização devem ser utilizadas quando não existe uma solução simples e diretamente
calculável para o problema. Isso geralmente ocorre quando a estrutura do problema é complexa, ou existem
milhões de possíveis soluções. Nesses casos, é possível que não exista nenhum procedimento direto de
solução, de forma que as técnicas de otimização podem ser utilizadas na busca pela melhor solução para o
problema. Em alguns casos, quando nenhuma solução pode ser encontrada, o problema é "relaxado"
(algumas restrições ou alternativas são descartadas), e a otimização pode ser utilizada para encontrar a
solução ótima.
A otimização pode se dividida em 2 classes: global e local. A otimização global encontra a melhor solução
do conjunto de "todas" as soluções possíveis. A otimização local encontra a melhor solução dentro de um
conjunto de soluções que está próximo a outro. Na otimização local, a solução encontrada depende do ponto
de início do processo de busca de otimização. A otimização global sempre encontrará a melhor solução
possível, independentemente das condições de início do processo de busca, porém, geralmente, requisita um
maior poder de computação.
Pode ser praticamente impossível de se encontrar uma "solução ótima global" em algumas aplicações,
entretanto, ums "solução ótima local" pode ser bastante eficiente. Em muitos casos, encontrar o ótimo global
não é necessário. Encontrar rapidamente uma "boa solução" (ótimo local) pode ser mais desejável do que
encontrar demoradamente a melhor solução possível. O tipo de otimização empregada depende da estrutura
do problema e do grau de confiabilidade das variáveis utilizadas. Se todas as variáveis de decisão são reais, e
a função-objetivo e restrições são lineares, a programação linear, geralmente, é a melhor escolha. Entretanto,
o mundo real usualmente requer funções não lineares, variáveis de valores discretos (ou inteiras), variáveis
lógicas e restrições de diferentes naturezas aplicadas a esse gama de elementos.
Existem numerosas técnicas de otimização. A aplicação de cada uma delas depende essencialmente do tipo
de problema. Sistemas baseados em regras são comumente usados em aplicações de controle, e envolvem
regras pré-determinadas para gerar as soluções. Programação linear e suas extensões são, via de regra, as
melhores técnicas, e são amplamente utilizadas para otimização de objetivos globais. “Redução de domínio”
e “Programação por Restrições” estão sendo combinadas em uma técnica relativamente nova aplicada
diretamente a problemas de "scheduling". Algoritmos genéticos e recozimento simulado são duas recentes
técnicas desenvolvidas que implementam soluções ao longo do tempo. E, agrupando boa parte dessas
tecnologias, temos uma verdadeira ciência do conhecimento em evolução, que é a utilização desses e outros
conceitos no que se denomina Inteligência Artificial, e seu braço mais mercadológico, a área de
desenvolvimento de Sistemas Especialistas.
Programação linear e inteira
A programação linear é provavelmente a mais conhecida e utilizada técnica de otimização em todo o mundo.
É geralmente utilizada para tomada de decisões gerenciais sobre a alocação de recursos para produção. Os
custos dos recursos e as receitas geradas pelos produtos são usados para determinar a melhor solução.
www.ilab.com.br - Tel: (16) 3623-5680
Página 1 de 5
Qualquer problema que possa ser formulado com variáveis de decisão reais, tendo uma função-objetivo
linear, e funções de restrição lineares, em princípio pode ser solucionado através da programação linear. Tais
programas originariamente utilizavam o método Simplex, porém, mais recentemente, métodos de "pontos
interiores" se mostraram mais eficientes.
Embora a programação linear seja muito eficiente para a resolução de problemas lineares, sua aplicação a
problemas que apresentem objetivos ou restrições não-lineares tem levado a problemas e falhas de
modelagem. Em alguns casos, funções não-lineares podem ser aproximadas por algumas funções lineares
conjugadas, e a programação linear ainda pode ser utilizada. Contudo, isso leva a uma representação
ineficiente do problema, podendo causar matrizes de decisão explosivamente grandes que demandam um
tempo excessivo para resolução. Esta é uma dificuldade comum em problemas que envolvem, por exemplo,
"scheduling" e "sequenciamento" de processos.
De forma equivalente, outros tipos de variáveis não podem ser tratadas diretamente com o uso de
programação linear. Programação inteira usa programação linear para resolver problemas sobre variáveis
inteiras, mas ainda com funções objetivo e restrições puramente lineares. As variáveis inteiras são
representadas como variáveis reais no algoritmo de resolução do problema. Então um processo repetitivo é
usado para "delimitar" o valor destas variáveis em valores inteiros, através da adição de restrições e
reprocessamento da solução. Esse método, conhecido como "branch & bound", finaliza quando todas as
variáveis assumem valores inteiros. Quando o número de variáveis inteiras é pequeno, a programação inteira
soluciona o problema rapidamente. Infelizmente esse procedimento pode consumir muito tempo com um
número grande de variáveis inteiras, podendo, em alguns casos, necessitar de milhões de iterações para
serem resolvidos.
Programação por restrições
A programação por restrições consiste de uma técnica de formulação de problemas onde o objetivo é o
descobrir algum estado do problema que satisfaça um determinado conjunto de restrições. O primeiro passo
na resolução de qualquer problema consiste na determinação da abrangência ou domínio do problema. O
conjunto de todos os possíveis estados do problema, onde se encontra a solução ainda desconhecida,
denomina-se espaço de busca.
Utilizando-se a técnica de programação por restrições, são formuladas condições que diminuem
substancialmente a quantidade de buscas necessárias para se encontrar a solução do problema. Em tese,
quanto maior for o número de restrições informadas ao sistema, menor será o número de possíveis soluções a
serem analisadas, e portanto, melhor será o desempenho da aplicação. Comparando-se a técnica de
programação por restrições com outros procedimentos tradicionais para solução de problemas de otimização
discreta, como a programação linear, notamos que a primeira possui algumas vantagens qualitativas.
A primeira delas diz respeito à representação do problema, que no caso da programação por restrições é
muito mais compacta - exigindo um número muito menor de variáveis - com melhorias no desempenho da
aplicação. O segundo ponto relaciona-se ao processo de propagação das restrições, que permite também um
desempenho melhor ao "eliminar" mais rapidamente combinações que não solucionam o problema, e
portanto agilizando a busca pela solução.
E por último, o que talvez seja a principal vantagem, a programação por restrições permite uma
representação mais direta de alguns problemas do que, por exemplo, a programação linear. Essa última, por
estar atrelada aos rígidos algoritmos implementados, necessita de uma estrutura que, muitas vezes, impõe
uma adaptação das variáveis para a representação do problema. A programação por restrições, por ser
implementada através uma linguagem de programação, permite a elaboração de algoritmos especialmente
dedicados a cada tipo de questão, conseguindo priorizar os pontos de maior importância, identificar pontos
de infactibilidade e propor caminhos alternativos segundo o entendimento e intervenção dos especialistas.
Nesse sentido, a modelagem do problema e o conhecimento existente sobre ele são muito mais valorizados e
contribuem mais efetivamente na sua solução.
www.ilab.com.br - Tel: (16) 3623-5680
Página 2 de 5
Algoritmos Genéticos
Algoritmos genéticos encontram a solução para problemas utilizando um mecanismo de evolução a partir de
uma solução aceitável para um nível superior de otimização. Em contraste com outros processos de
otimização, os algoritmos genéticos focam uma otimização local; entretanto, a evolução é controlada para
tentar percorrer todo o espaço de busca, o que pode tornar a otimização global. Uma população de soluções
existe em cada iteração do algoritmo. Essa população pode ser utilizada para evoluir para uma nova
população na próxima iteração. A evolução é arquivada utilizando operadores específicos: reprodução,
cruzamento e mutação.
O operador de reprodução copia uma solução a partir da população anterior para uma nova população com
uma probabilidade dependente da "saúde" da solução. A "saúde" da solução é o valor da função objetivo de
otimização. Quanto melhor a função-objetivo, maior será a probabilidade de a solução "sobreviver" para a
próxima iteração.
O operador de cruzamento divide uma seção de duas soluções. Cada nova solução contém parte de duas
últimas soluções. Por exemplo, consideremos o problema de encontrar o valor de 5 variáveis. Duas soluções
para esse problema poderiam ser [10010] e [11011]. Fazendo um cruzamento sobre os 3 valores
intermediários dessas soluções, obteríamos [11010] e [10011] na nova população. Esse operador busca criar
soluções que possuam as melhores propriedades das soluções originais.
O operador de mutação modifica randomicamente uma pequena parte de uma solução. Mutações muito
pequenas sempre ocorrem na prática do processo de busca, entretanto, esse passo é necessário quando da
busca de uma solução de otimização global. Com apenas os operadores de reprodução e cruzamento, os
algoritmos genéticos podem vasculhar apenas uma parte do espaço de busca onde exista um ótimo local. O
operador de mutação permite ao algoritmo pular para uma nova solução em outro contexto. Desta forma, se
ocorrerem mutações suficientes, o algoritmo conseguirá atingir um valor de ótimo global.
Obviamente, algoritmos genéticos demandam um enorme número de iterações para obter sucesso, porém a
simplicidade do processo permite uma velocidade de execução razoavelmente boa. Eles se mostraram
particularmente úteis para a resolução de problemas com restrições e funções objetivos que são muito
difíceis de serem tratadas. Algoritmos genéticos funcionam melhor com grandes populações de soluções,
uma vez que isso significa um aumento nas chances de uma boa solução. Infelizmente, o espaço necessário
para uma solução simples geralmente é grande, de forma que esses algoritmos usam uma grande quantidade
de memória para manter a população inteira de soluções. Gerando uma população inicial grande pode
consumir muito tempo, e não existe maneira de se saber de antemão quando o algoritmo encontrou uma
solução ótima global. Como uma evolução natural, o quanto mais permitirmos que um algoritmo genético
seja processado, melhor a solução se torna. A incerteza de quando finalizar o algoritmo, combinada com o
excessivo tamanho da população inicial de soluções, pode levar a um tempo indesejavelmente longo de
execução.
Heurísticas
Em muitos casos, a otimização não é possível ou simplesmente não é eficiente o suficiente para gerar
soluções no tempo disponível, de forma que é necessária a utilização de heurísticas. Heurísticas são
basicamente algoritmos que não buscam diretamente a otimização pura, mas geram soluções aceitáveis
("boas soluções"). São utilizadas por serem computacionalmente mais eficientes e/ou fáceis de serem
implementadas.
Entretanto, em alguns casos, elas podem não ser muito precisas ou previsíveis. Mais ainda, elas
ocasionalmente incorrem em falhas, devido à escalabilidade do problema e/ou hipóteses errôneas que
estejam sendo consideradas. Se um problema é resolvido repetitivamente e os parâmetros se alteram
constantemente, as chances de falha de uma heurística são consideravelmente maiores. Outra característica
www.ilab.com.br - Tel: (16) 3623-5680
Página 3 de 5
de um algoritmo heurístico é o de que ele sempre gera uma resposta para o problema, mas algumas vezes
essas soluções não são de boa qualidade.
A despeito dessas características, muitas vezes a performance de uma heurística pode ser melhorada através
da incorporação de algoritmos localizados de otimização. Soluções melhores são geradas para um
subconjunto de condições utilizando alguns passos de otimização local. Contudo, a "pura otimização" é a
única garantia da "melhor solução" para todos os parâmetros de um problema.
Sistemas baseados em regras
Sistemas baseados em regras não são ferramentas de otimização, mas muitas vezes são utilizados em
sistemas de controles, em heurísticas e em outras formas de sistemas que podem prover algum nível de
otimização. Esses sistemas consistem de um processo controlado por um conjunto fixo de centenas ou
mesmo milhares de regras. Na prática, as regras e suas interações são muito complexas, sendo que
dificilmente a otimização pode ser garantida. De fato, sistemas baseados em regras compreendem sistemas
heurísticos. Geralmente geram boas soluções, entretanto existem casos nos quais as regras demonstram uma
performance ruim. Atualmente esse tipo de tecnologia é mais utilizado em sistemas de alarme, e sistemas de
correlação de informações e filtragem de dados, particularmente em aplicações de monitoramento de redes
de telecomunicações.
Existe um caso no qual sistemas baseados em regras sempre atingem uma otimização real. Se tiver sido
provado que as regras utilizadas sempre gerem uma solução ótima, para qualquer estado do processo, o
sistema pode ser enquadrado dentro dos níveis de otimização real. Infelizmente, essas provas usualmente
transformam-se em problemas mais complexos que a aplicação original, inviabilizando essa conclusão.
Tipicamente o maior problema associado aos sistemas baseados em regras é o da formulação correta e
consistente das regras a serem aplicadas.
Recozimento Simulado (Simulated Annealing)
O recozimento simulado (simulated annealing) é um algoritmo de otimização similar aos algoritmos
genéticos, uma vez que utiliza o mesmo princípio de evolução da solução ao longo do tempo. O termo
"annealing" refere-se à forma como que os metais líquidos são esfriados vagarosamente de forma a garantir
uma baixa energia e formatos de estrutura altamente sólidos. O recozimento simulado pode ser encarado
como um algoritmo que "esfria" vagarosamente a solução para garantir que ela possua a menor funçãoobjetivo possível. Por garantir um alto nível de movimentação através do espaço de busca, o recozimento
simulado busca varrer todo esse espaço, de forma a permitir uma solução global. Mais tarde no processo, o
resfriamento permitirá apenas pequenos movimentos no espaço de soluções, e o processo converge
finalmente para uma solução final. A natureza de movimentos através do processo significa que, uma vez
que o processo "resfrie" totalmente, a solução com a menor função-objetivo possível é encontrada em uma
área específica da memória alocada pelo programa.
O recozimento simulado necessita de 4 elementos para processamento. O primeiro é uma descrição das
possíveis soluções. O segundo é um gerador de alterações randômicas entre as soluções. O terceiro é uma
função-objetivo para as soluções. Por último, o quarto elemento é um parâmetro de controle e um
"scheduling de recozimento", que descrevem como o parâmetro de controle varia ao longo do tempo.
O recozimento simulado tem as mesmas vantagens e desvantagens dos algoritmos genéticos. A abordagem
pode resolver problemas com funções de alto grau de complexidade, porém a otimização tem um caráter
local, e não existe maneira de saber quando uma solução ótima foi alcançada. Novamente, quanto mais se
permite que o algoritmo processe a solução, melhor a solução será. Entretanto, não existe maneira de se
certificar quando finalizar o processo e obter a melhor solução possível.
www.ilab.com.br - Tel: (16) 3623-5680
Página 4 de 5
Inteligência Artificial e Sistemas Especialistas
A Inteligência Artificial (I.A.) tem se consolidado, ao longo dos últimos anos, como uma das mais poderosas
ferramentas para obtenção de ganhos significativos de produtividade nas empresas. Os resultados práticos de
sua aplicação, nos mais diversos nichos de negócio, vêm crescendo tanto em valor como em importância à
medida que se aproximam dos setores gerenciais de tomada de decisão nas empresas.
Existem muitas idéias controvertidas e conceitos mal formulados a respeito do que é essencialmente a I.A..
Um conceito, que de algum modo é aceito universalmente, é o de que a I.A. compreende uma ciência para
desenvolvimento de técnicas e algoritmos destinados à resolução de problemas complexos.
A aplicação das técnicas de I.A. no desenvolvimento de aplicações resulta em sistemas especialistas, que são
nada mais do que programas de computador que usam conhecimento e procedimentos de inferência para
resolver problemas que são de uma complexidade e dificuldade superiores à capacidade humana em calculálos. Ou, em outras palavras, um sistema especialista emula a habilidade de tomada de decisão de um ou mais
especialistas humanos na resolução matemática de problemas.
Desta forma, um dos mitos de que esta classe de aplicações busca substituir a atuação humana perde
totalmente o sentido. Todo o processo de busca e tomada de decisão deve ser orientado a partir do
conhecimento dos "especialistas humanos", que serão os principais e essenciais condutores do sistema. Os
programas nada mais são, portando, do que ferramentas que embutiram dentro de seu código algum
conhecimento ou método para resolver uma questão, e que permitem aos "especialistas humanos" uma visão
mais aprofundada ou específica que seria impossível sem esse mecanismo de cálculo avançado.
A I.A. possui uma série de áreas de atuação atualmente. Algumas dessas áreas são muito específicas, outras
ainda de cunho apenas acadêmico, mas todas em constante desenvolvimento nos principais institutos de
pesquisa do mundo. Exemplos dessas áreas são:
• Reconhecimento ótico
• Redes neurais
• Robótica
• Representação de conhecimento
• Linguagem natural
• Compreensão da fala
• Problemas de busca
• Lógica difusa
Dentro do âmbito de aplicações comerciais, diversos estudos e pesquisas têm direcionado os esforços da I.A.
para o desenvolvimento de técnicas que solucionem problemas complexos de alocação, planejamento e
otimização de recursos. Nessa esfera, modernos algoritmos de otimização têm sido empregados em
aplicações comerciais, que demonstram uma capacidade ímpar na obtenção de retorno financeiro às
empresas.
www.ilab.com.br - Tel: (16) 3623-5680
Página 5 de 5