Ant Colony Optimization (ACO)
Ant Colony Optimization (ACO) is a swarm intelligence metaheuristic for optimization problems whose solutions can be represented as paths through graphs. Such paths are generated by simulated ants moving from node to node in a simulated graph. On each vertex, they decide where to go next based on the accumulated simulated pheromone on edges and an edge-based heuristic (usually the objective value). They fall into the family of Estimation of Distribution Algorithms (EDAs), which comprises all metaheuristics that iteratively construct and refine statistical models of the search space and that use this model to sample new candidate solutions.
Posts
Measuring the Runtime of (Optimization) Algorithms
My research area is metaheuristic optimization, i.e., algorithms that can find good approximate solutions for computationally hard problems in feasible time. The Traveling Salesperson Problem (TSP) is an example for such an optimization task. In a TSP, $n$ cities and the distances between them are given and the goal is to find the shortest round-trip tour that goes through each city exactly once and then returns to its starting point. The TSP is $\mathcal{NP}$-hard, meaning that any currently known algorithm for finding the exact / globally best solution for all possible TSP instances will need a time which grows exponentially with $n$ on the worst case instances. And this is unlikely to change. In other words, if a TSP instance has $n$ cities, then the worst-case runtime of any exact TSP solver is in ${\mathcal{O}}(2^n)$. Well, today we have algorithms that can exactly solve a wide range of problems with tens of thousands of nodes and approximate the solution of million-node problems with an error of less than one part per thousand. This is pretty awesome, but the worst-case runtime to find the exact (optimal) solution is still exponential.
Why research in Computational Intelligence should be less nature-inspired.
The inspiration gleaned from observing nature has led to several important advances in the field of optimization. Still, it seems to me that a lot of work is mainly based on such inspiration alone. This might divert attention away from practical and algorithmic concerns. As a result, there is a growing number of specialized terminologies used in the field of Evolutionary Computation (EC) and Swarm Intelligence (SI), which I consider as a problem for clarity in research. With this article, I would like to formulate my thoughts with the hope to contribute to a fruitful debate.
Publications
- Xinlu LI (李新路), Brian Keegan, Fredrick Mtenzi, Thomas Weise (汤卫思), and Tan MING (檀明): Energy-Efficient Load Balancing Ant Based Routing Algorithm for Wireless Sensor Networks. IEEE Access 7:113182-113196, August 2019.
- Thomas Weise (汤卫思), Xiao-Feng WANG (王晓峰), Qi QI (齐琪), Bin LI (李斌), and Ke TANG (唐珂): Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features. Applied Soft Computing Journal (ASOC), 73:366–382, December 2018.
- Wei SHI (施玮), Thomas Weise (汤卫思), Raymond Chiong, and Bülent Çatay: Hybrid PACO with Enhanced Pheromone Initialization for Solving the Vehicle Routing Problem with Time Windows. IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS'2015), part of the IEEE Symposium Series on Computational Intelligence (SSCI'2015), December 8-10, 2015, Cape Town, South Africa, pages 1735-1742. Los Alamitos, CA, USA: IEEE Computer Society Press.
- Thomas Weise (汤卫思), Raymond Chiong, Jörg Lässig, Ke TANG (唐珂), Shigeyoshi Tsutsui, Wenxiang CHEN (陈文祥), Zbigniew Michalewicz, and Xin YAO (姚新): Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem. IEEE Computational Intelligence Magazine (CIM) 9(3):40-52. August 2014.
- Wei SHI (施玮) and Thomas Weise (汤卫思): An Initialized ACO for the VRPTW. 14th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL'2013), October 20-23, 2013, Hefei, Anhui, China, Lecture Notes in Computer Science (LNCS), volume 8206/2013, pages 93-100. Berlin, Germany: Springer-Verlag GmbH.