Ant Colony Optimization and Constraint Programming www.it-ebooks.info Ant Colony Optimization and Constraint Programming Christine Solnon Series Editor Narendra Jussien www.it-ebooks.info First published 2010 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Adapted and updated from Optimisation par colonies de fourmis published 2008 in France by Hermes Science/Lavoisier © LAVOISIER 2008 Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address: ISTE Ltd John Wiley & Sons, Inc. 27-37 St George’s Road 111 River Street London SW19 4EU Hoboken, NJ 07030 UK USA www.iste.co.uk www.wiley.com © ISTE Ltd 2010 The rights of Christine Solnon to be identified as the author of this work have been asserted by her in accordance with the Copyright, Designs and Patents Act 1988. Library of Congress Cataloging-in-Publication Data Solnon, Christine. [Optimisation par colonies de fourmis. English] Ant colony optimization and constraint programming / Christine Solnon. p. cm. Includes bibliographical references and index. ISBN 978-1-84821-130-8 1. Constraint programming (Computer science) 2. Mathematical optimization. 3. Swarm intelligence. 4. Ant algorithms. I. Title. QA76.612.S6513 2010 005.1'16--dc22 2009050443 British Library Cataloguing-in-Publication Data A CIP record for this book is available from the British Library ISBN 978-1-84821-130-8 Printed and bound in Great Britain by CPI Antony Rowe, Chippenham and Eastbourne www.it-ebooks.info Table of Contents Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii Chapter1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1. Overviewofthebook . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1. Constraintprogramming . . . . . . . . . . . . . . . . . . 3 1.1.2. Antcolonyoptimization . . . . . . . . . . . . . . . . . . 4 1.1.3. Constraintprogrammingwithantcolonyoptimization . 4 Chapter2.ComputationalComplexity . . . . . . . . . . . . . . . . 7 2.1. Complexityofanalgorithm . . . . . . . . . . . . . . . . . . . 8 2.2. Complexityofaproblem . . . . . . . . . . . . . . . . . . . . . 10 2.2.1. TheP class . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.2. TheNP class . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.3. NP-completeproblems . . . . . . . . . . . . . . . . . . 12 2.2.4. NP-hardproblems . . . . . . . . . . . . . . . . . . . . . 14 2.2.5. Undecidableproblems . . . . . . . . . . . . . . . . . . . 14 2.2.6. Complexityofoptimizationproblems . . . . . . . . . . 15 2.3. Wherethemostdifficultinstancescanbefound . . . . . . . . 15 2.3.1. Phasetransition . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.2. Searchlandscape . . . . . . . . . . . . . . . . . . . . . . 19 2.4. SolvingNP-hardproblemsinpractice . . . . . . . . . . . . . 21 2.4.1. Exploitationofparticularcases . . . . . . . . . . . . . . 23 2.4.2. Approximationalgorithms . . . . . . . . . . . . . . . . . 23 2.4.3. Heuristicsandmetaheuristics . . . . . . . . . . . . . . . 24 2.4.4. Structuringandfilteringthesearchspace . . . . . . . . 24 v www.it-ebooks.info vi ACOandCP PARTI.CONSTRAINTPROGRAMMING . . . . . . . . . . . . . . . . 27 IntroductiontoPartI . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Chapter3.ConstraintSatisfactionProblems . . . . . . . . . . . . . 31 3.1. Whatisaconstraint? . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.1. Definitionofaconstraint. . . . . . . . . . . . . . . . . . 32 3.1.2. Arityofaconstraintandglobalconstraints . . . . . . . 33 3.2. Whatisaconstraintsatisfactionproblem? . . . . . . . . . . . 33 3.2.1. ComplexityofCSPs . . . . . . . . . . . . . . . . . . . . 34 3.3. OptimizationproblemsrelatedtoCSPs . . . . . . . . . . . . . 35 3.3.1. Maximizingconstraintsatisfaction . . . . . . . . . . . . 35 3.3.2. Constrainedoptimization . . . . . . . . . . . . . . . . . 36 3.4. Then-queensproblem . . . . . . . . . . . . . . . . . . . . . . 37 3.4.1. Descriptionoftheproblem . . . . . . . . . . . . . . . . 37 3.4.2. FirstCSPmodel . . . . . . . . . . . . . . . . . . . . . . 38 3.4.3. SecondCSPmodel . . . . . . . . . . . . . . . . . . . . . 39 3.4.4. ThirdCSPmodel . . . . . . . . . . . . . . . . . . . . . . 40 3.4.5. Influenceofthemodelonthesolutionprocess . . . . . 41 3.5. Thestablemarriageproblem . . . . . . . . . . . . . . . . . . . 43 3.5.1. Descriptionoftheproblem . . . . . . . . . . . . . . . . 43 3.5.2. CSPmodel . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.6. RandomlygeneratedbinaryCSPs . . . . . . . . . . . . . . . . 46 3.7. Thecarsequencingproblem . . . . . . . . . . . . . . . . . . . 47 3.7.1. Descriptionoftheproblem . . . . . . . . . . . . . . . . 47 3.7.2. CSPmodel . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.8. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Chapter4.ExactApproaches . . . . . . . . . . . . . . . . . . . . . . 53 4.1. Constructionofasearchtree . . . . . . . . . . . . . . . . . . . 53 4.2. Constraintpropagation . . . . . . . . . . . . . . . . . . . . . . 57 4.2.1. Forwardchecking. . . . . . . . . . . . . . . . . . . . . . 57 4.2.2. Maintainingarcconsistency . . . . . . . . . . . . . . . . 59 4.3. Orderingheuristics . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3.1. Heuristicsforchoosingvariables . . . . . . . . . . . . . 61 4.3.2. Heuristicsforchoosingvalues. . . . . . . . . . . . . . . 62 4.3.3. Randomizedrestart . . . . . . . . . . . . . . . . . . . . . 63 4.4. Fromsatisfactiontooptimizationproblems . . . . . . . . . . 63 4.5. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 www.it-ebooks.info TableofContents vii Chapter5.PerturbativeHeuristicApproaches . . . . . . . . . . . . 69 5.1. Geneticalgorithms . . . . . . . . . . . . . . . . . . . . . . . . 70 5.1.1. Basicprinciples . . . . . . . . . . . . . . . . . . . . . . . 70 5.1.2. UsingGAstosolveCSPs . . . . . . . . . . . . . . . . . 73 5.2. Localsearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.2.1. Basicprinciples . . . . . . . . . . . . . . . . . . . . . . . 73 5.2.2. MetaheuristicsbasedonLS . . . . . . . . . . . . . . . . 75 5.2.3. UsingLStosolveCSPs . . . . . . . . . . . . . . . . . . 77 5.3. Particleswarmoptimization . . . . . . . . . . . . . . . . . . . 78 5.3.1. Basicprinciples . . . . . . . . . . . . . . . . . . . . . . . 78 5.3.2. UsingPSOtosolveCSPs . . . . . . . . . . . . . . . . . 80 5.4. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Chapter6.ConstructiveHeuristicApproaches . . . . . . . . . . . . 85 6.1. Greedyrandomizedapproaches . . . . . . . . . . . . . . . . . 86 6.1.1. Basicprinciples . . . . . . . . . . . . . . . . . . . . . . . 86 6.1.2. UsinggreedyrandomizedalgorithmstosolveCSPs . . 88 6.2. Estimationofdistributionalgorithms . . . . . . . . . . . . . . 88 6.2.1. Basicprinciples . . . . . . . . . . . . . . . . . . . . . . . 88 6.2.2. UsingEDAstosolveCSPs . . . . . . . . . . . . . . . . 90 6.3. Antcolonyoptimization . . . . . . . . . . . . . . . . . . . . . 90 6.4. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Chapter7.ConstraintProgrammingLanguages . . . . . . . . . . . 93 7.1. Constraintlogicprogramming . . . . . . . . . . . . . . . . . . 94 7.2. Constraintprogramminglibraries . . . . . . . . . . . . . . . . 96 7.3. Constraint-basedlocalsearch . . . . . . . . . . . . . . . . . . 96 7.4. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 PARTII.ANTCOLONYOPTIMIZATION . . . . . . . . . . . . . . . 101 IntroductiontoPartII . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Chapter8.FromSwarmIntelligencetoAntColonyOptimization 105 8.1. Complexsystemsandswarmintelligence . . . . . . . . . . . 106 8.2. Searchingforshortestpathsbyantcolonies . . . . . . . . . . 108 8.3. Antsystemandthetravelingsalesmanproblem . . . . . . . . 111 8.3.1. Pheromonestructure . . . . . . . . . . . . . . . . . . . . 112 8.3.2. ConstructionofaHamiltoniancyclebyanant . . . . . 114 www.it-ebooks.info viii ACOandCP 8.3.3. Pheromoneupdatingstep . . . . . . . . . . . . . . . . . 115 8.3.4. Artificialversusrealants. . . . . . . . . . . . . . . . . . 115 8.4. GenericACOframework . . . . . . . . . . . . . . . . . . . . . 116 8.4.1. Pheromonestructureandconstructiongraph . . . . . . 116 8.4.2. Constructionofcombinationsbyants . . . . . . . . . . 118 8.4.3. Improvingcombinationswithlocalsearch . . . . . . . . 120 8.4.4. Pheromoneupdatingstep . . . . . . . . . . . . . . . . . 121 8.4.5. ParametersofanACOalgorithm . . . . . . . . . . . . . 122 Chapter9.IntensificationversusDiversification . . . . . . . . . . . 125 9.1. ACOmechanismsforintensifyingthesearch . . . . . . . . . 125 9.2. ACOmechanismsfordiversifyingthesearch . . . . . . . . . 127 9.3. Balancingintensificationanddiversification . . . . . . . . . . 128 9.4. Measuresofdiversification/intensification . . . . . . . . . . . 135 9.4.1. Theλ-branchingfactor. . . . . . . . . . . . . . . . . . . 136 9.4.2. Resamplingratio . . . . . . . . . . . . . . . . . . . . . . 136 9.4.3. Similarityratio . . . . . . . . . . . . . . . . . . . . . . . 137 Chapter10.BeyondStaticCombinatorialProblems . . . . . . . . 141 10.1.Multi-objectiveproblems. . . . . . . . . . . . . . . . . . . . . 141 10.1.1. Definitionofmulti-objectiveproblems . . . . . . . . . . 141 10.1.2. Solvingmulti-objectiveproblemswithACO . . . . . . 143 10.2.Dynamicoptimizationproblems. . . . . . . . . . . . . . . . . 145 10.2.1. Definitionofdynamicoptimizationproblems . . . . . . 145 10.2.2. SolvingdynamicoptimizationproblemswithACO. . . 146 10.3.Optimizationproblemsovercontinuousdomains . . . . . . . 147 10.3.1. Definitionofcontinuousoptimizationproblems. . . . . 147 10.3.2. SolvingcontinuousoptimizationproblemswithACO . 148 Chapter11.ImplementationIssues . . . . . . . . . . . . . . . . . . . 151 11.1.Datastructures. . . . . . . . . . . . . . . . . . . . . . . . . . . 151 11.1.1. Datastructuresassociatedwithpheromonefactors . . . 151 11.1.2. Datastructuresassociatedwithheuristicfactors. . . . . 153 11.1.3. Datastructuresassociatedwithants . . . . . . . . . . . 154 11.2.Selectionofacomponentwithrespecttoprobabilities . . . . 154 11.3.Implementationofalocalsearchprocedure . . . . . . . . . . 157 11.4.Computationofdiversification/intensificationmeasures . . . 157 11.4.1. Resamplingratio . . . . . . . . . . . . . . . . . . . . . . 158 11.4.2. Similarityratio . . . . . . . . . . . . . . . . . . . . . . . 158 www.it-ebooks.info TableofContents ix PARTIII.CPWITHACO . . . . . . . . . . . . . . . . . . . . . . . . 161 IntroductiontoPartIII . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Chapter12.SequencingCarswithACO . . . . . . . . . . . . . . . . 165 12.1.Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 12.2.Afirstpheromonestructureforidentifyinggoodcar sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 12.2.1. Pheromonestructure . . . . . . . . . . . . . . . . . . . . 167 12.2.2. Constructionofasequencebyanant . . . . . . . . . . . 168 12.2.3. Pheromonelayingstep . . . . . . . . . . . . . . . . . . . 170 12.3.Asecondpheromonestructureforidentifyingcriticalcars . . 171 12.3.1. Pheromonestructure . . . . . . . . . . . . . . . . . . . . 171 12.3.2. Constructionofasequencebyanant . . . . . . . . . . . 172 12.3.3. Pheromoneupdatingstep . . . . . . . . . . . . . . . . . 172 12.4.Combiningthetwopheromonestructures . . . . . . . . . . . 173 12.4.1. Firstpheromonestructure . . . . . . . . . . . . . . . . . 173 12.4.2. Secondpheromonestructure. . . . . . . . . . . . . . . . 173 12.4.3. Constructionofasequencebyanant . . . . . . . . . . . 173 12.5.ComparisonofthedifferentACOalgorithms . . . . . . . . . 174 12.5.1. Consideredalgorithms . . . . . . . . . . . . . . . . . . . 174 12.5.2. Testsuite. . . . . . . . . . . . . . . . . . . . . . . . . . . 175 12.5.3. Parametersettings . . . . . . . . . . . . . . . . . . . . . 175 12.5.4. Experimentalresults . . . . . . . . . . . . . . . . . . . . 177 12.6.ComparisonofACOwithstate-of-the-artapproaches. . . . . 178 12.6.1. Consideredapproaches. . . . . . . . . . . . . . . . . . . 178 12.6.2. IDWalk . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 12.6.3. VFLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 12.6.4. Experimentalset-up . . . . . . . . . . . . . . . . . . . . 180 12.6.5. Experimentalresults . . . . . . . . . . . . . . . . . . . . 180 12.7.Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 Chapter13.SubsetSelectionwithACO . . . . . . . . . . . . . . . . 185 13.1.Subsetselectionproblems . . . . . . . . . . . . . . . . . . . . 186 13.1.1. Maximumclique . . . . . . . . . . . . . . . . . . . . . . 186 13.1.2. Multidimensionalknapsack . . . . . . . . . . . . . . . . 187 13.1.3. MaximumBooleansatisfiability . . . . . . . . . . . . . 187 13.1.4. Maximumconstraintsatisfaction . . . . . . . . . . . . . 187 13.1.5. Minimumvertexcover . . . . . . . . . . . . . . . . . . . 188 13.1.6. Maximumcommonsubgraph . . . . . . . . . . . . . . . 188 www.it-ebooks.info x ACOandCP 13.1.7. Edge-weightedk-cardinalitytree . . . . . . . . . . . . . 189 13.2.DescriptionofAnt-SSP. . . . . . . . . . . . . . . . . . . . . . 189 13.2.1. Constructionofacombinationbyanant . . . . . . . . . 190 13.2.2. Pheromonelayingstep . . . . . . . . . . . . . . . . . . . 192 13.3.InstantiationsofAnt-SSPwithrespecttotwopheromone strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 13.3.1. Thevertexpheromonestrategy . . . . . . . . . . . . . . 193 13.3.2. Thecliquepheromonestrategy . . . . . . . . . . . . . . 193 13.3.3. Comparisonofthetwostrategies . . . . . . . . . . . . . 194 13.4.InstantiationofAnt-SSPtosolveCSPs . . . . . . . . . . . . . 196 13.4.1. Heuristicfactor . . . . . . . . . . . . . . . . . . . . . . . 196 13.4.2. Localsearch . . . . . . . . . . . . . . . . . . . . . . . . . 197 13.5.Experimentalresults . . . . . . . . . . . . . . . . . . . . . . . 197 13.5.1. Randomlygeneratedbinaryinstances . . . . . . . . . . 197 13.5.2. Resultsoninstancesofthe2006solvercompetition . . 199 13.6.Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 Chapter14.IntegrationofACOinaCPLanguage . . . . . . . . . 205 14.1.FrameworkforintegratingACOwithinaCPlibrary . . . . . 206 14.1.1. Pheromonestrategy. . . . . . . . . . . . . . . . . . . . . 207 14.1.2. Constructionofassignments. . . . . . . . . . . . . . . . 208 14.1.3. Pheromoneupdatingstep . . . . . . . . . . . . . . . . . 210 14.2.IllustrationofACO-CPonthecarsequencingproblem . . . . 210 14.2.1. CSPmodel . . . . . . . . . . . . . . . . . . . . . . . . . 210 14.2.2. Variableorderingheuristic . . . . . . . . . . . . . . . . . 211 14.2.3. Pheromonestrategies . . . . . . . . . . . . . . . . . . . . 211 14.2.4. Heuristicfactor . . . . . . . . . . . . . . . . . . . . . . . 212 14.2.5. Experimentalresults . . . . . . . . . . . . . . . . . . . . 213 14.3.Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 Chapter15.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 215 15.1.Towardsconstraint-basedACOsearch . . . . . . . . . . . . . 215 15.2.TowardsareactiveACOsearch . . . . . . . . . . . . . . . . . 216 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 www.it-ebooks.info Foreword Combinatorial optimization has a very special place in computer science. Ontheonehand,thisfieldaddressesfundamentalproblemssuchasscheduling, resourceallocationandvehiculerouting,whicharecentraltooureconomies. On the other hand, combinatorial optimization problems are extremely hard from a computational complexity standpoint: it is very unlikely that an efficient algorithm able to solve all these problems efficiently exists and that a single approach would outperform all others in this field. Different combinatorial problems, or even different instances of the same application, may be solved by very different techniques or by a combination of some of them. Moreover, whatever the approach considered, solving a combinatorial optimization problem usually requires a significant amount of programming andexperimentationwork. Inthisbook,ChristineSolnonfocusesonAntColonyOptimization(ACO), a relatively recent approach for solving combinatorial problems. The topic is relevant: during the last decade, ACO has gradually evolved from an intellectual curiosity to a metaheuristic that has obtained outstanding results onsomeapplications.Thisisthecase,forexample,ofschedulinginassembly lines: a particularly difficult application for which ACO is able to solve a largeclassofinstanceswithaveryimpressiveefficiencyandsuccessrate.The scientific article published by the author on this subject was, indeed, a true revelationformanyresearchers. However, this book does not introduce ACO in an isolated way, but providesanoverviewofmanyapproaches.Thefirstpartofthebookprovides ashortbutexcellentsummaryofthestateoftheart,withafocusonconstraint satisfaction problems. Not only does this presentation clearly identify ACO xi www.it-ebooks.info