5 Ant Colony Optimization

摘要: Ant Colony Optimization (ACO) is a paradigm for designing metaheuristic algorithms combinatorial optimization problems. The first algorithm which can be classified within this framework was presented in 1991 [21, 13] and, since then, many diverse variants of the basic principle have been reported literature. essential trait ACO combination priori information about structure promising solution with posteriori previously obtained good solutions. Metaheuristic are which, order to escape from local optima, drive some heuristic: either constructive heuristic starting null and adding elements build complete one, or search iteratively modifying its achieve better one. part permits lowlevel obtain solutions than those it could achieved alone, even if iterated. Usually, controlling mechanism by constraining randomizing set neighbor consider (as case simulated annealing [46] tabu [33]), combining taken different evolution strategies [11] genetic [40] bionomic [56] algorithms). characteristic their explicit use previous In fact, they low-level solution, as GRASP [30] does, but including population construction Monte Carlo way. A suggested also Genetic Algorithms [40], probability distribution explicitly defined components. particular way defining components associated probabilities problem-specific, designed ways, facing trade-off between specificity used conditioning number need constructed before effectively biasing dis-