超启发算法研究进展综述

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

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.     

Hyper-heuristics with low level parameter adaptation

Recent years have witnessed the great success of hyper-heuristics applying to numerous real-world applications. Hyper-heuristics raise the generality of search methodologies by manipulating a set of low level heuristics (LLHs) to solve problems, 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 paper, we show how to automatically maintain low level parameters (LLPs) using a hyper-heuristic with LLP adaptation (AD-HH), and exemplify the feasibility of AD-HH by adaptively maintaining the LLPs for two hyper-heuristic models. 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 SAR mechanism is able to explore the heuristic space more effectively and efficiently. To evaluate the performance of the proposed algorithms, we choose the p-median problem as a case study. The empirical results show that with the adaptation of the LLPs and the SAR mechanism, the proposed algorithms are able to achieve competitive results over the three heterogeneous classes of benchmark instances.     

An investigation on the generality level of selection hyper-heuristics under different empirical conditions

The present study concentrates on the generality of selection hyper-heuristics across various problem domains with a focus on different heuristic sets in addition to distinct experimental limits. While most hyper-heuristic research employs the term generality in describing the potential for solving various problems, the performance changes across different domains are rarely reported. Furthermore, a hyper-heuristic's performance study purely on the topic of heuristic sets is uncommon. Similarly, experimental limits are generally ignored when comparing hyper-heuristics. In order to demonstrate the effect of these generality related elements, nine heuristic sets with different improvement capabilities and sizes were generated for each of three target problem domains. These three problem domains are home care scheduling, nurse rostering and patient admission scheduling. Fourteen hyper-heuristics with varying intensification/diversification characteristics were analysed under various settings. Empirical results indicate that the performance of selection hyper-heuristics changes significantly under different experimental conditions.     

A hybrid multi-population framework for dynamic environments combining online and offline learning

Population based incremental learning algorithms and selection hyper-heuristics are highly adaptive methods which can handle different types of dynamism that may occur while a given problem is being solved. In this study, we present an approach based on a multi-population framework hybridizing these methods to solve dynamic environment problems. A key feature of the hybrid approach is the utilization of offline and online learning methods at successive stages. The performance of our approach along with the influence of different heuristic selection methods used within the selection hyper-heuristic is investigated over a range of dynamic environments produced by a well known benchmark generator as well as a real world problem, referred to as the Unit Commitment Problem. The empirical results show that the proposed approach using a particular hyper-heuristic outperforms some of the best known approaches in literature on the dynamic environment problems dealt with.     

Grammar-based generation of variable-selection heuristics for constraint satisfaction problems

We propose a grammar-based genetic programming framework that generates variable-selection heuristics for solving constraint satisfaction problems. This approach can be considered as a generation hyper-heuristic. A grammar to express heuristics is extracted from successful human-designed variable-selection heuristics. The search is performed on the derivation sequences of this grammar using a strongly typed genetic programming framework. The approach brings two innovations to grammar-based hyper-heuristics in this domain: the incorporation of if-then-else rules to the function set, and the implementation of overloaded functions capable of handling different input dimensionality. Moreover, the heuristic search space is explored using not only evolutionary search, but also two alternative simpler strategies, namely, iterated local search and parallel hill climbing. We tested our approach on synthetic and real-world instances. The newly generated heuristics have an improved performance when compared against human-designed heuristics. Our results suggest that the constrained search space imposed by the proposed grammar is the main factor in the generation of good heuristics. However, to generate more general heuristics, the composition of the training set and the search methodology played an important role. We found that increasing the variability of the training set improved the generality of the evolved heuristics, and the evolutionary search strategy produced slightly better results.     

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.     

Contrasting meta-learning and hyper-heuristic research: the role of evolutionary algorithms

The fields of machine meta-learning and hyper-heuristic optimisation have developed mostly independently of each other, although evolutionary algorithms (particularly genetic programming) have recently played an important role in the development of both fields. Recent work in both fields shares a common goal, that of automating as much of the algorithm design process as possible. In this paper we first provide a historical perspective on automated algorithm design, and then we discuss similarities and differences between meta-learning in the field of supervised machine learning (classification) and hyper-heuristics in the field of optimisation. This discussion focuses on the dimensions of the problem space, the algorithm space and the performance measure, as well as clarifying important issues related to different levels of automation and generality in both fields. We also discuss important research directions, challenges and foundational issues in meta-learning and hyper-heuristic research. It is important to emphasize that this paper is not a survey, as several surveys on the areas of meta-learning and hyper-heuristics (separately) have been previously published. The main contribution of the paper is to contrast meta-learning and hyper-heuristics methods and concepts, in order to promote awareness and cross-fertilisation of ideas across the (by and large, non-overlapping) different communities of meta-learning and hyper-heuristic researchers. We hope that this cross-fertilisation of ideas can inspire interesting new research in both fields and in the new emerging research area which consists of integrating those fields.     

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

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

一种基于动态决策块的超启发式跨单元调度方法

对运输能力受限条件下的跨单元调度问题进行分析, 提出一种基于动态决策块和蚁群优化 (Ant colony optimization, ACO) 的超启发式方法, 同时解决跨单元生产调度和运输调度问题. 在传统超启发式方法的基础上, 采用动态决策块策略, 通过蚁群算法合理划分决策块, 并为决策块选择合适的规则. 实验表明, 采用动态决策块策略的超启发式方法比传统的超启发式方法具有更好的性能, 本文所提的方法在最小化加权延迟总和目标方面有较好的优化能力 并且具有较高的计算效率.     

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.     

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.     

进化式超启发算法求解多车型低碳选址-路径问题

为了降低物流配送成本和减少CO$_2$排放量,提出一种综合考虑多车型和同时取送货的低碳选址-路径问题,并构建三维指数混合整数规划模型.针对所提问题,设计一种进化式超启发式求解算法,即在超启发式算法框架下,采用进化式策略作为高层学习策略,以实时准确地监控底层算子的性能信息并选择合适的底层算子,包括量子选择、蚂蚁策略、蛙跳机制以及自然竞争等.同时,挖掘算子性能信息以构建自适应接收机制,引导全局搜索,加快算法收敛速度.通过对不同规模实例的仿真实验与对比分析,验证了4种进化式超启发式算法在求解物流配送多车型同时取送货低碳选址-路径问题模型上的有效性与鲁棒性.     

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.     

An evolutionary-based hyper-heuristic approach for the Jawbreaker puzzle

In this paper a hyper-heuristic algorithm is designed and developed for its application to the Jawbreaker puzzle. Jawbreaker is an addictive game consisting in a matrix of colored balls, that must be cleared by popping sets of balls of the same color. This puzzle is perfect to be solved by applying hyper-heuristics algorithms, since many different low-level heuristics are available, and they can be applied in a sequential fashion to solve the puzzle. We detail a set of low-level heuristics and a global search procedure (evolutionary algorithm) that conforms to a robust hyper-heuristic, able to solve very difficult instances of the Jawbreaker puzzle. We test the proposed hyper-heuristic approach in Jawbreaker puzzles of different size and difficulty, with excellent results.     

超启发式交叉熵算法求解分布式装配柔性作业车间调度问题

本文针对一类新型两阶段分布式装配柔性作业车间调度问题(DAFJSP),建立问题模型,以最小化最大完工时间为优化目标并提出一种超启发式交叉熵算法(HHCEA)进行求解.首先,设计基于工序序列、工厂分配和产品序列的三维向量编码规则和结合贪婪策略的解码规则,同时提出4种启发式方法以提高初始解的质量.然后,设计高低分层结构的HHCEA,高层为提高对搜索方向的引导性,采用交叉熵算法(CEA)学习和积累优质排列的信息,其中各排列由结合问题特点设计的11种启发式操作(即11种有效的邻域操作)构成;低层为增加在解空间中的搜索深度,将高层确定的每个排列中的启发式操作依次重复执行指定次数并在执行过程中加入基于模拟退火的扰动机制,以此作为一种新的启发式方法执行搜索.最后,通过仿真实验与算法对比验证HHCEA可有效求解DAFJSP.     

A hyper-heuristic approach to aircraft structural design optimization

The conceptual design of an aircraft is a challenging problem in which optimization can be of great importance to the quality of design generated. Mass optimization of the structural design of an aircraft aims to produce an airframe of minimal mass whilst maintaining satisfactory strength under various loading conditions due to flight and ground manoeuvres. Hyper-heuristic optimization is an evolving field of research wherein the optimization process is continuously adapted in order to provide greater improvements in the quality of the solution generated. The relative infancy of hyper-heuristic optimization has resulted in limited application within the field of aerospace design. This paper describes a framework for the mass optimization of the structural layout of an aircraft at the conceptual level of design employing a novel hyper-heuristic approach. This hyper-heuristic approach encourages solution space exploration, thus reducing the likelihood of premature convergence, and improves the feasibility of and convergence upon the best solution found. A case study is presented to illustrate the effects of hyper-heuristics on the problem for a large commercial aircraft. Resulting solutions were generated of considerably lighter mass than the baseline aircraft. A further improvement in solution quality was found with the use of the hyper-heuristics compared to that obtained without, albeit with a penalty on computation time.     

超启发式遗传算法求解模糊柔性作业车间调度

本文提出一种混合超启发式遗传算法(HHGA),用于求解一类采用三角模糊数表示工件加工时间的模糊柔性作业车间调度问题(FFJSP),优化目标为最小化最大模糊完工时间(即makespan).首先,详细分析现有三角模糊数排序准则性质,并充分考虑取大操作的近似误差和模糊度,设计一种更为准确的三角模糊数排序准则,可合理计算FFJSP和其他各类调度问题解的目标函数值.其次,为实现对FFJSP解空间不同区域的有效搜索,HHGA将求解过程分为两层,高层利用带自适应变异算子的遗传算法对6种特定操作(即6种有效邻域操作)的排列进行优化;低层将高层所得的每种排列作为一种启发式算法,用于对低层相应个体进行操作来执行紧凑的变邻域局部搜索并生成新个体,同时加入模拟退火机制来避免搜索陷入局部极小.最后,仿真实验和算法比较验证了所提排序准则和HHGA的有效性.     

基于单亲遗传禁忌搜索算法的手术排程问题研究

针对规模较大的手术排程问题,分别以所有病人完成手术过程的最长时间和平均时间最小化为目标,构建了手术排程问题的数学模型。在分析解的最优化条件基础上,设计了一种将单亲遗传算法与禁忌搜索算法相结合的混合优化算法。按照个体的优劣及算法迭代情况设计了一种自适应选择机制,使个体自适应地选择执行变异操作或禁忌搜索算法。最后,仿真实验结果表明了所提算法的有效性和自适应选择机制的可行性。     

An evolutionary hyper-heuristic to optimise deep belief networks for image reconstruction

Deep Belief Networks (DBN) have become a powerful tools to deal with a wide range of applications. On complex tasks like image reconstruction, DBN’s performance is highly sensitive to parameter settings. Manually trying out different parameters is tedious and time consuming however often required in practice as there are not many better options. This work proposes an evolutionary hyper-heuristic framework for automatic parameter optimisation of DBN. The hyper-heuristic framework introduced here is the first of its kind in this domain. It involves a high level strategy and a pool of evolutionary operators such as crossover and mutation to generates DBN parameter settings by perturbing or modifying the current setting of a DBN. Providing a large set of operators could be beneficial to form a more effective high level strategy, but in the same time would increase the search space hence make it more difficulty to form a good strategy. To address this issue, a non-parametric statistical test is introduced to identify a subset of effective operators for different phases of the hyper-heuristic search. Three well-known image reconstruction datasets were used to evaluate the performance of the proposed framework. The results reveal that the proposed hyper-heuristic framework is very competitive when compared to the state of art methods.