Guilherme A. Derenievicz
Professor Adjunto
Departamento de Informática
Universidade Federal do Paraná
Pesquisa
Temas de Interesse
|
Diversas áreas das ciências modelam problemas utilizando restrições, que são parcelas de conhecimento que reduzem o espaço de possibilidaddes no mundo real. Estes problemas, denominados problemas de satisfação de restrições (CSPs) consistem em encontrar uma atribuição de valores a um conjunto de variáveis de forma a satisfazer o conjunto de restrições. Técnicas de processamento de restrições são então aplicadas a esses problemas, classificadas em dois principais grupos: busca e inferência. Satisfatibilidade booleana, coloração de grafos, sistemas lineares e o problema das 8 rainhas são exemplos de CSPs. Nesta linha de pesquisa, foca-se principalmente nas técnicas, algoritmos e estruturas de dados que podem ser aplicados na resolução de CSPs. Algumas técnicas de interesse são: busca heurística, retrocesso (backtracking), inferência, consistências locais, aprendizado de restrições, retrocesso não-cronológico, decomposição estrutural, entre outras. |
|
A aritmética intervalar foi proposta na década de 1960 como uma abordagem formal à análise de propagação de erros de arredondamento em sistemas computacionais. Ao representar valores reais por intervalos de precisão bem determinada, a aritmética intervalar caracteriza-se como uma extensão da aritmética convencional, definindo operações intervalares que são utilizadas em diversos métodos intervalares. A análise intervalar vem sendo aplicada em áreas como a robótica, redes neurais, mecânica quântica, sistemas temporais e, de forma mais geral, utilizada como forma de representação e processamento de problemas de satisfação de restrições numéricas e de otimização numérica. Nesta linha de pesquisa, foca-se no estudo das propriedades da aritmética intervalar e de métodos intervalares. Também é de interesse a implementação e aplicação de tais métodos, principalmente em CSPs e problemas de otimização, incluindo técnicas de consitência interval, branch and bound intervalar, entre outros. |
|
Problemas de otimização aparecem em diversas áreas do conhecimento. Em tais problemas, deseja-se encontrar a melhor solução de acordo com um objetivo, satisfazendo um conjunto de restrições. As características da função objetivo e do conjunto de restrições identificam classes de problemas de otimização: programação linear, programação não-linear, programação inteira, otimização combinatória, otimização restrita, etc. Diversas técnicas podem ser empregadas para resolver um problema de otimização: métodos iterativos, métodos exatos, métodos heurísticos e meta-heurísticos, métodos intervalares, entre outros. Nesta linha de pesquisa, foca-se principalmente nas técnicas e métodos de otimização provenientes da comunidade de inteligência artificial, tais como métodos heurísticos, processamento de restriçes, inferência, aprendizado, etc, e em métodos intervalares. Também é de interesse o estudo de técnicas de decomposição de problemas. |
|
A inteligência artificial (IA) busca abordar problemas que não possuem solução algorítmica viável pela computação convencional. Diversas técnicas e classes de algoritmos são utilizados para esse fim, como busca heurística, planejamento, aprendizado de máquina, inferência lógica, processamento de restrições, algoritmos bio-inspirados, representação de conhecimento, entre outros. Em particular, muitas técnicas da IA podem ser aplicadas no contexto de problemas de otimização, tais como algoritmos bio-inspirados, aprendizado, processamento de restrições e heurísticas. Além das técnicas aplicáveis a problemas de otimização, nesta linha de pesquisa foca-se também nos métodos e problemas da chamada IA clássica (símbolica), incluindo: satisfatibilidade booleana, CSP, planejamento, provas de teoremas, métodos formais, busca heurística, entre outros. |
Projetos Atuais
Processamento de restrições e técnicas de decomposição aplicados a problemas de otimização
Uma decomposição epífita é uma decomposição estrutural de instâncias de problemas de otimização que identifica uma combinação de consistências locais (consistência de arco generalizada e consistência relacional) como uma condição suficiente para busca sem retrocesso. Embora seja um forte resultado teórico, alcançar a consistência relacional é, em geral, um problema intratável. Nesse contexto, foram propostos os otimizadores não-lineares OGRe (Otimização Global Relaxada) e InDE (Interval Differential Evolution), o primeiro baseado em um algoritmo de Branch and Bound intervalar que busca alcançar essa consistência de forma aproximada, relaxando algumas restrições do problema, e o segundo integrando análise intervalar e a decomposição epífita em um algoritmo evolutivo (Evolução Diferencial). Embora ambos os métodos utilizem técnicas de decomposição estrutural e de processamento de restrições, são métodos com abordagens distintas. A proposta de otimizadores livres, de códigos-fonte abertos, baseados em estratégias recentes e com diferentes abordagens, e que vêm sendo aplicadas no cenário de otimização é de grande relevância em um ambiente no qual os principais otimizadores são fechados, pagos e pouco acessíveis. O objetivo desta pesquisa é analisar, propor e implementar técnicas de processamento de restrições e estratégias de decomposição estrutural aplicados a problemas de otimização contínuos, discretos e mistos, integrando estas técnicas em diversos algoritmos e estratégias usualmente aplicados em problemas de otimização. Este projeto contempla um período de 60 meses e espera-se, como resultados, a formação profissional de alunos de graduação e pós-graduação, a divulgação científica dos resultados em eventos e periódicos relevantes e a obtenção de algoritmos e otimizadores de códigos-fonte abertos para otimização contínua, inteira e mista.
Se você tem interesse em algum dos temas de pesquisa ou algum projeto de pesquisa atual, ou tem alguma outra proposta de pesquisa em áreas relacionadas (por exemplo: teoria da computação, algoritmos e estrutura de dados, métodos numéricos) e busca orientação (mestrado, iniciação científica ou trabalho de conclusão de curso) me envie um e-mail.
Co-orientações
|
Mariane Regina Sponchiado Cassenote (em andamento) Hiper-heurísticas para Otimização Global. Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática. (co-orientação de doutorado). |
|
Mariane Regina Sponchiado Cassenote (2019) Evolução diferencial intervalar: uma abordagem baseada em decomposição estrutural de problemas de otimização global. Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática. [URI] (co-orientação de mestrado).
Algoritmos de Evolução Diferencial (DE) têm se mostrado promissores para abordagem de problemas de otimização numérica global com restrições. Muitas variantes recentes de DE são aplicadas a otimização caixa-preta, em que a estrutura analítica da instância é desconhecida. Neste trabalho é apresentado um algoritmo InDE (do inglês Interval Differential Evolution), que explora as informações de uma decomposição estrutural da instância durante o processo de otimização. As restrições e a função objetivo da instância são decompostas em operadores e variáveis originais e auxiliares. Então, a estrutura da instância é codificada em um hipergrafo cujas arestas representam os operadores e vértices representam as variáveis. Uma decomposição Epífita é aplicada sobre o hipergrafo, permitindo que um subconjunto de variáveis críticas seja extraído. Os operadores evolutivos intervalares do InDE são aplicados somente sobre esse subconjunto de variáveis, atribuindo a cada variável um intervalo de valores reais. Os intervalos das demais variáveis da instância são dados por propagação através do hipergrafo de restrições. O otimizador implementado utiliza diversas abordagens adaptativas estado-da-arte em otimização baseada em meta-heurísticas. Os experimentos indicam que a utilização de informação estrutural melhora significativamente o desempenho do algoritmo DE. |
Grupos de Pesquisa
|
Laboratório de Inteligência Artificial e Métodos Formais - LIAMFLocalizado no Departamento de Informática da UFPR, o LIAMF foi criado em 1995 com o objetivo de desenvolver pesquisa básica e aplicada em temas da Inteligência Artificial Clássica, como Lógica, Representação de Conhecimento, Planejamento, Busca Heurística, Provadores de Teoremas, Métodos Formais e Sistemas Tutores Inteligentes. Atualmente, desenvolvemos pesquisa também em Programação por Restrições, Otimização, Processamento de Linguagem Natural e Aprendizado de Máquina. |
|
Grupo de Inteligência Artificial e Algoritmos - GIAALocalizado no Departamento de Informática e Estatística da UFSC, o GIAA agrega seus pesquisadores em torno de uma temática comum: problemas complexos. Os avanços tecnológicos presenciados nos últimos anos e as problemáticas decorrentes da integração destas tecnologias ressaltam a necessidade de desenvolver soluções robustas e adaptáveis. Desenvolvemos pesquisa básica e aplicada em Representação de Conhecimento e Raciocínio, Sistemas Multiagentes, Teoria da Computação, Algoritmos de Otimização, Reconhecimento de Padrões, Visão Computacional e Computação Quântica. |
