Description and composition of bio-inspired design patterns: a complete overview <s> Ant foraging pattern <s> Abstract We present an improvement heuristic for vehicle routing problems. The heuristic finds complex customer interchanges to improve an initial solution. Our approach is modular, thus it is easily adjusted to different side constraints such as time windows, backhauls and a heterogeneous vehicle fleet. The algorithm is well suited for parallelization. We report on a parallel implementation of the Simulated Trading heuristic on a cluster of workstations using PVM. The computational results were obtained using two sets of vehicle routing problems which differ in the presence of time windows. Our results show that Simulated Trading is better suited for problems with time windows. <s> BIB001 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Ant foraging pattern <s> The Generalized Assignment Problem consists in assigning a set of tasks to a set of agents with minimum cost. Each agent has a limited amount of a single resource and each task must be assigned to one and only one agent, requiring a certain amount of the resource of the agent. We present new metaheuristics for the generalized assignment problem based on hybrid approaches. One metaheuristic is a MAX-MIN Ant System (MMAS), an improved version of the Ant System, which was recently proposed by Stutzle and Hoos to combinatorial optimization problems, and it can be seen has an adaptive sampling algorithm that takes in consideration the experience gathered in earlier iterations of the algorithm. Moreover, the latter heuristic is combined with local search and tabu search heuristics to improve the search. A greedy randomized adaptive search heuristic (GRASP) is also proposed. Several neighborhoods are studied, including one based on ejection chains that produces good moves without increasing the computational effort. We present computational results of the comparative performance, followed by concluding remarks and ideas on future research in generalized assignment related problems. <s> BIB002 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Ant foraging pattern <s> Ant colony optimization (ACO) can be applied to the data mining field to extract rule-based classifiers. The aim of this paper is twofold. On the one hand, we provide an overview of previous ant-based approaches to the classification task and compare them with state-of-the-art classification techniques, such as C4.5, RIPPER, and support vector machines in a benchmark study. On the other hand, a new ant-based classification technique is proposed, named AntMiner+. The key differences between the proposed AntMiner+ and previous AntMiner versions are the usage of the better performing MAX-MIN ant system, a clearly defined and augmented environment for the ants to walk through, with the inclusion of the class variable to handle multiclass problems, and the ability to include interval rules in the rule list. Furthermore, the commonly encountered problem in ACO of setting system parameters is dealt with in an automated, dynamic manner. Our benchmarking experiments show an AntMiner+ accuracy that is superior to that obtained by the other AntMiner versions, and competitive or better than the results achieved by the compared classification techniques. <s> BIB003
Ant foraging is the activity where a set of ants collaborate to find food. The Ant Foraging Pattern is a decentralised collaborative search pattern. Mainly, the Ant Foraging Pattern has been applied to optimisation problems and used for swarm robotics. Aliases: Ant Colony Optimisation  . Problem: large scale optimisation problems that can be transformed into the problem of finding the shortest path on a weighted graph. Solution: the Ant Foraging Pattern provides rules to explore the environment in a decentralised manner and to exploit resources. Inspiration: the Ant Foraging Pattern is inspired by the Ant Colony Foraging behaviour. In ant colonies, ants coordinate their behaviour to find the shortest path from the nest to the food. Ant colonies use a stigmergic communication means, i.e. ants modify the environment by depositing a chemical substance called pheromone. This pheromone drives the behaviour of other ants in the colony, pheromone concentrations being used to recruit other ants. Following the highest pheromone concentration, ants find the shortest path from the nest to the food, and adapt this path when obstacles appear or when food is depleted. Forces: each ant has a probability of following the gradient produced by the pheromones. When one ant is not following the gradient, it walks randomly in the environment looking for new resources (exploration). When the probability of exploration is high (i.e. low probability of following the gradient), ants adapt faster to environmental changes but are slower in reaching the resources (exploitation). Whereas, with a low exploration (i.e. high probability of following the gradient), ants are quick in exploiting the resources since most of the ants follow the path to the resource. However, due to the lack of exploration, when the resource is depleted the ants spend more time to find new resources and adaptation is slower. Additionally, the Ant Foraging Pattern presents the same forces as the Digital Pheromone Pattern (Sect. 5.2.2). If the evaporation rate of the pheromone is too low, the pheromone scent does not evaporate quickly enough and stays where it has been laid down. The environment gets filled with pheromone and the exploitation is not efficient. A high evaporation rate causes the pheromone to evaporate before ants can build a path and maintain it, reducing the exploitation and incrementing the exploration. Entities-Dynamic-Environment: the entities involved in the Ant Foraging Pattern are the same as for the Digital Pheromone Pattern (Sect. 5.2.2). When one agent senses the presence of a digital pheromone, it decides to follow the gradient or to move randomly. The first rule models an agent that senses the values of the pheromone field in its location and in the neighbourhood, and then follows the direction of the highest gradient value to find food. The second rule models an agent that moves randomly. Both rules are subject to a rate which regulates the exploitation vs exploration activities. Implementation: according to some exploration probability, agents either follow scouts (i.e. are recruited to exploit food), or perform some random search. In the case of ants, scouts deposit pheromones in their environment, that are later sensed by other ants to find food sources. Figure 13a shows the general behaviour of ants, Fig. 13b shows the behaviour of ants looking for food, following a trail or taking a random path, finally Fig. 13c show the return to the nest, dropping pheromone, once a piece of food has been found. Known uses: the Ant Foraging Pattern has been mainly applied in Ant Colony Optimisation (ACO) (Dorig 1992) in applications such as, scheduling (Blu 2005; BIB003 , vehicle routing problems BIB001 Secomand 2000; Toth 2002) , or assignment problems BIB002 . Consequences: the system achieves high quality performance in NP-Hard search problems. Related Patterns: the Ant Foraging Pattern exploits the Digital Pheromone Pattern (Sect. 5.2.2). Thus, the Ant Foraging Pattern uses Evaporation, Spreading and Aggregation Patterns (see Appendix Table 2 for details about these patterns).