MODIFIED BIOGEOGRAPHICAL BASED OPTIMIZATION ALGORITHM (MBBO) AND EFFICIENT SIMULATED ANNEALING TO OBTAIN OPTIMAL SOLUTION FOR TRAVELLING TOURNAMENT PROBLEM (TTP)

Abstract

This project aims to apply evolutionary extended species abundance models of biogeography on Travelling Tournament Problem. This implementation shows a heuristic approach of enhanced simulated annealing based on extended species abundance models of biogeography in order to obtain optimal solution and to solve the problem of local minima for Travelling Tournament Problem. We upgrade the migration step of BBO by using probabilistic measures and hybridize it with simulated annealing to solve the TTP. Our proposed hybrid approach converges to an optimal solution for TTP. There is negative impact of non deterministic problems on the TTP solution. We considered all these non-deterministic problems as noise. The physical significance of noise in our algorithm is any existing parameter which can affect the fitness of the habitat. We also calculate the overall cost of TTP for various extended species abundance models of BBO(Linear and Non linear models) to achieve desirable results. The Extended species abundance models consist concepts of Growth Rate and Decline Rate which are correlated to Immigration Rate and Emigration Rate. The extended version of BBO have six Models consists of linear and non linear models which have the parameter specification: growth rate (𝜎𝑘) as a function of species evolution rate and the species immigration rate 𝜆 and species decline rate as a function of species extinction rate and emigration rate (𝜇) for the determination of the total species count at a given time instant on a single habitat. We demonstrate the performance of each of the extended models of BBO for solving the Travelling tournament problem and found that the average convergence of each of the proposed extended species abundance models is faster leading to better optimization results previous approaches applied on TTP We compare the performance of our approach with other methodologies like ACO and PSO. TTP is NP-hard problem for which we need to produce an output which is an optimal schedule from the input which is distance matrix given to us. We apply enhanced simulated annealing to this schedule and try to obtain efficient schedule. We apply cost function to this obtained schedule and generate the minimal cost for our TTP problem and solve the issue of local minima which exists in some genetic algorithms ant colony optimization (ACO) and particle swarm optimization (PSO). We plot some graphs representing the convergence rates of the cost produced by different approaches for TTP.