Problema da Diversidade Máxima

Problema da Diversidade Máxima

Definição

O Problema da Diversidade Máxima (PDM), segundo Duarte (2008), é um problema de Otimização Combinatória que tem por objetivo selecionar um número pré-estabelecido de elementos de um dado conjunto de maneira tal que a soma das diversidades entre os elementos selecionados seja a maior possível, ou seja, consiste em selecionar um subconjunto M com m elementos de um conjunto N, onde N = {1,...,n}, de tal forma que a diversidade entre os seus elementos selecionados seja máxima. O PDM é considerado um problema NP-difícil, isto é, não existe algoritmo conhecido que o resolva de forma exata em tempo polinomial e, à medida que o tamanho das instâncias vão se tornando suficientemente grandes, tornam-se impossíveis de serem resolvidas em tempo aceitável.

Algoritmo

Int m ← dimensão da partícula;

Int n ← número de partículas;

Float P [m] [n], P Best [m] ← {);

For i = 0 até Max (1, dimensão da instancia*0.4)

         P [i] ← Heurística_gulosa (i);

         P Best [i] [j] ← Escolhido aleatoriamente;

         Calcula GBest;

End-For

For i = Max (1, dimensão da instancia*0.4) até n-1

          For j=0 até m-1

                 P [i] [j] ← Escolhido aleatoriamente;

                 P Best [i] [j] ← P [i] [j];

          End-For

          Calcula GBest;

End-For

Busca_local (GBest,0);

For k=1 até n-1

       For i=1 até n-1

               For j=1 até m-1

                         Calcula velocidade de V[i] [j]               (Eq. 2);

                         Calcula nova posição de P [i] [j]          (Eq. 1);

               End-For

       End-For

       Calcula diversidade da partícula i;

       Se melhorar diversidade localmente então

                         PBest [i] ← P[i];

       End-Se

       Se melhorar diversidade globalmente então

                         GBest ← P [i];

                         Busca_local (GBest,i);

       End-Se

       Se tempo de processamento > 60 min então

                        Break;

       End-Se

End-For

Return (GBest);

Problema de localização máxima cobertura

Definição

Esse problema busca obter a configuração para localizar facilidades que atenda o maior número de indivíduos de uma população, considerada uma dada distância ou um tempo padrão do ponto de demanda.

Algoritmo

Procedure com base na Substituição de Vértices para o PLMDE

   {inicialização: lê dados e obtém as taxas de chegada}

    calcular fatorQ;

    construir localização Inicial(LocIni);

    rodar Hipercubo; {calcula taxas de ocupação utilizando o modelo Hipercubo}

    calcular cobertura (CobPop);

    MelhorSol = CobPop; {guarda a melhor solução}

    LocAux = LocIni; {guarda a solução corrente para desfazer a troca}

    MelhorLoc = LocIni; {guarda melhor localização}

    While (Condição de parada = false) do

        i=0

      While (i < NumÁreasDeDemanda) do

            i = i+1;

             For índice = 1 to NumServidores do

                   iEntra = i;

...