[PDF] Implementation and Applications of Ant Colony Algorithms

Optimisation combinatoire

L’optimisation combinatoire est un domaine assez r´ecent des math ematiques ap-´ pliquees, qui plonge ses racines dans la combinatoire (principalement la th´ ´eorie des graphes), la recherche operationnelle et l’informatique th´ ´eorique

Optimisation Combinatoire et Convexe

Optimisation Combinatoire et Convexe Approximation results A d’Aspremont M1 ENS 1/50 Today Semide nite relaxations Lagrangian relaxations for general QCQPs

Optimisation combinatoire

Optimisation combinatoire Définition Beaucoup de problème d’ordre pratique ou théorique nécessite de prendre, parmi un en-semble de choix possibles (très large), le meilleur choix selon un critère donné Remarque Domaine largement étudié en informatique, en mathématiques appliquées, en sciences de gestion, en génie industriel

Optimisation Combinatoire et Convexe

Optimisation Combinatoire et Convexe Semide nite programming A d’Aspremont M1 ENS 1/45 Introduction A linear program (LP) is written minimize cTx subject to Ax

Ordonancement sous incertitude: optimisation combinatoire

Ordonancement sous incertitude: optimisation combinatoire Marin Bougeret Michael Poss February 1, 2016 Context Applied scheduling problems face uncertainty due, for instance, to worker performance instabil-ities and tool quality variations Robust scheduling has been proposed nearly 20 years ago to handle such

Implementation and Applications of Ant Colony Algorithms

d’algorithmes pouvant trouver des solutions a des probl emes d’optimisation combinatoire Dans cette optique, la M etaheuristique des Colonies de Four-mis s’inspire de la biologie et propose di eren tes versions d’algorithmes tou-jours plus e caces Comme d’autres m etho des, l’Optimisation par Colonies

Les Méthodes Hybrides en Optimisation Combinatoire

Les M ethodes Hybrides en Optimisation Combinatoire :Algorithmes Exacts et Heuristiques Mathematics [math] Universit e Panth eon-Sorbonne - Paris I, 2003 French 2 Les probl`emes de type

MST et divergences informationelles : applications

mani`ere g´en ´erale dans les probl`emes d’optimisation combinatoire L’algorithme d’approximation des sous graphes minimaux contenant k points parmi N (k < N) pr´esen t´e dans [12] g´en ´eralise l’approche propos´ee par Ravi et al [16] dans le cas d = 2 et a permis de proposer un estimateur robuste de l’entropie d’une

UNIVERSITE DE MONTR´ EAL´ EXPLOITING GLOBAL CONSTRAINTS FOR

efficace pour r´esoudre les probl`emes d’optimisation combinatoire La PPC a ´et´e appliqu´ee avec succ`es `a de nombreux domaines; on mentionne le traitement de la langue naturelle, les syst`emes de base de donn´ees, la biologie mol´eculaire, les transports, la logistique, la chaˆıne

[PDF] tony buzan booster sa mémoire pdf

[PDF] ouverture numérique d'une fibre optique demonstration

[PDF] avc echelle fast

[PDF] vite avc

[PDF] question a poser pour detecter un avc

[PDF] fast avc

[PDF] référentiel de certification de la visite médicale

[PDF] leem

[PDF] nouvelle charte visite medicale 2017

[PDF] mathématique appliquée ? la finance pdf

[PDF] theoreme de bezout methode

[PDF] faire fonctionner un algorithme a la main

[PDF] ecrire un algorithme a la main

[PDF] expliquer les pourcentages en cm2

[PDF] les besoins nutritionnels de l'homme cours

Institutd'Informatique

Anneeacademique2004-2005

ImplementationandApplications

ofAntColonyAlgorithms

DenisDarquennes

Summary

SalesmanProblem.

AntSystem.

Resume

merce. i ii

Preface

Theworkingenvironment

problems. applications. lem.

Overviewofthemasterthesis

objectivesofthiswork. oftheAntColonyMetaheuristic. ornear-optimalsolutionstothisproblem. iii theAntColonyOptimizationfamily. thenewidea. algorithmsanddiscussawaytoimprovethem.

Acknowledgments

iv

Contents

Summary................................i

1Introduction1

2AntColonyOptimizationMetaheuristic3

2.1.3Stigmergy.........................7

problem..........................11

Problem17

v lem35

5TheEectofMemoryDepth47

6ExperimentalResults63

7Conclusion81

vi

Glossary

onthearcsithastraversed. spiredbytheforagingbehaviorofants. solutionsthatarenotnecessarilyoptimal. oftraversingthearcs. aresaidtobeintractable. itedbyanant. levelcomponents. mentatalatertime. pleagents. vii ingthearcs. saidtobetractable. antsthemselves. ofthatsize. viii

Chapter1

Introduction

1.1Theexistingcontext

totheirnest. givennumberofdestinations. 1

21.2.THEORIGINALCONTRIBUTION

1.2Theoriginalcontribution

aboutsolutionspreviouslyobserved.

Chapter2

AntColonyOptimization

Metaheuristic

Inthischapter,wewillbrie

ypresentsomebasicbiologicalnotionsthat oftheseideasincomputingscience.

2.1Somecontributionofbiologyincomput-

ingscience

2.1.1Socialinsectscooperation

interactionsamongrelativelysimpleagents, exibility,androbustness.This 3 uals.Theysolvetheseproblemsinavery exibleandrobustway: exibility performtheirtasks.

2.1.2Self-organizationinsocialinsects

exibleandrobustarti- intelligentsystems.

MAINIDEA

tosolvecomputationalproblems. in allowingthecolonytoselectthebestchoice. sources. uctuations(random thediscoveryofnewsolutions,and uctuationscanactasseedsfrom nestmatestothesefoodsources. byafewkeyproperties: andalargeperipheralregionofhoney. events. merelytheresultofanincreaseingroupsize.

2.1.3Stigmergy

interactionisanexampleofstigmergy. thebehaviorofotherindividuals.

82.2.THEACOMETAHEURISTICDESCRIPTION

associatedwith perturbation. nextsectionwilldiscribeit.

2.2TheACOmetaheuristicdescription

isdiscussedinsection3.1

2.2.1Themetaheuristicconcept

METAHEURISTIC

problems. optimizationproblemsinareasonabletime.

ACOMETAHEURISTIC

thebehaviorofrealants.

2.2.2Problemsmapping

T.(2004)Chapter2)

?,f, ),where s2S,and inapplicationstodynamicproblems. (respectivelymaximization)problem. 2

102.2.THEACOMETAHEURISTICDESCRIPTION

Thecombinatorialoptimizationproblem(

?,f, )ismappedonaproblem thenumberofcomponents. n<+1. .Notethat existssuchthats2~X. (t). thatJ(s,t)g(s,t): nections.

Theproblemconstraints

(t)areimplementedinthepolicyfollowedby ingproblem whichusesexactly(G)colours. withqassmallaspossible. colours,wesetm=n. x ij=(1ifvertexireceivescolourj

0otherwise

J i=f1;:::;ng1in thenwehavethat: X j2Jix ij=11n

122.2.THEACOMETAHEURISTICDESCRIPTION

Theobjectivefunctiontominimizeisgivenby:

f(x)=n X k=1k: nX l=1x lk! where(z)=(1ifz>0

0otherwise

consecutivecoloursbetween1and(G).

Alastsetofconstraintsexpressedby:

G j(x)=X [vi;vk]2Ex ij:xkj01jn cepts arebuilt feasiblesolutions.

PHEROMONETRAIL

HEURISTICVALUE

tionprovidedbyasourcedierentfromtheants. oftheLearningProcess,wecansay:

DISTRIBUTEDLEARNINGPROCESS

representedandperceivedbyotherants. agent.

2.2.5Theants'representation

M.,StutzleT.(2004)Chapter2)

142.2.THEACOMETAHEURISTICDESCRIPTION

solutionss2S. (i.e.,implementconstraints );(2)computetheheuristicvalues;(3) constraints. connection.

2.2.6Theimplementationofthemetaheuristic

tions,UpdatePheromones,andDaemonActions. buildsolutionstotheoptimizationproblem. againbyfutureants.

162.2.THEACOMETAHEURISTICDESCRIPTION

before,theDeamonActionsisoptional. procedureACOMetaheuristic

ScheduleActivities

ConstructAntsSolutions

UpdatePheromones

DaemonActions%optional

end-ScheduleActivities end-procedure pheromoneupdating,and(3)daemonactions.

Chapter3

TheNP-Completeproblems

andtheTravelingSalesman

Problem

interestsandvariants.Wewillbrie ydescribethedierentalgorithmsused

3.1Combinatorialoptimizationandcompu-

tationalcomplexity haveassociatedasetofprobleminstances. 17 ?,f, where s2S,and arecalledfeasible besolvableinO(nk)time.

APOLYNOMIALTIMEALGORITHM

usedtodenotethesize.

EXPONENTIALTIMEALGORITHM

calledanexponentialtimealgorithm. 2

TRACTABLEandINTRACTABLEPROBLEM

saidtobeintractable. \yes"iscorrect. referenceGarey,M.R.,&Johnson,D.S.(1979). instance-dependentruntime. constructiveorlocalsearchmethods. tice.

3.2Interestofthetravelingsalesmanprob-

lem todowithtravelingroutes. asshortaspossible.

Computerwiring

Vehiclerouting

Routeoptimizationinrobotic

Drillingofprintedcircuitboards

Chronologicalsequencing

3.3Descriptionofthetravelingsalesman

problem returninghome. once. f()isminimal,wheref()isgivenby: f()=n1X i=1d (i)(i+1)+d(n)(1): h1;2;:::;ni. matrixD=(d)ij. isvisitedatstepk.

3.4Dierentvariantsofthetravelingsales-

manproblem d classifyproblems.

SYMMETRICTSP(STSP)

ASYMMETRICTSP(ATSP)

METRICTSP(MTSP)

problemissaidtobemetric. wehave:

EUCLIDEANTSP(ETSP)

symmetricandmetric.

3.5Exactsolutionsofthetravelingsalesman

problemquotesdbs_dbs13.pdfusesText_19