An Evolutionary Algorithm With Guided Mutation for the Maximum Clique Problem
- 4 April 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 9 (2), 192-200
- https://doi.org/10.1109/tevc.2004.840835
Abstract
Estimation of distribution algorithms sample new solutions (offspring) from a probability model which characterizes the distribution of promising solutions in the search space at each generation. The location information of solutions found so far (i.e., the actual positions of these solutions in the search space) is not directly used for generating offspring in most existing estimation of distribution algorithms. This paper introduces a new operator, called guided mutation. Guided mutation generates offspring through combination of global statistical information and the location information of solutions found so far. An evolutionary algorithm with guided mutation (EA/G) for the maximum clique problem is proposed in this paper. Besides guided mutation, EA/G adopts a strategy for searching different search areas in different search phases. Marchiori's heuristic is applied to each new solution to produce a maximal clique in EA/G. Experimental results show that EA/G outperforms the heuristic genetic algorithm of Marchiori (the best evolutionary algorithm reported so far) and a MIMIC algorithm on DIMACS benchmark graphs.Keywords
This publication has 20 references indexed in Scilit:
- On Stability of Fixed Points of Limit Models of Univariate Marginal Distribution Algorithm and Factorized Distribution AlgorithmIEEE Transactions on Evolutionary Computation, 2004
- A study of drift analysis for estimating computation time of evolutionary algorithmsNatural Computing, 2004
- Towards an analytic framework for analysing the computation time of evolutionary algorithmsArtificial Intelligence, 2003
- From an individual to a population: an analysis of the first hitting time of population-based evolutionary algorithmsIEEE Transactions on Evolutionary Computation, 2002
- Annealed replication: a new heuristic for the maximum clique problemDiscrete Applied Mathematics, 2002
- Reactive Local Search for the Maximum Clique Problem1Algorithmica, 2001
- The compact genetic algorithmIEEE Transactions on Evolutionary Computation, 1999
- Tabu SearchPublished by Springer Science and Business Media LLC ,1998
- A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problemsJournal of the Operational Research Society, 1997
- HEURISTICS FOR INTEGER PROGRAMMING USING SURROGATE CONSTRAINTSDecision Sciences, 1977