Hybridising Ant Colony Optimisation with a upper confidence bound algorithm for routing and wavelength assignment in an optical burst switching network

摘要

Ant Colony Optimisation (ACO) has been extensively applied to the network routing problem. Simulated ants are used to explore the network while recording information regarding their success by means of pheromones that are deposited on the route. A balance must be found between exploration of new routes and exploitation of established routes. Modern Monte Carlo game play algorithms, like Upper Confidence Bound applied to Trees (UCT), also have to decide which game branches to explore and which solutions should be exploited. The Upper Confidence Bound 1 (UCB1) formula is used to choose move branches, thus creating a balance between exploration and exploitation. This paper investigates the use of the UCB1 formula in an ACO algorithm to determine which routes should be selected. UCB1 was incorporated into an ACO algorithm that allocates a path (from source to destination) and an appropriate wavelength to packets to be routed in a network, which employs Optical Burst Switching (OBS). The new algorithm was evaluated against an existing ant-based algorithm on three network topologies in order to determine its effectiveness. Results obtained indicated that the proposed algorithm outperformed the existing algorithm in most scenarios.