Specialty Oriented And Generality Oriented Heuristic Algorithm Design For Combinatorial Optimization Problem

In the field of heuristic algorithm design, the debate about whether algorithm design should be problem oriented or generality oriented has arisen for decades. On the one hand, some believe that algorithm design should be problem oriented, so that heuristics could exploit problem domain specific knowledge; on the other hand, some argue that algorithm should be generality oriented, and it is possible and important to design general, robust algorithms. In this thesis, we intend to take the p-median problem as a case study, and investigate the heuristic algorithm design from both the specialty and the generality perspective. On one hand, for the specialty aspect, we focus on the backbone guided algorithm design and analysis, which incorporates backbone and fat as the domain knowledge to boost the heuristic search procedure, especially under the context of large scale instance solving. On the other hand, we are also interested in the development of hyper-heuristics, which highlights the generality and cross domain (heterogeneous instance) problem solving. More detailed, our work could be summarized as follows:1. For the problem specific algorithm design aspect, to improve the performance of the large scale p-median instance solving, we focus on efficient algorithm design based on the concept of backbone. Backbone indicates the shared common parts of all global optimal solutions to an NP-hard problem instance. Both the extraction and the approximation of the backbone variables have essential impacts on the heuristic algorithm design. In this thesis we propose a Limit Crossing (LC) based backbone extraction approach. The unique feature of LC lies in its ability to extract exact information (part of all the global optimal solutions) using a heuristic algorithm. Further, we develop an Accelerated Limit Crossing based Multilevel Algorithm based on LC. Various experiments demonstrate the effectiveness of ALCMA. Over all the171benchmark instances, ALCMA is able to update52best known upper bounds, and achieve92best known upper bounds. Also, fitness landscape analysis is employed to discuss when ALCMA works and when it fails.2. As an extension of the backbone extraction, we apply LC to the semi-supervised clustering analysis, which is a well known data mining task, so as to extract pairwise constraints automatically. With LC, we could partially automate the time-consuming and error-prone work traditionally conducted by domain experts. Furthermore, experiments show that with the pairwise constraints extracted by LC, the performance of the consequent clustering algorithms could be improved.3. We also focus on the hyper-heuristics, which aims to raise the generality of heuristics by managing a set of Low Level Heuristics (LLHs), and aim to automate the algorithm design process. However, those LLHs are usually parameterized, which may contradict the domain independent motivation of hyper-heuristics. In this thesis, we show how to automatically maintain low level parameters (LLPs) using a hyper-heuristic with LLP adaptation (AD-HH). Furthermore, aiming at tackling the search space expansion due to the LLP adaptation, we apply a heuristic space reduction (SAR) mechanism to improve the AD-HH framework. The integration of the LLP adaptation and the SARmechanism is able to explore the heuristic space more effectively and efficiently. Experiments over three heterogeneous classes of benchmark instances show that with the adaptation of the LLPs and the SAR mechanism, the proposed algorithms are able to achieve competitive results, compared with both typical metaheuristics and ALCMA.