research-article

Geometric-based sampling for permutation optimization

Authors:

Olivier Regnier-Coudert,

Mayowa AyodeleAuthors Info & Claims

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Pages 399 - 406

https://doi.org/10.1145/2463372.2463422

Published: 06 July 2013 Publication History

Abstract

There exist several operators to search through permutation spaces that can benefit search and score algorithms when combined. This paper presents COMpetitive Mutating Agents (COMMA), an algorithm which uses geometric mutation operators to create a geometrically defined distribution of solutions. Sampling from the distribution generates solutions in a similar fashion as with Estimation of Distribution Algorithms (EDAs). COMMA is applied on classical permutation optimization benchmarks, namely the Quadratic Assignement and the Permutation Flowshop Scheduling Problems and its performance is compared with those of reference EDAs. Although COMMA does not require a model building step, results suggest that it is competitive with state-of-the-art EDAs. In addition, COMMA's underlying geometric-based sampling could be transposed to representations other than permutations.

References

[1]

R. Burkard, S. Karisch, and F. Rendl. QAPLIB -- a quadratic assignment problem library. Journal of Global Optimization, 10(4):391--403, 1997.

Digital Library

[2]

J. Ceberio, E. Irurozki, A. Mendiburu, and J. Lozano. A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems. Progress in Artificial Intelligence, 1:103--117, 2012.

[3]

K. Deep and H. Mebrahtu. Combined mutation operators of genetic algorithm for the travelling salesman problem. International Journal of Combinatorial Optimization Problems and Informatics, 2(3):1--23, 2011.

[4]

E. Dos Santos, E. Hruschka, and N. Ebecken. A distance-based mutation operator for learning bayesian network structures using evolutionary algorithms. Proceedings of the IEEE Congress on Evolutionary Computation, pages 1--8, 2010.

[5]

Z. Drezner, P. Hahn, and É. Taillard. Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Annals of Operations Research, 139(1):65--94, 2005.

[6]

J. Holland. Adaptation in natural and artificial systems. MIT press, 1975.

[7]

M. Jerrum. The complexity of finding minimum-length generator sequences. Theoretical Computer Science, 36:265--289, 1985.

Digital Library

[8]

P. Larra\ naga and J. Lozano. Estimation of distribution algorithms: A new tool for evolutionary computation. Kluwer Academic Publishers, Dordrecht, 2002.

[9]

E. Lawler. The quadratic assignment problem. Management science, 9(4):586--599, 1963.

Digital Library

[10]

A. Mendiburu, J. Lozano, and J. Miguel-Alonso. Parallel implementation of EDAs based on probabilistic graphical models. IEEE Transactions on Evolutionary Computation, 9(4):406--423, 2005.

Digital Library

[11]

A. Misevi\vcius, A. Tomkevi\vcius, and J. Karbauskas. Stagnation-protected tabu search variants for unstructured quadratic assignment problems. Information Technology and Control, 35(4):363--370, 2006.

[12]

A. Moraglio. Towards a Geometric Unification of Evolutionary Algorithms. PhD thesis, University of Essex, 2007.

[13]

G. Onwubolu and D. Davendra. Differential Evolution: A Handbook for Global Permutation-Based Combinatorial Optimization, volume 175. Springer, 2009.

Digital Library

[14]

O. Regnier-Coudert and J. McCall. Competing mutating agents for bayesian network structure learning. Parallel Problem Solving from Nature-PPSN XII, pages 216--225, 2012.

Digital Library

[15]

R. Ruiz and C. Maroto. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2):479--494, 2005.

[16]

M. Serpell and J. Smith. Self-adaptation of mutation operator and probability for permutation representations in genetic algorithms. Evolutionary Computation, 18(3):491--514, 2010.

Digital Library

[17]

E. Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278--285, 1993.

[18]

H. Zhang, X. Li, H. Li, and F. Huang. Particle swarm optimization-based schemes for resource-constrained project scheduling. Automation in Construction, 14(3):393--404, 2005.

Cited By

Byrski AKisiel-Dorohinicki MTusiński N(2017)Extending Estimation of Distribution Algorithms with Agent-Based Computing InspirationsTransactions on Computational Collective Intelligence XXVII10.1007/978-3-319-70647-4_13(191-207)Online publication date: 25-Nov-2017
https://doi.org/10.1007/978-3-319-70647-4_13
Regnier-Coudert OMcCall J(2014)Factoradic Representation for Permutation OptimisationParallel Problem Solving from Nature – PPSN XIII10.1007/978-3-319-10762-2_33(332-341)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10762-2_33

Index Terms

Geometric-based sampling for permutation optimization

Recommendations

Evolutionary algorithms and elliptical copulas applied to continuous optimization problems

Estimation of Distribution Algorithms (EDAs) constitutes a class of evolutionary algorithms that can extract and exploit knowledge acquired throughout the optimization process. The most critical step in the EDAs is the estimation of the joint ...
Sub-structural niching in estimation of distribution algorithms
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

We propose a sub-structural niching method that fully exploits the problem decomposition capability of linkage-learning methods such as the estimation distribution algorithms and concentrate on maintaining diversity at the sub-structural level. The ...
Improved biogeography-based optimisation

Biogeography-based optimisation (BBO) is one of the popular evolutionary algorithms, inspired by the theory of island biogeography. It has been successfully applied in various real world optimisation problems such as image segmentation, data clustering, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

July 2013

1672 pages

ISBN:9781450319638

DOI:10.1145/2463372

Editor:
Christian Blum
IKERBASQUE and University of the Basque Country UPV/EHU, Spain
,
General Chair:
Enrique Alba
University of Malaga, Spain

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '13

Sponsor:

SIGEVO

GECCO '13: Genetic and Evolutionary Computation Conference

July 6 - 10, 2013

Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
100
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Byrski AKisiel-Dorohinicki MTusiński N(2017)Extending Estimation of Distribution Algorithms with Agent-Based Computing InspirationsTransactions on Computational Collective Intelligence XXVII10.1007/978-3-319-70647-4_13(191-207)Online publication date: 25-Nov-2017
https://doi.org/10.1007/978-3-319-70647-4_13
Regnier-Coudert OMcCall J(2014)Factoradic Representation for Permutation OptimisationParallel Problem Solving from Nature – PPSN XIII10.1007/978-3-319-10762-2_33(332-341)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10762-2_33

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten