Problema da Diversidade Máxima
Por: Mariana Rodrigues • 20/5/2018 • Trabalho acadêmico • 1.362 Palavras (6 Páginas) • 165 Visualizações
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;
...