Hyperheuristics: Recent Developments

Nested Markov chain hyper-heuristic (NMHH): a hybrid hyper-heuristic framework for single-objective continuous problems

This article introduces a new hybrid hyper-heuristic framework that deals with single-objective continuous optimization problems. This approach employs a nested Markov chain on the base level in the search for the best-performing operators and their sequences and simulated annealing on the hyperlevel, which evolves the chain and the operator parameters. The novelty of the approach consists of the upper level of the Markov chain expressing the hybridization of global and local search operators and the lower level automatically selecting the best-performing operator sequences for the problem. Numerical experiments conducted on well-known benchmark functions and the comparison with another hyper-heuristic framework and six state-of-the-art metaheuristics show the effectiveness of the proposed approach.

Q-Learning-Based Hyperheuristic Evolutionary Algorithm for Dynamic Task Allocation of Crowdsensing

Task allocation is a crucial issue of mobile crowdsensing. The existing crowdsensing systems normally select the optimal participants giving no consideration to the sudden departure of mobile users, which significantly affects the sensing quality of tasks with a long sensing period. Furthermore, the ability of a mobile user to collect high-precision data is commonly treated as the same for different types of tasks, causing the unqualified data for some tasks provided by a competitive user. To address the issue, a dynamic task allocation model of crowdsensing is constructed by considering mobile user availability and tasks changing over time. Moreover, a novel indicator for comprehensively evaluating the sensing ability of mobile users collecting high-quality data for different types of tasks at the target area is proposed. A new Q -learning-based hyperheuristic evolutionary algorithm is suggested to deal with the problem in a self-learning way. Specifically, a memory-based initialization strategy is developed to seed a promising population by reusing participants who are capable of completing a particular task with high quality in the historical optima. In addition, taking both sensing ability and cost of a mobile user into account, a novel comprehensive strength-based neighborhood search is introduced as a low-level heuristic (LLH) to select a substitute for a costly participant. Finally, based on a new definition of the state, a Q -learning-based high-level strategy is designed to find a suitable LLH for each state. Empirical results of 30 static and 20 dynamic experiments expose that this hyperheuristic achieves superior performance compared to other state-of-the-art algorithms.

A competitive learning-based Grey wolf Optimizer for engineering problems and its application to multi-layer perceptron training

This article presents a competitive learning-based Grey Wolf Optimizer (Clb-GWO) formulated through the introduction of competitive learning strategies to achieve a better trade-off between exploration and exploitation while promoting population diversity through the design of difference vectors. The proposed method integrates population sub-division into majority groups and minority groups with a dual search system arranged in a selective complementary manner. The proposed Clb-GWO is tested and validated through the recent CEC2020 and CEC2019 benchmarking suites followed by the optimal training of multi-layer perceptron's (MLPs) with five classification datasets and three function approximation datasets. Clb-GWO is compared against the standard version of GWO, five of its latest variants and two modern meta-heuristics. The benchmarking results and the MLP training results demonstrate the robustness of Clb-GWO. The proposed method performed competitively compared to all its competitors with statistically significant performance for the benchmarking tests. The performance of Clb-GWO the classification datasets and the function approximation datasets was excellent with lower error rates and least standard deviation rates.

Agent State Flipping Based Hybridization of Heuristic Optimization Algorithms: A Case of Bat Algorithm and Krill Herd Hybrid Algorithm

This paper describes a unique meta-heuristic technique for hybridizing bio-inspired heuristic algorithms. The technique is based on altering the state of agents using a logistic probability function that is dependent on an agent’s fitness rank. An evaluation using two bio-inspired algorithms (bat algorithm (BA) and krill herd (KH)) and 12 optimization problems (cross-in-tray, rotated hyper-ellipsoid (RHE), sphere, sum of squares, sum of different powers, McCormick, Zakharov, Rosenbrock, De Jong No. 5, Easom, Branin, and Styblinski–Tang) is presented. Furthermore, an experimental evaluation of the proposed scheme using the industrial three-bar truss design problem is presented. The experimental results demonstrate that the hybrid scheme outperformed the baseline algorithms (mean rank for the hybrid BA-KH algorithm is 1.279 vs. 1.958 for KH and 2.763 for BA).

An Effective Approach for the Multiobjective Regional Low-Carbon Location-Routing Problem

In this paper, we consider a variant of the location-routing problem (LRP), namely the the multiobjective regional low-carbon LRP (MORLCLRP). The MORLCLRP seeks to minimize service duration, client waiting time, and total costs, which includes carbon emission costs and total depot, vehicle, and travelling costs with respect to fuel consumption, and considers three practical constraints: simultaneous pickup and delivery, heterogeneous fleet, and hard time windows. We formulated a multiobjective mixed integer programming formulations for the problem under study. Due to the complexity of the proposed problem, a general framework, named the multiobjective hyper-heuristic approach (MOHH), was applied for obtaining Pareto-optimal solutions. Aiming at improving the performance of the proposed approach, four selection strategies and three acceptance criteria were developed as the high-level heuristic (HLH), and three multiobjective evolutionary algorithms (MOEAs) were designed as the low-level heuristics (LLHs). The performance of the proposed approach was tested for a set of different instances and comparative analyses were also conducted against eight domain-tailored MOEAs. The results showed that the proposed algorithm produced a high-quality Pareto set for most instances. Additionally, extensive analyses were also carried out to empirically assess the effects of domain-specific parameters (i.e., fleet composition, client and depot distribution, and zones area) on key performance indicators (i.e., hypervolume, inverted generated distance, and ratio of nondominated individuals). Several management insights are provided by analyzing the Pareto solutions.

A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems

Hyper-heuristics are search methodologies that aim to provide high-quality solutions across a wide variety of problem domains, rather than developing tailor-made methodologies for each problem instance/domain. A traditional hyper-heuristic framework has two levels, namely, the high level strategy (heuristic selection mechanism and the acceptance criterion) and low level heuristics (a set of problem specific heuristics). Due to the different landscape structures of different problem instances, the high level strategy plays an important role in the design of a hyper-heuristic framework. In this paper, we propose a new high level strategy for a hyper-heuristic framework. The proposed high-level strategy utilizes a dynamic multiarmed bandit-extreme value-based reward as an online heuristic selection mechanism to select the appropriate heuristic to be applied at each iteration. In addition, we propose a gene expression programming framework to automatically generate the acceptance criterion for each problem instance, instead of using human-designed criteria. Two well-known, and very different, combinatorial optimization problems, one static (exam timetabling) and one dynamic (dynamic vehicle routing) are used to demonstrate the generality of the proposed framework. Compared with state-of-the-art hyper-heuristics and other bespoke methods, empirical results demonstrate that the proposed framework is able to generalize well across both domains. We obtain competitive, if not better results, when compared to the best known results obtained from other methods that have been presented in the scientific literature. We also compare our approach against the recently released hyper-heuristic competition test suite. We again demonstrate the generality of our approach when we compare against other methods that have utilized the same six benchmark datasets from this test suite.

A Case Study of Controlling Crossover in a Selection Hyper-heuristic Framework Using the Multidimensional Knapsack Problem

Hyper-heuristics are high-level methodologies for solving complex problems that operate on a search space of heuristics. In a selection hyper-heuristic framework, a heuristic is chosen from an existing set of low-level heuristics and applied to the current solution to produce a new solution at each point in the search. The use of crossover low-level heuristics is possible in an increasing number of general-purpose hyper-heuristic tools such as HyFlex and Hyperion. However, little work has been undertaken to assess how best to utilise it. Since a single-point search hyper-heuristic operates on a single candidate solution, and two candidate solutions are required for crossover, a mechanism is required to control the choice of the other solution. The frameworks we propose maintain a list of potential solutions for use in crossover. We investigate the use of such lists at two conceptual levels. First, crossover is controlled at the hyper-heuristic level where no problem-specific information is required. Second, it is controlled at the problem domain level where problem-specific information is used to produce good-quality solutions to use in crossover. A number of selection hyper-heuristics are compared using these frameworks over three benchmark libraries with varying properties for an NP-hard optimisation problem: the multidimensional 0-1 knapsack problem. It is shown that allowing crossover to be managed at the domain level outperforms managing crossover at the hyper-heuristic level in this problem domain.

A Reinforcement Learning - Great-Deluge Hyper-Heuristic for Examination Timetabling

Hyper-heuristics can be identified as methodologies that search the space generated by a finite set of low level heuristics for solving search problems. An iterative hyper-heuristic framework can be thought of as requiring a single candidate solution and multiple perturbation low level heuristics. An initially generated complete solution goes through two successive processes (heuristic selection and move acceptance) until a set of termination criteria is satisfied. A motivating goal of hyper-heuristic research is to create automated techniques that are applicable to a wide range of problems with different characteristics. Some previous studies show that different combinations of heuristic selection and move acceptance as hyper-heuristic components might yield different performances. This study investigates whether learning heuristic selection can improve the performance of a great deluge based hyper-heuristic using an examination timetabling problem as a case study.