Hybridisation of genetic algorithms and tabu search approach for reconstructing convex binary images from discrete orthogonal projections

Abstract

In this paper, we consider a variant of the NP-complete problem of reconstructing HV-convex binary images from two orthogonal projections, noted by RCBI(H, V). This variant is reformulated as a new integer programming problem. Since this problem is NP-complete, a new hybrid optimisation algorithm combining the techniques of genetic algorithms and tabu search methods, noted by GATS is proposed to find an optimal or an approximate solution for RCBI(H, V) problem. GATS starts from a set of solutions called 'population' initialised by using an extension of the network flow model, incorporating a cost function. Two operators, namely crossover and mutation are used to explore the search space, then the quality of each individual in the population is improved by using another local search method named tabu search operator. In this paper we describe the proposed algorithm, then we evaluate and compare its performance with other optimisation techniques. The analysis of the experimental results shows the advantages of our GATS approach in terms of reconstruction quality and computational time.