超启发算法研究进展综述

超启发算法是一类新兴的优化方法,通过机器学习、算法选择、算法生成等技术求解组合优化等问题,具备跨问题领域求解的能力。针对超启发算法研究进展进行综述和讨论。首先,梳理超启发算法的定义、结构、特点和分类;其次,归纳选择式超启发算法和生成式超启发算法的研究进展及相关技术,包括选择低层启发式算法采用的学习方法,迭代计算中的移动接受策略,低层启发式算法的生成方法;最后,讨论现有超启发算法研究中存在的不足及未来的研究方向。     

A multi-objective hyper-heuristic based on choice function

Hyper-heuristics are emerging methodologies that perform a search over the space of heuristics in an attempt to solve difficult computational optimization problems. We present a learning selection choice function based hyper-heuristic to solve multi-objective optimization problems. This high level approach controls and combines the strengths of three well-known multi-objective evolutionary algorithms (i.e. NSGAII, SPEA2 and MOGA), utilizing them as the low level heuristics. The performance of the proposed learning hyper-heuristic is investigated on the Walking Fish Group test suite which is a common benchmark for multi-objective optimization. Additionally, the proposed hyper-heuristic is applied to the vehicle crashworthiness design problem as a real-world multi-objective problem. The experimental results demonstrate the effectiveness of the hyper-heuristic approach when compared to the performance of each low level heuristic run on its own, as well as being compared to other approaches including an adaptive multi-method search, namely AMALGAM.     

Multigrid method with a new interpolation operator

We introduce new techniques to design interpolation in multigrid methods for elliptic problems with discontinuous coefficients. The new techniques employ the Nelder–Mead simplex algorithm and skills in space geometry. The Nelder–Mead algorithm was used to minimize a scalar-valued function, which is a sum of distances from a point to four planes. We derived interpolation scheme in space geometry. We observed that new interpolation is better than traditional bilinear interpolation and cubic interpolation, as prolongation operator in multigrid methods.     

A new hyper-heuristic as a general problem solver: an implementation in HyFlex

This study provides a new hyper-heuristic design using a learning-based heuristic selection mechanism together with an adaptive move acceptance criterion. The selection process was supported by an online heuristic subset selection strategy. In addition, a pairwise heuristic hybridization method was designed. The motivation behind building an intelligent selection hyper-heuristic using these adaptive hyper-heuristic sub-mechanisms is to facilitate generality. Therefore, the designed hyper-heuristic was tested on a number of problem domains defined in a high-level framework, i.e., HyFlex. The framework provides a set of problems with a number of instances as well as a group of low-level heuristics. Thus, it can be considered a good environment to measure the generality level of selection hyper-heuristics. The computational results demonstrated the generic performance of the proposed strategy in comparison with other tested hyper-heuristics composed of the sub-mechanisms from the literature. Moreover, the performance and behavior analysis conducted for the hyper-heuristic clearly showed its adaptive characteristics under different search conditions. The principles comprising the here presented algorithm were at the heart of the algorithm that won the first international cross-domain heuristic search competition.     

Iterated local search using an add and delete hyper-heuristic for university course timetabling

Hyper-heuristics are (meta-)heuristics that operate at a higher level to choose or generate a set of low-level (meta-)heuristics in an attempt of solve difficult optimization problems. Iterated local search (ILS) is a well-known approach for discrete optimization, combining perturbation and hill-climbing within an iterative framework. In this study, we introduce an ILS approach, strengthened by a hyper-heuristic which generates heuristics based on a fixed number of add and delete operations. The performance of the proposed hyper-heuristic is tested across two different problem domains using real world benchmark of course timetabling instances from the second International Timetabling Competition Tracks 2 and 3. The results show that mixing add and delete operations within an ILS framework yields an effective hyper-heuristic approach.     

A hyper-heuristic based framework for dynamic optimization problems

Most of the real world problems have dynamic characteristics, where one or more elements of the underlying model for a given problem including the objective, constraints or even environmental parameters may change over time. Hyper-heuristics are problem-independent meta-heuristic techniques that are automating the process of selecting and generating multiple low-level heuristics to solve static combinatorial optimization problems. In this paper, we present a novel hybrid strategy for applicability of hyper-heuristic techniques on dynamic environments by integrating them with the memory/search algorithm. The memory/search algorithm is an important evolutionary technique that have applied on various dynamic optimization problems. We validate performance of our method by considering both the dynamic generalized assignment problem and the moving peaks benchmark. The former problem is extended from the generalized assignment problem by changing resource consumptions, capacity constraints and costs of jobs over time; and the latter one is a well-known synthetic problem that generates and updates a multidimensional landscape consisting of several peaks. Experimental evaluation performed on various instances of the given two problems validates that our hyper-heuristic integrated framework significantly outperforms the memory/search algorithm.     

A hybrid particle swarm–Nelder–Mead optimization method for crack detection in cantilever beams

The estimation of a crack location and depth in a cantilever beam is formulated as an optimization problem and the optimal location and depth are found by minimizing the cost function which is based on the difference of the first four measured and calculated natural frequencies. Calculated natural frequencies are obtained using a rotational spring model of the crack, and measured natural frequencies are obtained by using cracked beam frequency response and modal analysis. A hybrid particle swarm–Nelder–Mead (PS–NM) algorithm is used for estimating the crack location and depth. The hybrid PS–NM is made-up of a modified particle swarm optimization algorithm (PSO), aimed to identify the most promising areas, and a Nelder–Mead simplex algorithm (NM) for performing local search within these areas. The PS–NM results are compared with those obtained by the PSO, a hybrid genetic–Nelder–Mead algorithm (GA–NM) and a neural network (NN). The proposed PS–NM method outperforms other methods in terms of speed and accuracy. The average estimation errors for crack location and depth are (0.06%, 0%) for the PS–NM, however, (0.09%, 0%), (0.46%, 0.54%) and (0.39%, 1.66%) for the GA–NM, the PSO and the NN methods, respectively. To validate the proposed method and investigate the modeling and measurement errors some experimental results are also included. The average values of experimental location and depth estimation errors are (9.24%, 8.56%) for the PS–NM, but (9.64%, 9.50%), (10.89%, 10.89%), (11.53%, 11.64%) for the GA–NM, the PSO and the NN methods, respectively.     

课程表问题的一种模拟退火超启发式算法

课程表问题是经典的组合优化问题,属于NP-hard问题.长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法.在此基础上提出了一种基于多个图染色启发式规则的模拟退火超启发式算法.在超启发式算法的框架中,用模拟退火算法作为高层搜索算法,多个图染色启发式规则为底层的构造算法.与现有的方法相比,该算法具有很好的通用性,可以很容易推广到考试时间表、会议安排.旅行商问题、背包问题等应用领域.实验表明,该算法是可行有效的,且无一例时间、空间冲突.     

Parallel hyper heuristic algorithm based on reinforcement learning for the corridor allocation problem and parallel row ordering problem

Hyper heuristics is a relatively new optimisation algorithm. Numerous studies have reported that hyper heuristics are well applied in combinatorial optimisation problems. As a classic combinatorial optimisation problem, the row layout problem has not been publicly reported on applying hyper heuristics to its various sub-problems. To fill this gap, this study proposes a parallel hyper-heuristic approach based on reinforcement learning for corridor allocation problems and parallel row ordering problems. For the proposed algorithm, an outer layer parallel computing framework was constructed based on the encoding of the problem. The simulated annealing, tabu search, and variable neighbourhood algorithms were used in the algorithm as low-level heuristic operations, and Q-learning in reinforcement learning was used as a high-level strategy. A state space containing sequences and fitness values was designed. The algorithm performance was then evaluated for benchmark instances of the corridor allocation problem (37 groups) and parallel row ordering problem (80 groups). The results showed that, in most cases, the proposed algorithm provided a better solution than the best-known solutions in the literature. Finally, the meta-heuristic algorithm applied to three low-level heuristic operations is taken as three independent algorithms and compared with the proposed hyper-heuristic algorithm on four groups of parallel row ordering problem instances. The effectiveness of Q-learning in selection is illustrated by analysing the comparison results of the four algorithms and the number of calls of the three low-level heuristic operations in the proposed method.     

Structural inverse analysis by hybrid simplex artificial bee colony algorithms

A hybrid simplex artificial bee colony algorithm (HSABCA) which combines Nelder–Mead simplex method with artificial bee colony algorithm (ABCA) is proposed for inverse analysis problems. The proposed algorithm is applied to parameter identification of concrete dam-foundation systems. To verify the performance of HSABCA, it is compared with the basic ABCA and a real coded genetic algorithm (RCGA) on two examples: a gravity dam and an arc dam. Results show that the proposed algorithm is an efficient tool for inverse analysis and it performs much better than ABCA and RCGA on such problems.     

The parallel downhill simplex algorithm for unconstrained optimisation

In this paper we present a parallel implementation of a well-known heuristic optimisation algorithm (the downhill simplex algorithm developed by Nelder and Mead in 1965) which is well suited for unconstrained optimisation. We present the sequential algorithm as well as the parallel algorithm which we used to generate numerical results. They include numerical results of experiments on neural networks and a test suite of functions which demonstrate the parallel algorithm's increased robustness and convergence rate for high-dimensional problems compared to the sequential algorithm. © 1998 John Wiley & Sons, Ltd.     

Choice function based hyper-heuristics for multi-objective optimization

A selection hyper-heuristic is a high level search methodology which operates over a fixed set of low level heuristics. During the iterative search process, a heuristic is selected and applied to a candidate solution in hand, producing a new solution which is then accepted or rejected at each step. Selection hyper-heuristics have been increasingly, and successfully, applied to single-objective optimization problems, while work on multi-objective selection hyper-heuristics is limited. This work presents one of the initial studies on selection hyper-heuristics combining a choice function heuristic selection methodology with great deluge and late acceptance as non-deterministic move acceptance methods for multi-objective optimization. A well-known hypervolume metric is integrated into the move acceptance methods to enable the approaches to deal with multi-objective problems. The performance of the proposed hyper-heuristics is investigated on the Walking Fish Group test suite which is a common benchmark for multi-objective optimization. Additionally, they are applied to the vehicle crashworthiness design problem as a real-world multi-objective problem. The experimental results demonstrate the effectiveness of the non-deterministic move acceptance, particularly great deluge when used as a component of a choice function based selection hyper-heuristic.     

A greedy gradient-simulated annealing selection hyper-heuristic

Educational timetabling problem is a challenging real world problem which has been of interest to many researchers and practitioners. There are many variants of this problem which mainly require scheduling of events and resources under various constraints. In this study, a curriculum based course timetabling problem at Yeditepe University is described and an iterative selection hyper-heuristic is presented as a solution method. A selection hyper-heuristic as a high level methodology operates on the space formed by a fixed set of low level heuristics which operate directly on the space of solutions. The move acceptance and heuristic selection methods are the main components of a selection hyper-heuristic. The proposed hyper-heuristic in this study combines a simulated annealing move acceptance method with a learning heuristic selection method and manages a set of low level constraint oriented heuristics. A key goal in hyper-heuristic research is to build low cost methods which are general and can be reused on unseen problem instances as well as other problem domains desirably with no additional human expert intervention. Hence, the proposed method is additionally applied to a high school timetabling problem, as well as six other problem domains from a hyper-heuristic benchmark to test its level of generality. The empirical results show that our easy-to-implement hyper-heuristic is effective in solving the Yeditepe course timetabling problem. Moreover, being sufficiently general, it delivers a reasonable performance across different problem domains.     

Two effective hybrid metaheuristic algorithms for minimization of multimodal functions

Global optimization problems naturally arise from many applications. We propose two hybrid metaheuristic algorithms for finding a global optimum of a continuous function. Our proposed algorithms are hybridizations of genetic algorithm (GA) and variable neighbourhood search (VNS). To increase the efficiency of our algorithms, for smooth functions we present an effective locally improving line search procedure, and for non-smooth functions, we use the simplex method proposed by Nelder and Mead. By use of the recently adopted non-parametric statistical tests of Kruskal–Wallis and Mann–Whitney for analysing the behaviour of evolutionary algorithms, we compare both the efficiency and the effectiveness of our proposed algorithms with efficiently representative metaheuristic algorithms such as the multiagent GA proposed by Liang et al., the ant colony algorithm proposed by Toksari, and the VNS of Toksari and Güner on a variety of standard test functions. Computational experiments demonstrate that our proposed algorithms are efficiently effective.     

混合流水车间插单重调度的超启发式遗传算法

针对带有紧急订单的混合流水车间插单重调度问题,提出了一种双层编码的超启发式遗传算法。针对混合流水车间具有的订单排序和机器选择的双决策特征,在算法低层设计双层编码方案,在个体中表示订单排序和机器选择两类信息,对应一个唯一调度解,进而提出了12种排序和选择启发式对个体进行迭代优化;在算法高层采用自适应遗传算法,用来确定订单排序启发式和机器选择启发式的操作组合以及各组合执行的次序,并设计了自适应变异算子来优化算法的有效性。大规模数据实验的结果表明,所提算法具有很好的求解质量和求解效率。     

Agile optimization of a two‐echelon vehicle routing problem with pickup and delivery

In this paper, we consider a vehicle routing problem in which a fleet of homogeneous vehicles, initially located at a depot, has to satisfy customers' demands in a two‐echelon network: first, the vehicles have to visit intermediate nodes (e.g., a retail center or a consolidation center), where they deliver raw materials or bulk products and collect a number of processed items requested by the customers in their route; then, the vehicles proceed to complete their assigned routes, thus delivering the processed items to the final customers before returning to the depot. During this stage, vehicles might visit other intermediate nodes for reloading new items. In some real‐life scenarios, this problem needs to be solved in just a few seconds or even milliseconds, which leads to the concept of “agile optimization.” This might be the case in some rescue operations using drones in humanitarian logistics, where every second can be decisive to save lives. In order to deal with this real‐time two‐echelon vehicle routing problem with pickup and delivery, an original constructive heuristic is proposed. This heuristic is able to provide a feasible and reasonably good solution in just a few milliseconds. The constructive heuristic is extended into a biased‐randomized algorithm using a skewed probability distribution to modify its greedy behavior. This way, parallel runs of the algorithm are able to generate even better results without violating the real‐time constraint. Results show that the proposed methodology generates competitive results in milliseconds, being able to outperform other heuristics from the literature.     

A unified hyper-heuristic framework for solving bin packing problems

One- and two-dimensional packing and cutting problems occur in many commercial contexts, and it is often important to be able to get good-quality solutions quickly. Fairly simple deterministic heuristics are often used for this purpose, but such heuristics typically find excellent solutions for some problems and only mediocre ones for others. Trying several different heuristics on a problem adds to the cost. This paper describes a hyper-heuristic methodology that can generate a fast, deterministic algorithm capable of producing results comparable to that of using the best problem-specific heuristic, and sometimes even better, but without the cost of trying all the heuristics. The generated algorithm handles both one- and two-dimensional problems, including two-dimensional problems that involve irregular concave polygons. The approach is validated using a large set of 1417 such problems, including a new benchmark set of 480 problems that include concave polygons.     

A hybrid Improved Quantum-behaved Particle Swarm Optimization–Simplex method (IQPSOS) to solve power system load flow problems

This study proposes a new approach, based on a hybrid algorithm combining of Improved Quantum-behaved Particle Swarm Optimization (IQPSO) and simplex algorithms. The Quantum-behaved Particle Swarm Optimization (QPSO) algorithm is the main optimizer of algorithm, which can give a good direction to the optimal global region and Nelder Mead Simplex method (NM) which is used as a local search to fine tune the obtained solution from QPSO. The proposed improved hybrid QPSO algorithm is tested on several benchmark functions and performed better than particle swarm optimization (PSO), QPSO and weighted QPSO (WQPSO). To assess the effectiveness and feasibility of the proposed method on real problems, it is used for solving the power system load flow problems and demonstrated by different standard and ill-conditioned test systems including IEEE 14, 30 and 57 buses test systems, and compared with the conventional Newton–Raphson (NR) method, PSO and some versions of QPSO algorithms. Furthermore, the proposed hybrid algorithm is proposed for solving load flow problems with considering the reactive limits at generation buses. Simulation results prove the robustness and better convergence of IQPSOS under normal and critical conditions, when conventional load flow methods fail.     

Modified Nelder-Mead self organizing migrating algorithm for function optimization and its application

In this paper, a modified Nelder Mead Self Organizing Migrating Algorithm (mNM-SOMA) has been presented for solving unconstrained optimization problems. It is based on the hybridization of self organizing migrating algorithm (SOMA) with modified Nelder Mead (mNM) Crossover Operator. SOMA is a low population based technique that has good exploration and exploitation qualities, but sometimes converges premature to local optima solution due to lack of diversity preserve mechanism. In this paper an attempt has been made to improve the efficiency of SOMA using a modified NM crossover operator (mNM) for maintaining the diversity in the search space. mNM-SOMA has been tested on a set of 15 test problems, taken form literature and results are compared with the results obtained by self organizing migrating genetic algorithm (SOMGA), SOMA, genetic algorithm (GA) and particle swarm optimization (PSO). For better presentation, results are also analyzed graphically using a Performance Index. Besides this, mNM-SOMA has also been used to solve Frequency Modulation Sounds Parameter Identification Problem. Analysis of numerical results infers mNM-SOMA as a less expensive robust technique.     

Integrating neural networks and logistic regression to underpin hyper-heuristic search

A hyper-heuristic often represents a heuristic search method that operates over a space of heuristic rules. It can be thought of as a high level search methodology to choose lower level heuristics. Nearly 200 papers on hyper-heuristics have recently appeared in the literature. A common theme in this body of literature is an attempt to solve the problems in hand in the following way: at each decision point, first employ the chosen heuristic(s) to generate a solution, then calculate the objective value of the solution by taking into account all the constraints involved. However, empirical studies from our previous research have revealed that, under many circumstances, there is no need to carry out this costly 2-stage determination and evaluation at all times. This is because many problems in the real world are highly constrained with the characteristic that the regions of feasible solutions are rather scattered and small. Motivated by this observation and with the aim of making the hyper-heuristic search more efficient and more effective, this paper investigates two fundamentally different data mining techniques, namely artificial neural networks and binary logistic regression. By learning from examples, these techniques are able to find global patterns hidden in large data sets and achieve the goal of appropriately classifying the data. With the trained classification rules or estimated parameters, the performance (i.e. the worth of acceptance or rejection) of a resulting solution during the hyper-heuristic search can be predicted without the need to undertake the computationally expensive 2-stage of determination and calculation. We evaluate our approaches on the solutions (i.e. the sequences of heuristic rules) generated by a graph-based hyper-heuristic proposed for exam timetabling problems. Time complexity analysis demonstrates that the neural network and the logistic regression method can speed up the search significantly. We believe that our work sheds light on the development of more advanced knowledge-based decision support systems.