Hybrid journal (It can contain Open Access articles) ISSN (Print) 1755-2176 - ISSN (Online) 1755-2184 Published by Inderscience Publishers[449 journals]

Authors:Weiqi Li, Xue Li Pages: 93 - 126 Abstract: This paper is the second part of our study. In the first part, we introduced the concept of solution attractor of local search system for the travelling salesman problem (TSP), described a procedure for constructing the solution attractor, and presented an attractor-based search system to solve the dynamic multi-objective TSP. In this paper, we report the results of our recent empirical study on some important properties of the solution attractor of local search system for the TSP. These properties include the nature of convergence of local search trajectories, the size of the constructed solution attractor, the relationship between the size of the problem and the size of the constructed solution attractor, the best tour in the solution attractor, and computational complexity in the attractor-based search system. Keywords: travelling salesman problem; TSP; global optimisation; analysis of heuristics; convergence of local search; solution attractor Citation: International Journal of Metaheuristics, Vol. 7, No. 2 (2019) pp. 93 - 126 PubDate: 2019-03-07T23:20:50-05:00 DOI: 10.1504/IJMHEUR.2019.098260 Issue No:Vol. 7, No. 2 (2019)

Authors:Raymond R. Hill, Edward A. Pohl Pages: 127 - 151 Abstract: Metaheuristic search algorithms have become ubiquitous in the applied optimisation world. Various works have appeared classifying and improving these algorithms and the particular processes embedded within the algorithms. Successful metaheuristic approaches have a common general structure to their search processes. To this end, we offer a structural taxonomy of metaheuristic search methods. This taxonomy serves as a framework for constructing and evaluating metaheuristic approaches from a general structural perspective as well as for conducting empirical research regarding the effectiveness of more detailed structural components. Implementation mechanisms of the detailed components within each structural component are left for future taxonomy research and development. Keywords: heuristic optimisation; taxonomy; metaheuristics; intensification; diversification; adaptive memory Citation: International Journal of Metaheuristics, Vol. 7, No. 2 (2019) pp. 127 - 151 PubDate: 2019-03-07T23:20:50-05:00 DOI: 10.1504/IJMHEUR.2019.098261 Issue No:Vol. 7, No. 2 (2019)

Authors:Derek H. Smith, Stephanie Perkins, Roberto Montemanni Pages: 152 - 175 Abstract: A hybrid algorithm for the maximum clique problem is presented. A heuristic is used to generate cliques and these are improved by some simple optimisations and Tabu search. All components of the algorithm make use of an exact algorithm or a pseudoexact algorithm, which is an exact algorithm with some specialised pruning. Pre-processing is useful for some instances. The algorithm is shown to be successful using standard and new benchmarks. Keywords: combinatorial optimisation; maximum clique; hybrid algorithm; Tabu search; pseudoexact algorithm; pre-processing; benchmarks Citation: International Journal of Metaheuristics, Vol. 7, No. 2 (2019) pp. 152 - 175 PubDate: 2019-03-07T23:20:50-05:00 DOI: 10.1504/IJMHEUR.2019.098270 Issue No:Vol. 7, No. 2 (2019)

Authors:Sonia Khatrouch, Safa Bhar Layeb, Jouhaina Chaouachi Siala Pages: 176 - 196 Abstract: We investigate a new variant of network design problems (NDPs) called the generalised discrete cost multicommodity network design problem (GDCMNDP) that arises in a wide variety of real-life situations such as transportation, telecommunication and logistics. The problem consists on identifying the optimal capacitated network by choosing the connections to be installed in order to satisfy partially or totally the multicommodity demands. The objective is to minimise the sum of installation costs and penalty costs due to the unrouted demands. For the GDCMNDP, we propose three basic greedy heuristics and three bio-inspired metaheuristics: a basic genetic algorithm, a hybrid genetic algorithm via a variable neighbourhood search procedure and a biogeography-based optimisation heuristic. To assess the performance of the proposed approaches, computational results are reported using real-world and benchmark instances from the literature. Computational results show that our hybrid genetic algorithm performs well by obtaining very good final solutions in reasonable times. Keywords: network design problems; NDPs; metaheuristics; hybrid genetic algorithm; HGA; biogeography-based optimisation; BBO; greedy heuristics Citation: International Journal of Metaheuristics, Vol. 7, No. 2 (2019) pp. 176 - 196 PubDate: 2019-03-07T23:20:50-05:00 DOI: 10.1504/IJMHEUR.2019.098274 Issue No:Vol. 7, No. 2 (2019)