Busca Local para Otimização Multiobjetivo
José Elias C. Arroyo
Depto de Ciência da Computação, UCAM-Campos,
28040-320, Campos, RJ
E-mail: [email protected]
Vinícius A. Armentano
Depto de Engenharia de Sistemas, FEEC- UNICAMP
Caixa Postal 6101, 13083-970, Campinas, SP
E-mail: [email protected].
Este trabalho propõe um método de busca local
(BLM) para gerar um conjunto de soluções não
dominadas de um problema de otimização multiobjetivo. Este tipo de problema consiste em minimizar ou maximizar simultaneamente várias funções
objetivos. Dado um vetor de r funções objetivos
(f1,..., fr), uma solução x domina y se fi (x) ≤ fi (y), ∀ i
= 1,...,r e fi (x) < fi (y) para pelo menos um i. Uma
solução x* é eficiente (ou Parto-ótima) se não existe
uma solução x tal que x domine x*.
Em otimização multiobjetivo, geralmente, não
existe uma única solução que otimize todos os objetivos. A solução do problema é dada pelo conjunto
de soluções eficientes e a escolha da solução de
melhor compromisso depende das preferências
dadas aos objetivos.
O método proposto é baseado fortemente no
conceito de dominância de Pareto e ele realiza uma
busca em paralelo explorando várias regiões do
espaço de soluções. A busca parte de um conjunto
inicial S de soluções, e a partir de cada solução x
deste conjunto gera-se uma vizinhança N(x).
Constrói-se então um próximo conjunto S’ das
soluções vizinhas não dominadas y∈ ∪ N (x ) . Caso
também é testada em 360 instâncias de grande porte (n =
20, 50, 80 e m =5, 10, 20). Os resultados são comparados
com os resultados obtidos pelo algoritmo genético com
busca local (AGBL) proposto em [2]. AGBL implementa
uma busca local baseada na minimização da combinação
linear ponderada dos objetivos: f = w1f1 +...+ wrfr, onde
Σi wi = 1.
Para as 360 instâncias testadas, os métodos BLM e
AGBL obtiveram, respectivamente, 8116 e 5892 soluções não dominadas.
Testes computacionais foram executados em uma
estação de trabalho SUN Ultra 60. Na Tabela 1,
apresenta-se a média dos tempos computacionais gastos
pelos métodos. Vale ressaltar que, a busca local BLM
explora 6 soluções em paralelo e, para cada solução gerase a vizinhança completa baseado na inserção de tarefas.
BLM
AGBL
n=20
0,533
9,79
n =50
50,33
182,93
n = 80
385,56
733,42
Tabela 1: Tempos computacionais (em segundos).
Os resultados obtidos mostram que o método BLM é
capaz
de gerar, rapidamente, varias soluções dominantes,
x∈S
e apresenta um desempenho superior que o algoritmo
S’ ≠ ∅, o processo se repete a partir deste novo AGBL.
conjunto. Quando o conjunto S’ contém um número
grande de soluções, é aplicado um procedimento de
redução proposto em [4]. Usando esta técnica Referências
selecionam-se soluções representativas para serem
[1] H. Ishibuchi and T. Murata, A multi-objective geneexploradas.
tic local search algorithm and its application to flowA busca local BLM é aplicada ao problema de
shop scheduling. IEEE Trans. on Systems, Man and
programação de tarefas flowshop minimizando dois
Cybernetics-part C: 28 (1998) 392-403.
objetivos: tempo de finalização da programação e o
atraso total em relação às datas de entrega das [2] C.J. Liao, W.C. Yu and C.B. Joe CB, Bicriterion
tarefas. Para o caso de m = 2 máquinas e n = 10, 15,
scheduling in the two-machine flowshop. J Opl Res
20 tarefas, a busca local é comparada com o algoSoc 48 (1997) 929-935.
ritmo Branch-and-Bound (B&B) [3]. De um total de
[3] J.N. Morse, Reducing the size of the nondo-minated
474 soluções eficientes obtidas pelo algoritmo
set: pruning by clustering. Comput Opns Res, 7
B&B, 357 (75,32%) soluções eficientes foram
(1980) 55-66.
obtidas pelo método BLM. A busca local BLM
529