MB-244 - PRINCÍPIOS DA PESQUISA OPERACIONAL
LISTA DE EXERCÍCIOS 12
1. A função de teste Booth é utilizada para teste de metaheurísticas, sendo definida
por: Max Z=(x1 + 2x2 - 7)2 + (2x2 + x2 -5)2 , S.A. -10 ≤ x1 ≤ 10, -10 ≤ x2 ≤ 10.
a) Iniciando a busca na solução x = (-10, -10), identifique a solução ótima
aproximada utilizando a Busca Tabu (Tmax = 3 e Btmax = 3)
b) Iniciando a busca na solução x = (-10,-10), identifique a solução ótima
aproximada utilizando o Simulated Annealing (Temperatura inicial = 10, =0,5).
Para geração dos números aleatórios faça: aleatório = (segundo corrente / 60)
2. Comente as afirmações:
a. Um método de resolução não-exato é aquele que pode gerar uma solução com
erro, dentro de uma margem.
b. Os métodos evolutivos são baseados nos mecanismos de seleção natural pois
seguem o princípio da sobrevivência do mais apto.
c. Os operadores de crossover e a mutação são os principais mecanismos de busca
dos AGs para explorar regiões desconhecidas do espaço de busca.
d. O objetivo de fazer mutação das soluções é aumentar a diversidade.
e. A Busca Tabu tenta evitar antecipadamente o perigo de ficar preso em ótimos
locais ao incorporar uma estrutura de memória que proíbe ou penaliza certos
movimentos que poderiam retornar a uma solução visitada recentemente.
f. A estratégia evolutiva é baseada na mutação da população de soluções.
g. Na estratégia evolutiva faz-se busca local gerando-se mutações de baixa
variância.
3. Seja o Problema de Programação Inteira (PPI):
Minimizar Z = 3x1 + 4x2 + 7x3 + 5x4
S.A.
x1 + 1,5x2 + 2,5x3 + 2x4 ≥ 5
xi ≥ 0 e inteiro, i=1,...,4
a) Construa a função penalidade do problema (M=10)
b) A solução x = (0,0,2,0) é um ótimo local?
c) Partindo da solução x = (0,0,0,0) faça uma busca local (mudança entre
vizinhanças até encontrar a solução ótima)
4. (Simulated Annealing) Qual a probabilidade de se aceitarem os seguintes
movimentos em um problema de maximização?
5. (Simulated Annealing) Avalie as probabilidades de se aceitar movimentos ruins no
simulated annealing quando Temperatura ϵ {10 ; 30 ; 50 ; 70 ; 90} e F.O. ϵ {10 ;
40 ; 70 ; 100 ; 130}. Crie um gráfico com todas as probabilidades encontradas.
6. (Algoritmos Genéticos) Identifique o valor dos seguintes números binários:
a) (101)b
b) (01101)b
c) (100110101)b
7. (Algoritmos Genéticos) Considere, em um problema de minimização, uma
população de 6 cromossomos com aptidões 3, 5, 8, 9, 11 e 12. Calcule o número
esperado de descendentes de cada um dos 6 cromossomos, considerando que a
população na próxima geração se mantenha. Avalie também o número esperado de
descendentes caso a população aumente para 10 cromossomos.
8. Seja o Problema de Programação Inteira (PPI):
Maximizar Z = 12x1 + 7x2 + 9x3 + 8x4
S.A.
3x1 + x2 + x3 + x4 ≤ 3
x1 + x4 ≤ 1
xi ϵ [0,1], i=1,...,4
a) Construa a função penalidade do problema (M=10)
b) Iniciando a busca na solução x = (1,0,0,0), identifique a solução ótima
aproximada utilizando a Busca Tabu (Tmax = 2 e Btmax = 2)
c) Aplique o Path-Relinking entre as soluções x = (1,0,0,0) e x = (0,1,1,0). Foi
possível encontrar uma solução melhorada?
d) Iniciando a busca na solução x = (1,0,0,0), identifique a solução ótima
aproximada utilizando o Simulated Annealing (Temperatura inicial = 12, =0,5).
Para geração dos números aleatórios faça: aleatório = (segundo corrente / 60)
e) Identifique um solução ótima aproximada utilizando algoritmo genético tendo
como população inicial {(0,0,1,0),(0,0,0,1),(0,1,1,0),(1,0,0,0)}. Construa e avalie
cada membro da próxima geração fazendo crossover entre 2 soluções (a melhor com
a pior e entre as 2 soluções intermediárias) e identifique os pontos de crossover por
Arredondamento{0,5+4*(segundo corrente / 60)}.
f) Avalie os resultados encontrados pelos métodos empregados e o esforço
necessário. Qual sua recomendação?