A Memetic Algorithm Instantiated with Selection Sort Consistently Finds Global Optima for the Error-Correcting Graph Isomorphism
View/ Open
Author(s)
Torres-Velazquez, R
Estivill-Castro, V
Griffith University Author(s)
Year published
2002
Metadata
Show full item recordAbstract
We study several tested cases of the error-correcting graph isomorphism problem. The set Sn of n! permutations on n items is the search space for this optimization problem. We apply MA-sorting. This is a memetic algorithm with domain-independent mutation operators based on classical sorting. Each sorting algorithm works on results to a comparison predicate and defines a path in SI.,. In MA-sorting the mutation operator is a local-search that evaluates permutations suggested by the sorting algorithm. When such evaluation results in an improvement, the mutation is accepted and the comparison operator of the sorting algorithm ...
View more >We study several tested cases of the error-correcting graph isomorphism problem. The set Sn of n! permutations on n items is the search space for this optimization problem. We apply MA-sorting. This is a memetic algorithm with domain-independent mutation operators based on classical sorting. Each sorting algorithm works on results to a comparison predicate and defines a path in SI.,. In MA-sorting the mutation operator is a local-search that evaluates permutations suggested by the sorting algorithm. When such evaluation results in an improvement, the mutation is accepted and the comparison operator of the sorting algorithm evaluates to true. In contrast with previous proposals, our MA-sorting instantiated with selection sort finds optimal solutions for this case study.
View less >
View more >We study several tested cases of the error-correcting graph isomorphism problem. The set Sn of n! permutations on n items is the search space for this optimization problem. We apply MA-sorting. This is a memetic algorithm with domain-independent mutation operators based on classical sorting. Each sorting algorithm works on results to a comparison predicate and defines a path in SI.,. In MA-sorting the mutation operator is a local-search that evaluates permutations suggested by the sorting algorithm. When such evaluation results in an improvement, the mutation is accepted and the comparison operator of the sorting algorithm evaluates to true. In contrast with previous proposals, our MA-sorting instantiated with selection sort finds optimal solutions for this case study.
View less >
Conference Title
CEC'02: PROCEEDINGS OF THE 2002 CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1 AND 2
Volume
2
Publisher URI
Copyright Statement
© 2002 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.