Aligning large language models with multiple human expectations and values is crucial for ensuring that they adequately serve a variety of user needs. To this end, offline multiobjective alignment algorithms such as the Rewards-in-Context algorithm have shown strong performance and efficiency. However, inappropriate preference representations and training with imbalanced reward scores limit the performance of such algorithms. In this work, we introduce ParetoHqD that addresses the above issues by representing human preferences as preference directions in the objective space and regarding data near the Pareto front as ''high-quality'' data. For each preference, ParetoHqD follows a two-stage supervised fine-tuning process, where each stage uses an individual Pareto high-quality training set that best matches its preference direction. The experimental results have demonstrated the superiority of ParetoHqD over five baselines on two multiobjective alignment tasks.

Neural neighborhood search (NNS) has emerged as a powerful paradigm for solving vehicle routing problems (VRP), evolving solutions through iterative improvement. However, existing approaches often treat operators as independent discrete tokens (e.g., via one-hot encoding), ignoring their intrinsic behaviors and semantics. To address this, we propose MODE (manifold operator decoding embeddings), an approach that integrates semantic structure into operator search space. Instead of learning representations from scratch during search, MODE first constructs a continuous operator manifold space by analyzing search trajectories and mapping behaviorally similar operators to proximal embeddings. These structured representations are then used by a lightweight MLP decoder to guide the search. By replacing abstract identifiers with dense, informative priors, MODE enables the policy to efficiently navigate the search space. Experiments on capacitated VRP (CVRP) demonstrate that leveraging manifold priors significantly enhances sample efficiency and solution quality. This work verifies that incorporating explicit semantic priors is superior to treating operators as independent tokens, offering a new perspective for designing effective neural search policies.

The multi-objective dynamic flexible job shop scheduling (MO-DFJSS) problem is crucial in modern manufacturing, impacting productivity and operational costs. Genetic Programming (GP) has emerged as a prominent method for MO-DFJSS due to its ability to evolve real-time responsible and effective scheduling heuristics. However, existing GP approaches often learn multiple heuristics for different regions of the Pareto front, making their management and selection complicated in real-world applications. This paper proposes a novel Pareto set learning GP (PSLGP) framework that addresses this limitation by learning a single, preference-conditioned heuristic that encompasses the entire Pareto front based on user preferences. This simplifies scheduling and allows for real-time adaptation to user-defined priorities. The framework employs a novel preference-conditioned heuristic representation that incorporates user preferences as additional inputs, enabling dynamic heuristic adjustments. To efficiently evaluate fitness without increasing training time, a surrogate model is used to estimate individual performance across different preferences, and three new fitness aggregation strategies are designed to ensure effective heuristic alignment across the Pareto front. Experimental results demonstrate that PSLGP significantly outperforms the state-of-the-art multi-objective GP approach, particularly in less busy MO-DFJSS environments, providing a more adaptable and efficient solution for dynamic scheduling challenges. Further analyses of preference influence, solution distribution, and heuristic structure provide evidence that the proposed PSLGP effectively learns preference-conditioned scheduling heuristics that align user preferences with various regions of the Pareto front.

Dynamic Flexible Job Shop Scheduling (DFJSS) is a critical combinatorial optimisation problem known for its dynamic nature and flexibility of machines. Traditional scheduling methods face limitations in adapting to such dynamic and flexible environments. Recently, there has been a trend in employing reinforcement learning (RL) to train scheduling agents for selecting manual scheduling heuristics at various decision points for DFJSS. However, the effectiveness of RL is constrained by the limited efficacy of the manually designed scheduling heuristics. Additionally, the process of manually designing diverse scheduling heuristics as the actions demands significant expert knowledge. In response, this paper proposes a Niching genetic programming (GP)-assisted RL method that leverages the evolutionary capabilities of GP to help RL solve the DFJSS problem effectively. Specifically, instead of using those manual scheduling heuristics, the RL actions are replaced with scheduling heuristics evolved by the Niching GP to optimise and adapt these heuristics based on real-time feedback from the environment. Experimental results demonstrate the effectiveness of the proposed method in comparison to the widely used manual scheduling heuristics and the baseline deep RL method. Further analyses reveal that the effectiveness of the proposed method is due to the behavioral differences among heuristics learned by the Niching GP, serving as actions for the RL. In addition, the effectiveness of the proposed algorithm benefits from the comparable percentages of contributions made by these learned heuristics throughout the long-term scheduling process.

Ontology is a kernel technique of the semantic web, which defines concepts, properties, and their relationships to establish a shared understanding of domain knowledge. Ontology matching identifies semantically similar entities across different ontologies, which uses similarity features to measure their similarity from different perspectives. However, due to the complexity of the entity heterogeneity, no single similarity feature is universally effective. In recent years, genetic algorithms have proven effective in constructing similarity features for ontology matching, but their potential is limited by the reliance on default classification strategies, empirical determination of the number of high-level features, the requirement for manually selecting, combining these features, and tuning the associated combination parameters. To overcome these drawbacks, we propose a multi-layer hybrid genetic programming approach to automatically construct high-level similarity features. This approach includes three novel components. First, a new multi-layer individual representation is designed, which faciliates the algorithm to adaptively explore the search space of constructing high-level similarity features. Second, to enhance the search effectiveness, a new initialization method and a mutation operator are developed, which use a weight-based strategy to adaptively select and construct a more diverse set of similarity features. Third, a compact genetic algorithm-based optimizer is designed to refine the tree structures of elite individuals. The experimental results on the ontology alignment evaluation initiative’s benchmark show that our algorithm can generate high-quality ontology matching results across various matching tasks, significantly outperforming the state-of-the-art ontology matching methods.

Cloud-Fog computing has emerged as an essential paradigm to support the growing demand for real-time data processing driven by the Internet of Things. By integrating the extensive computing capabilities of cloud data centres with the low-latency benefits of fog nodes, this architecture increases resource utilisation and improves quality of service. However, the dynamic and heterogeneous nature of cloud fog environments poses significant workflow scheduling challenges, especially when optimising multiple trade-offs such as latency, cost, energy consumption, and resource utilisation. This paper investigates the many-objective dynamic workflow scheduling problem under deadline constraints in container-based cloud-fog computing environments (MDWS-CoCF). Unlike existing studies that primarily focus on horizontal scaling, this work considers both vertical and horizontal scaling of containers, allowing for real-time adjustments of container configurations based on task-specific requirements. To address this complex problem, we first develop a dynamic workflow scheduling simulator that models real-world scenarios, including a variety of task categories and container scalability. Based on this simulator, we propose a Cooperative Coevolution Genetic Programming (CCGP) approach that evolves specialised heuristics for task selection, resource allocation, and container deployment to facilitate adaptive and efficient scheduling in MDWS-CoCF. Extensive simulations using real-world data traces show that the proposed CCGP approach significantly outperforms existing baseline algorithms, achieving superior performance as measured by the HyperVolume and Inverted Generational Distance metrics. The results show that the evolved heuristics are robust and effective under different dynamic scenarios, ensuring balanced optimisation of many objectives.

This paper studies the Dynamic Electric Dial-A-Ride Problem (DEDARP), which is a combinatorial optimisation problem that has applications in real-world ridesharing services with electric vehicles. In addition to the challenges from classical scheduling and route planning, we consider here the extra challenge of making real-time dispatching decisions in dynamic environments with new requests arriving over time and selecting proper times for the vehicles to recharge. To solve DEDARP effectively, we propose a Genetic Programming Hyper-Heuristic (GPHH) that evolves heuristics/policies to dispatch vehicles in real time. We have developed a simulation process that generates a solution for any given instance by two policies, one for vehicle allocation and the other for request allocation, and design fitness evaluations based on the simulation. Moreover, we propose a multi-tree GP to evolve these two policies simultaneously, which makes use of advanced terminals to comprehensively represent the state. Experimental results on a wide range of instances show that GPHH can evolve effective policies that make significantly better real-time dispatching decisions than human-designed policies based on prior knowledge.

Manually designing (meta-)heuristics for the Vehicle Routing Problem (VRP) is a challenging task that requires significant domain expertise. Recently, data-driven approaches have emerged as a promising solution, automatically learning heuristics that perform well on training instances and generalize to unseen test cases. Such an approach learns (meta-)heuristics that can perform well on the training instances, expecting it to generalize well on the unseen test instances. A recent method, named GPGLS, uses Genetic Programming (GP) to learn the utility function in Guided Local Search (GLS) and solved large scale VRP effectively. However, the selection of appropriate training instances during the learning process remains an open question, with most existing studies including GPGLS relying on random instance selection. To address this, we propose a novel method, CL-GPGLS, which integrates Curriculum Learning (CL) into GPGLS. Our approach leverages a predefined curriculum to introduce training instances progressively, starting with simpler tasks and gradually increasing complexity, enabling the model to better adapt and optimize for large-scale VRP (LSVRP). Extensive experiments verify the effectiveness of CL-GPGLS, demonstrating significant performance improvements over three baseline methods.

Energy-Efficient dynamic flexible job shop scheduling (E-DFJSS) is a valuable real-world combinational optimisation problem. As an important variant of DFJSS, E-DFJSS aims to optimise trade-off between production effectiveness and energy consumption. Genetic Programming (GP) has been successfully used to learn dispatching rules in E-DFJSS. Nevertheless, different users have different preferences on the trade-off between production effectiveness and energy consumption, the studies of preference-based multi-objective optimisation algorithms are limited. These existing related preference-based methods face the issue of premature convergence in the early stage when solving E-DFJSS, which results in insufficient diversity. To address these challenges, we develop a preference-based multi-objective GP approach for E-DFJSS. A fusion r-dominance and achievement scalarising function dominance criterion is embedded into the proposed algorithm to solve E-DFJSS. Experimental results on training and test on three scenarios with four preferences show that the proposed method could improve the effectiveness of learned scheduling heuristics by balancing diversity and convergence of evolutionary progress.

Efficient scheduling under uncertain durations and constrained resources remains a core challenge in the dynamic multi-mode resource-constrained project scheduling problem. Genetic programming (GP) has proven effective for evolving scheduling rules; however, conventional strategies often assess activities separately, disregarding potential synergies among modes of concurrently executable tasks. To overcome this limitation, we develop a group-based strategy that selects from feasible combinations of activity-mode tuples. New terminals are designed to capture the attributes of these combinations and embed them into a GP framework. Experimental evaluation across multiple scenarios demonstrates that our group-based GP approach outperforms conventional GP methods based on individual activity prioritisation.

The Uncertain Capacitated Arc Routing Problem (UCARP) presents unique challenges in real-world applications such as waste collection and winter gritting, where task demands and service costs are stochastic. Although Genetic Programming Hyper-Heuristics (GPHH) have demonstrated strong adaptability to such uncertainties by evolving dynamic routing policies, their complex decision-making processes hinder interpretability. To address this, a novel framework called Differential Evolution with Random Ablation (DERA) is introduced to generate diverse and feasible counterfactual explanations. Unlike traditional methods, DERA systematically explores multiple counterfactual scenarios by integrating random ablation into the optimisation process, thereby uncovering a broader range of plausible alternatives. Experimental results across various UCARP instances show that DERA consistently achieves high feasibility, minimal feature changes, and greater diversity in counterfactual explanations compared to baseline methods. This diversity enables a more comprehensive understanding of GPHH-evolved policies, providing actionable insights to improve decision-making transparency and robustness in dynamic environments.

Genetic programming (GP) has been popularly used to learn scheduling rules for dynamic flexible job shop scheduling. These scheduling rules serve as priority functions to prioritise candidate machines or operations at decision points. In the implementation level, a high prioritised machine and operation can be the ones with the highest or lowest priority value calculated with a scheduling rule in the decision making process. In theory, GP can adaptively evolve scheduling rules to accommodate different priority settings. However, research exploring the possible hidden differences during the evolutionary process remains limited. To fill this gap, this paper presents a comprehensive investigation into scheduling rules learned by GP under varying priority settings. The results show that while GP achieves similar performance in most investigated scenarios with different priority settings, GP-low where candidates with the lowest priority values are selected, can learn effective scheduling rules faster. Specifically, GP-low can learn smaller sequencing rules. Furthermore, visualisations of the scheduling rules illustrate how GP adaptively adjusts node positions to evolve effective rules. The study also highlights an inherent bias in initialised scheduling rules, which tend to prefer candidates with lower priority values in the examined scenarios. Moreover, GP-low exhibits a broader distribution of priority values. These findings can provide deeper insights into GP’s adaptive learning mechanisms and offer valuable guidance for decision-making of using scheduling rules.

The Capacitated Vehicle Routing Problem (CVRP) is a classic optimization problem with widespread applications in real-world scenarios. Existing research has developed numerous neighborhood operators capable of generating high-quality solutions. However, most neighborhood search algorithms either apply all operators in a predefined/random sequence or adaptively adjust only improvement operators, neglecting the learning of perturbation operators. This limitation often results in suboptimal performance. To address this issue, this paper proposes Learning Adaptive Neighborhood Search with Dual operator Selection (LANDS), an algorithm that integrates two RL-based controllers to adaptively select both improvement and perturbation operators simultaneously. Within this framework, the two controllers act as high-level guides, collaboratively directing the optimization process by selecting appropriate operators. Additionally, to reduce resource waste, a filtering mechanism is introduced to exclude operators deemed ineffective within the same improvement iteration, enhancing the algorithm's efficiency. The effectiveness of the proposed LANDS method is verified by a series of experiments.

Genetic programming-based hyper-heuristic approaches have successfully evolved effective scheduling heuristics for dynamic flexible job shop scheduling. However, in addition to effectiveness, users may prefer other important factors such as model size (i.e., bloat control), structural complexity, and interpretability. To evolve scheduling heuristics considering a wide range of factors, we aim to solve a new many-objective optimisation problem with one effectiveness indicator and four commonly considered model structural complexity measures. To solve this problem, we design a new multiform many-objective genetic programming-based hyper-heuristic algorithm, which optimises this proposed many-objective optimisation task and a constructed single-objective auxiliary task in a multitask manner. This auxiliary task is specifically designed to optimise effectiveness, aiming to find effective individuals and provide beneficial genetic materials for the original task to improve search performance via knowledge transfer. The experimental results show that this approach can produce scheduling heuristics that approximate the Pareto front better than the compared state-of-the-art algorithms across a series of scenarios. Further analysis demonstrates the interpretability of evolved scheduling heuristics and the advantages of considering comprehensive structural complexity measures simultaneously.

Meta-Black-Box Optimization (MetaBBO) garners attention due to its success in automating the configuration and generation of black-box optimizers, significantly reducing the human effort required for optimizer design and discovering optimizers with higher performance than classic human-designed optimizers. However, existing MetaBBO methods conduct one-off training under the assumption that a stationary problem distribution with extensive and representative training problem samples is pre-available. This assumption is often impractical in real-world scenarios, where diverse problems following shifting distribution continually arise. Consequently, there is a pressing need for methods that can continuously learn from new problems encountered on-the-fly and progressively enhance their capabilities. In this work, we explore a novel paradigm of lifelong learning in MetaBBO and introduce LiBOG, a novel approach designed to learn from sequentially encountered problems and generate high-performance optimizers for Black-Box Optimization (BBO). LiBOG consolidates knowledge both across tasks and within tasks to mitigate catastrophic forgetting. Extensive experiments demonstrate LiBOG's effectiveness in learning to generate high-performance optimizers in a lifelong learning manner, addressing catastrophic forgetting while maintaining plasticity to learn new tasks.

BACKGROUND: Chrysophrys auratus (family: Sparidae), commonly known as Australasian snapper, is a warm-water species being developed as a candidate for aquaculture in New Zealand. Genomic selection of elite snapper offers significant potential to accelerate genetic gains in aquaculture; however, the complexity of genetic architecture, coupled with challenges such as missing data and high dimensionality, poses significant hurdles. Machine learning techniques have emerged as powerful tools in genomic selection programmes due to their flexibility and ability to model complex, polygenic and non-linear relationships between genotypes and traits. This study aims to develop a comprehensive machine learning framework to evaluate imputation methods and genomic prediction models, and identify single-nucleotide polymorphisms associated with growth traits in snapper, ultimately contributing to the advancement of selective breeding programmes. RESULTS: We evaluated multiple approaches for each component of the machine learning framework. We developed and evaluated the Domain Knowledge-based K-nearest neighbour (DK-KNN) imputation method, achieving a notably high imputation accuracy of 98.33% in simulation testing, outperforming two alternative imputation methods. Among feature selection and classification combinations evaluated for growth prediction, Chi-squared feature selection paired with Distance-Weighted Discrimination (Chi2-DWD) achieved 60% prediction accuracy, comparable to genomic best linear unbiased prediction (60.3%) but without requiring the genomic relationship matrix. Notably, the two-stage approach using Domain Knowledge-based Pre-filtering (DK Pre-filtering) as a pre-filter did not substantially impact prediction accuracy, and it proved valuable in reducing the dimensionality of the feature space without affecting model performance. CONCLUSIONS: Integration of domain knowledge into machine learning frameworks effectively addresses missing values and high-dimensional challenges in snapper genomic data. The evaluated framework demonstrates that Chi2-DWD represents a promising combination for genomic prediction tasks. The DK Pre-filtering workflow as a pre-filtering method successfully removes redundant features without affecting model performance. Selected features showed biological significance and were confirmed to be associated with growth traits based on biological analysis, providing valuable insights for selective breeding programs.

The Vehicle Routing Problem (VRP) is a classic optimization problem with diverse real-world applications. The neighborhood search has emerged as an effective approach, yielding high-quality solutions across different VRPs. However, most existing studies exhaustively explore all considered neighborhoods with a pre-fixed order, leading to an inefficient search process. To address this issue, this paper proposes a Learning-aided Neighborhood Search algorithm (LaNS) that employs a cutting-edge multi-agent reinforcement learning-driven adaptive operator/neighborhood selection mechanism to achieve efficient routing for VRP. Within this framework, two agents serve as high-level instructors, collaboratively guiding the search direction by selecting perturbation/improvement operators from a pool of low-level heuristics. Furthermore, to equip the agents with comprehensive information for learning guidance knowledge, we have developed a new informative state representation. This representation transforms the spatial route structures into an image-like tensor, allowing us to extract spatial features using a convolutional neural network. Comprehensive evaluations on diverse VRP benchmarks, including the capacitated VRP (CVRP), multi-depot VRP (MDVRP) and cumulative multi-depot VRP with energy constraints, demonstrate LaNS's superiority over the state-of-the-art neighborhood search methods as well as the existing learning-guided neighborhood search algorithms.

Large-scale multiobjective binary optimization problems (MBOPs) often occur in real-world applications, where the function evaluation can only be performed through computationally expensive simulations, which renders standard exact and heuristic methods ineffective. Aggregation-based surrogate-assisted multiobjective evolutionary algorithms have been developed and shown to be promising for solving such problems. They define a set of uniformly distributed weight vectors as search directions, on which all search resources are placed to perform the evolution. However, the Pareto fronts of large-scale MBOPs are discrete and nonuniform. As a result, many weight vectors are useless, thus a lot of search resources are wasted. To address this challenge, we propose a surrogate-assisted neighborhood search (SANS) for expensive large-scale multiobjective binary optimization. SANS uses only a few weight vectors to save search resources while maintaining an adequate diversity. To further utilize the limited search resources, a Q-learning-based method is designed to dynamically allocate search resources to weight vectors. Furthermore, a surrogate-assisted variable neighborhood search is developed to speed up the search without getting trapped in a local optimum prematurely. To robustly and reliably predict the quality of the found solutions, global and local surrogate models are trained by different training samples and then work collaboratively. The experimental results have demonstrated the superiority of SANS over seven state-of-the-art algorithms on the MBOPs with up to 1000 decision variables using only 500 real solution evaluations.

Dynamic air traffic flow management (DATFM) aims at flexibly balancing air traffic demand with limited airspace by scheduling aircraft, particularly during unforeseen events, to maintain efficiency in aviation operations. Genetic programming (GP) has shown success in evolving effective heuristics across various domains. However, directly adopting GP to DATFM may be less effective due to the computationally intense simulations required for large-scale aircraft decision-making over broad airspace. To address the issue, we develop a novel multifidelity surrogate-assisted GP. The core idea is that if a computationally efficient low-fidelity surrogate provides enough information to guide the population toward promising areas effectively, then employing more accurate but resource-intensive evaluations would only increase computational effort without enhancing the direction of evolution. A key innovation in our method is a surrogate management strategy that automatically determines when and which surrogate model to use, based on collective information from the evolving population. This approach allows for more effective management of computational resources during the evolutionary process, enabling exploration of a broader range of the heuristic space and increasing the likelihood of identifying promising solutions. The proposed method has been tested on various benchmark instances derived from actual air traffic data. Extensive experimental results demonstrate that the proposed algorithm significantly outperforms current state-of-the-art methods in both effectiveness and efficiency.

Linear genetic programming (LGP) has been successfully applied to dynamic job shop scheduling (DJSS) to automatically evolve dispatching rules. Flow control operations are crucial in concisely describing complex knowledge of dispatching rules, such as different dispatching rules in different conditions. However, existing LGP methods for DJSS have not fully considered the use of flow control operations. They simply included flow control operations in their primitive set, which inevitably leads to a huge number of redundant and obscure solutions in LGP search spaces. To move one step toward evolving effective and interpretable dispatching rules, this paper explicitly considers the characteristics of flow control operations via grammar-guided linear genetic programming and focuses on IF operations as a starting point. Specifically, this paper designs a new set of normalized terminals to improve the interpretability of IF operations and proposes three restrictions by grammar rules on the usage of IF operations: specifying the available inputs, the maximum number, and the possible locations of IF operations. The experiment results verify that the proposed method can achieve significantly better test performance than state-of-the-art LGP methods and improves interpretability by IF-included dispatching rules. Further investigation confirms that the explicit introduction of IF operations helps effectively evolve different dispatching rules according to their decision situations.

Searching for symbolic models plays an important role in a wide range of domains such as neural architecture search and automatic program synthesis. Genetic programming is a promising stochastic method for searching effective symbolic models within an acceptable time. The genetic programming performance is closely related to the hardness of the fitness landscape. A better fitness landscape with less local optima normally implies that it is easier to search for better solutions. In recent years, there have been many studies enhancing genetic programming performance by forming better fitness landscapes. However, the better design of the fitness landscape highly relies on specific domain knowledge and consumes a lot of expert effort. This paper proposes a fitness landscape optimization method to automatically design better fitness landscapes for genetic programming search than the manually designed ones. We optimize the landscapes by optimizing the neighborhood structures of symbolic solutions. We verify the effectiveness of the proposed method in both supervised learning and combinatorial optimization problems. The results show that the proposed method significantly reduces the hardness of fitness landscapes. By simply searching against the automatically optimized fitness landscapes, a genetic programming method can have a very competitive performance with state-of-the-art methods.

Neural solvers (NSs) based on the attention mechanism have demonstrated remarkable effectiveness in solving routing problems like traveling salesman problems (TSPs) and vehicle routing problems (VRPs). However, in the generalization process, we find a phenomenon of the dispersion of attention scores in existing NSs, which leads to poor performance. To improve the generalization ability of NSs, this article proposes a distance-aware attention reshaping (DAR) method. Specifically, without increasing any parameter of the neural network (NN), we utilize the distance information between nodes to adjust attention scores. This enables an NS trained on small-scale instances with a certain distribution to make rational choices when solving large-scale problems with different distributions. Its effectiveness is verified both theoretically and empirically. Extensive experiments on the TSP, asymmetric TSP (ATSP), capacitated VRP (CVRP), VRP with time windows (VRPTW), capacitated arc routing problem (CARP), and knapsack problem (KP) demonstrate the advantages of our method. Our code is available at https://github.com/ftwangyang/DAR.

Multipoint dynamic aggregation (MPDA) is a multirobot task allocation problem, which requires the collaborative scheduling of multiple robots to complete time-varying tasks distributed on a map. Most existing studies consider the scenarios with homogeneous robots and tasks. To model the application scenarios where different types of robots are required, we propose a heterogeneous MPDA problem, which incorporates different types of robots and tasks with dependency. Correspondingly, a novel metaheuristic algorithm called multistage particle swarm optimization is designed and consists of two parts: 1) a multistage strategy and 2) a specially designed particle swarm optimization (PSO) algorithm. The multistage strategy imposes temporary constraints to force cooperation between robots, which can reduce and smoothen the search space. The proposed PSO contains a mixed updating mechanism consisting of a continuous velocity updating rule and a discrete position updating rule, which is effective for updating the permutation-based solutions of MPDA. The experiments on a newly designed benchmark test set show that the proposed algorithm is more effective and efficient than the state-of-the-art methods.

The job shop scheduling problem is an important combinatorial optimisation problem in the real world. Genetic programming hyper-heuristic has been successfully applied to automatically evolve effective dispatching rules to make a schedule in real time without much domain knowledge. However, the interpretability of GP-evolved rules has been largely neglected, which could lead to the lack of reliability and trustworthiness of the evolved rules in practice. Current work related to interpretable genetic programming algorithms primarily uses the model size as the interpretability metric. This could not fully reflect the interpretability of evolved rules. To overcome the limitation, we employ structural complexity and dimension gap as more comprehensive interpretability measures. In addition, a new multi-objective genetic programming algorithm, which applies the a non-dominated sorting method to solve the objective selection bias issue, is proposed to optimise the makespan (scheduling objective), structural complexity and dimension gap simultaneously. A variety of experiments demonstrates the competitive performance of our proposed algorithm based on effectiveness, convergence and diversity. Furthermore, the semantics of evolved dispatching rules are analysed to show their better interpretability.

The multi-mode resource-constrained project scheduling problem (MRCPSP) is a challenging problem for researchers and practitioners in operations research and project management. MRCPSP involves both selecting the execution mode for each activity and sequencing the activities in the schedule. Thus, activity prioritisation and mode selection are the two main decisions in building a project schedule. A rule-based heuristic approach is commonly used for solving this problem in practical complex scenarios. However, designing effective project scheduling rules highly relies on the expertise of professionals and domain knowledge. To address the above issue, this paper proposes a genetic programming-based hyper-heuristic (GPHH) to design heuristic rules automatically. Various decision strategies based on decision orders are proposed and their impact on the capacity of GPHH to learn effective scheduling rules is investigated. The experiment results demonstrate the evolved rules generated by GPHH outperform the existing manual heuristic rules and making two decisions simultaneously is identified as the most effective strategy.

The control of traffic signals is crucial for improving transportation efficiency. Recently, learning-based methods, especially Deep Reinforcement Learning (DRL), garnered substantial success in the quest for more efficient traffic signal control strategies. However, the design of rewards in DRL highly demands domain knowledge to converge to an effective policy, and the final policy also presents difficulties in terms of explainability. In this work, a new learning-based method for signal control in complex intersections is proposed. In our approach, we design a concept of phase urgency for each signal phase. During signal transitions, the traffic light control strategy selects the next phase to be activated based on the phase urgency. We then proposed to represent the urgency function as an explainable tree structure. The urgency function can calculate the phase urgency for a specific phase based on the current road conditions. Genetic programming is adopted to perform gradient-free optimization of the urgency function. We test our algorithm on multiple public traffic signal control datasets. The experimental results indicate that the tree-shaped urgency function evolved by genetic programming outperforms the baselines, including a state-of-the-art method in the transportation field and a well-known DRL-based method.

In many practical applications, usually, similar optimisation problems or scenarios repeatedly appear. Learning from previous problem-solving experiences can help adjust algorithm components of meta-heuristics, e.g., adaptively selecting promising search operators, to achieve better optimisation performance. However, those experiences obtained from previously solved problems, namely offline experiences, may sometimes provide misleading perceptions when solving a new problem, if the characteristics of previous problems and the new one are relatively different. Learning from online experiences obtained during the ongoing problem-solving process is more instructive but highly restricted by limited computational resources. This paper focuses on the effective combination of offline and online experiences. A novel hybrid framework that learns to dynamically and adaptively select promising search operators is proposed. Two adaptive operator selection modules with complementary paradigms cooperate in the framework to learn from offline and online experiences and make decisions. An adaptive decision policy is maintained to balance the use of those two modules in an online manner. Extensive experiments on 170 widely studied real-value benchmark optimisation problems and a benchmark set with 34 instances for combinatorial optimisation show that the proposed hybrid framework outperforms the state-of-the-art methods. Ablation study verifies the effectiveness of each component of the framework.

The document classification (DC) task assigns predefined classes to unlabeled documents using trained models. In the medical field, DC is crucial for tasks like categorizing risk factors and classifying electronic health records. This paper addresses challenges in medical document analysis, such as the prevalence of abbreviations and acronyms. Existing classification performance in medical documents is suboptimal. The paper introduces novel feature engineering methods leveraging domain-specific knowledge to enhance classification performance. Results indicate that the Three-Stage approach surpasses related works, showcasing improved medical document classification performance.

Symbolic regression (SR) is an important problem with many applications, such as automatic programming tasks and data mining. Genetic programming (GP) is a commonly used technique for SR. In the past decade, a branch of GP that utilizes the program behavior to guide the search, called semantic GP (SGP), has achieved great success in solving SR problems. However, existing SGP methods only focus on the tree-based chromosome representation and usually encounter the bloat issue and unsatisfactory generalization ability. To address these issues, we propose a new semantic linear GP (SLGP) algorithm. In SLGP, we design a new chromosome representation to encode the programs and semantic information in a linear fashion. To utilize the semantic information more effectively, we further propose a novel semantic genetic operator, namely, mutate-and-divide propagation, to recursively propagate the semantic error within the linear program. The empirical results show that the proposed method has better training and test errors than the state-of-the-art algorithms in solving SR problems and can achieve a much smaller program size.

Air traffic flow management plays a crucial role in efficient aviation. Most existing studies assume the flight speed as constant throughout the trip, leading to ineffective fixed-speed schedules. To address this issue, we propose a new problem model, which allows variable speed control to improve the flexibility and maneuverability of the management. In addition, we consider two conflicting objectives, which are minimizing the total flight delays and conflicts between flights, where the conflicts depend on the flight 4D trajectories (3D position plus time). To solve this new challenging problem, we propose a novel multi-objective evolutionary algorithm with new problem-specific individual representation and search operators. Specifically, the multi-chromosomes encoding scheme is designed to adapt to different types of operations. Then, to search the huge search space effectively, we develop a hybrid crossover operator that recombines the parents based on their flight routes. Furthermore, to balance the exploration and exploitation, we develop a new mutation strategy to utilize the heterogeneous search potential of different individuals. For exploitation, the knee individual in the Pareto front is improved by a new time shift operator for exploitation, and other non-dominated solutions are mutated by fixed-route mutation. For exploration, the dominated solutions are mutated randomly. To verify the effectiveness, we compare it with the real air traffic flow management schedules and the state-of-the-art algorithms on a range of real-world air traffic datasets. Extensive results show that the proposed algorithm can significantly outperform the baselines in generating safe and efficient 4D trajectories.

Air traffic flow management (ATFM) is the key driver of efficient aviation. It aims at balancing traffic demand against airspace capacity by scheduling aircraft, which is critical for air navigation service providers in delivering secure and sustainable air transport. Nowadays, the scale of scheduled aircraft grows dramatically along with the sharp increase in air traffic demand, which brings heavy pressure to efficient scheduling. Regarding safety and efficiency as two fundamental objectives of air transport, this paper proposes a cooperative co-evolutionary algorithm to solve large-scale multi-objective ATFM problems. First, a new multi-objective co-evolution framework with an evolving external archive is devised, in which the subcomponents collaborate with each other via the knee solution of the archive. Second, a novel fuzzy decomposition method is specifically designed to split the large-scale ATFM problem into small-size subcomponents by utilizing the spatiotemporal correlations of aircraft. During optimization, the proposed algorithm can continuously receive feedback from the optimization process and make the decomposition more likely better suited to the problem. Third, a new contribution-based probabilistic resource allocation mechanism is developed to automatically assign the computing resources to the unbalanced subcomponents. Finally, a test suite with different scales extracted from real air traffic data is created. Extensive experimental results show that, given the same number of fitness evaluations, the proposed algorithm significantly outperforms the state-of-the-art baselines in terms of effectiveness on all the benchmark instances.

Multitask genetic programming methods have been applied to various domains, such as classification, regression, and combinatorial optimization problems. Most existing multitask genetic programming methods are designed based on tree-based structures, which are not good at reusing building blocks since each sub-tree passes its outputs to only one parent. It may limit the design and performance of knowledge sharing in multitask optimization. Different from tree-based genetic programming, building blocks in linear genetic programming can be easily reused by more than one parent. Besides, existing multitask genetic programming methods always allocate each individual to a specific task and have to duplicate genetic materials from task to task in knowledge transfer, which is inefficient and often produces redundancy. Contrarily, it is natural for a linear genetic programming individual to produce multiple distinct outputs, which enables each linear genetic programming individual to solve multiple tasks simultaneously. With this in mind, we propose a new multitask linear genetic programming method that transfers knowledge via multi-output individuals (i.e., shared individuals among tasks). By integrating different solutions into one multi-output individual, the proposed method efficiently reuses common knowledge among tasks and maintains distinct behaviors for each task. The empirical results show that the proposed method has a significantly better test performance than state-of-the-art multitask genetic programming methods. Further analyses verify that the new knowledge transfer mechanism can adjust the transfer rate automatically and thus improves its effectiveness.

Genetic programming has been successfully used to evolve routing policies that can make real-time routing decisions for uncertain arc routing problems. Although the evolved routing policies are highly effective, they are typically very large and complex, and hard to be understood and trusted by real users. Existing studies have attempted to improve the interpretability by developing new genetic programming approaches to evolve both effective and interpretable (e.g., with smaller program size) routing policies. However, they still have limitations due to the trade-off between effectiveness and interpretability. To address this issue, we propose a new post-hoc explanation approach to explaining the effective but complex routing policies evolved by genetic programming. The new approach includes a local ranking explanation and a global explanation module. The local ranking explanation uses particle swarm optimisation to learn an interpretable linear model that accurately explains the local behaviour of the routing policy for each decision situation. Then, the global explanation module uses a clustering technique to summarise the local explanations into a global explanation. The experimental results and case studies on the benchmark datasets show that the proposed method can obtain accurate and understandable explanations of the routing policies evolved for uncertain arc routing problems. Our explanation approach is not restricted to uncertain arc routing, but has a great potential to be generalised to other optimisation and machine learning problems such as learning classifier systems and reinforcement learning.

Dynamic flexible job shop scheduling is a prominent combinatorial optimisation problem with many real-world applications. Genetic programming has been widely used to automatically evolve effective scheduling heuristics for dynamic flexible job shop scheduling. A limitation of genetic programming is the premature convergence due to the loss of population diversity. To overcome this limitation, this work considers using lexicase selection to improve population diversity, which has achieved success on regression and program synthesis problems. However, it is not trivial to apply lexicase selection to genetic programming for dynamic flexible job shop scheduling, since a fitness case (training scheduling simulation) is often large-scale, making the fitness evaluation very time-consuming. To address this issue, we propose a new multi-case fitness scheme, which creates multiple cases from a single scheduling simulation. Based on the multi-case fitness, we develop a new genetic programming algorithm with lexicase selection, which uses a single simulation for fitness evaluation, thus achieving a better balance between the number of cases for lexicase selection and evaluation efficiency. The experiments on a wide range of dynamic scheduling scenarios show that the proposed algorithm can achieve better population diversity and final performance than the current genetic programming parent selection methods and a state-of-the-art deep reinforcement learning method.

Dynamic flexible job shop scheduling is an important but difficult combinatorial optimisation problem that has numerous real-world applications. Genetic programming has been widely used to evolve scheduling heuristics to solve this problem. Ensemble methods have shown promising performance in many machine learning tasks, but previous attempts to combine genetic programming with ensemble techniques are still limited and require further exploration. This paper proposes a novel ensemble genetic programming method that uses a population consisting of both single individuals and ensembles. The main contributions include: 1) developing a genetic programming method that evolves a population comprising both single individuals and ensembles, allowing breeding between them to explore the search space more effectively; 2) proposing an ensemble construction and selection strategy to form ensembles by selecting diverse and complementary individuals; and 3) designing new crossover and mutation operators to produce offspring from single individuals and ensembles. Experimental results demonstrate that the proposed method outperforms existing traditional and ensemble genetic programming methods in most scenarios. Further analyses find that the success is attributed to the enhanced population diversity and extensive search space exploration achieved by the proposed method.

Job shop scheduling (JSS) is a process of optimizing the use of limited resources to improve the production efficiency. JSS has a wide range of applications, such as order picking in the warehouse and vaccine delivery scheduling under a pandemic. In real-world applications, the production environment is often complex due to dynamic events, such as job arrivals over time and machine breakdown. Scheduling heuristics, e.g., dispatching rules, have been popularly used to prioritize the candidates such as machines in manufacturing to make good schedules efficiently. Genetic programming (GP), has shown its superiority in learning scheduling heuristics for JSS automatically due to its flexible representation. This survey first provides comprehensive discussions of recent designs of GP algorithms on different types of JSS. In addition, we notice that in the recent years, a range of machine learning techniques, such as feature selection and multitask learning, have been adapted to improve the effectiveness and efficiency of scheduling heuristic design with GP. However, there is no survey to discuss the strengths and weaknesses of these recent approaches. To fill this gap, this article provides a comprehensive survey on GP and machine learning techniques on automatic scheduling heuristic design for JSS. In addition, current issues and challenges are discussed to identify promising areas for automatic scheduling heuristic design in the future.

Multi-cloud is a promising paradigm due to its advantages such as avoiding vendor lock-in and optimising costs. This article focuses on dynamic flexible workflow scheduling with minimum total monetary cost in multi-clouds, considering multiple categories of services for each cloud with different configurations and billing methods. Existing studies generally ignore the characteristics and states of each individual cloud when making schedules, which may be ineffective regarding cost savings and quality of service. To address this issue, we propose to introduce a cloud selection decision on top of the existing task selection and resource selection decisions to help us select appropriate resource for task in an overall cost-effective cloud. To automatically learn the task, cloud and resource selection rules simultaneously, we propose a new genetic programming with multi-tree representation based on a customised discrete event-driven dynamic workflow scheduling simulator. Simulation results based on two real-world data traces show that the proposed algorithm performs significantly better than the state-of-the-art algorithms in terms of reducing the rental costs and deadline deviation, and improving the success rate. The results also show that the superiority of the proposed algorithm lies in the ability to select an appropriate cloud resource for a task.

With technological breakthroughs, drone deliveries have become increasingly popular, especially during the COVID-19 pandemic. Driven by both economical benefit and efficiency, drone-truck combined deliveries are in demand. However, it is very challenging to handle the collaboration between trucks and drones. Existing methods for truck-only routing cannot be directly applied, since their solution representations and search operators cannot consider the drone-truck collaborations effectively. In this article, we model the system as traveling salesman problem with drones (TSP-Ds), and propose a new Memetic algorithm named MATSP-D for solving it. Specifically, we design a new drone-truck solution representation and develop new crossover and local search operators under the new representation, which can modify the drone services effectively. MATSP-D conducts exploration by crossover, and exploitation by a variable neighborhood search process. The experimental results show that the proposed MATSP-D significantly outperforms the state-of-the-art algorithms for most test instances, especially the large instances with more complex collaborations between the truck and drone. Further analysis verifies the effectiveness of the newly developed local search operators in searching for better-drone-truck collaborations.

Dynamic flexible job shop scheduling (DFJSS) is a critical and challenging combinatorial optimisation problem. Genetic programming (GP) has been widely used to learn scheduling heuristics for DFJSS automatically. Ideally, we prefer to have effective and small scheduling heuristics which tend to be easy to be interpreted. However, the effectiveness and the sizes of scheduling heuristics are conflicting, and reducing the rule sizes tends to worsen the effectiveness of scheduling heuristics. This is a typical multi-objective optimisation problem. However, the existing studies in multi-objective DFJSS consider the effectiveness-related objectives only such as minimising max-flowtime and mean-flowtime rather than interpretability-related objectives such as rule size. To fill this gap, this paper aims to propose an interpretability-aware multi-objective GP to learn a well-distributed Pareto-front of scheduling heuristics for DFJSS. This paper first adopts a multi-objective GP algorithm with α-dominance and archive from a routing problem to DFJSS. Then, we propose to use traditional dominance relation based Pareto front for α and archive updating and an objective normalisation based α-dominance sorting strategy to further improve the performance of the adopted multi-objective GP. The results show that the proposed algorithm can obtain significantly better performance than the state-of-the-art multi-objective GP algorithms in different DFJSS scenarios.

Counterfactual explanation is a popular eXplainable AI technique, that gives contrastive explanations to answer potential "what-if" questions about the workings of machine learning models. However, research into how explanations are understood by human beings has shown that an optimal explanation should be both selected and social, providing multiple varying explanations for the same event that allow a user to select specific explanations based on prior beliefs and cognitive biases. In order to provide such explanations, a Rashomon set of explanations can be created: a set of explanations utilising different features in the data. Current work to generate counterfactual explanations does not take this need into account, only focusing on producing a single optimal counterfactual.

The Vehicle Routing Problem (VRP) is a complex problem that comes with a great number of applications in logistics and supply chains. It is non-trivial to select the optimal VRP techniques to solve these applications, especially since there are several possible scenarios. As there is no way to predict how each algorithm would perform until it is (at least partially) deployed, it would make sense in selecting the ones that have higher adaptability to the given environment. In this paper, we consider this idea on the initialisation part of a local search-based metaheuristic. We argue that a proper initialisation is important for obtaining better VRP solutions and apply several machine learning techniques aiming to learn how to use distinct features from four commonly used construction heuristics solutions, predicting the scenarios in which they are the most effective. We also provide relevant discussions on the effects of the initial solution on a local search context. Results show that the proposed method can help select the best or an improving method for the majority of the instances considered, especially for large-scale VRP instances.

Dispatching rules are commonly used to make instant decisions in dynamic scheduling problems. Linear genetic programming (LGP) is one of the effective methods to design dispatching rules automatically. However, the effectiveness and efficiency of LGP methods are limited due to the large search space. Exploring the entire search space of programs is inefficient for LGP since a large number of programs might contain redundant blocks and might be inconsistent with domain knowledge, which would further limit the effectiveness of the produced LGP models. To improve the performance of LGP in dynamic job shop scheduling problems, this paper proposes a grammar-guided LGP to make LGP focus more on promising programs. Our dynamic job shop scheduling simulation results show that the proposed grammar-guided LGP has better training efficiency than basic LGP, and can produce solutions with good explanations. Further analyses show that grammar-guided LGP significantly improves the overall test effectiveness when the number of LGP registers increases.

Of great value to modern municipalities is the task of emergency medical response in the community. Resource allocation is vital to ensure minimal response times, which we may perform via human experts or automate by maximising ambulance coverage. To combat black-box modelling, we propose a modularised Genetic Programming Hyper Heuristic framework to learn the five key decisions of Emergency Medical Dispatch (EMD) within a reactive decision-making process. We minimise the representational distance between our work and reality by working with our local ambulance service to design a set of heuristics approximating their current decision-making processes and a set of synthetic datasets influenced by existing patterns in practice. Through our modularised framework, we learn each decision independently to identify those most valuable to EMD and learn all five decisions simultaneously, improving performance by 69% on the largest novel dataset. We analyse the decision-making logic behind several learned rules to further improve our understanding of EMD. For example, we find that emergency urgency is not necessarily considered when dispatching idle ambulances in favour of maximising fleet availability.

For solving combinatorial optimisation problems with metaheuristics, different search operators are applied for sampling new solutions in the neighbourhood of a given solution. It is important to understand the relationship between operators for various purposes, e.g., adaptively deciding when to use which operator to find optimal solutions efficiently. However, it is difficult to theoretically analyse this relationship, especially in the complex solution space of combinatorial optimisation problems. In this paper, we propose to empirically analyse the relationship between operators in terms of the correlation between their local optima and develop a measure for quantifying their relationship. The comprehensive analyses on a wide range of capacitated vehicle routing problem benchmark instances show that there is a consistent pattern in the correlation between commonly used operators. Based on this newly proposed local optima correlation metric, we propose a novel approach for adaptively selecting among the operators during the search process. The core intention is to improve search efficiency by preventing wasting computational resources on exploring neighbourhoods where the local optima have already been reached. Experiments on randomly generated instances and commonly used benchmark datasets are conducted. Results show that the proposed approach outperforms commonly used adaptive operator selection methods.

Evolutionary multitask multiobjective learning has been widely used for handling more than one multiobjective task simultaneously. However, it is rarely used in dynamic combinatorial optimization problems, which have valuable practical applications such as dynamic flexible job-shop scheduling (DFJSS) in manufacturing. Genetic programming (GP), as a popular hyperheuristic approach, has been used to learn scheduling heuristics for generating schedules for multitask single-objective DFJSS only. Searching in the heuristic space with GP is more difficult than in the solution space, since a small change on heuristics can lead to ineffective or even infeasible solutions. Multiobjective DFJSS is more challenging than single DFJSS, since a scheduling heuristic needs to cope with multiple objectives. To tackle this challenge, we first propose a multipopulation-based multitask multiobjective GP algorithm to preserve the quality of the learned scheduling heuristics for each task. Furthermore, we develop a multitask multiobjective GP algorithm with a task-oriented knowledge-sharing strategy to further improve the effectiveness of learning scheduling heuristics for DFJSS. The results show that the designed multipopulation-based GP algorithms, especially the one with the task-oriented knowledge-sharing strategy, can achieve good performance for all the examined tasks by maintaining the quality and diversity of individuals for corresponding tasks well. The learned Pareto fronts also show that the GP algorithm with task-oriented knowledge-sharing strategy can learn competitive scheduling heuristics for DFJSS on both of the objectives.

Evolutionary computation (EC) algorithms have been successfully applied to the small-scale water distribution network (WDN) optimization problem. However, due to the city expansion, the network scale grows at a fast speed so that the efficacy of many current EC algorithms degrades rapidly. To solve the large-scale WDN optimization problem effectively, a two-stage swarm optimizer with local search (TSOL) is proposed in this article. To address the issues caused by the large-scale and multimodal characteristics of the problem, the proposed algorithm divides the optimization process into an exploration stage and an exploitation stage. It first finds a promising region of the search space in the exploration stage. Then, it searches thoroughly in the promising region to obtain the final solution in the exploitation stage. To search effectively the huge search space, we propose an improved level-based learning optimizer and use it in both the exploration and exploitation stages. Two new local search algorithms are proposed to further improve the quality of the solution. Experiments on both synthetic benchmark networks and a real-world network show that the proposed algorithm has outperformed the state-of-the-art metaheuristic algorithms.

Uncertainty is ubiquitous in real-world routing applications. The automated design of the routing policy by hyperheuristic methods is an effective technique to handle the uncertainty and to achieve online routing for dynamic or stochastic routing problems. Currently, the tree representation routing policy evolved by genetic programming is commonly adopted because of the remarkable flexibility. However, numeric representations have never been used. Considering the practicability of the numeric representations and the capability of the numeric optimization methods, in this article, we investigate two numeric representations on a representative stochastic routing problem and uncertain capacitated arc routing problem. Specifically, a linear representation and an artificial neural-network (ANN) representation are implemented and compared with the tree representation to reveal the potential of the numeric representations and the characteristics of their optimization. Experimental results show that the tree representation is the best choice, but on a majority of the test instances, the numeric representations, especially the ANN representation, can provide competitive performance. Further analyses also show that training a good ANN representation policy requires more training data than the tree representation. Finally, a guideline of representation selection is given.

Explainable artificial intelligence (XAI) has received great interest in the recent decade, due to its importance in critical application domains, such as self-driving cars, law, and healthcare. Genetic programming (GP) is a powerful evolutionary algorithm for machine learning. Compared with other standard machine learning models such as neural networks, the models evolved by GP tend to be more interpretable due to their model structure with symbolic components. However, interpretability has not been explicitly considered in GP until recently, following the surge in the popularity of XAI. This article provides a comprehensive review of the studies on GP that can potentially improve the model interpretability, both explicitly and implicitly, as a byproduct. We group the existing studies related to explainable artificial intelligence by GP into two categories. The first category considers the intrinsic interpretability, aiming to directly evolve more interpretable (and effective) models by GP. The second category focuses on post-hoc interpretability, which uses GP to explain other black-box machine learning models, or explain the models evolved by GP by simpler models such as linear models. This comprehensive survey demonstrates the strong potential of GP for improving the interpretability of machine learning models and balancing the complex tradeoff between model accuracy and interpretability.

The uncertain capacitated arc routing problem (UCARP) is an NP-hard combinatorial optimization problem with a wide range of applications in logistics domains. Genetic programming (GP) hyper-heuristic has been successfully applied to evolve routing policies to effectively handle the uncertain environment in this problem. The real world usually encounters different but related instances due to events, such as season change and vehicle breakdowns, and it is desirable to transfer knowledge gained from solving one instance to help solve another related one. However, the solutions found by the GP process can lack diversity, and the existing methods use the transferred knowledge mainly during initialization. Thus, they cannot sufficiently handle the change from the source to the target instance. To address this issue, we develop a novel knowledge transfer GP with an auxiliary population. In addition to the main population for the target instance, we initialize an auxiliary population using the transferred knowledge and evolve it alongside the main population. We develop a novel scheme to carefully exchange the knowledge between the two populations, and a surrogate model to evaluate the auxiliary population efficiently. The experimental results confirm that the proposed method performed significantly better than the state-of-the-art GP approaches for a wide range of uncertain arc routing instances, in terms of both final performance and convergence speed.

The multi/many-objective traveling salesman problem (MOTSP), which is NP-hard, can be found in many real-world applications. The Lin–Kernighan (LK) algorithm, as one of the most successful local search (LS) methods for the single-objective traveling salesman problem, adopts a variable neighborhood LS. However, LK cannot be directly applied to the decomposition-based multiobjective optimization framework due to its incapability of effective knowledge transfer among different subproblems, especially for problems with more than two objectives. In this article, we propose an algorithm, called decomposition-based multiobjective LK heuristic with neighborhood structure transfer (NST-MOLK) for MOTSP. In NST-MOLK, the knowledge of a neighborhood structure has been transferred to enhance the efficiency and effectiveness of LK. The experimental studies have been conducted on both benchmark and real-world instances constructed based on the flight prices of seven airlines and 266 airports of different cities in China. Experimental results show that NST-MOLK outperforms both classical and state-of-the-art algorithms significantly. It has also been verified that neighborhood structure transfer can effectively improve the performance of NST-MOLK.

The uncertain capacitated arc routing problem (UCARP) is an important combinatorial optimization problem with many applications in the real world. Genetic programming hyper-heuristic has been successfully used to automatically evolve routing policies, which can make real-time routing decisions for UCARPs. It is desired to evolve routing policies that are both effective and small/simple to be easily understood. The effectiveness and size are two potentially conflicting objectives. A further challenge is the objective selection bias issue, i.e., it is much more likely to obtain small but ineffective routing policies than the effective ones that are typically large. In this article, we propose a new multiobjective genetic programming algorithm to evolve effective and small routing policies. The new algorithm employs the α dominance strategy with a newly proposed α adaptation scheme to address the objective selection bias issue. In addition, it contains a new archive strategy to prevent the loss of promising individuals due to the rotation of training instances. The experimental results showed that the newly proposed algorithm can evolve significantly better routing policies than the current state-of-the-art algorithms for UCARP in terms of both effectiveness and size. We have also analyzed the evolved routing policies to show better interpretability.

Genetic programming (GP) has achieved great success for learning scheduling heuristics in dynamic job-shop scheduling (JSS). In theory, generating a large number of offspring for GP, known as brood recombination, can improve its heuristic generation ability. However, it is time consuming to evaluate extra individuals. Phenotypic characterization-based surrogates with K-nearest neighbors have been successfully used for GP to preselect only promising individuals for real fitness evaluations in dynamic JSS. However, sample individuals used by surrogate are from only the current generation, since the fitness of individuals across generations is not comparable due to the rotation of training instances. The surrogate cannot accurately estimate the fitness of an offspring that is far away from all the limited sample individuals at the current generation. This article proposes an effective instance-rotation-based surrogate to address the above issue. Specifically, the surrogate uses the samples extracted from individuals across multiple generations with different instances. More importantly, we propose a fitness mapping strategy to make the fitness evaluated by different instances comparable. The results show that the GP with brood recombination and the proposed surrogate can significantly improve the quality of scheduling heuristics. The results also reveal that the proposed algorithm has successfully reduced the number of omitted promising offspring due to the higher accuracy of the surrogate. The samples in the new surrogate spread better in the phenotypic space, and the nearest neighbor tends to be closer to the predicted offspring. This makes the estimated fitness more accurate.

Multitask learning has been successfully used in handling multiple related tasks simultaneously. In reality, there are often many tasks to be solved together, and the relatedness between them is unknown in advance. In this article, we focus on the multitask genetic programming (GP) for the dynamic flexible job shop scheduling (DFJSS) problems, and address two challenges. The first is how to measure the relatedness between tasks accurately. The second is how to select task pairs to transfer knowledge during the multitask learning process. To measure the relatedness between DFJSS tasks, we propose a new relatedness metric based on the behavior distributions of the variable-length GP individuals. In addition, for more effective knowledge transfer, we develop an adaptive strategy to choose the most suitable assisted task for the target task based on the relatedness information between tasks. The findings show that in all of the multitask scenarios studied, the proposed algorithm can substantially increase the effectiveness of the learned scheduling heuristics for all the desired tasks. The effectiveness of the proposed algorithm has also been verified by the analysis of task relatedness and structures of the evolved scheduling heuristics, and the discussions of population diversity and knowledge transfer.

DynamicWorkflowScheduling inFogComputing (DWSFC) is an important optimisation problem with many real-world applications. The current workflow scheduling problems only consider cloud servers but ignore the roles of mobile devices and edge servers. Some applications need to consider the mobile devices, edge, and cloud servers simultaneously, making them work together to generate an effective schedule. In this article, a new problem model for DWSFC is considered and a new simulator is designed for the new DWSFC problem model. The designed simulator takes the mobile devices, edge, and cloud servers as a whole system, where they all can execute tasks. In the designed simulator, two kinds of decision points are considered, which are the routing decision points and the sequencing decision points. To solve this problem, a newMulti-TreeGeneticProgramming (MTGP) method is developed to automatically evolve scheduling heuristics that can make effective real-time decisions on these decision points. The proposed MTGP method with a multi-tree representation can handle the routing decision points and sequencing decision points simultaneously. The experimental results show that the proposed MTGP can achieve significantly better test performance (reduce the makespan by up to 50%) on all the tested scenarios than existing state-of-the-art methods.

Counterfactual explanations are a popular eXplainable AI technique, used to provide contrastive answers to “what-if” questions. These explanations are consistent with the way that an everyday person will explain an event, and have been shown to satisfy the ‘right to explanation’ of the European data regulations. Despite this, current work to generate counterfactual explanations either makes assumptions about the model being explained or utlises algorithms that perform suboptimally on continuous data. This work presents two novel algorithms to generate counterfactual explanations using Particle Swarm Optimization (PSO) and Differential Evolution (DE). These are shown to provide effective post-hoc explanations that make no assumptions about the underlying model or data structure. In particular, PSO is shown to generate counterfactual explanations that utilise significantly fewer features to generate sparser explanations when compared to previous related work.

Assigning ambulances to emergencies in real-time, ensuring both that patients receive adequate care and that the fleet remains capable of responding to any potential new emergency, is a critical component of any ambulance service. Thus far, most techniques to manage this problem are as convoluted as the problem itself. As such, many real-world medical services resort to using the naive closest-idle rule, whereby the nearest available vehicles are dispatched to serve each new call. This paper explores the feasibility of using a genetic programming hyper heuristic (GPHH) in order to generate intelligible rules of thumb to select which vehicles should attend any given emergency. Such rules, either manually or automatically designed, are evaluated within a novel solution construction procedure which constructs solutions to the ambulance dispatching problem given the parameters of the simulation environment. Experimental results suggest that GPHH is a promising technique to use when approaching the ambulance dispatching problem. Further, a GPHH-evolved rule's interpretability allows for detailed semantic analysis into which features of the environment are valuable to the decision making process, allowing for human dispatching agents to make more informed decisions in practice.

Job Shop Scheduling (JSS) is an important real-world problem. However, the problem is challenging because of many conflicting objectives and the complexity of production flows. Genetic programming-based hyper-heuristic (GP-HH) is a useful approach for automatically evolving effective dispatching rules for many-objective JSS. However, the evolved Pareto-front is highly irregular, seriously affecting the effectiveness of GP-HH. Although the reference points method is one of the most prominent and efficient methods for diversity maintenance in many-objective problems, it usually uses a uniform distribution of reference points which is only appropriate for a regular Pareto-front. In fact, some reference points may never be linked to any Pareto-optimal solutions, rendering them useless. These useless reference points can significantly impact the performance of any reference-point-based many-objective optimization algorithms such as NSGA-III. This paper proposes a new reference point adaption process that explicitly constructs the distribution model using Gaussian process to effectively reduce the number of useless reference points to a low level, enabling a close match between reference points and the distribution of Pareto-optimal solutions. We incorporate this mechanism into NSGA-III to build a new algorithm called MARP-NSGA-III which is compared experimentally to several popular many-objective algorithms. Experiment results on a large collection of many-objective benchmark JSS instances clearly show that MARP-NSGA-III can significantly improve the performance by using our Gaussian Process-based reference point adaptation mechanism.

Dynamic flexible job shop scheduling (DF JSS) is a complex and challenging combinatorial optimisation problem. In DF JSS, job operations have to be processed on a set of machines, and thus machine assignment and operation sequencing decisions need to be made simultaneously in dynamic situations. Genetic programming (GP), as a hyper-heuristic approach, has been widely used to learn scheduling heuristics for DF JSS automati-cally. However, the traditional GP parent selection method based on fitness value only may not be sufficiently effective, since not all the subtrees of a GP individual are meaningful and can contribute to the goodness of the individual. This paper proposes a new GP algorithm with a novel fitness function by incorporating the subtree importance into the parent selection method. Specifically, the subtree importance is measured by the correlation coefficient between the behaviour of subtrees and the GP individual. The proposed algorithm is expected to improve the effectiveness of GP by capturing more useful subtrees for producing offspring to the next generation. This paper uses nine DF JSS scenarios to examine the effectiveness of the proposed algorithm. The results show that the proposed algorithm achieves slightly better performance in some of the scenarios while no worse in all other scenarios. Further analyses, including the effect of the designed fitness function and sizes of the learned scheduling heuristics, are also conducted.

Dynamic flexible job shop scheduling is a challenging combinatorial optimisation problem, that aims to optimise machine resources for producing jobs to meet some goals. There are two important kinds of decisions that the scheduling process needs to make under dynamic environments, i.e., the routing decision for machine assignment and the sequencing decision for operation ordering. Genetic programming hyper-heuristic has been successfully applied for solving the dynamic flexible job shop scheduling problem with the advantage of automat-ically evolving good scheduling heuristics. Parent selection is an important process for genetic programming, intending to select good individuals as parents to generate offspring for the next generation. Traditional genetic programming methods select parents for crossover based on only fitness (e.g., tournament selection). In this paper, a new parent selection (i.e., cluster selection) method is proposed to select parents not only with good fitness but also with different behaviours. The proposed cluster selection is combined with genetic programming hyper-heuristic to study whether considering different behaviours in parent selection will improve the effectiveness of the evolved scheduling heuristics. The experimental results show that increasing the number of unique behaviours in the population cannot help evolve effective scheduling heuristics. Further analysis shows that considering behaviour to select parents does increase the number of unique behaviours in the population. However, it gives individuals with poor fitness more probability to be selected to generate offspring. This might be the reason why the proposed method cannot outperform the baseline method.

Dynamic flexible job shop scheduling has attracted widespread interest from scholars and industries due to its practical value. Genetic programming hyper-heuristic has achieved great success in automatically evolving effective scheduling heuristics to make real-time decisions (i.e., operation ordering and machine assignment) for dynamic flexible job shop scheduling. The design of the training set and fitness evaluation play key roles in improving the generalisation of the evolved scheduling heuristics. The commonly used strategies for improving the generalisation of learned scheduling heuristics include using multiple instances for evaluation at each generation or using a single instance but changing the instance at each new generation of the training process of genetic programming. However, using multiple instances is time-consuming, while changing a single instance at each new generation, potentially promising individuals that happen to underperform in one particular generation might be lost. To address this issue, this paper develops a genetic programming method with a multi-case fitness evaluation strategy, which is named GPMF to evolve the scheduling heuristics with better generalisation ability for the dynamic flexible job shop scheduling problem. The proposed multi-case fitness evaluation strategy divides one instance into multiple cases and uses the average value of the multi-case objectives as the fitness. Experimental results show that the proposed GPMF algorithm is significantly better than the baseline method in all the tested scenarios.

Dynamic flexible job shop scheduling is an important combinatorial optimisation problem that covers valuable practical applications such as order picking in warehouses and service allocation in cloud computing. Machine assignment and operation sequencing are two key decisions to be considered simultaneously in dynamic flexible job shop scheduling. Genetic programming has been successfully and widely used to learn scheduling heuristics, including a routing rule for machine assignment and a sequencing rule for operation sequencing simultaneously. There are mainly two types of learning strategies to evolve scheduling heuristics, i.e., learning one rule by fixing the other rule, and learning the routing rule and the sequencing rule simultaneously. However, there is no guidance on which learning strategy to use in specific cases. To fill this gap, this paper provides a comprehensive study of learning strategies on scheduling heuristics of genetic programming in dynamic flexible job shop scheduling by comparing five learning strategies, including two strategies that are extended from the existing studies. The results show that learning two rules simultaneously, either using cooperative coevolution or multi-tree representation, is more effective than only learning one type of rule. Cooperative coevolution is recommended if an algorithm aims to handle a problem by dividing it into small sub-problems, and focuses on the characteristics of routing rule and sequencing rule. Genetic programming with multi-tree representation that treats the routing rule and the sequencing rule as an individual, is preferred to reduce the complexities of algorithms.

The Large-Scale Vehicle Routing Problem is an NP-hard combinatorial optimisation problem with many challenges regarding the increasing number of possible solutions. To reduce the search space, limiting the neighbourhood size for the neighbourhood search approaches is a commonly used strategy to reach a good balance between efficiency and effectiveness. However, it lacks generalisability, since setting a fixed neighbourhood limit might be below optimal for certain instances. In this work, a heuristic method that automatically changes the neighbourhood size is proposed. The heuristic increases or decreases the search scope of the neighbourhood search operators to better match the search process. It does that by looking at the moving trajectories of the previous iteration. We combine the proposed online neighbourhood size adaption heuristic with the highly-efficient Knowledge-Guided Local Search (KGLS) and successfully achieved up to almost 40% improvement to the efficiency. Furthermore, the experiment results show that the KGLS with the adaptive neighbour size heuristic can obtain statistically better solutions on 50 out of the 110 instances compared, while worse on only 25 instances.

An emerging optimisation problem from real-world applications, named the multi-point dynamic aggregation (MPDA) problem, has become an active research of the multi-robot system. This paper focuses on a multi-objective MPDA (MO-MPDA) problem which is to design execution plans of robots for minimising the cost of used robots and maximising the efficiency of task execution. The MOMPDA problem has the issues of conflicting objectives, redundant representation, and variable-length encoding, posing extra challenges to address the MO-MPDA problem effectively. Combining the ∊-constraint method and decomposition mechanisms, a novel multi-objective evolutionary algorithm is proposed. The proposed algorithm selects the efficiency objective as the main objective and converts the cost objective as constraints. Thus, the multi-objective problem is decomposed into a series of scalar constrained optimisation subproblems by assigning each subproblem with an upper bound constraint. All the subproblems are optimised and evolved simultaneously with the transferring knowledge from other sub-problems to solve the MO-MPDA problem parallelly and efficiently. Besides, considering the characteristics of parent individuals, this paper designs a hybrid reproduction mechanism to transmit effective information to offspring individuals for tackling the encoding redundancy and varying-length. Experimental results show that the proposed algorithm significantly outperforms the state-of-the-art algorithms in terms of most-used metrics.

Linear genetic programming (LGP) has been successfully applied to various problems such as classification, symbolic regression and hyper-heuristics for automatic heuristic design. In contrast with the traditional tree-based genetic programming (TGP), LGP uses a sequence of instructions to represent an individual (program), and the data is carried by registers. A common issue of LGP is that LGP is susceptible to introns (i.e., instructions with no effect to the program output), which limits the effectiveness of traditional genetic operators. To address these issues, we propose a new graph-based LGP system. Specifically, graph-based LGP uses graph-based crossover and graph-based mutation to produce offspring. The graph-based crossover operator firstly converts each LGP parent to a directed acyclic graph (DAG), and then swaps the sub-graphs between the DAGs. The graph-based mutation selectively modify the connections in DAGs based on the height of sub graphs. To verify the effectiveness of the new graph-based genetic operators, we take the dynamic job shop scheduling as a case study, which has shown to be a challenging problem for LGP. The experimental results show that the LGP with the new graph-based genetic operators can obtain better scheduling heuristics than the LGP with the traditional operators and TGP.

The Uncertain Capacitated Arc Routing Problem (UCARP) is a well-known combinatorial optimisation problem that has many real-world applications. Genetic Programming is usually utilised to handle UCARP by evolving effective routing policies, which can respond to the uncertain environment in real-time. Previous studies mainly focus on the effectiveness of the routing policies but ignore the interpretability. In this paper, we focus on post-hoc interpretability, which explains a pre-trained complex routing policy. Unlike the existing explanation methods for classification/regression models, the behaviour of a routing policy is characterised as a ranking process rather than predicting a single output. To address this issue, this paper proposes a Local Ranking Explanation (LRE) method for GP-evolved routing policies for UCARP. Given a UCARP decision situation, LRE trains a linear model that gives the same ranks of the candidate tasks as those of the explained routing policy. The experimental results demonstrate that LRE can obtain more interpretable linear models that have highly correlated and consistent behaviours with the original routing policy in most decision situations. By analysing coefficients and attribute importance of the linear model, we managed to provide a local explanation of the original routing policy in a decision situation.

Containers are lightweight and provide the potential to reduce more energy consumption of data centers than Virtual Machines (VMs) in container-based clouds. On-line resource allocation is the most common operation in clouds. However, the on-lineResource Allocation in Container-based clouds (RAC)is new and challenging because of its two-level architecture, i.e., the allocations of containers to VMs and the allocation of VMs to physical machines. These two allocations interact with each other, and hence cannot be made separately. Since on-line container allocation requires a real-time response, most current allocation techniques rely on heuristics (e.g., First Fit and Best Fit), which do not consider the comprehensive information such as workload patterns and VM types. As a result, resources are not used efficiently and the energy consumption is not sufficiently optimized. We first propose a novel model of the on-lineRACproblem with the consideration of VM overheads, VM types and an affinity constraint. Then, we design a Cooperative Coevolution Genetic Programming (CCGP) hyper-heuristic approach to solve theRACproblem, namedCCGP-RAC.CCGP-RACcan learn the workload patterns and VM types from historical workload traces and generate allocation rules. The experiments show significant improvement in energy consumption compared to the state-of-the-art algorithms.

Multipoint dynamic aggregation is a meaningful optimization problem due to its important real-world applications, such as post-disaster relief, medical resource scheduling, and bushfire elimination. The problem aims to design the optimal plan for a set of robots to execute geographically distributed tasks. Unlike the majority of scheduling and routing problems, the tasks in this problem can be executed by multiple robots collaboratively. Meanwhile, the demand of each task changes over time at an incremental rate and is affected by the abilities of the robots executing it. This poses extra challenges to the problem, as it has to consider complex coupled relationships among robots and tasks. To effectively solve the problem, this article develops a new metaheuristic algorithm, called adaptive coordination ant colony optimization (ACO). We develop a novel coordinated solution construction process using multiple ants and pheromone matrices (each robot/ant forages a path according to its own pheromone matrix) to effectively handle the collaborations between robots. We also propose adaptive heuristic information based on domain knowledge to promote efficiency, a pheromone-based repair mechanism to tackle the tight constraints of the problem, and an elaborate local search to enhance the exploitation ability of the algorithm. The experimental results show that the proposed adaptive coordination ACO significantly outperforms the state-of-the-art methods in terms of both effectiveness and efficiency.

The multipoint dynamic aggregation (MPDA) problem of the multirobot system is of great significance for its real-world applications such as bush fire elimination. The problem is to design the optimal plan for a set of heterogeneous robots to complete some geographically distributed tasks collaboratively. In this article, we consider the dynamic version of the problem, where new tasks keep appearing after the robots are dispatched from the depot. The dynamic MPDA problem is a complicated optimization problem due to several characteristics, such as the collaboration of robots, the accumulative task demand, the relationships among robots and tasks, and the unpredictable task arrivals. In this article, a new model of the problem considering these characteristics is proposed. To solve the problem, we develop a new genetic programming hyperheuristic (GPHH) method to evolve reactive coordination strategies (RCSs), which can guide the robots to make decisions in real time. The proposed GPHH method contains a newly designed effective RCS heuristic template to generate the execution plan for the robots according to a GP tree. A new terminal set of features related to both robots and tasks and a cluster filter that assigns the robots to urgent tasks are designed. The experimental results show that the proposed GPHH significantly outperformed the state-of-the-art methods. Through further analysis, useful insights such as how to distribute and coordinate robots to execute different types of tasks are discovered.

Cooperative co-evolutionary algorithms have addressed many large-scale problems successfully, but the nonseparable large-scale problems with overlapping subcomponents are still a serious difficulty that has not been conquered yet. First, the existence of shared variables makes the problem hard to be decomposed. Second, existing cooperative co-evolutionary frameworks usually cannot maintain the two crucial factors: high cooperation frequency and effective computing resource allocation, simultaneously when optimizing the overlapping subcomponents. Aiming at these two issues, this article proposes a new contribution-based cooperative co-evolutionary algorithm to decompose and optimize nonseparable large-scale problems with overlapping subcomponents effectively and efficiently: 1) a contribution-based decomposition method is proposed to assign the shared variables. Among all the subcomponents containing a shared variable, the one that contributes the most to the entire problem will include the shared variable and 2) to achieve the two crucial factors at the same time, a new contribution-based optimization framework is designed to award the important subcomponents based on the round-robin structure. Experimental studies show that the proposed algorithm performs significantly better than the state-of-the-art algorithms due to the effective grouping structure generated by the proposed decomposition method and the fast optimizing speed provided by the new optimization framework.

The development of electric vehicle (EV) techniques has led to a new vehicle routing problem (VRP) called the capacitated EV routing problem (CEVRP). Because of the limited number of charging stations and the limited cruising range of EVs, not only the service order of customers but also the recharging schedules of EVs should be considered. However, solving these two aspects of the problem together is very difficult. To address the above issue, we treat CEVRP as a bilevel optimization problem and propose a novel bilevel ant colony optimization algorithm in this article, which divides CEVRP into two levels of subproblem: 1) capacitated VRP and 2) fixed route vehicle charging problem. For the upper level subproblem, the electricity constraint is ignored and an order-first split-second max-min ant system algorithm is designed to generate routes that fulfill the demands of customers. For the lower level subproblem, a new effective heuristic is designed to decide the charging schedule in the generated routes to satisfy the electricity constraint. The objective values of the resultant solutions are used to update the pheromone information for the ant system algorithm in the upper level. Through good orchestration of the two components, the proposed algorithm can significantly outperform state-of-the-art algorithms on a wide range of benchmark instances.

The capacitated arc routing problem (CARP) has attracted much attention for its many practical applications. The large-scale multidepot CARP (LSMDCARP) is an important CARP variant, which is very challenging due to its vast search space. To solve LSMDCARP, we propose an iterative improvement heuristic, called route clustering and search heuristic (RoCaSH). In each iteration, it first (re)decomposes the original LSMDCARP into a set of smaller single-depot CARP subproblems using route cutting off and clustering techniques. Then, it solves each subproblem using the effective Ulusoy's split operator and local search. On one hand, the route clustering helps the search for each subproblem by focusing more on the promising areas. On the other hand, the subproblem solving provides better routes for the subsequent route cutting off and clustering, leading to better problem decomposition. The proposed RoCaSH was compared with the state-of-the-art MDCARP algorithms on a range of MDCARP instances, including different problem sizes. The experimental results showed that RoCaSH significantly outperformed the state-of-the-art algorithms, especially for the large-scale instances. It managed to achieve much better solutions within a much shorter computational time.

Evolutionary multitask learning has achieved great success due to its ability to handle multiple tasks simultaneously. However, it is rarely used in the hyperheuristic domain, which aims at generating a heuristic for a class of problems rather than solving one specific problem. The existing multitask hyperheuristic studies only focus on heuristic selection, which is not applicable to heuristic generation. To fill the gap, we propose a novel multitask generative hyperheuristic approach based on genetic programming (GP) in this article. Specifically, we introduce the idea in evolutionary multitask learning to GP hyperheuristics with a suitable evolutionary framework and individual selection pressure. In addition, an origin-based offspring reservation strategy is developed to maintain the quality of individuals for each task. To verify the effectiveness of the proposed approach, comprehensive empirical studies have been conducted on the homogeneous and heterogeneous multitask dynamic flexible job shop scheduling. The results show that the proposed algorithm can significantly improve the quality of scheduling heuristics for each task in all the examined scenarios. In addition, the evolved scheduling heuristics verify the mutual help among the tasks in a multitask scenario.

Dynamic flexible job shop scheduling (JSS) has received widespread attention from academia and industry due to its practical application value. It requires complex routing and sequencing decisions under unpredicted dynamic events. Genetic programming (GP), as a hyperheuristic approach, has been successfully applied to evolve scheduling heuristics for JSS due to its flexible representation. However, the simulation-based evaluation is computationally expensive since there are many calculations based on individuals for making decisions in the simulation. To improve training efficiency, this article proposes a novel multifidelity-based surrogate-assisted GP. Specifically, multifidelity-based surrogate models are first designed by simplifying the problem expected to be solved. In addition, this article proposes an effective collaboration mechanism with knowledge transfer for utilizing the advantages of multifidelity-based surrogate models to solve the desired problems. This article examines the proposed algorithm in six different scenarios. The results show that the proposed algorithm can dramatically reduce the computational cost of GP without sacrificing the performance in all scenarios. With the same training time, the proposed algorithm can achieve significantly better performance than its counterparts in most scenarios while no worse in others.

The uncertain capacitated arc routing problem has many real-world applications in logistics domains. Genetic programming (GP) is a promising approach to training routing policies to make real-time decisions and handle uncertain events effectively. In the real world, there are various problem domains and no single routing policy can work effectively in all of them. Instead of training in isolation, we can leverage the relatedness between the problems and transfer knowledge from previously solved source problems to solve the target problem. The existing transfer methods are not effective enough due to the loss of diversity during the knowledge transfer. To increase the diversity of the transferred knowledge, in this article, we propose a novel GP method that removes phenotypic duplicates from the source individuals to initialize the target individuals. Furthermore, assuming that the transferred knowledge used in initialization already includes all the important knowledge explored for the source problem, it is more effective to explore new regions that have not been explored for the source problem. Therefore, we propose novel genetic operators that prohibit the search from revisiting the source individuals when solving the target problem. To speed up the revisit check, we propose to adapt a powerful hashing method for routing policies that greatly improves the efficiency of the genetic operators. Our experimental results show that the proposed method significantly outperforms the existing GP approaches with knowledge transfer in terms of both initial and final solution quality.

Many practical multiobjective optimization problems have a nested bilevel structure in variables, which can be modeled as bilevel multiobjective optimization problems (BLMOPs). In this article, a cooperative coevolution (CC) with knowledge-based variable decomposition, called bilevel multiobjective CC (BLMOCC), is proposed for BLMOPs. In BLMOCC, the variable interactions are represented by an interaction matrix. The perturbation-based variable decomposition combined with the matrix completion approach has been designed for dynamically discovering the correlation among the bilevel variables, based on which the variables are divided into different groups. To further handle possible weak correlations among various groups of variables, a CC has been adopted for optimizing them in a collaborative way. In experimental studies, BLMOCC is compared with a nested method (NS) and a state-of-the-art algorithm (H-BLEMO) on a set of benchmark problems. The effects of each component in BLMOCC have also been verified by comparing it with its three variants. The experimental results demonstrate that BLMOCC has the best performance among all the compared algorithms. In addition, BLMOCC has also been applied to a real-world management decision-making problem, which further validates its efficiency and effectiveness.

The blossoming of electric vehicles gives rise to a new vehicle routing problem (VRP) called capacitated electric VRP. Since charging is not as convenient as refueling, both the service of customers and the recharging of vehicles should be considered. In this article, we propose a confidence-based bilevel ant colony optimization (ACO) algorithm to solve the problem. It divides the whole problem into the upper level subproblem capacitated VRP and the lower level subproblem fixed routing vehicle charging problem. For the upper level subproblem, an ACO algorithm is used to generate customer service sequence. Both the direct encoding scheme and the order-first split-second encoding scheme are implemented to make a guideline of their applicable scenes. For the lower level subproblem, a new heuristic called simple enumeration is proposed to generate recharging schedules for vehicles. Between the two subproblems, a confidence-based selection method is proposed to select promising customer service sequence to conduct local search and lower level optimization. By setting adaptive confidence thresholds, the inferior service sequences that have little chance to become the iteration best are eliminated during the execution. The experiments show that the proposed algorithm has reached the state-of-the-art level and updated eight best known solutions of the benchmark.

The uncertain capacitated arc routing problem is an important optimization problem with many real-world applications. Genetic programming is considered a promising hyper-heuristic technique to automatically evolve routing policies that can make effective real-time decisions in an uncertain environment. Most existing research on genetic programming hyper-heuristic for the uncertain capacitated arc routing problem only focused on the test performance aspect. As a result, the routing policies evolved by genetic programming are usually too large and complex, and hard to comprehend. To evolve effective, smaller, and simpler routing policies, this article proposes a novel genetic programming approach, which simplifies the routing policies during the evolutionary process using a niching technique. The simplified routing policies are stored in an external archive. We also developed new elitism, parent selection, and breeding schemes for generating offspring from the original population and the archive. The experimental results show that the newly proposed approach can achieve significantly better test performance than the current state-of-the-art genetic programming algorithms for the uncertain capacitated arc routing problem. The evolved routing policies are smaller, and thus potentially more interpretable.

The Uncertain Capacited Arc Routing Problem (UCARP) is an important routing problem that can model uncertainties of real-world scenarios. Genetic Programming (GP) is a powerful method for evolving routing policies for vehicles to enable them make real-time decisions and handle environmental uncertainties. When facing various problem domains, knowledge transfer can improve the effectiveness of the GP training. Previous studies have demonstrated that due to the existence of duplicated GP individuals in the source domain, the existing transfer learning methods do not perform satisfactorily for UCARP. To address this issue, in this work, we propose a method for detecting duplicates in the source domain and initialising the GP population in the target domain with phenotypically unique individuals. Additionally, since the presence of duplicates can limit the number of good GP individuals, we propose a surrogate-assisted initialisation approach that is able to generate much more diversely distributed initial individuals in the target domain. Our experiments demonstrate that our proposed transfer learning method can significantly improve the effectiveness of GP for training new UCARP routing policies. Compared with the state-of-the-art GP with knowledge transfer, the proposed approach can obtain significantly better solutions on a wide range of UCRP instances, in terms of both initial and final quality.

The Large Scale Vehicle Routing Problem is a classical NP-hard problem. It has several applications in the industry and has always been the focus of studies and development of new, ever more complex, techniques to solve it. An important group of these techniques are Local Search-based, which are sensitive to the initial solution given to them. However, finding effective initial solutions is not a trivial task, requiring domain knowledge for building them. Although some Genetic Programming Hyper-Heuristics (GPHH) have tried to build better heuristics automatically, they barely give an advantage for improving the solution afterwards. This paper aims to show that Genetic Programming can identify better regions of the search space, where the initial solutions can be improved more efficiently with optimisation steps. This is done by developing new terminals and a new fitness function, which are based on the width of the routes, a metric that was recently found to be an important feature for good solutions. The obtained results show that the proposed approach finds better final solutions than when using classical initial heuristics or other GPHH, for both time efficiency and effectiveness.

The Large Scale Vehicle Routing Problem (LSVRP) is a classical combinatorial optimisation problem that serves several customers on a graph using a set of vehicles. Due to the NP-hardness and large problem size, LSVRP cannot be efficiently solved by exact approaches. Heuristic methods such as the Iterative Local Search or the Hybrid Genetic Algorithm still struggle for finding effective solutions for large scale instances. For these methods to deal with the large search space, pruning techniques are applied in order to limit the number of explored solutions. However, effective pruning is a hard task, requiring domain knowledge to craft good ways of limiting the search space without losing the ability to find better solutions. Hyper-heuristics are types of methods that aim to reduce domain knowledge on the creation of heuristics, and in this work, we also apply them for effective heuristic pruning. Our Evolutionary Hyper-Heuristic (EHH) automatically evolves limits to the solution search space together with the heuristic utilised to build and improve solutions for the LSVRP. We utilise a Guided Local Search (GLS) as the base algorithm in which our EHH searches for the best heuristic configuration. Our results show that the EHH can find better solutions for most LSVRP test instances when compared to the manually designed pruning of the GLS.

Genetic Programming Hyper-Heuristic (GPHH) has been successfully applied to evolve routing policies for the Uncertain Capacitated Arc Routing Problem (UCARP). However, the current GPHH approaches have a limitation that they only consider myopic information of the current decision step. In this paper, we proposed incorporating look-ahead information to the decision process of GP-evolved routing policies. We designed a number of potentially promising chains of candidate tasks, and expand the candidate task pool to consider both the single tasks and task chains. This way, the routing policy can consider the look-ahead information incorporated in the considered task chains. The proposed GP with Chain Policies (GPCP) was compared with the standard GPHH on a range of UCARP instances, and the results showed that the task chains can improve the effectiveness of the routing policies sometimes. The better performance of a routing policy largely depends on whether it can balance the selections of single tasks and task chains, and whether it can stick to the whole selected chain rather than only the first task of the chain. In addition, there are some abnormal runs with serious overfitting issue that we will address in our future work.

Genetic Programming (GP) has been successfully applied to evolve effective dispatching rules for Dynamic Job Shop Scheduling (DJSS). However, the GP-evolved rules are usually too complex and hard to interpret. In this paper, we aim to address this issue by evolving simpler rules without losing effectiveness. To this end, we develop a set of algebraic simplification operators based on our domain knowledge about dynamic scheduling, which can recursively convert a rule into a mathematically equivalent but simpler one. The algebraic simplification operators can guarantee that the individual stays equivalent before and after the simplification. Then, we develop a GP algorithm with these simplification operators. We compared the GP with the simplification operators with the baseline GP without simplification on a range of scheduling instances, and the results showed that using the algebraic simplification can slightly reduce the program size without sacrificing the test performance of the evolved dispatching rules. Furthermore, through deep analysis, we have also discovered the limitations of the pure algebraic simplification for GP to evolve DJSS dispatching rules, which can hardly simplify the individuals after the first generation.

The Uncertain Capacitated Arc Routing Problem (UCARP) has a variety of real-world applications. Genetic Programming Hyper-heuristic (GPHH) is considered a promising technique to handle UCARP. Many scholars have shown the power of GPHH of evolving effective routing policies. However, the size of the evolved routing policies is ignored. Typically, smaller routing policies can have better interpretability and generalisation. Thus, it is necessary to optimise the size along with the effectiveness. The objective selection bias issue arises as the size is much easier to be optimised than effectiveness. The Pareto front is biased to the size gradually during the evolutionary process. To address this issue, we develop an α dominance criteria based Multi-Objective GP with a self-adaptive α scheme (αMOGP-sa). The basic idea of the α dominance criteria is to set tradeoff rates between objectives. For different instances, the search space can be very different. In this case, the self-adaptive α scheme is employed to automatically tuning the α value during the evolutionary process so that we can identify a valid α value for different instances. This paper examines the proposed algorithm in eight different problem instances. The experimental results showed that αMOGP-sa could effectively handle the objective selection bias issue, and evolve much better Pareto front on Hyper-Volume and Inverted Generational Distance than the current state-of-the-art MOGP approach for UCARP in terms of effectiveness and size on all instances. Also, αMOGP-sa can evolve much smaller routing policies than the state-of-art single-objective GPHH without sacrificing effectiveness.

Genetic programming (GP) has achieved great success in evolving effective scheduling rules to make real-time decisions in dynamic flexible job shop scheduling (DFJSS). To improve generalization, a commonly used strategy is to change the training simulation(s) at each generation of the GP process. However, with such a simulation rotation, GP may lose potentially promising individuals that happen to perform poorly in one particular generation. To address this issue, this paper proposed a new multi-tree GP with archive (MTAGP) to evolve the routing and sequencing rules for DFJSS. The archive is used to store the potentially promising individuals of each generation during evolution of genetic programming. The individuals in the archive can then be fully utilized when the simulation is changed in subsequent generations. Through extensive experimental tests, the MTAGP algorithm proposed in this paper is more effective than the multi-tree GP without archive algorithm in a few scenarios. Further experiments were carried out to analyze the use of the archive and some possible guesses were ruled out. We argue that the use of archives does increase the diversity of the population. However, the number of individuals in the archive that ranked in the top five of the new population is small. Therefore, the archive may not be able to greatly improve the performance. In the future, we will investigate better ways to use the archive and better ways to update individuals in the archive.

Uncertain Capacitated Arc Routing Problem (UCARP) is an NP-hard optimisation problem with many applications in logistics domains. Genetic Programming (GP) is capable of evolving routing policies to handle the uncertain environment of UCARP. There are many different but related UCARP domains in the real world to be solved (e.g. winter gritting and waste collection for different cities). Instead of training a routing policy for each of them, we can use the multi-task learning paradigm to improve the training effectiveness by sharing the common knowledge among the related UCARP domains. Previous studies showed that GP population for solving UCARP loses diversity during its evolution, which decreases the effectiveness of knowledge sharing. To address this issue, in this work we propose a novel multi-task GP approach that takes the uniqueness of transferable knowledge, as well as its quality, into consideration. Additionally, the transferred knowledge is utilised in a manner that improves diversity. We investigated the performance of the proposed method with several experimental studies and demonstrated that the designed knowledge transfer mechanism can significantly improve the performance of GP for solving UCARP.

Genetic Programming Hyper-Heuristic (GPHH) is a promising technique to automatically evolve effective routing policies to handle the uncertain environment in the Uncertain Capacitated Arc Routing Problem (UCARP). Previous studies mainly focus on the effectiveness of the evolved routing policies, but the size is ignored. This paper aims to develop new GPHH methods to optimise the effectiveness and the size simultaneously. There are two challenges. First, it is much easier for GP to generate small but ineffective individuals than effective ones, thus the search can be easily stuck with small but ineffective individuals. Second, the effectiveness evaluation in GPHH is stochastic, making it challenging to identify and retain effective individuals. To address these issues, we develop a Two-Stage Multi-Objective GP algorithm with Archive (TSNSGPII-a). The two-stage framework addresses the bias towards the size. The external archive stores potentially effective individuals that may be lost during the evolution, and reuses them to generate offspring. The experimental results show that TSNSGPII-a can obtain significantly better routing policies than the existing state-of-the-art approaches in terms of both effectiveness and size. If selecting the most effective routing policy from the Pareto front, TSNSGPII-a can obtain significantly smaller routing policies with statistically comparable or significantly better effectiveness.

Dynamic Flexible Job Shop Scheduling (DFJSS) is an important and challenging problem, and can have multiple conflicting objectives. Genetic Programming Hyper-Heuristic (GPHH) is a promising approach to fast respond to the dynamic and unpredictable events in DFJSS. A GPHH algorithm evolves dispatching rules (DRs) that are used to make decisions during the scheduling process (i.e., the so-called heuristic template). In DFJSS, there are two kinds of scheduling decisions: the routing decision that allocates each operation to a machine to process it, and the sequencing decision that selects the next job to be processed by each idle machine. The traditional heuristic template makes both routing and sequencing decisions in a non-delay manner, which may have limitations in handling the dynamic environment. In this article, we propose a novel heuristic template that delays the routing decisions rather than making them immediately. This way, all the decisions can be made under the latest and most accurate information. We propose three different delayed routing strategies, and automatically evolve the rules in the heuristic template by GPHH. We evaluate the newly proposed GPHH with Delayed Routing (GPHH-DR) on a multiobjective DFJSS that optimises the energy efficiency and mean tardiness. The experimental results show that GPHH-DR significantly outperformed the state-of-the-art GPHH methods. We further demonstrated the efficacy of the proposed heuristic template with delayed routing, which suggests the importance of delaying the routing decisions.

Dynamic flexible job-shop scheduling (DFJSS) is a challenging combinational optimization problem that takes the dynamic environment into account. Genetic programming hyperheuristics (GPHH) have been widely used to evolve scheduling heuristics for job-shop scheduling. A proper selection of the terminal set is a critical factor for the success of GPHH. However, there is a wide range of features that can capture different characteristics of the job-shop state. Moreover, the importance of a feature is unclear from one scenario to another. The irrelevant and redundant features may lead to performance limitations. Feature selection is an important task to select relevant and complementary features. However, little work has considered feature selection in GPHH for DFJSS. In this article, a novel two-stage GPHH framework with feature selection is designed to evolve scheduling heuristics only with the selected features for DFJSS automatically. Meanwhile, individual adaptation strategies are proposed to utilize the information of both the selected features and the investigated individuals during the feature selection process. The results show that the proposed algorithm can successfully achieve more interpretable scheduling heuristics with fewer unique features and smaller sizes. In addition, the proposed algorithm can reach comparable scheduling heuristic quality with much shorter training time.

Dynamic flexible job shop scheduling (JSS) is a challenging combinatorial optimization problem due to its complex environment. In this problem, machine assignment and operation sequencing decisions need to be made simultaneously under the dynamic environments. Genetic programming (GP), as a hyperheuristic approach, has been successfully used to evolve scheduling heuristics for dynamic flexible JSS. However, in traditional GP, recombination between parents may disrupt the beneficial building blocks by choosing the crossover points randomly. This article proposes a recombinative mechanism to provide guidance for GP to realize effective and adaptive recombination for parents to produce offspring. Specifically, we define a novel measure for the importance of each subtree of an individual, and the importance information is utilized to decide the crossover points. The proposed recombinative guidance mechanism attempts to improve the quality of offspring by preserving the promising building blocks of one parent and incorporating good building blocks from the other. The proposed algorithm is examined on six scenarios with different configurations. The results show that the proposed algorithm significantly outperforms the state-of-the-art algorithms on most tested scenarios, in terms of both final test performance and convergence speed. In addition, the rules obtained by the proposed algorithm have good interpretability.

Dynamic flexible job shop scheduling (JSS) is an important combinatorial optimization problem with complex routing and sequencing decisions under dynamic environments. Genetic programming (GP), as a hyperheuristic approach, has been successfully applied to evolve scheduling heuristics for JSS. However, its training process is time consuming, and it faces the retraining problem once the characteristics of job shop scenarios vary. It is known that multitask learning is a promising paradigm for solving multiple tasks simultaneously by sharing knowledge among the tasks. To improve the training efficiency and effectiveness, this article proposes a novel surrogate-assisted evolutionary multitask algorithm via GP to share useful knowledge between different scheduling tasks. Specifically, we employ the phenotypic characterization for measuring the behaviors of scheduling rules and building a surrogate for each task accordingly. The built surrogates are used not only to improve the efficiency of solving each single task but also for knowledge transfer in multitask learning with a large number of promising individuals. The results show that the proposed algorithm can significantly improve the quality of scheduling heuristics for all scenarios. In addition, the proposed algorithm manages to solve multiple tasks collaboratively in terms of the evolved scheduling heuristics for different tasks in a multitask scenario.

With the ever increasing number of functionally similar web services being available on the Internet, the market competition is becoming intense. Web service providers (WSPs) realize that good Quality of Service (QoS) is a key of business success and low network latency is a critical measurement of good QoS. Because network latency is related to location, a straightforward way to reduce network latency is to allocate services to proper locations. However, Web Service Location Allocation Problem (WSLAP) is a challenging task since there are multiple objectives potentially conflicting with each other and the solution search space has a combinatorial nature. In this paper, we consider minimizing the network latency and total cost simultaneously and model the WSLAP as a multi-objective optimization problem. We develop a new PSO-based algorithm to provide a set of trade-off solutions. The results show that the new algorithm can provide a more diverse range of solutions than the compared three well known multi-objective optimization algorithms. Moreover, the new algorithm performs better especially on large problems.

Micro-services is a widely adopted architecture to develop large scale web applications. To provide a scalable and low-overhead resource service to micro-service applications, the new container-based clouds are proposed. The new clouds use both containers and VMs to manage resources to achieve a low-overhead, high-utilization data center. However, existing resource allocation approaches either do not consider the dependencies between containers or can only be applied in OS-level container clouds which allocate containers directly to physical machines. To address the multi-objective optimization problem, this work proposes a multi-objective NSGA-II to optimize the availability of applications and the energy consumption requirement of container-based clouds. Our goal is to provide solutions with different tradeoffs between two objectives for cloud providers to choose from. We evaluate the algorithm with a wide range of scenarios by simulation and compare with state-of-the-art algorithms. The results show that our approach significantly outperforms other approaches.

The Uncertain Capacitated Arc Routing Problem (UCARP) is an important combinatorial optimisation problem with extensive real-world applications. Genetic Programming (GP) has shown effectiveness in automatically evolving routing policies to handle the uncertain environment in UCARP. However, whenever a UCARP scenario changes, e.g. when a new vehicle is bought, the previously trained routing policy may no longer work effectively, and one has to retrain a new policy. Retraining a new policy from scratch can be time-consuming but the transfer of knowledge gained from solving the previous similar scenarios may help improve the efficiency of the retraining process. In this paper, we propose a novel transfer learning method by learning the probability distribution of good solutions from source domains and modelling it as a probabilistic prototype tree. We demonstrate that this approach is capable of capturing more information about the source domain compared to transfer learning based on (sub-)tree transfers and even create good trees that are not seen in source domains. Our experimental results showed that our method made the retraining process more efficient and one can obtain an initial state for solving difficult problems that is significantly better than existing methods. The final performance of all algorithms, were comparable, implying that there was no negative transfer.

One of the most known transportation problems, the Large-Scale Vehicle Routing Problem (LSVRP) requires more sophisticated methods to be solved due to the sheer amount of customers. Most current methods include manually designed heuristics and parameters, such as restrictions in the search space. Hyper-heuristics(HHs) appear as a counterpoint to the manually designed complex methods. This paper presents a preliminary study on adaptive search space based on clustering, utilizing a HH Selection framework with Genetic Algorithm (GA). The initial results show promise in having an adaptive search scope when compared to a fixed clustering approach. A comparison of the effects of having a route-first vs cluster-first initial solution is also presented, favouring the latter one, as well as a comparison between two types of chromosome decoding. Finally, the proposed method is compared to a manually designed algorithm, producing results with better quality. The method is shown to be significantly better for most scenarios, achieving solutions just as good as when no limits are applied, but in a much shorter time.

Multi-Point Dynamic Aggregation (MPDA) is a novel task model to determine task allocation for a multi-robot system. In an MPDA scenario, several robots with different abilities aim to complete a set of tasks cooperatively. The demand of each task is time varying. It increases over time at a certain rate (e.g. the bush fire in Australia). When a robot executes a task, the demand of the task decreases at another certain rate, depending on the robot's ability. In this paper, the objective is to design a task plan for minimising the maximal completed time of all tasks. But coupling cooperative and time-varying characteristics of MPDA brings great challenges to modelling, decoding, and optimisation. In this paper, a multi-permutation encoding is used to represent every robot's visiting sequence of tasks, and an implicit decoding strategy with heuristic rules is designed to simplify the problem from a hybrid variable optimisation to a multi-permutation optimisation. Memetic algorithms for the task allocation of MPDA with two local search methods are designed: equality one-step local search with a better exploration ability and elite multi-step local search with a better exploitation ability. Computational experiments show that the proposed decoding method leads to a better performance given the same computational time budget. Experimental results also show that the proposed memetic algorithms outperform the state-of-the-art method in solving the task planning problems of MPDA.

This paper looks at the stochastic Team orienteering Problem with Time Windows, a well-known problem that models the Personalised Tourist Trip Design Probelm. Due to the nature of randomness such as real-time delays, the traditional optimisation approaches are not effective in solving the stochastic problem variant. In this case, genetic programming hyper-heuristics (GPHH) are promising techniques for automatically learning heuristics to make real-time decisions to effectively handle the stochastic environment, however, they still have limitations as the decision making policies use short-sighted information. In this paper, we propose to incorporate global information into the GPHH solution, with a constructed terminal feature based on cluster information to be used by the GPHH, as well as a clustering-aware solution generation process. The experimental studies showed that the newly designed cluster-based feature gave an improvement over the standard GPHH solution. This suggests that incorporating cluster information can be beneficial. Although the clustering-aware solution generation process did not achieve satisfactory performance, the further analysis showed that it could lead to improved performance under certain condition. Overall we demonstrate the effectiveness of using clustering as a global information to enhance the performance of GPHH.

Genetic programming (GP) is considered the most popular method for automatically discovering and constructing dispatching rules for scheduling problems. Pareto Local Search (PLS) is a simple and effective local search method for tackling multi-objective combinatorial optimization problems. Researchers have studied the application of PLS to multiobjective evolutionary algorithms (MOEAs) with some success. In fact, by hybridizing global search with local search, the performance of many MOEAs can be noticeably improved. Despite its preliminary success, the practical use of PLS in GP is relatively limited. In this study, our aim is to enhance the quality of evolved dispatching rules for many-objective Job Shop Scheduling (JSS) through hybridizing GP with PLS techniques and designing an effective selection mechanism of initial solutions for PLS. In this paper, we propose a new GP-PLS algorithm that investigates whether the fitness-based selection mechanism for selecting initial solutions for PLS can increase the chance of discovering highly effective dispatching rules for many-objective JSS. To evaluate the effectiveness of our new algorithm, GPPLS is compared with the current state-of-the-art algorithms for many-objective JSS. The experimental results confirm that the proposed method can outperform the four recently proposed algorithms because of the proper use of local search techniques.

The Uncertain Capacitated Arc Routing Problem (UCARP) is a very important problem which has many real world applications. Genetic Programming Hyper-heuristic (GPHH), which can automatically evolve effective routing policies, is considered as a promising technique that can handle UCARP effectively. However, GP-evolved routing policies are often very complex and hard to be understood and trusted by human users. In this paper, we aim to improve the interpretability of the GP-evolved routing policies by reducing the size of the GP-evolved routing policies since smaller routing policies tend to be easier to understand. We propose a new Multi-Objective GP (MOGP) to optimise the performance (total cost) and size simultaneously. One main challenge is that the size is much easier to be optimised than the performance. Thus, the population tends to be biased to the small but poor routing policies and quickly lose the ability of exploration. To address this issue, we propose a MOGP approach with α dominance strategy (α-MOGP) which can balance the tradeoff between performance and individual size. The experimental results showed that α-MOGP could obtain much smaller routing policies than the state-of-the-art single-objective GPHH, without deteriorating the performance. Compared with traditional MOGP, α-MOGP can obtain a much better and more widespread Pareto front.

Potable water distribution networks are requisites of modern cities. Because of the city expansion, nowadays, the scale of the network grows rapidly, which brings great difficulty to its optimization. Evolutionary computation methods have been widely investigated on small-scale networks, but their performance is far from satisfactory on large-scale networks. Aimed at addressing this difficulty, a new memetic algorithm called level-based learning swarm optimizer with restart and local search is proposed in this paper to solve the large-scale water distribution network optimization problem. Instead of using traditional evolutionary computation algorithms, the level-based learning swarm optimizer that is especially proposed for large-scale optimization problems is applied as the population-based optimizer. Two restart strategies are incorporated to make the algorithm more effective. They can help the algorithm jump out from local optima thus to increase its exploration ability. Moreover, a simple yet effective local search algorithm is proposed based on the domain knowledge to further refine the solutions after the algorithm converges. Experimental results on both single-source and multi-source large-scale water distribution networks show that the proposed algorithm is more effective than the state-of-the-art evolutionary computation algorithms.

The uncertain capacitated arc routing problem is of great significance for its wide applications in the real world. In the uncertain capacitated arc routing problem, variables such as task demands and travel costs are realised in real time. This may cause the predefined solution to become ineffective and/or infeasible. There are two main challenges in solving this problem. One is to obtain a high-quality and robust baseline task sequence, and the other is to design an effective recourse policy to adjust the baseline task sequence when it becomes infeasible and/or ineffective during the execution. Existing studies typically only tackle one challenge (the other being addressed using a naive strategy). No existing work optimises the baseline task sequence and recourse policy simultaneously. To fill this gap, we propose a novel proactive-reactive approach, which represents a solution as a baseline task sequence and a recourse policy. The two components are optimised under a cooperative coevolution framework, in which the baseline task sequence is evolved by an estimation of distribution algorithm, and the recourse policy is evolved by genetic programming. The experimental results show that the proposed algorithm, called Solution-Policy Coevolver, significantly outperforms the state-of-the-art algorithms to the uncertain capacitated arc routing problem for the ugdb and uval benchmark instances. Through further analysis, we discovered that route failure is not always detrimental. Instead, in certain cases (e.g., when the vehicle is on the way back to the depot) allowing route failure can lead to better solutions.

Due to its direct relevance to post-disaster operations, meter reading and civil refuse collection, the Uncertain Capacitated Arc Routing Problem (UCARP) is an important optimisation problem. Stochastic models are critical to study as they more accurately represent the real world than their deterministic counterparts. Although there have been extensive studies in solving routing problems under uncertainty, very few have considered UCARP, and none consider collaboration between vehicles to handle the negative effects of uncertainty. This article proposes a novel Solution Construction Procedure (SCP) that generates solutions to UCARP within a collaborative, multi-vehicle framework. It consists of two types of collaborative activities: one when a vehicle unexpectedly expends capacity ( route failure), and the other during the refill process. Then, we propose a Genetic Programming Hyper-Heuristic (GPHH) algorithm to evolve the routing policy used within the collaborative framework. The experimental studies show that the new heuristic with vehicle collaboration and GP-evolved routing policy significantly outperforms the compared state-of-the-art algorithms on commonly studied test problems. This is shown to be especially true on instances with larger numbers of tasks and vehicles. This clearly shows the advantage of vehicle collaboration in handling the uncertain environment, and the effectiveness of the newly proposed algorithm.

Containerization does not only support fast development and deployment of web applications but also provides the potential to improve the energy efficiency in cloud data centers. In container-based clouds, containers are allocated to virtual machines (VMs) and VMs are allocated to physical machines (PMs). This new architecture requires consolidation algorithms to select heterogeneous VMs to host containers and consolidate VMs to PMs simultaneously. Existing server consolidation techniques in VM-based clouds can hardly be applied because of the two-level architecture of the container-based clouds. This paper proposes a novel genetic algorithm (GA) with dual chromosome representation to solve the problem. The experiments show that the proposed GA achieves significantly higher energy efficiency than the compared state-of-the-art algorithms on a wide range of test problems.

Document classification (DC) is the task of assigning pre-defined labels to unseen documents by utilizing a model trained on the available labeled documents. DC has attracted much attention in medical fields recently because many issues can be formulated as a classification problem. It can assist doctors in decision making and correct decisions can reduce the medical expenses. Medical documents have special attributes that distinguish them from other texts and make them difficult to analyze. For example, many acronyms and abbreviations, and short expressions make it more challenging to extract information. The classification accuracy of the current medical DC methods is not satisfactory. The goal of this work is to enhance the input feature sets of the DC method to improve the accuracy. To approach this goal, a novel two-stage approach is proposed. In the first stage, a domain-specific dictionary, namely the Unified Medical Language System (UMLS), is employed to extract the key features belonging to the most relevant concepts such as diseases or symptoms. In the second stage, PSO is applied to select more related features from the extracted features in the first stage. The performance of the proposed approach is evaluated on the 2010 Informatics for Integrating Biology and the Bedside (i2b2) data set which is a widely used medical text dataset. The experimental results show substantial improvement by the proposed method on the accuracy of classification.

Uncertain Capacitated Arc Routing Problem (UCARP) is a combinatorial optimization problem that has many important real-world applications. Genetic programming (GP) is a powerful machine learning technique that has been successfully used to automatically evolve routing policies for UCARP. Generalisation is an open issue in the field of UCARP and in this direction, an open challenge is the case of changes in number of vehicles which currently leads to new training procedures to be initiated. Considering the expensive training cost of evolving routing policies for UCARP, a promising strategy is to learn and reuse knowledge from a previous problem solving process to improve the effectiveness and efficiency of solving a new related problem, i.e. transfer learning. Since none of the existing GP transfer methods have been used as a hyper-heuristic in solving UCARP, we conduct a comprehensive study to investigate the behaviour of the existing GP transfer methods for evolving routing policy in UCARP, and identify the potentials of existing methods. The results suggest that the existing methods applying subtree transfer cannot scale well to environment changes and cannot be adapted for this purpose. However, applying GP transfer methods is a good option for creating a better initial populations on target domain and though this effect does not last, we can obtain comparable results in the target domain in a much shorter time. Overall, we conclude that UCARP needs stronger and more effective transfer learning methods.

Dynamic job shop scheduling is an important but difficult problem in manufacturing systems which becomes complex particularly in uncertain environments with varying shop scenarios. Genetic programming based hyper-heuristics (GPHH) have been a successful approach for dynamic job shop scheduling (DJSS) problems by enabling the automated design of dispatching rules for DJSS problems. GPHH is a computationally intensive and time consuming approach. Furthermore, when complex shop scenarios are considered, it requires a large number of training instances. When faced with multiple shop scenarios and a large number of problem instances, identifying good training instances to evolve dispatching rules which perform well over diverse scenarios is of vital importance though challenging. Essentially this requires the tackling of exploration versus exploitation trade-off. To address this challenge, we propose a new framework for GPHH which incorporates active sampling of good training instances during evolutionary process. We propose a sampling algorithm based on the ε-greedy method to evolve a set of dispatching rules. Through our experiments, we demonstrate the ability of our framework to efficiently identify useful training instances toward evolving dispatching rules which outperform the existing training methods.

Container technology has become a new trend in both the software industry and cloud computing. Containers support the fast development of web applications and they have the potential to reduce energy consumption in data centers. Containers are usually first allocated to virtual machines (VMs) and VMs are allocated to physical machines. The container allocation is a challenging task which involves a two-level allocation problem. Current research overly simplifies the container allocation into a one-level allocation problem and uses simple rule-based approaches to solve the problem. As a result, the resource is not allocated efficiently which leads to high energy consumption. This paper provides a novel definition of the two-level container allocation problem. Then, we develop a hybrid approach using genetic programming hyper-heuristics combined with human-designed rules to solve the problem. The experiments show that our hybrid approach is able to significantly reduce energy consumption than solely using human-designed rules.

Dynamic flexible job shop scheduling (DFJSS) considers making machine assignment and operation sequencing decisions simultaneously with dynamic events. Genetic programming hyper-heuristics (GPHH) have been successfully applied to evolving dispatching rules for DFJSS. However, existing studies mainly focus on evolving deterministic dispatching rules, which calculate priority values for the candidate machines or jobs and select the one with the best priority. Inspired by the effectiveness of training stochastic policies in reinforcement learning, and the fact that a dispatching rule in DFJSS is similar to a policy in reinforcement learning, we investigate the effectiveness of evolving stochastic dispatching rules for DFJSS in this paper. Instead of using the "winner-takes-all" mechanism, we define a range of probability distributions based on the priority values of the candidates to be used by the stochastic dispatching rules. These distributions introduce varying degrees of randomness. We empirically compare the effectiveness of GPHH in evolving the stochastic dispatching rules with different probability distributions, as well as evolving the deterministic dispatching rules. The results show that the evolved deterministic rules perform the best. We argue that this is because unlike the traditional reinforcement learning methods, the current GPHH does not store the quality (value function) of any particular state and action during the simulation, and thus cannot fully take advantage of the feedback given by the simulation. In the future, we will investigate better ways to make better use of the information during the simulation in GPHH to further improve its effectiveness.

Dynamic flexible job shop scheduling (DFJSS) is one of the well-known combinational optimisation problems, which aims to handle machine assignment (routing) and operation sequencing (sequencing) simultaneously in dynamic environment. Genetic programming, as a hyper-heuristic method, has been successfully applied to evolve the routing and sequencing rules for DFJSS, and achieved promising results. In the actual production process, it is necessary to get a balance between several objectives instead of simply focusing only one objective. No existing study considered solving multi-objective DFJSS using genetic programming. In order to capture multi-objective nature of job shop scheduling and provide different trade-offs between conflicting objectives, in this paper, two well-known multi-objective optimisation frameworks, i.e. non-dominated sorting genetic algorithm II (NSGA-II) and strength Pareto evolutionary algorithm 2 (SPEA2), are incorporated into the genetic programming hyper-heuristic method to solve the multi-objective DFJSS problem. Experimental results show that the strategy of NSGA-II incorporated into genetic programming hyper-heuristic performs better than SPEA2-based GPHH, as well as the weighted sum approaches, in the perspective of both training performance and generalisation.

The Uncertain Capacitated Arc Routing Problem (UCARP) is an important problem with many real-world applications. A major challenge in UCARP is to handle the uncertain environment effectively and reduce the recourse cost upon route failures. Genetic Programming Hyper-heuristic (GPHH) has been successfully applied to automatically evolve effective routing policies to make real-time decisions in the routing process. However, most existing studies obtain a single complex routing policy which is hard to interpret. In this paper, we aim to evolve an ensemble of simpler and more interpretable routing policies than a single complex policy. By considering the two critical properties of ensemble learning, i.e., the effectiveness of each ensemble element and the diversity between them, we propose two novel ensemble GP approaches namely DivBaggingGP and DivNichGP. DivBaggingGP evolves the ensemble elements sequentially, while DivNichGP evolves them simultaneously. The experimental results showed that both DivBaggingGP and DivNichGP could obtain more interpretable routing policies than the single complex routing policy. DivNichGP can achieve better test performance than DivBaggingGP as well as the single routing policy evolved by the current state-of-the-art GPHH. This demonstrates the effectiveness of evolving both effective and interpretable routing policies using ensemble learning.

Dynamic flexible job shop scheduling (DFJSS) is an important and a challenging combinatorial optimisation problem. Genetic programming hyper-heuristic (GPHH) has been widely used for automatically evolving the routing and sequencing rules for DFJSS. The terminal set is the key to the success of GPHH. There are a wide range of features in DFJSS that reflect different characteristics of the job shop state. However, the importance of a feature can vary from one scenario to another, and some features may be redundant or irrelevant under the considered scenario. Feature selection is a promising strategy to remove the unimportant features and reduce the search space of GPHH. However, no work has considered feature selection in GPHH for DFJSS so far. In addition, it is necessary to do feature selection for the two terminal sets simultaneously. In this paper, we propose a new two-stage GPHH approach with feature selection for evolving routing and sequencing rules for DFJSS. The experimental studies show that the best solutions achieved by the proposed approach are better than that of the baseline method in most scenarios. Furthermore, the rules evolved by the proposed approach involve a smaller number of unique features, which are easier to interpret.

Designing effective dispatching rules for production systems is a difficult and time-consuming task if it is done manually. In the last decade, the growth of computing power, advanced machine learning, and optimisation techniques has made the automated design of dispatching rules possible and automatically discovered rules are competitive or outperform existing rules developed by researchers. Genetic programming is one of the most popular approaches to discovering dispatching rules in the literature, especially for complex production systems. However, the large heuristic search space may restrict genetic programming from finding near optimal dispatching rules. This article develops a new hybrid genetic programming algorithm for dynamic job shop scheduling based on a new representation, a new local search heuristic, and efficient fitness evaluators. Experiments show that the new method is effective regarding the quality of evolved rules. Moreover, evolved rules are also significantly smaller and contain more relevant attributes.

This paper investigates the stochastic team orienteering problem with time windows, which is a well known problem to model personalised tourist trip design. Specifically, we consider the stochastic visit duration, which may make preplanned trip infeasible. Existing studies focus on optimising robust solutions in advance, which is not effective in adjusting the subsequent trip in real time. Decision making policies, on the other hand, are effective heuristics to this end. However, it is very challenging to manually design effective policies. In this paper, we investigate automatically evolving policies for the stochastic team orienteering problem with time windows by genetic programming hyper-heuristics. We designed novel problem-specific features for the terminal set, and a meta-algorithm for fitness evaluation. Furthermore, we developed two look-ahead features that can provide more fruitful information than the basic features for real-time decision making. The experimental studies showed that the proposed genetic programming hyper-heuristic can evolve policies that are much better than the manually designed policies. In addition, it seems that the look-ahead features are not so effective when directly included in the terminals. This suggests the requirement of more intelligent ways of incorporating lookahead information.

Service-oriented architecture (SOA) has been widely employed in the field of software engineering, since it encourages attributes such as modularity and code reusability across different applications. Web service composition, where atomic services that accomplish simple tasks are combined into an application that fulfils a more complex function, is one popular application of SOA. Existing composition works focus on building functional and quality-optimised applications. A subset of these works use multi-objective evolutionary computing techniques to produce a Pareto front of compositions, though they assume that the basic structure of the composition workflow is already known. In our recent work, we removed this assumption by combining NSGA-II with a solution representation that allows for different workflow structures to be investigated. However, the multi-objective nature of the problem made it difficult to apply local search to further improve the results. In this paper we hybridise NSGA-II with MOEA/D, which allows the problem to be decomposed into multiple single-objective subproblems where a simple form of local search can be applied. Experiment results show that the use of local search improves the quality of the fronts produced by the hybrid approach for a number of composition tasks.

In this paper, a novel bi-level grouping optimization (BIGO) model is proposed for solving the storage location assignment problem with grouping constraint (SLAP-GC). A major challenge in this problem is the grouping constraint which restricts the number of groups each product can have and the locations of items in the same group. In SLAP-GC, the problem consists of two subproblems, one is how to group the items, and the other one is how to assign the groups to locations. It is an arduous task to solve the two subproblems simultaneously. To overcome this difficulty, we propose a BIGO. BIGO optimizes item grouping in the upper level, and uses the lower-level optimization to evaluate each item grouping. Sophisticated fitness evaluation and search operators are designed for both upper and lower level optimization so that the feasibility of solutions can be guaranteed, and the search can focus on promising areas in the search space. Based on the BIGO model, a multistart random search method and a tabu search algorithm are proposed. The experimental results on the real-world dataset validate the efficacy of the BIGO model and the advantage of the tabu search method over the random search method.

Dynamic vehicle routing problem with time windows is an important combinatorial optimisation problem in many real-world applications. The most challenging part of the problem is to make real-time decisions (i.e. whether to accept the newly arrived service requests or not) during the execution of the routes. It is hardly applicable to use the optimisation methods such as mathematical programming and evolutionary algorithms that are competitive for static problems, since they are usually time-consuming, and cannot give real-time responses. In this paper, we consider solving this problem using heuristics. A heuristic gradually builds a solution by adding the requests to the end of the route one by one. This way, it can take advantage of the latest information when making the next decision, and give immediate response. In this paper, we propose a meta-algorithm to generate a solution given any heuristic. The meta-algorithm maintains a set of routes throughout the scheduling horizon. Whenever a new request arrives, it tries to re-generate new routes to include the new request by the heuristic. It accepts the new request if successful, and reject otherwise. Then we manually designed several heuristics, and proposed a genetic programming-based hyper-heuristic to automatically evolve heuristics. The results showed that the heuristics evolved by genetic programming significantly outperformed the manually designed heuristics.

Dynamic Job shop scheduling (DJSS) is a complex and hard problem in real-world manufacturing systems. In practice, the parameters of a job shop like processing times, due dates, etc. are uncertain. But most of the current research on scheduling consider only deterministic scenarios. In a typical dynamic job shop, once the information about a job becomes available it is considered unchanged. In this work, we consider genetic programming based dispatching rules to generate schedules in an uncertain environment where the process time of an operation is not known exactly until it is finished. Our primary goal is to investigate methods to incorporate the uncertainty information into the dispatching rules. We develop two training approaches, namely ex-post and ex-ante to evolve the dispatching rules to generate good schedules under uncertainty. Both these methods consider different ways of incorporating the uncertainty parameters into the genetic programs during evolution. We test our methods under different scenarios and the results compare well against the existing approaches. We also test the generalization capability of our methods across different levels of uncertainty and observe that the proposed methods perform well. In particular, we observe that the proposed ex-ante training approach outperformed other methods.

Web service and Cloud computing have significantly reformed the software industry. The need for web service allocation in the cloud environment is increasing dramatically. In order to reduce the cost for service providers as well as improve the utilization of cloud resource for cloud providers, this paper formulates the web service resource allocation in cloud environment problem as a two-level multi-objective bin packing problem. It proposes a NSGA-II-based algorithm with specifically designed genetic operators. We are compared with two varieties of the algorithm. The results show that the proposed algorithm can provide reasonably good results with low violation rate.

Dynamic job shop scheduling (DJSS) is a complex problem which is an important aspect of manufacturing systems. Even though the manufacturing environment is uncertain, most of the existing research works consider deterministic scheduling problems where the time required for processing any job is known in advance and never changes. In this work, we consider DJSS problems with varied uncertainty configurations of machines in terms of processing times and the total flow time as scheduling objective. With the varying levels of uncertainty many machines become bottlenecks of the job shop. It is essential to identify these bottleneck machines and schedule the jobs to be performed by them carefully. Driven by this idea, we develop a new effective method to evolve pairs of dispatching rules each for a different bottleneck level of the machines. A clustering approach to classifying the bottleneck level of the machines arising in the system due to uncertain processing times is proposed. Then, a cooperative co-evolution technique to evolve pairs of dispatching rules which generalize well across different uncertainty configurations is presented. We perform empirical analysis to show its generalization characteristic over the different uncertainty configurations and show that the proposed method outperforms the current approaches.

Uncertain Capacitated Arc Routing Problem (UCARP) is a variant of the well-known CARP. It considers a variety of stochastic factors to reflect the reality where the exact information such as the actual task demand and accessibilities of edges are unknown in advance. Existing works focus on obtaining a robust solution beforehand. However, it is also important to design effective heuristics to adjust the solution in real time. In this paper, we develop a new Genetic Programming-based Hyper-Heuristic (GPHH) for automated heuristic design for UCARP. A novel effective meta-algorithm is designed carefully to address the failures caused by the environment change. In addition, it employs domain knowledge to filter some infeasible candidate tasks for the heuristic function. The experimental results show that the proposed GPHH significantly outperforms the existing GPHH methods and manually designed heuristics. Moreover, we find that eliminating the infeasible and distant tasks in advance can reduce much noise and improve the efficacy of the evolved heuristics. In addition, it is found that simply adding a slack factor to the expected task demand may not improve the performance of the GPHH.

Web services have become increasingly popular in recent years, given their modular nature and reusability potential. A particularly promising application is in Web service composition, where multiple individual services with specific functionalities are composed to accomplish a more complex task. Researchers have proposed evolutionary computing techniques for creating compositions that are not only feasible, but also have the best possible Quality of Service (QoS). Some of these works employed multi-objective techniques to tackle the optimisation of compositions with conflicting QoS attributes, but they are not fully automated, i.e. they assume the composition workflow structure is already known. This assumption is often not satisfied, as the workflow is often unknown. This paper proposes a genetic programming-based method to automatically generate service compositions in a multi-objective context, based on a novel fragmented tree representation. An evaluation using benchmark datasets is carried out, comparing existing methods adapted to the multi-objective composition problem. Results show that the fragmented method has the lowest execution time overall. In terms of quality, its Pareto fronts are equivalent to those of one of the approaches but inferior to those of the other. More importantly, this work provides a foundation for future investigation of multi-objective fully automated service composition.

Identification of variable interaction is essential for an efficient implementation of a divide-and-conquer algorithm for large-scale black-box optimization. In this paper, we propose an improved variant of the differential grouping (DG) algorithm, which has a better efficiency and grouping accuracy. The proposed algorithm, DG2, finds a reliable threshold value by estimating the magnitude of roundoff errors. With respect to efficiency, DG2 reuses the sample points that are generated for detecting interactions and saves up to half of the computational resources on fully separable functions. We mathematically show that the new sampling technique achieves the lower bound with respect to the number of function evaluations. Unlike its predecessor, DG2 checks all possible pairs of variables for interactions and has the capacity to identify overlapping components of an objective function. On the accuracy aspect, DG2 outperforms the state-of-the-art decomposition methods on the latest large-scale continuous optimization benchmark suites. DG2 also performs reliably in the presence of imbalance among contribution of components in an objective function. Another major advantage of DG2 is the automatic calculation of its threshold parameter ($\epsilon $ ), which makes it parameter-free. Finally, the experimental results show that when DG2 is used within a cooperative co-evolutionary framework, it can generate competitive results as compared to several state-of-the-art algorithms.

In Job Shop Scheduling (JSS) problems, there are usually many conflicting objectives to consider, such as the makespan, mean flowtime, maximal tardiness, number of tardy jobs, etc. Most studies considered these objectives separately or aggregated them into a single objective (fitness function) and treat the problem as a single-objective optimization. Very few studies attempted to solve the multi-objective JSS with two or three objectives, not to mention the many-objective JSS with more than three objectives. In this paper, we investigate the many-objective JSS, which takes all the objectives into account. On the other hand, dispatching rules have been widely used in JSS due to its flexibility, scalability and quick response in dynamic environment. In this paper, we focus on evolving a set of trade-off dispatching rules for many-objective JSS, which can generate non-dominated schedules given any unseen instance. To this end, a new hybridized algorithm that combines Genetic Programming (GP) and NSGA-III is proposed. The experimental results demonstrates the efficacy of the newly proposed algorithm on the tested job-shop benchmark instances.

Genetic Programming (GP) has been extensively used to automatically design dispatching rules for job shop scheduling problems. However, the previous studies only focus on the performance on the training instances. So far, there is no systematic investigation of the reusability of the GP-evolved rules on unseen instances. In practice, it is desirable to train the rules on smaller job shop instances, and apply them to larger instances with more jobs and machines to save training time. In this case, the reusability of the GP-evolved rules under different numbers of jobs and machines is an important issue. In this paper, a comprehensive investigation is conducted to analyse how the variation in the numbers of jobs and machines from the training set to the test set affects the reusability of the GP-evolved rules. It is found that in terms of minimizing makespan, the reusability of the GP-evolved rules highly depends on variation in the numbers of jobs and machines. A better reusability can be achieved by choosing training instances whose numbers of jobs and machines (or at least the ratio between the numbers of jobs and machines) are closer to that of the test instances. Furthermore, the ratio between the numbers of jobs and machines is demonstrated to be an important factor to reflect the complexity of an instance for dispatching rules. This study is the first systematic investigation on the reusability of GP-evolved dispatching rules.

Evolutionary scheduling and combinatorial optimisation is an active research area and attracts the attentions of many researchers from computer science and operations research. Many advances have been made in this field and its scope in terms of techniques and applications has been continuously extended. In this position paper, we provide an overall picture of some key challenges in the field, discuss potential future research directions, and give our position in the field. We focus on three major issues that are encountered in practice, namely dynamic changes, multiple interdependent decisions, and multiple objectives. Our view is that the researchers should step out of our comfort zone to deal with messy and complicated issues in real-world applications.

Automatic design of dispatching rules with Genetic Programming (GP) in job shop scheduling has become more prevalent in recent years. When evolving dispatching rules, choosing a proper terminal set is an important issue. There are a large number of attributes in the job shop that can be taken into account as terminals. However, not all of them are useful to be included. It is not a trivial task to identify the most important attributes out of the entire attribute pool. On the other hand, including all the attributes in the terminal set leads to a huge search space for GP, and makes it hard to find the promising regions of the search space. In this paper, we first demonstrate the differences in importance of attributes by frequency analysis. Then, we propose a terminal weighting algorithm to learn the importance of the terminals on-the-fly, and an adaptive mutation scheme to guide the search to concentrate on the more important terminals. The experimental studies show that the proposed algorithm outperformed its counterpart without terminal weighting and adaptive mutation, in the tested dynamic job shop scheduling, while optimising the mean weighted tardiness. This verifies that focusing on the important terminals will help to search inside more promising regions and lead to better solutions.

Web service composition is a popular area of investigation, since it encourages code reuse as opposed to re-implementing already existing functionality modules. Performing such compositions manually can be quite time-consuming, since the functionality of each service included in a solution must be fulfilled, while at the same time selecting candidates with the best possible quality of service attributes. This work proposes a memetic algorithm that can perform Web service composition in a fully automated manner, optimising a sequence of services that is then decoded into the final solution. The key advantage of this representation is that it separates the quality optimisation technique from the enforcement of correctness constraints, thus simplifying the overall composition process and preventing solutions from being overly constrained. While this indirect composition approach has been investigated earlier, the previous representation relied on weights for establishing a service sequence and used PSO as the optimisation technique. In this work, on the other hand, sequences are directly represented using a vector of services, which reduces the overall search space. Additionally, the memetic algorithm employed in this work is better at exploring solutions within promising areas of the search space. Experiments were conducted comparing the memetic approach with the previously proposed PSO, with two key findings. Firstly, the new representation reduces the overall execution time while maintaining the original solution quality. Secondly, the use of the memetic local search improves the overall quality of solutions, though it may incur longer execution times.

Web Service Composition (WSC) is a prominent way of actualizing service-oriented architecture by integrating network-accessible Web services into a new invokable application. Evolutionary computation techniques have provided rewarding approaches in automatic Web service composition over the last decade. However, the studies on considering both functionality and non-functionality (i.e. Quality-of-Service, QoS) properties are still limited. In this paper, we propose a novel Graph-Based Memetic Algorithm (GBMA) for solving the QoS-aware WSC problems. GBMA adopts the graph representation proposed by GraphEvol, which is one of the state-of-the-art algorithms. More importantly, GBMA designs and uses a local search based on two newly designed move operators to overcome the drawbacks of the mutation operator in GraphEvol. The experimental results show that the proposed GBMA outperformed GraphEvol, which is the counterpart without local search, in terms of both solution quality and convergence speed. This demonstrates the efficacy and efficiency of combining local search with global search in solving QoS-aware WSC problems.

The entropy measures have been used in feature selection for decades, and showed competitive performance. In general, the problem aims at minimizing the conditional entropy of the class label on the selected features. However, the generalization of the entropy measures has been neglected in literature. Specifically, the use of conditional entropy has two critical issues. First, the empirical conditional distribution of the class label may have a low confidence and thus is unreliable. Second, there may not be enough training instances for the selected features, and it is highly likely to encounter new examples in the test set. To address these issues, a bi-objective optimization model with a modified entropy measure called the Bayesian entropy is proposed. This model considers the confidence of the optimized conditional entropy value as well as the conditional entropy value itself. As a result, it produces multiple feature subsets with different trade-offs between the entropy value and its confidence. The experimental results demonstrate that by solving the proposed optimization model with the new entropy measure, the number of features can be dramatically reduced within a much shorter time than the existing algorithms. Furthermore, similar or even better classification accuracy was achieved for most test problems.

Genetic Programming (GP) has been successfully used to automatically design dispatching rules in job shop scheduling. The goal of GP is to evolve a priority function that will be used to order the waiting jobs at each decision point, and decide the next job to be processed. To this end, the proper terminals (i.e. job shop features) have to be decided. When evolving the priority function, various job shop features can be included in the terminal set. However, not all the features are helpful, and some features are irrelevant to the rule. Including irrelevant features into the terminal set enlarges the search space, and makes it harder to achieve promising areas. Thus, it is important to identify the important features and remove the irrelevant ones to improve the GP-evolved rules. This paper proposes a domain-knowledge-free feature ranking and selection approach. As a result, the terminal set is significantly reduced and only the most important features are selected. The experimental results show that using only the selected features can lead to significantly better GP-evolved rules on both training and unseen test instances.

Self-adaptive mechanisms for the identification of the most suitable variation operator in evolutionary algorithms rely almost exclusively on the measurement of the fitness of the offspring, which may not be sufficient to assess the optimality of an operator (e.g., in a landscape with an high degree of neutrality). This paper proposes a novel adaptive operator selection mechanism which uses a set of four fitness landscape analysis techniques and an online learning algorithm, dynamic weighted majority, to provide more detailed information about the search space to better determine the most suitable crossover operator. Experimental analysis on the capacitated arc routing problem has demonstrated that different crossover operators behave differently during the search process, and selecting the proper one adaptively can lead to more promising results.

Abstract In this paper, the interdependence between sub-problems in a complex overall problem is investigated using a benchmark problem called Travelling Thief Problem (TTP), which is a combination of Travelling Salesman Problem (TSP) and Knapsack Problem (KP). First, the analysis on the mathematical formulation shows that it is impossible to decompose the problem into independent sub-problems due to the non-linear relationship in the objective function. Therefore, the algorithm for TTP is not straightforward although each sub-problem alone has been investigated intensively. Then, two meta-heuristics are proposed for TTP. One is the Cooperative Co-evolution (CC) that solves the sub-problems separately and transfers the information between them in each generation. The other is the Memetic Algorithm (MA) that solves TTP as a whole. The comparative results showed that MA consistently obtained much better results than both the standard and dynamic versions of CC within comparable computational budget. This indicates the importance of considering the interdependence between sub-problems in an overall problem like TTP.

In particle swarm optimization (PSO), the inertia weight is an important parameter for controlling its search capability. There have been intensive studies of the inertia weight in continuous optimization, but little attention has been paid to the binary case. This paper comprehensively investigates the effect of the inertia weight on the performance of binary PSO (BPSO), from both theoretical and empirical perspectives. A mathematical model is proposed to analyze the behavior of BPSO, based on which several lemmas and theorems on the effect of the inertia weight are derived. Our research findings suggest that in the binary case, a smaller inertia weight enhances the exploration capability while a larger inertia weight encourages exploitation. Consequently, this paper proposes a new adaptive inertia weight scheme for BPSO. This scheme allows the search process to start first with exploration and gradually move toward exploitation by linearly increasing the inertia weight. The experimental results on 0/1 knapsack problems show that the BPSO with the new increasing inertia weight scheme performs significantly better than that with the conventional decreasing and constant inertia weight schemes. This paper verifies the efficacy of increasing inertia weight in BPSO.

This article proposes a competitive divide-and-conquer algorithm for solving large-scale black-box optimization problems for which there are thousands of decision variables and the algebraic models of the problems are unavailable. We focus on problems that are partially additively separable, since this type of problem can be further decomposed into a number of smaller independent subproblems. The proposed algorithm addresses two important issues in solving large-scale black-box optimization: (1) the identification of the independent subproblems without explicitly knowing the formula of the objective function and (2) the optimization of the identified black-box subproblems. First, a Global Differential Grouping (GDG) method is proposed to identify the independent subproblems. Then, a variant of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is adopted to solve the subproblems resulting from its rotation invariance property. GDG and CMA-ES work together under the cooperative co-evolution framework. The resultant algorithm, named CC-GDG-CMAES, is then evaluated on the CEC’2010 large-scale global optimization (LSGO) benchmark functions, which have a thousand decision variables and black-box objective functions. The experimental results show that, on most test functions evaluated in this study, GDG manages to obtain an ideal partition of the index set of the decision variables, and CC-GDG-CMAES outperforms the state-of-the-art results. Moreover, the competitive performance of the well-known CMA-ES is extended from low-dimensional to high-dimensional black-box problems.

In many real-world applications, one needs to deal with a large multi-silo problem with interdependent silos. In order to investigate the interdependency between silos (subproblems), the Traveling Thief Problem (TTP) was designed as a benchmark problem. TTP is a combination of two well-known sub-problems, Traveling Salesman Problem (TSP) and Knapsack Problem (KP). Although each sub-problem has been intensively investigated, the interdependent combination has been demonstrated to be challenging, and cannot be solved by simply solving the sub-problems separately. The Two-Stage Memetic Algorithm (TSMA) is an effective approach that has decent solution quality and scalability, which consists of a tour improvement stage and an item picking stage. Unlike the traditional TSP local search operators adopted in the former stage, the heuristic for the latter stage is rather intuitive. To further investigate the effect of item picking heuristic, Genetic Programming (GP) is employed to evolve a gain function and a picking function, respectively. The resultant two heuristics were tested on some representative TTP instances, and showed competitive performance, which indicates the potential of evolving more promising heuristics for solving TTP more systematically by GP.

The Storage Location Assignment Problem (SLAP) is a significant optimisation problem in warehouse management. Given a number of products, each with a set of items with different popularities (probabilities of being ordered), SLAP is to find the best locations for the items of the products in the warehouse to minimise the warehouse operational cost. Specifically, the operational cost is the expected cost of picking the orders. Grouping constraints are included to take the practical considerations into account in the problem. That is, the items belonging to the same product are more desirable to be placed together. In this paper, the SLAP with Grouping Constraints (SLAP-GC) is investigated, and an efficient Restricted Neighbourhood Tabu Search (RNTS) algorithm is proposed to solving it. RNTS adopts the problem-specific search operators to maintain solution feasibility, and the tabu list to prevent searching back and forth. RNTS was empirically compared with the mathematical programming method and a previously designed Genetic Programming method, which is demonstrated to be the state-of-the-art algorithm for SLAP-GC. The experimental results on the real-world data show that RNTS outperforms the state-of-the-art algorithms for SLAP-GC in terms of solution quality and speed. It managed to achieve optimal solutions for most of the small-scale instances much faster and outperformed the Genetic Programming method in terms of both solution quality and running time on all the test instances.

In this paper, a Variable Neighborhood Decomposition (VND) is proposed for Large Scale Capacitated Arc Routing Problems (LSCARP). The VND employs the Route Distance Grouping (RDG) scheme, which is a competitive decomposition scheme for LSCARP, and generates different neighborhood structures with different tradeoffs between exploration and exploitation. The search first uses a neighborhood structure that is considered to be the most promising, and then broadens the neighborhood gradually as it is getting stuck in a local optimum. The experimental studies show that the VND performed better than the state-of-the-art RDG-MAENS counterpart, and the improvement is more significant when the subcomponent size is smaller. This implies a great potential of combining the VND with small subcomponents.

In this paper we investigate the performance of cooperative co-evolutionary (CC) algorithms on large-scale fully-separable continuous optimization problems. We have shown that decomposition can have significant impact on the performance of CC algorithms. The empirical results show that the subcomponent size should be chosen small enough so that the subcomponent size is within the capacity of the subcomponent optimizer. In practice, determining the optimal size is difficult. Therefore, adaptive techniques are desired by practitioners. Here we propose an adaptive method, MLSoft, that uses widely-used techniques in reinforcement learning such as the value function method and softmax selection rule to adapt the subcomponent size during the optimization process. The experimental results show that MLSoft is significantly better than an existing adaptive algorithm called MLCC on a set of large-scale fully-separable problems.

This study proposes a method for solving real-world warehouse Storage Location Assignment Problem (SLAP) under grouping constraints by Genetic Programming (GP). Integer Linear Programming (ILP) formulation is used to define the problem. By the proposed GP method, a subset of the items is repeatedly selected and placed into the available current best location of the shelves in the warehouse, until all the items have been assigned with locations. A heuristic matching function is evolved by GP to guide the selection of the subsets of items. Our comparison between the proposed GP approach and the traditional ILP approach shows that GP can obtain near-optimal solutions on the training data within a short period of time. Moreover, the evolved heuristics can achieve good optimization results on unseen scenarios, comparable to that on the scenario used for training. This shows that the evolved heuristics have good reusability and can be directly applied for slightly different scenarios without any new search process.

In this paper, a divide-and-conquer approach is proposed to solve the large-scale capacitated arc routing problem (LSCARP) more effectively. Instead of considering the problem as a whole, the proposed approach adopts the cooperative coevolution (CC) framework to decompose it into smaller ones and solve them separately. An effective decomposition scheme called the route distance grouping (RDG) is developed to decompose the problem. Its merit is twofold. First, it employs the route information of the best-so-far solution, so that the quality of the decomposition is upper bounded by that of the best-so-far solution. Thus, it can keep improving the decomposition by updating the best-so-far solution during the search. Second, it defines a distance between routes, based on which the potentially better decompositions can be identified. Therefore, RDG is able to obtain promising decompositions and focus the search on the promising regions of the vast solution space. Experimental studies verified the efficacy of RDG on the instances with a large number of tasks and tight capacity constraints, where it managed to obtain significantly better results than its counterpart without decomposition in a much shorter time. Furthermore, the best-known solutions of the EGL-G LSCARP instances are much improved.

Cooperative co-evolution has been introduced into evolutionary algorithms with the aim of solving increasingly complex optimization problems through a divide-and-conquer paradigm. In theory, the idea of co-adapted subcomponents is desirable for solving large-scale optimization problems. However, in practice, without prior knowledge about the problem, it is not clear how the problem should be decomposed. In this paper, we propose an automatic decomposition strategy called differential grouping that can uncover the underlying interaction structure of the decision variables and form subcomponents such that the interdependence between them is kept to a minimum. We show mathematically how such a decomposition strategy can be derived from a definition of partial separability. The empirical studies show that such near-optimal decomposition can greatly improve the solution quality on large-scale global optimization problems. Finally, we show how such an automated decomposition allows for a better approximation of the contribution of various subcomponents, leading to a more efficient assignment of the computational budget to various subcomponents.

In this paper, a simple but effective Random Route Grouping (RRG) scheme is developed to decompose the LargeScale Capacitated Arc Routing Problem (LSCARP). A theoretical analysis is given to show that the decomposition is guaranteed to be improved by RRG along with the improvement of the best-sofar solution during the search process. Then, RRG is combined with a cooperative co-evolution model to solve LSCARP. The experimental results on the EGL-G LSCARP set showed that given the same computational budget, the proposed approach obtained much better results than its counterpart without using decomposition.

In this paper, we present a novel portfolio optimization method that aims to generalize the delta changes of future returns, based on historical delta changes of returns learned in a past window of time. Our method addresses two issues in portfolio optimization. First, we observe that daily returns of stock prices are very noisy and often non-stationary and dependent. In addition, they do not follow certain well-defined distribution functions, such as the Gaussian distribution. To address this issue, we first aggregate the return values over a multi-day period into an average return in order to reduce the noise of daily returns. We further propose a pre-selection scheme based on stationarity, normality and independence tests in order to select a subset of stocks that have promising statistical properties. Second, we have found that optimizing the average risk in a past window does not typically generalize to future returns with minimal risks. To this end, we develop a portfolio optimization method that uses the delta changes of aggregated returns in a past window to optimize the delta changes of future expected returns. Our experimental studies show that data conditioning and aggregation in our proposed method is an effective means of improving the generalizability while simultaneously minimizing the risk of the portfolio.

The capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem with many real-world applications, e.g., salting route optimization and fleet management. There have been many attempts at solving CARP using heuristic and meta-heuristic approaches, including evolutionary algorithms. However, almost all such attempts formulate CARP as a single-objective problem although it usually has more than one objective, especially considering its real-world applications. This paper studies multiobjective CARP (MO-CARP). A new memetic algorithm (MA) called decomposition-based MA with extended neighborhood search (D-MAENS) is proposed. The new algorithm combines the advanced features from both the MAENS approach for single-objective CARP and multiobjective evolutionary optimization. Our experimental studies have shown that such combination outperforms significantly an off-the-shelf multiobjective evolutionary algorithm, namely nondominated sorting genetic algorithm II, and the state-of-the-art multiobjective algorithm for MO-CARP (LMOGA). Our work has also shown that a specifically designed multiobjective algorithm by combining its single-objective version and multiobjective features may lead to competitive multiobjective algorithms for multiobjective combinatorial optimization problems.

This paper investigates the Periodic Capacitated Arc Routing Problem (PCARP), which is often encountered in the waste collection application. PCARP is an extension of the well-known Capacitated Arc Routing Problem (CARP) from a single period to a multi-period horizon. PCARP is a hierarchical optimization problem which has a primary objective (minimizing the number of vehicles ) and a secondary objective (minimizing the total cost ). An important factor that makes PCARP challenging is that its primary objective is little affected by existing operators and thus difficult to improve. We propose a new Memetic Algorithm (MA) for solving PCARP. The MA adopts a new solution representation scheme and a novel crossover operator. Most importantly, a Route-Merging (RM) procedure is devised and embedded in the algorithm to tackle the insensitive objective . The MA with RM (MARM) has been compared with existing meta-heuristic approaches on two PCARP benchmark sets and a real-world data set. The experimental results show that MARM obtained better solutions than the compared algorithms in much less time, and even updated the best known solutions of all the benchmark instances. Further study reveals that the RM procedure plays a key role in the superior performance of MARM.

Capacitated Arc Routing Problem (CARP) has drawn much attention during the last few years because of its applications in the real world. Recently, we developed a Memetic Algorithm with Extended Neighborhood Search (MAENS), which is powerful in solving CARP. The excellent performance of MAENS is mainly due to one of its local search operators, namely the Merge-Split (MS) operator. However, the higher computational complexity of the MS operator compared to traditional local search operators remains as the major drawback of MAENS, especially when applying it to large-size instances. In this paper, we propose a heuristic candidate list strategy to sample the neighbors generated by the MS operator instead of enumerating or sampling them randomly, in order to avoid unnecessary callings of the MS operator during local search. Based on the strategy, an improved algorithm of MAENS, namely MAENS-II, is developed. Experimental results on benchmark instances showed that MAENS-II managed to obtain the same level of solution quality as MAENS with much less computational time. This should be credited to the utilization of the proposed heuristic strategy. On the other hand, in case both MAENS and MAENS-II were provided comparable computational time, MAENS-II outperformed MAENS in terms of solution quality.

In this paper, the Uncertain CARP (UCARP) is investigated. In UCARP, the demands of tasks and the deadheading costs of edges are stochastic and one has to design a robust solution for all possible environments. A problem model and a robustness measure for solutions are defined according to the requirements in reality. Three benchmark sets with uncertain parameters are generated by extending existing benchmark sets for static cases. In order to explore the solution space of UCARP, the most competitive algorithms for static CARP are tested on one of the generated uncertain benchmark sets. The experimental results showed that the optimal solution in terms of robustness in uncertain environment may be far away from the optimal one in terms of quality in a static environment and thus, utilizing only the expected value of the random variables can hardly lead to robust solutions.

Capacitated Arc Routing Problem (CARP) has attracted much interest because of its wide applications in the real world. Recently, a memetic algorithm proposed by Lacomme et al. (LMA) has been demonstrated to be a competitive approach to CARP. The crossover operation of LMA is carried out based on an implicit representation scheme, while it conducts local search on the basis of an explicit representation scheme. Hence, the search process of LMA involves frequent switch between the spaces defined by the two representation schemes. However, a good solution in one space is not necessarily good in the other. In this paper, we show that the local search process of LMA might be ineffective due to such reason, and suggest adopting a more careful way to coordinate the local search. As a result, two new local search methods are proposed, which resulted in two improved LMA (ILMA) algorithms. Experimental results on benchmark instances of CARP showed that the ILMA significantly outperformed LMA in terms of solution quality, and sometimes even in terms of computational time. Furthermore, ILMA improved the best known solutions for 8 problem instances out of the total 24 instances.

The capacitated arc routing problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. Since CARP is NP-hard and exact methods are only applicable to small instances, heuristic and metaheuristic methods are widely adopted when solving CARP. In this paper, we propose a memetic algorithm, namely memetic algorithm with extended neighborhood search (MAENS), for CARP. MAENS is distinct from existing approaches in the utilization of a novel local search operator, namely Merge-Split (MS). The MS operator is capable of searching using large step sizes, and thus has the potential to search the solution space more efficiently and is less likely to be trapped in local optima. Experimental results show that MAENS is superior to a number of state-of-the-art algorithms, and the advanced performance of MAENS is mainly due to the MS operator. The application of the MS operator is not limited to MAENS. It can be easily generalized to other approaches.

Capacitated arc routing problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. Since CARP is NP-hard and exact methods are only applicable for small instances, heuristics and metaheuristic methods are widely adopted when solving CARP. This paper demonstrates one major disadvantage encountered by traditional search algorithms and proposes a novel operator named global repair operator (GRO) to address it. We further embed GRO in a recently proposed tabu search algorithm (TSA) and apply the resultant repair-based tabu search (RTS) algorithm to five well-known benchmark test sets. Empirical results suggest that RTS not only outperforms TSA in terms of quality of solutions but also converges to the solutions faster. Moreover, RTS is also competitive with a number of state-of-the-art approaches for CARP. The efficacy of GRO is thereby justified. More importantly, since GRO is not specifically designed for the referred TSA, it might be a potential tool for improving any existing method that adopts the same solution representation.