# Adjustable Pheromone Reinforcement Strategies for Problems with Efficient Heuristic Information
## 2 Related Work  
Improvements made by ant colony optimization variants are achieved by changing either the solution construction procedure or the pheromone update procedure. In the case of a solution construction procedure, almost all ACO algorithms use the random proportional rule introduced by the ant system [15; 16] or the more general variant, the pseudo-random proportional rule, used by the ant colony system [17]. Many improvements in ant colony optimization variants are based on changing the way the pheromone trails are modified in the pheromone update procedure. These changes are more often concerned with the way the pheromone trails are reinforced than with the way the pheromone trails are evaporated. The initial variant of ACO, named the ant system [18], uses all solutions from the current iteration in the pheromone reinforcement procedure. The components of better solutions are proportionally reinforced with more pheromone value than the solutions with worse quality. This type of strategy provides only little guidance to the subsequent solution construction procedure in searching through the solution space. The pheromone reinforcement strategy introduced by the ant system causes too much exploration and too little exploitation of previous knowledge. In an attempt to improve algorithmic behavior, an ACO variant named the elitist ant system was proposed [16]. To make the algorithm greedier, in addition to pheromone reinforcement of all solutions in the current iteration, the components of the best solution found from the beginning of the algorithm (also called global-best solution) are reinforced with a weight determined by the parameter \(e\). More selective in choosing solutions for pheromone reinforcement is the rank-based ant system, which uses weights for pheromone reinforcement based on solution ranks and reinforces only w solutions from the current iteration [19], where w is an integer parameter. Modern variants of the ACO algorithms use only one solution, in some sense \"the best\" solution, to reinforce pheromone trails. The ant colony system (ACS) uses the global-best solution for pheromone reinforcement [16]. The MAX-MIN ant system (MMAS) uses the iteration-best or global-best solution [8]. The most commonly used variant of ACO is probably the MMAS because of its excellent performance on many combinatorial optimization problems. When a faster and greedier variant is preferred, then ACS might be used instead of MMAS. The best-worst ant system uses only the global-best solution to reinforce pheromone trails but also decreases the pheromone trails associated with the components of the worst solution in the current iteration that are not contained in the global-best solution [20; 21]. Although the authors of BWAS claimed good performance, the BWAS algorithm did not gain wide popularity. Population-based ant colony optimization uses the iteration-best solution to reinforce pheromone trails but also has a special mechanism to completely unmake the pheromone reinforcement made in the previous iteration, which is especially suitable for dynamic optimization problems [22; 23]. There are also some studies about reinforcing pheromone trails that cannot be applied in general cases and address only specific situations. In [24], [PERSON] et al. proposed a technique for situations when pheromone trails are associated with nodes instead of arcs of the construction graph. The best-so-far strategy is used together with new rules (these new rules are named \(r\)-best-node update rule and a relevant-node depositing rule; the first one has a somewhat similar name to our \(\kappa\)-best strategy, although the actual methods are very different) proposed by the authors specifically for this type of problem. Their approach is applied to the shortest path problem, even though the path is not uniquely defined by the set of nodes and, therefore, pheromone trails associated with arcs would seem a more appropriate choice.