Source-linked AI summary
HyFlex: A Benchmark Framework for Cross-domain Heuristic Search
Edmund Burke, Tim Curtois, Matthew Hyde, Gabriela Ochoa, Jose A. Vazquez-Rodriguez
TL;DR
Adaptive heuristic search methods need broader cross-domain testing, but implementing domain-specific components limits available evaluations. HyFlex provides a modular common interface and four implemented domains, enabling general-purpose methods to be developed and compared; its experiments show no single algorithm dominates all four domains, while the framework supported substantial community participation.
Problem
Adaptive heuristic methodologies are difficult to test across many combinatorial-optimization domains because implementing domain-specific software components requires substantial effort.
Method
HyFlex separates general-purpose search algorithms from problem-specific components through a common framework containing reusable interfaces, domains, instances, and search operators.
Results
No one of three evaluated algorithms is superior across all four problem domains, while HyFlex enabled cross-domain experiments without domain- or instance-specific tuning.
Takeaways & Limitations
HyFlex provides a benchmark for developing and reliably comparing self-configuring search heuristics across domains, with reported use by an international research community.
Takeaways & Limitations
The current interface can be extended with new domains, additional instances and operators, multi-objective and dynamic problems, and further domain feedback.
Abstract
from arXiv · showhide
Automating the design of heuristic search methods is an active research field within computer science, artificial intelligence and operational research. In order to make these methods more generally applicable, it is important to eliminate or reduce the role of the human expert in the process of designing an effective methodology to solve a given computational search problem. Researchers developing such methodologies are often constrained on the number of problem domains on which to test their adaptive, self-configuring algorithms; which can be explained by the inherent difficulty of implementing their corresponding domain specific software components. This paper presents HyFlex, a software framework for the development of cross-domain search methodologies. The framework features a common software interface for dealing with different combinatorial optimisation problems, and provides the algorithm components that are problem specific. In this way, the algorithm designer does not require a detailed knowledge the problem domains, and thus can concentrate his/her efforts in designing adaptive general-purpose heuristic search algorithms. Four hard combinatorial problems are fully implemented (maximum satisfiability, one dimensional bin packing, permutation flow shop and personnel scheduling), each containing a varied set of instance data (including real-world industrial applications) and an extensive set of problem specific heuristics and search operators. The framework forms the basis for the first International Cross-domain Heuristic Search Challenge (CHeSC), and it is currently in use by the international research community. In summary, HyFlex represents a valuable new benchmark of heuristic search generality, with which adaptive cross-domain algorithms are being easily developed, and reliably compared.
1 Introduction
HyFlex addresses limited cross-domain evaluation of adaptive heuristic methods by separating reusable general-purpose search logic from problem-specific components and providing a common framework.
- Automated heuristic design seeks to reduce human expertise while enabling self-managed methods to adapt to changing problem or search-space conditions.
- Researchers are constrained in testing adaptive methodologies because implementing problem models, representations, evaluations, and search operators across domains is difficult and labor-intensive.
- HyFlex is proposed as a modular, flexible Java class library for designing and testing iterative heuristic search algorithms across multiple problem domains.
- The framework supports hyper-heuristics, adaptive memetic algorithms, adaptive operator selection, reactive search, and variable neighborhood search.
- CHeSC runs submitted high-level strategies through HyFlex’s common interface, using shared representations and operators while evaluating hidden instances and domains.
2 The HyFlex Framework
HyFlex modularizes heuristic search by separating general-purpose algorithms from problem-specific domains, exposing reusable solution-management and heuristic interfaces that simplify cross-domain development.
- Overview of HyFlex: HyFlex is designed to develop, test, and compare iterative general-purpose heuristic search algorithms such as hyper-heuristics.
- Overview of HyFlex: The framework separates a general-purpose hyper-heuristic from a problem-specific component supplied by HyFlex.
- Overview of HyFlex: HyFlex extends the domain-barrier concept with a population of solutions and a richer variety of problem-specific heuristics and search operators.
- The ProblemDomain Class: The ProblemDomain interface provides configurable solution memory, random initialization, and problem-specific heuristics invoked through applyHeuristic(i, j, k).
- The ProblemDomain Class: Problem-specific operators include mutation, ruin-recreate, hill-climbing or local search, and crossover, each offering a distinct way to modify solutions.
- An Example Hyper-Heuristic: Only the solve() method and a one-line toString() method are needed to implement a hyper-heuristic, according to the example.
- Summary of HyFlex Description: HyFlex lets developers avoid domain expertise and focus on hyper-heuristic methodologies that can be evaluated across problem domains.
3 HyFlex Problem Domains
HyFlex currently implements four problem-domain modules, each with training instances and problem-specific heuristics for cross-domain search research.
- The implemented domains are maximum satisfiability, one-dimensional bin packing, permutation flow shop, and personnel scheduling.
- Each domain includes 10 training instances from different sources and problem-specific heuristics of the framework’s supported types.
3.1 Maximum Satisfiability (MAX-SAT)
HyFlex’s MAX-SAT module models clause satisfaction, evaluates solutions by broken clauses, and supplies nine search operators spanning several heuristic categories.
- Problem formulation: MAX-SAT seeks an assignment satisfying the maximum number of clauses, or equivalently minimizing the number of unsatisfied clauses.
- Solution initialisation and objective function: Solutions are initialized by randomly assigning true or false values to Boolean variables, and fitness returns the number of broken clauses.
- Search operators: The MAX-SAT domain contains 9 search operators, with net gain, positive gain, negative gain, and variable age used in their definitions.
- Mutational heuristics: Mutational operators include GSAT, HSAT, WalkSAT, and Novelty, which select variables using gain, age, broken-clause, or probabilistic rules.
- Ruin-recreate and local search heuristics: Ruin-recreate reinitializes a proportion of variables, while local-search operators use first-improvement flips based on random variables or broken clauses.
- Crossover heuristics: Crossover operators apply standard one-point or two-point crossover to Boolean variable strings.
3.2 One Dimensional Bin Packing
The bin-packing domain models assigning weighted pieces to capacity-limited bins while minimizing bins, and supplies initialization plus diverse search operators.
- Problem formulation: The objective is to assign each piece to one capacity-limited bin while minimizing the number of bins used.An alternative fitness function is employed to avoid large plateaus around the best solutions.
- Solution initialization: Solutions are initialized by randomizing piece order and applying first-fit, which places each piece into the first bin where it fits.
- Search operators: The domain provides 8 search operators spanning mutation, local search, crossover, and ruin-recreate strategies.
- Search operators: Mutation operators swap pieces, split overfilled bins, or remove and best-fit-repack pieces from selected high- or low-filled bins.
- Search operators: Local search accepts a generated neighbor immediately when its fitness is superior or equal, while rejecting worse neighbors.
- Search operators: Crossover orders parent bins by wasted space, adds mutually exclusive bins, and removes duplicate pieces while constructing offspring.
3.3 Permutation Flow Shop
The permutation flow-shop domain seeks a job order minimizing the final completion time across consecutive machines, with randomized NEH initialization and 15 operators.
- Problem formulation: The problem schedules n jobs on m consecutive machines while preserving the machine-1 order and preventing simultaneous processing conflicts.
- Problem formulation: The objective is to minimize the completion time of the last job to exit the shop, represented as max_i C_i.
- Solution initialization: A randomized NEH procedure initializes solutions by generating a random job permutation and incrementally constructing a schedule.
- Search operators: The domain implements 15 search operators, including reinsertion, swapping, shuffling, NEH-based perturbation, and local search.
- Search operators: Local searches remove jobs and test alternative positions using either steepest descent, first improvement, or a randomized single pass.
- Search operators: Crossover operators include PMX, OX, PPX, and a single-point operator that combines parent elements into a new permutation.
3.4 Personnel Scheduling
Personnel-scheduling instances vary in constraints and objectives across workplaces, so the domain combines multiple perturbation, local-search, crossover, and ruin-recreate operators.
- Problem formulation: Personnel-scheduling instances often have unique workplace-specific constraints and objectives beyond differences in employee, shift, or planning parameters.
- Search operators: The domain implements 12 search operators.
- Ruin-recreate heuristics: One perturbation randomly unassigns shifts, with the number of shifts proportional to the intensity-of-mutation parameter.
- Ruin-recreate heuristics: Ruin-and-recreate operators unassign selected employees’ schedules and rebuild them by prioritizing work requests, weekends, and work-pattern objectives.
- Ruin-recreate heuristics: The first ruin-and-recreate heuristic unassigns 2–6 schedules, based on a prior observation reported for instances of all sizes.
- Local search heuristics: Local-search operators add shifts or swap shifts between employees or within one employee’s schedule.
- Crossover heuristics: A crossover heuristic selects highly valuable assignments from each parent, where x ranges from 4–20 according to mutation intensity.
4 Algorithms
HyFlex illustrates three general algorithm designs: iterated local search, adaptive tabu search, and a population-based memetic algorithm.
- Overview: The examples use identical algorithms across domains and instances without domain- or instance-specific tuning.
- Iterated Local Search: Iterated local search perturbs an incumbent, applies the best improving local search heuristic, and retains only improvements until the time limit.
- TS-AA: TS-AA selects the highest-valued non-tabu heuristic, increasing its value after improvement and decreasing it after deterioration.
- TS-AA: TS-AA accepts every improving solution and probabilistically accepts worse solutions, adapting β upward when progress stalls and downward when search progresses.
- Memetic algorithm: The memetic algorithm maintains a population of 10 solutions, applies crossover, occasional mutation, and either local search or ruin-recreate modification.
5 Experiments and Results
The experiments compare three algorithms across 40 instances in four domains using common settings, revealing strong domain- and runtime-dependent performance differences.
- Experimental setup: The study compares the same three algorithms on 10 instances per domain, using five 10-minute runs per instance without domain- or instance-specific tuning.The setup covers MAX-SAT, bin packing, permutation flow shop, and personnel scheduling.
- Ordinal analysis: Borda ranks use the median best objective value across five runs; lower total scores indicate better performance across the 40 instances.The best possible total score is 40.
- Ordinal analysis: ILS achieves the best overall Borda score by a minimal difference, while TS-AA scores best in MAX-SAT and permutation flow shop.The overall comparison does not identify one uniformly dominant algorithm.
- Objective distributions: Performance differs significantly across domains: MA is best on the selected MAX-SAT instance but worst on personnel scheduling, while TS-AA shows the reverse pattern across those examples.TS-AA performs worst on the selected bin-packing and flow-shop instances but best on personnel scheduling.
- Interpretation: The results make cross-domain algorithm design challenging because improvements on one domain or instance may reduce solution quality elsewhere.The paper identifies online learning mechanisms that adapt during search as a central challenge.
- Progress over time: On the bin-packing trace, ILS and MA finish at approximately the same fitness, but MA finds better solutions sooner; TS-AA starts better than ILS before stagnating.By the end of the run, ILS has found a better solution than TS-AA.
6 Conclusions
The paper presents HyFlex as a common benchmark for developing and comparing cross-domain heuristic search methods. Its reported use and participation indicate practical research-community uptake, while the framework remains extensible.
- Framework contribution: HyFlex provides multiple problem domains, instances, and search operators through a common benchmark for developing and comparing cross-domain methodologies.This lets researchers focus on adaptive methodologies rather than implementing each problem domain.
- Empirical conclusion: The paper describes HyFlex architecture, four problem domains, and three example hyper-heuristics whose results differ across domains.No single algorithm is superior to the other two on all four domains.
- Future research: The results suggest scope for adaptive and self-configuring algorithms that learn from the search process and select suitable search operators.The example algorithms are explicitly not presented as state-of-the-art adaptive algorithms.
- Community uptake: By May 2011, HyFlex had been downloaded over 460 times, its webpages had received over 11,844 visits, and CHeSC had 43 participants from 23 countries.The paper presents these figures as evidence of research-community use and engagement.
- Scope and extensions: The framework can be extended with new domains, additional instances and operators, and multi-objective or dynamic problems.The interface can also incorporate additional domain feedback for adaptive search controllers.