Search

The Set-Union Knapsack Problem (SUKP) is a complex combinatorial optimisation problem with applications in resource allocation, portfolio selection, and logistics. This paper presents a parallel local search algorithm for solving SUKP on the Compute Unified Device Architecture (CUDA) platform in Graphics Processing Units (GPUs). The proposed method employs a compact algorithm that divides the search space into smaller regions. For diversity, each thread in a GPU block starts the search process from a different location in a region using a different initial solution. Each thread then searches the local optimum by utilising communication between individuals through a crossover operator exploiting the best solution within the GPU block. Through extensive experiments on a set of SUKP benchmark instances ranging in size from small to large, we demonstrate the effectiveness of the proposed algorithm in finding high-quality solutions within comparable time frames. Furthermore, a comparative performance analysis with the current state-of-the-art SUKP algorithms reveals the competitive advantage of the proposed method. The GPU-based parallel local search algorithm using uniform crossover is a valuable addition to the repertoire of algorithms addressing SUKP, highlighting its potential for practical applications in real-world decision-making scenarios. [ABSTRACT FROM AUTHOR]

When designing sound packages, often fully filling the available space with acoustic materials is not the most absorbing solution. Better solutions can be obtained by creating cavities of air pockets, but determining the most optimal shape and topology that maximises sound absorption is a computationally challenging task. Many recent topology optimisation applications in acoustics use heuristic methods such as solid-isotropic-material-with-penalisation (SIMP) to quickly find near-optimal solutions. This study investigates seven heuristic and metaheuristic optimisation approaches including SIMP applied to topology optimisation of acoustic porous materials for absorption maximisation. The approaches tested are hill climbing, constructive heuristics, SIMP, genetic algorithm, tabu search, covariance-matrix-adaptation evolution strategy (CMA-ES), and differential evolution. All the algorithms are tested on seven benchmark problems varying in material properties, target frequencies, and dimensions. The empirical results show that hill climbing, constructive heuristics, and a discrete variant of CMA-ES outperform the other algorithms in terms of the average quality of solutions over the different problem instances. Though gradient-based SIMP algorithms converge to local optima in some problem instances, they are computationally more efficient. One of the general lessons is that different strategies explore different regions of the search space producing unique sets of solutions. [ABSTRACT FROM AUTHOR]

In simultaneous multithreaded (SMT) processors, various data path resources are concurrently shared by many threads. A few heuristic approaches that explicitly distribute those resources among threads with the goal of improved overall performance have already been proposed. A selection hyperheuristic is a high-level search methodology that mixes a predetermined set of heuristics in an iterative framework to utilize their strengths for solving a given problem instance. In this study, we propose a set of selection hyperheuristics for selecting and executing the heuristic with the best performance at a given stage. To the best of our knowledge, this is one of the first studies implementing a hyperheuristic algorithm on hardware. The results of our experimental study show that hyperheuristics are indeed capable of improving the performance of the studied workloads. Our best performing hyperheuristic achieves better throughput than both baseline heuristics in 5 out of 12 workloads and gives about 15% peak performance gain. The average performance gains over the well-known hill-climbing and adaptive resource partitioning heuristics are about 5% and 2%, respectively. [ABSTRACT FROM AUTHOR]

A crew pairing represents a sequence of flight legs that constitute a crew work allocation, starting and ending at the same crew base. A complete set of crew pairings covers all flight legs in the timetable of an airline for a given planning horizon. That determines the rosters for the crew and their quality, since those pairings would potentially include layovers, deadheads and connection times which are the key factors which directly contribute to the operational crew costs. Considering that crew costs form the second largest bit in the overall operational cost, generating optimized crew pairings is a vital process for the airline companies. In this study, a score-based adaptive greedy heuristic and a genetic algorithm are presented for solving large scale instances of airline crew pairing problems. Both solution methods are applied to a set of real-world problem instances from Turkish Airlines which is one of the largest carriers in the world. The empirical results show that the proposed approaches are indeed capable of generating high quality solutions for crew pairing, even for the large scale problem instances. • An adaptive greedy heuristic for large scale airline crew pairing problems is improved. • A score-based adaptive greedy heuristic and a genetic algorithm are presented. • Solution methods are applied to a set of real-world problem instances from Turkish Airlines. [ABSTRACT FROM AUTHOR]

Construction heuristics play an important role in solving combinatorial optimization problems. These heuristics are usually used to create an initial solution to the problem which is improved using optimization techniques such as metaheuristics. For examination timetabling and university course timetabling problems essentially graph colouring heuristics have been used for this purpose. The process of deriving heuristics manually for educational timetabling is a time consuming task. Furthermore, according to the no free lunch theorem different heuristics will perform well for different problems and problem instances. Hence, automating the induction of construction heuristics will reduce the man hours involved in creating such heuristics, allow for the derivation of problem specific heuristics and possibly result in the derivation of heuristics that humans have not thought of. This paper presents generation construction hyper-heuristics for educational timetabling. The study investigates the automatic induction of two types of construction heuristics, namely, arithmetic heuristics and hierarchical heuristics. Genetic programming is used to evolve arithmetic heuristics. Genetic programming, genetic algorithms and the generation of random heuristic combinations is examined for the generation of hierarchical heuristics. The hyper-heuristics generating both types of heuristics are applied to the examination timetabling and the curriculum based university course timetabling problems. The evolved heuristics were found to perform much better than the existing graph colouring heuristics used for this domain. Furthermore, it was found that the while the arithmetic heuristics were more effective for the examination timetabling problem, the hierarchical heuristics produced better results than the arithmetic heuristics for the curriculum based course timetabling problem. Genetic algorithms proved to be the most effective at inducing hierarchical heuristics. [ABSTRACT FROM AUTHOR]

The majority of the studies that generate test cases for graphical user interface (GUI) applications are based on or address functional requirements only. In spite of the fact that interesting approaches have been proposed, they do not address functional and non-functional requirements of the GUI systems, and non-functional properties of the created test suites altogether to generate test cases. This is called a many-objective perspective where several desirable and different characteristics are considered together to generate the test cases. In this study, we show how to combine search-based (optimisation) with model-based testing to generate test cases for GUI applications taking into account the many-objective perspective. We rely on meta and hyper-heuristics and we address two particular issues (problems) considering code-driven and use case-driven GUI testing. As for the code-driven testing, we target desktop applications and automatically read the C++ source code of the system, translate it into an event flow graph (EFG), and use objective functions that are graph-based measures. As for the use case-driven testing, EFGs are created directly via use cases. A rigorous evaluation was performed using 32 problem instances where we considered three multi-objective evolutionary algorithms and six selection hyper-heuristics using those algorithms as low-level (meta)heuristics. The performance of the algorithms was compared based on five different indicators, and also a new Multi-Metric Indicator (MMI) utilising multiple indicators and providing a unique measure for all algorithms. Results show that the metaheuristics obtained better performances overall, particularly NSGA-II, while Choice Function was the most outstanding hyper-heuristic approach. • Use of search-based and model-based testing to create many-objective test cases. • Three metaheuristics and six selection hyper-heuristics were considered. • Evaluation was performed considering 32 graphical user interface problem instances. • Evaluation relied on 5 quality indicators and a new proposed Multi- Metric Indicator. • Metaheuristics performed better than hyper-heuristics for these problems. [ABSTRACT FROM AUTHOR]

The online bin packing problem is a well-known bin packing variant and which requires immediate decisions to be made for the placement of a lengthy sequence of arriving items of various sizes one at a time into fixed capacity bins without any overflow. The overall goal is maximising the average bin fullness. We investigate a ‘policy matrix’ representation, which assigns a score for each decision option independently and the option with the highest value is chosen, for one-dimensional online bin packing. A policy matrix might also be considered as a heuristic with many parameters, where each parameter value is a score. We hence effectively investigate a framework which can be used for creating heuristics via many parameters. The proposed framework combines a Genetic Algorithm optimiser, which searches the space of heuristics in policy matrix form, and an online bin packing simulator, which acts as the evaluation function. The empirical results indicate the success of the proposed approach, providing the best solutions for almost all item sequence generators used during the experiments. We also present a novel fitness landscape analysis on the search space of policies. This study hence gives evidence of the potential for automated discovery by intelligent systems of powerful heuristics for online problems; reducing the need for expensive use of human expertise. [ABSTRACT FROM AUTHOR]

Automating high school timetabling is a challenging task. This problem is a well known hard computational problem which has been of interest to practitioners as well as researchers. High schools need to timetable their regular activities once per year, or even more frequently. The exact solvers might fail to find a solution for a given instance of the problem. A selection hyper-heuristic can be defined as an easy-to-implement, easy-to-maintain and effective 'heuristic to choose heuristics' to solve such computationally hard problems. This paper describes the approach of the team hyper-heuristic search strategies and timetabling (HySST) to high school timetabling which competed in all three rounds of the third international timetabling competition. HySST generated the best new solutions for three given instances in Round 1 and gained the second place in Rounds 2 and 3. It achieved this by using a fairly standard stochastic search method but significantly enhanced by a selection hyper-heuristic with an adaptive acceptance mechanism. [ABSTRACT FROM AUTHOR]

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 hyperheuristics 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. [ABSTRACT FROM AUTHOR]

High school timetabling is one of those recurring NP-hard real-world combinatorial optimisation problems that has to be dealt with by many educational institutions periodically, and so has been of interest to practitioners and researchers. Solving a high school timetabling problem requires scheduling of resources and events into time slots subject to a set of constraints. Recently, an international competition, referred to as ITC 2011 was organised to determine the state-of-the-art approach for high school timetabling. The problem instances, obtained from eight different countries across the world used in this competition became a benchmark for further research in the field. Selection hyper-heuristics are general-purpose improvement methodologies that control/mix a given set of low level heuristics during the search process. In this study, we evaluate the performance of a range of selection hyper-heuristics combining different reusable components for high school timetabling. The empirical results show the success of the approach which embeds an adaptive great-deluge move acceptance method on the ITC 2011 benchmark instances. This selection hyper-heuristic ranks the second among the previously proposed approaches including the ones competed at ITC 2011. [ABSTRACT FROM AUTHOR]

Grouping problems are hard to solve combinatorial optimisation problems which require partitioning of objects into a minimum number of subsets while a given objective is simultaneously optimised. Selection hyper-heuristics are high level general purpose search methodologies that operate on a space formed by a set of low level heuristics rather than solutions. Most of the recently proposed selection hyper-heuristics are iterative and make use of two key methods which are employed successively; heuristic selection and move acceptance. In this study, we present a novel generic selection hyper-heuristic framework containing a fixed set of reusable grouping low level heuristics and an unconventional move acceptance mechanism for solving grouping problems. This framework deals with one solution at a time at any given decision point during the search process. Also, a set of high quality solutions, capturing the trade-off between the number of groups and the additional objective for the given grouping problem, is maintained. The move acceptance mechanism embeds a local search approach which is capable of progressing improvements on those trade-off solutions. The performance of different selection hyper-heuristics with various components under the proposed framework is investigated on graph colouring as a representative grouping problem. Then, the top performing hyper-heuristics are applied to a benchmark of examination timetabling instances. The empirical results indicate the effectiveness and generality of the proposed framework enabling grouping hyper-heuristics to achieve high quality solutions in both domains. [ABSTRACT FROM AUTHOR]

A square matrix of distinct numbers in which every row, column and both diagonals have the same total is referred to as a magic square. Constructing a magic square of a given order is considered a difficult computational problem, particularly when additional constraints are imposed. Hyper-heuristics are emerging high-level search methodologies that explore the space of heuristics for solving a given problem. In this study, we present a range of effective selection hyper-heuristics mixing perturbative low-level heuristics for constructing the constrained version of magic squares. The results show that selection hyper-heuristics, even the non-learning ones deliver an outstanding performance, beating the best-known heuristic solution on average. [ABSTRACT FROM PUBLISHER]

Meta-heuristics such as simulated annealing, genetic algorithms and tabu search have been successfully applied to many difficult optimization problems for which no satisfactory problem specific solution exists. However, expertise is required to adopt a meta-heuristic for solving a problem in a certain domain. Hyper-heuristics introduce a novel approach for search and optimization. A hyper-heuristic method operates on top of a set of heuristics. The most appropriate heuristic is determined and applied automatically by the technique at each step to solve a given problem. Hyper-heuristics are therefore assumed to be problem independent and can be easily utilized by non-experts as well. In this study, a comprehensive analysis is carried out on hyper-heuristics. The best method is tested against genetic and memetic algorithms on fourteen benchmark functions. Additionally, new hyper-heuristic frameworks are evaluated for questioning the notion of problem independence. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a multi-objective selection hyper-heuristic approach combining Reinforcement Learning, (meta)heuristic selection, and group decision-making as acceptance methods, referred to as Hyper-Heuristic based on Reinforcement LearnIng, Balanced Heuristic Selection and Group Decision AccEptance (HRISE), controlling a set of Multi-Objective Evolutionary Algorithms (MOEAs) as Low-Level (meta)Heuristics (LLHs). Along with the use of multiple MOEAs, we believe that having a robust LLH selection method as well as several move acceptance methods at our disposal would lead to an improved general-purpose method producing most adequate solutions to the problem instances across multiple domains. We present two learning hyper-heuristics based on the HRISE framework for multi-objective optimisation, each embedding a group decision-making acceptance method under a different rule: majority rule (HRISE_M) and responsibility rule (HRISE_R). A third hyper-heuristic is also defined where both a random LLH selection and a random move acceptance strategy are used. We also propose two variants of the late acceptance method and a new quality indicator supporting the initialisation of selection hyper-heuristics using low computational budget. An extensive set of experiments were performed using 39 multi-objective problem instances from various domains where 24 are from four different benchmark function classes, and the remaining 15 instances are from four different real-world problems. The cross-domain search performance of the proposed learning hyper-heuristics indeed turned out to be the best, particularly HRISE_R, when compared to three other selection hyper-heuristics, including a recently proposed one, and all low-level MOEAs each run in isolation. • Proposed three selection hyper-heuristics for multi-objective optimisation. • Hyper-heuristics embed reinforcement learning and group decision-making acceptance. • A new quality indicator and two new Late Acceptance variants are presented. • Dynamic control mechanism for running multi-objective evolutionary algorithms. • Best performance across 39 synthetic and real-world multi-objective problem instances. [ABSTRACT FROM AUTHOR]