most significant theoretical results so far published about convergence properties of ACO variants. 5.2.1 Ant System The importance of the original Ant System (AS) resides mainly in being the prototype of a number of ant algorithms which collectively implement the ACO paradigm. AS already follows the outline presented in the previous subsection, specifying its elements as follows. The move probability distribution defines probabilities pιψk to be equal to 0 for all moves which are infeasible (i.e., they are in the tabu list of ant that is a list containing all moves which are k, infeasible for ants starting from state otherwise they are computed by means of formula k ι), (5.1), where and are userdefined parameters (0 1): α β ≤ α,β ≤ In formula 5.1, tabuk is the tabu list of ant while parameters and specify the impact of trail k, α β and attractiveness, respectively. After each iteration of the algorithm, i.e., when all ants have t completed a solution, trails are updated by means of formula (5.2): where represents the sum of the contributions of all ants that used move (ιψ) to construct Δτιψ their solution, 0 1, is a user-defined parameter called and evaporation coefficient, ρ, ≤ ρ ≤ Δτιψ represents the sum of the contributions of all ants that used move (ιψ) to construct their solution. The ants’ contributions are proportional to the quality of the solutions achieved, i.e., the better solution is, the higher will be the trail contributions added to the moves it used. For example, in the case of the TSP, moves correspond to arcs of the graph, thus state could correspond to a ι
most significant theoretical results so far published about convergence properties of ACO variants. 5.2.1 Ant System The importance of the original Ant System (AS) resides mainly in being the prototype of a number of ant algorithms which collectively implement the ACO paradigm. AS already follows the outline presented in the previous subsection, specifying its elements as follows. The move probability distribution defines probabilities pιψk to be equal to 0 for all moves which are infeasible (i.e., they are in the tabu list of ant k, that is a list containing all moves which are infeasible for ants k starting from state ι), otherwise they are computed by means of formula (5.1), where α and β are userdefined parameters (0 ≤ α,β ≤ 1): In formula 5.1, tabuk is the tabu list of ant k, while parameters α and β specify the impact of trail and attractiveness, respectively. After each iteration t of the algorithm, i.e., when all ants have completed a solution, trails are updated by means of formula (5.2): where Δτιψ represents the sum of the contributions of all ants that used move (ιψ) to construct their solution, ρ, 0 ≤ ρ ≤ 1, is a user-defined parameter called evaporation coefficient, and Δτιψ represents the sum of the contributions of all ants that used move (ιψ) to construct their solution. The ants’ contributions are proportional to the quality of the solutions achieved, i.e., the better solution is, the higher will be the trail contributions added to the moves it used. For example, in the case of the TSP, moves correspond to arcs of the graph, thus state ι could correspond to a
ANT_COLONY_OPTIMISATION_APPLIED_TO_JOB_SHOP_SCHEDULING_PROBLEM.docx