How to exploit fitness landscape properties of timetabling problem: A new operator for quantum evolutionary algorithm

摘要

The fitness landscape of the timetabling problems is analyzed in this paper to provide some insight into the properties of the problem. The analyses suggest that the good solutions are clustered in the search space and there is a correlation between the fitness of a local optimum and its distance to the best solution. Inspired by these findings, a new operator for Quantum Evolutionary Algorithms is proposed which, during the search process, collects information about the fitness landscape and tried to capture the backbone structure of the landscape. The knowledge it has collected is used to guide the search process towards a better region in the search space. The proposed algorithm consists of two phases. The first phase uses a tabu mechanism to collect information about the fitness landscape. In the second phase, the collected data are processed to guide the algorithm towards better regions in the search space. The algorithm clusters the good solutions it has found in its previous search process. Then when the population is converged and trapped in a local optimum, it is divided into sub-populations and each sub-population is designated to a cluster. The information in the database is then used to reinitialize the q-individuals, so they represent better regions in the search space. This way the population maintains diversity and by capturing the fitness landscape structure, the algorithm is guided towards better regions in the search space. The algorithm is compared with some state-of-the-art algorithms from PATAT competition conferences and experimental results are presented.