Implementation of strong invariance on ACO algorithms and optimized routing of data packets in wired networks.

摘要

In the field of Artificial Intelligence, often, insects have become the prevailing source of innovation and inspiration. Ants are one such species that has provided computer science with a multitude of algorithms that allow the exploration of the workspace in the end goal of achieving some collective purpose, such as: job scheduling, vehicle routing, traffic congestion, predicting weather patterns, etc. Our focus in this thesis is centered on algorithms that are ant-based.;It is important to note that there are two distinct parts in this thesis; the first part, focuses on implementing the strong invariance on two existing ACO (Ant Colony Optimization) algorithms. The concepts of strong invariance have been presented in publications from a mathematical perspective. Our goal is the actual implementation of the strong invariant algorithms and their computational analysis to determine the benefit of such algorithms. We not only prove that our implementation does adhere to the definition of strong invariance, we also show that our implementation of Si-ACS found the optimal solution 5% more times than ACS and that it took 33% less iterations to do so. The results of our implementation of strong invariance on ACS (Ant Colony System) teach us that the individual and collaborative information that is gathered during the run of the algorithm results in finding the optimal solution in greater frequency and takes less time to run the algorithm, which could potentially save resources.;Based on our findings from the first part of this thesis, we apply the concepts of local and global information with the concepts of strong invariance on an ant-based algorithm used to solve network routing problems. The ant-based algorithm is called Antnet and at its foundation are the elements of ACO algorithms. Our optimization is two-fold, in one algorithm, we utilize the concepts of gathering local information regarding the network, to influence the next hop taken when routing data packets. Our second optimization algorithm focuses on using the collective (global) information-gathering concept to influence the next hop in a wired network. When comparing our optimization algorithms versus Antnet, we determined that our local (individual) gathering of information (Ind-A) was more advantageous in medium-sized networks with variable capacity, since it outperformed Antnet by 7% with respect to throughput, while having 3% less packets lost and less than 1% difference in delays per packet.