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.     

On the investigation of hyper-heuristics on a financial forecasting problem

Financial forecasting is a really important area in computational finance, with numerous works in the literature. This importance can be reflected in the literature by the continuous development of new algorithms. Hyper-heuristics have been successfully used in the past for a number of search and optimization problems, and have shown very promising results. To the best of our knowledge, they have not been used for financial forecasting. In this paper we present pioneer work, where we use different hyper-heuristics frameworks to investigate whether we can improve the performance of a financial forecasting tool called EDDIE 8. EDDIE 8 allows the GP (Genetic Programming) to search in the search space of indicators for solutions, instead of using pre-specified ones; as a result, its search area has dramatically increased and sometimes solutions can be missed due to ineffective search. We apply 14 different low-level heuristics to EDDIE 8, to 30 different datasets, and examine their effect to the algorithm’s performance. We then select the most prominent heuristics and combine them into three different hyper-heuristics frameworks. Results show that all three frameworks are competitive, and are able to show significantly improved results, especially in the case of best results. Lastly, analysis on the weights of the heuristics shows that there can be a constant swinging among some of the low-level heuristics, which denotes that the hyper-heuristics frameworks are able to ‘know’ the appropriate time to switch from one heuristic to the other, based on their effectiveness.     

Population based Local Search for university course timetabling problems

Population based algorithms are generally better at exploring a search space than local search algorithms (i.e. searches based on a single heuristic). However, the limitation of many population based algorithms is in exploiting the search space. We propose a population based Local Search (PB-LS) heuristic that is embedded within a local search algorithm (as a mechanism to exploit the search space). PB-LS employs two operators. The first is applied to a single solution to determine the force between the incumbent solution and the trial current solution (i.e. a single direction force), whilst the second operator is applied to all solutions to determine the force in all directions. The progress of the search is governed by these forces, either in a single direction or in all directions. Our proposed algorithm is able to both diversify and intensify the search more effectively, when compared to other local search and population based algorithms. We use university course timetabling (Socha benchmark datasets) as a test domain. In order to evaluate the effectiveness of PB-LS, we perform a comparison between the performances of PB-LS with other approaches drawn from the scientific literature. Results demonstrate that PB-LS is able to produce statistically significantly higher quality solutions, outperforming many other approaches on the Socha dataset.     

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.     

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

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

A hybrid multi-population genetic algorithm for the dynamic facility layout problem

Due to inherent complexity of the dynamic facility layout problem, it has always been a challenging issue to develop a solution algorithm for this problem. For more than one decade, many researchers have proposed different algorithms for this problem. After reviewing the shortcomings of these algorithms, we realize that the performance can be further improved by a more intelligent search. This paper develops an effective novel hybrid multi-population genetic algorithm. Using a proposed heuristic procedure, we separate solution space into different parts and each subpopulation represents a separate part. This assures the diversity of the algorithm. Moreover, to intensify the search more and more, a powerful local search mechanism based on simulated annealing is developed. Unlike the available genetic operators previously proposed for this problem, we design the operators so as to search only the feasible space; thus, we save computational time by avoiding infeasible space. To evaluate the algorithm, we comprehensively discuss the parameter tuning of the algorithms by Taguchi method. The perfectly tuned algorithm is then compared with 11 available algorithms in the literature using well-known set of benchmark instances. Different analyses conducted on the results, show that the proposed algorithm enjoys the superiority and outperformance over the other algorithms.     

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.     

超启发算法研究进展综述

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

SAR image segmentation based on quantum-inspired multiobjective evolutionary clustering algorithm

The segmentation task in the feature space of an image can be formulated as an optimization problem. Recent researches have demonstrated that the clustering techniques, using only one objective may not obtain suitable solution because the single objective function just can provide satisfactory result to one kind of corresponding data set. In this letter, a novel multiobjective clustering approach, named a quantum-inspired multiobjective evolutionary clustering algorithm (QMEC), is proposed to deal with the problem of image segmentation, where two objectives are simultaneously optimized. Based on the concepts and principles of quantum computing, the multi-state quantum bits are used to represent individuals and quantum rotation gate strategy is used to update the probabilistic individuals. The proposed algorithm can take advantage of the multiobjective optimization mechanism and the superposition of quantum states, and therefore it has a good population diversity and search capabilities. Due to a set of nondominated solutions in multiobjective clustering problems, a simple heuristic method is adopted to select a preferred solution from the final Pareto front and the results show that a good image segmentation result is selected. Experiments on one simulated synthetic aperture radar (SAR) image and two real SAR images have shown the superiority of the QMEC over three other known algorithms.     

Combined Petri net modelling and AI-based heuristic hybrid search for flexible manufacturing systems—part II. Heuristic hybrid search

This two-part paper presents modelling and scheduling approaches of flexible manufacturing systems using Petri nets (PNs) and artificial intelligence (AI)-based heuristic search methods. In Part I, PN-based modelling approaches and basic AI-based heuristic search algorithms were presented. In Part II, a new heuristic function that exploits PN information is proposed. Heuristic information obtained from the PN model is used to dramatically reduce the search space. This heuristic is derived from a new concept, the resource cost reachability matrix, which builds on the properties of B-nets proposed in Part I. Two hybrid search algorithms, (1) an approach to model dispatching rules using analysis information provided by the PN simulation and (2) an approach of the modified stage-search algorithm, are proposed to reduce the complexity of large systems. A random problem generator is developed to test the proposed methods. The experimental results show promising results.     

A stochastic framework for K-SVD with applications on face recognition

In recent years, the sparse representation modeling of signals has received a lot of attention due to its state-of-the-art performance in different computer vision tasks. One important factor to its success is the ability to promote representations that are well adapted to the data. This is achieved by the use of dictionary learning algorithms. The most well known of these algorithms is K-SVD. In this paper, we propose a stochastic framework for K-SVD called \(\alpha\)K-SVD. The \(\alpha\)K-SVD uses a parameter \(\alpha\) to control a compromise between exploring the space of dictionaries and improving a possible solution. The use of this heuristic search strategy was motivated by the fact that K-SVD uses a greedy search algorithm with fast convergence, possibly leading to local minimum. Our approach is evaluated on two public face recognition databases. The results show that our approach yields better results than K-SVD and LC-KSVD (a K-SVD adaptation to classification) when the sparsity level is low.     

A framework for learning in search-based systems

We provide an overall framework for learning in search based systems that are used to find optimum solutions to problems. This framework assumes that prior knowledge is available in the form of one or more heuristic functions (or features) of the problem domain. An appropriate clustering strategy is used to partition the state space into a number of classes based on the available features. The number of classes formed will depend on the resource constraints of the system. In the training phase, example problems are run using a standard admissible search algorithm. In this phase, heuristic information corresponding to each class is learned. This new information can be used in the problem solving phase by appropriate search algorithms so that subsequent problem instances can be solved more efficiently. In this framework, we also show that heuristic information of forms other than the conventional single valued underestimate value can be used, since we maintain the heuristic of each class explicitly. We show some novel search algorithms that can work with some such forms. Experimental results have been provided for some domains     

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

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

GSO:基于图神经网络的深度学习计算图子图替换优化框架

深度学习在各种实际应用中取得了巨大成功,如何有效提高各种复杂的深度学习模型在硬件设备上的执行效率是该领域重要的研究内容之一.深度学习框架通常将深度学习模型表达为由基础算子构成的计算图,为了提高计算图的执行效率,传统的深度学习系统通常基于一些专家设计的子图替换规则,采用启发式搜索算法来优化计算图.它们的不足主要有:1)搜...     

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.     

Breakout Local Search for maximum clique problems

The maximum clique problem (MCP) is one of the most popular combinatorial optimization problems with various practical applications. An important generalization of MCP is the maximum weight clique problem (MWCP) where a positive weight is associate to each vertex. In this paper, we present Breakout Local Search (BLS) which can be applied to both MC and MWC problems without any particular adaptation. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. Extensive experimental evaluations using the DIMACS and BOSHLIB benchmarks show that the proposed approach competes favourably with the current state-of-art heuristic methods for MCP. Moreover, it is able to provide some new improved results for a number of MWCP instances. This paper also reports for the first time a detailed landscape analysis, which has been missing in the literature. This analysis not only explains the difficulty of several benchmark instances, but also justifies to some extent the behaviour of the proposed approach and the used parameter settings.     

基于动态奖惩的CDCL SAT求解器分支启发式算法

分支启发式算法在CDCL SAT求解器中有着非常重要的作用,传统的分支启发式算法在计算变量活性得分时只考虑了冲突次数而并未考虑决策层和冲突决策层所带来的影响。为了提高SAT问题的求解效率,受EVSIDS和ACIDS的启发,提出了基于动态奖惩DRPB的分支启发式算法。每当冲突发生时,DRPB通过综合考虑冲突次数、决策层、冲突决策层和变量冲突频率来更新变量活性得分。用DRPB替代VSIDS算法改进了Glucose 3.0,并测试了SATLIB基准库、2015年和2016年SAT竞赛中的实例。实验结果表明,与传统、单一的奖励变量分支策略相比,所提分支策略可以通过减少搜索树的分支和布尔约束传播次数来减小搜索树的规模并提高SAT求解器的性能。     

A path selection-based algorithm for real-time data staging in Grid applications

Efficient data scheduling is becoming an important issue in distributed real-time applications that produce huge data sets. The Grid environment on which these applications may run seeks to harness the geographically distributed resources for the applications. Scheduling components should account for real-time measures of the applications and reduce communication overhead due to enormous data size experienced, especially in dissemination applications. In this study, we consider the data staging scheme to provide the dissemination of large-scale data sets for the distributed real-time applications. We propose a new path selection-based algorithm for optimizing a criterion that reflects the general satisfiability of the system. The algorithm adopts a blocking-time analysis method combined with a simple heuristic to explore the most likely regions of a search space. Two heuristics are provided for the algorithm to explore these regions of the search space. Simulation results show that the proposed algorithm together with either of the heuristic has higher performance compared to other algorithms in the literature. We also show by simulation that a new optimization criterion we proposed in this study is successful in improving the performance of the individual applications.     

两种高效局部搜索算法求解RB模型实例

RB （revised B）模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型,提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法,该算法通过约束判断和违反约束数计分来进行搜索,并引入了基于约束违反概率的权重计算公式,根据其关联的约束权重进行修正,再对变量进行迭代调整。然后提出最小化值域的MDMCH算法,该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间,并在最小化后的变量域内重新校准变量赋值,进而有效提高算法的收敛速度。此外,还提出了融入模拟退火策略的WSCH和MDSCH算法,这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明,与多种启发式算法相比,这两种算法在精度与时间效率方面均呈现明显提升,在复杂难解的实例中能够提供高效的求解效率,验证了算法的有效性和优越性。     

Heuristic-Based Backtracking Relaxation for Propositional Satisfiability

In recent years backtrack search algorithms for propositional satisfiability (SAT) have been the subject of dramatic improvements. These improvements allowed SAT solvers to successfully solve instances with thousands or tens of thousands of variables. However, many new challenging problem instances are still too hard for current SAT solvers. As a result, further improvements to SAT technology are expected to have key consequences in solving hard real-world instances. This paper introduces a new idea: choosing the backtrack variable using a heuristic approach with the goal of diversifying the regions of the space that are explored during the search. The proposed heuristics are inspired by the heuristics proposed in recent years for the decision branching step of SAT solvers, namely, VSIDS and its improvements. Completeness conditions are established, which guarantee completeness for the new algorithm, as well as for any other incomplete backtracking algorithm. Experimental results on hundreds of instances derived from real-world problems show that the new technique is able to speed SAT solvers, while aborting fewer instances. These results clearly motivate the integration of heuristic backtracking in SAT solvers.