Heurísticas para a AGM Multi-Objetivo

Entre os anos de 2004 e 2006 eu trabalhei, sob orientação da professora Elizabeth Ferreira Gouvêa Goldbarg e sob financiamento do CNPQ (bolsista PIBIC-Balcão), em um projeto de iniciação científica para estudar e desenvolver algoritmos para o problema da Arvore Geradora Mínima Multi-Objetivo (também conhecida como Árvore Geradora Mínima com Múltiplos Objetivos e Árvore Geradora Mínima Multi-Critério, daqui em diante abreviada para AGM-MO), intitulado Algoritmos heurísticos para o problema da Árvore Geradora Mínima Multi-Objetivo (AGM-MO). Quando comecei eu não tinha conhecimento algum sobre o assunto (nem otimização combinatória, nem multi-objetivo, nem heurísticas ou meta-heurísticas), então boa parte da minha pesquisa envolveu revisão de literatura e o estudo destes tópicos.

Minha intenção, com essa página, é criar um ponto de referência para aqueles que se interessam pelo assunto, seja otimização multi-objetivo ou especificamente o problema da AGM-MO. Vou disponibilizar alguns trabalhos que escrevi sobre o assunto, algumas boas referências de artigos (inclusive em BibTeX) e sites que encontrei em minhas revisões, alguns algoritmos de outras pessoas que implementei e os algoritmos que eu mesmo desenvolvi para o problema.

Gostaria de fazer com que os textos deste site fossem os mais claros e compreensíveis, na medida do possível (infelizmente, se você não é da área nem nunca ouviu falar de nada disso, só vai conseguir entender tudo até certo ponto). Desse modo, tentei fazer explicações básicas sobre todos os assuntos que menciono, para que o maior número de pessoas possa compreender de que trata toda esta pesquisa. Claro que, se você já é pesquisador da área, pode pular isso tudo e ir direto ao ponto: os algoritmos desenvolvidos (e seus resultados) ou as referências bibliográficas. Se nunca ouviu falar de nada disso, sugiro que inicie pelo primeiro ponto. Não tenha medo, fiz o máximo para os textos não ficarem chatos ou maçantes, coloquei o máximo de exemplos e aplicações possível.

  1. Introdução a teoria dos grafos
  2. O problema da árvore geradora mínima (AGM)
  3. Introdução a otimização combinatória
  4. Otimização combinatória multi-objetivo
  5. O problema da árvore geradora mínima multi-objetivo (AGM-MO)
    1. Revisão da literatura
    2. Instâncias de teste
    3. Algoritmos desenvolvidos na pesquisa
      1. Heurística construtiva randomizada: rmc-Kruskal
      2. Busca tabu
      3. Algoritmo memético
      4. Algoritmo transgenético

Trabalhos publicados/apresentados

Abaixo alguns artigos e apresentações que fiz sobre o tema durante minha pesquisa. Ainda faltam adicionar alguns trabalhos.

  • Apresentação para a CIENTEC/2006 (04/10/2006): apresentei meu trabalho na feira de ciências da UFRN no dia 04/10/2006. A apresentação está em formato PDF.
  • Relatório anual do CNPQ (2006): Relatório falando sobre minha pesquisa, enviado ao CNPQ. Já contém a descriçao do memético e alguns resultados, mas ainda não inclui os resultados do transgenético.
  • Relatório anual do CNPQ (2005): Relatório falando sobre minha pesquisa, enviado ao CNPQ. Contém apenas alguns detalhes iniciais, revisão bibliográfica e a implementação do algoritmo de Zhou e Gen.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.