Você está aqui: Página Inicial / Pós-Graduação / Informática / Temas de Pesquisa / Resolvendo problemas reais utilizando inteligência computacional e otimização

Resolvendo problemas reais utilizando inteligência computacional e otimização

Prof. Dr. Bruno Nogueira e Prof. Dr. Rian Pinheiro

Problemas de otimização podem ser definidos, de forma geral, da seguinte maneira: dado um conjunto S e uma função custo definida sobre este conjunto, encontrar um elemento de S que maximiza/minimiza esta função. Técnicas de inteligência computacional e otimização possuem uma ampla gama de aplicações, uma vez que quase toda empresa está envolvida na resolução de problemas de otimização. Muitos problemas práticos e teóricos em engenharia, economia e planejamento podem ser modelados convenientemente como problemas de otimização. Por exemplo, empresas de telecomunicações interessadas no melhor projeto das redes de comunicação para otimizar o custo e a qualidade do serviço; empresas que operam no mercado financeiro interessadas na melhor estratégia de alocação de ativos para otimizar o lucro e o risco; empresas de distribuição interessadas na melhor alocação das entregas nos veículos disponíveis de forma a otimizar a distância percorrida pelos veículos.

Todavia, resolver alguns dos problemas mencionados anteriormente é uma tarefa bastante complexa, já que vários deles pertencem à classe NP-difícil, o que torna sua resolução por meio de métodos exatos pouco efetiva em instâncias de dimensões elevadas. Do ponto de vista teórico, esses problemas apresentam além da natureza combinatória uma elevada complexidade computacional. Inclusive, não são conhecidos métodos eficientes para solucioná-los.  Ainda assim, em certos casos o uso de tais abordagens pode ser factível na prática. O desenvolvimento da estratégia de resolução adequada deve levar em conta a dimensão e complexidade do problema. Os métodos de resolução — cujos fundamentos básicos serão descritos a seguir — terão como base as abordagens baseadas em meta-heurísticas e/ou em modelos de programação linear inteira, além da combinação de ambas as estratégias.

No geral, os algoritmos podem ser classificados como exatos ou aproximados. Algoritmos exatos, tais como técnicas de enumeração do tipo branch-and-bound [3, 9] − garantem encontrar uma solução ótima para qualquer instância de um problema de otimização. Normalmente, utiliza-se modelos de programação linear inteira para tal. Como muitos desses problemas são NP-Difícil [4], os métodos exatos levam um tempo de computação bastante elevado. Como alternativa tem-se a construção de métodos aproximados, também conhecidos como heurísticas, que tem por objetivo conduzir a uma boa solução de um problema, mas que não garante produzir uma solução ótima.

Uma meta-heurística é uma estratégia de busca, não específica para um determinado problema, que tenta explorar eficientemente o espaço das soluções viáveis desse problema [1]. São algoritmos aproximados que incorporam mecanismos para evitar confinamento em mínimos ou máximos locais. Conhecimentos específicos do problema podem ser utilizados na forma de heurística para auxiliar no processo de busca (por exemplo, na busca de um possível bom vizinho de um determinado ponto). Resumindo, pode-se dizer que metaheurísticas são mecanismos de alto nível para explorar espaços de busca, cada uma usando um determinado tipo de estratégia.

Dentre as meta-heurísticas mais utilizadas destacam-se: algoritmos genéticos, programação genética, simulated annealing, colônia de formigas, VNS, ILS, GRASP e busca tabu [2, 6, 7, 8]. Cada método tem sua peculiaridade e uma forma diferente de escape de ótimos locais. O termo matheuristics descreve a integração entre a programação matemática e as meta-heurísticas [5].

Como leitura inicial recomenda-se [10] ou [11-12].

 

  1. Talbi, E. (2009), Metaheuristics: From Design to Implementation, John Wiley & Sons.

  2. Gendreau, M. & Potvin, J.-Y. (2010), Handbook of Metaheuristics, 2nd ed., Springer Publishing Company, Incorporated.

  3. Wolsey, L. A. (1998), Integer Programming, Wiley-Interscience, Series in Discrete Mathematics Optimization.

  4. Garey, M. R.; Johnson, D. S. (1979).  Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Freeman and Co.

  5. Bastos, L., Ochi, L. S., Protti, F., Subramanian, A., Martins, I. C. & Pinheiro, R. G. S. (2016), ‘Efficient algorithms for cluster editing’, Journal of Combinatorial Optimization 31(1), 347–371.

  6. Nogueira, B., Pinheiro, R. G. S. & Subramanian, A. (2018). ‘A hybrid iterated local search heuristic for the maximum weight independent set problem’. Optimization Letters (12), 567-583.

  7. Nogueira, B. & Pinheiro, R. G. S. (2018). ‘A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs’. Computers & Operations Research (90), 232-248.

  8. Nogueira, B. & Pinheiro, R. G. S. . ‘A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems’. To Appear in Annals of Operations Research.

  9. Pinheiro, R.G.S., Martins,I.C., Protti, F., Ochi, L.S., Simonetti, L.G. & Subramanian , A. (2017), ‘On solving manufacturing cell formation via Bicluster Editing’, European Journal of Operational Research 254 (3), 769-779

  10. http://www.decom.ufop.br/prof/marcone/Disciplinas/InteligenciaComputacional/InteligenciaComputacional.pdf

  11. CV Lattes: http://lattes.cnpq.br/6805191874473768

  12. CV Lattes: http://lattes.cnpq.br/1447954471683870