Ant algorithms were first written about in 1991 and since then they have been applied to many problems with great success. During these years the algorithms themselves have been modified for improved performance and also been influenced by research in other fields. Since the earliest Ant algorithms, heuristics and local search have been the primary knowledge sources. This thesis asks the question "how is knowledge used in Ant algorithms?" To answer this question three Ant algorithms are implemented. The first is the Graph based Ant System (GBAS), a theoretical model not yet implemented, and the others are two influential algorithms, the Ant System and Max-Min Ant System. A comparison is undertaken to show that the theoretical model empirically models what happens in the other two algorithms. Therefore, this chapter explores whether different pheromone matrices (representing the internal knowledge) have a significant effect on the behaviour of the algorithm. It is shown that only under extreme parameter settings does the behaviour of Ant System and Max-Min Ant System differ from that of GBAS. The thesis continues by investigating how inaccurate knowledge is used when it is the heuristic that is at fault. This study reveals that Ant algorithms are not good at dealing with this information, and if they do use a heuristic they must rely on it relating valid guidance. An additional benefit of this study is that it shows heuristics may offer more control over the exploration-exploitation trade-off than is afforded by other parameters. The second point where knowledge enters the algorithm is through the local search. The thesis looks at what happens to the performance of the Ant algorithms when a local search is used and how this affects the parameters of the algorithm. It is shown that the addition of a local search method does change the behaviour of the algorithm and that the strength of the method has a strong influence on how the parameters are chosen. The final study focuses on whether Ant algorithms are effective for driving a local search method. The thesis demonstrates that these algorithms are not as effective as some simpler fixed and variable neighbourhood search methods.

Numerous organizations collect and distribute non-aggregate personal data for a variety of different purposes, including demographic and public health research. In these situations, the data distributor is responsible with the protection of the anonymity and personal information of individuals. Microaggregation is one of the most commonly used statistical disclosure control methods. In microaggregation, the set of original records is first partitioned into several groups. The records in the same group are similar to each other. The minimum number of records in each group is k. Each record is replaced by the mean value of the group (centroid). The confidentiality of records is protected by ensuring that each group has at least a minimum of k records and each record is indistinguishable from at least k-1 other records in the microaggregated dataset. The goal of this process is to keep the within-group homogeneity higher and the information loss lower, where information loss is the sum squared deviation between the actual records and the group centroids. Several heuristics have been proposed for the NP-hard minimum information loss microaggregation problem. Among the most promising methods is the multivariate Hansen-Mukherjee (MHM) algorithm that uses a shortest path algorithm to identify the best partition consistent with a specified ordering of records. Developing improved heuristics for ordering multivariate points for microaggregation remains an open research challenge. This dissertation adapts a version of the population-based ant colony optimization algorithm (PACO) to order records within which MHM algorithm is used iteratively to improve the quality of grouping. Results of computational experiments using benchmark test problems indicate that P-ACO/MHM based microaggregation algorithm yields comparable or improved information loss than those obtained by extant methods.

This diploma thesis deals with ant colony optimization for shortest path problems. In the theoretical part it describes Ant Colony Optimization. In the practical part ant colony optimization algorithms are selected for the design and implementation of shortest path problems in the Java.

The ant system is a new meta-heuristic for hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. It was first proposed for tackling the well known Traveling Salesman Problem (TSP), but has been also successfully applied to problems such as quadratic assignment, job-shop scheduling, vehicle routing and graph coloring.In this paper we introduce a new rank based version of the ant system and present results of a computational study, where we compare the ant system with simulated annealing and a genetic algorithm on several TSP instances. It turns out that our rank based ant system can compete with the other methods in terms of average behavior, and shows even better worst case behavior. (author's abstract) / Series: Working Papers SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

This work deals with the issue of swarm intelligence as a subdiscipline of artificial intelligence. It describes biological background of the dilemma briefly and presents the principles of searching paths in ant colonies as well. There is also adduced combinatorial optimization and two selected tasks are defined in detail: Travelling Salesman Problem and Quadratic Assignment Problem. The main part of this work consists of description of swarm intelligence methods for solving mentioned problems and evaluation of experiments that were made on these methods. There were tested Ant System, Ant Colony System, Hybrid Ant System and Max-Min Ant System algorithm. Within the work there were also designed and tested my own method Genetic Ant System which enriches the basic Ant System i.a. with development of unit parameters based on genetical principles. The results of described methods were compared together with the ones of classical artificial intelligence within the frame of both solved problems.

In this work, we present a way to extend Ant Colony Optimization (ACO), so that it can be applied to both continuous and mixed-variable optimization problems. We demonstrate, first, how ACO may be extended to continuous domains. We describe the algorithm proposed, discuss the different design decisions made, and we position it among other metaheuristics. Following this, we present the results of numerous simulations and testing. We compare the results obtained by the proposed algorithm on typical benchmark problems with those obtained by other methods used for tackling continuous optimization problems in the literature. Finally, we investigate how our algorithm performs on a real-world problem coming from the medical field—we use our algorithm for training neural network used for pattern classification in disease recognition. Following an extensive analysis of the performance of ACO extended to continuous domains, we present how it may be further adapted to handle both continuous and discrete variables simultaneously. We thus introduce the first native mixed-variable version of an ACO algorithm. Then, we analyze and compare the performance of both continuous and mixed-variable ACO algorithms on different benchmark problems from the literature. Through the research performed, we gain some insight into the relationship between the formulation of mixed-variable problems, and the best methods to tackle them. Furthermore, we demonstrate that the performance of ACO on various real-world mixed-variable optimization problems coming from the mechanical engineering field is comparable to the state of the art.

The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer.In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time.We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space.A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.

This thesis deals with the implementation of the metaheuristic algorithms into the Drools Planner. The Drools Planner is an open source tool for solving optimization problems. This work describes design and implementation of Ant colony optimization metaheuristics in the Drools Planner. Evaluation of the algorithm results is done by Drools Planner benchmark with different kinds of optimization problems.

This thesis focuses on applying one of the rapidly growing non-deterministic optimization algorithms, the ant colony algorithm, for simulating automatic hose/pipe routing with several conflicting objectives. Within the thesis, methods have been developed and applied to single objective hose routing, multi-objective hose routing and multi-hose routing. The use of simulation and optimization in engineering design has been widely applied in all fields of engineering as the computational capabilities of computers has increased and improved. As a result of this, the application of non-deterministic optimization techniques such as genetic algorithms, simulated annealing algorithms, ant colony algorithms, etc. has increased dramatically resulting in vast improvements in the design process. Initially, two versions of ant colony algorithms have been developed based on, respectively, a random network and a grid network for a single objective (minimizing the length of the hoses) and avoiding obstacles in the CAD model. While applying ant colony algorithms for the simulation of hose routing, two modifications have been proposed for reducing the size of the search space and avoiding the stagnation problem. Hose routing problems often consist of several conflicting or trade-off objectives. In classical approaches, in many cases, multiple objectives are aggregated into one single objective function and optimization is then treated as a single-objective optimization problem. In this thesis two versions of ant colony algorithms are presented for multihose routing with two conflicting objectives: minimizing the total length of the hoses and maximizing the total shared length (bundle length). In this case the two objectives are aggregated into a single objective. The current state-of-the-art approach for handling multi-objective design problems is to employ the concept of Pareto optimality. Within this thesis a new Pareto-based general purpose ant colony algorithm (PSACO) is proposed and applied to a multi-objective hose routing problem that consists of the following objectives: total length of the hoses between the start and the end locations, number of bends, and angles of bends. The proposed method is capable of handling any number of objectives and uses a single pheromone matrix for all the objectives. The domination concept is used for updating the pheromone matrix. Among the currently available multi-objective ant colony optimization (MOACO) algorithms, P-ACO generates very good solutions in the central part of the Pareto front and hence the proposed algorithm is compared with P-ACO. A new term is added to the random proportional rule of both of the algorithms (PSACO and P-ACO) to attract ants towards edges that make angles close to the pre-specified angles of bends. A refinement algorithm is also suggested for searching an acceptable solution after the completion of searching the entire search space. For all of the simulations, the STL format (tessellated format) for the obstacles is used in the algorithm instead of the original shapes of the obstacles. This STL format is passed to the C++ library RAPID for collision detection. As a result of using this format, the algorithms can handle freeform obstacles and the algorithms are not restricted to a particular software package.

Opposition-based learning (OBL) was recently proposed to extend di erent machine learning algorithms. The main idea of OBL is to consider opposite estimates, actions or states as an attempt to increase the coverage of the solution space and to reduce exploration time. OBL has already been applied to reinforcement learning, neural networks and genetic algorithms. This thesis explores the application of OBL to ant algorithms. Ant algorithms are based on the trail laying and following behaviour of ants. They have been successfully applied to many complex optimization problems. However, like any other technique, they can benefit from performance improvements. Thus, this work was motivated by the idea of developing more complex pheromone and path selection behaviour for the algorithm using the concept of opposition. This work proposes opposition-based extensions to the construction and update phases of the ant algorithm. The modifications that focus on the solution construction include three direct and two indirect methods. The three direct methods work by pairing the ants and synchronizing their path selection. The two other approaches modify the decisions of the ants by using opposite-pheromone content. The extension of the update phase lead to an approach that performs additional pheromone updates using opposite decisions. Experimental validation was done using two versions of the ant algorithm: the Ant System and the Ant Colony System. The di erent OBL extensions were applied to the Travelling Salesman Problem (TSP) and to the Grid World Problem (GWP). Results demonstrate that the concept of opposition is not easily applied to the ant algorithm. One pheromone-based method showed performance improvements that were statistically significant for the TSP. The quality of the solutions increased and more optimal solutions were found. The extension to the update phase showed some improvements for the TSP and led to accuracy improvements and a significant speed-up for the GWP. The other extensions showed no clear improvement. The proposed methods for applying opposition to the ant algorithm have potential, but more investigations are required before ant colony optimization can fully benefit from opposition. Most importantly, fundamental theoretical work with graphs, specifically, clearly defining opposite paths or opposite path components, is needed. Overall, the results indicate that OBL ideas can be beneficial for ant algorithms.