Automated lesion detection in chest X-rays has demonstrated significant potential for improving clinical diagnosis by precisely localizing pathological abnormalities. While recent promptable detection frameworks have achieved remarkable accuracy in target localization, existing methods typically rely on manual annotations as prompts, which are labor-intensive and impractical for clinical applications. To address this limitation, we propose SP-Det, a novel self-prompted detection framework that automatically generates rich textual context to guide multi-label lesion detection without requiring expert annotations. Specifically, we introduce an expert-free dual-text prompt generator (DTPG) that leverages two complementary textual modalities: semantic context prompts that capture global pathological patterns and disease beacon prompts that focus on disease-specific manifestations. Moreover, we devise a bidirectional feature enhancer (BFE) that synergistically integrates comprehensive diagnostic context with disease-specific embeddings to significantly improve feature representation and detection accuracy. Extensive experiments on two chest X-ray datasets with diverse thoracic disease categories demonstrate that our SP-Det framework outperforms state-of-the-art detection methods while completely eliminating the dependency on expert-annotated prompts compared to existing promptable architectures.

The universality of deep neural networks across different modalities and their generalization capabilities to unseen domains play an essential role in medical image segmentation. The recent segment anything model (SAM) has demonstrated strong adaptability across diverse natural scenarios. However, the huge computational costs, demand for manual annotations as prompts and conflict-prone decoding process of SAM degrade its generalization capabilities in medical scenarios. To address these limitations, we propose a modality-decoupled lightweight SAM for domain-generalized medical image segmentation, named De-LightSAM. Specifically, we first devise a lightweight domain-controllable image encoder (DC-Encoder) that produces discriminative visual features for diverse modalities. Further, we introduce the self-patch prompt generator (SP-Generator) to automatically generate high-quality dense prompt embeddings for guiding segmentation decoding. Finally, we design the query-decoupled modality decoder (QM-Decoder) that leverages a one-to-one strategy to provide an independent decoding channel for every modality, preventing mutual knowledge interference of different modalities. Moreover, we design a multi-modal decoupled knowledge distillation (MDKD) strategy to leverage robust common knowledge to complement domain-specific medical feature representations. Extensive experiments indicate that De-LightSAM outperforms state-of-the-arts in diverse medical imaging segmentation tasks, displaying superior modality universality and generalization capabilities. Especially, De-LightSAM uses only 2.0% parameters compared to SAM-H. The source code is available at https://github.com/xq141839/De-LightSAM.

Recently, researchers have achieved significant results in the skeleton-based action recognition. To better model the skeleton sequences, we drive the encoder to learn more discriminative representations in the self-supervised setting. We find that instead of clustering feature vectors to assign pseudo labels for samples as in DeepCluster, ranking them is a more reasonable, reliable, and efficient way to learn more effective feature representations. With this intuition, we propose a novel self-supervised learning framework,DeepRank. Specifically, we rank triplets of skeleton sequences with the ranking labels, obtained from the relative distances among them. Besides, to deeply mine complementary discriminative information that exists in different modalities of skeleton sequences, we further proposeMulti-ViewDeepRank(MV-DeepRank) to enable encoders to comprehensively learn complementary features from multiple modalities. Extensive experimental results on the NTU RGB+D, NTU RGB+D 120, PKU-MMD I, and PKU-MMD II datasets under various evaluation settings demonstrate the generality, transferability, and superiority of our proposed self-supervised learning frameworks. Notably, our frameworks surpass the previous methods that employ the same backbone networks as ours by at least 1.8% (ST-GCN) and 2.1% (STTFormer) under the finetuning setting. Additionally, DeepRank gains a significant advantage on computational complexities,$O(1)$, over the contrastive learning-based methods,$O(\rm{batch size})$, and the clustering-based methods,$O(\rm{number of clusters})$.

Numerous existing deep learning models for time-series classification (TSC) tend to overlook the intricate interplay between higher-and lower-level semantic information. While the focus is often on extracting higher-level semantics from lower-level sources, the reciprocal influence of lower-level information on higher levels is undervalued. To address this, we propose an ensemble transitive bidirectional decoupled self-distillation (ETBiDecSD) method for TSC. ETBiDecSD enhances the robustness of higher-level semantic information using an average feature ensemble (AFE) method to amalgamate the output from each level. Simultaneously, the integrated features are transmitted to each lower level through a directional decoupled distillation (DD) structure. Additionally, to promote deep interaction between higher-and lower-level semantic information, ETBiDecSD introduces a transitive bidirectional DD (TBDD) structure, facilitating the transfer of target-class and nontarget-class knowledge between higher and lower levels. Experimental results demonstrate that whether a fully convolutional network (FCN) with four convolutional blocks or InceptionTime with four Inception blocks is used as the baseline, ETBiDecSD outperforms a quantity of well-established self-distillation algorithms across 85 widely used UCR2018 datasets, as evidenced by the metrics “win”/“tie”/“lose” and avg. rank, which are derived from accuracy andF1-scores. Notably, when compared to a nonself-distillation FCN, ETBiDecSD achieves “win”/“tie”/“lose” results of 64/4/17 in terms of accuracy and 65/4/16 in terms ofF1-score. Similarly, in comparison to a nonself-distillation InceptionTime, ETBiDecSD attains “win”/“tie”/“lose” results of 60/12/13 for accuracy and 57/12/16 forF1-score.

Small lesions play a critical role in early disease diagnosis and intervention of severe infections. Popular models often face challenges in segmenting small lesions, as it occupies only a minor portion of an image, while down-sampling operations may inevitably lose focus on local features of small lesions. To tackle the challenges, we propose a Small-Size-Sensitive Mamba (S³-Mamba), which promotes the sensitivity to small lesions across three dimensions: channel, spatial, and training strategy. Specifically, an Enhanced Visual State Space block is designed to focus on small lesions through multiple residual connections to preserve local features, and selectively amplify important details while suppressing irrelevant ones through channel-wise attention. A Tensor-based Cross-feature Multi-scale Attention is designed to integrate input image features and intermediate-layer features with edge features and exploit the attentive support of features across multiple scales, thereby retaining spatial details of small lesions at various granularities. Finally, we introduce a novel regularized curriculum learning to automatically assess lesion size and sample difficulty, and gradually focus from easy samples to hard ones like small lesions. Extensive experiments on three medical image segmentation datasets show the superiority of our S³-Mamba, especially in segmenting small lesions.

Recent motion-aware large language models have demonstrated promising potential in unifying motion comprehension and generation. However, existing approaches primarily focus on coarse-grained motion-text modeling, where text describes the overall semantics of an entire motion sequence in just a few words. This limits their ability to handle fine-grained motion-relevant tasks, such as understanding and controlling the movements of specific body parts. To overcome this limitation, we pioneer MG-MotionLLM, a unified motion-language model for multi-granular motion comprehension and generation. We further introduce a comprehensive multi-granularity training scheme by incorporating a set of novel auxiliary tasks, such as localizing temporal boundaries of motion segments via detailed text as well as motion detailed captioning, to facilitate mutual reinforcement for motion-text modeling across various levels of granularity. Extensive experiments show that our MG-MotionLLM achieves superior performance on classical text-to-motion and motion-to-text tasks, and exhibits potential in novel fine-grained motion comprehension and editing tasks. Project page: CVI-SZU/MG-MotionLLM

Data-driven genetic programming (GP) has proven highly effective in solving combinatorial optimization problems under dynamic and uncertain environments. A central challenge lies in fast fitness evaluations on large training datasets, especially for complex real-world problems involving time-consuming simulations. Surrogate models, like phenotypic characterization (PC)-based K-nearest neighbors (KNN), have been applied to reduce computational cost. However, the PC-based similarity measure is confined to behavioral characteristics, overlooking genotypic differences, which can limit surrogate quality and impair performance. To address these issues, this paper proposes a pheno-geno unified surrogate GP algorithm, PGU-SGP, integrating phenotypic and genotypic characterization (GC) to enhance surrogate sample selection and fitness prediction. A novel unified similarity metric combining PC and GC distances is proposed, along with an effective and efficient GC representation. Experimental results of a real-life vehicle scheduling problem demonstrate that PGU-SGP reduces training time by approximately 76% while achieving comparable performance to traditional GP. With the same training time, PGU-SGP significantly outperforms traditional GP and the state-of-the-art algorithm on most datasets. Additionally, PGU-SGP shows faster convergence and improved surrogate quality by maintaining accurate fitness rankings and appropriate selection pressure, further validating its effectiveness.

The Remote Procedure Call (RPC) is commonly used for inter-process communications over network, allowing a program to invoke a procedure in another address space, even in another machine as if it were a local call. Its convenience comes from encapsulating network communication. However, for the same reason, it cannot be penetrated by current static analyzers. Since the RPC based programs/frameworks play a more important role in various domains, the static analysis of RPC is significant and cannot be ignored. We have observed that many of the existing RPC frameworks/programs written in Java are based on explicit protocols, which makes them possible to be modelled for static analysis. The challenges are how to identify RPC operations in different frameworks/programs and how to automatically establish relationships between clients and servers. In this paper, we propose a novel approach, RPCBridge, which uses an adapter to unify the most basic operations during the RPC process. It models the RPC with logic rules in a straightforward and precise way based on its semantics, performs points-to analysis and constructs RPC edges in the call graph, making it more complete. The evaluation on real-world large-scale Java programs based on 5 common RPC frameworks shows that our approach can effectively capture the operations of the RPC and construct critical links between clients and servers, in which 60.1 % are the true caller-callee pairs after execution. Our approach is expected to bring significant benefits (+24.3 % leakage paths for the taint analyzer) for previously incompletely modelled code with a very little memory and time overhead, and connect the modules in a system, so that it can be statically analyzed more holistically.

Over the years, various sophisticated deep learning algorithms have surfaced for multivariate time series classification (MTSC), notably the dual-network-based model. This model comprises two parallel networks tailored to time series data: one for local feature extraction and the other for global relation extraction. However, effectively integrating these dual networks poses a significant challenge. To address this, we propose a knowledge aggregation transformer network (KATN) for MTSC. KATN, composed of four aggregation transformer blocks, extracts abundant regularizations and connections hidden within the data. Each block incorporates a modified residual network (MResNet) for local feature extraction and a multi-head attention network for global relation extraction. Initially, the block merges MResNet's output feature with that of the multi-head attention network through an additive operation. Subsequently, it aligns features with a fully connected (i.e., dense) layer and activates neural units using the Gaussian error linear unit function. This strategic feature aggregation allows for capturing long-range dependencies among multiple variables in multivariate time series data. Experimental results demonstrate that KATN significantly outperforms 6 state-of-the-art transformer variants, achieving a ‘win’/‘tie’/‘lose’ record of 9/6/15 and securing the lowest AVG_rank score. Furthermore, when evaluated against 18 existing MTSC algorithms across 13 UEA datasets, KATN consistently delivers superior performance, attaining the lowest AVG_rank score among all compared methods.

Efficient truck dispatching is crucial for optimizing container terminal operations within dynamic and complex scenarios. Despite good progress being made recently with more advanced uncertainty-handling techniques, existing approaches still have generalization issues and require considerable expertise and manual interventions in algorithm design. In this work, we present deep reinforcement learning-assisted genetic programming hyper-heuristics (DRL-GPHH) and their ensemble variant (DRL-GPEHH). These frameworks utilize a reinforcement learning agent to orchestrate a set of auto-generated genetic programming (GP) low-level heuristics, leveraging the collective intelligence, ensuring advanced robustness and an increased level of automation of the algorithm development. DRL-GPEHH, notably, excels through its concurrent integration of a GP heuristic ensemble, achieving enhanced adaptability and performance in complex, dynamic optimization tasks. This method effectively navigates traditional convergence issues of deep reinforcement learning (DRL) in sparse reward and vast action spaces, while avoiding the reliance on expert-designed heuristics. It also addresses the inadequate performance of the single GP individual in varying and complex environments and preserves the inherent interpretability of the GP approach. Evaluations across various real port operational instances highlight the adaptability and efficacy of our frameworks. Essentially, innovations in DRL-GPHH and DRL-GPEHH reveal the synergistic potential of reinforcement learning and GP in dynamic truck dispatching, yielding transformative impacts on algorithm design and significantly advancing solutions to complex real-world optimization problems.

This article proposes a semi-supervised contrastive capsule transformer method with feature-based knowledge distillation (KD) that simplifies the existing semisupervised learning (SSL) techniques for wearable human activity recognition (HAR), called CapMatch. CapMatch gracefully hybridizes supervised learning and unsupervised learning to extract rich representations from input data. In unsupervised learning, CapMatch leverages the pseudolabeling, contrastive learning (CL), and feature-based KD techniques to construct similarity learning on lower and higher level semantic information extracted from two augmentation versions of the data, "weak" and "timecut," to recognize the relationships among the obtained features of classes in the unlabeled data. CapMatch combines the outputs of the weak- and timecut-augmented models to form pseudolabeling and thus CL. Meanwhile, CapMatch uses the feature-based KD to transfer knowledge from the intermediate layers of the weak-augmented model to those of the timecut-augmented model. To effectively capture both local and global patterns of HAR data, we design a capsule transformer network consisting of four capsule-based transformer blocks and one routing layer. Experimental results show that compared with a number of state-of-the-art semi-supervised and supervised algorithms, the proposed CapMatch achieves decent performance on three commonly used HAR datasets, namely, HAPT, WISDM, and UCI_HAR. With only 10% of data labeled, CapMatch achieves values of higher than 85.00% on these datasets, outperforming 14 semi-supervised algorithms. When the proportion of labeled data reaches 30%, CapMatch obtains values of no lower than 88.00% on the datasets above, which is better than several classical supervised algorithms, e.g., decision tree and -nearest neighbor (KNN).

Recently, numerous deep learning algorithms have addressed wearable human activity recognition (HAR), but they often struggle with efficient knowledge transfer to lightweight models for mobile devices. Knowledge distillation (KD) is a popular technique for model compression, transferring knowledge from a complex teacher to a compact student. Most existing KD algorithms consider homogeneous architectures, hindering performance in heterogeneous setups. This is an under-explored area in wearable HAR. To bridge this gap, we propose a heterogeneous mutual KD (HMKD) framework for wearable HAR. HMKD establishes mutual learning within the intermediate and output layers of both teacher and student models. To accommodate substantial structural differences between teacher and student, we employ a weighted ensemble feature approach to merge the features from their intermediate layers, enhancing knowledge exchange within them. Experimental results on the HAPT, WISDM, and UCI_HAR datasets show HMKD outperforms ten state-of-the-art KD algorithms in terms of classification accuracy. Notably, with ResNetLSTMaN as the teacher and MLP as the student, HMKD increases by 9.19% in MLP's $F_{1}$ score on the HAPT dataset.

In regression analysis, methodologies range from black-box approaches like artificial neural networks to white-box techniques like symbolic regression. Renowned for its trans-parency and interpretability, symbolic regression has become increasingly prominent in elucidating complex data relationships. Nevertheless, its effectiveness in managing complex piecewise symbolic regression tasks poses significant challenges. This paper introduces a novel Hierarchical Cooperative Genetic Program-ming (HCGP) framework to address this issue. The HCGP model utilizes a unique hierarchical structure, incorporating dual cooperative genetic programming (GP) populations. This innovative design significantly enhances the capability to solve complex piecewise symbolic regression problems. Implementing a scenario-based GP is central to the HCGP framework, which strategically selects the appropriate underlying calculation GP. This feature enables the system to autonomously learn and adapt to complex scenarios, selecting the most suitable calculation GPs for each case. Our HCGP approach distinguishes itself from traditional and state-of-the-art methods. It demonstrates particular proficiency in modeling piecewise expressions within complex scenarios. The empirical evaluation of our model, conducted using benchmark datasets, has exhibited its superior accuracy and computational efficiency. This progress emphasizes the potential of HCGP in sophisticated data modeling and marks a substantial advancement in a hierarchical structure in complex piecewise symbolic regression.

The online bin packing problem is a well-known optimization challenge that finds application in a wide range of real-world scenarios. In the paper, we propose a novel algorithm called FuzzyPatternPack(FPP), which leverages fuzzy inference and pattern-based predictions of the distribution of item sizes in online bin packing. In comparison to traditional heuristics like BestFit(BF) and FirstFit(FF), as well as the more recent PatternPack(PaP) and ProfilePacking(PrP) algorithm based on online predictions, FPP demonstrates competitive and superior performance in solving various benchmark problems. Particularly, it excels in addressing problems with evolving distributions, making it a promising solution for real-world applications where the item sizes may change over time. This research unveils the promising potential of employing fuzzy logic to effectively address uncertainty in scheduling and planning problems.

With a recently defined AutoGCOP framework, the design of local search algorithms has been defined as the composition of elementary algorithmic components . The effective compositions of the best algorithms thus retain useful knowledge of effective algorithm design . This paper investigates machine learning to learn and extract useful knowledge in effective algorithmic compositions. The process of forecasting algorithmic components in the design of effective local search algorithms is defined as a sequence classification task , and solved by a long short-term memory (LSTM) neural network to systematically analyse algorithmic compositions. Compared with other learning models, the results reveal the superior prediction performance of the proposed LSTM . Further analysis identifies some key features of algorithmic compositions and confirms their effectiveness for improving the prediction, thus supporting effective automated algorithm design.

Multivariate time series classification (MTSC) based on deep learning (DL) has attracted increasingly more research attention. The performance of a DL-based MTSC algorithm is heavily dependent on the quality of the learned representations providing semantic information for downstream tasks, e.g., classification. Hence, a model’s representation learning ability is critical for enhancing its performance. This article proposes a densely knowledge-aware network (DKN) for MTSC. The DKN’s feature extractor consists of a residual multihead convolutional network (ResMulti) and a transformer-based network (Trans), called ResMulti-Trans. ResMulti has five residual multihead blocks for capturing the local patterns of data while Trans has three transformer blocks for extracting the global patterns of data. Besides, to enable dense mutual supervision between lower-and higher-level semantic information, this article adapts densely dual self-distillation (DDSD) for mining rich regularizations and relationships hidden in the data. Experimental results show that compared with 5 state-of-the-art self-distillation variants, the proposed DDSD obtains 13/4/13 in terms of “win”/“tie”/“lose” and gains the lowest-AVG_rank score. In particular, compared with pure ResMulti-Trans, DKN results in 20/1/9 regarding win/tie/lose. Last but not least, DKN overweighs 18 existing MTSC algorithms on 10 UEA2018 datasets and achieves the lowest-AVG_rank score.

Compilers are among the most critical components in the software development. Obviously, their correctness is very important, yet they are among the most complex software systems. The traditional grammar-based compiler random testing measures have two shortcomings. Firstly, the technique generating test programs for one programming language is difficult to migrate to another. The second one is that traditional grammar-based technique haven’t optimized the relation of identifier definition and use yet, causing the undefined identifiers problems or the low quality of the generated test programs. To address these problems, we propose a scope-based compiler testing method ScopeGen in this paper. To generate runnable and diverse test programs, ScopeGen supports two types of identifier strategies based on the scope information, one is scope distance based and the other is global optimization based. These identifier strategies guide the definition and use of identifiers and balance the distribution of identifiers in different scopes. Benefiting from the public grammar dataset Grammar-v4, ScopeGen can be easily migrated to various programming languages. We implement a program generator and generate grammatically correct and runnable test programs for C, Java and Python. Next, we conduct differential testing to identify various bugs in compilers by comparing the output of different compilers. The experimental evaluation of 9 compilers (gcc, clang, icc, icx, Ark, Javac, CPython, Pypy and Codon) shows that ScopeGen outperforms the two state-of-the-art methods (i.e., Csmith and YARPGen) improving more than 69% in inconsistency finding ability. By running ScopeGen we have reported 114 bugs for 4 compilers, 84 of which were confirmed.

With the increasing accessibility of remote sensing videos, remote sensing tracking is gradually becoming a hot issue. However, accurately detecting and tracking in complex remote sensing scenes is still a challenge. In this article, we propose a collaborative learning tracking network for remote sensing videos, including a consistent receptive field parallel fusion module (CRFPF), dual-branch spatial-channel co-attention (DSCA) module, and geometric constraint retrack strategy (GCRT). Considering the small-size objects of remote sensing scenes are difficult for general forward networks to extract effective features, we propose a CRFPF-module to establish parallel branches with consistent receptive fields to separately extract from shallow to deep features and then fuse hierarchical features adaptively. Since the objects and their background are difficult to distinguish, the proposed DSCA-module uses the spatial-channel co-attention mechanism to collaboratively learn the relevant information, which enhances the saliency of the objects and regresses to precise bounding boxes. Considering the interference of similar objects, we designed a GCRT-strategy to judge whether there is a false detection through the estimated motion trajectory and then recover the correct object by weakening the feature response of interference. The experimental results and theoretical analysis on multiple datasets demonstrate our proposed method's feasibility and effectiveness. Code and net are available at https://github.com/Dawn5786/CoCRF-TrackNet.

We are very pleased to introduce this special issue on multiobjective evolutionary optimization for machine learning (MOML). Optimization is at the heart of many machine-learning techniques. However, there is still room to exploit optimization in machine learning. Every machine-learning technique has hyperparameters that can be tuned using evolutionary computation and optimization, considering normally multiple criteria, such as bias, variance, complexity, and fairness in model selection. Multiobjective evolutionary optimization can help meet these criteria for optimizing machine-learning models. Some of the existing approaches address these multiple criteria by transforming the problem into a single-objective optimization problem. However, multiobjective optimization models are able to outperform single-objective ones in contributing to multiple intended objectives (criteria). In recent years, evolutionary computation has been shown to be the premier method for solving multiobjective optimization problems (MOPs), producing both optimal and diverse solutions beyond the capabilities of other heuristics. This is particularly true for very large solution spaces, which is the case in real-world machine-learning problems with many features.

In a marine container terminal, truck dispatching is a crucial problem that impacts the operation efficiency of the whole port. Traditionally, this problem is formulated as an offline optimization problem, whose solutions are, however, impractical for most real-world scenarios primarily because of the uncertainties of dynamic events in both yard operations and seaside loading–unloading operations. These solutions are either unattractive or infeasible to execute. Herein, for more intelligent handling of these uncertainties and dynamics, a novel cooperative double-layer genetic programming hyper-heuristic (CD-GPHH) is proposed to tackle this challenging online optimization problem. In this new CD-GPHH, a novel scenario genetic programming (GP) approach is added on top of a traditional GP method that chooses among different GP heuristics for different scenarios to facilitate optimized truck dispatching. In contrast to traditional arithmetic GP (AGP) and GP with logic operators (LGP) which only evolve on one population, our CD-GPHH method separates the scenario and the calculation into two populations, which improved the quality of solutions in multiscenario problems while reducing the search space. Experimental results show that our CD-GPHH dominates AGP and LGP in solving a multiscenario function fitting problem as well as a truck dispatching problem in a container terminal.

Metaheuristic algorithms have been investigated intensively to address highly complex combinatorial optimization problems. However, most metaheuristic algorithms have been designed manually by researchers of different expertise without a consistent framework. This article proposes a general search framework (GSF) to formulate in a unified way a range of different metaheuristics. With generic algorithmic components, including selection heuristics and evolution operators, the unified GSF aims to serve as the basis of analyzing algorithmic components for automated algorithm design. With the established new GSF, two reinforcement learning (RL)-based methods, deep$Q$-network based and proximal policy optimization-based methods, have been developed to automatically design a new general population-based algorithm. The proposed RL-based methods are able to intelligently select and combine appropriate algorithmic components during different stages of the optimization process. The effectiveness and generalization of the proposed RL-based methods are validated comprehensively across different benchmark instances of the capacitated vehicle routing problem with time windows. This study contributes to making a key step toward automated algorithm design with a general framework supporting fundamental analysis by effective machine learning.

A competitive traveling salesmen problem is a variant of traveling salesman problem in that multiple agents compete with each other in visiting a number of cities. The agent who is the first one to visit a city will receive a reward. Each agent aims to collect as more rewards as possible with the minimum traveling distance. There is still not effective algorithms for this complicated decision making problem. We investigate an improved ant colony approach for the competitive traveling sales-men problem which adopts a time dominance mechanism and a revised pheromone depositing method to improve the quality of solutions with less computational complexity. Simulation results show that the proposed algorithm outperforms the state of art algorithms.

Integrated berth and quay crane allocation problem (BQCAP) are two essential seaside operational problems in container terminal scheduling. Most existing works consider only one objective on operation and partition of quay into berths of the same lengths. In this study, BQCAP is modeled in a multiobjective setting that aims to minimize total equipment used and overall operational time and the quay is partitioned into berths of different lengths, to make the model practical in the real-world and complex quay layout setting. To solve the new BQCAP efficiently, a multiobjective hydrologic cycle optimization algorithm is devised considering problem characteristics and historical Pareto-optimal solutions. Specifically, the quay crane of the large vessel in all Pareto-optimal solutions is rearranged to increase the chance of finding a good solution. Besides, worse solutions are probabilistic retained to maintain diversity. The proposed algorithm is applied to a real-world terminal scheduling problem with different sizes from a container terminal company. Experimental results show that our algorithm generally outperforms the other well-known peer algorithms and its variants on solving BQCAP, especially in finding the Pareto-optimal solutions range.

The increasing applications of polarimetric synthetic aperture radar (PolSAR) image classification demand for effective superpixels’ algorithms. Fuzzy superpixels’ algorithms reduce the misclassification rate by dividing pixels into superpixels, which are groups of pixels of homogenous appearance and undetermined pixels. However, two key issues remain to be addressed in designing a fuzzy superpixel algorithm for PolSAR image classification. First, the polarimetric scattering information, which is unique in PolSAR images, is not effectively used. Such information can be utilized to generate superpixels more suitable for PolSAR images. Second, the ratio of undetermined pixels is fixed for each image in the existing techniques, ignoring the fact that the difficulty of classifying different objects varies in an image. To address these two issues, we propose a polarimetric scattering information-based adaptive fuzzy superpixel (AFS) algorithm for PolSAR images classification. In AFS, the correlation between pixels’ polarimetric scattering information, for the first time, is considered through fuzzy rough set theory to generate superpixels. This correlation is further used to dynamically and adaptively update the ratio of undetermined pixels. AFS is evaluated extensively against different evaluation metrics and compared with the state-of-the-art superpixels’ algorithms on three PolSAR images. The experimental results demonstrate the superiority of AFS on PolSAR image classification problems.

Over the years, a large number of deep learning algorithms have been developed for time series classification (TSC). These algorithms were usually invented by researchers with prior knowledge and experience. However, it is a critical challenge for beginners to design decent structures to address various TSC problems. To this end, we propose a robust neural temporal search (RNTS) framework for identifying the relationships and features in TSC data, which mainly contains a temporal search network and an attentional LSTM network. To be specific, inspired by the idea of neural architecture search (NAS), the temporal search network automatically transforms its structure for each dataset according to its characteristics, responsible for extracting basic features. The attentional LSTM network is used to explore the complex shapelets and relationships the former may ignore. Experimental results demonstrate that RNTS achieves the best overall performance on 24 standard datasets selected from the UCR 2018 archive, in terms of three measures based on the top-l accuracy, compared with a number of state-of-the-art approaches.

This special section is formed by 15 articles of outstanding quality that together comprise a snapshot of cutting edge automated machine learning (AutoML) research.

In recent research, hyper-heuristics have attracted increasing attention in various fields. The most appealing feature of hyper-heuristics is that they aim to provide more generalized solutions to optimization problems by searching in a high-level space of heuristics instead of direct problem domains. Despite the promising findings in hyper-heuristics, the design of more general search methodologies still presents a key research. Evolutionary multitasking is a relatively new evolutionary paradigm which attempts to solve multiple optimization problems simultaneously. It exploits the underlying similarities among different optimization tasks by transferring information among them, thus accelerating the optimization of all tasks. Inherently, hyper-heuristics and evolutionary multitasking are similar in the following three ways: 1) they both operate on third-party search spaces; 2) high-level search methodologies are universal; and 3) they both conduct cross-domain optimization. To integrate their advantages effectively, i.e., the knowledge-transfer and cross-domain optimization of evolutionary multitasking and the search in the heuristic spaces of hyper-heuristics, in this article, a unified framework of evolutionary multitasking graph-based hyper-heuristic (EMHH) is proposed. To assess the generality and effectiveness of the EMHH, population-based graph-based hyper-heuristics integrated with evolutionary multitasking to solve exam timetabling and graph-coloring problems, separately and simultaneously, are studied. The experimental results demonstrate the effectiveness, efficiency, and increased the generality of the proposed unified framework compared with single-tasking hyper-heuristics.

International and domestic maritime trade has been expanding dramatically in the last few decades, seaborne container transportation has become an indispensable part of maritime trade efficient and easy-to-use containers. As an important hub of container transport, container terminals use a range of metrics to measure their efficiency, among which the hourly container throughput (i.e., the number of twentyfoot equivalent unit containers, or TEUs) is the most important objective to improve. This paper proposes a genetic programming approach to build a dynamic truck dispatching system trained on real-world stochastic operations data. The experimental results demonstrated the superiority of this dynamic approach and the potential for practical applications.

Directed grey-box fuzzing is an effective technique to find bugs in programs with the guidance of user-specified target locations. However, it can hardly reach a target location guarded by certain syntax tokens (Guard Tokens for short), which is often seen in programs with string operations or grammar/lexical parsing. Only the test inputs containing Guard Tokens are likely to reach the target locations, which challenges the effectiveness of mutation-based fuzzers. In this paper, a Guard Token directed grey-box fuzzer called GTFuzz is presented, which extracts Guard Tokens according to the target locations first and then exploits them to direct the fuzzing. Specifically, to ensure the new test cases generated from mutations contain Guard Tokens, new strategies of seed prioritization, dictionary generation, and seed mutation are also proposed, so as to make them likely to reach the target locations. Experiments on real-world software show that GTFuzz can reach the target locations, reproduce crashes, and expose bugs more efficiently than the state-of-the-art grey-box fuzzers (i.e., AFL, AFLGO and FairFuzz). Moreover, GTFuzz identified 23 previously undiscovered bugs in LibXML2 and MJS.

In mobile-edge computing (MEC), smart mobile devices (SMDs) with limited computation resources and battery lifetime can offload their computing-intensive tasks to MEC servers, thus to enhance the computing capability and reduce the energy consumption of SMDs. Nevertheless, offloading tasks to the edge incurs additional transmission time and thus higher execution delay. This article studies the tradeoff between the completion time of applications and the energy consumption of SMDs in MEC networks. The problem is formulated as a multiobjective computation offloading problem (MCOP), where the task precedence, i.e., ordering of tasks in SMD applications, is introduced as a new constraint in the MCOP. An improved multiobjective evolutionary algorithm based on decomposition (MOEA/D) with two performance enhancing schemes is proposed: 1) the problem-specific population initialization scheme uses a latency-based execution location (EL) initialization method to initialize the EL (i.e., either local SMD or MEC server) for each task and 2) the dynamic voltage and frequency scaling-based energy conservation scheme helps to decrease the energy consumption without increasing the completion time of applications. The simulation results clearly demonstrate that the proposed algorithm outperforms a number of state-of-the-art heuristics and metaheuristics in terms of the convergence and diversity of the obtained nondominated solutions.

In this work, using a Behavioural Operational Research (BOR) perspective, we develop a model for the Home Health Care Nurse Scheduling Problem (HHCNSP) with application to renal patients taking Peritoneal Dialysis (PD) at their own homes as treatment for their Chronic Kidney Disease (CKD) in the UK. The modelling framework presented in this paper can be extended to much wider spectra of scheduling problems concerning patients with different long-term conditions in future work.

Compared with traditional course websites, the open online course platforms have a larger number of courses, and course recommendation is becoming increasingly important. In this paper, we shall propose a course recommendation model based on academic social networks, a hybrid method combing with association rules algorithm and an improved multi-similarity algorithm of multi-source information, which can recommend courses according to potential relationships between courses and users implicit interests. The proposed model is applied to SCHOLAT. Judging from our experimental results, the new model is capable of reducing cold-start problem and providing better accuracy.

In this paper, a Mixed-Shift Vehicle Routing Problem is proposed based on a real-life container transportation problem. In a long planning horizon of multiple shifts, transport tasks are completed satisfying the time constraints. Due to the different travel distances and time of tasks, there are two types of shifts ( long shift and short shift ) in this problem. The unit driver cost for long shifts is higher than that of short shifts . A mathematical model of this Mixed-Shift Vehicle Routing Problem with Time Windows (MS-VRPTW) is established in this paper, with two objectives of minimizing the total driver payment and the total travel distance. Due to the large scale and nonlinear constraints, the exact search showed is not suitable to MS-VRPTW. An initial solution construction heuristic (EBIH) and a selective perturbation Hyper-Heuristic (GIHH) are thus developed. In GIHH, five heuristics with different extents of perturbation at the low level are adaptively selected by a high level selection scheme with the Hill Climbing acceptance criterion. Two guidance indicators are devised at the high level to adaptively adjust the selection of the low level heuristics for this bi-objective problem. The two indicators estimate the objective value improvement and the improvement direction over the Pareto Front, respectively. To evaluate the generality of the proposed algorithms, a set of benchmark instances with various features is extracted from real-life historical datasets. The experiment results show that GIHH significantly improves the quality of the final Pareto Solution Set, outperforming the state-of-the-art algorithms for similar problems. Its application on VRPTW also obtains promising results.

Recommender system (RS) plays an important role in helping users find the information they are interested in and providing accurate personality recommendation. It has been found that among all the users, there are some user groups called “core users” or “information core” whose historical behavior data are more reliable, objective and positive for making recommendations. Finding the information core is of great interests to greatly increase the speed of online recommendation. There is no general method to identify core users in the existing literatures. In this paper, a general method of finding information core is proposed by modelling this problem as a combinatorial optimization problem. A novel Evolutionary Algorithm with Elite Population (EA-EP) is presented to search for the information core, where an elite population with a new crossover mechanism named as ordered crossover is used to accelerate the evolution. Experiments are conducted on Movielens (100k) to validate the effectiveness of our proposed algorithm. Results show that EA-EP is able to effectively identify core users and leads to better recommendation accuracy compared to several existing greedy methods and the conventional collaborative filter (CF). In addition, EA-EP is shown to significantly reduce the time of online recommendation.

This paper proposes a change detection algorithm in synthetic aperture radar (SAR) images based on the salient image guidance and an accelerated genetic algorithm (S-aGA). The difference image is first generated by logarithm ratio operator based on the bi-temporal SAR images acquired in the same region. Then a saliency detection model is applied in the difference image to extract the salient regions containing the changed class pixels. The salient regions are further divided by fuzzy c-means (FCM) clustering algorithm into three categories: changed class (set of pixels with high gray values), unchanged class (set of pixels with low gray values) and undetermined class (set of pixels with middle gray value, which are difficult to classify). Finally, the proposed accelerated GA is applied to explore the reduced search space formed by the undetermined-class pixels according to an objective function considering neighborhood information. In S-aGA, an efficient mutation operator is designed by using the neighborhood information of undetermined-class pixels as the heuristic information to determine the mutation probability of each undetermined-class pixel adaptively, which accelerates the convergence of the GA significantly. The experimental results on two data sets demonstrate the efficiency of the proposed S-aGA. On the whole, S-aGA outperforms five other existing methods including the simple GA in terms of detection accuracy. In addition, S-aGA could obtain satisfying solution within limited generations, converging much faster than the simple GA.

In this paper, we investigate a constrained portfolio selection problem with cardinality constraint, minimum size and position constraints, and non-convex transaction cost. A hybrid method named Local Search Branch-and-Bound (LS-B&B) which integrates local search with B&B is proposed based on the property of the problem, i.e. cardinality constraint. To eliminate the computational burden which is mainly due to the cardinality constraint, the corresponding set of binary variables is identified as core variables. Variable fixing (Bixby, Fenelon et al. 2000) is applied on the core variables, together with a local search, to generate a sequence of simplified sub-problems. The default B&B search then solves these restricted and simplified subproblems optimally due to their reduced size comparing to the original one. Due to the inherent similar structures in the sub-problems, the solution information is reused to evoke the repairing heuristics and thus accelerate the solving procedure of the subproblems in B&B. The tight upper bound identified at early stage of the search can discard more subproblems to speed up the LS-B&B search to the optimal solution to the original problem. Our study is performed on a set of portfolio selection problems with non-convex transaction costs and a number of trading constraints based on the extended mean-variance model. Computational experiments demonstrate the effectiveness of the algorithm by using less computational time.

The Vehicle Routing Problem with Time Windows (VRPTW) consists of constructing least cost routes from a depot to a set of geographically scattered service points and back to the depot, satisfying service time interval and capacity constraints. A Variable Neighbourhood Search algorithm with Compound Neighbourhoods is proposed to solve VRPTW in this paper. A number of independent neighbourhood operators are composed into compound neighbourhood operators in a new way, to explore wider search area concerning two objectives (to minimize the number of vehicles and the total travel distance) simultaneously. Promising results are obtained on benchmark datasets

This paper studies the state-of-art constrained portfolio optimisation models, using exact solver to identify the optimal solutions or lower bound for the benchmark instances at the OR-library with extended constraints. The effects of pre-assignment, round-lot, and class constraints based on the quantity and cardinality constrained Markowitz model are firstly investigated to gain insights of increased problem difficulty, followed by the analysis of various constraint settings including those mostly studied in the literature. The study aims to provide useful guidance for future investigations in computational algorithms

This paper presents a modified ant colony optimization (ACO) approach for the network coding resource minimization problem. It is featured with several attractive mechanisms specially devised for solving the concerned problem: 1) a multidimensional pheromone maintenance mechanism is put forward to address the issue of pheromone overlapping; 2) problem-specific heuristic information is employed to enhance the capability of heuristic search (neighboring area search); 3) a tabu-table-based path construction method is devised to facilitate the construction of feasible (link-disjoint) paths from the source to each receiver; 4) a local pheromone updating rule is developed to guide ants to construct appropriate promising paths; and 5) a solution reconstruction method is presented, with the aim of avoiding prematurity and improving the global search efficiency of proposed algorithm. Due to the way it works, the ACO can well exploit the global and local information of routing-related problems during the solution construction phase. The simulation results on benchmark instances demonstrate that with the integrated five extended mechanisms, our algorithm outperforms a number of existing algorithms with respect to the best solutions obtained and the computational time.

Portfolio optimization is one of the most important problems in the finance field. The traditional mean-variance model has its drawbacks since it fails to take the market uncertainty into account. In this work, we investigate a two-stage stochastic portfolio optimization model with a comprehensive set of real world trading constraints in order to capture the market uncertainties in terms of future asset prices. A hybrid approach, which integrates genetic algorithm (GA) and a linear programming (LP) solver is proposed in order to solve the model, where GA is used to search for the assets selection heuristically and the LP solver solves the corresponding sub-problems of weight allocation optimally. Scenarios are generated to capture uncertain prices of assets for five benchmark market instances. The computational results indicate that the proposed hybrid algorithm can obtain very promising solutions. Possible future research directions are also discussed.

In this paper we investigate a multi-objective portfolio selection model with three criteria: risk, return and liquidity for investors. Non-probabilistic uncertainty factors in the market, such as imprecision and vagueness of investors’ preference and judgement are simulated in the portfolio selection process. The liquidity of portfolio cannot be accurately predicted in the market, and thus is measured by fuzzy set theory. Invertors’ individual preference and judgement are cooperated in the decision making process by using satisfaction functions to measure the objectives. A compromise based goal programming approach is applied to find compromised solutions. By this approach, not only can we obtain quality solutions in a reasonable computational time, but also we can achieve a trade-off between the objectives according to investors’ preference and judgement to enable a better decision making. We analyse the portfolio strategies obtained by using the proposed simulation approach subject to different settings in the satisfaction functions.

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

Hyper-heuristic approaches aim to automate heuristic design in order to solve multiple problems instead of designing tailor-made methodologies for individual problems. Hyper-heuristics accomplish this through a high-level heuristic (heuristic selection mechanism and an acceptance criterion). This automates heuristic selection, deciding whether to accept or reject the returned solution. The fact that different problems, or even instances, have different landscape structures and complexity, the design of efficient high-level heuristics can have a dramatic impact on hyper-heuristic performance. In this paper, instead of using human knowledge to design the high-level heuristic, we propose a gene expression programming algorithm to automatically generate, during the instance-solving process, the high-level heuristic of the hyper-heuristic framework. The generated heuristic takes information (such as the quality of the generated solution and the improvement made) from the current problem state as input and decides which low-level heuristic should be selected and the acceptance or rejection of the resultant solution. The benefit of this framework is the ability to generate, for each instance, different high-level heuristics during the problem-solving process. Furthermore, in order to maintain solution diversity, we utilize a memory mechanism that contains a population of both high-quality and diverse solutions that is updated during the problem-solving process. The generality of the proposed hyper-heuristic is validated against six well-known combinatorial optimization problems, with very different landscapes, provided by the HyFlex software. Empirical results, comparing the proposed hyper-heuristic with state-of-the-art hyper-heuristics, conclude that the proposed hyper-heuristic generalizes well across all domains and achieves competitive, if not superior, results for several instances on all domains.

Nurse scheduling is a complex combinatorial optimization problem. With increasing healthcare costs, and a shortage of trained staff it is becoming increasingly important for hospital management to make good operational decisions. A major element of hospital expenditure is staff cost. In order to help Kajang Hospital to make decisions about staffing and work scheduling, a simulation model was created to analyse the impact of alternate work schedules and investigate the optimum balance between the staffing levels of the ward and the ability to achieve good quality schedules. In this paper, we extend our novel approach to solve the nurse scheduling problem by transforming it through Information Granulation. This approach satisfies the rules of a typical hospital environment based on a real data set benchmark problem from Kajang Hospital. Generating good work schedules has a great influence on nurses` working condition which is strongly related to the level of a quality health care. Domain transformation is an approach to solving complex problems that relies on well-justified simplification of the original problem. Solution of such a simplified problem and subsequent refinement of this solution to compensate for the simplifications introduced in the first step. Compared to conventional methods, our approach involves judicious grouping (information granulation) of shifts types’ that transforms the original problem into a smaller solution domain. Later these schedules from the smaller problem domain are converted back into the original problem domain by taking into account the constraints that could not be represented in the smaller domain. An Integer Programming (IP) is formulated to solve the transformed scheduling problem by expending the branch and bound algorithm. We have used the GNU Octave, open source mathematical modelling and simulation software for Windows to solve this problem. Results from simulations on real data problem sets for a typical hospital in Malaysia shows that this algorithm facilitated computation of feasible schedules in a short time with non-critical constraints being satisfied to a large degree. The resulting solutions facilitated cost benefit analysis of different staffing levels.

Abstract: We present a computational study on 112 instances of the Workforce Scheduling and Routing Problem (WSRP). This problem has applications in many service provider industries where employees visit customers to perform activities. Given their similarity, we adapt a mathematical programming model from the literature on vehicle routing problem with time windows (VRPTW) to conduct this computational study on the WSRP. We generate a set of WSRP instances from a well-known VRPTW data set. This work has three objectives. First, to investigate feasibility and optimality on a range of medium size WSRP instances with different dis-tribution of visiting locations and including teaming and connected activities constraints. Second, to compare the generated WSRP instances to their counterpart VRPTW instances with respect to their difficulty. Third, to determine the computation time required by a mathematical programming solver to find feasible solutions for the generated WSRP instances. It is observed that although the solver can achieve feasible solutions for some instances, the current solver capabilities are still limited. Another observation is the WSRP instances present an increased degree of difficulty because of the additional constraints. The key contribution of this paper is to present some test instances and corresponding benchmark study for the WSRP.

This paper discusses and analyses the tradeoff between the flexibility afforded with greater number of staff and the implied cost of employing extra staff in the context of the nurse-scheduling problem. If the number of staff is constant, our study allows quantification of the degree of pressure put on the staff resulting from the schedules that do not satisfy their preferences for shift allocation. We present a practical approach, based on our domain transformation methodology that achieves good quality schedules without high computational requirements.

Simulation modelling of the initial assignments of exams to time-slots provides an alternative approach to the establishment of a set of feasible solutions that are subsequently optimized. In this research, we analyze two backtracking strategies for reassigning exams after the initial allocation of exams to time-slots. We propose two approaches for backtracking, BT1 and BT2. The study indicates that backtracking is an effective approach for improving the quality of the examination schedule where BT2 has outperformed BT1 in a number of cases.

The relevant literature showed that many heuristic techniques have been investigated for constrained portfolio optimization problem but none of these studies presents multi-objective Scatter Search approach.In this work, we present a hybrid multi-objective population-based evolutionary algorithm based on Scatter Search with an external archive to solve the constrained portfolio selection problem.We considered the extended meanvariance portfolio model with three practical constraints which limit the number of assets in a portfolio, restrict the proportions of assets held in the portfolio and pre-assign specific assets in the portfolio.The proposed hybrid metaheuristic algorithm follows the basic structure of the Scatter Search and defines the reference set solutions based on Pareto dominance and crowding distance.New Subset generation and combination methods are proposed to generate efficient and diversified portfolios.Hill Climbing operation is integrated to search for improved portfolios.The performance of the proposed multi-objective Scatter Search algorithm is compared with the Non-dominated Sorting Genetic Algorithm (NSGA-II), Strength Pareto Evolutionary Algorithm (SPEA-2) and Pareto Envelope-based Selection Algorithm (PESA-II).Experimental results indicate that the proposed algorithm is a promising approach for solving the constrained portfolio selection problem.Measurements by the performance metrics indicate that it outperforms NSGA-II, SPEA2 and PESA-II on the solution quality within a shorter computational time.

This paper presents a variable depth search for the nurse rostering problem. The algorithm works by chaining together single neighbourhood swaps into more effective compound moves. It achieves this by using heuristics to decide whether to continue extending a chain and which candidates to examine as the next potential link in the chain. Because end users vary in how long they are willing to wait for solutions, a particular goal of this research was to create an algorithm that accepts a user specified computational time limit and uses it effectively. When compared against previously published approaches the results show that the algorithm is very competitive.

Designing generic problem solvers that perform well across a diverse set of problems is a challenging task. In this work, we propose a hyper-heuristic framework to automatically generate an effective and generic solution method by utilizing grammatical evolution. In the proposed framework, grammatical evolution is used as an online solver builder, which takes several heuristic components (e.g., different acceptance criteria and different neighborhood structures) as inputs and evolves templates of perturbation heuristics. The evolved templates are improvement heuristics, which represent a complete search method to solve the problem at hand. To test the generality and the performance of the proposed method, we consider two well-known combinatorial optimization problems: exam timetabling (Carter and ITC 2007 instances) and the capacitated vehicle routing problem (Christofides and Golden instances). We demonstrate that the proposed method is competitive, if not superior, when compared to state-of-the-art hyper-heuristics, as well as bespoke methods for these different problem domains. In order to further improve the performance of the proposed framework we utilize an adaptive memory mechanism, which contains a collection of both high quality and diverse solutions and is updated during the problem solving process. Experimental results show that the grammatical evolution hyper-heuristic, with an adaptive memory, performs better than the grammatical evolution hyper-heuristic without a memory. The improved framework also outperforms some bespoke methodologies, which have reported best known results for some instances in both problem domains.

This paper presents a new class of intelligent systems, called Evolutionary Ruin and Stochastic Recreate, that can learn and adapt to the changing enviroment. It improves the original Ruin and Recreate principle’s performance by incorporating an Evolutionary Ruin step which implements evolution within a single solution. In the proposed approach, a cycle of Solution Decomposition, Evolutionary Ruin and Stochastic Recreate continues until stopping conditions are reached. The Solution Decomposition step first uses some domain knowledge to break a solution down into its components and assign a score to each. The Evolutionary Ruin step then applies two operators (namely Selection and Mutation) to destroy a certain fraction of the entire solution. After the above steps, an input solution becomes partial and thus the resulting partial solution needs to be repaired. The repair is carried out by using the Stochastic Recreate step to reintroduce the removed items in a specific way (somewhat stochastic in order to have a better chance to jump out of the local optima), and then ask the underlying improvement heuristic whether this move will be accepted. These three steps are executed in sequence until a specific stopping condition is reached. Therefore, optimisation is achieved by solution disruption, iterative improvement and a stochastic constructive repair process performed within. Encouraging experimental results on exam timetabling problems are reported.

The Second International Timetabling Competition (TTC2007) opened in August 2007. Building on the success of the first competition in 2002, this sequel aimed to further develop research activity in the area of educational timetabling. The broad aim of the competition was to create better understanding between researchers and practitioners by allowing emerging techniques to be developed and tested on real-world models of timetabling problems. To support this, a primary goal was to provide researchers with models of problems faced by practitioners through incorporating a significant number of real-world constraints. Another objective of the competition was to stimulate debate within the widening timetabling research community. The competition was divided into three tracks to reflect the important variations that exist in educational timetabling within higher education. Because these formulations incorporate an increased number of “real-world” issues, it is anticipated that the competition will now set the research agenda within the field. After finishing in January 2008, final results were made available in May 2008. Along with background to the competition, the competition tracks are described here along with a brief overview of the techniques used by the competition winners.

Nurse Rostering problems represent a subclass of scheduling problems that are hard to solve. Their complexity is due to the large solution spaces and the many objectives and constraints that need to be fulfilled. In this study, we propose a hierarchical method of granulation of problem domain through preprocessing of constraints. A set of zero-cost patterns in the granulated search space provides a basis for the generation of work schedules. Feasible schedules calculated for week 1 are used to define zero-cost shift patterns that can be deployed in week 2. These in turn are used for the generation of feasible schedules for week 2. The process can be applied over the extended time frame. We show that the granulation of the problem description in terms of constraints and scheduling time frames leads to a more manageable computing task.

conflict chains, spread matrix, pre-processing, exam-to-slot allocation. In this paper, we are introducing a new method of granular exam-to-slot allocation based on the preprocessing of the basic student-exam information into a more abstract (granulated) entity of conflict chains. Since the conflict chains are designed to capture the mutual dependencies between exams, they enable us to reason about the exam-to-slot allocation for all exams in a chain rather than just one exam at-a-time. The initial exam-to-slot allocation, generated through the processing of conflict chains, is then refined by considering the spread of the exams in the examination session so as to minimize the appropriately defined cost function. The granular pre-processing of problem data has been shown to enhance the efficiency of the exam scheduling task and has led to the identification of very competitive exam schedules.

Hyper-heuristics can be thought of as "heuristics to choose heuristics". They are concerned with adaptively finding solution methods, rather than directly producing a solution for the particular problem at hand. Hence, an important feature of hyper-heuristics is that they operate on a search space of heuristics rather than directly on a search space of problem solutions. A motivating aim is to build systems which are fundamentally more generic than is possible today. Understanding the structure of these heuristic search spaces is therefore, a research direction worth exploring. In this paper, we use the notion of fitness landscapes in the context of constructive hyper-heuristics. We conduct a landscape analysis on a heuristic search space conformed by sequences of graph coloring heuristics for timetabling. Our study reveals that these landscapes have a high level of neutrality and positional bias. Furthermore, although rugged, they have the encouraging feature of a globally convex or big valley structure, which indicates that an optimal solution would not be isolated but surrounded by many local minima. We suggest that using search methodologies that explicitly exploit these features may enhance the performance of constructive hyper-heuristics.