Genetic and Local Search Algorithms as Robust and Simple Optimization Tools
MetaheuristicsPublished 1 January 1996
Mutsunori Yagiura, Toshihide Ibaraki
Citations19
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The results indicate that the performance of GA is not sensitive about crossovers if implemented with mutations, simple implementation of MLS is usually competitive with (or even better than) GA, and GRASP type modification of MLS improves its performance to some extent.
Abstract
One of the attractive features of recent metaheuristics is in its robustness and simplicity. To investigate this direction, the single machine scheduling problem is solved by various genetic algorithms (GA) and random multi-start local search algorithms (MLS), using rather simple definitions of neighbors, mutations and crossovers. The results indicate that: (1) the performance of GA is not sensitive about crossovers if implemented with mutations, (2) simple implementation of MLS is usually competitive with (or even better than) GA, (3) GRASP type modification of MLS improves its performance to some extent, and (4) G A combined with local search is quite effective if longer computational time is allowed.
Keywords
Computer ScienceEngineering
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
Handbook of Genetic Algorithms
7,308 Citations1991Lawrence Davis
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
international conference on Genetic algorithmsA study of permutation crossover operators on the traveling salesman problem
892 Citations1987I. M. Oliver, David J. Smith +1 more
International Joint Conference on Artificial IntelligenceApplying adaptive algorithms to epistatic domains
646 Citations1985Lawrence Davis
New techniques for applying adaptive algorithms to epistatic domains, while retaining some of the strength of Holland's convergence proof are described, for two-dimensional bin-packing problems and graph coloring problems.
Operations ResearchA Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
409 Citations1994Thomas A. Feo, Maurício G. C. Resende +1 more
Computational results indicate that the heuristic frequently finds the optimal or expected optimal solution in a fraction of the time required by implementations of simulated annealing, tabu search, and an exact partial enumeration method.
Parallel ComputingEvolution algorithms in combinatorial optimization
397 Citations1988Heinz Mühlenbein, M. Gorges-Schleuter +1 more
A new genetic algorithm which relies on intelligent evolution of individuals is presented, which is inherently parallel and shows a superlinear speedup in multiprocessor systems.
international conference on Genetic algorithmsA Comparison of Genetic Sequencing Operators.
367 Citations1991Timothy Starkweather, Susan E. McDaniel +3 more
This work compares six sequencing operators that have been developed for use with genetic algorithms and indicates that the eeective-ness of diierent operators is dependent on the problem domain.
Operations Research LettersA new adaptive multi-start technique for combinatorial global optimizations
351 Citations1994Kenneth D. Boese, Andrew B. Kahng +1 more
This work motivates a new adaptive multi-start paradigm for heuristic global optimization, wherein starting points for greedy descent are adaptively derived from the best previously found local minima.
Operations Research LettersA decomposition algorithm for the single machine total tardiness problem
302 Citations1982Chris N. Potts, L. N. Van Wassenhove
The problem of sequencing jobs on a single machine to minimize total tardiness is considered and an algorithm, which decomposes the problem into subproblems which are then solved by dynamic programming when they are sufficiently small.
Operations ResearchA Branch and Bound Algorithm for the Total Weighted Tardiness Problem
276 Citations1985Chris N. Potts, Luk N. Van Wassenhove
This paper presents a new branch and bound algorithm for the single machine total weighted tardiness problem that obtains lower bounds using a Lagrangian relaxation approach with subproblems that are total weighted completion time problems.
Lecture notes in computer scienceGenetic local search algorithms for the traveling salesman problem
220 Citations1991Nico L. J. Ulder, Emile Aarts +3 more
Experimental approaches to Genetic Local Search with 2-Opt neighbourhoods and Lin-Kernighan neighbourhoods are compared with the corresponding classical multi-start Local Search algorithms, as well as with Simulated Annealing and Threshold Accepting.
Foundations of genetic algorithmsSimulated Crossover in Genetic Algorithms
168 Citations1993Gilbert Syswerda
A new class of crossover operator, simulated crossover, is presented that treats the population of a genetic algorithm as a conditional variable to a probability density function that predicts the likelihood of generating samples in the problem space.
Discrete Applied MathematicsGenetic local search in combinatorial optimization
91 Citations1994Antoon Kolen, Erwin Pesch
The most common application of genetic algorithms to combinatorial optimization problems has been restricted to the traveling salesman problem, but some ideas to address this problem are reviewed and some new results are presented.
Computers & Operations ResearchA GRASP™ for a difficult single machine scheduling problem
89 Citations1991Thomas A. Feo, Krishnamurthi Venkatraman +1 more
A greedy randomized adaptive search procedure (GRASP) is presented for an unusually difficult single machine scheduling problem with flow time and earliness penalties and constructs an optimal solution typically within 10 s of CPU time on a personal computer for 58 out of the 60 problems tested with 30 jobs.
Operations ResearchA Greedy Randomized Adaptive Search Procedure for the Two-Partition Problem
75 Citations1994Manuel Laguna, Thomas A. Feo +1 more
A greedy randomized adaptive search procedure (GRASP) for the network 2-partition problem is presented and the ability of GRASP to find optimal solutions is assessed by comparing its performance with a general purpose mixed integer programming package.
European Journal of Operational ResearchA dynamic programming method for single machine scheduling
61 Citations1994Toshihide Ibaraki, Yuichi Nakamura
Computational results on problem instances of up to n = 35 exhibit a clear superiority of this SSDP approach over the original dynamic programming recursion.
IEEJ Transactions on Electronics Information and SystemsOn Genetic Crossover Operators for Sequencing Problems
4 Citations1994Mutsunori Yagiura, Toshihide Ibaraki
A simple criteria for measuring the quality of crossover operators is proposed, and some computational analysis on single machine scheduling problem is added to validate the effectiveness of the proposed criteria.