Fairness in machine learning (ML) has garnered significant attention. However, current research has mainly concentrated on the distributive fairness of ML models, with limited focus on another dimension of fairness, i.e., procedural fairness. In this paper, we first define the procedural fairness of ML models by drawing from the established understanding of procedural fairness in philosophy and psychology fields, and then give formal definitions of individual and group procedural fairness. Based on the proposed definition, we further propose a novel metric to evaluate the group procedural fairness of ML models, called GPFFAE, which utilizes a widely used explainable artificial intelligence technique, namely feature attribution explanation (FAE), to capture the decision process of ML models. We validate the effectiveness of GPFFAE on a synthetic dataset and eight real-world datasets. Our experimental studies have revealed the relationship between procedural and distributive fairness of ML models. After validating the proposed metric for assessing the procedural fairness of ML models, we then propose a method for identifying the features that lead to the procedural unfairness of the model and propose two methods to improve procedural fairness based on the identified unfair features. Our experimental results demonstrate that we can accurately identify the features that lead to procedural unfairness in the ML model, and both of our proposed methods can significantly improve procedural fairness while also improving distributive fairness, with a slight sacrifice on the model performance.

Offering rich contexts to Large Language Models (LLMs) has shown to boost the performance in various tasks, but the resulting longer prompt would increase the computational cost and might exceed the input limit of LLMs. Recently, some prompt compression methods have been suggested to shorten the length of prompts by using language models to generate shorter prompts or by developing computational models to select important parts of original prompt. The generative compression methods would suffer from issues like hallucination, while the selective compression methods have not involved linguistic rules and overlook the global structure of prompt. To this end, we propose a novel selective compression method called PartPrompt. It first obtains a parse tree for each sentence based on linguistic rules, and calculates local information entropy for each node in a parse tree. These local parse trees are then organized into a global tree according to the hierarchical structure such as the dependency of sentences, paragraphs, and sections. After that, the root-ward propagation and leaf-ward propagation are proposed to adjust node values over the global tree. Finally, a recursive algorithm is developed to prune the global tree based on the adjusted node values. The experiments show that PartPrompt receives the state-of-the-art performance across various datasets, metrics, compression ratios, and target LLMs for inference. The in-depth ablation studies confirm the effectiveness of designs in PartPrompt, and other additional experiments also demonstrate its superiority in terms of the coherence of compressed prompts and in the extreme long prompt scenario.

In this paper, we introduce a novel approach for addressing the multi-objective optimization problem in large language model merging via black-box multi-objective optimization algorithms. The goal of model merging is to combine multiple models, each excelling in different tasks, into a single model that outperforms any of the individual source models. However, the effectiveness of conventional model merging methods is constrained by human intuition or domain knowledge. While existing optimization-based model merging methods can automatically search for model merging parameter configurations, they often struggle to find a satisfactory configuration within a limited evaluation budget. To address this challenge, we propose a novel and sample-efficient automated model merging method, named MM-MO. This method leverages multi-objective Bayesian optimization algorithms to autonomously search for great merging configurations across various tasks. In MMMO, we proposed an enhanced acquisition strategy and an auxiliary optimization objective to improve the search process. Our enhanced acquisition strategy integrates a weak-to-strong method to refine the acquisition function, enabling previously evaluated superior configurations to guide the search for new ones. Meanwhile, Fisher information is utilized to further filter these configurations, increasing the possibility of finding high-quality merging configurations. Additionally, we design a sparsity metric as an auxiliary optimization objective, further enhance the models generalization performance across different tasks. We conducted comprehensive experiments with other mainstream model merging methods, demonstrating that the proposed MMMO algorithm is competitive and effective in achieving high-quality model merging.

For automated vehicle, motion planning especially multi-vehicle cooperative motion planning (MVCMP), is an important and challenging problem, while the high-dimensional coupled nonlinear constraints make it become a highly non-convex nonlinear programming (NLP) problem. In this paper, we propose a parallel computing and convexifying guidance framework based on alternating direction method of multipliers (ADMM) and constraint convexification. By applying ADMM and introducing auxiliary variables, the original problem is decomposed into two types of sub-problems that can be solved in a parallel manner. The first type of sub-problem only contains kinematics constraints and can be tackled by the proposed ‘First Solve Then Regulate Time’ (FSTRT) method, which can eliminate the time coupling and divide this sub-problem into multiple parallel secondary sub-problems for each vehicle. The second type of sub-problem only considers collision avoidance constraints among multiple vehicles, and can also be solved in parallel based on copy variable. In particular, the terminal guided convex feasible set (TG-CFS) algorithm and convexifying guidance strategy are proposed to achieve constraint convexification and efficient warm-start for this sub-problem. The advantage of proposed algorithm lies at effectively resolving constraint coupling and reduce the dimension of original problem, thereby achieving parallel and fast computation of the sub-problems. Simulation and comparison results of different cases indicate that the proposed algorithm can significantly improve the computational efficiency while preserving the optimality.

Transfer reinforcement learning (TRL) aims to boost the efficiency of reinforcement learning (RL) agents by leveraging knowledge from related tasks. Prior research primarily focuses on intradomain transfer, overlooking the complexities of transferring knowledge across tasks with differing state and action spaces. Recent efforts in cross-domain TRL aim to bridge this gap by establishing mappings between disparate source and target spaces, thereby enabling knowledge transfer across RL tasks with varied state and action configurations. However, existing studies often rely on strict prior assumptions about the relationships between state spaces, which limits their practical generality. In this article, we propose a novel approach to cross-domain TRL based on seeded graph matching, which enables alignment between source and target tasks regardless of differences in their state-action spaces. In particular, we model RL tasks as directed graphs, identify seed node pairs based on common RL properties, and devise a graph matching algorithm to align the source and target tasks by leveraging their structural characteristics. Building on this alignment, we introduce a policy-based transfer algorithm that improves the performance of the target RL task as its RL process progresses. Finally, we conduct comprehensive empirical studies on both discrete and continuous tasks with diverse state-action spaces. The experimental results validate the effectiveness of the proposed algorithm.

Multi-objective Bayesian optimization (MOBO) has shown promising performance on various expensive multi-objective optimization problems (EMOPs). However, effectively modeling complex distributions of the Pareto optimal solutions is difficult with limited function evaluations. Existing Pareto set learning algorithms may exhibit considerable instability in such expensive scenarios, leading to significant deviations between the obtained solution set and the Pareto set (PS). In this paper, we propose a novel Composite Diffusion Model based Pareto Set Learning algorithm (CDM-PSL) for expensive MOBO. CDM-PSL includes both unconditional and conditional diffusion model for generating high-quality samples efficiently. Besides, we introduce a weighting method based on information entropy to balance different objectives. This method is integrated with a guiding strategy to appropriately balancing different objectives during the optimization process. Experimental results on both synthetic and real-world problems demonstrates that CDM-PSL attains superior performance compared with state-of-the-art MOBO algorithms.

Standardized benchmarks like RobustBench are crucial for evaluating adversarial robustness. However, the increasing dominance of models trained on massive synthetic datasets (orders of magnitude larger than original training sets) raises questions about reported performance gains. This work identifies and investigates a potential inflation factor: high feature-level similarity between large-scale synthetic training data and benchmark test sets. We argue this similarity is an inherent characteristic arising from the probabilistic generation process of these large datasets, which naturally produces examples highly similar to test instances in feature space. This creates what we term an “Implicit Information Advantage,” where models effectively train on near-duplicates of test instances. Through comprehensive empirical analysis, we demonstrate that: (1) Synthetic datasets exhibit significantly higher similarity to the test set compared to the original training data. (2) A direct correlation exists between this similarity and robustness outcomes, with test images benefiting most having the highest similarity scores. (3) Strikingly, ablation studies show that training on just a small fraction (e.g., 1%) of the most similar synthetic examples can yield robustness comparable to using the full massive dataset. These findings suggest current benchmarks may overestimate true robust generalization due to this similarity artifact. We call for revised evaluation protocols and greater transparency to ensure benchmarks accurately measure true generalization. Code and data can be found in https://github.com/fzjcdt/RethinkingRobustBench.

Training recommendation models on large datasets is time- and resource-intensive. It is desired to construct concise yet informative datasets for efficient training. Recent advances in dataset condensation offer a promising solution by synthesizing compact datasets. However, existing methods face two key limitations when applied to recommendation: (1) they fail to generate discrete user-item interactions, and (2) they could not preserve users' potential preferences. To address the limitations, we propose a lightweight condensation framework tailored for recommendation (DConRec), focusing on condensing user-item historical interaction sets. Specifically, we model the discrete user-item interactions via a probabilistic approach and design a pre-augmentation module to incorporate the potential user preferences into the condensed datasets. While the substantial size of datasets leads to costly optimization, we propose a lightweight policy gradient estimation to accelerate the data synthesis. Experimental results on multiple real-world datasets demonstrate the effectiveness and efficiency of DConRec. Besides, we theoretically examine the provable convergence of DConRec.

Graph condensation has recently emerged as a prevalent technique to improve the training efficiency for graph neural networks (GNNs). It condenses a large graph into a small one such that a GNN trained on this small synthetic graph can achieve comparable performance to a GNN trained on the large graph. However, while existing graph condensation studies mainly focus on the best trade-off between graph size and the GNNs' performance (model utility), they overlook the security issues of graph condensation. To bridge this gap, we first explore backdoor attack against the GNNs trained on the condensed graphs. We introduce an effective backdoor attack against graph condensation, termed BGC. This attack aims to (1) preserve the condensed graph quality despite trigger injection, and (2) ensure trigger efficacy through the condensation process, achieving a high attack success rate. Specifically, BGC consistently updates triggers during condensation and targets representative nodes for poisoning. Extensive experiments demonstrate the effectiveness of our attack. BGC achieves a high attack success rate (close to 1.0) and good model utility in all cases. Furthermore, the results against multiple defense methods demonstrate BGC's resilience under their defenses. Finally, we analyze the key hyperparameters that influence the attack performance. Our code is available at: https://github.com/JiahaoWuGitIBGC.

Black-box optimization aims to find the optima through building a model close to the black-box objective function based on function value evaluation. However, in many real-world tasks, such as the design of molecular formulas and mechanical structures, it is perilous, costly, or even infeasible to evaluate the objective function value of an actively sampled solution. In this situation, optimization can only be conducted via utilizing offline historical data, which yields offline black-box optimization. Different from the traditional goal that is to pursue the optimal solution, this paper emphasizes that the goal of offline optimization is to stably surpass the offline dataset during optimization procedure. Although benchmarks called Design-Bench already exist in this emerging field, it can hardly evaluate the stability of offline optimization and mainly provides real-world offline tasks and the corresponding offline datasets. To this end, this paper proposes benchmarks named SOO-Bench (i.e., Stable Offline Optimization Benchmarks) for offline black-box optimization algorithms, so as to systematically evaluate the stability of surpassing the offline dataset under different data distributions. Along with SOO-Bench, we also propose a stability indicator to measure the degree of stability. Specifically, SOO-Bench includes various real-world offline optimization tasks and offline datasets under different data distributions, involving the fields of satellites, materials science, structural mechanics, and automobile manufacturing. Empirically, baseline and state-of-the-art algorithms are tested and analyzed on SOO-Bench. Hopefully, SOO-Bench is expected to serve as a catalyst for the rapid developments of more novel and stable offline optimization methods. The code is available at \url{https://github.com/zhuyiyi-123/SOO-Bench}.

Large language models (LLMs) have shown great potential as general-purpose AI assistants across various domains. To fully leverage this potential in specific applications, many companies provide fine-tuning API services, enabling users to upload their own data for LLM customization. However, fine-tuning services introduce a new safety threat: user-uploaded data, whether harmful or benign, can break the model’s alignment, leading to unsafe outputs. Moreover, existing defense methods struggle to address the diversity of fine-tuning datasets (e.g., varying sizes, tasks), often sacrificing utility for safety or vice versa. To address this issue, we propose Safe Delta, a safety-aware post-training defense method that adjusts the delta parameters (i.e., the parameter change before and after fine-tuning). Specifically, Safe Delta estimates the safety degradation, selects delta parameters to maximize utility while limiting overall safety loss, and applies a safety compensation vector to mitigate residual safety loss. Through extensive experiments on four diverse datasets with varying settings, our approach consistently preserves safety while ensuring that the utility gain from benign datasets remains unaffected.

Real-time solutions to the influence blocking maximization (IBM) problems are crucial for promptly containing the spread of misinformation. However, achieving this goal is nontrivial, mainly because assessing the blocked influence of an IBM problem solution typically requires plenty of expensive Monte Carlo simulations (MCSs). This work presents a novel approach that enables solving IBM problems with hundreds of thousands of nodes and edges in seconds. The key idea is to construct a fast-to-evaluate surrogate model called neural influence estimator (NIE) offline as a substitute for the time-intensive MCSs, and then combine it with optimization algorithms to address IBM problems online. To this end, a learning problem is formulated to build the NIE that takes the false-and-true information instance as input, extracts features describing the topology and interrelationship between two seed sets, and predicts the blocked influence. A well-trained NIE can generalize across different IBM problems given a social network, and can be readily combined with existing IBM optimization algorithms. The experiments on 25 IBM problems with up to millions of edges show that the NIE-based optimization method can be up to four orders of magnitude faster than MCSs-based optimization method to achieve the same optimization quality. Moreover, given a one-minute limit, the NIE-based method can solve IBM problems with up to hundreds of thousands of nodes, which is at least one order of magnitude larger than what can be solved by existing methods.

Multi-modal neural architecture search (MNAS) is an effective approach to obtain task-adaptive multi-modal classification models. Deep neural networks, as currently main-stream feature extractors, can provide hierarchical features for each modality. Existing MNAS methods face difficulty in exploiting such hierarchical features due to their different form coexistence such as tensorial multi-scale features and vectorized penultimate features. Moreover, existing methods always focus on the evolution of fusion operators or vectorized features of all modalities, constraining search space. In this paper, a novel two-stage method called multi-modal multi-scale evolutionary neural architecture search (MM-ENAS) is proposed. The first stage unifies the representation form of hierarchical features by the proposed evolutionary statistics strategy. The second stage identifies the optimal combination of basic fusion operations for all unified hierarchical features by the evolutionary algorithm. MM-ENAS increases search space by simultaneously searching for feature statistical extraction methods, basic fusion operators and feature representation set consisting of tensorial multi-scale features and vectorized penultimate features. Experimental results on three multi-modal tasks demonstrate that the proposed method achieves competitive performance in terms of accuracy, search time, and number of parameters compared to existing representative MNAS methods. Additionally, the method exhibits fast adaptation to various multi-modal tasks.

Evolutionary reinforcement learning (ERL), which integrates the evolutionary algorithms (EAs) and reinforcement learning (RL) for optimization, has demonstrated remarkable performance advancements. By fusing both the approaches, ERL has emerged as a promising research direction. This survey offers a comprehensive overview of the diverse research branches in ERL. Specifically, we systematically summarize the recent advancements in related algorithms and identify three primary research directions: 1) EA-assisted optimization of RL; 2) RL-assisted optimization of EA; and 3) synergistic optimization of EA and RL. Following that, we conduct an in-depth analysis of each research direction, organizing multiple research branches. We elucidate the problems that each branch aims to tackle and how the integration of EAs and RL addresses these challenges. In conclusion, we discuss potential challenges and prospective future research directions across various research directions. To facilitate researchers in delving into ERL, we organize the algorithms and codes involved onhttps://github.com/yeshenpy/Awesome-Evolutionary-Reinforcement-Learning.

Large-scale multiobjective optimization problems (LSMOPs), characterized by a substantial number of decision variables, pose significant challenges for many existing evolutionary algorithms. However, the search efficiency of these algorithms is not yet satisfactory. This is mainly because that the search efficiency of these algorithms may deteriorate dramatically since the search space increases exponentially with the number of decision variables. Having this in mind, we proposed a large-Scale multiobjective optimization framework named causal inference-based competitive swarm optimizer (CI-CSO). Specifically, a causal-information-(CI)-based operator is designed for competitive swarm optimizers. First, a causal inference technique named information geometric causal inference (IGCI) is introduced to adequately explore the CI between decision variables and fitness values. To further distinguish the positive or negative impacts of these critical variables on solution quality, a CI processing module is designed, facilitating targeted optimization. To enhance search efficiency, CI-based offspring generator are employed, leveraging the variance of causal effects to dynamically adjust the search step size and sampling range. To evaluate its performance, the proposed CI-based operator is embedded into two multiobjective evolutionary algorithms (MOEAs) (LSTPA and LMOCSO). To demonstrate the effectiveness of the proposed framework, experimental results are presented using the LSMOP test suite and five real-world problems, each involving up to 10 000 decision variables. In addition, six classic algorithms are included for comparison.

This paper proposes a surrogate-assisted evolutionary framework (called SELF) to solve expensive multitask optimization problems (ExMTOPs). SELF consists of two main phases: global knowledge transfer phase and local knowledge transfer phase. In the former, a multitask Gaussian process model (MTGP) is established by fusing previously evaluated solutions of multiple optimization tasks. MTGP can capture task-relevant information and the knowledge of landscapes. Then, differential evolution assisted with MTGP is proposed to preselect high-quality candidates. During the preselection, the knowledge of landscapes is transferred among multiple optimization tasks for locating promising regions quickly. In the latter, for each optimization task, Bayesian optimization is adopted to improve the quality of the best individual in the population. Moreover, the improved best individuals in the populations of multiple optimization tasks are adaptively transferred based on a transfer probability, which is computed through the task-relevant information provided by MTGP. By combining these two phases, SELF not only achieves the tradeoff between exploration and exploitation, but also utilizes the global and local knowledge transfer to improve the efficiency for solving ExMTOPs. We test SELF on seven benchmark test problems in the IEEE CEC2017 evolutionary multitask optimization competition. The results demonstrate that the performance of SELF is better than that of other seven advanced methods. In addition, we also apply SELF to deal with two real-world ExMTOPs. The designs provided by SELF exhibit the best performance among all the compared methods, verifying the potential of SELF in practical engineering applications.

To solve dynamic multiobjective optimization problems (DMOPs), the optimization algorithms are required to track the movement of the Pareto set after the environmental changes effectively. Many prediction-based dynamic multiobjective evolutionary algorithms (DMOEAs) have been proposed to address this challenge by utilizing environmental information for population reinitialization. However, when environmental changes are complex, irregular, and severe, the solutions and information during the evolution process often contain noise, making it difficult for prediction-based DMOEAs to accurately predict and reinitialize the population. To address this issue, we propose a novel dynamic multiobjective evolutionary algorithm (DM-DMOEA) which uses a diffusion model-based prediction strategy. In DM-DMOEA, to improve the prediction accuracy, the diffusion model is introduced to extract the relationships of high-quality solutions and reinitialize the population, and a PS estimation method is employed to integrate both historical and new environmental information, providing a set of high-quality solutions for diffusion model training. To speed up the response time, a variational autoencoder (VAE) is used to map the decision space to a latent space, which can reduce the diffusion model size and accelerate the diffusion process. To evaluate the effectiveness of the proposed DM-DMOEA on DMOPs, comprehensive experiments are conducted on several benchmarks and a practical problem. The results show that the DM-DMOEA outperforms other four state-of-the-art DMOEAs in most cases.

This paper proposes a new parameterless constraint-handling technique, named constrained probabilistic Pareto dominance (CPPD), for expensive constrained multiobjective optimization problems (CMOPs). In CPPD, when comparing two solutions, in terms of each original objective, we design a new objective for each solution, which is the negative product of two probabilities calculated based on the predicted fitness mean values and the uncertainty information provided by Kriging models: 1) the probability that this solution satisfies all constraints, denoted as PoF, and 2) the probability that this solution is better than the other on the original objective, denoted as PoB. It is evident that for each solution, PoF and PoB indicate its feasibility and its optimality on the corresponding original objective, respectively. Then, Pareto dominance based on new objectives is executed. As a result, both competitive feasible solutions and promising infeasible solutions with good diversity can be preserved by CPPD. These two kinds of solutions can help the population to exploit the located feasible parts and to explore new feasible parts, respectively. Further, based on CPPD, we develop a Pareto-based Kriging-assisted constrained multiobjective evolutionary algorithm (called PEA) to deal with expensive CMOPs with two or three objectives. Finally, PEA is generalized to solve expensive constrained many-objective optimization problems, named PEA+. The effectiveness of CPPD, PEA, and PEA+ is verified by comprehensive experiments.

Training recommendation models on large datasets requires significant time and resources. It is desired to construct concise yet informative datasets for efficient training. Recent advances in dataset condensation show promise in addressing this problem by synthesizing small datasets. However, applying existing methods of dataset condensation to recommendation has limitations: (1) they fail to generate discrete user-item interactions, and (2) they could not preserve users’ potential preferences. To address the limitations, we propose a lightweight condensation framework tailored for recommendation (DConRec), focusing on condensing user-item historical interaction sets. Specifically, we model the discrete user-item interactions via a probabilistic approach and design a pre-augmentation module to incorporate the potential preferences of users into the condensed datasets. While the substantial size of datasets leads to costly optimization, we propose a lightweight policy gradient estimation to accelerate the data synthesis. Experimental results on multiple real-world datasets have demonstrated the effectiveness and efficiency of our framework. Besides, we provide a theoretical analysis of the provable convergence of DConRec.

Node importance estimation (NIE) is the task of inferring the importance scores of the nodes in a graph. Due to the availability of richer data and knowledge, recent research interests of NIE have been dedicated to knowledge graphs (KGs) for predicting future or missing node importance scores. Existing state-of-the-art NIE methods train the model by available labels, and they consider every interested node equally before training. However, the nodes with higher importance often require or receive more attention in real-world scenarios, e.g., people may care more about the movies or webpages with higher importance. To this end, we introduce Label Informed ContrAstive Pretraining (LICAP) to the NIE problem for being better aware of the nodes with high importance scores. Specifically, LICAP is a novel type of contrastive learning (CL) framework that aims to fully utilize continuous labels to generate contrastive samples for pretraining embeddings. Considering the NIE problem, LICAP adopts a novel sampling strategy called top nodes preferred hierarchical sampling to first group all interested nodes into a top bin and a nontop bin based on node importance scores, and then divide the nodes within the top bin into several finer bins also based on the scores. The contrastive samples are generated from those bins and are then used to pretrain node embeddings of KGs via a newly proposed predicate-aware graph attention networks (PreGATs), so as to better separate the top nodes from nontop nodes, and distinguish the top nodes within the top bin by keeping the relative order among finer bins. Extensive experiments demonstrate that the LICAP pretrained embeddings can further boost the performance of existing NIE methods and achieve new state-of-the-art performance regarding both regression and ranking metrics. The source code for reproducibility is available at https://github.com/zhangtia16/LICAP.

Messenger RNA (mRNA) vaccines have emerged as highly effective strategies in the prophylaxis and treatment of diseases. mRNA design, a key to the success of mRNA vaccines, in-volves finding optimal codons and increasing secondary structure stability to lengthen mRNA half-life, ultimately enhancing protein expression. Despite receiving widespread attention, most methods primarily rely on manual design, which is time-consuming and labor-intensive. While optimization approaches can alleviate this issue, existing methods still exhibit critical limitations caused by conflicts between codon usage and mRNA structural stability, compounded by the vast design space of mRNA resulting from the presence of synonymous codons. In this paper, a novel multi-objective evolutionary optimization-based mRNA design method is proposed. We first formulate the mRNA design problem as a multi-objective optimization problem and then develop an Elite Archive-Assisted Multi-Objective Evolutionary algorithm for mRNA Design, namely EAA-MOED, by incorporating a novel elite archive-assisted method into a weighted optimization framework to improve search efficiency. Experimental studies, involving two state-of-the-art mRNA design methods and five well-known MOEAs, show the competitiveness of the proposed EAA-MOED in mRNA design.

Evolutionary algorithms (EAs) have achieved remarkable success in tackling complex combinatorial optimization problems. However, EAs often demand carefully-designed operators with the aid of domain expertise to achieve satisfactory performance. In this work, we present the first study on large language models (LLMs) as evolutionary combinatorial optimizers. The main advantage is that it requires minimal domain knowledge and human efforts, as well as no additional training of the model. This approach is referred to as LLM-driven EA (LMEA). Specifically, in each generation of the evolutionary search, LMEA instructs the LLM to select parent solutions from current population, and perform crossover and mutation to generate offspring solutions. Then, LMEA evaluates these new solutions and include them into the population for the next generation. LMEA is equipped with a self-adaptation mechanism that controls the temperature of the LLM. This enables it to balance between exploration and exploitation and prevents the search from getting stuck in local optima. We investigate the power of LMEA on the classical traveling salesman problems (TSPs) widely used in combinatorial optimization research. Notably, the results show that LMEA performs competitively to traditional heuristics in finding high-quality solutions on TSP instances with up to 20 nodes. Additionally, we also study the effectiveness of LLM-driven crossover/mutation and the self- adaptation mechanism in evolutionary search. In summary, our results reveal the great potentials of LLMs as evolutionary optimizers for solving combinatorial problems. We hope our research shall inspire future explorations on LLM-driven EAs for complex optimization challenges.

The multiple-choice knapsack problem (MCKP) is a classic NP-hard combinatorial optimization problem. Motivated by several significant real-world applications, this work investigates a novel variant of MCKP called the chance-constrained MCKP (CCMCKP), where item weights are random variables. In particular, we focus on the practical scenario of CCMCKP, in which the probability distributions of random weights are unknown and only sample data is available. We first present the problem formulation of CCMCKP and then establish the two benchmark sets. The first set contains synthetic instances, while the second set is designed to simulate a real-world application scenario of a telecommunication company. To solve CCMCKP, we propose a data-driven adaptive local search (DDALS) algorithm. Compared to existing stochastic optimization and distributionally robust optimization methods, the main novelty of DDALS lies in its data-driven solution evaluation approach, which does not make any assumptions about the underlying distributions and is highly effective even when faced with a high intensity of the chance constraint and a limited amount of sample data. Experimental results demonstrate the superiority of DDALS over the baselines on both the benchmarks. Finally, DDALS can serve as the baseline for future research, and the benchmark sets are open-sourced to further promote research on this challenging problem.

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.

Multi-task learning uses knowledge transfer among tasks to improve the generalization performance of all tasks. For deep multi-task learning, knowledge transfer is often implemented via sharing all hidden features of tasks. A major shortcoming is that it can lead to negative knowledge transfer across tasks when task correlation is weak. To overcome it, this paper proposes an evolutionary method to learn sparse sharing representations adaptively. By embedding the neural network optimization into evolutionary multitasking, our proposed method finds an optimal combination of tasks and sharing features. It can identify negative correlation and redundant features and then remove them from the hidden feature set. Thus, an optimal sparse sharing subnetwork can be produced for each task. Experiment results show that the proposed method achieve better learning performance with a smaller inference model than other related methods.

The field of adversarial textual attack has significantly grown over the past few years, where the commonly considered objective is to craft adversarial examples (AEs) that can successfully fool the target model. However, the imperceptibility of attacks, which is also essential for practical attackers, is often left out by previous studies. In consequence, the crafted AEs tend to have obvious structural and semantic differences from the original human-written text, making them easily perceptible. In this work, we advocate leveraging multi-objectivization to address such an issue. Specifically, we reformulate the problem of crafting AEs as a multi-objective optimization problem, where the attack imperceptibility is considered as an auxiliary objective. Then, we propose a simple yet effective evolutionary algorithm, dubbed HydraText, to solve this problem. HydraText can be effectively applied to both score-based and decision-based attack settings. Exhaustive experiments involving 44,237 instances demonstrate that HydraText consistently achieves competitive attack success rates and better attack imperceptibility than the recently proposed attack approaches. A human evaluation study also shows that the AEs crafted by HydraText are more indistinguishable from human-written text. Finally, these AEs exhibit good transferability and can bring notable robustness improvement to the target model by adversarial training.

A recurrent neural network (RNN) has shown powerful performance in tackling various natural language processing (NLP) tasks, resulting in numerous powerful models containing both RNN neurons and feedforward neurons. On the other hand, the deep structure of RNN has heavily restricted its implementation on mobile devices, where quite a few applications involve NLP tasks. Magnitude-based pruning (MP) is a promising way to address such a challenge. However, the existing MP methods are mostly designed for feedforward neural networks that do not involve a recurrent structure, and, thus, have performed less satisfactorily on pruning models containing RNN layers. In this article, a novel stage-wise MP method is proposed by explicitly taking the featured recurrent structure of RNN into account, which can effectively prune feedforward layers and RNN layers, simultaneously. The connections of neural networks are first grouped into three types according to how they are intersected with recurrent neurons. Then, an optimization-based pruning method is applied to compress each group of connections, respectively. Empirical studies show that the proposed method performs significantly better than the commonly used RNN pruning methods; i.e., up to 96.84% connections are pruned with little or even no degradation of precision indicators on the testing datasets.

The agile earth observation satellite scheduling problem (AEOSSP) with time-dependent transition times is a complex combinational optimization problem that has emerged from the development of large-scale satellite management techniques. To address this problem, we propose a deep reinforcement learning-based construction model (DRL-CM) that consists of five parts: 1) a Markov decision process (MDP); 2) a feature engineering; 3) a constructive heuristic neural network (CHNN); 4) an RL training method; and 5) an evaluation system. Specifically, the CHNN comprises six modules containing three special components that we propose: a dynamic encoder, a dynamic global layer, and a two-stage attention layer. First, we build the MDP of the AEOSSP and the feature engineering with effective features required for decision-making. Second, we design the CHNN to function as the MDP policy and train it with an RL model. Finally, we propose a comprehensive evaluation system for the validation of our model. The experimental results indicate that the proposed DRL-CM outperforms the state-of-the-art algorithm in terms of both optimization speed and quality. In addition, the feature engineering and network architecture built in our model are verified to be effective in comprehensive experiments.

This article devises a two-phase Kriging-assisted evolutionary algorithm (named TEA) to tackle expensive constrained multiobjective optimization problems (CMOPs). In the first phase, only objectives are considered, which can help the population to cross infeasible obstacles and to evolve toward the unconstrained Pareto front. Since the unconstrained Pareto front is in front of the feasible region in the objective space, the first phase can find some feasible solutions during the evolution. In the second phase, both objectives and constraints are considered. In this article, we also propose two transition conditions to judge whether the search should be switched from the first phase to the second phase, by making use of the candidates evaluated by the original objectives and constraints in the first phase. These two transition conditions aim at maintaining some high-quality feasible solutions when the first phase ends, which is able to motivate the population to converge toward the constrained Pareto front with good diversity in the second phase. Furthermore, in both phases, we design a new Pareto dominance relationship (called PDPD) by incorporating the probability distribution information derived from the Kriging models. PDPD is further generalized to handle constraints in expensive CMOPs, Constrained PDPD (CPDPD), which provides high credibility for the comparison between two individuals with respect to both objectives and constraints. Finally, three benchmark test suites and a real-world application confirm the superiority of TEA.

Attack Ensemble (AE), which combines multiple attacks together, provides a reliable way to evaluate adversarial robustness. In practice, AEs are often constructed and tuned by human experts, which however tends to be sub-optimal and time-consuming. In this work, we present AutoAE, a conceptually simple approach for automatically constructing AEs. In brief, AutoAE repeatedly adds the attack and its iteration steps to the ensemble that maximizes ensemble improvement per additional iteration consumed. We show theoretically that AutoAE yields AEs provably within a constant factor of the optimal for a given defense. We then use AutoAE to construct two AEs for l∞ and l2 attacks, and apply them without any tuning or adaptation to 45 top adversarial defenses on the RobustBench leaderboard. In all except one cases we achieve equal or better (often the latter) robustness evaluation than existing AEs, and notably, in 29 cases we achieve better robustness evaluation than the best known one. Such performance of AutoAE shows itself as a reliable evaluation protocol for adversarial robustness, which further indicates the huge potential of automatic AE construction. Code is available at https://github.com/LeegerPENG/AutoAE.

In multi-domain learning (MDL) scenarios, high labeling effort is required due to the complexity of collecting data from various domains. Active Learning (AL) presents an encouraging solution to this issue by annotating a smaller number of highly informative instances, thereby reducing the labeling effort. Previous research has relied on conventional AL strategies for MDL scenarios, which underutilize the domain-shared information of each instance during the selection procedure. To mitigate this issue, we propose a novel perturbation-based two-stage multi-domain active learning (P2S-MDAL) method incorporated into the well-regarded ASP-MTL model. Specifically, P2S-MDAL involves allocating budgets for domains and establishing regions for diversity selection, which are further used to select the most cross-domain influential samples in each region. A perturbation metric has been introduced to evaluate the robustness of the shared feature extractor of the model, facilitating the identification of potentially cross-domain influential samples. Experiments are conducted on three real-world datasets, encompassing both texts and images. The superior performance over conventional AL strategies shows the effectiveness of the proposed strategy. Additionally, an ablation study has been carried out to demonstrate the validity of each component. Finally, we outline several intriguing potential directions for future MDAL research, thus catalyzing the field's advancement.

Multi-domain learning (MDL) refers to simultaneously constructing a model or a set of models on datasets collected from different domains. Conventional approaches emphasize domain-shared information extraction and domain-private information preservation, following the shared-private framework (SP models), which offers significant advantages over single-domain learning. However, the limited availability of annotated data in each domain considerably hinders the effectiveness of conventional supervised MDL approaches in real-world applications. In this paper, we introduce a novel method called multi-domain contrastive learning (MDCL) to alleviate the impact of insufficient annotations by capturing both semantic and structural information from both labeled and unlabeled data. Specifically, MDCL comprises two modules: inter-domain semantic alignment and intra-domain contrast. The former aims to align annotated instances of the same semantic category from distinct domains within a shared hidden space, while the latter focuses on learning a cluster structure of unlabeled instances in a private hidden space for each domain. MDCL is readily compatible with many SP models, requiring no additional model parameters and allowing for end-to-end training. Experimental results across five textual and image multi-domain datasets demonstrate that MDCL brings noticeable improvement over various SP models. Furthermore, MDCL can further be employed in multi-domain active learning (MDAL) to achieve a superior initialization, eventually leading to better overall performance.

Multi-fidelity simulation is an effective approach to balancing speed and accuracy in expensive simulation, and its performance is affected by the quality of multi-fidelity simulation models. Building high-quality simulation models is non-trivial, especially for complex systems, because current manual modeling methods require sufficient domain knowledge and experience, increasing the labor and time costs. Motivated by the issues, this paper focuses on one of the most crucial simulation types, discrete event simulation, and develops a computer-aid multi-fidelity simulation modeling method called Optimization-based Multi-fidelity Simulation Modeling (OMFSM). OMFSM formulates multi-fidelity simulation modeling as a bi-objective simulation optimization problem to optimize speed and accuracy. An efficient optimization algorithm called Multi-objective Simulation Optimization based on Hypervolume (MOSO-HV) is tailored to select a set of high-quality models. Experimental results in a digital twin emergency department demonstrate that the computer-aid modeling method builds more and better multi-fidelity simulation models than manual modeling and reveal the effectiveness of MOSO-HV for OMFSM. The utility of OMFSM in multi-fidelity simulation is also justified by a real-world optimization problem. Note to Practitioners—Multi-fidelity simulation is an essential technique to fulfill the demand for accuracy analysis and quick decision-making in Industrial 4.0, such as digital twins and virtual reality. The quality of multi-fidelity simulation models significantly influences the performance of multi-fidelity simulation. Developers currently build multi-fidelity simulation models manually, and their experience determines the model’s quality. To reduce the labor and time costs in constructing high-quality multi-fidelity simulation models, we propose a computer-aid method named OMFSM from optimization for the first time. Experiments on a real case prove that OMFSM lightens the burden of manual modeling and provides more and better models for multi-fidelity simulation.

Cooperative coevolution (CC) is a paradigm equipped with the divide-and-conquer strategy for solving large-scale optimization problems (LSOPs). Currently, the computational resource allocation schemes of most CC could be divided into two categories, namely, equal allocation to all subproblems and preference allocation to the subproblems with a large contribution. However, the difficult subproblems are not carefully considered by the existing computational resource allocation schemes. For these subproblems, the investment of computational resources cannot quickly improve the fitness value, which leads to their small early contribution and being neglected. In this article, we comprehensively analyze the imbalanced nature of the subproblems from their difficulty and contribution in LSOPs. First, we propose a method to quantify the optimization difficulty of the problems during the evolution process, which considers both the difficulty of the fitness landscape and the behaviors of the optimization algorithm. Then, we propose a novel both difficulty and contribution-based CC framework, called DCCC, which encourages the allocation of the computational resources to more contributing and more difficult subproblems. DCCC is tested on the CEC’2010 and CEC’2013 large-scale optimization benchmarks, and is compared with several typical CC frameworks and state-of-the-art large-scale optimization algorithms. The experimental results demonstrate that DCCC is very competitive.

The geometric high-order regularization methods such as mean curvature and Gaussian curvature, have been intensively studied during the last decades due to their abilities in preserving geometric properties including image edges, corners, and contrast. However, the dilemma between restoration quality and computational efficiency is an essential roadblock for high-order methods. In this paper, we propose fast multi-grid algorithms for minimizing both mean curvature and Gaussian curvature energy functionals without sacrificing accuracy for efficiency. Unlike the existing approaches based on operator splitting and the Augmented Lagrangian method (ALM), no artificial parameters are introduced in our formulation, which guarantees the robustness of the proposed algorithm. Meanwhile, we adopt the domain decomposition method to promote parallel computing and use the fine-to-coarse structure to accelerate convergence. Numerical experiments are presented on image denoising, CT, and MRI reconstruction problems to demonstrate the superiority of our method in preserving geometric structures and fine details. The proposed method is also shown effective in dealing with large-scale image processing problems by recovering an image of size $1024\times 1024$ within 40s, while the ALM-based method requires around 200s.

Deep neural networks are vulnerable to adversarial examples, even in the black-box setting where the attacker is only accessible to the model output. Recent studies have devised effective black-box attacks with high query efficiency. However, such performance is often accompanied by compromises in attack imperceptibility, hindering the practical use of these approaches. In this article, we propose to restrict the perturbations to a small salient region to generate adversarial examples that can hardly be perceived. This approach is readily compatible with many existing black-box attacks and can significantly improve their imperceptibility with little degradation in attack success rates. Furthermore, we propose the Saliency Attack, a new black-box attack aiming to refine the perturbations in the salient region to achieve even better imperceptibility. Extensive experiments show that compared to the state-of-the-art black-box attacks, our approach achieves much better imperceptibility scores, including most apparent distortion (MAD), L 0 and L 2 distances, and also obtains significantly better true success rate and effective query number judged by a human-like threshold on MAD. Importantly, the perturbations generated by our approach are interpretable to some extent. Finally, it is also demonstrated to be robust to different detection-based defenses.

Social recommendations utilize social relations to enhance the representation learning for recommendations. Most social recommendation models unify user representations for the user-item interactions (collaborative domain) and social relations (social domain). However, such an approach may fail to model the users' heterogeneous behavior patterns in two domains, impairing the expressiveness of user representations. In this work, to address such limitation, we propose a novel Disentangled contrastive learning framework for social Recommendations (DcRec). More specifically, we propose to learn disentangled users' representations from the item and social domains. Moreover, disentangled contrastive learning is designed to perform knowledge transfer between disentangled users' representations for social recommendations. Comprehensive experiments on various real-world datasets demonstrate the superiority of our proposed model.

Dynamic Network Embedding (DNE) is attracting much attention due to the time-evolving nature of many real-world networks. The main objective of DNE is to efficiently update node embeddings while preserving network topology at each timestep. The idea of most existing DNE methods is to capture the topological changes at or around the most affected nodes (instead of all nodes) and accordingly update node embeddings. Unfortunately, this kind of approximation, although can improve efficiency, cannot effectively preserve the global topology of a dynamic network at each timestep, due to not considering the inactive sub-networks that receive accumulated topological changes propagated via the high-order proximity. To address this issue, we propose a new DNE method for better global topology preservation. Extensive experiments demonstrate the effectiveness and efficiency of the proposed method.

Hierarchical reinforcement learning (HRL) has been proven to be effective for tasks with sparse rewards, for it can improve the agent's exploration efficiency by discovering high-quality hierarchical structures (e.g., subgoals or options). However, automatically discovering high-quality hierarchical structures is still a great challenge. Previous HRL methods can only find the hierarchical structures in simple environments, as they are mainly achieved through the randomness of agent's policies during exploration. In complicated environments, such a randomness-driven exploration paradigm can hardly discover high-quality hierarchical structures because of the low exploration efficiency. In this paper, we propose CDHRL, a causality-driven hierarchical reinforcement learning framework, to build high-quality hierarchical structures efficiently in complicated environments. The key insight is that the causalities among environment variables are naturally fit for modeling reachable subgoals and their dependencies; thus, the causality is suitable to be the guidance in building high-quality hierarchical structures. Roughly, we build the hierarchy of subgoals based on causality autonomously, and utilize the subgoal-based policies to unfold further causality efficiently. Therefore, CDHRL leverages a causality-driven discovery instead of a randomness-driven exploration for high-quality hierarchical structure construction. The results in two complex environments, 2D-Minecraft and Eden, show that CDHRL can discover high-quality hierarchical structures and significantly enhance exploration efficiency.

Over the past few years, various word-level textual attack approaches have been proposed to reveal the vulnerability of deep neural networks used in natural language processing. Typically, these approaches involve an important optimization step to determine which substitute to be used for each word in the original input. However, current research on this step is still rather limited, from the perspectives of both problem-understanding and problem-solving. In this paper, we address these issues by uncovering the theoretical properties of the problem and proposing an efficient local search algorithm (LS) to solve it. We establish thefirstprovable approximation guarantee on solving the problem in general cases. Extensive experiments involving 5 NLP tasks, 8 datasets and 26 NLP models show that LS can largely reduce the number of queries usually by an order of magnitude to achieve high attack success rates. Further experiments show that the adversarial examples crafted by LS usually have higher quality, exhibit better transferability, and can bring more robustness improvement to victim models by adversarial training.

Since automatic algorithm configuration methods have been very effective, recently there is increasing research interest in utilizing them for automatic solver construction, resulting in several notable approaches. For these approaches, a basic assumption is that the given training set could sufficiently represent the target use cases such that the constructed solvers can generalize well. However, such an assumption does not always hold in practice since in some cases, we might only have scarce and biased training data. This article studies effective construction approaches for the parallel algorithm portfolios that are less affected in these cases. Unlike previous approaches, the proposed approach simultaneously considers instance generation and portfolio construction in an adversarial process, in which the aim of the former is to generate instances that are challenging for the current portfolio, while the aim of the latter is to find a new component solver for the portfolio to better solve the newly generated instances. Applied to two widely studied problem domains, that is, the Boolean satisfiability problems (SAT) and the traveling salesman problems (TSPs), the proposed approach identified parallel portfolios with much better generalization than the ones generated by the existing approaches when the training data were scarce and biased. Moreover, it was further demonstrated that the generated portfolios could even rival the state-of-the-art manually designed parallel solvers.

Constrained multiobjective optimization problems (CMOPs) involve both conflicting objective functions and various constraints. Due to the presence of constraints, CMOPs' Pareto-optimal solutions are very likely lying on constraint boundaries. The experience from the constrained single-objective optimization has shown that to quickly obtain such an optimal solution, the search should surround the boundary of the feasible region from both the feasible and infeasible sides. In this article, we extend this idea to cope with CMOPs and, accordingly, we propose a novel constrained multiobjective evolutionary algorithm with bidirectional coevolution, called BiCo. BiCo maintains two populations, that is: 1) the main population and 2) the archive population. To update the main population, the constraint-domination principle is equipped with an NSGA-II variant to move the population into the feasible region and then to guide the population toward the Pareto front (PF) from the feasible side of the search space. While for updating the archive population, a nondominated sorting procedure and an angle-based selection scheme are conducted in sequence to drive the population toward the PF within the infeasible region while maintaining good diversity. As a result, BiCo can get close to the PF from two complementary directions. In addition, to coordinate the interaction between the main and archive populations, in BiCo, a restricted mating selection mechanism is developed to choose appropriate mating parents. Comprehensive experiments have been conducted on three sets of CMOP benchmark functions and six real-world CMOPs. The experimental results suggest that BiCo can obtain quite competitive performance in comparison to eight state-of-the-art-constrained multiobjective evolutionary optimizers.

The gradient learning descent method is the main workhorse of training tasks in artificial intelligence and machine-learning research. Current theoretical studies of gradient descent only use the continuous domains, which is unreal since electronic computers use the float point numbers to store and deal with data. Although existing results are sufficient for the extremely tiny errors in high-precision machines, they need to be improved for low-precision cases. This article presents an understanding of the learning algorithm in computers with floats. The performances of three gradient descents with the floating domain are investigated when the objective function is smooth. When the function is assumed to have the PŁ condition, the convergence speed can be improved. We proved that for floating gradient descent to obtain an error with$\epsilon $, the iteration is$O(1/\epsilon)$for the general smooth case, and$O(\ln (1/\epsilon))$for the PŁ case. But$\epsilon $should be larger than the$s$-bit machine epsilon$\delta (s)$in the deterministic case, that is,$\epsilon \geq \Omega (\delta (s))$, while$\epsilon \geq \Omega (\sqrt {\delta (s)})$for the stochastic case. Floating stochastic and sign gradient descents can both output an$\epsilon $noised result in$O(1/\epsilon ^{2})$iterations.

Dynamic optimization, for which the objective functions change over time, has attracted intensive investigations due to the inherent uncertainty associated with many real-world problems. For its robustness with respect to noise, evolutionary algorithms (EAs) have been expected to have great potential for dynamic optimization. Many dynamic optimization methods, such as diversity-driven methods, memory methods, and prediction methods have been proposed based on EAs to deal with environmental changes. However, they face difficulties in adapting to fast changes in dynamic optimization as EAs normally need quite a few fitness evaluations to find a near-optimum solution. To address this issue, this article proposes a new framework of applying EAs in the context of dynamic optimization to deal with fast changing environments. We suggest that instead of online evolving (searching) solutions for the ever-changing objective function, EAs are more suitable for acquiring an archive of solutions in an offline way, which could be adopted to construct a system to provide high-quality solutions efficiently in a dynamic environment. To be specific, we formulate the offline search as a static set-oriented optimization problem. Then, a set of solutions is obtained by an EA for this set-oriented optimization problem. After this, the obtained solution set is adopted to do fast adaptation to the corresponding dynamic optimization problem. The general framework is instantiated for continuous dynamic-constrained optimization problems, and the empirical results show the potential of the proposed framework. The superiority of the framework is also verified on a dynamic vehicle routing problem with changing demands.

The Vehicle Routing Problem (VRP) is a well-known NP-hard combinatorial optimization problem, which has wide spread applications in real world, such as logistics, bus route planning, and urban path planning. To solve VRP, traditional optimization methods usually start the search from scratch and ignore the VRPs solved in the past, which could lead to repeated explorations of the search space of related problems, and thus results in slow optimization process involving unnecessary computational cost. Keeping this in mind, to speed up the optimization for vehicle routing, this article presents a new study towards faster vehicle routing by transferring knowledge from customer representations which are learned from past solved VRPs. In particular, we propose to capture the useful traits buried in previous optimized routing solutions by learning a new customer representation, which can be transferred across VRPs, serving as the prior knowledge, to bias the optimization in the target VRP. In contrast to existing approaches, the proposed knowledge transfer is consist of a learning of new customer representation based on the optimized routing solution, which is general to VRPs possessing different structural properties, and a weighted$l_{1}$norm-regularized formulation for building sparse mapping across VRPs, that is easy to solve. Further, the proposed knowledge transfer across VRPs occurs along the whole optimization search process, and is thus able to guide the routing optimization process consistently. To verify the efficacy of the proposed method, by using population-based optimization method as the VRP solver, comprehensive empirical studies on both commonly used VRP benchmarks and real world vehicle routing application are presented.

Airspace complexity is a critical metric in current Air Traffic Management systems for indicating the security degree of airspace operations. Airspace complexity can be affected by many coupling factors in a complicated and nonlinear way, making it extremely difficult to be evaluated. In recent years, machine learning has been proved as a promising approach and achieved significant results in evaluating airspace complexity. However, existing machine learning based approaches require a large number of airspace operational data labeled by experts. Due to the high cost in labeling the operational data and the dynamical nature of the airspace operating environment, such data are often limited and may not be suitable for the changing airspace situation. In light of these, we propose a novel unsupervised learning approach for airspace complexity evaluation based on a deep neural network trained by unlabeled samples. We introduce a new loss function to better address the characteristics pertaining to airspace complexity data, including dimension coupling, category imbalance, and overlapped boundaries. Due to these characteristics, the generalization ability of existing unsupervised models is adversely impacted. The proposed approach is validated through extensive experiments based on the real-world data of six sectors in Southwestern China airspace. Experimental results show that our deep unsupervised model outperforms the state-of-the-art methods in terms of airspace complexity evaluation accuracy.

Learning low-dimensional topological representation of a network in dynamic environments is attracting much attention due to the time-evolving nature of many real-world networks. The main and common objective of Dynamic Network Embedding (DNE) is to efficiently update node embeddings while preserving network topology at each time step. The idea of most existing DNE methods is to capture the topological changes at or around the most affected nodes (instead of all nodes) and accordingly update node embeddings. Unfortunately, this kind of approximation, although can improve efficiency, cannot effectively preserve the global topology of a dynamic network at each time step, due to not considering the inactive sub-networks that receive accumulated topological changes propagated via the high-order proximity. To tackle this challenge, we propose a novel node selecting strategy to diversely select the representative nodes over a network, which is coordinated with a new incremental learning paradigm of Skip-Gram based embedding approach. The extensive experiments show GloDyNE, with a small fraction of nodes being selected, can already achieve the superior or comparable performance w.r.t. the state-of-the-art DNE methods in three typical downstream tasks. Particularly, GloDyNE significantly outperforms other methods in the graph reconstruction task, which demonstrates its ability of global topology preservation.

Optimization problems with costly function evaluation widely exist in real-world applications. Surrogate models are commonly used in the field of optimization to deal with such expensive optimization problems. In surrogate model-assisted evolutionary algorithms (EAs), surrogate models like regression models, ranking models or classification models are built based on historical data and then used to compare candidate solutions in place of real function evaluations. Researchers have also proposed various methods to make better use of surrogate models in the optimization process of EAs. However, there is no comprehensive study about how much accuracy of the built model is accurate enough to bring benefits to the optimization. Motivated by this, this work proposes a method to study the performance effect of model accuracy on surrogate model-assisted EAs. Specifically, the method does not really build surrogate models but assumes different model accuracies in individual selection. Two classification-assisted EAs, classification-assisted differential evolution (CADE) and relationship classification-based preselection strategy (RCPS) are analyzed in this work. The experimental results on a set of test functions show that a weak learner with classification accuracy larger than 50% is acceptable ignoring the cost of model building. Another observation is that the performances of CADE and RCPS increase monotonically and nonlinearly with the classification accuracy.

Dynamic Network Embedding (DNE) has recently drawn much attention due to the dynamic nature of many real-world networks. Comparing to a static network, a dynamic network has a unique character called the degree of changes, which can be defined as the average number of the changed edges between consecutive snapshots spanning a dynamic network. The degree of changes could be quite different even for the dynamic networks generated from the same dataset. It is natural to ask whether existing DNE methods are effective and robust w.r.t. the degree of changes. Towards robust DNE, we suggest two important scenarios. One is to investigate the robustness w.r.t. different slicing settings that are used to generate different dynamic networks with different degree of changes, while another focuses more on the robustness w.r.t. different number of changed edges over timesteps.

Abstract Effective exploration is key to a successful search process. The recently proposed negatively correlated search (NCS) tries to achieve this by coordinated parallel exploration, where a set of search processes are driven to be negatively correlated so that different promising areas of the search space can be visited simultaneously. Despite successful applications of NCS, the negatively correlated search behaviors were mostly devised by intuition, while deeper (e.g., mathematical) understanding is missing. In this paper, a more principled NCS, namely NCNES, is presented, showing that the parallel exploration is equivalent to a process of seeking probabilistic models that both lead to solutions of high quality and are distant from previous obtained probabilistic models. Reinforcement learning, for which exploration is of particular importance, are considered for empirical assessment. The proposed NCNES is applied to directly train a deep convolution network with 1.7 million connection weights for playing Atari games. Empirical results show that the significant advantages of NCNES, especially on games with uncertain and delayed rewards, can be highly owed to the effective parallel exploration ability.

Stochastic gradient descent (SGD) has become the method of choice to tackle large-scale datasets due to its low computational cost and good practical performance. Learning rate analysis, either capacity-independent or capacity-dependent, provides a unifying viewpoint to study the computational and statistical properties of SGD, as well as the implicit regularization by tuning the number of passes. Existing capacity-independent learning rates require a nontrivial bounded subgradient assumption and a smoothness assumption to be optimal. Furthermore, existing capacity-dependent learning rates are only established for the specific least squares loss with a special structure. In this paper, we provide both optimal capacity-independent and capacity-dependent learning rates for SGD with general convex loss functions. Our results require neither bounded subgradient assumptions nor smoothness assumptions, and are stated with high probability. We achieve this improvement by a refined estimate on the norm of SGD iterates based on a careful martingale analysis and concentration inequalities on empirical processes.

Stochastic gradient descent (SGD) has become the method of choice for training highly complex and nonconvex models since it can not only recover good solutions to minimize training errors but also generalize well. Computational and statistical properties are separately studied to understand the behavior of SGD in the literature. However, there is a lacking study to jointly consider the computational and statistical properties in a nonconvex learning setting. In this paper, we develop novel learning rates of SGD for nonconvex learning by presenting high-probability bounds for both computational and statistical errors. We show that the complexity of SGD iterates grows in a controllable manner with respect to the iteration number, which sheds insights on how an implicit regularization can be achieved by tuning the number of passes to balance the computational and statistical errors. As a byproduct, we also slightly refine the existing studies on the uniform convergence of gradients by showing its connection to Rademacher chaos complexities.

Recently, evolutionary multitasking (EMT) has been proposed in the field of evolutionary computation as a new search paradigm, for solving multiple optimization tasks simultaneously. By sharing useful traits found along the evolutionary search process across different optimization tasks, the optimization performance on each task could be enhanced. The autoencoding-based EMT is a recently proposed EMT algorithm. In contrast to most existing EMT algorithms, which conduct knowledge transfer across tasks implicitly via crossover, it intends to perform knowledge transfer explicitly among tasks in the form of task solutions, which enables the employment of task-specific search mechanisms for different optimization tasks in EMT. However, the autoencoding-based explicit EMT can only work on continuous optimization problems. It will fail on combinatorial optimization problems, which widely exist in real-world applications, such as scheduling problem, routing problem, and assignment problem. To the best of our knowledge, there is no existing effort working on explicit EMT for combinatorial optimization problems. Taking this cue, in this article, we thus embark on a study toward explicit EMT for combinatorial optimization. In particular, by using vehicle routing as an illustrative combinatorial optimization problem, the proposed explicit EMT algorithm (EEMTA) mainly contains a weighted l1-norm-regularized learning process for capturing the transfer mapping, and a solution-based knowledge transfer process across vehicle routing problems (VRPs). To evaluate the efficacy of the proposed EEMTA, comprehensive empirical studies have been conducted with the commonly used vehicle routing benchmarks in multitasking environment, against both the state-of-the-art EMT algorithm and the traditional single-task evolutionary solvers. Finally, a real-world combinatorial optimization application, that is, the package delivery problem (PDP), is also presented to further confirm the efficacy of the proposed algorithm.

Minimum cost seed selection for competitive influence maximization, which selects a set of key users (called seed set) to spread its influence widely into the network at a minimum cost in a competitive social network, is a key algorithmic problem in social influence analysis. Due to its application potential in multiple fields, such as market expansion, election campaigns, and cultural competition, numerous studies have been emerging recently. Despite these efforts, this problem has not been satisfactorily solved since not only finding a (nearly) optimal solution for cost minimization but also evaluating a seed set is computationally complex. Existing works either trade approximation guarantees for practical efficiency using heuristics, or vice versa due to costly Monte Carlo simulations. In this article, a competitive reverse influence estimation-based greedy (CRIEG) algorithm, which provides bounded approximation guarantees, but offers significantly improved empirical efficiency under the competitive independent cascade model, is proposed. The core of the algorithm is a novel estimation method that improves the efficiency by constructing representative sketches to avoid heavy repeated simulations without compromising its performance guarantees. The experimental results on eight real-world networks with up to 1.13 million users show that compared with state-of-the-art algorithms, our algorithm is the most efficient while keeping the best performance, and can be orders of magnitude faster.

Generalization, i.e., the ability of solving problem instances that are not available during the system design and development phase, is a critical goal for intelligent systems. A typical way to achieve good generalization is to learn a model from vast data. In the context of heuristic search, such a paradigm could be implemented as configuring the parameters of a parallel algorithm portfolio (PAP) based on a set of “training” problem instances, which is often referred to as PAP construction. However, compared to the traditional machine learning, PAP construction often suffers from the lack of training instances, and the obtained PAPs may fail to generalize well. This article proposes a novel competitive co-evolution scheme, named co-evolution of parameterized search (CEPS), as a remedy to this challenge. By co-evolving a configuration population and an instance population, CEPS is capable of obtaining generalizable PAPs with few training instances. The advantage of CEPS in improving generalization is analytically shown in this article. Two concrete algorithms, namely, CEPS-TSP and CEPS-VRPSPDTW, are presented for the traveling salesman problem (TSP) and the vehicle routing problem with simultaneous pickup-delivery and time windows (VRPSPDTW), respectively. The experimental results show that CEPS has led to better generalization, and even managed to find new best-known solutions for some instances.

Some signal processing and multimedia applications can be specified by synchronous dataflow (SDF) models. The problem of SDF mapping to a given set of heterogeneous processors has been known to be NP-hard and widely studied in the design automation field. However, modern embedded applications are becoming increasingly complex with dynamic behaviors changes over time. As a significant extension to the SDF, the multi-mode dataflow (MMDF) model has been proposed to specify such an application with a finite number of behaviors (or modes) and each behavior (mode) is represented by an SDF graph. The multiprocessor mapping of an MMDF is far more challenging as the design space increases with the number of modes. Instead of using traditional genetic algorithm (GA)-based design space exploration (DSE) method that encodes the design space as a whole, this article proposes a novel cooperative co-evolutionary genetic algorithm (CCGA)-based framework to efficiently explore the design space by a new problem-specific decomposition strategy in which the solutions of node mapping for each individual mode are assigned to an individual population. Besides, a problem-specific local search operator is introduced as a supplement to the global search of CCGA for further improving the search efficiency of the whole framework. Furthermore, a fitness approximation method and a hybrid fitness evaluation strategy are applied for reducing the time consumption of fitness evaluation significantly. The experimental studies demonstrate the advantage of the proposed DSE method over the previous GA-based method. The proposed method can obtain an optimization result with 2×−3× better quality using less (1/2−1/3) optimization time.

Over the last decade, research on automated parameter tuning, often referred to as automatic algorithm configuration (AAC), has made significant progress. Although the usefulness of such tools has been widely recognized in real world applications, the theoretical foundations of AAC are still very weak. This paper addresses this gap by studying the performance estimation problem in AAC. More specifically, this paper first proves the universal best performance estimator in a practical setting, and then establishes theoretical bounds on the estimation error, i.e., the difference between the training performance and the true performance for a parameter configuration, considering finite and infinite configuration spaces respectively. These findings were verified in extensive experiments conducted on four algorithm configuration scenarios involving different problem domains. Moreover, insights for enhancing existing AAC methods are also identified.

MOTIVATION: Inferring gene regulatory networks from gene expression time series data is important for gaining insights into the complex processes of cell life. A popular approach is to infer Boolean networks. However, it is still a pressing open problem to infer accurate Boolean networks from experimental data that are typically short and noisy. RESULTS: To address the problem, we propose a Boolean network inference algorithm which is able to infer accurate Boolean network topology and dynamics from short and noisy time series data. The main idea is that, for each target gene, we use an And/Or tree ensemble algorithm to select prime implicants of which each is a conjunction of a set of input genes. The selected prime implicants are important features for predicting the states of the target gene. Using these important features we then infer the Boolean function of the target gene. Finally, the Boolean functions of all target genes are combined as a Boolean network. Using the data generated from artificial and real-world gene regulatory networks, we show that our algorithm can infer more accurate Boolean network topology and dynamics from short and noisy time series data than other algorithms. Our algorithm enables us to gain better insights into complex regulatory mechanisms of cell life. AVAILABILITY AND IMPLEMENTATION: Package ATEN is freely available at https://github.com/ningshi/ATEN. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Network resource allocation is an important issue for designing energy-harvesting wireless sensor networks (EH-WSNs). This article considers the capacity assignment problem in EH-WSNs with the interference channel for fixed data and energy flow topologies. We focus on the optimal data rates, power allocations, and energy transfers, minimizing the total network delay for the network. We first consider a simplified model where the data flow is fixed on each data link and optimizes transmit power at each sensor node for a single energy harvest in a time slot. However, the optimization problem is nonconvex, making it difficult to find the optimal solution. Unlike the most traditional methods that approximate the original optimization problem as a convex optimization problem by considering the relatively high signal-to-interference-plus-noise ratio (SINR), this article aims to directly solve the original nonconvex formulation by employing a powerful evolutionary algorithm, i.e., negatively correlated search (NCS). Then, we investigate the joint optimization problem of capacity and flow for the entire EH-WSNs, and develop a novel multiobjective NCS algorithm (MOEA/D-NCS) to deal with the complicated nonlinear constraints and optimize the data rates, power allocations, and energy transfer simultaneously, so as to minimize the total network delay. The numerical results demonstrate that solving the nonconvex problem with approximated approach is a good alternative for solving the approximated convex problem with accurate optimization approaches; the joint optimization of capacity and flow is a good solution for EH-WSNs; and the scheme of partial transmission for data flow is an advantage in respect of decreasing the network delay. The solution of this article could also be beneficial to other complex optimization problems in the wireless network design.

As one of the classical problems in the economic market, the newsvendor problem aims to make maximal profit by determining the optimal order quantity of products. However, the previous newsvendor models assume that the selling price of a product is a predefined constant and only regard the order quantity as a decision variable, which may result in an unreasonable investment decision. In this article, a new newsvendor model is first proposed, which involves of both order quantity and selling price as decision variables. In this way, the newsvendor problem is reformulated as a mixed-variable nonlinear programming problem, rather than an integer linear programming problem as in previous investigations. In order to solve the mixed-variable newsvendor problem, a histogram model-based estimation of distribution algorithm (EDA) called EDAmvnis developed, in which an adaptive-width histogram model is used to deal with the continuous variables and a learning-based histogram model is applied to deal with the discrete variables. The performance of EDAmvn was assessed on a test suite with eight representative instances generated by the orthogonal experiment design method and a real-world instance generated from real market data of Alibaba. The experimental results show that, EDAmvnoutperforms not only the state-of-the-art mixed-variable evolutionary algorithms, but also a commercial software, i.e., Lingo.

Stochastic gradient descent (SGD) is a popular and efficient method with wide applications in training deep neural nets and other nonconvex models. While the behavior of SGD is well understood in the convex learning setting, the existing theoretical results for SGD applied to nonconvex objective functions are far from mature. For example, existing results require to impose a nontrivial assumption on the uniform boundedness of gradients for all iterates encountered in the learning process, which is hard to verify in practical implementations. In this article, we establish a rigorous theoretical foundation for SGD in nonconvex learning by showing that this boundedness assumption can be removed without affecting convergence rates, and relaxing the standard smoothness assumption to Hölder continuity of gradients. In particular, we establish sufficient conditions for almost sure convergence as well as optimal convergence rates for SGD applied to both general nonconvex and gradient-dominated objective functions. A linear convergence is further derived in the case with zero variances.

Dimensionality reduction is often employed to deal with the data with a huge number of features, which can be generally divided into two categories: feature transformation and feature selection. Due to the interpretability, the efficiency during inference and the abundance of unlabeled data, unsupervised feature selection has attracted much attention. In this paper, we consider its natural formulation, column subset selection (CSS), which is to minimize the reconstruction error of a data matrix by selecting a subset of features. We propose an anytime randomized iterative approach POCSS, which minimizes the reconstruction error and the number of selected features simultaneously. Its approximation guarantee is well bounded. Empirical results exhibit the superior performance of POCSS over the state-of-the-art algorithms.

Exploiting parallelism is becoming more and more important in designing efficient solvers for computationally hard problems. However, manually building parallel solvers typically requires considerable domain knowledge and plenty of human effort. As an alternative, automatic construction of parallel portfolios (ACPP) aims at automatically building effective parallel portfolios based on a given problem instance set and a given rich configuration space. One promising way to solve the ACPP problem is to explicitly group the instances into different subsets and promote a component solver to handle each of them. This paper investigates solving ACPP from this perspective, and especially studies how to obtain a good instance grouping. The experimental results on two widely studied problem domains, the boolean satisfiability problems (SAT) and the traveling salesman problems (TSP), showed that the parallel portfolios constructed by the proposed method could achieve consistently superior performances to the ones constructed by the state-of-the-art ACPP methods, and could even rival sophisticated hand-designed parallel solvers.

Cooperative Co-evolution (CC) is a promising framework to scale up conventional evolutionary algorithms for large scale global optimization (LSGO) problems. However, how to group decision variables is still a problem while there is no prior knowledge about the dependence relationship between variables. In this paper, a new kind of CC algorithm called Soft Grouping Cooperative Co-evolution (SGCC) is proposed to tackle the problem. Instead of explicitly dividing variables into multiple groups, the algorithm softly assigns variables into multiple groups by controlling the degree of membership of variables to the groups. In this work, the degree of membership is controlled by a probability distribution function. The experimental investigation shows that Soft Grouping CC is better than the explicit grouping CC on partially separable and non-separable problems.

Optimal energy-delay scheduling for capacity assignment problem in energy harvesting wireless sensor networks (EH-WSNs) with interference channel is addressed for fixed data flows and energy topologies. We formulate the optimization problem for a single time slot and multiple time slots, respectively. We focus on the optimal data rates, power allocations and energy transfers for the optimization problem. The objective is to minimize the total network delay. However, the optimization problem is non-convex, making it difficult to find the optimal solution. Unlike the most traditional methods that approximate the original optimization problem as a convex optimization problem by considering the relatively high Signal-to-Interference-plus-Noise Ratio (SINR), this paper aims to directly solve the original non-convex formulation by employing a powerful evolutionary algorithm, i.e., Negatively Correlated Search (NCS). The simulations under both no-energy-transfer scenario and energy-transfer scenario are carried out, demonstrating that solving the non-convex problem with approximated approach is a good alternative to solving the approximated convex problem with accurate optimization approaches. This idea could also be beneficial to other complex optimization problems in the wireless networks design.

Stochastic composite mirror descent (SCMD) is a simple and efficient method able to capture both geometric and composite structures of optimization problems in machine learning. Existing strategies require to take either an average or a random selection of iterates to achieve optimal convergence rates, which, however, can either destroy the sparsity of solutions or slow down the practical training speed. In this paper, we propose a theoretically sound strategy to select an individual iterate of the vanilla SCMD, which is able to achieve optimal rates for both convex and strongly convex problems in a non-smooth learning setting. This strategy of outputting an individual iterate can preserve the sparsity of solutions which is crucial for a proper interpretation in sparse learning problems. We report experimental comparisons with several baseline methods to show the effectiveness of our method in achieving a fast training speed as well as in outputting sparse solutions.

Efficient exploration is crucial to achieving good performance in reinforcement learning. Existing systematic exploration strategies (R-MAX, MBIE, UCRL, etc.), despite being promising theoretically, are essentially greedy strategies that follow some predefined heuristics. When the heuristics do not match the dynamics of Markov decision processes (MDPs) well, an excessive amount of time can be wasted in travelling through already-explored states, lowering the overall efficiency. We argue that explicit planning for exploration can help alleviate such a problem, and propose a Value Iteration for Exploration Cost (VIEC) algorithm which computes the optimal exploration scheme by solving an augmented MDP. We then present a detailed analysis of the exploration behaviour of some popular strategies, showing how these strategies can fail and spend O(n^2 md) or O(n^2 m + nmd) steps to collect sufficient data in some tower-shaped MDPs, while the optimal exploration scheme, which can be obtained by VIEC, only needs O(nmd), where n, m are the numbers of states and actions and d is the data demand. The analysis not only points out the weakness of existing heuristic-based strategies, but also suggests a remarkable potential in explicit planning for exploration.

The performance of many nature-inspired optimization algorithms (NIOAs) depends strongly on their implemented coordinate system. However, the commonly used coordinate system is fixed and not well suited for different function landscapes, NIOAs thus might not search efficiently. To overcome this shortcoming, in this paper we propose a framework, named ACoS, to adaptively tune the coordinate systems in NIOAs. In ACoS, an Eigen coordinate system is established by making use of the cumulative population distribution information, which can be obtained based on a covariance matrix adaptation strategy and an additional archiving mechanism. Since the population distribution information can reflect the features of the function landscape to some extent, NIOAs in the Eigen coordinate system have the capability to identify the modality of the function landscape. In addition, the Eigen coordinate system is coupled with the original coordinate system, and they are selected according to a probability vector. The probability vector aims to determine the selection ratio of each coordinate system for each individual, and is adaptively updated based on the collected information from the offspring. ACoS has been applied to two of the most popular paradigms of NIOAs, i.e., particle swarm optimization and differential evolution, for solving 30 test functions with 30D and 50D at the 2014 IEEE Congress on Evolutionary Computation. The experimental studies demonstrate its effectiveness.

The performance of traditional multiobjective evolutionary algorithms (MOEAs) often deteriorates rapidly as the number of decision variables increases. While some efforts were made to design new algorithms by adapting existing techniques to large-scale single-objective optimization to the MOEA context, the specific difficulties that may arise from large-scale multiobjective optimization have rarely been studied. In this paper, the exclusive challenges along with the increase of the number of variables of a multiobjective optimization problem (MOP) are examined empirically, and the popular benchmarks are categorized into three groups accordingly. Problems in the first category only require MOEAs to have stronger convergence, and can thus be mitigated using techniques employed in large-scale single-objective optimization. Problems that require MOEAs to have stronger diversification but ignore a correlation between position and distance functions are grouped as the second. The rest of the problems that pose a great challenge to the balance between diversification and convergence by considering a correlation between position and distance functions are grouped as the third. While existing large-scale MOEAs perform well on the problems in the first two categories, they suffer a significant loss when applied to those in the third category. To solve large-scale MOPs in this category, we have developed a novel indicator-based algorithm with an enhanced diversification mechanism. The proposed algorithm incorporates a new solution generator with an external archive, thus forcing the search toward different subregions of the Pareto front using a dual local search mechanism. The results obtained by applying the proposed algorithm to a wide variety of problems (108 instances in total) with up to 8192 variables demonstrate that it outperforms eight state-of-the-art approaches on the examined problems in the third category and show its advantage in the balance between diversification and convergence.

The first cooperative co-evolutionary algorithm (CCEA) was proposed by Potter and De Jong in 1994 and since then many CCEAs have been proposed and successfully applied to solving various complex optimization problems. In applying CCEAs, the complex optimization problem is decomposed into multiple subproblems, and each subproblem is solved with a separate subpopulation, evolved by an individual evolutionary algorithm (EA). Through cooperative co-evolution of multiple EA subpopulations, a complete problem solution is acquired by assembling the representative members from each subpopulation. The underlying divide-and-conquer and collaboration mechanisms enable CCEAs to tackle complex optimization problems efficiently, and hence CCEAs have been attracting wide attention in the EA community. This paper presents a comprehensive survey of these CCEAs, covering problem decomposition, collaborator selection, individual fitness evaluation, subproblem resource allocation, implementations, benchmark test problems, control parameters, theoretical analyses, and applications. The unsolved challenges and potential directions for their solutions are discussed.

Service composition is a key enabling technology in service-oriented computing for developing versatile applications by integrating various existing interoperable services. Although actively studied, most existing works on service composition neglect the existence of complementarity among candidate services within a service class, so-called internal complementarity. In fact, complementary candidate services within a service class can be composed to form a composite candidate service which may yield better service utility than that provided by any existing candidate service within that service class. This work focuses on web service composition where internal complementarity is more likely to happen. Specifically, we aim at addressing the problem of QoS-aware web service selection with internal complementarity (WSS-IC). We first transform this problem into a multi-choice multi-dimensional knapsack problem (MMKP) and prove such a transformation per se has non-polynomial time complexity in the worse case.Then, we perform complexity analysis to demonstrate that existing approaches to MMKPs are not computationally feasible to resolve QoS-aware WSS-IC. This fact motivates us to propose an iteratively improving framework for deriving the solution iteration by iteration while taking into account both solution structure and QoS constraints. At each iteration, the current solution gets improved by solving a disjunctively constrained knapsack problem. To verify the effectiveness of the proposed framework, two heuristic approaches are implemented under this framework. Experimental results demonstrate that our approaches outperform the compared methods in terms of both solution quality and computation time.

This paper considers the multiset selection problem with size constraints, which arises in many real-world applications such as budget allocation. Previous studies required the objective function f to be submodular, while we relax this assumption by introducing the notion of the submodularity ratios (denoted by α_f and β_f). We propose an anytime randomized iterative approach POMS, which maximizes the given objective f and minimizes the multiset size simultaneously. We prove that POMS using a reasonable time achieves an approximation guarantee of max{1-1/e^(β_f), (α_f/2)(1-1/e^(α_f))}. Particularly, when f is submdoular, this bound is at least as good as that of the previous greedy-style algorithms. In addition, we give lower bounds on the submodularity ratio for the objectives of budget allocation. Experimental results on budget allocation as well as a more complex application, namely, generalized influence maximization, exhibit the superior performance of the proposed approach.

In noisy evolutionary optimization, sampling is a common strategy to deal with noise, which evaluates the fitness of a solution multiple times (called sample size) independently and then uses the average to approximate the true fitness. Previous studies mainly focused on the empirical design of efficient sampling strategies, and the few theoretical analyses mainly proved the effectiveness of sampling with a fixed sample size in some situations. There are many fundamental theoretical issues to be addressed. In this paper, we first investigate the effect of sample size. By analyzing the (1+1)-EA on noisy LeadingOnes, we show that as the sample size increases, the running time can reduce from exponential to polynomial, but then return to exponential. This discloses that a proper sample size is crucial in practice. Then, we investigate what other strategies can work when sampling with any fixed sample size fails. By two illustrative examples, we prove that using parent populations can be better, and if using parent populations is also ineffective, adaptive sampling (i.e., sampling with an adaptive sample size) can work.

Evolutionary algorithms (EAs) have been widely applied to solve multi-objective optimization problems. In contrast to great practical successes, their theoretical foundations are much less developed, even for the essential theoretical aspect, i.e., running time analysis. In this paper, we propose a general approach to estimating upper bounds on the expected running time of multi-objective EAs (MOEAs), and then apply it to diverse situations, including bi-objective and many-objective optimization as well as exact and approximate analysis. For some known asymptotic bounds, our analysis not only provides their leading constants, but also improves them asymptotically. Moreover, our results provide some theoretical justification for the good empirical performance of MOEAs in solving multi-objective combinatorial problems.

Deep neural networks (DNNs) have achieved great success, but the applications to mobile devices are limited due to their huge model size and low inference speed. Much effort thus has been devoted to pruning DNNs. Layer-wise neuron pruning methods have shown their effectiveness, which minimize the reconstruction error of linear response with a limited number of neurons in each single layer pruning. In this paper, we propose a new layer-wise neuron pruning approach by minimizing the reconstruction error of nonlinear units, which might be more reasonable since the error before and after activation can change significantly. An iterative optimization procedure combining greedy selection with gradient decent is proposed for single layer pruning. Experimental results on benchmark DNN models show the superiority of the proposed approach. Particularly, for VGGNet, the proposed approach can compress its disk space by 13.6× and bring a speedup of 3.7×; for AlexNet, it can achieve a compression rate of 4.1× and a speedup of 2.2×, respectively.

Pairwise learning refers to learning tasks with the associated loss functions depending on pairs of examples. Recently, pairwise learning has received increasing attention since it covers many machine learning schemes, e.g., metric learning, ranking and AUC maximization, in a unified framework. In this paper, we establish a unified generalization error bound for regularized pairwise learning without either Bernstein conditions or capacity assumptions. We apply this general result to typical learning tasks including distance metric learning and ranking, for each of which our discussion is able to improve the state-of-the-art results.

Layer-wise magnitude-based pruning (LMP) is a very popular method for deep neural network (DNN) compression. However, tuning the layer-specific thresholds is a difficult task, since the space of threshold candidates is exponentially large and the evaluation is very expensive. Previous methods are mainly by hand and require expertise. In this paper, we propose an automatic tuning approach based on optimization, named OLMP. The idea is to transform the threshold tuning problem into a constrained optimization problem (i.e., minimizing the size of the pruned model subject to a constraint on the accuracy loss), and then use powerful derivative-free optimization algorithms to solve it. To compress a trained DNN, OLMP is conducted within a new iterative pruning and adjusting pipeline. Empirical results show that OLMP can achieve the best pruning ratio on LeNet-style models (i.e., 114 times for LeNet-300-100 and 298 times for LeNet-5) compared with some state-of-the- art DNN pruning methods, and can reduce the size of an AlexNet-style network up to 82 times without accuracy loss.

Subset selection is a fundamental problem in many areas, which aims to select the best subset of size at most $k$ from a universe. Greedy algorithms are widely used for subset selection, and have shown good approximation performances in deterministic situations. However, their behaviors are stochastic in many realistic situations (e.g., large-scale and noisy). For general stochastic greedy algorithms, bounded approximation guarantees were obtained only for subset selection with monotone submodular objective functions, while real-world applications often involve non-monotone or non-submodular objective functions and can be subject to a more general constraint than a size constraint. This work proves their approximation guarantees in these cases, and thus largely extends the applicability of stochastic greedy algorithms.

The problem of selecting a sequence of items from a universe that maximizes some given objective function arises in many real-world applications. In this paper, we propose an anytime randomized iterative approach POSeqSel, which maximizes the given objective function and minimizes the sequence length simultaneously. We prove that for any previously studied objective function, POSeqSel using a reasonable time can always reach or improve the best known approximation guarantee. Empirical results exhibit the superior performance of POSeqSel.

The subset selection problem that selects a few items from a ground set arises in many applications such as maximum coverage, influence maximization, sparse regression, etc. The recently proposed POSS algorithm is a powerful approximation solver for this problem. However, POSS requires centralized access to the full ground set, and thus is impractical for large-scale real-world applications, where the ground set is too large to be stored on one single machine. In this paper, we propose a distributed version of POSS (DPOSS) with a bounded approximation guarantee. DPOSS can be easily implemented in the MapReduce framework. Our extensive experiments using Spark, on various real-world data sets with size ranging from thousands to millions, show that DPOSS can achieve competitive performance compared with the centralized POSS, and is almost always better than the state-of-the-art distributed greedy algorithm RandGreeDi.

We study stochastic composite mirror descent, a class of scalable algorithms able to exploit the geometry and composite structure of a problem. We consider both convex and strongly convex objectives with non-smooth loss functions, for each of which we establish high-probability convergence rates optimal up to a logarithmic factor. We apply the derived computational error bounds to study the generalization performance of multi-pass stochastic gradient descent (SGD) in a non-parametric setting. Our high-probability generalization bounds enjoy a logarithmical dependency on the number of passes provided that the step size sequence is square-summable, which improves the existing bounds in expectation with a polynomial dependency and therefore gives a strong justification on the ability of multi-pass SGD to overcome overfitting. Our analysis removes boundedness assumptions on subgradients often imposed in the literature. Numerical results are reported to support our theoretical findings.

In real-world optimization tasks, the objective (i.e., fitness) function evaluation is often disturbed by noise due to a wide range of uncertainties. Evolutionary algorithms are often employed in noisy optimization, where reducing the negative effect of noise is a crucial issue. Sampling is a popular strategy for dealing with noise: to estimate the fitness of a solution, it evaluates the fitness multiple ([Formula: see text]) times independently and then uses the sample average to approximate the true fitness. Obviously, sampling can make the fitness estimation closer to the true value, but also increases the estimation cost. Previous studies mainly focused on empirical analysis and design of efficient sampling strategies, while the impact of sampling is unclear from a theoretical viewpoint. In this article, we show that sampling can speed up noisy evolutionary optimization exponentially via rigorous running time analysis. For the (1[Formula: see text]1)-EA solving the OneMax and the LeadingOnes problems under prior (e.g., one-bit) or posterior (e.g., additive Gaussian) noise, we prove that, under a high noise level, the running time can be reduced from exponential to polynomial by sampling. The analysis also shows that a gap of one on the value of [Formula: see text] for sampling can lead to an exponential difference on the expected running time, cautioning for a careful selection of [Formula: see text]. We further prove by using two illustrative examples that sampling can be more effective for noise handling than parent populations and threshold selection, two strategies that have shown to be robust to noise. Finally, we also show that sampling can be ineffective when noise does not bring a negative impact.

As a well-known engineering practice, concurrent engineering (CE) considers all elements involved in a product's life cycle from the early stages of product development, and emphasizes executing all design tasks simultaneously. As a result, there exist various complex design problems in CE, which usually have many design parameters or require different disciplinary knowledge to solve them. To address these problems and enable concurrent design, different methods have been developed. The original problem is usually divided into small subproblems so that each subproblem can be solved individually and simultaneously. However, good decomposition, optimization, and communication strategies among subproblems are still needed in the field of CE. This paper attempts to study and analyze cooperative co-evolution (CC) based design optimization in CE by employing a parallel CC framework. Furthermore, it aims to develop new concurrent design methods based on parallel CC to solve different kinds of CE problems. To achieve this goal, a new novelty-driven CC is developed for design problems with complex structures and a novel concurrent design method is presented for quasi-separable multidisciplinary design optimization (MDO) problems. The efficacy of the new methods is studied on universal electric motor design problems and a general MDO problem, and compared to that of some existing methods. Additionally, this paper studies how the communication frequency among subpopulations affects the performance of the proposed methods. The optimal communication frequencies under different communication costs are reported as experimental results for both proposed methods on the test problems. Based on this paper, an effective self-adaptive method is proposed to be used in both optimization schemes, which is able to adapt the communication frequency during the optimization process.

The problem of maximizing monotonek-submodular functions under a size constraint arises in many applications, and it is NP-hard. In this paper, we propose a new approach which employs a multiobjective evolutionary algorithm to maximize the given objective and minimize the size simultaneously. For general cases, we prove that the proposed method can obtain the asymptotically tight approximation guarantee, which was also achieved by the greedy algorithm. Moreover, we further give instances where the proposed approach performs better than the greedy algorithm on applications of influence maximization, information coverage maximization, and sensor placement. Experimental results on real-world data sets exhibit the superior performance of the proposed approach.

Divide-and-conquer (DC) is conceptually well suited to deal with high-dimensional optimization problems by decomposing the original problem into multiple low-dimensional subproblems, and tackling them separately. Nevertheless, the dimensionality mismatch between the original problem and subproblems makes it nontrivial to precisely assess the quality of a candidate solution to a subproblem, which has been a major hurdle for applying the idea of DC to nonseparable high-dimensional optimization problems. In this paper, we suggest that searching a good solution to a subproblem can be viewed as a computationally expensive problem and can be addressed with the aid of meta-models. As a result, a novel approach, namely self-evaluation evolution (SEE) is proposed. Empirical studies have shown the advantages of SEE over four representative compared algorithms increase with the problem size on the CEC2010 large scale global optimization benchmark. The weakness of SEE is also analyzed in the empirical studies.

Incremental learning with concept drift has often been tackled by ensemble methods, where models built in the past can be retrained to attain new models for the current data. Two design questions need to be addressed in developing ensemble methods for incremental learning with concept drift, i.e., which historical (i.e., previously trained) models should be preserved and how to utilize them. A novel ensemble learning method, namely, Diversity and Transfer-based Ensemble Learning (DTEL), is proposed in this paper. Given newly arrived data, DTEL uses each preserved historical model as an initial model and further trains it with the new data via transfer learning. Furthermore, DTEL preserves a diverse set of historical models, rather than a set of historical models that are merely accurate in terms of classification accuracy. Empirical studies on 15 synthetic data streams and 5 real-world data streams (all with concept drifts) demonstrate that DTEL can handle concept drift more effectively than 4 other state-of-the-art methods.

Previous running time analyses of evolutionary algorithms (EAs) in noisy environments often studied the one-bit noise model, which flips a randomly chosen bit of a solution before evaluation. In this paper, we study a natural extension of one-bit noise, the bit-wise noise model, which independently flips each bit of a solution with some probability. We analyze the running time of the (1+1)-EA solving OneMax and LeadingOnes under bit-wise noise for the first time, and derive the ranges of the noise level for polynomial and super-polynomial running time bounds. The analysis on LeadingOnes under bit-wise noise can be easily transferred to one-bit noise, and improves the previously known results.

This paper considers the subset selection problem with a monotone objective function and a monotone cost constraint, which relaxes the submodular property of previous studies. We first show that the approximation ratio of the generalized greedy algorithm is $\frac{\alpha}{2}(1 \textendash \frac{1}{e^{\alpha}})$ (where $\alpha$ is the submodularity ratio); and then propose POMC, an anytime randomized iterative approach that can utilize more time to find better solutions than the generalized greedy algorithm. We show that POMC can obtain the same general approximation guarantee as the generalized greedy algorithm, but can achieve better solutions in cases and applications.

This paper considers the problem of minimizing the ratio of two set functions, i.e., $f/g$. Previous work assumed monotone and submodular of the two functions, while we consider a more general situation where $g$ is not necessarily submodular. We derive that the greedy approach GreedRatio, as a fixed time algorithm, achieves a $\frac{|X^*|}{(1+(|X^*| \textendash 1)(1 \textendash \kappa_f))\gamma(g)}$ approximation ratio, which also improves the previous bound for submodular $g$. If more time can be spent, we present the PORM algorithm, an anytime randomized iterative approach minimizing $f$ and $\textendash g$ simultaneously. We show that PORM using reasonable time has the same general approximation guarantee as GreedRatio, but can achieve better solutions in cases and applications.

The problem of selecting the best $k$-element subset from a universe is involved in many applications. While previous studies assumed a noise-free environment or a noisy monotone submodular objective function, this paper considers a more realistic and general situation where the evaluation of a subset is a noisy monotone function (not necessarily submodular), with both multiplicative and additive noises. To understand the impact of the noise, we firstly show the approximation ratio of the greedy algorithm and POSS, two powerful algorithms for noise-free subset selection, in the noisy environments. We then propose to incorporate a noise-aware strategy into POSS, resulting in the new PONSS algorithm. We prove that PONSS can achieve a better approximation ratio under some assumption such as i.i.d. noise distribution. The empirical results on influence maximization and sparse regression problems show the superior performance of PONSS.

Under/overestimation of state/action values are harmful for reinforcement learning agents. In this paper, we show that a state/action value estimated using the Bellman equation can be decomposed to a weighted sum of path-wise values that follow log-normal distributions. Since log-normal distributions are skewed, the distribution of estimated state/action values can also be skewed, leading to an imbalanced likelihood of under/overestimation. The degree of such imbalance can vary greatly among actions and policies within a single problem instance, making the agent prone to select actions/policies that have inferior expected return and higher likelihood of overestimation. We present a comprehensive analysis to such skewness, examine its factors and impacts through both theoretical and empirical results, and discuss the possible ways to reduce its undesirable effects.

The capacitated arc routing problem (CARP) is a challenging optimization problem with lots of applications in the real world. Numerous approaches have been proposed to tackle this problem. Most of these methods, albeit showing good performance on CARP instances of small and median sizes, do not scale well to large-scale CARPs, e.g., taking at least a few hours to achieve a satisfactory solution on a CARP instance with thousands of tasks. In this paper, an efficient and scalable approach is proposed for CARPs. The key idea of the proposed approach is to hierarchically decompose the tasks involved in a CARP instance into subgroups and solve the induced subproblems recursively. The output of the subproblems at the lower layer in the hierarchy is treated as virtual tasks and new subproblems are formulated based on these virtual tasks using clustering techniques. By this means, the number of tasks (or virtual tasks) decreases rapidly from the bottom to the top layers of the hierarchy, and the sizes of all subproblems at each layer can be kept tractable even for very large-scale CARPs. Empirical studies are conducted on CARP instances with up to 3584 tasks, which are an order of magnitude larger than the number of tasks involved in all CARP instances investigated in the literature. The results show that the proposed approach significantly outperforms existing methods in terms of scalability. Since the proposed hierarchical decomposition scheme is designed to obtain a good permutation of tasks in a CARP instance, it may also be generalized to other hard optimization problems that can be formulated as permutation-based optimization problems.

Air traffic flow management (ATFM) aims to facilitate the utilization of airspace and airport resources and is critical in air transportation systems. During the past decades, several challenging problems have arisen from this domain and attracted intensive studies. This paper addresses the problem of alleviating the airspace congestion and reducing the flight delays in ATFM simultaneously. We formulate this problem as a multi-objective air traffic network flow optimization (MATNFO) problem. In this MATNFO model, comprehensive ATFM actions, for instance, ground-holding, airborne-holding, rerouting, and speed control, are considered. Meanwhile, a systematic approach, namely route and time-slot assignment (RTA) algorithm, is developed to solve the MATNFO problem. The idea of divide-and-conquer is embedded in the algorithm by sequentially applying both route searching module and time refinement module. Furthermore, for the sake of efficiency, a pre-selection operator is proposed as one heuristic strategy to identify promising solutions and reduce the search space by defining a sector equilibrium metric. Experiments on real data of the Chinese airspace show that the RTA algorithm outperforms an existing competitor and three related multi-objective evolutionary algorithms. In addition, RTA is competent for high-quality real-time air traffic network flow assignment.

In real-world applications, the oracle who can label all instances correctly may not exist or may be too expensive to acquire. Alternatively, crowdsourcing provides an easy way to get labels at a low cost from multiple non-expert annotators. During the past few years, much attention has been paid to learning from such crowdsourcing data, namelyLearning from Crowds(LFC). Despite their proper statistical foundations, the existing methods for LFC still suffer from several disadvantages, such as needing prior knowledge to select the expertise model to represent the behavior of annotators, involving non-convex optimization problems, or restricting the classifier type being used. This paper addresses LFC from a quality-sensitive perspective and presents a novel framework named QS-LFC. Through reformulating the original LFC problem as a quality-sensitive learning problem, the above-mentioned disadvantages of existing methods can be avoided. Further, a support vector machine (SVM) implementation of QS-LFC is proposed. Experimental results on both synthetic and real-world data sets demonstrate that QS-LFC can achieve better generalization performance and is more robust to the noisy labels, than the existing methods.

With the explosively increase of information and products, recommender systems have played a more and more important role in the recent years. Various recommendation algorithms, such as content-based methods and collaborative filtering methods, have been proposed. There are a number of performance metrics for evaluating recommender systems, and considering only the precision or diversity might be inappropriate. However, to the best of our knowledge, no existing work has considered recommendation with many objectives. In this paper, we model a many-objective search-based recommender system and adopt a recently proposed many-objective evolutionary algorithm to optimize it. Experimental results on the Movielens data set demonstrate that our algorithm performs better in terms of Generational Distance (GD), Inverted Generational Distance (IGD) and Hypervolume (HV) on most test cases.

In the past few years, Evolutionary Algorithms (EAs) based UAV path planners have drawn increasing research interests. However, they are not scalable to large-scale problems, i.e., lots of waypoints. Recently, we have proposed a novel EA-based framework, named Separately Evolving Waypoints (SEW), that can deal with large-scale problems. However, the difficulty of UAV path planning depends not only on the number of waypoints, but on the number of constraints it has to satisfy, especially the number of obstacles. In particular, the number of waypoints required is also partly determined by the number of constraints. Hence, it is critical to further improve SEW with respect to large number of obstacles. Originally, a state-of-the-art global optimization approach is employed. In this work, we discuss how the increasing number of obstacles will deteriorate the performance of the global optimizer, then we propose multimodal optimization approaches that facilitates the performance of SEW against large number of obstacles.

Learning from crowds, which the labels of the instances are collected through crowdsourcing ways, has become an important research topic recently. Personal Classifier (PC) approach is a representative approach for learning from crowds due to its convex optimization formulation. PC approach makes assumptions about parameters' distribution, thus it is a parametric approach. However, these assumptions may not always hold, especially for real-world data sets. In this paper, we propose a new non-parametric approach, called NP approach, for learning from crowds. NP approach has a convex optimization formulation but without assumptions about parameters' distribution. In addition, NP approach can be generalized to the non-linear case directly, while the PC approach does not. Experimental studies show that NP approach outperforms other two compared approaches.

Object detection from still images has been among the most active and challenging area in computer vision recently. In contrast, fully supervised object detection from video has rarely been investigated. In this paper, we propose an algorithm to improve the performance of object detection from video. Our proposed method is based on an empirical property that the trajectory of an object is important for detection in videos. We use object trajectory to filter outliers, determine probable location of object and correct detection errors. We compare our method with baseline method which regard video frames as still images directly. Experiments show that our method outperform the compared baseline in terms of average precision while inducing moderate computation overhead.

Evolutionary algorithms (EAs) have been shown to be powerful tools for complex optimization problems, which are ubiquitous in both communication and big data analytics. This paper presents a new EA, namely negatively correlated search (NCS), which maintains multiple individual search processes in parallel and models the search behaviors of individual search processes as probability distributions. NCS explicitly promotes negatively correlated search behaviors by encouraging differences among the probability distributions (search behaviors). By this means, individual search processes share information and cooperate with each other to search diverse regions of a search space, which makes NCS a promising method for nonconvex optimization. The co-operation scheme of NCS could also be regarded as a novel diversity preservation scheme that, different from other existing schemes, directly promotes diversity at the level of search behaviors rather than merely trying to maintain diversity among candidate solutions. Empirical studies showed that NCS is competitive to well-established search methods in the sense that NCS achieved the best overall performance on 20 multimodal (nonconvex) continuous optimization problems. The advantages of NCS over state-of-the-art approaches are also demonstrated with a case study on the synthesis of unequally spaced linear antenna arrays.

Module identification or community detection in complex networks has become increasingly important in many scientific fields because it provides insight into the relationship and interaction between network function and topology. In recent years, module identification algorithms based on stochastic optimization algorithms such as evolutionary algorithms have been demonstrated to be superior to other algorithms on small- to medium-scale networks. However, the scalability and resolution limit (RL) problems of these module identification algorithms have not been fully addressed, which impeded their application to real-world networks. This paper proposes a novel module identification algorithm called cooperative co-evolutionary module identification to address these two problems. The proposed algorithm employs a cooperative co-evolutionary framework to handle large-scale networks. We also incorporate a recursive partitioning scheme into the algorithm to effectively address the RL problem. The performance of our algorithm is evaluated on 12 benchmark complex networks. As a medical application, we apply our algorithm to identify disease modules that differentiate low- and high-grade glioma tumors to gain insights into the molecular mechanisms that underpin the progression of glioma. Experimental results show that the proposed algorithm has a very competitive performance compared with other state-of-the-art module identification algorithms.

Traditional multiobjective evolutionary algorithms face a great challenge when dealing with many objectives. This is due to a high proportion of nondominated solutions in the population and low selection pressure toward the Pareto front. In order to tackle this issue, a series of indicator-based algorithms have been proposed to guide the search process toward the Pareto front. However, a single indicator might be biased and lead the population to converge to a subregion of the Pareto front. In this paper, a multi-indicator-based algorithm is proposed for many-objective optimization problems. The proposed algorithm, namely stochastic ranking-based multi-indicator Algorithm (SRA), adopts the stochastic ranking technique to balance the search biases of different indicators. Empirical studies on a large number (39 in total) of problem instances from two well-defined benchmark sets with 5, 10, and 15 objectives demonstrate that SRA performs well in terms of inverted generational distance and hypervolume metrics when compared with state-of-the-art algorithms. Empirical studies also reveal that, in the case a problem requires the algorithm to have strong convergence ability, the performance of SRA can be further improved by incorporating a direction-based archive to store well-converged solutions and maintain diversity.

The uncertain capacitated arc routing problem is a challenging problem in which the demands of tasks, the costs of edges, and the presence of tasks and edges are uncertain. The objective of this problem is to find a robust optimal solution for a finite set of possible scenarios. In this paper, we propose a novel robust optimization approach, called an estimation of distribution algorithm (EDA) with stochastic local search (SLS), to tackle this problem. The proposed method integrates an EDA with a novel two phase SLS procedure to minimize the maximal total cost over a set of different scenarios. The SLS procedure avoids excessive fitness evaluations of unpromising moves in local search. Our experimental results on two sets of benchmark problems (a total of 55 problem instances) showed that the proposed approach outperformed existing state-of-the-art algorithms.

Class evolution, the phenomenon of class emergence and disappearance, is an important research topic for data stream mining. All previous studies implicitly regard class evolution as a transient change, which is not true for many real-world problems. This paper concerns the scenario where classes emerge or disappear gradually. A class-based ensemble approach, namely Class-Based ensemble for Class Evolution (CBCE), is proposed. By maintaining a base learner for each class and dynamically updating the base learners with new data, CBCE can rapidly adjust to class evolution. A novel under-sampling method for the base learners is also proposed to handle the dynamic class-imbalance problem caused by the gradual evolution of classes. Empirical studies demonstrate the effectiveness of CBCE in various class evolution scenarios in comparison to existing class evolution adaptation methods.

Many real-world problems often have several, usually conflicting objectives. Traditional multi-objective optimization problems (MOPs) usually search for the Pareto-optimal solutions for this predicament. A special class of MOPs, the convex hull maximization problems which prefer solutions on the convex hull, has posed a new challenge for existing approaches for solving traditional MOPs, as a solution on the Pareto front is not necessarily a good solution for convex hull maximization. In this work, the difference between traditional MOPs and the convex hull maximization problems is discussed and a new Evolutionary Convex Hull Maximization Algorithm (ECHMA) is proposed to solve the convex hull maximization problems. Specifically, a Convex Hull-based sorting with Convex Hull of Individual Minima (CH-CHIM-sorting) is introduced, as well as a novel selection scheme, Extreme Area Extract-based selection (EAE-selection). Experimental results show that ECHMA significantly outperforms the existing approaches for convex hull maximization and evolutionary multi-objective optimization approaches in achieving a better approximation to the convex hull more stably and with a more uniformly distributed set of solutions.

Differential evolution (DE) is a powerful population-based stochastic optimization algorithm. Although its efficacy has been witnessed in various applications, the performance of DE is usually challenged when the computational budget is decreased and/or the search landscape's complexity is increased. To address these issues, we propose a new local ensemble surrogate assisted crowding DE (LES-CDE) algorithm, which consists of multiple local surrogate models built upon the historical search information accumulated in diverse overlapped local regions of the search space. In LES-CDE, an ensemble of several adjacent local surrogates is utilized to guide the creation of promising trial vectors. To maintain the local nature of each surrogate model, LES-CDE uses the replacement scheme of crowding DE (CDE) to update the population which also serves as model landmarks. We test LES-CDE under varying parameters and compare them with CDE on 15 numerical test problems taken from CEC 2015 single-objective real-parameter optimization testbed. Results from our experiments demonstrate the superiority of LES-CDE over CDE in a statistically significant manner.

Cloud service composition problem (CSCP) is usually long-term based in practice. A logical request is to maximize end users' long-term benefit. Thus, the overall long-term QoS properties of the composite service should be optimized and the users' requirements during the period should be satisfied. However, the benefit-maximization has not been considered under the background of long-term based CSCP in existing research yet. To fill this gap, in this paper, a new formulation LCSCP is proposed to define the long-term based CSCP as an optimization problem. Then, for the sake of efficiency, three meta-heuristic approaches (i.e, Genetic Algorithm, Simulated Annealing and Tabu Search) are studied. Comprehensive experiments are designed and conducted to test their various aspects of performance on different test sets with different workflows. Experimental results provide a basic perspective of how these three widely adopted meta-heuristic frameworks work on this new problem, which can be baseline work for further research.

Ordinal regression has a wide range of applications, while it is intractable to be solved when lacking sufficient labeled data. In this paper, we propose an evolutionary semi-supervised kernel Fisher discriminant approach for ordinal regression. The proposed algorithm obtains the projection and thresholds by incorporating the unlabeled data with a weighting scheme, where the weights indicate the degrees of contributions to the class distribution by different training instances. The projection maps the original data to a one-dimensional space, and the thresholds are used for the prediction. The weights are computed with a label propagation method first. However, it is not always accurate. In order to further tune the weights to be more accurate, the differential evolution algorithm is applied here in this work. By a delicate weight update rule, the weights can be evolved indirectly. This tuning scheme makes the size of evolutionary individual just associated with the number of ranks rather than the number of instances. The experimental studies demonstrate that our algorithm can effectively use unlabeled data and yield satisfactory learning performance.

In this paper, a novel multiple sub-models maintenance technique, named maintaining and processing sub-models (MAPS), is proposed. MAPS aims to enhance the ability of estimation of distribution algorithms (EDAs) on multimodal problems. The advantages of MAPS over the existing multiple sub-models based EDAs stem from the explicit detection of the promising areas, which can save many function evaluations for exploration and thus accelerate the optimization speed. MAPS can be combined with any EDA that adopts a single Gaussian model. The performance of MAPS has been assessed through empirical studies where MAPS is integrated with three different types of EDAs. The experimental results show that MAPS can lead to much faster convergence speed and obtain more stable solutions than the compared algorithms on 12 benchmark problems.

The focus of most research in evolutionary dynamic optimization has been tracking moving optimum (TMO). Yet, TMO does not capture all the characteristics of real-world dynamic optimization problems (DOPs), especially in situations where a solution's future fitness has to be considered. To account for a solution's future fitness explicitly, we propose to find robust solutions to DOPs, which are formulated as the robust optimization over time (ROOT) problem. In this paper we analyze two robustness definitions in ROOT and then develop two types of benchmark problems for the two robustness definitions in ROOT, respectively. The two types of benchmark problems are motivated by the inappropriateness of existing DOP benchmarks for the study of ROOT. Additionally, we evaluate four representative methods from the literature on our proposed ROOT benchmarks, in order to gain a better understanding of ROOT problems and their relationship to more popular TMO problems. The experimental results are analyzed, which show the strengths and weaknesses of different methods in solving ROOT problems with different dynamics. In particular, the real challenges of ROOT problems have been revealed for the first time by the experimental results on our proposed ROOT benchmarks.

Evolutionary algorithms integrating various niching techniques have been widely used to find multiple optima of an optimization problem. In recent years, an increasing amount of research has been focused on the design and application of speciation-based niching techniques. These techniques rely on speciation to partition a population into subpopulations (species) such that each occupies a different region of attraction (niche) on the fitness landscape. Existing speciation methods are either distance-based or topology-based. Topology-based methods are more flexible and have fewer assumptions than distance-based methods. However, existing topology-based methods all require sampling and evaluating new individuals in order to capture the landscape topography. This incurs additional fitness evaluations (FEs), which is a drawback, especially when the FE budget is limited. In this paper, a new topology-based speciation method named history-based topological speciation (HTS) is proposed. It relies exclusively on search history to capture the landscape topography and, therefore, does not require any additional FEs to be performed. To the best of our knowledge, HTS is the only parameter-free speciation method at the moment. Both theoretical and empirical analyses have been conducted. Theoretical analysis shows that HTS incurs acceptable computational overhead. In the experimental study, HTS outperformed existing topology-based methods on benchmark functions in up to 32-D space and with as many as 50 optima, and the time overhead was practically negligible if a single FE took seconds.

The receiver operating characteristic (ROC) is commonly used to analyze the performance of classifiers in data mining. An important topic in ROC analysis is the ROC convex hull (ROCCH), which is the least convex majorant (LCM) of the empirical ROC curve and covers potential optima for a given set of classifiers. ROCCH maximization problems have been taken as multiobjective optimization problem (MOPs) in some previous work. However, the special characteristics of ROCCH maximization problem makes it different from traditional MOPs. In this paper, the difference will be discussed in detail and a new convex hull-based multiobjective genetic programming (CH-MOGP) is proposed to solve ROCCH maximization problems. Specifically, convex hull-based without redundancy sorting (CWR-sorting) is introduced, which is an indicator-based selection scheme that aims to maximize the area under the convex hull. A novel selection procedure is also proposed based on the proposed sorting scheme. It is hypothesized that by using a tailored indicator-based selection, CH-MOGP becomes more efficient for ROC convex hull approximation than algorithms that compute all Pareto optimal points. Empirical studies are conducted to compare CH-MOGP to both existing machine learning approaches and multiobjective genetic programming (MOGP) methods with classical selection schemes. Experimental results show that CH-MOGP outperforms the other approaches significantly.

Hyperspectral image classification is a challenging problem. Among existing approaches to addressing this problem, the active learning (AL) and semisupervised learning (SSL) techniques have attracted much attention in recent years. AL usually involves a labor-intensive human-labeling process while SSL, although avoiding human labeling by assigning pseudolabels to unlabeled data, may introduce incorrect pseudolabels and thus deteriorate classification performance. To overcome these drawbacks, a novel approach named collaborative active and semisupervised learning (CASSL) is proposed in this paper. CASSL combines AL and SSL to invoke a collaborative labeling process by both human experts and classifiers. Specifically, an AL-based pseudolabel verification procedure is performed for gradually improving the pseudolabeling accuracy to facilitate SSL. Meanwhile, only those unlabeled data with low pseudolabeling confidence in SSL will become the query candidates in AL. We evaluate the performance of CASSL on three hyperspectral data sets and compare it with that of two state-of-the-art hyperspectral image classification methods. Experimental results reveal the superiority of CASSL.

Software defect prediction can help to allocate testing resources efficiently through ranking software modules according to their defects. Existing software defect prediction models that are optimized to predict explicitly the number of defects in a software module might fail to give an accurate order because it is very difficult to predict the exact number of defects in a software module due to noisy data. This paper introduces a learning-to-rank approach to construct software defect prediction models by directly optimizing the ranking performance. In this paper, we build on our previous work, and further study whether the idea of directly optimizing the model performance measure can benefit software defect prediction model construction. The work includes two aspects: one is a novel application of the learning-to-rank approach to real-world data sets for software defect prediction, and the other is a comprehensive evaluation and comparison of the learning-to-rank method against other algorithms that have been used for predicting the order of software modules according to the predicted number of defects. Our empirical studies demonstrate the effectiveness of directly optimizing the model performance measure for the learning-to-rank approach to construct defect prediction models for the ranking task.

Evolutionary algorithm-based unmanned aerial vehicle (UAV) path planners have been extensively studied for their effectiveness and flexibility. However, they still suffer from a drawback that the high-quality waypoints in previous candidate paths can hardly be exploited for further evolution, since they regard all the waypoints of a path as an integrated individual. Due to this drawback, the previous planners usually fail when encountering lots of obstacles. In this paper, a new idea of separately evaluating and evolving waypoints is presented to solve this problem. Concretely, the original objective and constraint functions of UAVs path planning are decomposed into a set of new evaluation functions, with which waypoints on a path can be evaluated separately. The new evaluation functions allow waypoints on a path to be evolved separately and, thus, high-quality waypoints can be better exploited. On this basis, the waypoints are encoded in a rotated coordinate system with an external restriction and evolved with JADE, a state-of-the-art variant of the differential evolution algorithm. To test the capabilities of the new planner on planning obstacle-free paths, five scenarios with increasing numbers of obstacles are constructed. Three existing planners and four variants of the proposed planner are compared to assess the effectiveness and efficiency of the proposed planner. The results demonstrate the superiority of the proposed planner and the idea of separate evolution.

Dynamic Optimization Problems (DOPs) have been widely studied using Evolutionary Algorithms (EAs). Yet, a clear and rigorous definition of DOPs is lacking in the Evolutionary Dynamic Optimization (EDO) community. In this paper, we propose a unified definition of DOPs based on the idea of multiple-decision-making discussed in the Reinforcement Learning (RL) community. We draw a connection between EDO and RL by arguing that both of them are studying DOPs according to our definition of DOPs. We point out that existing EDO or RL research has been mainly focused on some types of DOPs. A conceptualized benchmark problem, which is aimed at the systematic study of various DOPs, is then developed. Some interesting experimental studies on the benchmark reveal that EDO and RL methods are specialized in certain types of DOPs and more importantly new algorithms for DOPs can be developed by combining the strength of both EDO and RL methods.

Multi-Objective Evolutionary Algorithms have been deeply studied in the research community and widely used in the real-world applications. However, the performance of traditional Pareto-based MOEAs, such as NSGA-II and SPEA2, may deteriorate when tackling Many-Objective Problems, which refer to the problems with at least four objectives. The main cause for the degradation lies in that the high-proportional non-dominated solutions severely weaken the differentiation ability of Pareto-dominance. This may lead to stagnation. The Two Archive Algorithm (TAA) uses two archives, namely Convergence Archive (CA) and Diversity Archive (DA) as non-dominated solution repositories, focusing on convergence and diversity respectively. However, as the objective dimension increases, the size of CA increases enormously, leaving little space for DA. Besides, the update rate of CA is quite low, which causes severe problems for TAA to drive forth. Moreover, since TAA prefers DA members that are far away from CA, DA might drag the population backwards. In order to deal with these weaknesses, this paper proposes an improved version of TAA, namely ITAA. Compared to TAA, ITAA incorporates a ranking mechanism for updating CA which enables truncating CA while CA overflows. Besides, a shifted density estimation technique is embedded to replace the old ranking method in DA. The efficiency of ITAA is demonstrated by the experimental studies on benchmark problems with up to 20 objectives.

Differential evolution (DE), as a very powerful population-based stochastic optimizer, is one of the most active research topics in the field of evolutionary computation. Self-adaptive differential evolution (SaDE) is a well-known DE variant, which aims to relieve the practical difficulty faced by DE in selecting among many candidates the most effective search strategy and its associated parameters. SaDE operates with multiple candidate strategies and gradually adapts the employed strategy and its accompanying parameter setting via learning the preceding behavior of already applied strategies and their associated parameter settings. Although highly effective, SaDE concentrates more on exploration than exploitation. To enhance SaDE's exploitation capability while maintaining its exploration power, we incorporate local search chains into SaDE following two different paradigms (Lamarckian and Baldwinian) that differ in the ways of utilizing local search results in SaDE. Our experiments are conducted on the CEC-2014 real-parameter single-objective optimization testbed. The statistical comparison results demonstrate that SaDE with Baldwinian local search chains, armed with suitable parameter settings, can significantly outperform original SaDE as well as classic DE at any tested problem dimensionality.

The synthesis of exact integer algorithms is a hard task for Genetic Programming (GP), as it exhibits epistasis and deceptiveness. Most existing studies in this domain only target few and simple problems or test a small set of different representations. In this paper, we present the (to the best of our knowledge) largest study on this domain to date. We first propose a novel benchmark suite of 20 non-trivial problems with a variety of different features. We then test two approaches to reduce the impact of the negative features: (a) a new nested form of Transactional Memory (TM) to reduce epistatic effects by allowing instructions in the program code to be permutated with less impact on the program behavior and (b) our recently published Frequency Fitness Assignment method (FFA) to reduce the chance of premature convergence on deceptive problems. In a full-factorial experiment with six different loop instructions, TM, and FFA, we find that GP is able to solve all benchmark problems, although not all of them with a high success rate. Several interesting algorithms are discovered. FFA has a tremendous positive impact while TM turns out not to be useful.

Path planning technique is vital to Unmanned Aerial Vehicle (UAV). Evolutionary Algorithms (EAs) have been widely used in planning path for UAV. In these EA-based path planners, Cartesian coordinate system and polar coordinate system are commonly used to codify the path. However, either of them has its drawback: Cartesian coordinate systems result in an enormous search space, whilst polar coordinate systems are unfit for local modifications resulting e.g., from mutation and/ or crossover. In order to overcome these two drawbacks, we solve the UAV path planning in a new coordinate system. As the new coordinate system is only a rotation of Cartesian coordinate system, it is inherently easy for local modification. Besides, this new coordinate system has successfully reduced the search space by explicitly dividing the mission space into several subspaces. Within this new coordinate system, an Estimation of Distribution Algorithms (EDAs) based path planner is proposed in this paper. Some experiments have been designed to test different aspects of the new path planner. The results show the effectiveness of this planner.

The convex hull has been extensively studied in computational geometry and its applications have spread over an impressive number of fields. How to find the convex hull is an important and challenging problem. Although many algorithms had been proposed for that, most of them can only tackle the problem in two or three dimensions and the biggest issue is that those algorithms rely on the samples' coordinates to find the convex hull. In this paper, we propose an approximation algorithm named FVDM, which only utilizes the information of the samples' distance matrix to find the convex hull. Experiments demonstrate that FVDM can effectively identify the vertices of the convex hull.

Architectural Design Space Exploration (DSE) is a notoriously difficult problem due to the exponentially large size of the design space and long simulation times. Previously, many studies proposed to formulate DSE as a regression problem which predicts architecture responses (e.g., time, power) of a given architectural configuration. Several of these techniques achieve high accuracy, though often at the cost of significant simulation time for training the regression models.We argue that the information the architect mostly needs during the DSEprocess is whether a given configuration will perform better than another one in the presences ofdesign constraints, or better than any other one seen so far, rather than precisely estimating the performance of that configuration. Based on this observation, we propose a novel rankingbased approach to DSE where we train a model to predict which of two architecture configurations will perform best. We show that, not only this ranking model more accurately predicts the relative merit of two architecture configurations than an ANN-based state-of-the-art regression model, but also that it requires much fewer training simulations to achieve the same accuracy, or that it can be used for and is even better at quantifying the performance gap between two configurations. We implement the framework for training and using this model, called ArchRanker, and we evaluate it on several DSE scenarios (unicore/multicore design spaces, and both time and power performance metrics). We try to emulate as closely as possible the DSE process by creating constraint-based scenarios, or an iterative DSEprocess. We find that ArchRanker makes 29.68% to 54.43% fewer incorrect predictions on pairwise relative merit of configurations (tested with 79,800 configuration pairs) than an ANN-based regression model across all DSE scenarios considered (values averaged over all benchmarks for each scenario). We also find that, to achieve the same accuracy as ArchRanker, the ANN often requires three times more training simulations.

Population-based Algorithm Portfolios (PAP) is an appealing framework for integrating different Evolutionary Algorithms (EAs) to solve challenging numerical optimization problems. Particularly, PAP has shown significant advantages to single EAs when a number of problems need to be solved simultaneously. Previous investigation on PAP reveals that choosing appropriate constituent algorithms is crucial to the success of PAP. However, no method has been developed for this purpose. In this paper, an extended version of PAP, namely PAP based on Estimated Performance Matrix (EPM-PAP) is proposed. EPM-PAP is equipped with a novel constituent algorithms selection module, which is based on the EPM of each candidate EAs. Empirical studies demonstrate that the EPM-based selection method can successfully identify appropriate constituent EAs, and thus EPM-PAP outperformed all single EAs considered in this work.

Metaheuristic optimization procedures such as evolutionary algorithms are usually driven by an objective function that rates the quality of a candidate solution. However, it is not clear in practice whether an objective function adequately rewards intermediate solutions on the path to the global optimum and it may exhibit deceptiveness, epistasis, neutrality, ruggedness, and a lack of causality. In this paper, we introduce the frequency fitness H, subject to minimization, which rates how often solutions with the same objective value have been discovered so far. The ideas behind this method are that good solutions are difficult to find and that if an algorithm gets stuck at a local optimum, the frequency of the objective values of the surrounding solutions will increase over time, which will eventually allow it to leave that region again. We substitute a frequency fitness assignment process (FFA) for the objective function into several different optimization algorithms. We conduct a comprehensive set of experiments: the synthesis of algorithms with genetic programming (GP), the solution of MAX-3SAT problems with genetic algorithms, classification with Memetic Genetic Programming, and numerical optimization with a$(1+1)$Evolution Strategy, to verify the utility of FFA. Given that they have no access to the original objective function at all, it is surprising that for some problems (e.g., the algorithm synthesis task) the FFA-based algorithm variants perform significantly better. However, this cannot be guaranteed for all tested problems. Thus, we also analyze scenarios where algorithms using FFA do not perform better or perform even worse than with the original objective functions.

Variable Interaction Learning (VIL) is an emerging technique regarding detecting interacting variables so that Cooperative Coevolutionary Evolutionary Algorithms (CCEAs) can decompose problems accordingly and tackle subproblems of smaller sizes. While previous approaches are developed to efficiently perform VIL, no study has been on the actual usefulness of the detected variable interactions in terms of the performance of CCEAs. Since VIL is a computationally expensive task by itself, overly spending time on VIL without notable benefits for CCEAs should be avoided. It is hence critical to study the real impact of problem decomposition on CCEAs. We conduct empirical studies to address three closely related questions: 1) will a better problem decomposition lead to better performance of CCEAs, 2) when will improving problem decomposition benefit CCEAs, and 3) to what extent will improving problem decomposition enhance the performance of CCEAs.

Hyperspectral image classification is difficult due to the high dimensional features, high intraclass variance, low interclass variance but limited training samples. In this paper, the ECASSL (Ensured Collaborative Active and Semi-Supervised Labeling) approach, which attempts to exploit pseudo-labeled samples to improve the performance of active learning based hyperspectral image classification, is proposed. In detail, in each round of active query, we obtain new human labeled samples from active query strategy and pseudo-labeled samples from the current trained classifier collaboratively. After that, we update the classifier base on latest labeled and pseudo-labeled samples. And then we correct those pseudo-labels obtained from previous iterations with the new classifier. Finally, we train the final classifier base on both the labeled samples and pseudo-labeled samples. The experiment results show that our algorithm significantly reduced the need of labeled samples while achieving comparable performance when compared with state-of-the-art algorithms for hyperspectral image classification.

Pipe breaks in urban water distribution network lead to significant economical and social costs, putting the service quality as well as the profit of water utilities at risk. To cope with such a situation, scheduled preventive maintenance is desired, which aims to predict and fix potential break pipes proactively. Physical models developed for understanding and predicting the failure of pipes are usually expensive, thus can only be used on a limited number of trunk pipes. As an alternative, statistical models that try to predict pipe breaks based on historical data are far less expensive, and therefore have attracted a lot of interests from water utilities recently. In this paper, we report a novel data mining prediction system that has been built for a water utility in a big Chinese city. Various aspects of how to build such a system are described, including problem formulation, data cleaning, model construction, as well as evaluating the importance of attributes according to the requirements of end users in water utilities. Satisfactory results have been achieved by our prediction system. For example, with the system trained on the available dataset at the end of 2010, the water utility would avoid 50% of pipe breaks in 2011 by examining only 6.98% of its pipes in advance. During the construction of the system, we find that the extremely skew distribution of break and non-break pipes, interestingly, is not an obstacle. This lesson could serve as a practical reference for both academical studies on imbalanced learning as well as future explorations on pipe failure prediction problems.

Class imbalance learning tackles supervised learning problems where some classes have significantly more examples than others. Most of the existing research focused only on binary-class cases. In this paper, we study multiclass imbalance problems and propose a dynamic sampling method (DyS) for multilayer perceptrons (MLP). In DyS, for each epoch of the training process, every example is fed to the current MLP and then the probability of it being selected for training the MLP is estimated. DyS dynamically selects informative data to train the MLP. In order to evaluate DyS and understand its strength and weakness, comprehensive experimental studies have been carried out. Results on 20 multiclass imbalanced data sets show that DyS can outperform the compared methods, including pre-sample methods, active learning methods, cost-sensitive methods, and boosting-type methods.

Evolutionary dynamic optimization has been drawing more and more research attention, and yet most work in this area is focused on Tracking Moving Optimum (TMO), which is to optimize the current fitness function at any time point. Recently, we proposed a more practical way to solve dynamic optimization problems, which is referred to as Robust Optimization Over Time (ROOT). In ROOT, we are trying to find solutions whose performances are acceptable over more than one environmental state, i.e., fitness functions. Before any development of benchmarks or algorithms for ROOT, it is necessary to have some understanding of what aspects of an environment can change and more importantly how these changes influence the solving of ROOT problems. In this paper, we develop a number of measures which can be used to characterize and analyse the underlying changing environment in the framework of ROOT. We test these measures on several benchmark problem instances, and it is shown that these measures are able to differentiate different dynamics effectively and provide useful information about what kind of algorithms might or might not suit certain dynamic environments.

A developmental, ontogenic approach to Capacitated Arc Routing Problems (CARPs) is introduced. The genotypes of this method are constructive heuristics specified as trees of mathematical functions which are evolved with Genetic Programming (GP). In a genotype-phenotype mapping, they guide a virtual vehicle which starts at the depot. The genotype is used to compute a heuristic value for each edge with unsatisfied demands. Local information such as the visiting costs from the current position, the remaining load of the vehicle, and the edge demands are available to the heuristic. The virtual vehicle then serves the edge with the lowest heuristic value and is located at its end. This process is repeated until all requirements have been satisfied. The resulting phenotypes are sets of tours which, in turn, are sequences of edges. We show that our method has three advantages: 1) The genotypes can be reused to seed the population in new GP runs. 2) The size of the genotypes is independent from the problem scale. 3) The evolved heuristics even work well in modified or dynamic scenarios and are robust in the presence of noise.

This paper presents a comparative study of two indirect solution representations, a generative and an ontogenic one, on a set of well-known 2D truss design problems. The generative representation encodes the parameters of a trusses design as a mapping from a 2D space. The ontogenic representation encodes truss design parameters as a local truss transformation iterated several times, starting from a trivial initial truss. Both representations are tested with a naive evolution strategy based optimization scheme, as well as the state of the art HyperNEAT approach. We focus both on the best objective value obtained and the computational cost to reach a given level of optimality. The study shows that the two solution representations behave very differently. For experimental settings with equal complexity, with the same optimization scheme and settings, the generative representation provides results which are far from optimal, whereas the ontogenic representation delivers near-optimal solutions. The ontogenic representation is also much less computationally expensive than a direct representation until very close to the global optimum. The study questions the scalability of the generative representations, while the results for the ontogenic representation display much better scalability.

In this paper, we evaluate the applicability of genetic programming (GP) for the evolution of distributed algorithms. We carry out a large-scale experimental study in which we tackle three well-known problems from distributed computing with six different program representations. For this purpose, we first define a simulation environment in which phenomena such as asynchronous computation at changing speed and messages taking over each other, i.e., out-of-order message delivery, occur with high probability. Second, we define extensions and adaptations of established GP approaches (such as tree-based and linear GP) in order to make them suitable for representing distributed algorithms. Third, we introduce novel rule-based GP methods designed especially with the characteristic difficulties of evolving algorithms (such as epistasis) in mind. Based on our extensive experimental study of these approaches, we conclude that GP is indeed a viable method for evolving non-trivial, deterministic, non-approximative distributed algorithms. Furthermore, one of the two rule-based approaches is shown to exhibit superior performance in most of the tasks and thus can be considered as an interesting idea also for other problem domains.

Thermal models of buildings are often used to identify energy savings within a building. Given that a significant proportion of that energy is typically used to maintain building temperature, establishing the optimal control of the buildings thermal system is important. This requires an understanding of the thermal dynamics of the building, which is often obtained from physical thermal models. However, these models require detailed building parameters to be specified and these can often be difficult to determine. In this paper, we propose an evolutionary approach to parameter identification for thermal models that are formulated as an optimization task. A state-of-the-art evolutionary algorithm, i.e., SaNSDE+, has been developed. A fitness function is defined, which quantifies the difference between the energy-consumption time-series data that are derived from the identified parameters and that given by simulation with a set of predetermined target model parameters. In comparison with a conventional genetic algorithm, fast evolutionary programming, and two state-of-the-art evolutionary algorithms, our experimental results show that the proposed SaNSDE+ has significantly improved both the solution quality and the convergence speed, suggesting this is an effective tool for parameter identification for simulated building thermal models.

The Area Under the ROC Curve (AUC) metric has achieved a big success in binary classification problems since they measure the performance of classifiers without making any specific assumptions about the class distribution and misclassification costs. This is desirable because the class distribution and misclassification costs may be unknown during training process or even change in environment. MAUC, the extension of AUC to multi-class problems, has also attracted a lot of attention. However, despite the emergence of approaches for training classifiers with large AUC, little has been done for MAUC. This paper analyzes MAUC in-depth, and reveals that the maximization of MAUC can be achieved by decomposing the multi-class problem into a number of independent sub-problems. These sub-problems are formulated in the form of a “learning to rank” problem, for which well-established methods already exist. Based on the analysis, a method that employs RankBoost algorithm as the sub-problem solver is proposed to achieve classification systems with maximum MAUC. Empirical studies have shown the advantages of the proposed method over other eight relevant methods. Due to the importance of MAUC to multi-class cost-sensitive learning and class imbalanced learning problems, the proposed method is a general technique for both problems. It can also be generalized to accommodate other learning algorithms as the sub-problem solvers.

Like most Evolutionary Algorithms (EAs), Differential Evolution (DE) usually requires a large number of fitness evaluations to obtain a sufficiently good solution. This is an obstacle for applying DE to computationally expensive problems. Many previous studies have been carried out to develop surrogate assisted approaches for EAs to reduce the number of real fitness evaluations. Existing methods typically build surrogates with either regression or ranking methods. However, due to the pairwise selection scheme of DE, it is more appropriate to formulate the construction of surrogate as a classification problem rather than a regression or ranking problem. Hence, we propose a classification-assisted DE in this paper. Experimental studies showed that the classification-assisted DE has great potential when compared to the DE that uses regression or ranking techniques to build surrogates.

In this work, we propose a new genetic programming algorithm with local search strategies, named Memetic Genetic Programming(MGP), for classification problems. MGP aims to acquire a classifier with large Area Under the ROC Curve (AUC), which has been proved to be a better performance metric for traditionally used metrics (e.g., classification accuracy). Three new points are presented in our new algorithm. First, a new representation called statistical genetic decision tree (SGDT) for GP is proposed on the basis of Genetic Decision Tree (GDT). Second, a new fitness function is designed by using statistic in formation from SGDT. Third, the concept of memetic computing is introduced into SGDT. As a result, the MGP is equipped with a local search method based on the training algorithms for decision trees. The efficacy of the MGP is empirically justified against a number of relevant approaches.

The large-scale Crossing Waypoints Location Problem (CWLP) is a crucial problem in the design of Air Route Network (ARN). CWLP is fully non-separable and non-differentiable, and thus traditional algorithms can hardly deal with it. This paper proposes an algorithm named Cooperative Co-evolution with Weighted Random Grouping (CCWR) to tackle it. CCWR employs the weighted random (WR) grouping strategy, which is specifically designed for CWLP, to divide the large-scale Crossing Waypoints (CWs) into small sub-groups and an Evolutionary Algorithm (EA) to solve the smaller scale CWs location problem in each sub-group. Experiments on the database of the ARN in China have been carried out to evaluate the performance of CCWR. The results showed that CCWR is superior to a number of state-of-the-art algorithms, and the advanced performance of CCWR is mainly due to the WR grouping strategy.

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.

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.

Dynamic optimization problems (DOPs) are those whose specifications change over time during the optimization, resulting in continuously moving optima. Most research work on DOPs is based on the assumption that the goal of addressing DOPs is to track the moving optima. In this paper, we first point out the practical limitations on tracking the moving optima. We then propose to find optimal solutions that are robust over time as an alternative goal, which leads to a new concept of robust optimization over time (ROOT) problem. In order to investigate the properties of ROOT in more depth, we study the new characteristics of ROOT and investigate its similarities to and differences from the traditional robust optimization problem, which hereafter is referred to as robust optimization for short. To facilitate future research on ROOT, we suggest a ROOT benchmark problem by modifying the moving peaks test problem. Several performance measures for comparing algorithms for solving ROOT problems are proposed.

Estimation of distribution algorithms (EDAs) are widely used in stochastic optimization. Impressive experimental results have been reported in the literature. However, little work has been done on analyzing the computation time of EDAs in relation to the problem size. It is still unclear how well EDAs (with a finite population size larger than two) will scale up when the dimension of the optimization problem (problem size) goes up. This paper studies the computational time complexity of a simple EDA, i.e., the univariate marginal distribution algorithm (UMDA), in order to gain more insight into EDAs complexity. First, we discuss how to measure the computational time complexity of EDAs. A classification of problem hardness based on our discussions is then given. Second, we prove a theorem related to problem hardness and the probability conditions of EDAs. Third, we propose a novel approach to analyzing the computational time complexity of UMDA using discrete dynamic systems and Chernoff bounds. Following this approach, we are able to derive a number of results on the first hitting time of UMDA on a well-known unimodal pseudo-boolean function, i.e., the LeadingOnes problem, and another problem derived from LeadingOnes, named BVLeadingOnes. Although both problems are unimodal, our analysis shows that LeadingOnes is easy for the UMDA, while BVLeadingOnes is hard for the UMDA. Finally, in order to address the key issue of what problem characteristics make a problem hard for UMDA, we discuss in depth the idea of ¿margins¿ (or relaxation). We prove theoretically that the UMDA with margins can solve the BVLeadingOnes problem efficiently.

In this paper, we consider the scenario that a population-based algorithm is applied to a numerical optimization problem and a solution needs to be presented within a given time budget. Although a wide range of population-based algorithms, such as evolutionary algorithms, particle swarm optimizers, and differential evolution, have been developed and studied under this scenario, the performance of an algorithm may vary significantly from problem to problem. This implies that there is an inherent risk associated with the selection of algorithms. We propose that, instead of choosing an existing algorithm and investing the entire time budget in it, it would be less risky to distribute the time among multiple different algorithms. A new approach named population-based algorithm portfolio (PAP), which takes multiple algorithms as its constituent algorithms, is proposed based upon this idea. PAP runs each constituent algorithm with a part of the given time budget and encourages interaction among the constituent algorithms with a migration scheme. As a general framework rather than a specific algorithm, PAP is easy to implement and can accommodate any existing population-based search algorithms. In addition, a metric is also proposed to compare the risks of any two algorithms on a problem set. We have comprehensively evaluated PAP via investigating 11 instantiations of it on 27 benchmark functions. Empirical results have shown that PAP outperforms its constituent algorithms in terms of solution quality, risk, and probability of finding the global optimum. Further analyses have revealed that the advantages of PAP are mostly credited to the synergy between constituent algorithms, which should complement each other either over a set of problems, or during different stages of an optimization process.

Software testing is an important issue in software engineering. As software systems become increasingly large and complex, the problem of how to optimally allocate the limited testing resource during the testing phase has become more important, and difficult. Traditional Optimal Testing Resource Allocation Problems (OTRAPs) involve seeking an optimal allocation of a limited amount of testing resource to a number of activities with respect to some objectives (e.g., reliability, or cost). We suggest solving OTRAPs with Multi-Objective Evolutionary Algorithms (MOEAs). Specifically, we formulate OTRAPs as two types of multi-objective problems. First, we consider the reliability of the system and the testing cost as two objectives. Second, the total testing resource consumed is also taken into account as the third objective. The advantages of MOEAs over state-of-the-art single objective approaches to OTRAPs will be shown through empirical studies. Our study has revealed that a well-known MOEA, namely Nondominated Sorting Genetic Algorithm II (NSGA-II), performs well on the first problem formulation, but fails on the second one. Hence, a Harmonic Distance Based Multi-Objective Evolutionary Algorithm (HaD-MOEA) is proposed and evaluated in this paper. Comprehensive experimental studies on both parallel-series, and star-structure modular software systems have shown the superiority of HaD-MOEA over NSGA-II for OTRAPs.

Redundancy allocation problems (RAPs) have attracted much attention for the past thirty years due to its wide applications in improving the reliability of various engineering systems. Because RAP is an NP-hard problem, and exact methods are only applicable to small instances, various heuristic and meta-heuristic methods have been proposed to solve it. In the literature, most studies on RAPs have been conducted for single-level systems. However, real-world engineering systems usually contain multiple levels. In this paper, the RAP on multi-level systems is investigated. A novel memetic algorithm (MA) is proposed to solve this problem. Two genetic operators, namely breadth-first crossover and breadth-first mutation, and a local search method are designed for the MA. Comprehensive experimental studies have shown that the proposed MA outperformed the state-of-the-art approach significantly on two representative examples.

Despite the wide-spread popularity of estimation of distribution algorithms (EDAs), there has been no theoretical proof that there exist optimisation problems where EDAs perform significantly better than traditional evolutionary algorithms. Here, it is proved rigorously that on a problem called SUBSTRING, a simple EDA called univariate marginal distribution algorithm (UMDA) is efficient, whereas the (1+1) EA is highly inefficient. Such studies are essential in gaining insight into fundamental research issues, i.e., what problem characteristics make an EDA or EA efficient, under what conditions an EDA is expected to outperform an EA, and what key factors are in an EDA that make it efficient or inefficient.

The fast evolutionary programming (FEP) introduced the Cauchy distribution into its mutation operator, thus the performances of EP were promoted significantly on a number of benchmark problems. However, the scaling parameter of the Cauchy mutation is invariable, which has become an obstacle for FEP to reach better performance. This paper proposes and analyzes a new stochastic method for controlling the variable scaling parameters of Cauchy mutation. This stochastic method collects information from a group of individuals randomly selected from the population. Empirical evidence validates our method to be very helpful in promoting the performance of FEP.

Univariate Marginal Distribution Algorithms (UMDAs) are a kind of Estimation of Distribution Algorithms (EDAs) which do not consider the dependencies among the variables. In this paper, on the basis of our proposed approach in [1], we present a rigorous proof for the result that the UMDA with margins (in [1] we merely showed the effectiveness of margins) cannot find the global optimum of the TRAPLEADINGONES problem [2] within polynomial number of generations with a probability that is super-polynomially close to 1. Such a theoretical result is significant in sheding light on the fundamental issues of what problem characteristics make an EDA hard/easy and when an EDA is expected to perform well/poorly for a given problem.

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.

JADE is a recent variant of differential evolution (DE) for numerical optimization, which has been reported to obtain some promising results in experimental study. However, we observed that the reliability, which is an important characteristic of stochastic algorithms, of JADE still needs to be improved. In this paper we apply two strategies together on the original JADE, to dedicatedly improve the reliability of it. We denote the new algorithm as rJADE. In rJADE, we first modify the control parameter adaptation strategy of JADE by adding a weighting strategy. Then, a ldquorestart with knowledge transferrdquo strategy is applied by utilizing the knowledge obtained from previous failures to guide the subsequent search. Experimental studies show that the proposed rJADE achieved significant improvements on a set of widely used benchmark functions.

The Redundancy Allocation Problem (RAP) is a kind of reliability optimization problems. It involves the selection of components with appropriate levels of redundancy or reliability to maximize the system reliability under some predefined constraints. We can formulate the RAP as a combinatorial problem when just considering the redundancy level, while as a continuous problem when considering the reliability level. The RAP employed in this paper is that kind of combinatorial optimization problems. During the past thirty years, there have already been a number of investigations on RAP. However, these investigations often treat RAP as a single objective problem with the only goal to maximize the system reliability (or minimize the designing cost). In this paper, we regard RAP as a multi-objective optimization problem: the reliability of the system and the corresponding designing cost are considered as two different objectives. Consequently, we can utilize a classical Multi-objective Evolutionary Algorithm (MOEA), named Non-dominated Sorting Genetic Algorithm II (NSGA-II), to cope with this multi-objective redundancy allocation problem (MORAP) under a number of constraints. The experimental results demonstrate that the multi-objective evolutionary approach can provide more promising solutions in comparison with two widely used single-objective approaches on two parallel-series systems which are frequently studied in the field of reliability optimization.

In this paper, we propose a new algorithm, named JACC-G, for large scale optimization problems. The motivation is to improve our previous work on grouping and adaptive weighting based cooperative coevolution algorithm, DECC-G [1], which uses random grouping strategy to divide the objective vector into subcomponents, and solve each of them in a cyclical fashion. The adaptive weighting mechanism is used to adjust all the subcomponents together at the end of each cycle. In the new JACC-G algorithm: (1) A most recent and efficient Differential Evolution (DE) variant, JADE [2], is employed as the subcomponent optimizer to seek for a better performance; (2) The adaptive weighting is time-consuming and expected to work only in the first few cycles, so a detection module is added to prevent applying it arbitrarily; (3) JADE is also used to optimize the weight vector in adaptive weighting process instead of using a basic DE in previous DECC-G. The efficacy of the proposed JACC-G algorithm is evaluated on two sets of widely used benchmark functions up to 1000 dimensions.

Class imbalance learning is an important research area in machine learning, where instances in some classes heavily outnumber the instances in other classes. This unbalanced class distribution causes performance degradation. Some ensemble solutions have been proposed for the class imbalance problem. Diversity has been proved to be an influential aspect in ensemble learning, which describes the degree of different decisions made by classifiers. However, none of those proposed solutions explore the impact of diversity on imbalanced data sets. In addition, most of them are based on re-sampling techniques to rebalance class distribution, and over-sampling usually causes overfitting (high generalisation error). This paper investigates if diversity can relieve this problem by using negative correlation learning (NCL) model, which encourages diversity explicitly by adding a penalty term in the error function of neural networks. A variation model of NCL is also proposed - NCLCost. Our study shows that diversity has a direct impact on the measure of recall. It is also a factor that causes the reduction of F-measure. In addition, although NCL-based models with extreme settings do not produce better recall values of minority class than SMOTEBoost [1], they have slightly better performance of F-measure and G-mean than both independent ANNs and SMOTEBoost and better recall than independent ANNs.

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.

Scheduling aircraft landings has been a complex and challenging problem in air traffic control for long time. In this paper, we propose to solve the aircraft landing scheduling problem (ALSP) using multi-objective evolutionary algorithms (MOEAs). Specifically, we consider simultaneously minimizing the total scheduled time of arrival and the total cost, and formulate the ALSP as a 2-objective optimization problem. A MOEA named Multi-Objective Neighborhood Search Differential Evolution (MONSDE) is applied to solve the 2-objective ALSP. Besides, a ranking scheme named non-dominated average ranking is also proposed to determine the optimal landing sequence. Advantages of our approaches are demonstrated on two example scenarios.

Nowadays, as the software systems become increasingly large and complex, the problem of allocating the limited testing-resource during the testing phase has become more and more difficult. In this paper, we propose to solve the testing-resource allocation problem (TRAP) using multi-objective evolutionary algorithms. Specifically, we formulate TRAP as two multi-objective problems. First, we consider the reliability of the system and the testing cost as two objectives. In the second formulation, the total testing-resource consumed is also taken into account as the third goal. Two multi-objective evolutionary algorithms, Non-dominated Sorting Genetic Algorithm II (NSGA2) and Multi-Objective Differential Evolution Algorithms (MODE), are applied to solve the TRAP in the two scenarios. This is the first time that the TRAP is explicitly formulated and solved by multi-objective evolutionary approaches. Advantages of our approaches over the state-of-the-art single-objective approaches are demonstrated on two parallel-series modular software models.

In this paper we investigate several self-adaptive mechanisms to improve our previous work on NSDE, which is a recent DE variant for numerical optimization. The self-adaptive methods originate from another DE variant, SaDE, but are remarkably modified and extended to fit our NSDE. And thus a self-adaptive NSDE (SaNSDE) is proposed to improve NSDEpsilas performance. Three self-adaptive mechanisms are utilized in SaNSDE: self-adaptation for two candidate mutation strategies, self-adaptations for controlling scale factor F and crossover rate CR, respectively. Experimental studies are carried out on a broad range of different benchmark functions, and the proposed SaNSDE has shown significant superiority over NSDE.

In this paper, we propose a multilevel cooperative coevolution (MLCC) framework for large scale optimization problems. The motivation is to improve our previous work on grouping based cooperative coevolution (EACC-G), which has a hard-to-determine parameter, group size, in tackling problem decomposition. The problem decomposer takes group size as parameter to divide the objective vector into low dimensional subcomponents with a random grouping strategy. In the MLCC, a set of problem decomposers is constructed based on the random grouping strategy with different group sizes. The evolution process is divided into a number of cycles, and at the start of each cycle MLCC uses a self-adapted mechanism to select a decomposer according to its historical performance. Since different group sizes capture different interaction levels between the original objective variables, MLCC is able to self-adapt among different levels. The efficacy of the proposed MLCC is evaluated on the set of benchmark functions provided by CECpsila2008 special session.

Addressing dynamic optimization problems (DOPs) has been a challenging task for the genetic algorithm (GA) community. One approach is to maintain the diversity of the population via introducing immigrants. This paper intensively examines several design decisions when employing immigrants schemes, and from these observations an environmental information-based immigrants scheme is derived for GAs to deal with DOPs. In the scheme, the environmental information (e.g., the allele distribution over the population in this paper) from previous generation is used to create immigrants to replace the worst individuals in the current population. In this way, the introduced immigrants are more adapted to the changing environment. A hybrid scheme combining immigrants based on current environmental information and its complementation is also proposed in this paper to address different degrees of changes. Experimental results validate the efficacy of the proposed environmental information-based and hybrid environmental information-based immigrants schemes.

Negative correlation learning (NCL) is a successful scheme for constructing neural network ensembles. In batch learning mode, NCL outperforms many other ensemble learning approaches. Recently, NCL is also shown to be a potentially powerful approach to incremental learning, while the advantage of NCL has not yet been fully exploited. In this paper, we propose a selective NCL approach for incremental learning. In the proposed approach, the previously trained ensemble is cloned when a new data set presents and the cloned ensemble is trained on the new data set. Then, the new ensemble is combined with the previous ensemble and a selection process is applied to prune the whole ensemble to a fixedsize. Simulation results on several benchmark datasets show that the proposed algorithm outperforms two recent incremental learning algorithms based on NCL.

Estimation of Distribution Algorithm (EDA) is a well-known stochastic optimization technique. The average time complexity is a crucial criterion that measures the performance of the stochastic algorithms. In the past few years, various kinds of EDAs have been proposed, but the related theoretical study on the time complexity of these algorithms is relatively few. This paper analyzed the time complexity of two early versions of EDA, the Univariate Marginal Distribution Algorithm (UMDA) and the Incremental UMDA (IUMDA). We generalize the concept of convergence to convergence time, and manage to estimate the upper bound of the mean First Hitting Times (FHTs) of UMDA (IUMDA) on a well-known pseudo-modular function, which is frequently studied in the field of genetic algorithms. Our analysis shows that UMDA (IUMDA) has O(n) behaviors on the pseudo-modular function. In addition, we analyze the mean FHT of IUMDA on a hard problem. Our result shows that IUMDA may spend exponential generations to find the global optimum. This is the first time that the mean first hitting times of UMDA (IUMDA) are theoretically studied.

Most reported studies on differential evolution (DE) are obtained using low-dimensional problems, e.g., smaller than 100, which are relatively small for many real-world problems. In this paper we propose two new efficient DE variants, named DECC-I and DECC-II, for high-dimensional optimization (up to 1000 dimensions). The two algorithms are based on a cooperative coevolution framework incorporated with several novel strategies. The new strategies are mainly focus on problem decomposition and subcomponents cooperation. Experimental results have shown that these algorithms have superior performance on a set of widely used benchmark functions.