Programação

GRASP e Otimiza¸˜o Global Cont´ ca ınua
Douglas S. Gon¸alves , c Departamento de Matem´tica Aplicada, IMECC, UNICAMP, a 13083-970, Campinas, SP e-mail: [e-mail]

Resumo: Neste trabalho realizamos o estudo da metaheur´ ıstica C-GRASP, ou GRASP cont´ ınuo, e sua aplica¸ao na otimiza¸˜o global de fun¸˜es cont´ c˜ ca co ınuas em caixas. C-GRASP ´ uma extens˜o e a da metaheur´ ıstica GRASP, do dom´ ınio da otimiza¸˜o discreta para o da otimiza¸ao cont´ ca c˜ ınua. Basicamente trata-se de uma heur´ ıstica do tipo busca local com recome¸os (multistart), por´m a c e cada itera¸˜o emprega uma fase de constru¸˜o composta por caracter´ ca ca ısticas gananciosas, adaptativas e aleat´rias, que resultam em solu¸˜es diversificadas e de boa qualidade para a fase de busca o co local. Uma proposta alternativa para a fase local ´ apresentada e o desempenho das heur´ e ısticas comparado sobre um conjunto de problemas teste extra´ ıdos da literatura.
Palavras-chave: GRASP, C-GRASP, Metaheur´ ısticas, Otimiza¸˜o Global ca 1

Introdu¸˜o ca Em muitos problemas de otimiza¸˜o encontrar uma solu¸˜o local ´ suficiente. Por´m em alguns ca ca e e problemas h´ a necessidade de se encontrar o minimizador global. Dentre outras ´reas estes a a problemas aparecem na Economia, na Engenharia Qu´ ımica, etc, [5].
De um modo geral, o problema de otimiza¸˜o global pode ser definido como encontrar x ∈ ca ¯
X ⊂ Rn tal que f (¯) ≤ f (x), ∀x ∈ X. Neste trabalho, consideramos f ∈ C 2 e X definido x por restri¸˜es de canaliza¸˜o nas vari´veis, X = {x ∈ Rn | li ≤ xi ≤ ui , para i = 1, 2, . . . , n}. co ca a Apesar da simplicidade do conjunto vi´vel X, n˜o h´ hip´tese alguma de convexidade sobre f , a a a o e as n˜o convexidades da fun¸˜o podem levar a in´meros m´ a ca u ınimos locais, o que dificulta a busca pelo minimizador global.
Neste trabalho consideramos o estudo do C-GRASP ou, GRASP cont´ ınuo, introduzido