组合优化近似搜索算法中的超启发式发展趋势

对组合优化中近似搜索算法采用的超启发式策略进行了总结和分类，并着重从强化和变化两个概念出发分析了不同超启发式的优缺点，探讨了其发展趋势，目的是为开发博采众长的混合近似搜索算法提供参考和指导。     

Evaluating a local genetic algorithm as context-independent local search operator for metaheuristics

Local genetic algorithms have been designed with the aim of providing effective intensification. One of their most outstanding features is that they may help classical local search-based metaheuristics to improve their behavior. This paper focuses on experimentally investigating the role of a recent approach, the binary-coded local genetic algorithm (BLGA), as context-independent local search operator for three local search-based metaheuristics: random multi-start local search, iterated local search, and variable neighborhood search. These general-purpose models treat the objective function as a black box, allowing the search process to be context-independent. The results show that BLGA may provide an effective and efficient intensification, not only allowing these three metaheuristics to be enhanced, but also predicting successful applications in other local search-based algorithms. In addition, the empirical results reported here reveal relevant insights on the behavior of classical local search methods when they are performed as context-independent optimizers in these three well-known metaheuristics.     

Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local Optima

Hybridizing evolutionary algorithms with local search has become a popular trend in recent years. There is empirical evidence for various combinatorial problems where hybrid evolutionary algorithms perform better than plain evolutionary algorithms. Due to the rapid development of a highly active field of research, theory lags far behind and a solid theoretical foundation of hybrid metaheuristics is sorely needed.     

A quality and distance guided hybrid algorithm for the vertex separator problem

This paper presents a quality and distance guided local search (QD-LS) as the diversification strategy for metaheuristics. QD-LS uses an augmented evaluation function which considers both solution quality and distance between the current solution and the best found solution to guide the search towards promising regions of the search space. To evaluate the performance of QD-LS, we propose a quality and distance guided hybrid algorithm (QD-HA) for solving the vertex separator problem. Based on the framework of evolutionary algorithms, QD-HA integrates a basic tabu search procedure with a random greedy recombination operator and QD-LS strategy. Assessed on two sets of 348 common benchmark instances, QD-HA achieves highly competitive results in terms of both solution quality and computational efficiency compared with state-of-the-art algorithms in the literature. Specifically, it improves the previous best known results for 63 out of 244 large instances while matching the best known results for others. The impact of the quality and distance based diversification strategy is also investigated.     

Multiobjective memetic algorithms for time and space assembly line balancing

This paper presents three proposals of multiobjective memetic algorithms to solve a more realistic extension of a classical industrial problem: time and space assembly line balancing. These three proposals are, respectively, based on evolutionary computation, ant colony optimisation, and greedy randomised search procedure. Different variants of these memetic algorithms have been developed and compared in order to determine the most suitable intensification–diversification trade-off for the memetic search process. Once a preliminary study on nine well-known problem instances is accomplished with a very good performance, the proposed memetic algorithms are applied considering real-world data from a Nissan plant in Barcelona (Spain). Outstanding approximations to the pseudo-optimal non-dominated solution set were achieved for this industrial case study.     

Embedded local search approaches for routing optimization

This paper presents a new class of heuristics which embed an exact algorithm within the framework of a local search heuristic. This approach was inspired by related heuristics which we developed for a practical problem arising in electronics manufacture. The basic idea of this heuristic is to break the original problem into small subproblems having similar properties to the original problem. These subproblems are then solved using time intensive heuristic approaches or exact algorithms and the solution is re-embedded into the original problem. The electronics manufacturing problem where we originally used the embedded local search approach, contains the Travelling Salesman Problem (TSP) as a major subproblem. In this paper we further develop our embedded search heuristic, HyperOpt, and investigate its performance for the TSP in comparison to other local search based approaches. We introduce an interesting hybrid of HyperOpt and 3-opt for asymmetric TSPs which proves more efficient than HyperOpt or 3-opt alone. Since pure local search seldom yields solutions of high quality we also investigate the performance of the approaches in an iterated local search framework. We examine iterated approaches of Large-Step Markov Chain and Variable Neighbourhood Search type and investigate their performance when used in combination with HyperOpt. We report extensive computational results to investigate the performance of our heuristic approaches for asymmetric and Euclidean Travelling Salesman Problems. While for the symmetric TSP our approaches yield solutions of comparable quality to 2-opt heuristic, the hybrid methods proposed for asymmetric problems seem capable of compensating for the time intensive embedded heuristic by finding tours of better average quality than iterated 3-opt in many less iterations and providing the best heuristic solutions known, for some instance classes.     

Guided restarting local search for production planning

Planning problems can be solved with a large variety of different approaches, and a significant amount of work has been devoted to the automation of planning processes using different kinds of methods. This paper focuses on the use of specific local search algorithms for real-world production planning based on experiments with real-world data, and presents an adapted local search guided by evolutionary metaheuristics. To make algorithms efficient, many specifics need to be considered and included in the problem solving. We demonstrate that the use of specialized local searches can significantly improve the convergence and efficiency of the algorithm. The paper also includes an experimental study of the efficiency of two memetic algorithms, and presents a real-world software implementation for the production planning.     

Metaheuristics for the single machine weighted quadratic tardiness scheduling problem

This paper considers the single machine scheduling problem with weighted quadratic tardiness costs. Three metaheuristics are presented, namely iterated local search, variable greedy and steady-state genetic algorithm procedures. These address a gap in the existing literature, which includes branch-and-bound algorithms (which can provide optimal solutions for small problems only) and dispatching rules (which are efficient and capable of providing adequate solutions for even quite large instances). A simple local search procedure which incorporates problem specific information is also proposed.The computational results show that the proposed metaheuristics clearly outperform the best of the existing procedures. Also, they provide an optimal solution for all (or nearly all, in the case of the variable greedy heuristic) the smaller size problems. The metaheuristics are quite close in what regards solution quality. Nevertheless, the iterated local search method provides the best solution, though at the expense of additional computational time. The exact opposite is true for the variable greedy procedure, while the genetic algorithm is a good all-around performer.     

Estimation-based metaheuristics for the probabilistic traveling salesman problem

The probabilistic traveling salesman problem (PTSP) is a central problem in stochastic routing. Recently, we have shown that empirical estimation is a promising approach to devise highly effective local search algorithms for the PTSP. In this paper, we customize two metaheuristics, an iterated local search algorithm and a memetic algorithm, to solve the PTSP. This customization consists in adopting the estimation approach to evaluate the solution cost, exploiting a recently developed estimation-based local search algorithm, and tuning the metaheuristics parameters. We present an experimental study of the estimation-based metaheuristic algorithms on a number of instance classes. The results show that the proposed algorithms are highly effective and that they define a new state-of-the-art for the PTSP.     

A guided cooperative search for the vehicle routing problem with time windows

We have developed a pattern-identification mechanism that endows cooperative search with capabilities to create new information and guide the global search. The proposed mechanism sends information to independent metaheuristics about promising and unpromising patterns in the solution space. By fixing or prohibiting specific solution attribute values in certain search metaheuristics, we can focus the search on desired regions. The mechanism thus enforces better coordination between individual methods and controls the global search's diversification and intensification. An enhanced cooperative-search mechanism creates new information from exchanged solutions and guides the global search with a pattern-identification mechanism.     

Metaheuristics and cooperative approaches for the Bi-objective Ring Star Problem

This paper presents and investigates different approaches to solve a new bi-objective routing problem called the ring star problem. It consists of locating a simple cycle through a subset of nodes of a graph while optimizing two kinds of cost. The first objective is the minimization of a ring cost that is related to the length of the cycle. The second one is the minimization of an assignment cost from non-visited nodes to visited ones. In spite of its obvious bi-objective formulation, this problem has always been investigated in a single-objective way. To tackle the bi-objective ring star problem, we first investigate different stand-alone search methods. Then, we propose two cooperative strategies that combine two multi-objective metaheuristics: an elitist evolutionary algorithm and a population-based local search. We apply these new hybrid approaches to well-known benchmark test instances and demonstrate their effectiveness in comparison to non-hybrid algorithms and to state-of-the-art methods.     

A two‐phase harmony search algorithm for continuous optimization

Harmony search (HS) algorithm is inspired by the music improvisation process in which a musician searches for the best harmony and continues to polish the harmony to improve its aesthetics. The efficiency of evolutionary algorithms depends on the extent of balance between diversification and intensification during the course of the search. An ideal evolutionary algorithm must have efficient exploration in the beginning and enhanced exploitation toward the end. In this paper, a two‐phase harmony search (TPHS) algorithm is proposed that attempts to strike a balance between exploration and exploitation by concentrating on diversification in the first phase using catastrophic mutation and then switches to intensification using local search in the second phase. The performance of TPHS is analyzed and compared with 4 state‐of‐the‐art HS variants on all the 30 IEEE CEC 2014 benchmark functions. The numerical results demonstrate the superiority of the proposed TPHS algorithm in terms of accuracy, particularly on multimodal functions when compared with other state‐of‐the‐art HS variants; further comparison with state‐of‐the‐art evolutionary algorithms reveals excellent performance of TPHS on composition functions. Composition functions are combined, rotated, shifted, and biased version of other unimodal and multimodal test functions and mimic the difficulties of real search spaces by providing a massive number of local optima and different shapes for different regions of the search space. The performance of the TPHS algorithm is also evaluated on a real‐life problem from the field of computer vision called camera calibration problem, ie, a 12‐dimensional highly nonlinear optimization problem with several local optima.     

A hybrid genetic algorithm for the phylogeny problem using path-relinking as a progressive crossover strategy

A phylogenetic tree relates taxonomic units using their similarities over a set of characteristics. Given a set of taxonomic units and their characteristics, the phylogeny problem under the parsimony criterion consists in finding a phylogenetic tree with a minimum number of evolutionary steps. We developed a hybrid genetic algorithm for the problem of building a phylogenetic tree minimizing parsimony. The algorithm combines local search with a crossover strategy based on path-relinking, an intensification technique originally used in the context of other metaheuristics such as scatter search and GRASP. Computational experiments on benchmark and randomly generated instances show that the proposed algorithm is very robust and outperforms other heuristics in terms of solution quality and running times.     

MAGMA: a multiagent architecture for metaheuristics

In this work, we introduce a multiagent architecture called the MultiAGent Metaheuristic Architecture (MAGMA) conceived as a conceptual and practical framework for metaheuristic algorithms. Metaheuristics can be seen as the result of the interaction among different kinds of agents: The basic architecture contains three levels, each hosting one or more agents. Level-0 agents build solutions, level-1 agents improve solutions, and level-2 agents provide the high level strategy. In this framework, classical metaheuristic algorithms can be smoothly accommodated and extended. The basic three level architecture can be enhanced with the introduction of a fourth level of agents (level-3 agents) coordinating lower level agents. With this additional level, MAGMA can also describe, in a uniform way, cooperative search and, in general, any combination of metaheuristics. We describe the entire architecture, the structure of agents in each level in terms of tuples, and the structure of their coordination as a labeled transition system. We propose this perspective with the aim to achieve a better and clearer understanding of metaheuristics, obtain hybrid algorithms, suggest guidelines for a software engineering-oriented implementation and for didactic purposes. Some specializations of the general architecture will be provided in order to show that existing metaheuristics [e.g., greedy randomized adaptive procedure (GRASP), ant colony optimization (ACO), iterated local search (ILS), memetic algorithms (MAs)] can be easily described in our framework. We describe cooperative search and large neighborhood search (LNS) in the proposed framework exploiting level-3 agents. We show also that a simple hybrid algorithm, called guided restart ILS, can be easily conceived as a combination of existing components in our framework.     

A study on integrating sequence dependent setup time flexible flow lines and preventive maintenance scheduling

This paper investigates flexible flow line problems with sequence dependent setup times and different preventive maintenance policies. The optimization criterion is the minimization of makespan. The contribution of this work could be divided into two parts: (1) Since the proposed integrating methods in the literature are often not only complicated but also problem-specific, we have been thinking of providing a technique simple to implement, yet easily extendible to any other machine scheduling problems to overcome the foregoing drawbacks. (2) In order to tackle the problem, we propose a novel variable neighborhood search (VNS) as well as the adaptations of some existing high performing metaheuristics in the literature. The proposed VNS uses advanced neighborhood search structures. In order to evaluate the algorithms, a benchmark is established with the meticulous care. All the results illustrate that the VNS outperforms the other algorithms.     

An effective hybrid algorithm for university course timetabling

The university course timetabling problem is an optimisation problem in which a set of events has to be scheduled in timeslots and located in suitable rooms. Recently, a set of benchmark instances was introduced and used for an ‘International Timetabling Competition’ to which 24 algorithms were submitted by various research groups active in the field of timetabling. We describe and analyse a hybrid metaheuristic algorithm which was developed under the very same rules and deadlines imposed by the competition and outperformed the official winner. It combines various construction heuristics, tabu search, variable neighbourhood descent and simulated annealing. Due to the complexity of developing hybrid metaheuristics, we strongly relied on an experimental methodology for configuring the algorithms as well as for choosing proper parameter settings. In particular, we used racing procedures that allow an automatic or semi-automatic configuration of algorithms with a good save in time. Our successful example shows that the systematic design of hybrid algorithms through an experimental methodology leads to high performing algorithms for hard combinatorial optimisation problems.     

Anwendung von Metaheuristiken zur Lösung betrieblicher Planungsprobleme

Application of metaheuristics within operations management — Potential and limitations of software reuse Business reality comprises a large variety of well structured problems (e.g. in production and logistics management), for which effective and efficient solution procedures are available from research. This includes metaheuristics such as iterative local search, tabu search and evolutionary algorithms. However, the implementation of these quantitative solution procedures as part of decision support systems usually requires problem-specific adaptations. To simplify this task we developed an application framework in C++, which represents various metaheuristics as reusable software components. These components can be used in arbitrary application domains. The framework clearly simplifies the effective practical application of metaheuristics. Nevertheless, a certain effort may be unavoidable if one aims at high-quality solutions in novel applications.     

Improving the Clustering Search heuristic: An application to cartographic labeling

The use of hybrid metaheuristics is a good approach to improve the quality and efficiency of metaheuristics. This paper presents a hybrid method based on Clustering Search (CS). CS seeks to combine metaheuristics and heuristics for local search, intensifying the search on regions of the search space which are considered promising. We propose a more efficient way to detect promising regions, based on the clustering techniques of Density-based spatial clustering of applications with noise (DBSCAN), Label-propagation (LP), and Natural Group Identification (NGI) algorithms. This proposal is called Density Clustering Search (DCS). To analyze this new approach, we propose to solve a combinatorial optimization problem with many practical applications, the Point Feature Cartographic Label Placement (PFCLP). The PFCLP attempts to locate identifiers (labels) of regions on a map without damaging legibility. The computational tests used instances taken from the literature. The results were satisfactory for clusters made with LP and NGI, presenting better results than the classic CS, which indicates these methods are a good alternative for the improvement of this method.     

Comparing evolutionary algorithms on binary constraint satisfaction problems

Constraint handling is not straightforward in evolutionary algorithms (EAs) since the usual search operators, mutation and recombination, are 'blind' to constraints. Nevertheless, the issue is highly relevant, for many challenging problems involve constraints. Over the last decade, numerous EAs for solving constraint satisfaction problems (CSP) have been introduced and studied on various problems. The diversity of approaches and the variety of problems used to study the resulting algorithms prevents a fair and accurate comparison of these algorithms. This paper aligns related work by presenting a concise overview and an extensive performance comparison of all these EAs on a systematically generated test suite of random binary CSPs. The random problem instance generator is based on a theoretical model that fixes deficiencies of models and respective generators that have been formerly used in the evolutionary computing field.