@incollection{BinOli02a, author = "S. Binato and G.C. Oliveira", title = "A {Reactive GRASP} for transmission network expansion planning", booktitle = "Essays and surveys in metaheuristics", editor = "C.C. Ribeiro and P. Hansen", publisher = "Kluwer Academic Publishers", year = "2002", pages = "81--100", annote = "The {GRASP} previously proposed by Binato, Oliveira, and Ara\'ujo (1998) for solving a transmission network expansion problem is enhanced with the reactive scheme of Prais and Ribeiro (2000) to self-adjust the {GRASP} RCL parameter $\alpha$. They also propose to apply a bias distribution function of Bresina (1996) to bias the random greedy construction phase towards the most promising variables." } @inproceedings{Bre96a, author = "J.L. Bresina", title = "Heuristic-biased stochastic sampling", booktitle = "Proceedings of the AAAI-96", year = "1996", pages = "271--278", annote = "This paper presents a generalization of iterative sampling called Heuristic-Biased Stochastic Sampling (HBSS). The two search techniques have the same overall control structure. The difference lies in how a choice is made at each decision point. HBSS uses a given search heuristic to focus its exploration. The degree of focusing is determined by a chosen {\em bias function} that reflects the confidence one has in the heuristic's accuracy. This methodology can be directly applied in a {GRASP} construction phase, by biasing the selection of RCL elements to favor those with higher greedy function values.", } @Article{CanResRib01a, author = "S.A. Canuto and M.G.C. Resende and C.C. Ribeiro", title = "Local search with perturbation for the prize-collecting {Steiner} tree problems in graphs", journal = "Networks", volume = "38", pages = "50--58", year = "2001", annote = "Several local search strategies have been investiged in this paper for solving the prize-collecting {Steiner} tree problems in graphs, including path relinking, VNS, and a {GRASP} that uses some cost perturbations. The greedy choice takes into account the input edge weights, while the local search routine defines as neighborhood of a solution $T(X)$ the set of all minimum spanning trees $T(X')$, where $X'$ differs from $X$ for exactly one node.", } @phdthesis{Pra00a, author = "M. Prais", title = "Estrat\'egias de varia\c{c}\~ao de par\^ametros em procedimentos {GRASP} e aplica\c{c}\~oes", school = "Department of Computer Science, Catholic University of Rio de Janeiro", address = "Rio de Janeiro, Brazil", year = "2000", annote = "This thesis describes a {GRASP} for a matrix decomposition problem in {TDMA} traffic assignment. It proposes Reactive {GRASP}, a refinement of {GRASP} where the RCL parameter is adjusted dynamically to favor values that produce good solutions. Reactive {GRASP} is compared with other RCL strategies on matrix decomposition, set covering, maximum satisfiability and graph planarization." } @Article{PraRib00b, author = "M. Prais and C.C. Ribeiro", title = "Varia\c{c}\~ao de par\^ametros em procedimentos {GRASP}", journal = "Investigaci\'on Operativa", volume = "9", year = "2000", pages = "1--20", annote = "The {GRASP} RCL parameter $\alpha$ that determines the size of the restricted candidate list can be adjusted, leading to different behavior of the {GRASP} implementation. This paper investigates four strategies for the variation of the parameter $\alpha$: 1) reactive -- $\alpha$ is self-adjusted along the iterations; 2) uniform -- $\alpha$ is randomly chosen from a discrete uniform probability distribution; 3) hybrid -- $\alpha$ is randomly chosen from a fixed probability distribution concentrated around the value corresponding to the purely greedy choice; 4) fixed -- $\alpha$ has a fixed value close to the purely greedy choice. The reactive strategy is the most flexible and adherent to the characteristics of the specific problem to be solved. In Portuguese.", } @Article{RanAbrBoa00a, author = "M.C. Rangel and N.M.M. Abreu and P.O. {Boaventura Netto}", title = "{GRASP} para o {PQA}: {U}m limite de aceita\c{c}\~{a}o para solu\c{c}\~{o}es iniciais", journal = "Pesquisa Operacional", volume = "20", year = "2000", pages = "45--58", annote = "This paper presents a modified version of the {GRASP} algorithm proposed by Li, Pardalos, and Resende (1994) for the quadratic assignment problem. The new {GRASP} uses a criterion to accept or reject a given initial solution, thus trying to avoid searches that eventually can be fruitless. It computes a normalized limit cost, defined with the aid of {QAP} upper and lower bounds easily obtained and discards all solutions with cost less than the computed limit. In Portuguese.", } @Article{RibUchWer02a, author = "C.C. Ribeiro and E. Uchoa and R.F. Werneck", title = "A hybrid {GRASP} with perturbations for the {Steiner} problem in graphs", journal = "INFORMS Journal on Computing", volume = "14", pages = "228--246", year = "2002", annote = "In this hybrid {GRASP} here proposed for the {Steiner} problem in graphs, the {GRASP} construction phase is replaced by either one of several different construction procedures that apply weight perturbation strategies combining intensification and diversification elements. The local search phase circularly explores two different strategies. The first defines a simple node-based neighborhood structure. The second one uses a key-path-based neighborhood, where a key-node is a {Steiner} node with degree at least three and a key-path is a {Steiner} tree $T$ whose extremities are either terminals of key-node (if there are any, intermediate nodes are {Steiner} node with degree two in $T$). An adaptive path-relinking procedure is at the end used as a post-optimization strategy.", } @Article{FleGlo99a, author = "C. Fleurent and F. Glover", title = "Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory", journal = "INFORMS Journal on Computing", volume = "11", year = "1999", pages = "198--204", annote = "Adaptive memory strategies that are the heart of tabu search methods are shown to be a foundation for alternative, enhanced, multistart approaches. This paper illustrates that constructive multistart methods, such as Random Restart and {GRASP}, can be improved by the addition of memory and associated heuristic search principles. The improved results indicate that these principles (learning, intensification, candidate list strategies, POP) are not limited to applications with transition neighborhoods, as in local search, but can also be useful for applications characterized by constructive (and destructive) neighborhoods. The paper shows that the {GRASP} for QAP of Li, Pardalos, and Resende (1994) can be improved upon by using these memory strategies. Study of alternatives to memoryless multistart approaches like {GRASP} is conducted for the quadratic assignment problem. Adaptive memory strategies retain and analyze features of selected solutions in order to provide a basis for improving future executions of the constructive process. The authors show that the most effective strategies are tabu search methods, which use memory in both improving and constructive phases.", }