A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 2) MATHEMATICAL REPRESENTATION OF ACO <s> An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). We propose it as a viable new approach to stochastic combinatorial optimization. The main characteristics of this model are positive feedback, distributed computation, and the use of a constructive greedy heuristic. Positive feedback accounts for rapid discovery of good solutions, distributed computation avoids premature convergence, and the greedy heuristic helps find acceptable solutions in the early stages of the search process. We apply the proposed methodology to the classical traveling salesman problem (TSP), and report simulation results. We also discuss parameter selection and the early setups of the model, and compare it with tabu search and simulated annealing using TSP. To demonstrate the robustness of the approach, we show how the ant system (AS) can be applied to other optimization problems like the asymmetric traveling salesman, the quadratic assignment and the job-shop scheduling. Finally we discuss the salient characteristics-global data structure revision, distributed communication and probabilistic transitions of the AS. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 2) MATHEMATICAL REPRESENTATION OF ACO <s> In this paper we present an extension of ant colony optimization (ACO) to continuous domains. We show how ACO, which was initially developed to be a metaheuristic for combinatorial optimization, can be adapted to continuous optimization without any major conceptual change to its structure. We present the general idea, implementation, and results obtained. We compare the results with those reported in the literature for other continuous optimization methods: other ant-related approaches and other metaheuristics initially developed for combinatorial optimization and later adapted to handle the continuous case. We discuss how our extended ACO compares to those algorithms, and we present some analysis of its efficiency and robustness. <s> BIB002
The feasible solution of the problem to be optimized is represented by the ant's walking path, and all the paths of the whole ant colony constitute the solution space of the problem. Artificial ants construct solutions from sequences of solution components taken from a finite set of m available solution components C = {c ij }. And a solution construction starts with an empty partial solution s P = ∅. Then, at each step, the current partial solution s P is extended by adding a feasible solution component from the set N (s P ) ∈ C\s P , which is done probabilistically as represented in Eq. (1) BIB001 . where τ α ij is the pheromone value associated with component c ij , and η(·) is a weighting function that assigns a heuristic value to each feasible solution component c ij ∈ N (s P ) at each step. α and β are positive parameters determining the relation between pheromone information and heuristic information. The pheromone in Eq. (1) through the following pheromone evaporation process to increase the pheromone values associated with good or promising solutions, and decrease those that are associated with bad ones BIB002 . where ρ ∈ (0, 1] is the evaporation rate. Different versions of ACO algorithms update pheromones in different ways.