《物流系统分析与优化》课程教学课件（PPT讲稿）Ant Colony Optimization（ACO）and Real Version ACOR

Ant Colony Optimization (ACO)and Real Version ACO

Ant Colony Optimization (ACO) and Real Version ACOR

ACOM. Dorigo et al. (1999)Antalgorithms- inspired by the observation of real ant colonies-An important and interesting behavior of antcolonies is their foraging behavior, and, inparticular, how ants can find the shortest pathsbetween food sources and their nest

ACO • M. Dorigo et al. (1999) • Ant algorithms – inspired by the observation of real ant colonies – An important and interesting behavior of ant colonies is their foraging behavior, and, in particular, how ants can find the shortest paths between food sources and their nest

While walkingfromfood sources to thenestand vice versa, ants deposit on the ground asubstance called pheromone, forming in thisway a pheromone trail. Ants can smellpheromone, and when choosing their way,they tend to choose, in probability, pathsmarked by strong pheromone concentrations.The pheromone trail allows the ants to findtheir way back to the food source (or to thenest)

• While walking from food sources to the nest and vice versa, ants deposit on the ground a substance called pheromone, forming in this way a pheromone trail. Ants can smell pheromone, and when choosing their way, they tend to choose, in probability, paths marked by strong pheromone concentrations. The pheromone trail allows the ants to find their way back to the food source (or to the nest)

15cmUpperBranchNestFoodLowerBranch(a)

-%Passagesupperbranch-%Passageslowerbranch10075BREEEEdJE50250051015252030Time (minutes)(b)

ForagingForagingareaareaNestNest(b)(a)

%otexperiments040602080100+1+0-20LE20-40TEAUOEBLAREOEDL40-60SILE60-80T>e80-100(c)

. ldeas stem from real ants with the use of(a) a colony of cooperating individuals(b) an (artificial) pheromone trail for localstigmergetic communication,(c) a sequence of local moves to find shortest paths(d) a stochastic decision policy using localinformation and no lookahead

• Ideas stem from real ants with the use of (a) a colony of cooperating individuals (b) an (artificial) pheromone trail for local stigmergetic communication, (c) a sequence of local moves to find shortest paths, (d) a stochastic decision policy using local information and no lookahead

Characteristics not found in real ants- Artificial antsliveina discrete world andtheirmoves consist oftransitions from discrete statesto discrete states-Artificial antshaveaninternal state.Thisprivatestatecontainsthememory of the ants'past actions.-Artifcial antsdeposit anamountof pheromone thatisafunctionof the qualityof thesolutionfound.- Artifcial ants'timing in pheromone laying is problem dependentandoftendoes notreflect realants'behavior.Forexample,inmany cases artificialants update pheromone trails only afterhaving generated a solution.-Toimproveoverallsystemefficiency,AcOalgorithmscanbeenrichedwithextra capabilities suchaslookahead,localoptimization,backtracking,and so onthat cannotbefound inreal ants

• Characteristics not found in real ants – Artificial ants live in a discrete world and their moves consist of transitions from discrete states to discrete states. – Artificial ants have an internal state. This private state contains the memory of the ants’ past actions. – Artifcial ants deposit an amount of pheromone that is a function of the quality of the solution found. – Artifcial ants’ timing in pheromone laying is problem dependent and often does not reflect real ants’ behavior. For example, in many cases artificial ants update pheromone trails only after having generated a solution. – To improve overall system efficiency, ACO algorithms can be enriched with extra capabilities such as lookahead, local optimization, backtracking, and so on that cannot be found in real ants

Acois aconstructivealgorithm and it constructsasolution stochastically based on the pheromoneinformation, and problem dependent heuristicinformation.Thepheromoneinformationmustberepresentedinaform appropriate for the problem.The pheromoneinformation will be updated dynamically during thesearch process to simulate realants'foraging behavior.Theproblemdependentheuristicinformationisnotavailable inrealantsbutoften addedinartificialantstohelpsolveaproblemmoreeffectively

• ACO is a constructive algorithm and it constructs a solution stochastically based on the pheromone information, and problem dependent heuristic information. • The pheromone information must be represented in a form appropriate for the problem. The pheromone information will be updated dynamically during the search process to simulate real ants’ foraging behavior. • The problem dependent heuristic information is not available in real ants but often added in artificial ants to help solve a problem more effectively