• O objetivo do Trabalho 1e é a implementação de uma metaeurística ( um algoritmo que busca encontrar "boas" soluções para um problema onde encontrar a solução ótima pode demandar um tempo excessivo para a aplicação desejada).
  
  A metaeurística no caso deste trabalho é a GRASP ("Greedy Randomized Adaptive Search Procedure").
  
  A apresentação do seu algoritmo deve conter uma descrição de cada um dos elementos em uma GRASP, são eles:
  • Uma heurística gulosa que constrói uma solução sequencialmente;
    
    
  • Uma forma de se aleatorizar essa heurística gulosa (em problemas onde o peso dos seus elementos definem o critério guloso, uma forma é adicionar "perturbações" aos valores dos elementos de modo a alterar sua ordenação). É importante que seja possível controlar o "nível" de aleatoriazação;
    
    
  • Uma busca local, isto é, um procedimento onde a cada iteração a solução corrente é trocada pela solução vizinha de melhor valor, até que não exista uma solução vizinha com valor melhor do que a solução corrente. (aqui você deve definir sua vizinhança).
    
    
  • A metaeurística GRASP consiste em repetir, quantas vezes quanto o tempo adequado permitir, a construção gulosa (aleatorizada) de uma solução e uma aplicação subsequente de uma busca local.
  
  
• O problema sobre o qual deve-se aplicar a metaeurística GRASP segue:
  
  
  • Problema do Corte Máximo (MAX-CUT): Dado um grafo G=(V,E) e os pesos w_e ³ 0 associados às arestas em E, encontrar um conjunto X Ì V, tal que o valor do corte definido por X: å_{(i,j)| i Î X, j Î V-X}w_(i,j), seja máximo.
    
    
  • Utilize as operações abaixo para obter uma busca local eficiente :
    1. Dado um conjunto X Ì V, encontrar o valor do corte definido por X: å_{(i,j)| i Î X j Î V-X}w_(i,j). Isto é, a soma dos pesos associados às arestas com uma extremidade em X e outra em V-X.
    2. Calcular o novo valor de um corte quando um vértice, j, é retirado do conjunto X. A complexidade deve ser O(n). Explique por que essa operação é W (n). Mostre como seria o caso para a inclusão de um vértice, k, em X.
    3. Obter o vértice cuja retirada ou inclusão no conjunto X impõe a maior redução sobre o valor do corte. Qual a complexidade dessa operação ?
    4. Dado que as variações estão disponíveis, antes da retirada de um dado vértice, proponha um algoritmo O(n) para determinar as variações (para todos os vértices) após a retirada ou a inclusão de um vértice v.
    5. Proponha um algoritmo para fazer a inversão, isto é, retirada quando está em X e inclusão quando não está, sucessiva de todos elementos em X, a cada iteração inverte-se sempre o vértice que corresponde à maior redução (ou menor aumento, caso não seja possível uma redução). O algoritmo deve executar em O(n²).
  
  Utilize como tempo de CPU máximo 10 minutos, faça com que seu algoritmo imprima a melhor solução encontrada até então.
  
  Utilize como instâncias os grafos no link "Dados Max-Cut" na URL http://www-di.inf.puc-rio.br/~poggi//aalg022.html . (Estes grafos podem ser transformados numa matriz |V| × |V| simétrica.) Obs.: A instância com |V|=50 já deve ser difícil de ser resolvida exatamente.

This document was translated from L^AT_EX by H^EV^EA.