In-context learning (ICL) has proven to be adept at adapting large language models (LLMs) to downstream tasks without parameter updates, based on a few demonstration examples. Prior work has found that the ICL performance is susceptible to the selection of examples in prompt and made efforts to stabilize it. However, existing example selection studies ignore the ethical risks behind the examples selected, such as gender and race bias. In this work, we conduct extensive experiments and discover that (1) example selection with high accuracy does not mean low bias; (2) example selection for ICL may amplify the biases of LLMs; (3) example selection contributes to spurious correlations of LLMs. Based on the above observations, we propose the Remind with Bias-aware Embedding (ReBE), which removes the spurious correlations through contrastive learning and obtains bias-aware embedding for LLMs based on prompt tuning. Finally, we demonstrate that ReBE effectively mitigates biases of LLMs without significantly compromising accuracy and is highly compatible with existing example selection methods.

With the rapid deployment of Chinese large language models (LLMs), culturally-grounded bias evaluation remains understudied due to the dominance of English benchmarks and simplistic Chinese scenarios. To address this, we propose GeWu, a comprehensive benchmark featuring a culturally-aware dataset of 60,192 questions spanning 14 social groups with fine-grained Chinese contexts, significantly exceeding existing resources in breadth and depth. Our two-stage evaluation first quantifies bias via multiple-choice questions using a novel probability-based scoring mechanism to sensitively capture bias tendencies, distilling high-bias scenarios into GeWu-1K. This refined subset then enables multi-turn dialogue evaluations for in-depth analysis under realistic conditions. Experiments reveal that GeWu effectively exposes social biases in state-of-the-art Chinese LLMs, with 13.93% of scenarios eliciting universal bias across all models. This highlights persistent challenges and provides actionable insights for bias mitigation in Chinese contexts.

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.

In Artificial Intelligence, there is an increasing demand for adaptive models capable of dealing with a diverse spectrum of learning tasks, surpassing the limitations of systems devised to cope with a single task. The recent emergence of General-Purpose Artificial Intelligence Systems (GPAIS) poses model configuration and adaptability challenges at far greater complexity scales than the optimal design of traditional Machine Learning models. Evolutionary Computation (EC) has been a useful tool for both the design and optimization of Machine Learning models, endowing them with the capability to configure and/or adapt themselves to the task under consideration. Therefore, their application to GPAIS is a natural choice. This paper aims to analyze the role of EC in the field of GPAIS, exploring the use of EC for their design or enrichment. We also match GPAIS properties to Machine Learning areas in which EC has had a notable contribution, highlighting recent milestones of EC for GPAIS. Furthermore, we discuss the challenges of harnessing the benefits of EC for GPAIS, presenting different strategies to both design and improve GPAIS with EC, covering tangential areas, identifying research niches, and outlining potential research directions for EC and GPAIS.

The generation of motion behaviors plays a pivotal role in constructing effective simulated scenarios for testing autonomous driving systems (ADSs). The controllability (i.e., the ability to synthesize specific motion patterns) and multimodality (i.e., the capacity to represent multiple motion intentions) of generated motion behaviors are essential for the purposeful and comprehensive evaluation of ADS. Although recent studies have made progress in either multimodal or controllable motion behavior generation, it remains a major challenge to simultaneously generate multimodal motion behaviors in a controllable manner. In this work, we propose a unified framework, CoMoGen, to generate multimodal motion behaviors in a controllable manner under open-loop evaluation assumption. The proposed framework consists of three core components: i) a learning-based vehicle placer, responsible for positioning generated vehicles in non-conflicting initial locations; ii) a robust model-based trajectory candidate generator, capable of synthesizing controllable and multimodal trajectory candidates. iii) a learning-based trajectory selector, developed to evaluate and select multimodal trajectories for the placed vehicles. Experiments on the INTERACTION dataset demonstrate strong controllability and multimodality of CoMoGen. Further experiments on three additional real-world datasets, that are unseen during training, as well as on diverse synthesized high-definition maps, validate the remarkable generalization capability of CoMoGen.

Many real-world optimization problems exhibit dynamic characteristics, posing significant challenges for traditional optimization methods. Evolutionary Dynamic Optimization Algorithms (EDOAs) have been developed to address these challenges by adapting to changing environments over time. However, the reproducibility and consistency of experimental results in the literature remain limited due to the lack of publicly available source codes and the complexity of accurately re-implementing algorithms and performance evaluation protocols. To support the community, we introduce E volutionary D ynamic O ptimization LAB oratory (EDOLAB), an open source MATLAB platform designed for both research and educational purposes. EDOLAB includes 27 EDOAs, four highly configurable benchmark generators, and a growing suite of performance indicators. The platform supports full parameter tuning, batch experiment management, parallel execution, and automated statistical comparisons—including rankings, significance testing, box plots, and performance trend visualizations over time. An educational application allows users to observe: (a) dynamic changes in a 2D problem landscape, (b) the movement of individuals in response to these changes, and (c) the ability of an algorithm to track moving optima. By providing an integrated environment for experimentation, benchmarking, and instructional use, EDOLAB promotes reproducibility, comparative analysis, and a deeper understanding of EDOAs in dynamic environments.

Yuxuan Li, Xinwei Guo, Jiashi Gao, Guanhua Chen, Xiangyu Zhao, Jiaxin Zhang, Quanying Liu, Haiyan Wu, Xin Yao, Xuetao Wei. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Workflow scheduling has been extensively studied in distributed computing, with most research primarily focusing on single workflow scheduling problems. However, in real-world scenarios, multiple workflows from different individual users often need to be scheduled concurrently on shared computing resources, which raises significant fairness concerns among these workflows. Existing approaches typically overlook fairness in multiple workflow scheduling, leading to disproportionate completion time slowdowns across different workflows. To address this challenge, we introduce a novel fairness metric that quantitatively captures the slowdown disparity among multiple workflows and propose the FairFlowSR (Fair-Flow Stochastic Ranking) algorithm to ensure fairness among concurrent workflows. The FairFlowSR algorithm integrates two key components: a fair selection strategy that balances exploitation and exploration, and a stochastic ranking method that effectively handles fairness constraints. Extensive experimental results demonstrate that FairFlowSR significantly outperforms state-of-the-art algorithms, achieving superior fairness maintenance and competitive makespan optimization. These results validate the effectiveness of our approach in achieving a balanced trade-off between efficiency and fairness in multiple-workflow scheduling scenarios.

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.

The paper introduces a novel hybrid island-based framework in which diverse metaheuristics cooperate to effectively explore the search space. A core component of the framework is a diversity-driven migration mechanism, enabling adaptive management of the information flow between islands. Three fundamental aspects of migration - what to migrate, when to migrate, and where to migrate - are thoroughly analyzed, leading to the development of strategies that foster synergy between heterogeneous algorithms. These strategies balance exploration and exploitation, ensuring effective global and local search. The framework was evaluated on a set of diverse optimization benchmarks, both discrete (Traveling Salesman Problem instances) and continuous (BBOB functions). Experimental results demonstrate that the proposed approach surpasses traditional algorithms and their island-based variants in convergence speed, solution quality, and resilience to stagnation. Adaptive mechanisms dynamically adjust migration strategies during the optimization process, further enhancing the framework's effectiveness. The proposed method represents an advancement in hybrid metaheuristic systems, offering scalability and flexibility that are essential for solving complex optimization tasks.

Parallel Algorithm Portfolio (PAP) is a promising approach to solving computationally hard problems efficiently. A portfolio is a set of problem solvers, each optimized for different problem types. However, the portfolio configuration process is computationally expensive, requiring numerous solver evaluations. This paper explores two methods to accelerate PAP construction. The first method leverages the vast amount of data generated during portfolio configuration to train a surrogate model, reducing the need for costly evaluations. The second method investigates training portfolios on smaller problem instances before applying them to more complex target instances. A comprehensive experimental study on the Traveling Salesman Problem instances demonstrates that both methods significantly reduce computational time, albeit at the cost of slightly reducing portfolio performance.

The optimization of complex problems remains a significant challenge across various domains of science and engineering. This paper introduces a novel approach to island-based optimization that dynamically adapts metaheuristic selection during runtime, extending the Diversity-driven Cooperating Portfolio of Metaheuristics (DdCPM) framework. Our method integrates additional metaheuristics beyond the original implementation and proposes adaptation strategies that dynamically reconfigure the algorithm portfolio based on performance indicators and population characteristics. Experimental results across both discrete and continuous optimization benchmarks demonstrate that adaptive metaheuristic selection enhances solution quality and convergence rates compared to static approaches. The proposed framework represents an advancement in hybrid optimization systems, offering improved performance through intelligent adaptation mechanisms that correspond to the evolving state of the search process.

Text-to-Image (T2I) diffusion models exhibit concerning tendencies to generate harmful imagery that perpetuates social biases and stereotypes, posing significant ethical risks in real-world applications. While existing mitigation approaches predominantly employ black-box methodologies through dataset augmentation or constrained fine-tuning, they face critical limitations, including high data acquisition costs and potential exacerbation of stereotypes during model retraining. Inspired by neuroscience principles where neurological dysfunction often stems from aberrant neural activation patterns, we propose a novel framework, StereoClinic, targeting the root cause of stereotype generation through direct neural intervention. Our solution introduces two synergistic components: Diffusion Deep Taylor Decomposition (DDTD) for precisely localizing stereotype-related neurons via Layer-wise Relevance Propagation (LRP) attribution analysis, and Stereotype Neuron Suppression (SNS) implementing targeted activation damping to neutralize bias propagation. Through extensive empirical evaluations across multiple bias dimensions, we demonstrate that our method achieves significant stereotype mitigation without compromising image quality or requiring additional training data. This neuro-inspired approach establishes a new paradigm for model interpretability and ethical alignment in generative AI systems.

The overlapping coalition structure generation problem (OCSGP) is a challenging computational problem in multi-agent systems. It focuses on selecting possibly overlapping coalitions from a set of agents to maximize the social welfare of all coalitions while containing all agents. However, in practical applications, coalitions may be formed to selectively respond to tasks from a pool of potential tasks assigned to agents. Consequently, this study considers OCSGP in a task-based setting, where each agent has finite resources and can only respond to tasks of interest, and each coalition can only take on mutually disjoint subsets of tasks. Specifically, we first present a model of the task-based OCSGP and investigate its computational complexity. Our theoretical results demonstrate that this specific OCSGP remains intractable even under restrictive assumptions. Subsequently, we develop a generic evolutionary algorithm framework (EAF) to find an approximately optimal overlapping coalition structure (OCS) in time quartic polynomial in the size of the instance. Particularly, we devise a specific solution-repair based heuristic of cubic time complexity to generate a feasible OCS. Finally, we compare the proposed EAF with a task-oriented heuristic and a hybrid algorithm for OCSGP, and examine its applicability in the pursuit-evasion problem. The experimental results reveal that the proposed EAF exhibits superior performance in finding feasible OCSs and demonstrates flexible adaptability to problem size and resource status.

In a real-world setting, several correlational data streams are active at once. An essential question is how to use the correlations between data streams to enhance the effectiveness of machine learning models. The fact that data streams are nonstationary and the correlations across data streams might change over time presents another difficulty. We suggest an ensemble chain-structured model, Evolutionary regressor chains (RCs), to track the correlations between data streams to solve these issues. We develop a heuristic order searching approach to search for the chain's optimal order. With the ability to monitor the dynamicity of the correlations, the heuristic order searching technique can also update the chains over time. Furthermore, a way for reducing computing complexity while maintaining the ensemble's diversity is proposed. The method's theoretical foundation is established through a dynamic regret analysis proving optimal adaptation in the data streams. The outcomes of our experiments demonstrate the effectiveness of Evolutionary RCs.

Multi-objective optimization problems (MOPs) containing a large number of decision variables, which are also known as large-scale multi-objective optimization problems (LSMOPs), pose great challenges to most existing evolutionary algorithms. This is mainly because that a high dimensional decision space degrades the effectiveness of search operators notably, and balancing convergence and diversity becomes a challenging task. In this paper, we propose a two-population based algorithm for large-scale multi-objective optimization named LSTPA. In the proposed algorithm, solutions are classified in to two subpopulations: a Convergence subPopulation (CP) and a Diversity subPopulation (DP), aiming at convergence and diversity respectively. In order to improve convergence speed, a fitness-aware variation operator (FAVO) is applied to drive DP solutions towards CP. Besides, an adaptive penalty based boundary intersection (APBI) strategy is adopted for environmental selection in order to balance convergence and diversity temporally during different stages of evolution process. Experimental results on benchmark test problems with 100-2000 decision variables demonstrate that the proposed algorithm can achieve the best overall performance compared with several state-of-the-art large-scale multi-objective evolutionary algorithms.

In dynamic multi-objective optimization problems (DMOPs) where the number of objectives changes, the Pareto-optimal set (PS) manifold may expand or contract over time. Knowledge transfer has been utilized to solve DMOPs because it can transfer valuable information from one problem-solving instance (i.e., source) to solving another related problem instance. However, existing transfer approaches suffer from poor diversity and convergence after a severe increase and decrease in the number of objectives, respectively. The reason is that most transfer approaches simply transfer knowledge from the solutions before the change, which causes degeneration in quality of transferred solutions due to dissimilarity between the problem instances before and after the severe change. In this paper, we propose a simple-yet-effective transfer approach, called similarity transfer approach (STA) to tackling a severely changing number of objectives. It selects the historically most similar environment to the current one as the source problem instance and transfers knowledge from that environment. Furthermore, a novel strategy of randomization enhancing transfer diversity is proposed in STA if the transfer from the most similar environment still lacks sufficient diversity when increasing the number of objectives. Comprehensive studies using 13 DMOP benchmarks with a severely changing number of objectives demonstrate that our proposed STA is effective in improving solution quality not only immediately after changes but also after optimization, in comparison to state-of-the-art algorithms.

Dynamic multi-objective optimization problems (DMOPs) with a changing number of objectives may have Pareto-optimal set (PS) manifold expanding or contracting over time. Knowledge transfer has been used for solving DMOPs, since it can transfer useful information from solving one problem instance to solve another related problem instance. However, we show that the state-of-the-art transfer approach based on heuristic lacks diversity on problem with extremely strong bias and loses convergence on problems with multi-modality and variable correlation, after the number of objectives increases and decreases, respectively. Therefore, we propose a novel transfer strategy based on learning, called learning to expand and contract PS (denoted as LEC) for enhancing diversity and convergence after number of objective increases and decreases, respectively. It firstly learns potentially good directions for expansion and contraction separately via principal component analysis. Then, the most promising expansion and contraction directions are selected from their candidates according to whether they help diversity and convergence, respectively. Lastly, PS is learnt to be expanded and contracted based on these most promising directions. Comprehensive studies using 13 DMOP benchmarks with a changing number of objectives demonstrate that our proposed LEC is effective on improving solution quality, not only right after changes but also after optimization of different generations, compared to state-of-the-art algorithms.

Traveling salesman problem (TSP) is a combinatorial optimization problem, serving as basis for many real-world applications (e.g., transportation planning, circuit board design, and DNA sequencing). In TSP, it is common to encounter some dynamic events, for example, traffic jam, and roadworks in transportation planning. To deal with such dynamic TSP (DTSP) scenarios, numerous techniques have been designed over decades. In this article, we take a different perspective to study DTSP. Instead of focusing only on algorithm design for DTSP, we investigate how dynamic events in DTSP affect its fitness landscape (e.g., the location of local optimal solutions and the ruggedness level of search space). We consider three dynamic events, including node addition, node deletion and weight changes, and analyze how they affect the TSP with respect to the overall landscape structure and solution optimality. Experimental results show that the weight change event has great effect on the problem’s fitness landscape, introducing more local optima and reducing the basin of attraction for the global optimum. This may suggest that search algorithms need to have stronger exploration capability when handling weight change dynamic events. Furthermore, our experimental studies also demonstrate that the dynamic solution adaptation strategy on the original global optimum is effective for tracking the new optimum after dynamic changes.

When solving dynamic multiobjective optimization problems, most evolutionary algorithms attempt to predict the initial population in a new environment by mining the relationships between solutions during historical environment changes. However, the complex relationships between solutions and the limited amount of available data often make it difficult to extract useful information efficiently, which may deteriorate the prediction accuracy. To address this problem, this paper proposes a spatial-temporal topological tensor-based prediction method to generate the initial population in a new environment under the decomposition framework of MOEA/D. The method relies on the idea that the population distribution in each environment has topological similarity along the time dimension in the objective space, which makes it efficient to represent the population distribution in terms of a tensor and predict new solutions along each decomposition axis in a new environment by an improved tensor-based multi-short time series prediction method. Experimental results on various benchmark problems and a real-world problem show that the proposed method is competitive or even superior to state-of-the-art dynamic multiobjective evolutionary algorithms based on prediction strategies.

Multiobjective evolutionary learning (MOEL) has demonstrated its advantages of training fairer machine learning models considering a predefined set of conflicting objectives, including accuracy and different fairness measures. Recent works propose to construct a representative subset of fairness measures as optimization objectives of MOEL throughout model training. However, the determination of a representative measure set relies on the dataset, prior knowledge, and requires substantial computational costs. What is more, those representative measures may differ across different model training processes. Instead of using a static predefined set determined before model training, this article proposes to dynamically and adaptively determine a representative measure set online during the model training. The dynamically determined representative set is then used as optimizing objectives of the MOEL framework and can vary with time. Extensive experimental results on 12 well-known benchmark datasets demonstrate that our proposed framework achieves outstanding performance compared to the state-of-the-art approaches for mitigating unfairness in terms of accuracy as well as 25 fairness measures although only a few of them were dynamically selected and used as optimization objectives. The results indicate the importance of setting optimization objectives dynamically during training.

Dynamic material handling (DMH) involves the assignment of dynamically arriving material transporting tasks to suitable vehicles in real time for minimizing makespan and tardiness. In real-world scenarios, historical task records are usually available, which enables the training of a decision policy on multiple instances consisting of historical records. Recently, reinforcement learning (RL) has been applied to solve DMH. Due to the occurrence of dynamic events such as new tasks, adaptability is highly required. Solving DMH is challenging since constraints, including task delay, should be satisfied. A feedback is received only when all tasks are served, which leads to sparse reward. Besides, making the best use of limited computational resources and historical records for training a robust policy is crucial. The time allocated to different problem instances would highly impact the learning process. To tackle those challenges, this article proposes a novel adaptive constrained evolutionary RL (ACERL) approach, which maintains a population of actors for diverse exploration. ACERL accesses each actor for tackling sparse rewards and constraint violation to restrict the behavior of the policy. Moreover, ACERL adaptively selects the most beneficial training instances for improving the policy. Extensive experiments on eight training and eight unseen test instances demonstrate the outstanding performance of ACERL compared with several state-of-the-art algorithms. Policies trained by ACERL can schedule the vehicles while fully satisfying the constraints. Additional experiments on 40 unseen noised instances show the robust performance of ACERL. Cross validation further presents the overall effectiveness of ACREL. Besides, a rigorous ablation study highlights the coordination and benefits of each ingredient of ACERL.

Vertical Federated Learning (VFL) enables an active party with labeled data to enhance model performance (utility) by collaborating with multiple passive parties that possess auxiliary features corresponding to the same sample identifiers (IDs). Model serving in VFL is vital for real-world, delay-sensitive applications, and it faces two major challenges: 1) robustness against arbitrarily-aligned data and stragglers; and 2) privacy protection, ensuring minimal label leakage to passive parties. Existing methods fail to transfer knowledge among parties to improve robustness in a privacy-preserving way. In this paper, we introduce a privacy-preserving knowledge transfer framework, Complementary Knowledge Distillation (CKD), designed to enhance the robustness and privacy of multi-party VFL systems. Specifically, we formulate a Complementary Label Coding (CLC) objective to encode only complementary label information of the active party's local model for passive parties to learn. Then, CKD selectively transfers the CLC-encoded complementary knowledge 1) from the passive parties to the active party, and 2) among the passive parties themselves. Experimental results on four real-world datasets demonstrate that CKD outperforms existing approaches in terms of robustness against arbitrarily-aligned data, while also minimizing label privacy leakage.

The online data markets have emerged as a valuable source of diverse datasets for training machine learning (ML) models. However, datasets from different data providers may exhibit varying levels of bias with respect to certain sensitive attributes in the population (such as race, sex, age, and marital status). Recent dataset acquisition research has focused on maximizing accuracy improvements for downstream model training, ignoring the negative impact of biases in the acquired datasets, which can lead to an unfair model. Can a consumer obtain an unbiased dataset from datasets with diverse biases? In this work, we propose a fairness-aware data acquisition framework (FAIRDA) to acquire high-quality datasets that maximize both accuracy and fairness for consumer local classifier training while remaining within a limited budget. Given the biases of data commodities remain opaque to consumers, the data acquisition in FAIRDA employs explore-exploit strategies. Based on whether exploration and exploitation are conducted sequentially or alternately, we introduce two algorithms: the knowledge-based offline data acquisition (KDA) and the reward-based online data acquisition algorithms (RDA). Each algorithm is tailored to specific customer needs, giving the former an advantage in computational efficiency and the latter an advantage in robustness. We conduct experiments to demonstrate the effectiveness of the proposed data acquisition framework in steering users toward fairer model training compared to existing baselines under varying market settings.

Network slicing is an essential technology in 5G and the forthcoming 6G networks. It aims to embed multiple virtual networks, i.e., network slices, on top of a shared substrate network to meet diverse service requirements. While a considerable body of existing research strives to maximize overall profits by meeting the resource demands of the network slices, optimizing their reliability is frequently overlooked. In this paper, we formalize the network slicing problem as a multi-objective optimization problem that aims to maximize total profits and reliability of network slices. To tackle this problem, we propose a new multi-objective optimization approach that improves over the state-of-the-art algorithm, which can achieve good approximate Pareto front results balancing total profits and reliability of network slices. The performance of our proposed method is evaluated on both artificial and real-world network topologies. Experimental results demonstrate the superior performance of our proposed method compared to the baseline algorithm, outperforming the latter in 92% of instances in terms of the Hypervolume (HV) metric.

The uncapacitated facility location problem (UFLP) is a well-known combinational optimization problem, attracting numerous heuristic and meta-heuristic methods. However, these effective algorithms still encounter challenges when solving large-scale UFLP instances. To deal with the thousands of decision variables, one possible approach is to predict and remove unimportant facilities and thus decreases the dimensionality of problem instances. This paper explores the problem reduction of large-scale instances of UFLP. We propose suitable features of facilities to construct machine learning models for UFLP by learning from small instances. Based on this model, we introduce a novel problem reduction strategy-based optimization framework, and apply it to large instances. Through comprehen-sive experiments, we show that the proposed problem reduction strategy can effectively transform the UFLP instances to smaller ones. The performance of existing solution methods can be significantly enhanced, especially on large-scale instances. Under the proposed framework, we also show the generalization abilities of our models, which can be improved further.

Federated learning (FL) stands as a paradigmatic approach that facilitates model training across heterogeneous and diverse datasets originating from various data providers. However, conventional FLs fall short of achieving consistent performance, potentially leading to performance degradation for clients who are disadvantaged in data resources. Influenced by the Matthew effect, deploying a performance-imbalanced global model in applications further impedes the generation of high-quality data from disadvantaged clients, exacerbating the disparities in data resources among clients. In this work, we propose anti-Matthew fairness for the global model at the client level, requiring equal accuracy and equal decision bias across clients. To balance the trade-off between achieving anti-Matthew fairness and performance optimality, we formalize the anti-Matthew effect federated learning (anti-Matthew FL) as a multi-constrained multi-objectives optimization (MCMOO) problem and propose a three-stage multi-gradient descent algorithm to obtain the Pareto optimality. We theoretically analyze the convergence and time complexity of our proposed algorithms. Additionally, through extensive experimentation, we demonstrate that our proposed anti-Matthew FL outperforms other state-of-the-art FL algorithms in achieving a high-performance global model while effectively bridging performance gaps among clients. We hope this work provides valuable insights into the manifestation of the Matthew effect in FL and other decentralized learning scenarios and can contribute to designing fairer learning mechanisms, ultimately fostering societal welfare.

Recently, evolutionary reinforcement learning has obtained much attention in various domains. Maintaining a population of actors, evolutionary reinforcement learning utilises the collected experiences to improve the behaviour policy through efficient exploration. However, the poor scalability of genetic operators limits the efficiency of optimising high-dimensional neural networks. To address this issue, this paper proposes a novel cooperative coevolutionary reinforcement learning (CoERL) algorithm. Inspired by cooperative coevolution, CoERL periodically and adaptively decomposes the policy optimisation problem into multiple subproblems and evolves a population of neural networks for each of the subproblems. Instead of using genetic operators, CoERL directly searches for partial gradients to update the policy. Updating policy with partial gradients maintains consistency between the behaviour spaces of parents and offspring across generations. The experiences collected by the population are then used to improve the entire policy, which enhances the sampling efficiency. Experiments on six benchmark locomotion tasks demonstrate that CoERL outperforms seven state-of-the-art algorithms and baselines. Ablation study verifies the unique contribution of CoERL’s core ingredients.

Clustering in dynamic environments is of increasing importance, with broad applications ranging from real-time data analysis and online unsupervised learning to dynamic facility location problems. While meta-heuristics have shown promising effectiveness in static clustering tasks, their application for tracking optimal clustering solutions or robust clustering over time in dynamic environments remains largely underexplored. This is partly due to a lack of dynamic datasets with diverse, controllable, and realistic dynamic characteristics, hindering systematic performance evaluations of clustering algorithms in various dynamic scenarios. This deficiency leads to a gap in our understanding and capability to effectively design algorithms for clustering in dynamic environments. To bridge this gap, this paper introduces the Dynamic Dataset Generator (DDG). DDG features multiple dynamic Gaussian components integrated with a range of heterogeneous, local, and global changes. These changes vary in spatial and temporal severity, patterns, and domain of influence, providing a comprehensive tool for simulating a wide range of dynamic scenarios.

The split delivery vehicle routing problem with three-dimensional loading constraints (3L-SDVRP) extends the traditional capacitated vehicle routing problem by integrating vehicle routing and three-dimensional packing, thus increasing the overall complexity of the problem. The interaction between routing and packing is crucial to the efficacy of any solution method for 3L-SDVRP. However, conventional approaches such as packing first routing second (P1R2) and routing first packing second (R1P2) exhibit limitations in computational efficiency and adaptability. Based on current strategies, we propose a interactive routing-packing strategy that adaptively decides between loading a single node or two nodes together during the routing. By allowing independent node loading, our method enables the generation of a loading plan prior to routing, thereby eliminating the need for repetitive solving packing sub-problem---an advantage similar to the P1R2 paradigm. Conversely, loading two nodes together requires immediate packing adjustments and helps to reduce the number of vehicles needed---a benefit akin to the R1P2. Our strategy integrates the strengths of both P1R2 and R1P2, thereby achieving enhanced loading flexibility and computational efficiency. Experimental results demonstrate that our methodology outperforms existing strategies regarding vehicle count.

Deep reinforcement learning has recently been successfully applied to online procedural content generation in which a policy determines promising game-level segments. However, existing methods can hardly discover diverse level patterns, while the lack of diversity makes the gameplay boring. This paper proposes an ensemble reinforcement learning approach that uses multiple negatively correlated sub-policies to generate different alternative level segments, and stochastically selects one of them following a selector model. A novel policy regularisation technique is integrated into the approach to diversify the generated alternatives. In addition, we develop theorems to provide general methodologies for optimising policy regularisation in a Markov decision process. The proposed approach is compared with several state-of-the-art policy ensemble methods and classic methods on a well-known level generation benchmark, with two different reward functions expressing game-design goals from different perspectives. Results show that our approach boosts level diversity notably with competitive performance in terms of the reward. Furthermore, by varying the regularisation coefficient, the trained generators form a well-spread Pareto front, allowing explicit trade-offs between diversity and rewards of generated levels.

Nowadays, neural network (NN) and deep learning (DL) techniques are widely adopted in many applications, including recommender systems. Given the sparse and stochastic nature of collaborative filtering (CF) data, recent works have critically analyzed the effective improvement of neural-based approaches compared to simpler and often transparent algorithms for recommendation. Previous results showed that NN and DL models can be outperformed by traditional algorithms in many tasks. Moreover, given the largely black-box nature of neural-based methods, interpretable results are not naturally obtained. Following on this debate, we first present a transparent probabilistic model that topologically organizes user and product latent classes based on the review information. In contrast to popular neural techniques for representation learning, we readily obtain a statistical, visualization-friendly tool that can be easily inspected to understand user and product characteristics from a textual-based perspective. Then, given the limitations of common embedding techniques, we investigate the possibility of using the estimated interpretable quantities as model input for a rating prediction task. To contribute to the recent debates, we evaluate our results in terms of both capacity for interpretability and predictive performances in comparison with popular text-based neural approaches. The results demonstrate that the proposed latent class representations can yield competitive predictive performances, compared to popular, but difficult-to-interpret approaches.

Federated learning (FL) offers a machine learning paradigm that protects privacy, allowing multiple clients to collaboratively train a global model while only accessing their local data. Recent research in FL has increasingly focused on improving the uniformity of model performance across clients, a fairness principle known as egalitarian fairness. However, achieving egalitarian fairness in FL may sacrifice the model performance for data-rich clients to benefit those with less data. This trade-off raises concerns about the stability of FL, as data-rich clients may opt to leave the current coalition and join another that is more closely aligned with its expected high performance. In this context, our work rigorously addresses the critical concern: **Does egalitarian fairness lead to instability?** Drawing from game theory and social choice theory, we initially characterize fair FL systems as altruism coalition formation games (ACFGs) and reveal that the instability issues emerging from the pursuit of egalitarian fairness are significantly related to the clients’ altruism within the coalition and the configuration of the friends-relationship networks among the clients. Then, we theoretically propose the optimal egalitarian fairness bounds that an FL coalition can achieve while maintaining core stability under various types of altruistic behaviors. The theoretical contributions clarify the quantitative relationships between achievable egalitarian fairness and the disparities in the sizes of local datasets, disproving the misconception that egalitarian fairness inevitably leads to instability. Finally, we conduct experiments to evaluate the consistency of our theoretically derived egalitarian fairness bounds with the empirically achieved egalitarian fairness in fair FL settings.

Text-to-Image (T2I) has witnessed significant advancements, demonstrating superior performance for various generative tasks. However, the presence of stereotypes in T2I introduces harmful biases that require urgent attention as the T2I technology becomes more prominent. Previous work for stereotype mitigation mainly concentrated on mitigating stereotypes engendered with individual objects within images, which failed to address stereotypes engendered by the association of multiple objects, referred to as *Association-Engendered Stereotypes*. For example, mentioning ''black people'' and ''houses'' separately in prompts may not exhibit stereotypes. Nevertheless, when these two objects are associated in prompts, the association of ''black people'' with ''poorer houses'' becomes more pronounced. To tackle this issue, we propose a novel framework, MAS, to Mitigate Association-engendered Stereotypes. This framework models the stereotype problem as a probability distribution alignment problem, aiming to align the stereotype probability distribution of the generated image with the stereotype-free distribution. The MAS framework primarily consists of the *Prompt-Image-Stereotype CLIP* (*PIS CLIP*) and *Sensitive Transformer*. The *PIS CLIP* learns the association between prompts, images, and stereotypes, which can establish the mapping of prompts to stereotypes. The *Sensitive Transformer* produces the sensitive constraints, which guide the stereotyped image distribution to align with the stereotype-free probability distribution. Moreover, recognizing that existing metrics are insufficient for accurately evaluating association-engendered stereotypes, we propose a novel metric, *Stereotype-Distribution-Total-Variation*(*SDTV*), to evaluate stereotypes in T2I. Comprehensive experiments demonstrate that our framework effectively mitigates association-engendered stereotypes.

Large Language Models (LLMs) have demonstrated remarkable capabilities, surpassing human experts in various benchmark tests and playing a vital role in various industry sectors. Despite their effectiveness, a notable drawback of LLMs is their inconsistent moral behavior, which raises ethical concerns. This work delves into symmetric moral consistency in large language models and demonstrates that modern LLMs lack sufficient consistency ability in moral scenarios. Our extensive investigation of twelve popular LLMs reveals that their assessed consistency scores are influenced by position bias and selection bias rather than their intrinsic abilities. We propose a new framework tSMC, which gauges the effects of these biases and effectively mitigates the bias impact based on the Kullback–Leibler divergence to pinpoint LLMs' mitigated Symmetric Moral Consistency. We find that the ability of LLMs to maintain consistency varies across different moral scenarios. Specifically, LLMs show more consistency in scenarios with clear moral answers compared to those where no choice is morally perfect. The average consistency score of 12 LLMs ranges from $60.7\%$ in high-ambiguity moral scenarios to $84.8\%$ in low-ambiguity moral scenarios.

Abstract The split delivery vehicle routing problem with three-dimensional loading constraints (3L-SDVRP) intertwines complex routing and packing challenges. The current study addresses 3L-SDVRP using intelligent optimization algorithms, which iteratively evolve towards optimal solutions. A pivotal aspect of these algorithms is search operators that determine the search direction and the search step size. Effective operators significantly improve algorithmic performance. Traditional operators like swap, shift, and 2-opt fall short in complex scenarios like 3L-SDVRP, mainly due to their limited capacity to leverage domain knowledge. Additionally, the search step size is crucial: smaller steps enhance fine-grained search (exploitation), while larger steps facilitate exploring new areas (exploration). However, optimally balancing these step sizes remains an unresolved issue in 3L-SDVRP. To address this, we introduce an adaptive knowledge-guided insertion (AKI) operator. This innovative operator uses node distribution characteristics for adaptive node insertion, enhancing search abilities through domain knowledge integration and larger step sizes. Integrating AKI with the local search framework, we develop an adaptive knowledge-guided search (AKS) algorithm, which effectively balances exploitation and exploration by combining traditional neighbourhood operators for detailed searches with the AKI operator for broader exploration. Our experiments demonstrate that the AKS algorithm significantly outperforms the state-of-the-art method in solving various 3L-SDVRP instances.

We propose a new adversarial training framework -- generative adversarial ranking networks (GARNet) to learn from user preferences among a list of samples so as to generate data meeting user-specific criteria. Verbosely, GARNet consists of two modules: a ranker and a generator. The generator fools the ranker to raise generated samples to the top; while the ranker learns to rank generated samples at the bottom. Meanwhile, the ranker learns to rank samples regarding the interested property by training with preferences collected on real samples. The adversarial ranking game between the ranker and the generator enables an alignment between the generated data distribution and the user-preferred data distribution with theoretical guarantees and empirical verification. Specifically, we first prove that when training with full preferences on a discrete property, the learned distribution of GARNet rigorously coincides with the distribution specified by the given score vector based on user preferences. The theoretical results are then extended to partial preferences on a discrete property and further generalized to preferences on a continuous property. Meanwhile, numerous experiments show that GARNet can retrieve the distribution of user-desired data based on full/partial preferences in terms of various interested properties (i.e., discrete/continuous property, single/multiple properties). Code is available at https://github.com/EvaFlower/GARNet.

Abstract Real-world datasets inevitably contain biases that arise from different sources or conditions during data collection. Consequently, such inconsistency itself acts as a confounding factor that disturbs the cluster analysis. Existing methods eliminate the biases by projecting data onto the orthogonal complement of the subspace expanded by the confounding factor before clustering. Therein, the interested clustering factor and the confounding factor are coarsely considered in the raw feature space, where the correlation between the data and the confounding factor is ideally assumed to be linear for convenient solutions. These approaches are thus limited in scope as the data in real applications is usually complex and non-linearly correlated with the confounding factor. This paper presents a new clustering framework named Sanitized Clustering Against confounding Bias, which removes the confounding factor in the semantic latent space of complex data through a non-linear dependence measure. To be specific, we eliminate the bias information in the latent space by minimizing the mutual information between the confounding factor and the latent representation delivered by variational auto-encoder. Meanwhile, a clustering module is introduced to cluster over the purified latent representations. Extensive experiments on complex datasets demonstrate that our SCAB achieves a significant gain in clustering performance by removing the confounding bias.

Explainable artificial intelligence (XAI) has gained significant attention, especially in AI-powered autonomous and adaptive systems (AASs). However, a discernible disconnect exists among research efforts across different communities. The machine learning community often overlooks “explaining to whom,” while the human-computer interaction community has examined various stakeholders with diverse explanation needs without addressing which XAI methods meet these requirements. Currently, no clear guidance exists on which XAI methods suit which specific stakeholders and their distinct needs. This hinders the achievement of the goal of XAI: providing human users with understandable interpretations. To bridge this gap, this article presents a comprehensive XAI roadmap. Based on an extensive literature review, the roadmap summarizes different stakeholders, their explanation needs at different stages of the AI system lifecycle, the questions they may pose, and existing XAI methods. Then, by utilizing stakeholders’ inquiries as a conduit, the roadmap connects their needs to prevailing XAI methods, providing a guideline to assist researchers and practitioners to determine more easily which XAI methodologies can meet the specific needs of stakeholders in AASs. Finally, the roadmap discusses the limitations of existing XAI methods and outlines directions for future research.

Gridless methods show great superiority in line spectral estimation. These methods need to solve an atomic$l_{0}$norm (i.e., the continuous analog of$l_{0}$norm) minimization problem to estimate frequencies and model order. Since this problem is NP-hard to compute, relaxations of the atomic$l_{0}$norm, such as the nuclear norm and reweighted atomic norm, have been employed for promoting sparsity. However, the relaxations give rise to a resolution limit, subsequently leading to biased model order and convergence error. To overcome the above shortcomings of relaxation, we propose a novel idea of simultaneously estimating the frequencies and model order using the atomic$l_{0}$norm. To accomplish this idea, we build a multiobjective optimization model. The measurement error and the atomic$l_{0}$norm are taken as the two optimization objectives. The proposed model directly exploits the model order via the atomic$l_{0}$norm, thus breaking the resolution limit. We further design a variable-length evolutionary algorithm to solve the proposed model, which includes two innovations. One is a variable-length coding and search strategy. It flexibly codes and interactively searches diverse solutions with different model orders. These solutions act as steppingstones that helpfully exploring the variable and open-ended frequency search space and provide extensive potentials toward the optima. Another innovation is a model-order pruning mechanism, which heuristically prunes less contributive frequencies within the solutions, thus significantly enhancing convergence and diversity. Simulation results confirm the superiority of our approach in both frequency estimation and model-order selection.

Engine calibration problems are black-box optimization problems which are evaluation costly and most of them are constrained in the objective space. In these problems, decision variables may have different impacts on objectives and constraints, which could be detected by sensitivity analysis. Most existing surrogate-assisted evolutionary algorithms do not analyze variable sensitivity, thus, useless effort may be made on some less sensitive variables. This article proposes a surrogate-assisted bilevel evolutionary algorithm to solve a real-world engine calibration problem. Principal component analysis is performed to investigate the impact of variables on constraints and to divide decision variables into lower-level and upper-level variables. The lower-level aims at optimizing lower-level variables to make candidate solutions feasible, and the upper-level focuses on adjusting upper-level variables to optimize the objective. In addition, an ordinal-regression-based surrogate is adapted to estimate the ordinal landscape of solution feasibility. Computational studies on a gasoline engine model demonstrate that our algorithm is efficient in constraint handling and also achieves a smaller fuel consumption value than other state-of-the-art calibration methods.

Many real-world problems are computationally costly and the objective functions evolve over time. Data-driven, a.k.a. surrogate-assisted, evolutionary optimization has been recognized as an effective approach to tackle expensive black-box optimization problems in a static environment whereas it has rarely been studied under dynamic environments. This paper proposes a simple yet effective transfer learning framework to empower data-driven evolutionary optimization to solve expensive dynamic optimization problems. Specifically, a hierarchical multi-output Gaussian process is proposed to capture the correlation among data collected from different time steps with a linearly increased number of hyperparameters. Furthermore, an adaptive source task selection along with a bespoke warm staring initialization mechanisms are proposed to better leverage the knowledge extracted from previous optimization processes. By doing so, the data-driven evolutionary optimization can jump start the optimization in the new environment with a very limited computational budget. Experiments on synthetic benchmark test problems and a real-world case study demonstrate the effectiveness of our proposed algorithm in comparison with nine state-of-the-art peer algorithms.

Most multi-objective optimisation algorithms maintain an archive explicitly or implicitly during their search. Such an archive can be solely used to store high-quality solutions presented to the decision maker, but in many cases may participate in the search process (e.g., as the population in evolutionary computation). Over the last two decades, archiving, the process of comparing new solutions with previous ones and deciding how to update the archive/population, stands as an important issue in evolutionary multi-objective optimisation (EMO). This is evidenced by constant efforts from the community on developing various effective archiving methods, ranging from conventional Pareto-based methods to more recent indicator-based and decomposition-based ones. However, the focus of these efforts is on empirical performance comparison in terms of specific quality indicators; there is lack of systematic study of archiving methods from a general theoretical perspective. In this paper, we attempt to conduct a systematic overview of multi-objective archiving, in the hope of paving the way to understand archiving algorithms from a holistic perspective of theory and practice, and more importantly providing a guidance on how to design theoretically desirable and practically useful archiving algorithms. In doing so, we also present that archiving algorithms based on weakly Pareto compliant indicators (e.g., -indicator), as long as designed properly, can achieve the same theoretical desirables as archivers based on Pareto compliant indicators (e.g., hypervolume indicator). Such desirables include the property limit-optimal, the limit form of the possible optimal property that a bounded archiving algorithm can have with respect to the most general form of superiority between solution sets.

Unbalanced classification is an essential machine learning task, which has attracted widespread attention from both the academic and industrial communities due mainly to its broad applications. Evolutionary computation (EC) has contributed greatly to unbalanced classification. However, to the best of our knowledge, there have not been any comprehensive investigations on the strengths and weaknesses of alternative EC methods in addressing various challenging problems in unbalanced classification. This article reviews the literature which utilize EC techniques for unbalanced classification, with the aim of revealing the contributions of EC to unbalanced classification, providing an overview of recent advances, and identifying limitations of existing works. In addition, we present a series of real-world applications, and identify open challenges as well as possible research directions for the future.

Robust optimization over time (ROOT) is the combination of robust optimization and dynamic optimization. In ROOT, frequent changes to deployed solutions are undesirable, which can be due to the high cost of switching between deployed solutions, limitations on the resources required to deploy new solutions, and/or the system’s inability to tolerate frequent changes in the deployed solutions. ROOT is dedicated to the study and development of algorithms capable of dealing with the implications of deploying or maintaining solutions over longer time horizons involving multiple environmental changes. This paper presents an in-depth review of the research on ROOT. The overarching aim of this survey is to help researchers gain a broad perspective on the current state of the field, what has been achieved so far, and the existing challenges and pitfalls. This survey also aims to improve accessibility and clarity by standardizing terminology and unifying mathematical notions used across the field, providing explicit mathematical formulations of definitions, and improving many existing mathematical descriptions. Moreover, we classify ROOT problems based on two ROOT-specific criteria: the requirements for changing or keeping deployed solutions and the number of deployed solutions. This classification helps researchers gain a better understanding of the characteristics and requirements of ROOT problems, which is crucial to systematic algorithm design and benchmarking. Additionally, we classify ROOT methods based on the approach they use for finding robust solutions and provide a comprehensive review of them. This survey also reviews ROOT benchmarks and performance indicators. Finally, we identify several future research directions.

The feature attribution-based explanation (FAE) methods, which indicate how much each input feature contributes to the model’s output for a given data point, are one of the most popular categories of explainable machine learning techniques. Although various metrics have been proposed to evaluate the explanation quality, no single metric could capture different aspects of the explanations. Different conclusions might be drawn using different metrics. Moreover, during the processes of generating explanations, existing FAE methods either do not consider any evaluation metric or only consider the faithfulness of the explanation, failing to consider multiple metrics simultaneously. To address this issue, we formulate the problem of creating FAE explainable models as a multi-objective learning problem that considers multiple explanation quality metrics simultaneously. We first reveal conflicts between various explanation quality metrics, including faithfulness, sensitivity, and complexity. Then, we define the considered multi-objective explanation problem and propose a multi-objective feature attribution explanation (MOFAE) framework to address this newly defined problem. Subsequently, we instantiate the framework by simultaneously considering the explanation’s faithfulness, sensitivity, and complexity. Experimental results comparing with six state-of-the-art FAE methods on eight datasets demonstrate that our method can optimize multiple conflicting metrics simultaneously and can provide explanations with higher faithfulness, lower sensitivity, and lower complexity than the compared methods. Moreover, the results have shown that our method has better diversity, i.e., it provides various explanations that achieve different tradeoffs between multiple conflicting explanation quality metrics. Therefore, it can provide tailored explanations to different stakeholders based on their specific requirements.

Weakly supervised anomaly detection (WSAD) has gained increasing attention due to its core idea of enhancing the performance of unsupervised anomaly detection by leveraging prior knowledge from a limited number of labeled anomalies. In this article, we introduce a novel WSAD framework that surpasses current state-of-the-art methods in terms of accuracy, exhibits greater robustness to data uncertainty, and is more efficient in utilizing limited labeled anomalies. Our method is built upon twin fuzzy networks (TFN) that learn robust fuzzy if–then rules from a pairwise training set. TFN can extract informative prototypes of training instances, exploiting the very few labeled anomalies efficiently. A two-stage sequential training scheme, comprising fuzzy C-means clustering and interpolation consistency regularization, ensures that the fuzzy rules form a solid foundation for anomaly detection while improving TFN's generalization ability. The training process of TFN relies on closed-form optimization rather than gradient-based methods, leading to significantly faster training speeds. Comprehensive experiments conducted on numerous real-world datasets confirm the advantages of the TFN framework over existing alternatives.

AdaBoost approaches have been used for multi-class imbalance classification with an imbalance ratio measured on class sizes. However, such ratio would assign each training sample of the same class with the same weight, thus failing to reflect the data distribution within a class. We propose to incorporate the density information of training samples into the class imbalance ratio so that samples of the same class could have different weights. As one could use the entire training set to calculate the imbalance and density factors, the weight of a training sample resulting from the two factors remains static throughout the training epochs. However, static weights could not reflect the up-to-date training status of base learners. To deal with this, we propose to design an adaptive weighting mechanism by making use of up-to-date training status to further alleviate the multi-class imbalance issue. Ultimately, we incorporate the class imbalance ratio, the density-based factor, and the adaptive weighting mechanism into a single variable, based on which the adaptive weights of all training samples are computed. Experimental studies are carried out to investigate the effectiveness of the proposed approach and each of the three components in dealing with multi-class imbalance classification problem.

In light of the dynamic plasticity, nanosize, and energy efficiency of memristors, memristive reservoirs have attracted increasing attention in diverse fields of research recently. However, limited by deterministic hardware implementation, hardware reservoir adaptation is hard to realize. Existing evolutionary algorithms for evolving reservoirs are not designed for hardware implementation. They often ignore the circuit scalability and feasibility of the memristive reservoirs. In this work, based on the reconfigurable memristive units (RMUs), we first propose an evolvable memristive reservoir circuit that is capable of adaptive evolution for varying tasks, where the configuration signals of memristor are evolved directly avoiding the device variance of the memristors. Second, considering the feasibility and scalability of memristive circuits, we propose a scalable algorithm for evolving the proposed reconfigurable memristive reservoir circuit, where the reservoir circuit will not only be valid according to the circuit laws but also has the sparse topology, alleviating the scalability issue and ensuring the circuit feasibility during the evolution. Finally, we apply our proposed scalable algorithm to evolve the reconfigurable memristive reservoir circuits for a wave generation task, six prediction tasks, and one classification task. Through experiments, the feasibility and superiority of our proposed evolvable memristive reservoir circuit are demonstrated.

This article proposes differential-critic generative adversarial network (DiCGAN) to learn the distribution of user-desired data when only partial instead of the entire dataset possesses the desired property. DiCGAN generates desired data that meet the user's expectations and can assist in designing biological products with desired properties. Existing approaches select the desired samples first and train regular GANs on the selected samples to derive the user-desired data distribution. However, the selection of the desired data relies on global knowledge and supervision over the entire dataset. DiCGAN introduces a differential critic that learns from pairwise preferences, which are local knowledge and can be defined on a part of training data. The critic is built by defining an additional ranking loss over the Wasserstein GAN's critic. It endows the difference of critic values between each pair of samples with the user preference and guides the generation of the desired data instead of the whole data. For a more efficient solution to ensure data quality, we further reformulate DiCGAN as a constrained optimization problem, based on which we theoretically prove the convergence of our DiCGAN. Extensive experiments on a diverse set of datasets with various applications demonstrate that our DiCGAN achieves state-of-the-art performance in learning the user-desired data distributions, especially in the cases of insufficient desired data and limited supervision.

The multi-objective testing resource allocation problem (MOTRAP) is concerned on how to reasonably plan the testing time of software testers to save the cost and improve the reliability as much as possible. The feasible solution space of a MOTRAP is determined by its variables (i.e., the time invested in each component) and constraints (e.g., the pre-specified reliability, cost, or time). Although a variety of state-of-the-art constrained multi-objective optimisers can be used to find individual solutions in this space, their search remains inefficient and expensive due to the fact that this space is very tiny compared to the large search space. The decision maker may often suffer a prolonged but unsuccessful search that fails to return a feasible solution. In this work, we first formulate a heavily constrained MOTRAP on the basis of an architecture-based model, in which reliability, cost, and time are optimised under the pre-specified multiple constraints on reliability, cost, and time. Then, to estimate the feasible solution space of this specific MOTRAP, we develop theoretical and algorithmic approaches to deduce new tighter lower and upper bounds on variables from constraints. Importantly, our approach can help the decision maker identify whether their constraint settings are practicable, and meanwhile, the derived bounds can just enclose the tiny feasible solution space and help off-the-shelf constrained multi-objective optimisers make the search within the feasible solution space as much as possible. Additionally, to further make good use of these bounds, we propose a generalised bound constraint handling method that can be readily employed by constrained multi-objective optimisers to pull infeasible solutions back into the estimated space with theoretical guarantee. Finally, we evaluate our approach on application and empirical cases. Experimental results reveal that our approach significantly enhances the efficiency, effectiveness, and robustness of off-the-shelf constrained multi-objective optimisers and state-of-the-art bound constraint handling methods at finding high-quality solutions for the decision maker. These improvements may help the decision maker take the stress out of setting constraints and selecting constrained multi-objective optimisers and facilitate the testing planning more efficiently and effectively.

Multi-class imbalance learning usually confronts more challenges especially when learning from streaming data. Most existing methods focus on manipulating class imbalance ratios, disregarding other data properties such as the borderline and the disjunct. Recent studies have shown non-negligible impact of disregarding these properties on deteriorating predictive performance. Online multi-class imbalance would further exacerbate such negative impact. To abridge the research gap of online multi-class imbalance learning, we propose to enhance the number of training times of borderline samples based on the disjunct class-wise clusters that are adaptively constructed over time for each class individually. Specifically, we propose a borderline enhanced strategy for ensemble aiming to increase the number of training times of samples neighboring to borderline areas of different classes. We also propose to generate synthetic samples for training based on the adaptively learned disjunct clusters that are maintained for each class individually online, catering for online multi-class imbalance problem directly. These two components construct the Borderline Enhanced Disjunct Cluster Based Oversampling Ensemble (BEDCOE). Experimental studies are conducted and demonstrate the effectiveness of BEDCOE and each of its components in dealing with online multi-class imbalance.

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

Evolutionary algorithms have been used to evolve a population of actors to generate diverse experiences for training reinforcement learning agents, which helps to tackle the temporal credit assignment problem and improves the exploration efficiency. However, when adapting this approach to address constrained problems, balancing the trade-off between the reward and constraint violation is hard. In this paper, we propose a novel evolutionary constrained reinforcement learning (ECRL) algorithm, which adaptively balances the reward and constraint violation with stochastic ranking, and at the same time, restricts the policy's behaviour by maintaining a set of Lagrange relaxation coefficients with a constraint buffer. Extensive experiments on robotic control benchmarks show that our ECRL achieves outstanding performance compared to state-of-the-art algorithms. Ablation analysis shows the benefits of introducing stochastic ranking and constraint buffer.

As one of the core parts of flexible manufacturing systems, material handling involves storage and transportation of materials between workstations with automated vehicles. The improvement in material handling can impulse the overall efficiency of the manufacturing system. However, the occurrence of dynamic events during the optimisation of task arrangements poses a challenge that requires adaptability and effectiveness. In this paper, we aim at the scheduling of automated guided vehicles for dynamic material handling. Motivated by some real-world scenarios, unknown new tasks and unexpected vehicle breakdowns are regarded as dynamic events in our problem. We formulate the problem as a constrained Markov decision process which takes into account tardiness and available vehicles as cumulative and instantaneous constraints, respectively. An adaptive constrained reinforcement learning algorithm that combines Lagrangian relaxation and invalid action masking, named RCPOM, is proposed to address the problem with two hybrid constraints. Moreover, a gym-like dynamic material handling simulator, named DMH-GYM, is developed and equipped with diverse problem instances, which can be used as benchmarks for dynamic material handling. Experimental results on the problem instances demonstrate the outstanding performance of our proposed approach compared with eight state-of-the-art constrained and non-constrained reinforcement learning algorithms, and widely used dispatching rules for material handling.

Detecting whether a distribution shift has occurred in the dataset is a critical aspect when implementing machine learning models, as even a small shift in the data distribution may largely affect the performance of a machine learning model and thus cause the deployed model to fail. In this work, we focus on detecting harmful dataset shifts, i.e., shifts that are detrimental to the performance of the machine learning model. The existing methods usually detect whether there is a shift between two datasets according to the following framework: first carrying out dimensionality reduction on the datasets, then determining whether dataset shift exists according to the two-sample statistical test(s) on the reduced datasets. The knowledge contained in the model trained on the dataset is not utilized in the above described dataset shift detection framework. To address this, this paper proposes to take advantage of explainable artificial intelligence (XAI) techniques to exploit the knowledge in trained models when detecting harmful dataset shifts. Specifically, we employ the feature attribution explanation (FAE) method to capture the knowledge in the model and combine it with a widely-used two-sample test method, i.e., maximum mean difference (MMD), to detect harmful dataset shifts. The experimental results on more than twenty different shifts in three widely used image datasets demonstrate that the proposed method is more effective in identifying harmful dataset shifts than existing methods. Moreover, experiments on several different models show that the method is robust and effective over different models, i.e., its detection performance is not sensitive to the model used.

Deep learning models can be fooled by small$l_{p}$-norm adversarial perturbations and natural perturbations in terms of attributes. Although the robustness against each perturbation has been explored, it remains a challenge to address the robustness against joint perturbations effectively. In this paper, we study the robustness of deep learning models against joint perturbations by proposing a novel attack mechanism named Semantic-Preserving Adversarial (SPA) attack, which can then be used to enhance adversarial training. Specifically, we introduce an attribute manipulator to generate natural and human-comprehensible perturbations and a noise generator to generate diverse adversarial noises. Based on such combined noises, we optimize both the attribute value and the diversity variable to generate jointly-perturbed samples. For robust training, we adversarially train the deep learning model against the generated joint perturbations. Empirical results on four benchmarks show that the SPA attack causes a larger performance decline with small$l_{\infty}$norm-ball constraints compared to existing approaches. Furthermore, our SPA-enhanced training outperforms existing defense methods against such joint perturbations.

Just-in-Time Software Defect Prediction (JIT-SDP) can be seen as an online learning problem where additional software changes produced over time may be labeled and used to create training examples. These training examples form a data stream that can be used to update JIT-SDP models in an attempt to avoid models becoming obsolete and poorly performing. However, labeling procedures adopted in existing online JIT-SDP studies implicitly assume that practitioners would not inspect software changes upon a defect-inducing prediction, delaying the production of training examples. This is inconsistent with a real-world scenario where practitioners would adopt JIT-SDP models and inspect certain software changes predicted as defect-inducing to check whether they really induce defects. Such inspection means that some software changes would be labeled much earlier than assumed in existing work, potentially leading to different JIT-SDP models and performance results. This paper aims at formulating a more practical human labeling procedure that takes into account the adoption of JIT-SDP models during the software development process. It then analyses whether and to what extent it would impact the predictive performance of JIT-SDP models. We also propose a new method to target the labeling of software changes with the aim of saving human inspection effort. Experiments based on 14 GitHub projects revealed that adopting a more realistic labeling procedure led to significantly higher predictive performance than when delaying the labeling process, meaning that existing work may have been underestimating the performance of JIT-SDP. In addition, our proposed method to target the labeling process was able to reduce human effort while maintaining predictive performance by recommending practitioners to inspect software changes that are more likely to induce defects. We encourage the adoption of more realistic human labeling methods in research studies to obtain an evaluation of JIT-SDP predictive performance that is closer to reality.

Abstract Just-In-Time Software Defect Prediction (JIT-SDP) is concerned with predicting whether software changes are defect-inducing or clean. It operates in scenarios where labels of software changes arrive over time with delay, which in part corresponds to the time we wait to label software changes as clean (waiting time). However, clean labels decided based on waiting time may be different from the true labels of software changes, i.e., there may be label noise. This typically overlooked issue has recently been shown to affect the validity of continuous performance evaluation procedures used to monitor the predictive performance of JIT-SDP models during the software development process. It is still unknown whether this issue could potentially also affect evaluation procedures that rely on retrospective collection of software changes such as those adopted in JIT-SDP research studies, affecting the validity of the conclusions of a large body of existing work. We conduct the first investigation of the extent with which the choice of waiting time and its corresponding label noise would affect the validity of retrospective performance evaluation procedures. Based on 13 GitHub projects, we found that the choice of waiting time did not have a significant impact on the validity and that even small waiting times resulted in high validity. Therefore, (1) the estimated predictive performances in JIT-SDP studies are likely reliable in view of different waiting times, and (2) future studies can make use of not only larger (5k+ software changes), but also smaller (1k software changes) projects for evaluating performance of JIT-SDP models.

Reinforcement learning algorithms have performed well in playing challenging board and video games. More and more studies focus on improving the generalisation ability of reinforcement learning algorithms. The GVGAI Learning Competition aims to develop agents capable of learning to play different game levels that were unseen during training. This paper summarises the five years' GVGAI Learning Competition editions. At each edition, three new games were designed. The training and test levels were designed separately in the first three editions. Since 2020, three test levels of each game were generated by perturbing or combining two training levels. Then, we present a novel reinforcement learning technique with dual-observation for general video game playing, assuming that it is more likely to observe similar local information in different levels rather than global information. Instead of directly inputting a single, raw pixel-based screenshot of the current game screen, our proposed general technique takes the encoded, transformed global and local observations of the game screen as two simultaneous inputs, aiming at learning local information for playing new levels. Our proposed technique is implemented with three state-of-the-art reinforcement learning algorithms and tested on the game set of the 2020 GVGAI Learning Competition. Ablation studies show the outstanding performance of using encoded, transformed dual observations as input.

Audio recordings used as evidence have become increasingly important to litigation. Before their admissibility as evidence, an audio forensic expert is often required to help determine whether the submitted audio recordings are altered or authentic. Within this field, the copy-move forgery detection (CMFD), which focuses on finding possible forgeries that are derived from the same audio recording, has been an urgent problem in blind audio forensics. However, most of the existing methods require idealistic pre-segmentation and artificial threshold selection to calculate the similarity between segments, which may result in serious misleading and misjudgment especially on high frequency words. In this work, we present a robust method for detecting and locating an audio copy-move forgery on the basis of constant Q spectral sketches (CQSS) and the integration of a customised genetic algorithm (GA) and support vector machine (SVM). Specifically, the CQSS features are first extracted by averaging the logarithm of the squared-magnitude constant Q transform. Then, the CQSS feature set is automatically optimised by a customised GA combined with SVM to obtain the best feature subset and classification model at the same time. Finally, the integrated method, named CQSS-GA-SVM, is evaluated against the state-of-the-art approaches to blind detection of copy-move forgeries on real-world copy-move datasets with read English and Chinese corpus, respectively. The experimental results demonstrate that the proposed CQSS-GA-SVM exhibits significantly high robustness against post-processing based anti-forensics attacks and adaptability to the changes of the duplicated segment duration, the training set size, the recording length, and the forgery type, which may be beneficial to improving the work efficiency of audio forensic experts.

In practical multicriterion decision making, it is cumbersome if a decision maker (DM) is asked to choose among a set of tradeoff alternatives covering the whole Pareto-optimal front. This is a paradox in conventional evolutionary multiobjective optimization (EMO) that always aim to achieve a well balance between convergence and diversity. In essence, the ultimate goal of multiobjective optimization is to help a DM identify solution(s) of interest (SOI) achieving satisfactory tradeoffs among multiple conflicting criteria. Bearing this in mind, this article develops a framework for designing preference-based EMO algorithms to find SOI in an interactive manner. Its core idea is to involve human in the loop of EMO. After every several iterations, the DM is invited to elicit her feedback with regard to a couple of incumbent candidates. By collecting such information, her preference is progressively learned by a learning-to-rank neural network and then applied to guide the baseline EMO algorithm. Note that this framework is so general that any existing EMO algorithm can be applied in a plug-in manner. Experiments on 48 benchmark test problems with up to ten objectives and a real-world multiobjective robot control problem fully demonstrate the effectiveness of our proposed algorithms for finding SOI.

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

Many real-world optimization problems are dynamic. The field of robust optimization over time (ROOT) deals with dynamic optimization problems in which frequent changes of the deployed solution are undesirable. This can be due to the high cost of switching the deployed solutions, the limitation of the needed resources to deploy such new solutions, and/or the system being intolerant towards frequent changes of the deployed solution. In the considered ROOT problems in this article, the main goal is to find solutions that maximize the average number of environments where they remain acceptable. In the state-of-the-art methods developed to tackle these problems, the decision makers/metrics used to select solutions for deployment mostly make simplifying assumptions about the problem instances. Besides, the current methods all use the population control components which have been originally designed for tracking the global optimum over time without taking any robustness considerations into account. In this paper, a multi-population ROOT method is proposed with two novel components: a robustness estimation component that estimates robustness of the promising regions, and a dual-mode computational resource allocation component to manage sub-populations by taking several factors, including robustness, into account. Our experimental results demonstrate the superiority of the proposed method over other state-of-the-art approaches.

In the literature of mitigating unfairness in machine learning, many fairness measures are designed to evaluate predictions of learning models and also utilised to guide the training of fair models. It has been theoretically and empirically shown that there exist conflicts and inconsistencies among accuracy and multiple fairness measures. Optimising one or several fairness measures may sacrifice or deteriorate other measures. Two key questions should be considered, how to simultaneously optimise accuracy and multiple fairness measures, and how to optimise all the considered fairness measures more effectively. In this paper, we view the mitigating unfairness problem as a multi-objective learning problem considering the conflicts among fairness measures. A multi-objective evolutionary learning framework is used to simultaneously optimise several metrics (including accuracy and multiple fairness measures) of machine learning models. Then, ensembles are constructed based on the learning models in order to automatically balance different metrics. Empirical results on eight well-known datasets demonstrate that compared with the state-of-the-art approaches for mitigating unfairness, our proposed algorithm can provide decision-makers with better tradeoffs among accuracy and multiple fairness metrics. Furthermore, the high-quality models generated by the framework can be used to construct an ensemble to automatically achieve a better tradeoff among all the considered fairness metrics than other ensemble methods.

Dynamic time-linkage optimization problems (DTPs) are special dynamic optimization problems (DOPs) with the time-linkage property. The environment of DTPs changes not only over time but also depends on the previous applied solutions. DTPs are hardly solved by existing dynamic evolutionary algorithms because they ignore the time-linkage property. In fact, they can be viewed as multiple decision-making problems and solved by reinforcement learning (RL). However, only some discrete DTPs are solved by RL-based evolutionary optimization algorithms with the assumption of observable objective functions. In this work, we propose a dynamic evolutionary optimization algorithm using surrogate-assisted$Q$-learning for continuous black-box DTPs. To observe the states of black-box DTPs, the state extraction and prediction methods are applied after the search process at each time step. Based on the learned information, a surrogate-assisted$Q$-learning is introduced to evaluate and select candidate solutions in the continuous decision space in a long-term consideration. We evaluate the components of our proposed algorithm on various benchmark problems to study their behaviors. Results of comparative experiments indicate that the proposed algorithm outperforms other compared algorithms and performs robustly on DTPs with up to 30 decision variables and different dynamic changes.

Population clustering methods, which consider the position and fitness of individuals to form sub-populations in multi-population algorithms, have shown high efficiency in tracking the moving global optimum in dynamic optimization problems. However, most of these methods use a fixed population size, making them inflexible and inefficient when the number of promising regions is unknown. The lack of a functional relationship between the population size and the number of promising regions significantly degrades performance and limits an algorithm’s agility to respond to dynamic changes. To address this issue, we propose a new species-based particle swarm optimization with adaptive population size and number of sub-populations for solving dynamic optimization problems. The proposed algorithm also benefits from a novel systematic adaptive deactivation component that, unlike the previous deactivation components, adapts the computational resource allocation to the sub-populations by considering various characteristics of both the problem and the sub-populations. We evaluate the performance of our proposed algorithm for the Generalized Moving Peaks Benchmark and compare the results with several peer approaches. The results indicate the superiority of the proposed method.

In a streaming environment, the characteristics of the data themselves and their relationship with the labels are likely to experience changes as time goes on. Most drift detection methods for supervised data streams are performance-based, that is, they detect changes only after the classication accuracy deteriorates. This may not be sufcient in many application areas where the reason behind a drift is also important. Another category of drift detectors are data distribution-based detectors. Although they can detect some drifts within the input space, changes affecting only the labelling mechanism cannot be identied. Furthermore, little work is available on drift detection for high-dimensional supervised data streams. In this paper we propose an advanced Hierarchical Reduced-space Drift Detection Framework for Supervised Data Streams (HRDS) which captures drifts regardless of their effects on classication performance. This framework suggests monitoring both marginal and class-conditional distributions within a lower-dimensional space specically relevant to the assigned classication task. Experimental comparisons have demonstrated that the proposed HRDS not only achieves high-quality performance on high-dimensional data streams, but also outperforms its competitors in terms of detection recall, precision and F-measure across a wide range of different concept drift types including subtle drifts.

In recent years, learning from streaming data, commonly known as stream learning, has enjoyed tremendous growth and shown a wealth of development at both the conceptual and application levels. Stream learning is highly visible in both the machine learning and data science fields and has become a hot new direction in research. Advancements in stream learning include learning with concept drift detection, that includes whether a drift has occurred; understanding where, when, and how a drift occurs; adaptation by actively or passively updating models; and online learning, active learning, incremental learning, and reinforcement learning in data streaming situations.

Brain-inspired computing takes inspiration from the brain to create energy-efficient hardware systems for information processing, capable of performing highly sophisticated tasks. Systems built with emerging electronics, such as memristive devices, can achieve gains in speed and energy by mimicking the distributed topology of the brain. In this work, a brain-inspired hardware architecture for evolutionary algorithms is proposed based on memristive arrays, which can realize sparse and approximate computing as a result of the parallel analog computing characteristic of the memristive arrays. On this basis, an efficient evolvable brain-inspired hardware system is implemented. We experimentally show that the approach can offer at least a four orders of magnitude speed improvement. We also use experimentally grounded simulations to explore fault tolerance and different parameter settings in the implemented hardware system. The experimental results show that the evolvable hardware system, implemented based on the proposed hardware architecture, can continuously evolve toward a better system even if there are failures or parameter changes in the memristive arrays, demonstrating that the proposed hardware architecture has good adaptability and fault tolerance.

The multi-objective testing resource allocation problem (MOTRAP) aims at seeking a good trade-off between system reliability, testing cost, and testing time, which is of significant importance to facilitate the testing planning. Yet most studies focus on the time constraint but rarely consider the practical reliability requirement. In this work, we address MOTRAP on an architecture-based model (ABM) with the personalized preference over reliability. More specifically, we first present a reliability-constrained MOTRAP model on the basis of ABM and illustrate how to use this model for real-world systems. Then, to leverage the problem's knowledge, we develop new lower and upper bounds on testing time invested in different components from both theoretical and algorithmic perspectives on the basis of the Lagrange multiplier and half-interval search. Importantly, these new derived bounds have strong implications due to the fact that they can be easily employed by optimizers as the limits of variables to prune the search space to the region of interests of the decision maker and locate feasible solutions with the expected reliability. Finally, we evaluate the proposed bounds in popular multi-objective optimizers for MOTRAP on application and empirical cases. Experimental results demonstrate that our new bounds practically improve the search performance of optimizers, and decision makers can easily combine these new bounds with off-the-shelf optimizers to find higher-quality solutions that they are interested in, which greatly soothes away stress on optimizer and solution selections of decision makers.

The dynamic capacitated arc routing problem (DCARP) aims at re-scheduling the service plans of agents, such as vehicles in a city scenario, when dynamic events deteriorate the quality of the current schedule. Various algorithms have been proposed to solve DCARP instances in different dynamic scenarios. However, most existing work evaluated their algorithms' performance based on artificially constructed dynamic environments instead of using more realistic traffic simulations which are built on actual traffic data. In this paper, we constructed a novel DCARP benchmarking framework based on the Simulation of Urban MObility (SUMO) transportation simulation software, which allows to include real-world traffic environments for generating a set of DCARP instances from dynamic events, such as road congestion or task changes. The flexibility of the framework allows to develop DCARP optimization algorithms and evaluate their effectiveness more comprehensively. We use the benchmarking framework to generate 12 different dynamic instances using real-world traffic data of Dublin City. We then demonstrate the value of our framework by using these instances to compare our previously proposed hybrid local search algorithm (HyLS) with a state-of-the-art meta-heuristic optimization algorithm. The generated benchmark scenarios indicate that HyLS is a very effective optimizer on DCARP scenarios with real traffic data for reducing the total service cost. They also demonstrate the importance of our DCARP benchmarking framework for the development and benchmarking of optimization algorithms in more realistic scenarios.

Dynamic multi-objective optimization problems (DMOPs) are widely accepted to be more challenging than stationary problems due to the time-dependent nature of the objective functions and/or constraints. Evaluation of purpose-built algorithms for DMOPs is often performed on narrow selections of dynamic instances with differing change magnitude and frequency or a limited selection of problems. In this paper, we focus on the reproducibility of simulation experiments for parameters of DMOPs. Our framework is based on an extension of PlatEMO, allowing for the reproduction of results and performance measurements across a range of dynamic settings and problems. A baseline schema for dynamic algorithm evaluation is introduced, which provides a mechanism to interrogate performance and optimization behaviours of well-known evolutionary algorithms that were not designed specifically for DMOPs. Importantly, by determining the maximum capability of non-dynamic multi-objective evolutionary algorithms, we can establish the minimum capability required of purpose-built dynamic algorithms to be useful. The simplest modifications to manage dynamic changes introduce diversity. Allowing non-dynamic algorithms to incorporate mutated/random solutions after change events determines the improvement possible with minor algorithm modifications. Future expansion to include current dynamic algorithms will enable reproduction of their results and verification of their abilities and performance across DMOP benchmark space.

The Capacitated Arc Routing Problem (CARP) aims at assigning vehicles to serve tasks which are located at different arcs in a graph. However, the originally planned routes are easily affected by different dynamic events like newly added tasks. This gives rise to Dynamic CARP (DCARP) instances, which need to be efficiently optimized for new high-quality service plans in a short time. However, it is unknown which dynamic events make DCARP instances especially hard to solve. Therefore, in this paper, we provide an investigation of the influence of different dynamic events on DCARP instances from the perspective of fitness landscape analysis based on a recently proposed hybrid local search (HyLS) algorithm. We generate a large set of DCARP instances based on a variety of dynamic events and analyze the fitness landscape of these instances using several different measures such as fitness correlation length. From the empirical results we conclude that cost-related events have no significant impact on the difficulty of DCARP instances, but instances which require more new vehicles to serve the remaining tasks are harder to solve. These insights improve our understanding of the DCARP instances and pave the way for future work on improving the performance of DCARP algorithms.

Recently, learned image compression methods have shown their outstanding rate-distortion performance when compared to traditional frameworks. Although numerous progress has been made in learned image compression, the computation cost is still at a high level. To address this problem, we propose AdderIC, which utilizes adder neural networks (AdderNet) to construct an image compression framework. According to the characteristics of image compression, we introduce several strategies to improve the performance of AdderNet in this field. Specifically, Haar Wavelet Transform is adopted to make AdderIC learn high-frequency information efficiently. In addition, implicit deconvolution with the kernel size of 1 is applied after each adder layer to reduce spatial redundancies. Moreover, we develop a novel Adder-ID-PixelShuffle cascade upsampling structure to remove checkerboard artifacts. Experiments demonstrate that our AdderIC model can largely outperform conventional AdderNet when applied in image compression and achieve comparable rate-distortion performance to that of its CNN baseline with about 80% multiplication FLOPs and 30% energy consumption reduction.

Traditional methods for solving problems within computer science rely mostly upon the application of handcrafted algorithms. As however manual engineering of them can be considered to be a tedious process, it is interesting to consider how far internal mechanisms can be directly learned in an end-to-end manner instead. This is especially tempting to consider for metaheuristic and evolutionary optimization routines which inherently rely upon creating abundant amounts of data during run-time. To implement such an approach for these types of algorithms, it effectively requires a pipeline to first acquire deran-domized algorithm components in a domain-dependent manner and secondly a mapping to select them based upon characteristic features which unveil the black box character of an optimization problem. While in principle, within our prior work we proposed methods for extracting spatial features from metadata, these unfortunately fail to acknowledge the time-dependent nature of it. Thus, fail in scenarios when the inputs generated from initial iterations are not expressive enough. For this reason we specifically develop within this work architectures for spatio-temporal data processing. Particularly, we find that our proposed GCN-GRU and LSTM architectures, which take inspiration from CNN-LSTMs originally proposed for activity recognition in multimedia data-streams, demonstrate high efficiency and most consistent performance on time series of variable length. Further, we can also demonstrate that the class activation map (CAM) for interpretable learning with time series data helps to understand and reflects problem-dependent properties of the search behavior of an optimization algorithm.

The extensive use of artificial intelligence (AI) in the real world brings some potential risks due to the undesirable behavior exhibited by AI systems using data-driven machine learning (ML) at their cores. Thus, preventing undesirable behaviors of ML, such as opacity (lack of transparency and explainability), unfairness (bias or discrimination), unsafety and insecurity, privacy disclosure, etc., is an imperative and pressing challenge. This work proposes an evolutionary constrained learning (ECL) framework for constructing ML models that can satisfy behavioral constraints so that the undesirable behaviors can be prevented. To evaluate our framework, we use it to create neural network models that preclude the undesirable behavior (that is, unfairness) on different benchmark datasets. The experimental results demonstrate the effectiveness of our proposed ECL approach for preventing undesirable behaviors of ML.

Recent advancements in machine learning comprise generative models such as autoencoders (AE) for learning and compressing 3D data to generate low-dimensional latent representations of 3D shapes. Learning latent representations that disentangle the underlying factors of variations in 3D shapes is an intuitive way to achieve generalization in generative models. However, it remains an open problem to learn a generative model of 3D shapes such that the latent variables are disentangled and represent different interpretable aspects of 3D shapes. In this paper, we propose Split-AE, which is an autoencoder-based architecture for partitioning the latent space into two sets, named as content and style codes. The content code represents global features of 3D shapes to differentiate between semantic categories of shapes, while style code represents distinct visual features to differentiate between shape categories having similar semantic meaning. We present qualitative and quantitative experiments to verify feature disentanglement using our Split-AE. Further, we demonstrate that, given a source shape as an initial shape and a target shape as a style reference, the trained Split-AE combines the content of a source and style of a target shape to generate a novel augmented shape, that possesses the distinct features of the target shape category yet maintains the similarity of the global features with the source shape. We conduct a qualitative study showing that the augmented shapes exhibit a realistic interpretable mixture of content and style features across different shape classes with similar semantic meaning.

Many real-world data stream applications suffer from verification latency, where the labels of the training examples arrive with a delay. In binary classification problems, the labeling process frequently involves waiting for a pre-determined period of time to observe an event that assigns the example to a given class. Once this time passes, if such labeling event does not occur, the example is labeled as belonging to the other class. For example, in software defect prediction, one may wait to see if a defect is associated to a software change implemented by a developer, producing a defect-inducing training example. If no defect is found during the waiting time, the training example is labeled as clean. Such verification latency inherently causes label noise associated to insufficient waiting time. For example, a defect may be observed only after the pre-defined waiting time has passed, resulting in a noisy example of the clean class. Due to the nature of the waiting time, such noise is frequently one-sided, meaning that it only occurs to examples of one of the classes. However, no existing work tackles label noise associated to verification latency. This paper proposes a novel data stream learning approach that estimates the confidence in the labels assigned to the training examples and uses this to improve predictive performance in problems with one-sided label noise. Our experiments with 14 real-world datasets from the domain of software defect prediction demonstrate the effectiveness of the proposed approach compared to existing ones.

Time Delay Reservoir (TDR) is a hardware-friendly machine learning approach from two perspectives. First, it can prevent the connection overhead of neural networks with increasing neurons. Second, through its dynamic system representation, TDR can also be implemented in hardware by different systems. However, it performs poorly on tasks that involve long-term dependency. In this work, we first introduce a higher-order delay unit, which is capable of accumulating and transferring the long history states in an adaptive manner to further enhance the reservoir memory. Particle Swarm Optimisation is applied to optimize the enhanced degree of memory adaptivity. Our experiments demonstrate its superiority both for short- and long-term memory datasets over seven existing approaches. In light of the hardware-friendly feature of TDR, we further propose a memristive implementation of our adaptive memory-enhanced TDR, where a dynamic memristor and the memristor-based delay element are applied to construct the reservoir. Through circuit simulation, the feasibility of our proposed memristive implementation is verified. The comparisons with different hardware reservoirs show that our proposed memristive implementation is effective both for short- and long-term memory datasets, while exhibiting benefits in terms of smaller circuit area and lower power consumption compared with traditional hardware reservoirs.

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.

We propose a new framework of computing-inspired multifocal cancer detection procedure (MCDP). Under the rubric of MCDP, the tumor foci to be detected are regarded as solutions of the objective function, the tissue region around the cancer areas represents the parameter space, and the nanorobots loaded with contrast medium molecules for cancer detection correspond to the optimization agents. The process that the nanorobots detect tumors by swimming in the high-risk tissue region can be regarded as the process that the agents search for the solutions of an objective function in the parameter space with some constraints. For multimodal optimization (MMO) aiming to locate multiple optimal solutions in a single simulation run, the niche technology has been widely used. Specifically, the niche genetic algorithm (NGA) has been shown to be particularly effective in solving MMO. It can be used to identify the global optima of multiple hump functions in a running, effectively keep the diversity of the population, and prematurely avoid the genetic algorithm. Learning from the optimization procedure of NGA, we propose the NGA-inspired MCDP in order to locate the tumor targets efficiently while taking into account realistic in vivo propagation and controlling of nanorobots, which is different from the use scenario of the standard NGA. To improve the performance of the MCDP, we also modify the crossover operator of the original NGA from crossing within a population to crossing between two populations. Finally, we present comprehensive numerical examples to demonstrate the effectiveness of the NGA-inspired MCDP when the biological objective function is associated with the blood flow velocity profile caused by tumor-induced angiogenesis.

Several evolution strategies for in vivo computation are proposed with the aim of realizing tumor sensitization and targeting (TST) by externally manipulable nanoswimmers. In such targeting systems, nanoswimmers assembled by magnetic nanoparticles are externally manipulated to search for the tumor in the high-risk tissue by a rotating magnetic field produced by a coil system. This process can be interpreted as in vivo computation, where the tumor in the high-risk tissue corresponds to the global maximum or minimum of the in vivo optimization problem, the nanoswimmers are seen as the computational agents, the tumor-triggered biological gradient field (BGF) is used for fitness evaluation of the agents, and the high-risk tissue is the search space. Considering that the state-of-the-art magnetic nanoswimmer control method can only actuate all the nanoswimmers heading in the same direction simultaneously, we introduce the orthokinetic movement strategies into the agent location updating in the existing swarm intelligence algorithms. Especially, the gravitational search algorithm (GSA) is revisited and the corresponding in vivo optimization algorithm called orthokinetic GSA (OGSA) is proposed to carry out the TST. Furthermore, to determine the direction of the orthokinetic agent movement in every iteration of the operation, we propose several strategies according to the fitness ranking of the nanoswimmers in the BGF. To verify the superiority of the OGSA and choose the optimal evolution strategy, some numerical experiments are presented and compared with that of the brute-force search, which represents the traditional method for TST. It is found that the TST performance can be improved by the weak priority evolution strategy (WP-ES) in most of the scenarios.

By modeling the tumor sensitization and targeting (TST) as a natural computational process, we have proposed the framework of nanorobots-assisted in vivo computation. The externally manipulable nanorobots are steered to detect the tumor in the high-risk tissue, which is analogous to the process of searching for the optimal solution by the computing agents in the search space. To overcome the constraint of a nanorobotic platform that can only generate a uniform magnetic field to actuate the nanorobots, we have proposed the weak priority evolution strategy (WP-ES) in our previous works. However, these works do not consider the proportions of the nanorobot control and tracking operations, which are part and parcel of in vivo computation as the control operation aims at searching for the tumor effectively while the tracking mode is used for gathering information about the biological gradient function (BGF). Careful planning about the durations spent in these operations is needed for optimal performance of the TST strategy. To account for this issue, in the current article, we propose a novel computational principle, called the tension-relaxation (T-R) principle, to balance the displacements of nanorobots during each control and tracking cycle. Furthermore, we build three tumor vascular models with different sizes to represent three different targeting regions as the morphology of tumor vasculature determined by the tumor growth process is an important factor affecting TST. We carry out the computational experiments for tumors with three different sizes for several representative landscapes by introducing the T-R principle into the WP-ES-based swarm intelligence algorithms and considering the realistic internal constraints. The experimental outcomes demonstrate the effectiveness of the proposed TST strategy.

Dynamic changes are an important and inescapable aspect of many real-world optimization problems. Designing algorithms to find and track desirable solutions while facing challenges of dynamic optimization problems is an active research topic in the field of swarm and evolutionary computation. To evaluate and compare the performance of algorithms, it is imperative to use a suitable benchmark that generates problem instances with different controllable characteristics. In this article, we give a comprehensive review of existing benchmarks and investigate their shortcomings in capturing different problem features. We then propose a highly configurable benchmark suite, the generalized moving peaks benchmark, capable of generating problem instances whose components have a variety of properties, such as different levels of ill-conditioning, variable interactions, shape, and complexity. Moreover, components generated by the proposed benchmark can be highly dynamic with respect to the gradients, heights, optimum locations, condition numbers, shapes, complexities, and variable interactions. Finally, several well-known optimizers and dynamic optimization algorithms are chosen to solve generated problems by the proposed benchmark. The experimental results show the poor performance of the existing methods in facing new challenges posed by the addition of new properties.

Memetic algorithm (MA) is widely applied to optimize routing problems as it provides one way to combine local search with global search. However, the local search in MA needs to be carefully designed according to the problem’s characteristics. In this article, we consider a real-world large-scale waste collection problem with multiple depots, multiple disposal facilities, multiple trips, and working time constraints. Vehicles with a limited capacity and working time can start from different depots, collect waste at different sites, and make multiple trips to different disposal facilities to empty the waste and return to its origin. While the existing work considered problems with multiple trips and time constraints, none have tackled problems with multiple depots, multiple disposal facilities, multiple trips, as well as working time constraints. The change from “single-depot” to “multidepot” not only reflects better the situation in real life but also leads to a qualitative different and more complex problem. In this article, we first model this complex problem mathematically. Then, a novel region-focused MA is proposed to tackle this new challenge. Compared to classic MA, this region-focused one is enhanced by two major components: 1) a new heuristic-assisted solution initialization algorithm and 2) a region-focused local search with novel heuristics. Comprehensive computational studies show that our proposed approaches significantly outperform several state-of-the-arts on our real problem of thousands of tasks. The new local search procedure and solution initialization method significantly improve the search ability in combination with global search ability of MA.

Knee points, characterized as a small improvement on one objective can lead to a significant degradation on at least one of the other objectives, are attractive to decision makers (DMs) in multicriterion decision making. This article presents a simple and effective knee point identification (KPI) method to help DMs identify solution(s) of interest from a given set of tradeoff solutions thus facilitating posterior decision making. Our basic idea is to sequentially validate whether a solution is a knee point or not by comparing its localized tradeoff utility with others within its neighborhood characterized from a decomposition perspective. In particular, a solution is a knee point if and only if it has the best-localized tradeoff utility among its neighbors. We implement a GPU version that carries out the KPI in a parallel manner. This GPU version reduces the worst-case complexity from quadratic to linear. The performance of our proposed method is compared with five state-of-the-art KPI methods on 134 test problem instances and two real-world engineering design problems. Empirical results demonstrate its outstanding performance especially on problems with many local knee points. We further validate the usefulness of our proposed method for guiding evolutionary multiobjective optimization algorithms to search for knee points on the fly during the evolutionary process.

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.

Scalability of optimization algorithms is a major challenge in coping with the ever-growing size of optimization problems in a wide range of application areas from high-dimensional machine learning to complex large-scale engineering problems. The field of large-scale global optimization is concerned with improving the scalability of global optimization algorithms, particularly, population-based metaheuristics. Such metaheuristics have been successfully applied to continuous, discrete, or combinatorial problems ranging from several thousand dimensions to billions of decision variables. In this two-part survey, we review recent studies in the field of large-scale black-box global optimization to help researchers and practitioners gain a bird’s-eye view of the field, learn about its major trends, and the state-of-the-art algorithms. Part I of the series covers two major algorithmic approaches to large-scale global optimization: 1) problem decomposition and 2) memetic algorithms. Part II of the series covers a range of other algorithmic approaches to large-scale global optimization, describes a wide range of problem areas, and finally, touches upon the pitfalls and challenges of current research and identifies several potential areas for future research.

This article is the second part of a two-part survey series on large-scale global optimization. The first part covered two major algorithmic approaches to large-scale optimization, namely, decomposition methods and hybridization methods, such as memetic algorithms and local search. In this part, we focus on sampling and variation operators, approximation and surrogate modeling, initialization methods, and parallelization. We also cover a range of problem areas in relation to large-scale global optimization, such as multiobjective optimization, constraint handling, overlapping components, the component imbalance issue and benchmarks, and applications. The article also includes a discussion on pitfalls and challenges of the current research and identifies several potential areas of future research.

The capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem abstracted from many real-world applications, such as waste collection, road gritting, and mail delivery. However, few studies considered dynamic changes during the vehicles’ service, which can cause the original schedule infeasible or obsolete. The few existing studies are limited by the dynamic scenarios considered, and by overly complicated algorithms that are unable to benefit from the wealth of contributions provided by the existing CARP literature. In this article, we first provide a mathematical formulation of dynamic CARP (DCARP) and design a simulation system that is able to consider dynamic events while a routing solution is already partially executed. We then propose a novel framework which can benefit from the existing static CARP optimization algorithms so that they could be used to handle DCARP instances. The framework is very flexible. In response to a dynamic event, it can use either a simple restart strategy or a sequence transfer strategy that benefits from the past optimization experience. Empirical studies have been conducted on a wide range of DCARP instances to evaluate our proposed framework. The results show that the proposed framework significantly improves over state-of-the-art dynamic optimization algorithms.

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

With modern requirements, there is an increasing tendency of considering multiple objectives/criteria simultaneously in many Software Engineering (SE) scenarios. Such a multi-objective optimization scenario comes with an important issue — how to evaluate the outcome of optimization algorithms, which typically is a set of incomparable solutions (i.e., being Pareto nondominated to each other). This issue can be challenging for the SE community, particularly for practitioners of Search-Based SE (SBSE). On one hand, multi-objective optimization could still be relatively new to SE/SBSE researchers, who may not be able to identify the right evaluation methods for their problems. On the other hand, simply following the evaluation methods for general multi-objective optimization problems may not be appropriate for specific SBSE problems, especially when the problem nature or decision maker’s preferences are explicitly/implicitly known. This has been well echoed in the literature by various inappropriate/inadequate selection and inaccurate/misleading use of evaluation methods. In this paper, we first carry out a systematic and critical review of quality evaluation for multi-objective optimization in SBSE. We survey 717 papers published between 2009 and 2019 from 36 venues in seven repositories, and select 95 prominent studies, through which we identify five important but overlooked issues in the area. We then conduct an in-depth analysis of quality evaluation indicators/methods and general situations in SBSE, which, together with the identified issues, enables us to codify a methodological guidance for selecting and using evaluation methods in different SBSE scenarios.

Search operator design and parameter tuning are essential parts of algorithm design. However, they often involve trial-and-error and are very time-consuming. A new differential evolution (DE) algorithm with adaptive exploration and exploitation control (AEEC-DE) is proposed in this work to tackle this challenge. The proposed method improves the performance of DE by automatically selecting trial vector generation strategies (both mutation and crossover operators) and dynamically generating the associated control parameter values. A probability-based exploration and exploitation measurement is introduced to estimate whether the state of each newly generated individual is in exploration or exploitation. The state of historical individuals is used to assess the exploration and exploitation capabilities of different generation strategies and parameter values. Then, the strategies and parameters of DE are adapted following the common belief that evolutionary algorithms (EAs) should start with exploration and then gradually change into exploitation. The performance of AEEC-DE is evaluated through experimental studies on a set of test problems and compared with several state-of-the-art adaptive DE variants.

In the early design phase of automotive digital development, one of the key challenges for the designer is to consider multiple-criteria like aerodynamics and structural efficiency besides aesthetic aspects for designing a car shape. In our research, we imagine a cooperative design system in the automotive domain which provides guidance to the designer for finding sets of design options or well-performing designs for preferred search areas. In the present paper, we focus on two perspectives for this multi-criteria decision-making problem: First, a scenario without prior information about design preferences, where the designer aims to explore the search space for a diverse set of design alternatives. Second, a scenario where the designer has a prior intuition on preferred solutions of interest. For both scenarios, we assume that historic 3D car shape data exists, which we can utilize to learn a compact low-dimensional design representation based on a variational autoencoder (VAE). In contrast to evolutionary multi-objective optimization approaches where starting populations are randomly initialized, we propose to seed the population more efficiently by exploiting the advantage of linear interpolation in the latent space of the VAE. In our experiments, we demonstrate that the multi-objective optimization converges faster and achieves a diverse set of solutions. For the second scenario, when specifying design preferences by weights, we improve on the weighted-sum method, which simplifies the multi-objective problem and propose a strategy for efficiently adapting the weights towards the preferred design solution.

Many real-world applications have the time-linkage property, and the only theoretical analysis is recently given by Zheng, et al. (TEVC 2021) on their proposed time-linkage OneMax problem, OneMax(0,1n). However, only two elitist algorithms (1 + 1) EA and (μ + 1) EA are analyzed, and it is unknown whether the non-elitism mechanism could help to escape the local optima existed in OneMax(0,1n). In general, there are few theoretical results on the benefits of the non-elitism in evolutionary algorithms. In this work, we analyze on the influence of the non-elitism via comparing the performance of the elitist (1 + λ) EA and its non-elitist counterpart (1, λ) EA. We prove that with probability 1 - o(1) (1 + λ) EA will get stuck in the local optima and cannot find the global optimum, but with probability 1, (1, λ) EA can reach the global optimum and its expected runtime is O(n3+c log n) with [EQUATION] for the constant c ≥ 1. Noting that a smaller offspring size is helpful for escaping from the local optima, we further resort to the compact genetic algorithm where only two individuals are sampled to update the probabilistic model, and prove its expected runtime of O(n3 log n). Our computational experiments also verify the efficiency of the two non-elitist algorithms.

Recent years have seen the advancement of data-driven paradigms in population-based and evolutionary optimization. This reflects on one hand the mere abundance of available data, but on the other hand also progresses in the refinement of previously available machine learning methods. Surprisingly, deep pattern recognition methods emerging from the studies of neural networks have only been sparingly applied. This comes unexpected, as the complex data generated by evolutionary search algorithms can be considered tedious and intractable for manual analysis with mere practical intuitions. In this work, we therefore explore opportunities to employ deep networks to directly learn problem characteristics of continuous optimization problems. Particularly, with data obtained during initial runs of an optimization algorithm. We find that a graph neural network, trained upon a graph representation of continuous search spaces, shows in comparison to more traditional approaches higher validation accuracy and retrieves characteristics within the latent space which are better at distinguishing different continuous optimization problems. We hope that our study can pave the way towards new approaches which allow us to learn problem-dependent algorithm components and recall these from predictions of inputs generated during the run-time of an optimization algorithm.

Designing advanced neural architectures to tackle specific tasks involves weeks or even months of intensive investigation by experts with rich domain knowledge. In recent years, neural architecture search (NAS) has attracted the interest of many researchers due to its ability to automatically design efficient neural architectures. Among different search strategies, evolutionary algorithms have achieved significant successes as derivative-free optimization algorithms. However, the tremendous computational resource consumption of the evolutionary neural architecture search dramatically restricts its application. In this paper, we explore how fitness approximation-based evolutionary algorithms can be applied to neural architecture search and propose NAS-EA-FA to accelerate the search process. We further exploit data augmentation and diversity of neural architectures to enhance the algorithm, and present NAS-EA-FA V2. Experiments show that NAS-EA-FA V2 is at least five times faster than other state-of-the-art neural architecture search algorithms like regularized evolution and iterative neural predictor on NASBench-101, and it is also the most effective and stable algorithm on NASBench-201. All the code used in this paper is available at https://github.com/fzjcdt/NAS-EA-FA.

Graph neural networks have recently received increasing attention. These methods often map nodes into latent spaces and learn vector representations of the nodes for a variety of downstream tasks. To gain trust and to promote collaboration between AIs and humans, it would be better if those representations were interpretable for humans. However, most explainable AIs focus on a supervised learning setting and aim to answer the following question: “Why does the model predict y for an input x?”. For an unsupervised learning setting as node embedding, interpretation can be more complicated since the embedding vectors are usually not understandable for humans. On the other hand, nodes and edges in a graph are often associated with texts in many real-world applications. A question naturally arises: could we integrate the human-understandable textural data into graph learning to facilitate interpretable node embedding? In this paper we present interpretable graph neural networks (iGNN), a model to learn textual explanations for node representations modeling the extra information contained in the associated textual data. To validate the performance of the proposed method, we investigate the learned interpretability of the embedding vectors and use functional interpretability to measure it. Experimental results on multiple text-labeled graphs show the effectiveness of the iGNN model on learning textual explanations of node embedding while performing well in downstream tasks.

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.

Surrogate-assisted evolutionary algorithms (SAEAs), which use efficient surrogate models or meta-models to approximate the fitness function in evolutionary algorithms (EAs), are effective and popular methods for solving computationally expensive optimization problems. During the past decades, a number of SAEAs have been proposed by combining different surrogate models and EAs. This paper dedicates to providing a more systematical review and comprehensive empirical study of surrogate models used in single-objective SAEAs. A new taxonomy of surrogate models in SAEAs for single-objective optimization is introduced in this paper. Surrogate models are classified into two major categories: absolute fitness models, which directly approximate the fitness function values of candidate solutions, and relative fitness models, which estimates the relative rank or preference of candidates rather than their fitness values. Then, the characteristics of different models are analyzed and compared by conducting a series of experiments in terms of time complexity (execution time), model accuracy, parameter influence, and the overall performance when used in EAs. The empirical results are helpful for researchers to select suitable surrogate models when designing SAEAs. Open research questions and future work are discussed at the end of the paper.

The multiobjective testing resource allocation problem (MOTRAP) is how to efficiently allocate the finite testing time to various modules, with the aim of optimizing system reliability, testing cost, and testing time simultaneously. To deal with this problem, a common approach is to use multiobjective evolutionary algorithms (MOEAs) to seek a set of tradeoff solutions between the three objectives. However, such a tradeoff set may contain a substantial proportion of solutions with very low reliability level, which consume lots of computational resources but may be valueless to the software project manager. In this article, a MOTRAP model with a prespecified reliability is first proposed. Then, new lower bounds on the testing time invested in different modules are theoretically deduced from the necessary condition for the achievement of the given reliability, based on which an exact algorithm for determining the new lower bounds is presented. Moreover, several enhanced constraint-handling techniques (ECHTs) derived from the new bounds are successively developed to be combined with MOEAs to correct and reduce the constraint violation. Finally, the proposed ECHTs are evaluated in comparison with various state-of-the-art constraint-solving approaches. The comparative results demonstrate that the proposed ECHTs can work well with MOEAs, make the search focus on the feasible region of the prespecified reliability, and provide the software project manager with better and more diverse, satisfactory choices in test planning.

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.

Cooperative co-evolution (CC) is an efficient and practical evolutionary framework for solving large-scale optimization problems. The performance of CC is affected by the variable decomposition. An accurate variable decomposition can help to improve the performance of CC on solving an optimization problem. The variable grouping methods usually spend many computational resources obtaining an accurate variable decomposition. To reduce the computational cost on the decomposition, we propose an efficient recursive differential grouping (ERDG) method in this article. By exploiting the historical information on examining the interrelationship between the variables of an optimization problem, ERDG is able to avoid examining some interrelationship and spend much less computation than other recursive differential grouping methods. Our experimental results and analysis suggest that ERDG is a competitive method for decomposing large-scale continuous problems and improves the performance of CC for solving the large-scale optimization problems.

Many real-world optimization problems are dynamic. The field of dynamic optimization deals with such problems where the search space changes over time. In this two-part article, we present a comprehensive survey of the research in evolutionary dynamic optimization for single-objective unconstrained continuous problems over the last two decades. In Part A of this survey, we propose a new taxonomy for the components of dynamic optimization algorithms (DOAs), namely, convergence detection, change detection, explicit archiving, diversity control, and population division and management. In comparison to the existing taxonomies, the proposed taxonomy covers some additional important components, such as convergence detection and computational resource allocation. Moreover, we significantly expand and improve the classifications of diversity control and multipopulation methods, which are underrepresented in the existing taxonomies. We then provide detailed technical descriptions and analysis of different components according to the suggested taxonomy. Part B of this survey provides an in-depth analysis of the most commonly used benchmark problems, performance analysis methods, static optimization algorithms used as the optimization components in the DOAs, and dynamic real-world applications. Finally, several opportunities for future work are pointed out.

This article presents the second Part of a two-Part survey that reviews evolutionary dynamic optimization (EDO) for single-objective unconstrained continuous problems over the last two decades. While in the first part, we reviewed the components of dynamic optimization algorithms (DOAs); in this part, we present an in-depth review of the most commonly used benchmark problems, performance analysis methods, static optimization methods used in the framework of DOAs, and real-world applications. Compared to the previous works, this article provides a new taxonomy for the benchmark problems used in the field based on their baseline functions and dynamics. In addition, this survey classifies the commonly used performance indicators into fitness/error-based and efficiency-based ones. Different types of plots used in the literature for analyzing the performance and behavior of algorithms are also reviewed. Furthermore, the static optimization algorithms that are modified and utilized in the framework of DOAs as the optimization components are covered. We then comprehensively review some real-world dynamic problems that are optimized by EDO methods. Finally, some challenges and opportunities are pointed out for future directions.

In real-world applications, many optimization problems have the time-linkage property, that is, the objective function value relies on the current solution as well as the historical solutions. Although the rigorous theoretical analysis on evolutionary algorithms (EAs) has rapidly developed in recent two decades, it remains an open problem to theoretically understand the behaviors of EAs on time-linkage problems. This article takes the first step to rigorously analyze EAs for time-linkage functions. Based on the basic OneMax function, we propose a time-linkage function where the first bit value of the last time step is integrated but has a different preference from the current first bit. We prove that with probability 1-o(1), randomized local search and (1 + 1) EA cannot find the optimum, and with probability 1-o(1), (μ+1) EA is able to reach the optimum.

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.

Digital microfluidic biochips (DMFBs) have been a revolutionary platform for automating and miniaturizing laboratory procedures with the advantages of flexibility and reconfigurability. The placement problem is one of the most challenging issues in the design automation of DMFBs. It contains three interacting NP-hard sub-problems: resource binding, operation scheduling, and module placement. Besides, during the optimization of placement, complex constraints must be satisfied to guarantee feasible solutions, such as precedence constraints, storage constraints, and resource constraints. In this article, a new placement method for DMFB is proposed based on an evolutionary algorithm with novel heuristic-based decoding strategies for both operation scheduling and module placement. Specifically, instead of using the previous list scheduler and path scheduler for decoding operation scheduling chromosomes, we introduce a new heuristic scheduling algorithm (called order scheduler) with fewer limitations on the search space for operation scheduling solutions. Besides, a new 3D placer that combines both scheduling and placement is proposed where the usage of the microfluidic array over time in the chip is recorded flexibly, which is able to represent more feasible solutions for module placement. Compared with the state-of-the-art placement methods (T-tree and 3D-DDM), the experimental results demonstrate the superiority of the proposed method based on several real-world bioassay benchmarks. The proposed method can find the optimal results with the minimum assay completion time for all test cases.

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.

Evolutionary algorithms are a class of population-based meta-heuristic methods partially inspired by natural evolution. Specifically, they rely on stochastic variation and selection processes to sequentially find optimal solutions of a function of interest. We attempt in this work to extract preferences in these stochastic evolutionary operators in form of empirical and improved distributions as basis for model-based mutation operators. The latter can be considered as representing problem-tailored search operators which exist independently from the optimisation run and thus can be transferred to similar problem instances. This offline approach is different to existing model-based optimisation techniques, e.g. EDA's, CMA-ES and Bayesian approaches, where adaption happens rather in an online manner without the influence of prior experience. Our approach can be rather considered to follow the recent line of research on knowledge transfer in optimisation, which until now heavily relies upon the transfer of candidate solutions across different optimisation tasks. We investigate in this paper the interplay between algorithm and optimisation task, its influence on the retrieved distributions and explore whether or not these can lead to performance improvements on a selected range of problems, as well as when transferring them across problems. At last, we make a comparison of built distributions in the hope of relating similarity in statistical distances between distributions to possible performance gains.

The Capacitated Arc Routing Problem (CARP) is a general and challenging arc routing problem. As the problem size increasing, exact methods are not applicable, and heuristic and meta-heuristic algorithms are promising approaches to solve it. To obtain good performance, parameter values of heuristics or meta-heuristics should be properly set. In recent years, automatic parameter tuning, which includes off-line and online parameter tuning, has attracted considerable attention in the evolutionary computation community. At present, parameters are usually determined through simple off-line parameter tuning, such as empirical analysis or grid search, when designing algorithms for CARP. However, using off-line parameter tuning on CARP has some disadvantages, among which the computational cost is the serious one. This work proposed an online parameter tuning approach using exponential recency-weighted kernel density estimation (ERW-KDE), and combines it with the SAHiD algorithm, which is an hierarchical decomposition based algorithm for CARP, to constitute the online parameter tuned SAHiD (OPT-SAHiD) algorithm. The experimental results show that OPT-SAHiD significantly outperforms the compared algorithms on two CARP benchmark sets owing to the proposed online automatic parameter tuning approach. The proposed online automatic parameter tuning approach based on ERW-KDE not only improves the performance of SAHiD algorithm, but also removes the additional computational overhead required for offline parameter tuning.

Transfer learning has been used for solving multiple optimization and dynamic multi-objective optimization problems, since transfer learning is believed to be able to transfer useful information from one problem instance to help solving another related problem instance. This paper aims to study how effective transfer learning is in dynamic multi-objective optimization (DMO). Through computation time analysis of transfer learning, we show that the `inner' optimization problem introduced by transfer learning is very time-consuming. In order to enhance the efficiency, two alternatives are computationally investigated on a number of dynamic bi- and tri-objective test problems. Experimental results have shown that the greatly enhanced efficiency does not result in much degeneration on the performance of transfer learning. Considering the high computational cost of transfer learning, it is likely that the original purpose of using transfer learning in DMO might be negated. In other words, the computation time saved in optimization is eaten up by computationally expensive transfer learning. As a result, there is less gain than expected in the overall computational efficiency. To verify this, experiments have been conducted, regarding using computational cost of transfer learning to optimize randomly generated solutions. The results have demonstrated that the convergence and diversity of final solutions generated from the random solutions are significantly better than those generated from transferred solutions under the same total computational budget.

Applying latent variable evolution to game level design has become more and more popular as little human expert knowledge is required. However, defective levels with illegal patterns may be generated due to the violation of constraints for level design. A traditional way of repairing the defective levels is programming specific rule-based repairers to patch the flaw. However, programming these constraints is sometimes complex and not straightforward. An autonomous level repairer which is capable of learning the constraints is needed. In this paper, we propose a novel approach, CNet, to learn the probability distribution of tiles giving its surrounding tiles on a set of real levels, and then detect the illegal tiles in generated new levels. Then, an evolutionary repairer is designed to search for optimal replacement schemes equipped with a novel search space being constructed with the help of CNet and a novel heuristic function. The proposed approaches are proved to be effective in our case study of repairing GAN-generated and artificially destroyed levels of Super Mario Bros. game. Our CNet-assisted evolutionary repairer can also be easily applied to other games of which the levels can be represented by a matrix of objects or tiles.

The performance of deep reinforcement learning methods prone to degenerate when applied to tasks requiring relatively longer horizon memory or with highly variable dynamics. In this paper, we utilize the probabilistic latent context variables motivated by recent Meta-RL materials, and propose the Latent Context based Soft Actor-Critic (LC-SAC) approach to address aforementioned issues. The latent context is capable to encode information about both the agent's previous behaviors and the dynamics of the current undergoing environment, which empirically believed to be beneficial for efficient policy optimization. Experiment results demonstrate that LC-SAC can achieve comparable performance with SAC on a collection of continuous control benchmarks and outperforms SAC in some particular tasks with above two characteristics. Moreover, we also introduce a simple but general procedure to integrate LC-SAC with diverse-quality demonstrations to enable efficient reuse of human prior knowledge, and finally achieve competitive performance with comparatively small number of interactions with environments.

The notion of learning from different problem instances, although an old and known one, has in recent years regained popularity within the optimization community. Notable endeavors have been drawing inspiration from machine learning methods as a means for algorithm selection and solution transfer. However, surprisingly approaches which are centered around internal sampling models have not been revisited. Even though notable algorithms have been established in the last decades. In this work, we progress along this direction by investigating a method that allows us to learn an evolutionary search strategy reflecting rough characteristics of a fitness landscape. This latter model of a search strategy is represented through a flexible mixture-based distribution, which can subsequently be transferred and adapted for similar problems of interest. We validate this approach in two series of experiments in which we first demonstrate the efficacy of the recovered distributions and subsequently investigate the transfer with a systematic from the literature to generate benchmarking scenarios.

The reliable facility location problem (RFLP) is an important research topic of operational research and plays a vital role in the decision-making and management of modern supply chain and logistics. Through solving RFLP, the decision-maker can obtain reliable location decisions under the risk of facilities’ disruptions or failures. In this paper, we propose a novel model for the RFLP. Instead of assuming allocating a fixed number of facilities to each customer as in the existing works, we set the number of allocated facilities as an independent variable in our proposed model, which makes our model more close to the scenarios in real life but more difficult to be solved by traditional methods. To handle it, we propose EAMLS, a hybrid evolutionary algorithm, which combines a memorable local search (MLS) method and an evolutionary algorithm (EA). Additionally, a novel metric called l3-value is proposed to assist the analysis of the algorithm’s convergence speed and exam the process of evolution. The experimental results show the effectiveness and superior performance of our EAMLS, compared to a CPLEX solver and a Genetic Algorithm (GA), on large-scale problems.

The quality of solution sets generated by decomposition-based evolutionary multi-objective optimisation (EMO) algorithms depends heavily on the consistency between a given problem's Pareto front shape and the specified weights' distribution. A set of weights distributed uniformly in a simplex often leads to a set of well-distributed solutions on a Pareto front with a simplex-like shape, but may fail on other Pareto front shapes. It is an open problem on how to specify a set of appropriate weights without the information of the problem's Pareto front beforehand. In this article, we propose an approach to adapt weights during the evolutionary process (called AdaW). AdaW progressively seeks a suitable distribution of weights for the given problem by elaborating several key parts in weight adaptation-weight generation, weight addition, weight deletion, and weight update frequency. Experimental results have shown the effectiveness of the proposed approach. AdaW works well for Pareto fronts with very different shapes: 1) the simplex-like, 2) the inverted simplex-like, 3) the highly nonlinear, 4) the disconnect, 5) the degenerate, 6) the scaled, and 7) the high-dimensional.

To promote engineering self-aware and self-adaptive software systems in a reusable manner, architectural patterns and the related methodology provide an unified solution to handle the recurring problems in the engineering process. However, in existing patterns and methods, domain knowledge and engineers’ expertise that is built over time are not explicitly linked to the self-aware processes. This link is important, as knowledge is a valuable asset for the related problems and its absence would cause unnecessary overhead, possibly misleading results, and unwise waste of the tremendous benefits that could have been brought by the domain expertise. This article highlights the importance of synergizing domain expertise and the self-awareness to enable better self-adaptation in software systems, relying on well-defined expertise representation, algorithms, and techniques. In particular, we present a holistic framework of notions, enriched patterns and methodology, dubbed DBASES, that offers a principled guideline for the engineers to perform difficulty and benefit analysis on possible synergies, in an attempt to keep “engineers-in-the-loop.” Through three tutorial case studies, we demonstrate how DBASES can be applied in different domains, within which a carefully selected set of candidates with different synergies can be used for quantitative investigation, providing more informed decisions of the design choices.

The articles in this month’s special issue cover concepts and fundamentals, architectures and techniques, and applications and case studies in the exciting area of self-awareness in autonomous systems.

The rate of transient faults has increased significantly as the technology scales up. The tolerance of transient faults has become an important issue in the system design. Dual modular redundancy (DMR) and triple modular redundancy (TMR) are two commonly used techniques that can achieve fault detection and masking through executing redundant tasks. As DMR and TMR have different time and cost overheads, we must carefully determine which one should be used for each task (i.e., task hardening) to achieve the optimal system design. Furthermore, for multi-core systems, the system-level design includes the allocation of cores for the tasks (i.e., task mapping) as well. This paper aims at task hardening and mapping simultaneously for independent tasks on multi-cores with heterogeneous performances, in order to minimize the maximum completion time of all tasks (i.e., makespan). We demonstrate that once task hardening is given, task mapping of independent tasks can be achieved by employing min–max-weight perfect matching with a polynomial time complexity. Besides, as there is a trade-off between cost and time performance, we propose a multi-objective memetic algorithm (MOMA)-based task hardening method to obtain a set of solutions with different numbers of cores (i.e., costs), so the designer can choose different solutions according to different requirements. The key idea of the MOMA is to incorporate problem-specific knowledge into the global search of evolutionary algorithms. Our experimental studies have demonstrated the effectiveness of the proposed method and have shown that by combining the results of MOMA and MOEA we can provide a designer with a highly accurate set of solutions within a reasonable amount of time.

Coalition formation has been a fundamental form of resource cooperation for achieving joint goals in multiagent systems. Most existing studies still focus on the traditional assumption that an agent has to contribute its resources to all the goals, even if the agent is not interested in the goal at all. In this article, a natural extension of the traditional coalitional resource games (CRGs) is studied from both theoretical and empirical perspectives, in which each agent has uncompromising, personalized preferences over goals. Specifically, a new CRGs model with agents’ strict preferences for goals is presented, in which an agent is willing to contribute its resources only to the goals that are in its own interest set. The computational complexity of the basic decision problems surrounding the successful coalition is reinvestigated. The results suggest that these problems in such a strict preference way are complex and intractable. To find the largest successful coalition for possible computation reduction or potential parallel processing, a flow-network–based exhaust algorithm, called FNetEA, is proposed to achieve the optimal solution. Then, to solve the problem more efficiently, a hybrid algorithm, named 2D-HA, is developed to find the approximately optimal solution on the basis of genetic algorithm, two-dimensional (2D) solution representation, and a heuristic for solution repairs. Through extensive experiments, the 2D-HA algorithm exhibits the prominent ability to provide reassurances that the optimal solution could be found within a reasonable period of time, even in a super-large-scale space.

Ratio error (RE) estimation of the voltage transformers (VTs) plays an important role in modern power delivery systems. Existing RE estimation methods mainly focus on periodical calibration but ignore the time-varying property. Consequently, it is difficult to efficiently estimate the state of the VTs in real time. To address this issue, we formulate a time-varying RE estimation (TREE) problem into a large-scale multiobjective optimization problem, where the multiple objectives and inequality constraints are formulated by statistical and physical rules extracted from the power delivery systems. Furthermore, a set of TREE problems from different substations is systematically formulated into a benchmark test suite for characterizing their different properties. The formulation of these TREE problems not only transfers an expensive RE estimation task to a relatively cheaper optimization problem but also promotes the research in large-scale multiobjective optimization by providing a real-world benchmark test suite with complex variable interactions and correlations to different objectives. To the best of our knowledge, this is the first time to formulate a real-world problem into a benchmark test suite for large-scale multiobjective optimization, and it is also the first work proposing to solve TREE problems via evolutionary multiobjective optimization.

Parameter tuning, that is, to find appropriate parameter settings (or configurations) of algorithms so that their performance is optimized, is an important task in the development and application of metaheuristics. Automating this task, i.e., developing algorithmic procedure to address parameter tuning task, is highly desired and has attracted significant attention from the researchers and practitioners. During last two decades, many automatic parameter tuning approaches have been proposed. This paper presents a comprehensive survey of automatic parameter tuning methods for metaheuristics. A new classification (or taxonomy) of automatic parameter tuning methods is introduced according to the structure of tuning methods. The existing automatic parameter tuning approaches are consequently classified into three categories: 1) simple generate-evaluate methods; 2) iterative generate-evaluate methods; and 3) high-level generate-evaluate methods. Then, these three categories of tuning methods are reviewed in sequence. In addition to the description of each tuning method, its main strengths and weaknesses are discussed, which is helpful for new researchers or practitioners to select appropriate tuning methods to use. Furthermore, some challenges and directions of this field are pointed out for further research.

The ultimate goal of multiobjective optimization is to help a decision maker (DM) identify solution(s) of interest (SOI) achieving satisfactory tradeoffs among multiple conflicting criteria. This can be realized by leveraging DM's preference information in evolutionary multiobjective optimization (EMO). No consensus has been reached on the effectiveness brought by incorporating preference in EMO (either a priori or interactively) versus a posteriori decision making after a complete run of an EMO algorithm. Bearing this consideration in mind, this article: 1) provides a pragmatic overview of the existing developments of preference-based EMO (PBEMO) and 2) conducts a series of experiments to investigate the effectiveness brought by preference incorporation in EMO for approximating various SOI. In particular, the DM's preference information is elicited as a reference point, which represents her/his aspirations for different objectives. The experimental results demonstrate that preference incorporation in EMO does not always lead to a desirable approximation of SOI if the DM's preference information is not well utilized, nor does the DM elicit invalid preference information, which is not uncommon when encountering a black-box system. To a certain extent, this issue can be remedied through an interactive preference elicitation. Last but not the least, we find that a PBEMO algorithm is able to be generalized to approximate the whole PF given an appropriate setup of preference information.

Scalability is a crucial aspect of designing efficient algorithms. Despite their prevalence, large-scale dynamic optimization problems are not well studied in the literature. This paper is concerned with designing benchmarks and frameworks for the study of large-scale dynamic optimization problems. We start by a formal analysis of the moving peaks benchmark (MPB) and show its nonseparable nature irrespective of its number of peaks. We then propose a composite MPB suite with exploitable modularity covering a wide range of scalable partially separable functions suitable for the study of large-scale dynamic optimization problems. The benchmark exhibits modularity, heterogeneity, and imbalance features to resemble real-world problems. To deal with the intricacies of large-scale dynamic optimization problems, we propose a decomposition-based coevolutionary framework which breaks a large-scale dynamic optimization problem into a set of lower-dimensional components. A novel aspect of the framework is its efficient bi-level resource allocation mechanism which controls the budget assignment to components and the populations responsible for tracking multiple moving optima. Based on a comprehensive empirical study on a wide range of large-scale dynamic optimization problems with up to 200-D, we show the crucial role of problem decomposition and resource allocation in dealing with these problems. The experimental results clearly show the superiority of the proposed framework over three other approaches in solving large-scale dynamic optimization problems.

The design space exploration (DSE) of fault-tolerant multiprocessor systems is very complex, as it contains three interacting NP-hard problems: 1) task hardening; 2) task mapping; and 3) task scheduling. In addition, replication-based task hardening can introduce new tasks, called replicas, into the system, enlarging the design space further. As a population-based global optimization algorithm, evolutionary algorithms (EAs) have been widely used to explore this huge design space over the last decade. However, as analyzed in this paper, the search space of previous works is highly redundant, resulting in poor efficiency and scalability. This paper proposes an efficient EA-based DSE method for the design of large-scale fault-tolerant multiprocessor systems. The main novelties of this paper include: 1) mapping exploration is explicitly separated, i.e., task mapping is optimized during the evolutionary search, while replica mapping is constructed heuristically according to the current co-synthesis state; 2) the design space of task hardening and task mapping are explored independently by a cooperative co-EA; and 3) as a complement to global search of EA, problem-specific local search operators are designed for both task hardening and task mapping, reducing the number of fitness evaluations required. Compared with the most relevant state-of-the-art method, the superiority of the proposed method is demonstrated using extensive experiments on a large set of benchmarks, e.g., 1.75×~2.50× better results can be obtained on the benchmarks of 300 tasks and 30 processors.

Imbalanced datasets may negatively impact the predictive performance of most classical classification algorithms. This problem, commonly found in real-world, is known in machine learning domain as imbalanced learning. Most techniques proposed to deal with imbalanced learning have been proposed and applied only to binary classification. When applied to multiclass tasks, their efficiency usually decreases and negative side effects may appear. This paper addresses these limitations by presenting a novel adaptive approach, E-MOSAIC (Ensemble of Classifiers based on MultiObjective Genetic Sampling for Imbalanced Classification). E-MOSAIC evolves a selection of samples extracted from training dataset, which are treated as individuals of a MOEA. The multiobjective process looks for the best combinations of instances capable of producing classifiers with high predictive accuracy in all classes. E-MOSAIC also incorporates two mechanisms to promote the diversity of these classifiers, which are combined into an ensemble specifically designed for imbalanced learning. Experiments using twenty imbalanced multi-class datasets were carried out. In these experiments, the predictive performance of E-MOSAIC is compared with state-of-the-art methods, including methods based on presampling, active-learning, cost-sensitive, and boosting. According to the experimental results, the proposed method obtained the best predictive performance for the multiclass accuracy measures mAUC and G-mean.

A Software Product Line (SPL) is a set of products built from a number of features, the set of valid products being defined by a feature model. Typically, it does not make sense to test all products defined by an SPL and one instead chooses a set of products to test (test selection) and, ideally, derives a good order in which to test them (test prioritisation). Since one cannot know in advance which products will reveal faults, test selection and prioritisation are normally based on objective functions that are known to relate to likely effectiveness or cost. This article introduces a new technique, the grid-based evolution strategy (GrES), which considers several objective functions that assess a selection or prioritisation and aims to optimise on all of these. The problem is thus a many-objective optimisation problem. We use a new approach, in which all of the objective functions are considered but one (pairwise coverage) is seen as the most important. We also derive a novel evolution strategy based on domain knowledge. The results of the evaluation, on randomly generated and realistic feature models, were promising, with GrES outperforming previously proposed techniques and a range of many-objective optimisation algorithms.

Overlapping coalition formation (OCF), which provides a natural framework for modeling scenarios where each agent can join and allocate their resources to several completely different coalitions at the same time, has become a very active topic in multiagent systems. For OCF in resource-constrained and subadditive task oriented domains, an agent may not possess sufficient resources to meet the needs of multiple coalitions simultaneously. As a result, there may exist many potential resource conflicts among the rival overlapping coalitions. To tackle such situations, we first present a natural variation of the traditional OCF model and analyze the size of the solution space and the computational complexity of the overlapping coalition structure generation (OCSG) problem. Next, we develop a generic task-oriented heuristic (TOH) for individual repairs that can be used in binary meta-heuristic algorithms to generate overlapping coalitions in a parallel manner. Moreover, we show how the proposed TOH repairs a 2-D individual to resolve resource conflicts and discuss several basic properties. Finally, to evaluate the effectiveness of TOH, we compare it with the existing agent-oriented heuristic for the OCSG problem. The empirical results demonstrate that TOH is of high efficiency and effectiveness in harsh environments with fierce competition over scarce resources.

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.

Surrogate-assisted evolutionary algorithms have played an important role in expensive optimization where a small number of real-objective function evaluations are allowed. Usually, the surrogate models are used for the same purpose, e.g., to approximate the real-objective function or the aggregation fitness function. However, there is little work on surrogate-assisted optimization by model fusion, i.e., different surrogate models are fused for different purposes to improve the performance of the algorithm. In this work, we propose a surrogate-assisted approach by model fusion for solving expensive many-objective optimization problems, in which the Kriging assisted objective function approximation method is fused with the classifier assisted approach. The proposed algorithm is compared with some state-of-the-art surrogate-assisted algorithms on DTLZ problems and a real-world problem, and some encouraging results have been achieved by our proposed model fusion based approach.

Dynamic multi-objective optimization problems are very common in many real-world applications. Such problems are often characterized by time varying objectives, constraints or parameters. Consideration of dynamics is typically limited to a single dynamic time scale; a restriction on the realistic description of real-world scenarios. In this paper, we investigate the effects of asynchrony on algorithm performance for two and three objective benchmark optimization problems with two independent time variables. The independent update of these time variables is parameterized on a logarithmic scale between slow-relative change, synchronous change and fast-relative changes. To evaluate the effect of the asynchronous modes, six established multi-objective optimization algorithms, tailored specifically for dynamic problems, were used to solve the problems. The hybrid-based methods achieve significantly better hypervolume and generational distance measurements when compared to random re-initialization, diversity focused and population prediction methods. Interestingly, for selected values of the change-frequency parameter, the best operating ranges of the algorithms differ. The benefits of mutation over replacement in diversity schemes are observed. Future application to power, economic and chemical scenarios are proposed.

The Capacitated Arc Routing Problem (CARP) is an essential and challenging problem in smart logistics. Parameter tuning is commonly encountered in designing and applying heuristic or meta-heuristic algorithms for CARP. Recently, automatic parameter tuning or hyper-parameter optimization, which focuses on automatically finding an optimal parameter setting of an algorithm for problems at hand, has attracted considerable attention and become popular for addressing parameter tuning problems. This paper studies automatic parameter tuning for advanced algorithms in solving CARP. When designing algorithms for CARP, parameters are usually determined through empirical analysis or following some rules of thumb. This paper uses an automatic parameter tuning approach, that is, Bayesian optimization method, to tune an algorithm called SAHiD, which is a scalable approach based on hierarchical decomposition for large-scale CARP. The experimental results show that the algorithm's performance can be significantly improved with automatic parameter tuning. The tuned SAHiD algorithm obtains better solutions and faster convergence speed than original SAHiD on test CARP instances.

We propose two novel evolution strategies of swarm intelligence for nanoswimmer-oriented in vivo computation, which corresponds to the computing model of the direct targeting strategy (DTS) where externally manipulable magnetic nanoswimmers are employed for cancer detection. In the DTS, the nanoswimmers move in the high-risk tissue region guided by an external magnetic field to search for the early cancer that cannot be visualized using traditional imaging modalities due to their limited resolution. Subject to the constraint of the state-of-the-art controlling technology which can only generate a uniform magnetic field to steer all the nanoswimmers simultaneously, we revisit the conventional gravitational search algorithm (GSA) and propose the orthokinetic gravitational search algorithm (OGSA) to carry out the DTS. Furthermore, we propose the general evolution strategy (G-ES) and the weak priority evolution strategy (WP-ES) and apply them to the OGSA for the path planning of magnetic nanoswimmers. To prove the superiority of the OGSA in the DTS, we present some simulation examples and make comparison with the "brute-force" search, which corresponds to the traditional systemic targeting strategy. Furthermore, we compare the performance of WP-ES and G-ES in the OGSA. It is found that the WP-ES can improve the performance of swarm intelligence algorithms (e.g., GSA) in the DTS.

Very expensive problems are very common in practical system that one fitness evaluation costs several hours or even days. Surrogate assisted evolutionary algorithms (SAEAs) have been widely used to solve this crucial problem in the past decades. However, most studied SAEAs focus on solving problems with a budget of at least ten times of the dimension of problems which is unacceptable in many very expensive real-world problems. In this paper, we employ Voronoi diagram to boost the performance of SAEAs and propose a novel framework named Voronoi-based efficient surrogate assisted evolutionary algorithm (VESAEA) for very expensive problems, in which the optimization budget, in terms of fitness evaluations, is only 5 times of the problem's dimension. In the proposed framework, the Voronoi diagram divides the whole search space into several subspace and then the local search is operated in some potentially better subspace. Additionally, in order to trade off the exploration and exploitation, the framework involves a global search stage developed by combining leave-one-out cross-validation and radial basis function surrogate model. A performance selector is designed to switch the search dynamically and automatically between the global and local search stages. The empirical results on a variety of benchmark problems demonstrate that the proposed framework significantly outperforms several state-of-art algorithms with extremely limited fitness evaluations. Besides, the efficacy of Voronoi-diagram is furtherly analyzed, and the results show its potential to optimize very expensive problems.

The recently proposed Scalable Approach Based on Hierarchical Decomposition (SAHiD) has shown its superiority on large-scale capacitated arc routing problems (CARP) in terms of both computational efficiency and solution quality. The main idea of SAHiD is that the underlying Hierarchical decomposition (HD) scheme is able to efficiently obtain a good permutation of tasks for CARP in a hierarchical divide-and-conquer way, where both the number and size of subproblems can be kept in tractable for large-scale problems with thousands of tasks. Motivated by the frequent observations of the similarity between CARP and Capacitated Vehicle Routing Problem (CVRP), the HD scheme and SAHiD algorithm are expected to work well on CVRPs. This paper applies SAHiD to large-scale CVRPs and discovers that SAHiD does not work as well as expected on large-scale CVRP. Possible reasons for this are given after extensive experimental studies. Two directions for improving SAHiD on large-scale CVRP are pointed out.

Surrogate-assisted evolutionary algorithms (SAEAs) are powerful optimisation tools for computationally expensive problems (CEPs). However, a randomly selected algorithm may fail in solving unknown problems due to no free lunch theorems, and it will cause more computational resource if we re-run the algorithm or try other algorithms to get a much solution, which is more serious in CEPs. In this paper, we consider an algorithm portfolio for SAEAs to reduce the risk of choosing an inappropriate algorithm for CEPs. We propose two portfolio frameworks for very expensive problems in which the maximal number of fitness evaluations is only 5 times of the problem's dimension. One framework named Par-IBSAEA runs all algorithm candidates in parallel and a more sophisticated framework named UCB-IBSAEA employs the Upper Confidence Bound (UCB) policy from reinforcement learning to help select the most appropriate algorithm at each iteration. An effective reward definition is proposed for the UCB policy. We consider three state-of-the-art individual-based SAEAs on different problems and compare them to the portfolios built from their instances on several benchmark problems given limited computation budgets. Our experimental studies demonstrate that our proposed portfolio frameworks significantly outperform any single algorithm on the set of benchmark problems.

The topological information is essential for studying the relationship between nodes in a network. Recently, Network Representation Learning (NRL), which projects a network into a low-dimensional vector space, has been shown their advantages in analyzing large-scale networks. However, most existing NRL methods are designed to preserve the local topology of a network and they fail to capture the global topology. To tackle this issue, we propose a new NRL framework, named HSRL, to help existing NRL methods capture both local and global topological information of a network. Specifically, HSRL recursively compresses an input network into a series of smaller networks using a community-awareness compressing strategy. Then, an existing NRL method is used to learn node embeddings for each compressed network. Finally, the node embeddings of the input network are obtained by concatenating the node embeddings resulting from all compressed networks. Empirical studies of link prediction on five real-world datasets demonstrate the advantages of HSRL over state-of-the-art methods.

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.

With the wide application of machine learning algorithms to the real world, class imbalance and concept drift have become crucial learning issues. Applications in various domains such as risk manag...

Studying coevolutionary systems in the context of simplified models (i.e., games with pairwise interactions between coevolving solutions modeled as self plays) remains an open challenge since the rich underlying structures associated with pairwise-comparison-based fitness measures are often not taken fully into account. Although cyclic dynamics have been demonstrated in several contexts (such as intransitivity in coevolutionary problems), there is no complete characterization of cycle structures and their effects on coevolutionary search. We develop a new framework to address this issue. At the core of our approach is the directed graph (digraph) representation of coevolutionary problems that fully captures structures in the relations between candidate solutions. Coevolutionary processes are modeled as a specific type of Markov chains-random walks on digraphs. Using this framework, we show that coevolutionary problems admit a qualitative characterization: a coevolutionary problem is either solvable (there is a subset of solutions that dominates the remaining candidate solutions) or not. This has an implication on coevolutionary search. We further develop our framework that provides the means to construct quantitative tools for analysis of coevolutionary processes and demonstrate their applications through case studies. We show that coevolution of solvable problems corresponds to an absorbing Markov chain for which we can compute the expected hitting time of the absorbing class. Otherwise, coevolution will cycle indefinitely and the quantity of interest will be the limiting invariant distribution of the Markov chain. We also provide an index for characterizing complexity in coevolutionary problems and show how they can be generated in a controlled manner.

A well-defined distance is critical for the performance of time series classification. Existing distance measurements can be categorized into two branches. One is to utilize handmade features for calculating distance, e.g., dynamic time warping, which is limited to exploiting the dynamic information of time series. The other methods make use of the dynamic information by approximating the time series with a generative model, e.g., Fisher kernel. However, previous distance measurements for time series seldom exploit the label information, which is helpful for classification by distance metric learning. In order to attain the benefits of the dynamic information of time series and the label information simultaneously, this paper proposes a multiobjective learning algorithm for both time series approximation and classification, termed multiobjective model-metric (MOMM) learning. In MOMM, a recurrent network is exploited as the temporal filter, based on which, a generative model is learned for each time series as a representation of that series. The models span a non-Euclidean space, where the label information is utilized to learn the distance metric. The distance between time series is then calculated as the model distance weighted by the learned metric. The network size is also optimized to learn parsimonious representations. MOMM simultaneously optimizes the data representation, the time series model separation, and the network size. The experiments show that MOMM achieves not only superior overall performance on uni/multivariate time series classification but also promising time series prediction performance.

Engineering designs can involve multiple stages, where at each stage, the design models are incrementally modified and optimized. In contrast to traditional dynamic optimization problems, where the changes are caused by some objective factors, the changes in such incremental optimization problems (IOPs) are usually caused by the modifications made by the decision makers during the design process. While existing work in the literature is mainly focused on traditional dynamic optimization, little research has been dedicated to solving such IOPs. In this paper, we study how to adopt cooperative coevolution to efficiently solve a specific type of IOPs, namely, those with increasing decision variables. First, we present a benchmark function generator on the basis of some basic formulations of IOPs with increasing decision variables and exploitable modular structure. Then, we propose a contribution-based cooperative coevolutionary framework coupled with an incremental grouping method for dealing with them. On one hand, the benchmark function generator is capable of generating various benchmark functions with various characteristics. On the other hand, the proposed framework is promising in solving such problems in terms of both optimization accuracy and computational efficiency. In addition, the proposed method is further assessed using a real-world application, i.e., the design optimization of a stepped cantilever beam.

In this paper, we propose a framework to accelerate the computational efficiency of evolutionary algorithms on large-scale multiobjective optimization. The main idea is to track the Pareto optimal set (PS) directly via problem reformulation. To begin with, the algorithm obtains a set of reference directions in the decision space and associates them with a set of weight variables for locating the PS. Afterwards, the original large-scale multiobjective optimization problem is reformulated into a low-dimensional single-objective optimization problem. In the reformulated problem, the decision space is reconstructed by the weight variables and the objective space is reduced by an indicator function. Thanks to the low dimensionality of the weight variables and reduced objective space, a set of quasi-optimal solutions can be obtained efficiently. Finally, a multiobjective evolutionary algorithm is used to spread the quasi-optimal solutions over the approximate Pareto optimal front evenly. Experiments have been conducted on a variety of large-scale multiobjective problems with up to 5000 decision variables. Four different types of representative algorithms are embedded into the proposed framework and compared with their original versions, respectively. Furthermore, the proposed framework has been compared with two state-of-the-art algorithms for large-scale multiobjective optimization. The experimental results have demonstrated the significant improvement benefited from the framework in terms of its performance and computational efficiency in large-scale multiobjective optimization.

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.

When solving constrained multiobjective optimization problems, an important issue is how to balance convergence, diversity, and feasibility simultaneously. To address this issue, this paper proposes a parameter-free constraint handling technique, a two-archive evolutionary algorithm, for constrained multiobjective optimization. It maintains two collaborative archives simultaneously: one, denoted as the convergence-oriented archive (CA), is the driving force to push the population toward the Pareto front; the other one, denoted as the diversity-oriented archive (DA), mainly tends to maintain the population diversity. In particular, to complement the behavior of the CA and provide as much diversified information as possible, the DA aims at exploring areas under-exploited by the CA including the infeasible regions. To leverage the complementary effects of both archives, we develop a restricted mating selection mechanism that adaptively chooses appropriate mating parents from them according to their evolution status. Comprehensive experiments on a series of benchmark problems and a real-world case study fully demonstrate the competitiveness of our proposed algorithm, in comparison to five state-of-the-art constrained evolutionary multiobjective optimizers.

Generative adversarial networks (GANs) have been effective for learning generative models for real-world data. However, accompanied with the generative tasks becoming more and more challenging, existing GANs (GAN and its variants) tend to suffer from different training problems such as instability and mode collapse. In this paper, we propose a novel GAN framework called evolutionary GANs (E-GANs) for stable GAN training and improved generative performance. Unlike existing GANs, which employ a predefined adversarial objective function alternately training a generator and a discriminator, we evolve a population of generators to play the adversarial game with the discriminator. Different adversarial training objectives are employed as mutation operations and each individual (i.e., generator candidature) are updated based on these mutations. Then, we devise an evaluation mechanism to measure the quality and diversity of generated samples, such that only well-performing generator(s) are preserved and used for further training. In this way, E-GAN overcomes the limitations of an individual adversarial training objective and always preserves the well-performing offspring, contributing to progress in, and the success of GANs. Experiments on several datasets demonstrate that E-GAN achieves convincing generative performance and reduces the training problems inherent in existing GANs.

Decomposition has become an increasingly popular technique for evolutionary multiobjective optimization (EMO). A decomposition-based EMO algorithm is usually designed to approximate a whole Pareto-optimal front (PF). However, in practice, a decision maker (DM) might only be concerned in her/his region of interest (ROI), i.e., a part of the PF. Solutions outside that might be useless or even noisy to the decision-making procedure. Furthermore, there is no guarantee that the preferred solutions will be found when many-objective problems. This paper develops an interactive framework for the decomposition-based EMO algorithm to lead a DM to the preferred solutions of her/his choice. It consists of three modules, i.e., consultation, preference elicitation, and optimization. Specifically, after every several generations, the DM is asked to score a few candidate solutions in a consultation session. Thereafter, an approximated value function, which models the DM's preference information, is progressively learned from the DM's behavior. In the preference elicitation session, the preference information learned in the consultation module is translated into the form that can be used in a decomposition-based EMO algorithm, i.e., a set of reference points that are biased toward the ROI. The optimization module, which can be any decomposition-based EMO algorithm in principle, utilizes the biased reference points to guide its search process. Extensive experiments on benchmark problems with three to ten objectives fully demonstrate the effectiveness of our proposed method for finding the DM's preferred solutions.

In many cities around the world, private vehicles are increasingly causing severe traffic congestion, pollution, and accidents. Public transports have been widely recognized as an effective way to improve urban life. To dissuade citizens from using private vehicles, it is necessary to design a practical, efficient, and economical public bus network. The transit network design problem (TNDP) determines the transit network (i.e., public bus network) for a city. It involves different stakeholders with diverse interests and values. To capture their conflicting expectations, numerous optimization objectives arise naturally. This paper introduces the TNDP as a many-objective optimization problem that generates a diverse set of alternative solutions. We apply several state-of-the-art many-objective evolutionary algorithms for the newly formulated TNDP. To efficiently explore the high-dimensional objective space of the TNDP, we develop problem-specific genetic operators for the evolutionary algorithm. We rigorously tested our approach on several benchmark datasets. The simulation results exhibit the effectiveness of the approach in addressing the challenges of a modern city. Based on the obtained results, we found $\theta $ -DEA to be the most robust among our employed algorithms. In addition, we observed the usefulness of the crossover operator, which randomly combines two solutions into one, and a simple mutation scheme, which is not biased to any objective function, to handle the many-objective nature of the TNDP.

Sparse Bayesian learning is a state-of-the-art supervised learning algorithm that can choose a subset of relevant samples from the input data and make reliable probabilistic predictions. However, in the presence of high-dimensional data with irrelevant features, traditional sparse Bayesian classifiers suffer from performance degradation and low efficiency due to the incapability of eliminating irrelevant features. To tackle this problem, we propose a novel sparse Bayesian embedded feature selection algorithm that adopts truncated Gaussian distributions as both sample and feature priors. The proposed algorithm, called probabilistic feature selection and classification vector machine (PFCVM LP ) is able to simultaneously select relevant features and samples for classification tasks. In order to derive the analytical solutions, Laplace approximation is applied to compute approximate posteriors and marginal likelihoods. Finally, parameters and hyperparameters are optimized by the type-II maximum likelihood method. Experiments on three datasets validate the performance of PFCVM LP along two dimensions: classification performance and effectiveness for feature selection. Finally, we analyze the generalization performance and derive a generalization error bound for PFCVM LP . By tightening the bound, the importance of feature selection is demonstrated.

Software effort estimation (SEE) usually suffers from inherent uncertainty arising from predictive model limitations and data noise. Relying on point estimation only may ignore the uncertain factors and lead project managers (PMs) to wrong decision making. Prediction intervals (PIs) with confidence levels (CLs) present a more reasonable representation of reality, potentially helping PMs to make better-informed decisions and enable more flexibility in these decisions. However, existing methods for PIs either have strong limitations or are unable to provide informative PIs. To develop a “better” effort predictor, we propose a novel PI estimator called Synthetic Bootstrap ensemble of Relevance Vector Machines (SynB-RVM) that adopts Bootstrap resampling to produce multiple RVM models based on modified training bags whose replicated data projects are replaced by their synthetic counterparts. We then provide three ways to assemble those RVM models into a final probabilistic effort predictor, from which PIs with CLs can be generated. When used as a point estimator, SynB-RVM can either significantly outperform or have similar performance compared with other investigated methods. When used as an uncertain predictor, SynB-RVM can achieve significantly narrower PIs compared to its base learner RVM. Its hit rates and relative widths are no worse than the other compared methods that can provide uncertain estimation.

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.

Service composition aims to search a composition plan of candidate services that produces the optimal results with respect to multiple and possibly conflicting Quality-of-Service (QoS) attributes, e.g., latency, throughput and cost. This leads to a multi-objective optimization problem for which evolutionary algorithm is a promising solution. In this paper, we investigate different ways of injecting knowledge about the problem into the Multi-Objective Evolutionary Algorithm (MOEA) by seeding. Specifically, we propose four alternative seeding strategies to strengthen the quality of the initial population for the MOEA to start working with. By using the real-world WS-DREAM dataset, we conduced experimental evaluations based on 9 different workflows of service composition problems and several metrics. The results confirm the effectiveness and efficiency of those seeding strategies. We also observed that, unlike the discoveries for other problem domains, the implication of the number of seeds on the service composition problems is minimal, for which we investigated and discussed the possible reasons.

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.

Dynamic optimization problems (DOPs) are problems that change over time. However, most investigations in this domain are focused on tracking moving optima (TMO) without considering the cost of switching from one solution to another when the environment changes. Robust optimization over time (ROOT) tries to address this shortcoming by finding solutions which remain acceptable for several environments. However, ROOT methods change solutions only when they become unacceptable. Indeed, TMO and ROOT are two extreme cases in the sense that in the former, the switching cost is considered zero and in the latter, it is considered very large. In this paper, we propose a new semi ROOT algorithm based on a new approach to switching cost. This algorithm changes solutions when: 1) the current solution is not acceptable and 2) the current solution is still acceptable but algorithm has found a better solution and switching is preferable despite the cost. The main objective of the proposed algorithm is to maximize the performance based on the fitness of solutions and their switching cost. The experiments are done on modified moving peaks benchmark (mMPB) and the performance of the proposed algorithm alongside state-of-the-art ROOT and TMO methods is investigated.

A new computing-inspired multiple-cancer detection procedure (MCDP) is proposed. In the MCDP, the cancer areas to be detected can be regarded as solutions of an objective function, the tissue region around the cancer areas can be mapped to the parameter space of the solutions, and the nanorobots correspond to the agents in the optimization procedure. The process that the nanorobots look for the cancer areas by swimming in the tissue region can be mapped to the process that the agents search for the solutions in the parameter space. Niche Genetic Algorithm (NGA) is widely used in multimodal function optimization and non-monotonic function optimization. It can search all global optimums of multiple hump function in a running, keep the diversity of the population effectively, and avoid premature of solutions got from normal GA. Inspired by the optimization procedure of NGA, the multiple cancer detection procedure (MCDP) has been studied and the NGA-inspired cancer detection procedure has been proposed in order to locate the targets efficiently at the same time by taking into account realistic in vivo propagation and controlling of nanorobots. Finally, some comparative numerical examples are presented to demonstrate the effectiveness of the NGA-inspired MCDP.

Software effort estimation (SEE) usually suffers from data scarcity problem due to the expensive or long process of data collection. As a result, companies usually have limited projects for effort estimation, causing unsatisfactory prediction performance. Few studies have investigated strategies to generate additional SEE data to aid such learning. We aim to propose a synthetic data generator to address the data scarcity problem of SEE. Our synthetic generator enlarges the SEE data set size by slightly displacing some randomly chosen training examples. It can be used with any SEE method as a data preprocessor. Its effectiveness is justified with 6 state-of-the-art SEE models across 14 SEE data sets. We also compare our data generator against the only existing approach in the SEE literature. Experimental results show that our synthetic projects can significantly improve the performance of some SEE methods especially when the training data is insufficient. When they cannot significantly improve the prediction performance, they are not detrimental either. Besides, our synthetic data generator is significantly superior or perform similarly to its competitor in the SEE literature. Therefore, our data generator plays a non-harmful if not significantly beneficial effect on the SEE methods investigated in this paper. Therefore, it is helpful in addressing the data scarcity problem of SEE.

Self-adaptive system (SAS) can adapt itself to optimize various key performance indicators in response to the dynamics and uncertainty in environment. In this paper, we present Debt Learning Driven Adaptation (DLDA), an framework that dynamically determines when and whether to adapt the SAS at runtime. DLDA leverages the temporal adaptation debt, a notion derived from the technical debt metaphor, to quantify the time-varying money that the SAS carries in relation to its performance and Service Level Agreements. We designed a temporal net debt driven labeling to label whether it is economically healthier to adapt the SAS (or not) in a circumstance, based on which an online machine learning classifier learns the correlation, and then predicts whether to adapt under the future circumstances. We conducted comprehensive experiments to evaluate DLDA with two different planners, using 5 online machine learning classifiers, and in comparison to 4 state-of-the-art debt-oblivious triggering approaches. The results reveal the effectiveness and superiority of DLDA according to different metrics.

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.

Rather than a whole Pareto-optimal front, which demands too many points (especially in a high-dimensional space), the decision maker (DM) may only be interested in a partial region, called the region of interest (ROI). In this case, solutions outside this region can be noisy to the decision-making procedure. Even worse, there is no guarantee that we can find the preferred solutions when tackling problems with complicated properties or many objectives. In this paper, we develop a systematic way to incorporate the DM's preference information into the decomposition-based evolutionary multiobjective optimization methods. Generally speaking, our basic idea is a nonuniform mapping scheme by which the originally evenly distributed reference points on a canonical simplex can be mapped to new positions close to the aspiration-level vector supplied by the DM. By this means, we are able to steer the search process toward the ROI either directly or interactively and also handle many objectives. Meanwhile, solutions lying on the boundary can be approximated as well given the DM's requirements. Furthermore, the extent of the ROI is intuitively understandable and controllable in a closed form. Extensive experiments on a variety of benchmark problems with 2 to 10 objectives, fully demonstrate the effectiveness of our proposed method for approximating the preferred solutions in the ROI.

Existing studies on dynamic multiobjective optimization (DMO) focus on problems with time-dependent objective functions, while the ones with a changing number of objectives have rarely been considered in the literature. Instead of changing the shape or position of the Pareto-optimal front/set (PF/PS) when having time-dependent objective functions, increasing or decreasing the number of objectives usually leads to the expansion or contraction of the dimension of the PF/PS manifold. Unfortunately, most existing dynamic handling techniques can hardly be adapted to this type of dynamics. In this paper, we report our attempt toward tackling the DMO problems with a changing number of objectives. We implement a dynamic two-archive evolutionary algorithm which maintains two co-evolving populations simultaneously. In particular, these two populations are complementary to each other: one concerns more about the convergence while the other concerns more about the diversity. The compositions of these two populations are adaptively reconstructed once the environment changes. In addition, these two populations interact with each other via a mating selection mechanism. Comprehensive experiments are conducted on various benchmark problems with a time-dependent number of objectives. Empirical results fully demonstrate the effectiveness of our proposed algorithm.

Recently, by taking advantage of evolutionary multiobjective optimization techniques in diversity preservation, the means of multiobjectivization has attracted increasing interest in the studies of multimodal optimization (MMO). While most existing work of multiobjectivization aims to find all optimal solutions simultaneously, in this paper, we propose to approximate multimodal fitness landscapes via multiobjectivization, thus providing an estimation of potential optimal areas. To begin with, an MMO problem is transformed into a multiobjective optimization problem (MOP) by adding an adaptive diversity indicator as the second optimization objective, and an approximate fitness landscape is obtained via optimization of the transformed MOP using a multiobjective evolutionary algorithm. Then, on the basis of the approximate fitness landscape, an adaptive peak detection method is proposed to find peaks where optimal solutions may exist. Finally, local search is performed inside the detected peaks on the approximate fitness landscape. To assess the performance of the proposed algorithm, extensive experiments are conducted on 20 multimodal test functions, in comparison with three state-of-the-art algorithms for MMO. Experimental results demonstrate that the proposed algorithm not only shows promising performance in benchmark comparisons, but also has good potential in assisting preference-based decision-making in MMO.

Measuring the performance of an algorithm for solving multiobjective optimization problem has always been challenging simply due to two conflicting goals, i.e., convergence and diversity of obtained tradeoff solutions. There are a number of metrics for evaluating the performance of a multiobjective optimizer that approximates the whole Pareto-optimal front. However, for evaluating the quality of a preferred subset of the whole front, the existing metrics are inadequate. In this paper, we suggest a systematic way to adapt the existing metrics to quantitatively evaluate the performance of a preference-based evolutionary multiobjective optimization algorithm using reference points. The basic idea is to preprocess the preferred solution set according to a multicriterion decision making approach before using a regular metric for performance assessment. Extensive experiments on several artificial scenarios, and benchmark problems fully demonstrate its effectiveness in evaluating the quality of different preferred solution sets with regard to various reference points supplied by a decision maker.

Studying the search behavior of evolutionary many-objective optimization is an important, but challenging issue. Existing studies rely mainly on the use of performance indicators which, however, not only encounter increasing difficulties with the number of objectives, but also fail to provide the visual information of the evolutionary search. In this paper, we propose a class of scalable test problems, called multiline distance minimization problem (ML-DMP), which are used to visually examine the behavior of many-objective search. Two key characteristics of the ML-DMP problem are: 1) its Pareto optimal solutions lie in a regular polygon in the 2-D decision space and 2) these solutions are similar (in the sense of Euclidean geometry) to their images in the high-dimensional objective space. This allows a straightforward understanding of the distribution of the objective vector set (e.g., its uniformity and coverage over the Pareto front) via observing the solution set in the 2-D decision space. Fifteen well-established algorithms have been investigated on three types of ten ML-DMP problem instances. Weakness has been revealed across classic multiobjective algorithms (such as Pareto-based, decomposition-based, and indicator-based algorithms) and even state-of-the-art algorithms designed especially for many-objective optimization. This, together with some interesting observations from the experimental studies, suggests that the proposed ML-DMP may also be used as a benchmark function to challenge the search ability of optimization algorithms.

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.

Fitness landscape analysis (FLA) is an important approach for studying how hard problems are for metaheuristic algorithms to solve. Static FLA focuses on extracting the properties of a problem and does not consider any information about the optimization algorithms; thus, it is not adequate for indicating whether a particular algorithm is suitable for solving a problem. By contrast, dynamic FLA considers the behavior of algorithms in combination with the properties of an optimization problem to determine the effectiveness of a given algorithm for solving that problem. However, previous dynamic FLA approaches are all individually based and lack statistical significance. In this paper, the concept of population evolvability is presented, as an extension of dynamic FLA, to quantify the effectiveness of population-based metaheuristic algorithms for solving a given problem. Specifically, two measures of population evolvability are defined that describe the probability that a population will obtain improved solutions to a problem and its ability to do so. Then, a combined measure is derived from these two measures to represent the overall population evolvability. Subsequently, the significance and validity of the proposed measures are investigated through analytical and experimental studies. Finally, the utility of the proposed measures is illustrated in an application of algorithm selection for black-box optimization problems. High accuracy in selecting the best algorithm is observed in a statistical analysis, with a low computational cost in terms of fitness evaluations.

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.

In spread spectrum (SS) based robust audio watermarking, the scaling parameter is an important factor for balancing between robustness and imperceptibility. There have been intense studies of the embedded parameter optimization in light of the signal-to-noise ratio (SNR), but little attention has been given to the constrained SNR. Moreover, traditional population-based stochastic search algorithms for optimizing the embedded parameter significantly increase the computation pressure of the corresponding audio watermarking schemes. This paper comprehensively investigates the effect of the constrained SNR on the optimization of the scaling parameter, from both model and algorithmic perspectives. Specifically, the empirical relationship between the scaling parameter, robustness, and imperceptibility is first analyzed in detail. Next, an SNR-constrained optimization model is presented. Then, to solve the proposed model and find the current optimal scaling parameter for watermark embedding, a binary search algorithm and a heuristic search (HS) algorithm are, respectively, developed. Finally, we embed the proposed model and heuristics in the SS-based audio watermarking scheme and compare the integrated technique (called SS-SNR-HS) with the existing similar schemes. The experimental results demonstrate that SS-SNR-HS not only is computationally simple, but also achieves better balance between imperceptibility and robustness and, thus, seems promising in copyright protection of online digital audio.

Negative correlation learning (NCL) is an ensemble learning algorithm that introduces a correlation penalty term to the cost function of each individual ensemble member. Each ensemble member minimizes its mean square error and its error correlation with the rest of the ensemble. This paper analyzes NCL and reveals that adopting a negative correlation term for unlabeled data is beneficial to improving the model performance in the semisupervised learning (SSL) setting. We then propose a novel SSL algorithm, Semisupervised NCL (SemiNCL) algorithm. The algorithm considers the negative correlation terms for both labeled and unlabeled data for the semisupervised problems. In order to reduce the computational and memory complexity, an accelerated SemiNCL is derived from the distributed least square algorithm. In addition, we have derived a bound for two parameters in SemiNCL based on an analysis of the Hessian matrix of the error function. The new algorithm is evaluated by extensive experiments with various ratios of labeled and unlabeled training data. Comparisons with other state-of-the-art supervised and semisupervised algorithms confirm that SemiNCL achieves the best overall performance.

Semisupervised classification (SSC) consists of using both labeled and unlabeled data to classify unseen instances. Due to the large number of unlabeled data typically available, SSC algorithms must be able to handle large-scale data sets. Recently, various ensemble algorithms have been introduced with improved generalization performance when compared to single classifiers. However, existing ensemble methods are not able to handle typical large-scale data sets. We propose efficient cluster-based boosting (ECB), a multiclass SSC algorithm with cluster-based regularization that avoids generating decision boundaries in high-density regions. A semisupervised selection procedure reduces time and space complexities by selecting only the most informative unlabeled instances for the training of each base learner. We provide evidences to demonstrate that ECB is able to achieve good performance with small amounts of selected data and a relatively small number of base learners. Our experiments confirmed that ECB scales to large data sets while delivering comparable generalization to state-of-the-art methods.

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.

As an emerging research topic, online class imbalance learning often combines the challenges of both class imbalance and concept drift. It deals with data streams having very skewed class distributions, where concept drift may occur. It has recently received increased research attention; however, very little work addresses the combined problem where both class imbalance and concept drift coexist. As the first systematic study of handling concept drift in class-imbalanced data streams, this paper first provides a comprehensive review of current research progress in this field, including current research focuses and open challenges. Then, an in-depth experimental study is performed, with the goal of understanding how to best overcome concept drift in online learning with class imbalance.

Self-Adaptive Software (SAS) can reconfigure itself to adapt to the changing environment at runtime, aiming to continually optimize conflicted nonfunctional objectives (e.g., response time, energy consumption, throughput, cost, etc.). In this article, we present Feature-guided and knEe-driven Multi-Objective optimization for Self-Adaptive softwAre (FEMOSAA), a novel framework that automatically synergizes the feature model and Multi-Objective Evolutionary Algorithm (MOEA) to optimize SAS at runtime. FEMOSAA operates in two phases: at design time, FEMOSAA automatically transposes the engineers’ design of SAS, expressed as a feature model, to fit the MOEA, creating new chromosome representation and reproduction operators. At runtime, FEMOSAA utilizes the feature model as domain knowledge to guide the search and further extend the MOEA, providing a larger chance for finding better solutions. In addition, we have designed a new method to search for the knee solutions, which can achieve a balanced tradeoff. We comprehensively evaluated FEMOSAA on two running SAS: One is a highly complex SAS with various adaptable real-world software under the realistic workload trace; another is a service-oriented SAS that can be dynamically composed from services. In particular, we compared the effectiveness and overhead of FEMOSAA against four of its variants and three other search-based frameworks for SAS under various scenarios, including three commonly applied MOEAs, two workload patterns, and diverse conflicting quality objectives. The results reveal the effectiveness of FEMOSAA and its superiority over the others with high statistical significance and nontrivial effect sizes.

A proportional-integral-derivative (PID) controller is a control loop feedback mechanism widely employed in industrial control systems. The parameters tuning is a sticking point, having a great effect on the control performance of a PID system. There is no perfect rule for designing controllers, and finding an initial good guess for the parameters of a well-performing controller is difficult. In this paper, we develop a knowledge-based particle swarm optimization by incorporating the dynamic response information of PID into the optimizer. Prior knowledge not only empowers the particle swarm optimization algorithm to quickly identify the promising regions, but also helps the proposed algorithm to increase the solution precision in the limited running time. To benchmark the performance of the proposed algorithm, an electric pump drive and an automatic voltage regulator system are selected from industrial applications. The simulation results indicate that the proposed algorithm with a newly proposed performance index has a significant performance on both test cases and outperforms other algorithms in terms of overshoot, steady state error, and settling time.

Multimodal optimization has attracted increasing interest recently. Despite the emergence of various multimodal optimization algorithms during the last decade, little work has been dedicated to the development of benchmark tools. In this paper, we propose a visualization method for benchmark studies of multimodal optimization, called parallel peaks. Inspired by parallel coordinates, the proposed parallel peaks method is capable of visualizing both distribution information and convergence information of a given candidate solution set inside a 2D coordinate plane. To the best of our knowledge, this is the first visualization method in the multimodal optimization area. Our empirical results demonstrate that the proposed parallel peaks method can be robustly used to visualize candidate solutions sets with a range of properties, including high-accuracy solutions sets, high-dimensional solution sets and solution sets with a large number of optima. Additionally, by visualizing the populations obtained during the optimization process, it can also be used to investigate search behaviors of multimodal optimization algorithms.

Symbolic regression has been one of the main learning domains for Genetic Programming. However, most work so far on using genetic programming for symbolic regression only focus on point prediction. The problem of symbolic interval regression is for each input to find a prediction interval containing the output with a given statistical confidence. This problem is important for many risk-sensitive domains (such as in medical and financial applications). In this paper, we propose the combination of conformal prediction and genetic programming for solving the problem of symbolic interval regression. We study two approaches called black-box conformal prediction genetic programming (black-box CPGP) and white-box conformal prediction genetic programming (white-box CPGP) on a number of benchmarks and previously used problems. We compare the performance of these approaches with two popular interval regressors in statistic and machine learning domains, namely, the linear quantile regression and quantile random forrest. The experimental results show that, on the two performance metrics, black-box CPGP is comparable to the linear quantile regression and not much worse than the quantile random forrest on validity and much better than them on efficiency.

In this paper, we present a new SaaS (software as a service) design for employee job performance appraisals, SaaS-JPA. We use IoT and computer systems to collect data related to the daily works of employees. A semantic model is developed to guide the data collection process, facilitate data interpretation and interoperation, and enable big data analysis to make job performance appraisal decisions. We also propose two new performance assessment models: The similarity-based relative performance model and the revenue-based performance model. These performance models are enabled by the service technologies and big data analytics. Finally, we discuss the design of SaaS-JPA.

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.

Software Effort Estimation (SEE) models can be used for decision-support by software managers to determine the effort required to develop a software project. They are created based on data describing projects completed in the past. Such data could include past projects from within the company that we are interested in (WC projects) and/or from other companies (cross-company, i.e., CC projects). In particular, the use of CC data has been investigated in an attempt to overcome limitations caused by the typically small size of WC datasets. However, software companies operate in non-stationary environments, where changes may affect the typical effort required to develop software projects. Our previous work showed that both WC and CC models of the past can become more or less useful over time, i.e., they can sometimes be helpful and sometimes misleading. So, how can we know if and when a model created based on past data represents well the current projects being estimated? We propose an approach called Dynamic Cross-company Learning (DCL) to dynamically identify which WC or CC past models are most useful for making predictions to a given company at the present. DCL automatically emphasizes the predictions given by these models in order to improve predictive performance. Our experiments comparing DCL against existing WC and CC approaches show that DCL is successful in improving SEE by emphasizing the most useful past models. A thorough analysis of DCL’s behaviour is provided, strengthening its external validity.

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.

Maintaining diversity is one important aim of multiobjective optimization. However, diversity for manyobjective optimization problems is less straightforward to define than for multiobjective optimization problems. Inspired by measures for biodiversity, we propose a new diversity metric for many-objective optimization, which is an accumulation of the dissimilarity in the population, where an Lp-norm-based (p<;1) distance is adopted to measure the dissimilarity of solutions. Empirical results demonstrate our proposed metric can more accurately assess the diversity of solutions in various situations. We compare the diversity of the solutions obtained by four popular many-objective evolutionary algorithms using the proposed diversity metric on a large number of benchmark problems with two to ten objectives. The behaviors of different diversity maintenance methodologies in those algorithms are discussed in depth based on the experimental results. Finally, we show that the proposed diversity measure can also be employed for enhancing diversity maintenance or reference set generation in many-objective optimization.

This paper aims to study how the population size affects the computation time of evolutionary algorithms (EAs) in a rigorous way. The computation time of EAs can be measured by either the number of generations (hitting time) or the number of fitness evaluations (running time) to find an optimal solution. Population scalability is the ratio of the expected hitting time between a benchmark algorithm and an algorithm using a larger population size. Average drift analysis is introduced to compare the expected hitting time of two algorithms and to estimate lower and upper bounds on the population scalability. Several intuitive beliefs are rigorously analyzed. It is proven that: 1) using a population sometimes increases rather than decreases the expected hitting time; 2) using a population cannot shorten the expected running time of any elitist EA on any unimodal function on the time-fitness landscape, however, this statement is not true in terms of the distance-based fitness landscape; and 3) using a population cannot always reduce the expected running time on deceptive functions, which depends on whether the benchmark algorithm uses elitist selection or random selection.

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

Cooperative co-evolution (CC) is an explicit means of problem decomposition in multipopulation evolutionary algorithms for solving large-scale optimization problems. For CC, subpopulations representing subcomponents of a large-scale optimization problem co-evolve, and are likely to have different contributions to the improvement of the best overall solution to the problem. Hence, it makes sense that more computational resources should be allocated to the subpopulations with greater contributions. In this paper, we study how to allocate computational resources in this context and subsequently propose a new CC framework named CCFR to efficiently allocate computational resources among the subpopulations according to their dynamic contributions to the improvement of the objective value of the best overall solution. Our experimental results suggest that CCFR can make efficient use of computational resources and is a highly competitive CCFR for solving large-scale optimization problems.

Semi-supervised learning (SSL) concerns the problem of how to improve classifiers’ performance through making use of prior knowledge from unlabeled data. Many SSL methods have been developed to integrate unlabeled data into the classifiers based on either the manifold or cluster assumption in recent years. In particular, the graph-based approaches, following the manifold assumption, have achieved a promising performance in many real-world applications. However, most of them work well on small-scale data sets only and lack probabilistic outputs. In this paper, a scalable graph-based SSL framework through sparse Bayesian model is proposed by defining a graph-based sparse prior. Based on the traditional Bayesian inference technique, a sparse Bayesian SSL algorithm (SBS$^2$L) is obtained, which can remove the irrelevant unlabeled samples and make probabilistic prediction for out-of-sample data. Moreover, in order to scale SBS$^2$L to large-scale data sets, an incremental SBS$^2$L (ISBS$^2$L) is derived. The key idea of ISBS$^2$L is employing an incremental strategy and sequentially selecting parts of unlabeled samples that contribute to the learning instead of using all available unlabeled samples directly. ISBS$^2$L has lower time and space complexities than previous SSL algorithms with the use of all unlabeled samples. Extensive experiments on various data sets verify that our algorithms can achieve comparable classification effectiveness and efficiency with much better scalability. Finally, the generalization error bound is derived based on robustness analysis.

In software testing, optimal testing resource allocation problems (OTRAPs) are important when seeking a good tradeoff between reliability, cost, and time with limited resources. There have been intensive studies of OTRAPs using multiobjective evolutionary algorithms (MOEAs), but little attention has been paid to the constraint handling. This paper comprehensively investigates the effect of the constraint handling on the performance of nondominated sorting genetic algorithm II (NSGA-II) for solving OTRAPs, from both theoretical and empirical perspectives. The heuristics for individual repairs are first proposed to handle constraint violations in NSGA-II, based on which several properties are derived. Additionally, theZ-score based Euclidean distance is adopted to estimate the difference between solutions. Finally, the above methods are evaluated and the experiments show several results. 1) The developed heuristics for constraint handling are better than the Existing Strategy in terms of the capacity and coverage values. 2) TheZ-score operation obtains better diversity values and reduces repeated solutions. 3) The modified NSGA-II for OTRAPs (called NSGA-II-TRA) performs significantly better than the existing MOEAs in terms of capacity and coverage values, which suggests that NSGA-II-TRA could obtain more and higher quality testing-time-allocation schemes, especially for large, complex datasets. 4) NSGA-II-TRA is robust according to the sensitivity analysis results.

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.

Cooperative Co-evolution (CC) is a promising framework for solving large-scale optimization problems. However, the round-robin strategy of CC is not an efficient way of allocating the available computational resources to components of imbalanced functions. The imbalance problem happens when the components of a partially separable function have non-uniform contributions to the overall objective value. Contribution-Based Cooperative Co-evolution (CBCC) is a variant of CC that allocates the available computational resources to the individual components based on their contributions. CBCC variants (CBCC1 and CBCC2) have shown better performance than the standard CC in a variety of cases. In this paper, we show that over-exploration and over-exploitation are two major sources of performance loss in the existing CBCC variants. On that basis, we propose a new contribution-based algorithm that maintains a better balance between exploration and exploitation. The empirical results show that the new algorithm is superior to its predecessors as well as the standard CC.

By studying the fitness landscape properties of engine calibration problem we propose a new Principal Component Analysis (PCA) based optimisation algorithm for the problem. The engine calibration problem in this paper is to minimise the fuel consumption, gas emission and particle emission of a Jaguar car engine. To evaluate the fuel consumption and emissions of the engine, a model of the engine that was developed in University of Birmingham was used. A strength Pareto method is used to convert the three objectives into one fitness value. Then a local search algorithm is used to find local optima. We then study these local optima to find the properties of good solutions in the landscape. Our studies on the good solutions show that the best solutions in the landscape show some patterns. We perform Principal Component Analysis (PCA) on the good solutions and show that these components present certain properties, which can be exploited to develop new exploration operators for evolutionary algorithms. We use the newly proposed operator on some well-known algorithms and show that the performance of the algorithms can be improved significantly.

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.

Time series forecasting for streaming data plays an important role in many real applications, ranging from IoT systems, cyber-networks, to industrial systems and healthcare. However the real data is often complicated with anomalies and change points, which can lead the learned models deviating from the underlying patterns of the time series, especially in the context of online learning mode. In this paper we present an adaptive gradient learning method for recurrent neural networks (RNN) to forecast streaming time series in the presence of anomalies and change points. We explore the local features of time series to automatically weight the gradients of the loss of the newly available observations with distributional properties of the data in real time. We perform extensive experimental analysis on both synthetic and real datasets to evaluate the performance of the proposed method.

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.

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

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

Abstract It is hard to obtain the entire solution set of a many-objective optimization problem (MaOP) by multi-objective evolutionary algorithms (MOEAs) because of the difficulties brought by the large number of objectives. However, the redundancy of objectives exists in some problems with correlated objectives (linearly or nonlinearly). Objective reduction can be used to decrease the difficulties of some MaOPs. In this paper, we propose a novel objective reduction approach based on nonlinear correlation information entropy (NCIE). It uses the NCIE matrix to measure the linear and nonlinear correlation between objectives and a simple method to select the most conflicting objectives during the execution of MOEAs. We embed our approach into both Pareto-based and indicator-based MOEAs to analyze the impact of our reduction method on the performance of these algorithms. The results show that our approach significantly improves the performance of Pareto-based MOEAs on both reducible and irreducible MaOPs, but does not much help the performance of indicator-based MOEAs.

Time series forecasting (TSF) has been widely used in many application areas such as science, engineering, and finance. The phenomena generating time series are usually unknown and information available for forecasting is only limited to the past values of the series. It is, therefore, necessary to use an appropriate number of past values, termed lag, for forecasting. This paper proposes a layered ensemble architecture (LEA) for TSF problems. Our LEA consists of two layers, each of which uses an ensemble of multilayer perceptron (MLP) networks. While the first ensemble layer tries to find an appropriate lag, the second ensemble layer employs the obtained lag for forecasting. Unlike most previous work on TSF, the proposed architecture considers both accuracy and diversity of the individual networks in constructing an ensemble. LEA trains different networks in the ensemble by using different training sets with an aim of maintaining diversity among the networks. However, it uses the appropriate lag and combines the best trained networks to construct the ensemble. This indicates LEAs emphasis on accuracy of the networks. The proposed architecture has been tested extensively on time series data of neural network (NN)3 and NN5 competitions. It has also been tested on several standard benchmark time series data. In terms of forecasting accuracy, our experimental results have revealed clearly that LEA is better than other ensemble and nonensemble methods.

Using a set of binary classifiers to solve multiclass classification problems has been a popular approach over the years. The decision boundaries learnt by binary classifiers (also called base classifiers) are much simpler than those learnt by multiclass classifiers. This paper proposes a new classification framework, termed binarization with boosting and oversampling (BBO), for efficiently solving multiclass classification problems. The new framework is devised based on the one-versus-all (OVA) binarization technique. Unlike most previous work, BBO employs boosting for solving the hard-to-learn instances and oversampling for handling the class-imbalance problem arising due to OVA binarization. These two features make BBO different from other existing works. Our new framework has been tested extensively on several multiclass supervised and semi-supervised classification problems using five different base classifiers, including neural networks, C4.5, k -nearest neighbor, repeated incremental pruning to produce error reduction, support vector machine, random forest, and learning with local and global consistency. Experimental results show that BBO can exhibit better performance compared to its counterparts on supervised and semi-supervised classification problems.

Regularity models have been used in dealing with noise-free multiobjective optimization problems. This paper studies the behavior of a regularity model in noisy environments and argues that it is very suitable for noisy multiobjective optimization. We propose to embed the regularity model in an existing multiobjective evolutionary algorithm for tackling noises. The proposed algorithm works well in terms of both convergence and diversity. In our experimental studies, we have compared several state-of-the-art of algorithms with our proposed algorithm on benchmark problems with different levels of noises. The experimental results showed the effectiveness of the regularity model on noisy problems, but a degenerated performance on some noisy-free problems.

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.

Feature selection is an important task in data mining and machine learning to reduce the dimensionality of the data and increase the performance of an algorithm, such as a classification algorithm. However, feature selection is a challenging task due mainly to the large search space. A variety of methods have been applied to solve feature selection problems, where evolutionary computation (EC) techniques have recently gained much attention and shown some success. However, there are no comprehensive guidelines on the strengths and weaknesses of alternative approaches. This leads to a disjointed and fragmented field with ultimately lost opportunities for improving performance and successful applications. This paper presents a comprehensive survey of the state-of-the-art work on EC for feature selection, which identifies the contributions of these different algorithms. In addition, current issues and challenges are also discussed to identify promising areas for future research.

Many-objective optimization has posed a great challenge to the classical Pareto dominance-based multiobjective evolutionary algorithms (MOEAs). In this paper, an evolutionary algorithm based on a new dominance relation is proposed for many-objective optimization. The proposed evolutionary algorithm aims to enhance the convergence of the recently suggested nondominated sorting genetic algorithm III by exploiting the fitness evaluation scheme in the MOEA based on decomposition, but still inherit the strength of the former in diversity maintenance. In the proposed algorithm, the nondominated sorting scheme based on the introduced new dominance relation is employed to rank solutions in the environmental selection phase, ensuring both convergence and diversity. The proposed algorithm is evaluated on a number of well-known benchmark problems having 3-15 objectives and compared against eight state-of-the-art algorithms. The extensive experimental results show that the proposed algorithm can work well on almost all the test functions considered in this paper, and it is compared favorably with the other many-objective optimizers. Additionally, a parametric study is provided to investigate the influence of a key parameter in the proposed algorithm.

The decomposition-based multiobjective evolutionary algorithms (MOEAs) generally make use of aggregation functions to decompose a multiobjective optimization problem into multiple single-objective optimization problems. However, due to the nature of contour lines for the adopted aggregation functions, they usually fail to preserve the diversity in high-dimensional objective space even by using diverse weight vectors. To address this problem, we propose to maintain the desired diversity of solutions in their evolutionary process explicitly by exploiting the perpendicular distance from the solution to the weight vector in the objective space, which achieves better balance between convergence and diversity in many-objective optimization. The idea is implemented to enhance two well-performing decomposition-based algorithms, i.e., MOEA, based on decomposition and ensemble fitness ranking. The two enhanced algorithms are compared to several state-of-the-art algorithms and a series of comparative experiments are conducted on a number of test problems from two well-known test suites. The experimental results show that the two proposed algorithms are generally more effective than their predecessors in balancing convergence and diversity, and they are also very competitive against other existing algorithms for solving many-objective optimization problems.

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.

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

Software project scheduling in dynamic and uncertain environments is of significant importance to real-world software development. Yet most studies schedule software projects by considering static and deterministic scenarios only, which may cause performance deterioration or even infeasibility when facing disruptions. In order to capture more dynamic features of software project scheduling than the previous work, this paper formulates the project scheduling problem by considering uncertainties and dynamic events that often occur during software project development, and constructs a mathematical model for the resulting multi-objective dynamic project scheduling problem (MODPSP), where the four objectives of project cost, duration, robustness and stability are considered simultaneously under a variety of practical constraints. In order to solve MODPSP appropriately, a multi-objective evolutionary algorithm based proactive-rescheduling method is proposed, which generates a robust schedule predictively and adapts the previous schedule in response to critical dynamic events during the project execution. Extensive experimental results on 21 problem instances, including three instances derived from real-world software projects, show that our novel method is very effective. By introducing the robustness and stability objectives, and incorporating the dynamic optimization strategies specifically designed for MODPSP, our proactive-rescheduling method achieves a very good overall performance in a dynamic environment.

High defect density and extreme parameter variation make it very difficult to implement reliable logic functions in crossbar-based nanoarchitectures. It is a major design challenge to tolerate defects and variations simultaneously for such architectures. In this paper, a method based on a bipartite matching and memetic algorithm is proposed for defect- and variation-tolerant logic mapping (D/VTLM) problem in crossbar-based nanoarchitectures. In the proposed method, the search space of the D/VTLM problem can be dramatically reduced through the introduction of the min-max weight maximum-bipartite-matching (MMW-MBM) and a related heuristic bipartite matching method. MMW-MBM is defined on a weighted bipartite graph as an MBM, where the maximal weight of the edges in the matching has a minimal value. In addition, a defect- and variation-aware local search (D/VALS) operator is proposed for D/VTLM and embedded in a global search framework. The D/VALS operator is able to utilize the domain knowledge extracted from problem instances and, thus, has the potential to search the solution space more efficiently. Compared with the state-of-the-art heuristic and recursive algorithms, and a simulated annealing algorithm, the good performance of our proposed method is verified on a 3-bit adder and a large set of random benchmarks of various scales.

Architecture-based software performance optimization can not only significantly save time but also reduce cost. A few rule-based performance optimization approaches at software architecture (SA) level have been proposed in recent years. However, in these approaches, the number of rules being used and the order of application of each rule are uncertain in the optimization process and these uncertainties have not been fully considered so far. As a result, the search space for performance improvement is limited, possibly excluding optimal solutions. Aiming to solve this problem, we propose an evolutionary algorithm for rule-based performance optimization at SA level named EA4PO. First, the rule-based software performance optimization at SA level is abstracted into a mathematical model called RPOM. RPOM can precisely characterize the mathematical relation between the usage of rules and the optimal solution in the performance improvement space. Then, a framework named RSEF is designed to support the execution of rule sequences. Based on RPOM and RSEF, EA4PO is proposed to find the optimal performance improvement solution. In EA4PO, an adaptive mutation operator is designed to guide the search direction by fully considering heuristic information of rule usage during the evolution. Finally, the effectiveness of EA4PO is validated by comparing EA4PO with a typical rule-based approach. The results show that EA4PO can explore a relatively larger space and get better solutions.

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.

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

We study heterogeneity among nodes in self-organizing smart camera networks, which use strategies based on social and economic knowledge to target communication activity efficiently. We compare homogeneous configurations, when cameras use the same strategy, with heterogeneous configurations, when cameras use different strategies. Our first contribution is to establish that static heterogeneity leads to new outcomes that are more efficient than those possible with homogeneity. Next, two forms of dynamic heterogeneity are investigated: nonadaptive mixed strategies and adaptive strategies, which learn online. Our second contribution is to show that mixed strategies offer Pareto efficiency consistently comparable with the most efficient static heterogeneous configurations. Since the particular configuration required for high Pareto efficiency in a scenario will not be known in advance, our third contribution is to show how decentralized online learning can lead to more efficient outcomes than the homogeneous case. In some cases, outcomes from online learning were more efficient than all other evaluated configuration types. Our fourth contribution is to show that online learning typically leads to outcomes more evenly spread over the objective space. Our results provide insight into the relationship between static, dynamic, and adaptive heterogeneity, suggesting that all have a key role in achieving efficient self-organization.

The number of objectives in many-objective optimization problems (MaOPs) is typically high and evolutionary algorithms face severe difficulties in solving such problems. In this paper, we propose a new scalable evolutionary algorithm, called evolutionary path control strategy (EPCS), for solving MaOPs. The central component of our algorithm is the use of a reference vector that helps simultaneously minimizing all the objectives of an MaOP. In doing so, EPCS employs a new fitness assignment strategy for survival selection. This strategy consists of two procedures and our algorithm applies them sequentially. It encourages a population of solutions to follow a certain path reaching toward the Pareto optimal front. The essence of our strategy is that it reduces the number of nondominated solutions to increase selection pressure in evolution. Furthermore, unlike previous work, EPCS is able to apply the classical Pareto-dominance relation with the new fitness assignment strategy. Our algorithm has been tested extensively on several scalable test problems, namely five DTLZ problems with 5 to 40 objectives and six WFG problems with 2 to 13 objectives. Furthermore, the algorithm has been tested on six CEC09 problems having 2 or 3 objectives. The experimental results show that EPCS is capable of finding better solutions compared to other existing algorithms for problems with an increasing number of objectives.

The maximum balanced biclique problem (MBBP), an NP-hard combinatorial optimization problem, has been attracting more attention in recent years. Existing node-deletion-based algorithms usually fail to find high-quality solutions due to their easy stagnation in local optima, especially when the scale of the problem grows large. In this paper, a new algorithm for the MBBP, evolutionary algorithm with structure mutation (EA/SM), is proposed. In the EA/SM framework, local search complemented with a repair-assisted restart process is adopted. A new mutation operator, SM, is proposed to enhance the exploration during the local search process. The SM can change the structure of solutions dynamically while keeping their size (fitness) and the feasibility unchanged. It implements a kind of large mutation in the structure space of MBBP to help the algorithm escape from local optima. An MBBP-specific local search operator is designed to improve the quality of solutions efficiently; besides, a new repair-assisted restart process is introduced, in which the Marchiori's heuristic repair is modified to repair every new solution reinitialized by an estimation of distribution algorithm (EDA)-like process. The proposed algorithm is evaluated on a large set of benchmark graphs with various scales and densities. Experimental results show that: 1) EA/SM produces significantly better results than the state-of-the-art heuristic algorithms; 2) it also outperforms a repair-based EDA and a repair-based genetic algorithm on all benchmark graphs; and 3) the advantages of EA/SM are mainly due to the introduction of the new SM operator and the new repair-assisted restart process.

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.

The hardness of fitness functions is an important research topic in the field of evolutionary computation. In theory, this paper can help with understanding the ability of evolutionary algorithms (EAs). In practice, this paper may provide a guideline to the design of benchmarks. The aim of this paper is to answer the following research questions. Given a fitness function class, which functions are the easiest with respect to an EA? Which are the hardest? How are these functions constructed? This paper provides theoretical answers to these questions. The easiest and hardest fitness functions are constructed for an elitist (1 + 1) EA to maximize a class of fitness functions with the same optima. It is demonstrated that the unimodal functions are the easiest and deceptive functions are the hardest in terms of the time-based fitness landscape. This paper also reveals that in a fitness function class, the easiest function to one algorithm may become the hardest to another algorithm, and vice versa.

Meta-heuristic algorithms are often inspired by natural phenomena, including the evolution of species in Darwinian natural selection theory, ant behaviors in biology, flock behaviors of some birds, and annealing in metallurgy. Due to their great potential in solving difficult optimization problems, meta-heuristic algorithms have found their way into automobile engine design. There are different optimization problems arising in different areas of car engine management including calibration, control system, fault diagnosis, and modeling. In this paper we review the state-of-the-art applications of different meta-heuristic algorithms in engine management systems. The review covers a wide range of research, including the application of meta-heuristic algorithms in engine calibration, optimizing engine control systems, engine fault diagnosis, and optimizing different parts of engines and modeling. The meta-heuristic algorithms reviewed in this paper include evolutionary algorithms, evolution strategy, evolutionary programming, genetic programming, differential evolution, estimation of distribution algorithm, ant colony optimization, particle swarm optimization, memetic algorithms, and artificial immune system.

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.

Many-objective optimization problems (ManyOPs) refer, usually, to those multiobjective problems (MOPs) with more than three objectives. Their large numbers of objectives pose challenges to multiobjective evolutionary algorithms (MOEAs) in terms of convergence, diversity, and complexity. Most existing MOEAs can only perform well in one of those three aspects. In view of this, we aim to design a more balanced MOEA on ManyOPs in all three aspects at the same time. Among the existing MOEAs, the two-archive algorithm (Two_Arch) is a low-complexity algorithm with two archives focusing on convergence and diversity separately. Inspired by the idea of Two_Arch, we propose a significantly improved two-archive algorithm (i.e., Two_Arch2) for ManyOPs in this paper. In our Two_Arch2, we assign different selection principles (indicator-based and Pareto-based) to the two archives. In addition, we design a new Lp-norm-based (p <; 1) diversity maintenance scheme for ManyOPs in Two_Arch2. In order to evaluate the performance of Two_Arch2 on ManyOPs, we have compared it with several MOEAs on a wide range of benchmark problems with different numbers of objectives. The experimental results show that Two_Arch2 can cope with ManyOPs (up to 20 objectives) with satisfactory convergence, diversity, and complexity.

Rescheduling in railway networks is a challenging problem in both practice and theory. It requires good quality solutions in reasonable computation time to resolve unexpected situations, involving different problem scales, railway network infrastructures, objectives, and constraints. This paper presents a comprehensive survey on different problem models for rescheduling in railway networks by a clear classification. Some frequently used models are described in detail through reviewing their variables and constraints. This paper also focuses on the solution approaches proposed in the literature. The main ideas of the solution approaches with the objectives are described. Based on our review results, the analysis of the problem models used in various problem types and the solution approaches used in different problem models are presented. Conclusion and suggestions for further research to rescheduling in railway networks are drawn toward the end of the paper.

The classification of patterns into naturally ordered labels is referred to as ordinal regression or ordinal classification. Usually, this classification setting is by nature highly imbalanced, because there are classes in the problem that are a priori more probable than others. Although standard over-sampling methods can improve the classification of minority classes in ordinal classification, they tend to introduce severe errors in terms of the ordinal label scale, given that they do not take the ordering into account. A specific ordinal over-sampling method is developed in this paper for the first time in order to improve the performance of machine learning classifiers. The method proposed includes ordinal information by approaching over-sampling from a graph-based perspective. The results presented in this paper show the good synergy of a popular ordinal regression method (a reformulation of support vector machines) with the graph-based proposed algorithms, and the possibility of improving both the classification and the ordering of minority classes. A cost-sensitive version of the ordinal regression method is also introduced and compared with the over-sampling proposals, showing in general lower performance for minority classes.

Online class imbalance learning is a new learning problem that combines the challenges of both online learning and class imbalance learning. It deals with data streams having very skewed class distributions. This type of problems commonly exists in real-world applications, such as fault diagnosis of real-time control monitoring systems and intrusion detection in computer networks. In our earlier work, we defined class imbalance online, and proposed two learning algorithms OOB and UOB that build an ensemble model overcoming class imbalance in real time through resampling and time-decayed metrics. In this paper, we further improve the resampling strategy inside OOB and UOB, and look into their performance in both static and dynamic data streams. We give the first comprehensive analysis of class imbalance in data streams, in terms of data distributions, imbalance rates and changes in class imbalance status. We find that UOB is better at recognizing minority-class examples in static data streams, and OOB is more robust against dynamic changes in class imbalance status. The data distribution is a major factor affecting their performance. Based on the insight gained, we then propose two new ensemble methods that maintain both OOB and UOB with adaptive weights for final predictions, called WEOB1 and WEOB2. They are shown to possess the strength of OOB and UOB with good accuracy and robustness.

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.

The use and search of finite-state machine (FSM) representations has a long history in evolutionary computation. The flexibility of Mealy-style and Moore-style FSMs is traded against the large number of parameters required to encode machines with many states and/or large output alphabets. Recent work using Mealy FSMs on the Tartarus problem has shown good performance of the resulting machines, but the evolutionary search is slower than for other representations. The aim of this paper is two-fold: first, a comparison between Mealy and Moore representations is considered on two problems, and then the impact of cooperative coevolution on FSM evolutionary search is examined. The results suggest that the search space of Moore-style FSMs may be easier to explore through evolutionary search than the search space of an equivalent-sized Mealy FSM representation. The results presented also suggest that the tested cooperative coevolutionary algorithms struggle to appropriately manage the non-separability present in FSMs, indicating that new approaches to cooperative coevolution may be needed to explore FSMs and similar graphical structures.

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.

Most of the studies on project scheduling problems assume that every assigned participant or every team of the same number of participants, completes tasks with an equal efficiency, but this is usually not the case for real world problems. This paper presents a more realistic and complex model with extra consideration on team efficiency which are quantitatively measured on employee-task assignment. This study demonstrates the impacts of team efficiency in a well-studied software project management problem. Moreover, this study illustrates how a heuristic optimization method, population-based incremental learning, copes with such added complexity. The experimental results show that the resulting near optimal solutions not only satisfy constraints, but also reflect the impacts of team efficiency. The findings will hopefully motivate future studies on comprehensive understandings of the quality and efficiency of team work.

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.

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

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.

Previous works using Cross-Company (CC) data for making Within-Company (WC) Software Effort Estimation (SEE) try to use CC data or models directly to provide predictions in the WC context. So, these data or models are only helpful when they match the WC context well. When they do not, a fair amount of WC training data, which are usually expensive to acquire, are still necessary to achieve good performance. We investigate how to make best use of CC data, so that we can reduce the amount of WC data while maintaining or improving performance in comparison to WC SEE models. This is done by proposing a new framework to learn the relationship between CC and WC projects explicitly, allowing CC models to be mapped to the WC context. Such mapped models can be useful even when the CC models themselves do not match the WC context directly. Our study shows that a new approach instantiating this framework is able not only to use substantially less WC data than a corresponding WC model, but also to achieve similar/better performance. This approach can also be used to provide insight into the behaviour of a company in comparison to others.

Online class imbalance learning is an emerging learning area that combines the challenges of both online learning and class imbalance learning. In addition to the learning difficulty from the imbalanced distribution, another major challenge is that the imbalanced rate in a data stream can be dynamically changing. OOB and UOB are two state-of-the-art methods for online class imbalance problems [1]. UOB is better at recognizing minority-class examples when the imbalance rate does not change much over time, while OOB is more prepared for the case with a dynamic rate. Aiming for an effective method for both static and dynamic cases, this paper proposes a multi-objective ensemble method MOSOB that combines OOB and UOB. MOSOB finds the Pareto-optimal weights for OOB and UOB at each time step, to maximize minority-class recall and majority-class recall simultaneously. Experiments on five real-world data applications show that MOSOB performs well in both static and dynamic data streams. Furthermore, we look into its performance on a group of highly imbalanced data streams. To respond to the minority class within 10000 time steps, the imbalance rate can be as low as 0.1% for easy data streams; at least 3% of imbalance rate is required to classify difficult data streams.

Contemporary software systems are becoming increasingly large, heterogeneous, and decentralised. They operate in dynamic environments and their architectures exhibit complex trade-offs across dimensions of goals, time, and interaction, which emerges internally from the systems and externally from their environment. This gives rise to the vision of self-aware architecture, where design decisions and execution strategies for these concerns are dynamically analysed and seamlessly managed at run-time. Drawing on the concept of self-awareness from psychology, this paper extends the foundation of software architecture styles for self-adaptive systems to arrive at a new principled approach for architecting self-aware systems. We demonstrate the added value and applicability of the approach in the context of service provisioning to cloud-reliant service-based applications.

Since the 1970s the goal of generating programs in an automatic way (i.e., Automatic Programming) has been sought. A user would just define what he expects from the program (i.e., the requirements), and it should be automatically generated by the computer without the help of any programmer. Unfortunately, this task is much harder than expected. Although transformation methods are usually employed to address this problem, they cannot be employed if the gap between the specification and the actual implementation is too wide. In this paper we introduce a novel conceptual framework for evolving programs from their specification. We use genetic programming to evolve the programs, and at the same time we exploit the specification to co-evolve sets of unit tests. Programs are rewarded by how many tests they do not fail, whereas the unit tests are rewarded by how many programs they make to fail. We present and analyse seven different problems on which this novel technique is successfully applied.

Computing unique input output (UIO) sequences is a fundamental and hard problem in conformance testing of finite state machines (FSM). Previous experimental research has shown that evolutionary algorithms (EAs) can be applied successfully to find UIOs for some FSMs. However, before EAs can be recommended as a practical technique for computing UIOs, it is necessary to better understand the potential and limitations of these algorithms on this problem. In particular, more research is needed in determining for what instance classes of the problem EAs are feasible, and for what instance classes EAs are provably better than random search strategies. This paper presents rigorous theoretical and numerical analyses of the runtime of the (1 + 1) EA and random search on several selected instance classes of this problem. The theoretical analysis shows firstly, that there are instance classes where the EA is efficient, while random testing fails completely. Secondly, an instance class that is difficult for both random testing and the EA is presented. Finally, a parametrised instance class with tunable difficulty is presented. The numerical study estimates the constants in the asymptotic expressions obtained in the theoretical analysis, and the variability of the runtime. The numerical results fit well with the theoretical results, even for small problem instance sizes. Together, these results provide a first theoretical characterisation of the potential and limitations of the (1 + 1) EA on the problem of computing UIOs.

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.

The construction of promising solutions for NP-hard combinatorial optimization problems (COPs) in meta-heuristics is usually based on three types of information, namely a priori information, a posteriori information learned from visited solutions during the search procedure, and online information collected in the solution construction process. Prior information reflects our domain knowledge about the COPs. Extensive domain knowledge can surely make the search effective, yet it is not always available. Posterior information could guide the meta-heuristics to globally explore promising search areas, but it lacks local guidance capability. On the contrary, online information can capture local structures, and its application can help exploit the search space. In this paper, we studied the effects of using this information on metaheuristic's algorithmic performances for the COPs. The study was illustrated by a set of heuristic algorithms developed for the quadratic assignment problem. We first proposed an improved scheme to extract online local information, then developed a unified framework under which all types of information can be combined readily. Finally, we studied the benefits of the three types of information to meta-heuristics. Conclusions were drawn from the comprehensive study, which can be used as principles to guide the design of effective meta-heuristic in the future.

Nondominated sorting plays an important role in Pareto-based multiobjective evolutionary algorithms (MOEAs). When faced with many-objective optimization problems multiobjective optimization problems (MOPs) with more than three objectives, the number of comparisons needed in nondominated sorting becomes very large. In view of this, a new corner sort is proposed in this paper. Corner sort first adopts a fast and simple method to obtain a nondominated solution from the corner solutions, and then uses the nondominated solution to ignore the solutions dominated by it to save comparisons. Obtaining the nondominated solutions requires much fewer objective comparisons in corner sort. In order to evaluate its performance, several state-of-the-art nondominated sorts are compared with our corner sort on three kinds of artificial solution sets of MOPs and the solution sets generated from MOEAs on benchmark problems. On one hand, the experiments on artificial solution sets show the performance on the solution sets with different distributions. On the other hand, the experiments on the solution sets generated from MOEAs show the influence that different sorts bring to MOEAs. The results show that corner sort performs well, especially on many-objective optimization problems. Corner sort uses fewer comparisons than others.

Classification algorithms can suffer from performance degradation when the class distribution is unbalanced. This paper develops a two-step approach to evolving ensembles using genetic programming (GP) for unbalanced data. The first step uses multiobjective (MO) GP to evolve a Pareto-approximated front of GP classifiers to form the ensemble by trading-off the minority and the majority class against each other during learning. The MO component alleviates the reliance on sampling to artificially rebalance the data. The second step, which is the focus this paper, proposes a novel ensemble selection approach using GP to automatically find/choose the best individuals for the ensemble. This new GP approach combines multiple Pareto-approximated front members into a single composite genetic program solution to represent the (optimized) ensemble. This ensemble representation has two main advantages/novelties over traditional genetic algorithm (GA) approaches. First, by limiting the depth of the composite solution trees, we use selection pressure during evolution to find small highly-cooperative groups of individuals for the ensemble. This means that ensemble sizes are not fixed a priori (as in GA), but vary depending on the strength of the base learners. Second, we compare different function set operators in the composite solution trees to explore new ways to aggregate the member outputs and thus, control how the ensemble computes its output. We show that the proposed GP approach evolves smaller more diverse ensembles compared to an established ensemble selection algorithm, while still performing as well as, or better than the established approach. The evolved GP ensembles also perform well compared to other bagging and boosting approaches, particularly on tasks with high levels of class imbalance.

This paper addresses the problem of finding sparse solutions to linear systems. Although this problem involves two competing cost function terms (measurement error and a sparsity-inducing term), previous approaches combine these into a single cost term and solve the problem using conventional numerical optimization methods. In contrast, the main contribution of this paper is to use a multiobjective approach. The paper begins by investigating the sparse reconstruction problem, and presents data to show that knee regions do exist on the Pareto front (PF) for this problem and that optimal solutions can be found in these knee regions. Another contribution of the paper, a new soft-thresholding evolutionary multiobjective algorithm (StEMO), is then presented, which uses a soft-thresholding technique to incorporate two additional heuristics: one with greater chance to increase speed of convergence toward the PF, and another with higher probability to improve the spread of solutions along the PF, enabling an optimal solution to be found in the knee region. Experiments are presented, which show that StEMO significantly outperforms five other well known techniques that are commonly used for sparse reconstruction. Practical applications are also demonstrated to fundamental problems of recovering signals and images from noisy data.

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

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

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.

The defect-tolerant logic mapping (DTLM), which has been proved to be an NP-complete combinatorial search problem, is a key step for logic implementation in emerging crossbar-based nano-architectures. However, no practically satisfactory solution has been suggested for the DTLM until now. In this paper, the problem of DTLM is first modeled as a combinatorial optimization problem through the introduction of maximum-bipartite-matching. Then, a new memetic algorithm with fitness approximation (MA/FA) is proposed to solve the optimization problem efficiently. In MA/FA, a new greedy reassignment local search operator, capable of utilizing the domain knowledge and information from problem instances, is designed to help the algorithm find optimal logic mapping with consumption of relatively lower computational resources. A fitness approximation method is adopted to reduce the time consumption of fitness evaluation dramatically. In addition, a hybrid fitness evaluation strategy that combines the exact and approximated fitness evaluation methods is presented to balance the accuracy and time efficiency of fitness evaluation. The effectiveness and efficiency of the proposed methods are testified and evaluated on a large set of benchmark instances of various scales, and the advantage of MA/FA on keeping good balance between effectiveness and efficiency is also observed.

Imbalanced learning problems contain an unequal distribution of data samples among different classes and pose a challenge to any classifier as it becomes hard to learn the minority class samples. Synthetic oversampling methods address this problem by generating the synthetic minority class samples to balance the distribution between the samples of the majority and minority classes. This paper identifies that most of the existing oversampling methods may generate the wrong synthetic minority samples in some scenarios and make learning tasks harder. To this end, a new method, called Majority Weighted Minority Oversampling TEchnique (MWMOTE), is presented for efficiently handling imbalanced learning problems. MWMOTE first identifies the hard-to-learn informative minority class samples and assigns them weights according to their euclidean distance from the nearest majority class samples. It then generates the synthetic samples from the weighted informative minority class samples using a clustering approach. This is done in such a way that all the generated samples lie inside some minority class cluster. MWMOTE has been evaluated extensively on four artificial and 20 real-world data sets. The simulation results show that our method is better than or comparable with some other existing methods in terms of various assessment metrics, such as geometric mean (G-mean) and area under the receiver operating curve (ROC), usually known as area under curve (AUC).

The emergence of large sensor networks has facilitated the collection of large amounts of real-time data to monitor and control complex engineering systems. However, in many cases the collected data may be incomplete or inconsistent, while the underlying environment may be time-varying or unformulated. In this paper, we develop an innovative cognitive fault diagnosis framework that tackles the above challenges. This framework investigates fault diagnosis in the model space instead of the signal space. Learning in the model space is implemented by fitting a series of models using a series of signal segments selected with a sliding window. By investigating the learning techniques in the fitted model space, faulty models can be discriminated from healthy models using a one-class learning algorithm. The framework enables us to construct a fault library when unknown faults occur, which can be regarded as cognitive fault isolation. This paper also theoretically investigates how to measure the pairwise distance between two models in the model space and incorporates the model distance into the learning algorithm in the model space. The results on three benchmark applications and one simulated model for the Barcelona water distribution network confirm the effectiveness of the proposed framework.

Probabilistic classification vector machine (PCVM) is a sparse learning approach aiming to address the stability problems of relevance vector machine for classification problems. Because PCVM is based on the expectation maximization algorithm, it suffers from sensitivity to initialization, convergence to local minima, and the limitation of Bayesian estimation making only point estimates. Another disadvantage is that PCVM was not efficient for large data sets. To address these problems, this paper proposes an efficient PCVM (EPCVM) by sequentially adding or deleting basis functions according to the marginal likelihood maximization for efficient training. Because of the truncated prior used in EPCVM, two approximation techniques, i.e., Laplace approximation and expectation propagation (EP), have been used to implement EPCVM to obtain full Bayesian solutions. We have verified Laplace approximation and EP with a hybrid Monte Carlo approach. The generalization performance and computational effectiveness of EPCVM are extensively evaluated. Theoretical discussions using Rademacher complexity reveal the relationship between the sparsity and the generalization bound of EPCVM.

In this article we present an approach to object tracking handover in a network of smart cameras, based on self-interested autonomous agents, which exchange responsibility for tracking objects in a market mechanism, in order to maximise their own utility. A novel ant-colony inspired mechanism is used to learn the vision graph, that is, the camera neighbourhood relations, during runtime, which may then be used to optimise communication between cameras. The key benefits of our completely decentralised approach are on the one hand generating the vision graph online, enabling efficient deployment in unknown scenarios and camera network topologies, and on the other hand relying only on local information, increasing the robustness of the system. Since our market-based approach does not rely on a priori topology information, the need for any multicamera calibration can be avoided. We have evaluated our approach both in a simulation study and in network of real distributed smart cameras.

Several variants of evolutionary algorithms (EAs) have been applied to solve the project scheduling problem (PSP), yet their performance highly depends on design choices for the EA. It is still unclear how and why different EAs perform differently. We present the first runtime analysis for the PSP, gaining insights into the performance of EAs on the PSP in general, and on specific instance classes that are easy or hard. Our theoretical analysis has practical implications-based on it, we derive an improved EA design. This includes normalizing employees' dedication for different tasks to ensure they are not working overtime; a fitness function that requires fewer pre-defined parameters and provides a clear gradient towards feasible solutions; and an improved representation and mutation operator. Both our theoretical and empirical results show that our design is very effective. Combining the use of normalization to a population gave the best results in our experiments, and normalization was a key component for the practical effectiveness of the new design. Not only does our paper offer a new and effective algorithm for the PSP, it also provides a rigorous theoretical analysis to explain the efficiency of the algorithm, especially for increasingly large projects.

Market mechanisms are a means by which resources in contention can be allocated between contending parties, both in human economies and those populated by software agents. Designing such mechanisms has traditionally been carried out by hand, and more recently by automation. Assessing these mechanisms typically involves them being evaluated with respect to multiple conflicting objectives, which can often be nonlinear, noisy, and expensive to compute. For typical performance objectives, it is known that designed mechanisms often fall short on being optimal across all objectives simultaneously. However, in all previous automated approaches, either only a single objective is considered, or else the multiple performance objectives are combined into a single objective. In this paper we do not aggregate objectives, instead considering a direct, novel application of multi-objective evolutionary algorithms (MOEAs) to the problem of automated mechanism design. This allows the automatic discovery of trade-offs that such objectives impose on mechanisms. We pose the problem of mechanism design, specifically for the class of linear redistribution mechanisms, as a naturally existing multi-objective optimisation problem. We apply a modified version of NSGA-II in order to design mechanisms within this class, given economically relevant objectives such as welfare and fairness. This application of NSGA-II exposes tradeoffs between objectives, revealing relationships between them that were otherwise unknown for this mechanism class. The understanding of the trade-off gained from the application of MOEAs can thus help practitioners with an insightful application of discovered mechanisms in their respective real/artificial markets.

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

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.

Concept drift detection methods are crucial components of many online learning approaches. Accurate drift detections allow prompt reaction to drifts and help to maintain high performance of online models over time. Although many methods have been proposed, no attention has been given to data streams with imbalanced class distributions, which commonly exist in real-world applications, such as fault diagnosis of control systems and intrusion detection in computer networks. This paper studies the concept drift problem for online class imbalance learning. We look into the impact of concept drift on single-class performance of online models based on three types of classifiers, under seven different scenarios with the presence of class imbalance. The analysis reveals that detecting drift in imbalanced data streams is a more difficult task than in balanced ones. Minority-class recall suffers from a significant drop after the drift involving the minority class. Overall accuracy is not suitable for drift detection. Based on the findings, we propose a new detection method DDM-OCI derived from the existing method DDM. DDM-OCI monitors minority-class recall online to capture the drift. The results show a quick response of the online model working with DDM-OCI to the new concept.

We present novel, efficient, model based kernels for time series data rooted in the reservoir computation framework. The kernels are implemented by fitting reservoir models sharing the same fixed deterministically constructed state transition part to individual time series. The proposed kernels can naturally handle time series of different length without the need to specify a parametric model class for the time series. Compared with most time series kernels, our kernels are computationally efficient. We show how the model distances used in the kernel can be calculated analytically or efficiently estimated. The experimental results on synthetic and benchmark time series classification tasks confirm the efficiency of the proposed kernel in terms of both generalization accuracy and computational speed. This paper also investigates on-line reservoir kernel construction for extremely long time series.

Although class imbalance learning and online learning have been extensively studied in the literature separately, online class imbalance learning that considers the challenges of both fields has not drawn much attention. It deals with data streams having very skewed class distributions, such as fault diagnosis of real-time control monitoring systems and intrusion detection in computer networks. To fill in this research gap and contribute to a wide range of real-world applications, this paper first formulates online class imbalance learning problems. Based on the problem formulation, a new online learning algorithm, sampling-based online bagging (SOB), is proposed to tackle class imbalance adaptively. Then, we study how SOB and other state-of-the-art methods can benefit a class of fault detection data under various scenarios and analyze their performance in depth. Through extensive experiments, we find that SOB can balance the performance between classes very well across different data domains and produce stable G-mean when learning constantly imbalanced data streams, but it is sensitive to sudden changes in class imbalance, in which case SOB's predecessor undersampling-based online bagging (UOB) is more robust.

Ensembles of learning machines and locality are considered two important topics for the next research frontier on Software Effort Estimation (SEE). We aim at (1) evaluating whether existing automated ensembles of learning machines generally improve SEEs given by single learning machines and which of them would be more useful; (2) analysing the adequacy of different locality approaches; and getting insight on (3) how to improve SEE and (4) how to evaluate/choose machine learning (ML) models for SEE. A principled experimental framework is used for the analysis and to provide insights that are not based simply on intuition or speculation. A comprehensive experimental study of several automated ensembles, single learning machines and locality approaches, which present features potentially beneficial for SEE, is performed. Additionally, an analysis of feature selection and regression trees (RTs), and an investigation of two tailored forms of combining ensembles and locality are performed to provide further insight on improving SEE. Bagging ensembles of RTs show to perform well, being highly ranked in terms of performance across different data sets, being frequently among the best approaches for each data set and rarely performing considerably worse than the best approach for any data set. They are recommended over other learning machines should an organisation have no resources to perform experiments to chose a model. Even though RTs have been shown to be more reliable locality approaches, other approaches such as k-Means and k-Nearest Neighbours can also perform well, in particular for more heterogeneous data sets. Combining the power of automated ensembles and locality can lead to competitive results in SEE. By analysing such approaches, we provide several insights that can be used by future research in the area.

The current European debt crisis has drawn considerable attention to credit-rating agencies' news about sovereign ratings. From a technical point of view, credit rating constitutes a typical ordinal regression problem because credit-rating agencies generally present a scale of risk composed of several categories. This fact motivated the use of an ordinal regression approach to address the problem of sovereign credit rating in this paper. Therefore, the ranking of different classes will be taken into account for the design of the classifier. To do so, a novel model is introduced in order to replicate sovereign rating, based on the negative correlation learning framework. The methodology is fully described in this paper and applied to the classification of the 27 European countries' sovereign rating during the 2007-2010 period based on Standard and Poor's reports. The proposed technique seems to be competitive and robust enough to classify the sovereign ratings reported by this agency when compared with other existing well-known ordinal and nominal methods.

In classification, machine learning algorithms can suffer a performance bias when data sets are unbalanced. Data sets are unbalanced when at least one class is represented by only a small number of training examples (called the minority class), while the other class(es) make up the majority. In this scenario, classifiers can have good accuracy on the majority class, but very poor accuracy on the minority class(es). This paper proposes a multiobjective genetic programming (MOGP) approach to evolving accurate and diverse ensembles of genetic program classifiers with good performance on both the minority and majority of classes. The evolved ensembles comprise of nondominated solutions in the population where individual members vote on class membership. This paper evaluates the effectiveness of two popular Pareto-based fitness strategies in the MOGP algorithm (SPEA2 and NSGAII), and investigates techniques to encourage diversity between solutions in the evolved ensembles. Experimental results on six (binary) class imbalance problems show that the evolved ensembles outperform their individual members, as well as single-predictor methods such as canonical GP, naive Bayes, and support vector machines, on highly unbalanced tasks. This highlights the importance of developing an effective fitness evaluation strategy in the underlying MOGP algorithm to evolve good ensemble members.

Since estimation of distribution algorithms (EDAs) were proposed, many attempts have been made to improve EDAs' performance in the context of global optimization. So far, the studies or applications of multivariate probabilistic model-based EDAs in continuous domain are still mostly restricted to low-dimensional problems. Traditional EDAs have difficulties in solving higher dimensional problems because of the curse of dimensionality and rapidly increasing computational costs. However, scaling up continuous EDAs for large-scale optimization is still necessary, which is supported by the distinctive feature of EDAs: because a probabilistic model is explicitly estimated, from the learned model one can discover useful properties of the problem. Besides obtaining a good solution, understanding of the problem structure can be of great benefit, especially for black box optimization. We propose a novel EDA framework with model complexity control (EDA-MCC) to scale up continuous EDAs. By employing weakly dependent variable identification and subspace modeling, EDA-MCC shows significantly better performance than traditional EDAs on high-dimensional problems. Moreover, the computational cost and the requirement of large population sizes can be reduced in EDA-MCC. In addition to being able to find a good solution, EDA-MCC can also provide useful problem structure characterizations. EDA-MCC is the first successful instance of multivariate model-based EDAs that can be effectively applied to a general class of up to 500-D problems. It also outperforms some newly developed algorithms designed specifically for large-scale optimization. In order to understand the strengths and weaknesses of EDA-MCC, we have carried out extensive computational studies. Our results have revealed when EDA-MCC is likely to outperform others and on what kind of benchmark functions.

Unlike evolutionary dynamics, coevolutionary dynamics can exhibit a wide variety of complex regimes. This has been confirmed by numerical studies, e.g., in the context of evolutionary game theory (EGT) and population dynamics of simple two-strategy games with various types of replication and selection mechanisms. Using the framework of shadowing lemma, we study to what degree can such infinite population dynamics: 1) be reliably simulated on finite precision computers; and 2) be trusted to represent coevolutionary dynamics of possibly very large, but finite, populations. In a simple EGT setting of two-player symmetric games with two pure strategies and a polymorphic equilibrium, we prove that for (μ,λ), truncation, sequential tournament, best-of-group tournament, and linear ranking selections, the coevolutionary dynamics do not possess the shadowing property. In other words, infinite population simulations cannot be guaranteed to represent real trajectories or to be representative of coevolutionary dynamics of potentially very large, but finite, populations.

In class imbalance learning problems, how to better recognize examples from the minority class is the key focus, since it is usually more important and expensive than the majority class. Quite a few ensemble solutions have been proposed in the literature with varying degrees of success. It is generally believed that diversity in an ensemble could help to improve the performance of class imbalance learning. However, no study has actually investigated diversity in depth in terms of its definitions and effects in the context of class imbalance learning. It is unclear whether diversity will have a similar or different impact on the performance of minority and majority classes. In this paper, we aim to gain a deeper understanding of if and when ensemble diversity has a positive impact on the classification of imbalanced data sets. First, we explain when and why diversity measured by Q-statistic can bring improved overall accuracy based on two classification patterns proposed by Kuncheva et al. We define and give insights into good and bad patterns in imbalanced scenarios. Then, the pattern analysis is extended to single-class performance measures, including recall, precision, and F-measure, which are widely used in class imbalance learning. Six different situations of diversity's impact on these measures are obtained through theoretical analysis. Finally, to further understand how diversity affects the single class performance and overall performance in class imbalance problems, we carry out extensive experimental studies on both artificial data sets and real-world benchmarks with highly skewed class distributions. We find strong correlations between diversity and discussed performance measures. Diversity shows a positive impact on the minority class in general. It is also beneficial to the overall performance in terms of AUC and G-mean.

In this paper, two neural network threshold ensemble models are proposed for ordinal regression problems. For the first ensemble method, the thresholds are fixed a priori and are not modified during training. The second one considers the thresholds of each member of the ensemble as free parameters, allowing their modification during the training process. This is achieved through a reformulation of these tunable thresholds, which avoids the constraints they must fulfill for the ordinal regression problem. During training, diversity exists in different projections generated by each member is taken into account for the parameter updating. This diversity is promoted in an explicit way using a diversity-encouraging error function, extending the well-known negative correlation learning framework to the area of ordinal regression, and inheriting many of its good properties. Experimental results demonstrate that the proposed algorithms can achieve competitive generalization performance when considering four ordinal regression metrics.

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.

Ensembles of learning machines are promising for software effort estimation (SEE), but need to be tailored for this task to have their potential exploited. A key issue when creating ensembles is to produce diverse and accurate base models. Depending on how differently different performance measures behave for SEE, they could be used as a natural way of creating SEE ensembles. We propose to view SEE model creation as a multiobjective learning problem. A multiobjective evolutionary algorithm (MOEA) is used to better understand the tradeoff among different performance measures by creating SEE models through the simultaneous optimisation of these measures. We show that the performance measures behave very differently, presenting sometimes even opposite trends. They are then used as a source of diversity for creating SEE ensembles. A good tradeoff among different measures can be obtained by using an ensemble of MOEA solutions. This ensemble performs similarly or better than a model that does not consider these measures explicitly. Besides, MOEA is also flexible, allowing emphasis of a particular measure if desired. In conclusion, MOEA can be used to better understand the relationship among performance measures and has shown to be very effective in creating SEE models.

To facilitate software testing, and save testing costs, a wide range of machine learning methods have been studied to predict defects in software modules. Unfortunately, the imbalanced nature of this type of data increases the learning difficulty of such a task. Class imbalance learning specializes in tackling classification problems with imbalanced distributions, which could be helpful for defect prediction, but has not been investigated in depth so far. In this paper, we study the issue of if and how class imbalance learning methods can benefit software defect prediction with the aim of finding better solutions. We investigate different types of class imbalance learning methods, including resampling techniques, threshold moving, and ensemble algorithms. Among those methods we studied, AdaBoost.NC shows the best overall performance in terms of the measures including balance, G-mean, and Area Under the Curve (AUC). To further improve the performance of the algorithm, and facilitate its use in software defect prediction, we propose a dynamic version of AdaBoost.NC, which adjusts its parameter automatically during training. Without the need to pre-define any parameters, it is shown to be more effective and efficient than the original AdaBoost.NC.

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.

Search Based Software Engineering (SBSE) has proved to be a very effective way of optimising software engineering problems. Nevertheless, its full potential as a means of dynamic adaptivity remains under explored. This paper sets out the agenda for Dynamic Adaptive SBSE, in which the optimisation is embedded into deployed software to create self-optimising adaptive systems. Dynamic Adaptive SBSE will move the research agenda forward to encompass both software development processes and the software products they produce, addressing the long-standing, and as yet largely unsolved, grand challenge of self-adaptive systems.

Even though genetic algorithms (GAs) have been used for solving the project scheduling problem (PSP), it is not well understood which problem characteristics make it difficult/easy for GAs. We present the first runtime analysis for the PSP, revealing what problem features can make PSP easy or hard. This allows to assess the performance of GAs and to make informed design choices. Our theory has inspired a new evolutionary design, including normalisation of employees' dedication for different tasks to eliminate the problem of exceeding their maximum dedication. Theoretical and empirical results show that our design is very effective in terms of hit rate and solution quality.

Some machine learning applications involve the question of whether or not to use unreliable data for the learning. Previous work shows that learners trained using unreliable data in addition to reliable data present either similar or worse performance than learners trained solely on reliable data. Such learners frequently use unreliable data as if they were reliable and consider only the offline learning scenario. The present paper shows that it is possible to use unreliable data to improve the performance in online learning scenarios with a pre-existing set of unreliable data. We propose an approach called Dynamic Un+Reliable data learners (DUR) able to determine when unreliable data could be useful by maintaining a fixed size weighted memory of unreliable data learners. The weights represent how well learners perform for the current concept and are updated throughout DUR's lifetime. This approach manages not only to outperform an approach which uses only reliable data, but also an approach which uses unreliable data as if they were reliable. Moreover, the variance in performance is reduced in comparison to the approach which uses only reliable data. In other words, DUR is a more reliable learner.

Engineered systems are designed to deftly operate under predetermined conditions yet are notoriously fragile when unexpected perturbations arise. In contrast, biological systems operate in a highly flexible manner; learn quickly adequate responses to novel conditions, and evolve new routines and traits to remain competitive under persistent environmental change. A recent theory on the origins of biological flexibility has proposed that degeneracy-the existence of multi-functional components with partially overlapping functions-is a primary determinant of the robustness and adaptability found in evolved systems. While degeneracy's contribution to biological flexibility is well documented, there has been little investigation of degeneracy design principles for achieving flexibility in systems engineering. Actually, the conditions that can lead to degeneracy are routinely eliminated in engineering design. With the planning of transportation vehicle fleets taken as a case study, this article reports evidence that degeneracy improves the robustness and adaptability of a simulated fleet towards unpredicted changes in task requirements without incurring costs to fleet efficiency. We find that degeneracy supports faster rates of design adaptation and ultimately leads to better fleet designs. In investigating the limitations of degeneracy as a design principle, we consider decision-making difficulties that arise from degeneracy's influence on fleet complexity. While global decision-making becomes more challenging, we also find degeneracy accommodates rapid distributed decision-making leading to (near-optimal) robust system performance. Given the range of conditions where favorable short-term and long-term performance outcomes are observed, we propose that degeneracy may fundamentally alter the propensity for adaptation and is useful within different engineering and planning contexts.

Many real-world dynamic problems have constraints, and in certain cases not only the objective function changes over time, but also the constraints. However, there is no research in answering the question of whether current algorithms work well on continuous dynamic constrained optimization problems (DCOPs), nor is there any benchmark problem that reflects the common characteristics of continuous DCOPs. This paper contributes to the task of closing this gap. We will present some investigations on the characteristics that might make DCOPs difficult to solve by some existing dynamic optimization (DO) and constraint handling (CH) algorithms. We will then introduce a set of benchmark problems with these characteristics and test several representative DO and CH strategies on these problems. The results confirm that DCOPs do have special characteristics that can significantly affect algorithm performance. The results also reveal some interesting observations where the presence or combination of different types of dynamics and constraints can make the problems easier to solve for certain types of algorithms. Based on the analyses of the results, a list of potential requirements that an algorithm should meet to solve DCOPs effectively will be proposed.

Recently, the generalization framework in co-evolutionary learning has been theoretically formulated and demonstrated in the context of game-playing. Generalization performance of a strategy (solution) is estimated using a collection of random test strategies (test cases) by taking the average game outcomes, with confidence bounds provided by Chebyshev's theorem. Chebyshev's bounds have the advantage that they hold for any distribution of game outcomes. However, such a distribution-free framework leads to unnecessarily loose confidence bounds. In this paper, we have taken advantage of the near-Gaussian nature of average game outcomes and provided tighter bounds based on parametric testing. This enables us to use small samples of test strategies to guide and improve the co-evolutionary search. We demonstrate our approach in a series of empirical studies involving the iterated prisoner's dilemma (IPD) and the more complex Othello game in a competitive co-evolutionary learning setting. The new approach is shown to improve on the classical co-evolutionary learning in that we obtain increasingly higher generalization performance using relatively small samples of test strategies. This is achieved without large performance fluctuations typical of the classical approach. The new approach also leads to faster co-evolutionary search where we can strictly control the condition (sample sizes) under which the speedup is achieved (not at the cost of weakening precision in the estimates).

The interplay between mutation and selection plays a fundamental role in the behavior of evolutionary algorithms (EAs). However, this interplay is still not completely understood. This paper presents a rigorous runtime analysis of a non-elitist population-based EA that uses the linear ranking selection mechanism. The analysis focuses on how the balance between parameter η, controlling the selection pressure in linear ranking, and parameter χ controlling the bit-wise mutation rate, impacts the runtime of the algorithm. The results point out situations where a correct balance between selection pressure and mutation rate is essential for finding the optimal solution in polynomial time. In particular, it is shown that there exist fitness functions which can only be solved in polynomial time if the ratio between parameters η and χ is within a narrow critical interval, and where a small change in this ratio can increase the runtime exponentially. Furthermore, it is shown quantitatively how the appropriate parameter choice depends on the characteristics of the fitness function. In addition to the original results on the runtime of EAs, this paper also introduces a very useful analytical tool, i.e., multi-type branching processes, to the runtime analysis of non-elitist population-based EAs.

This paper presents a new cooperative coevolving particle swarm optimization (CCPSO) algorithm in an attempt to address the issue of scaling up particle swarm optimization (PSO) algorithms in solving large-scale optimization problems (up to 2000 real-valued variables). The proposed CCPSO2 builds on the success of an early CCPSO that employs an effective variable grouping technique random grouping. CCPSO2 adopts a new PSO position update rule that relies on Cauchy and Gaussian distributions to sample new points in the search space, and a scheme to dynamically determine the coevolving subcomponent sizes of the variables. On high-dimensional problems (ranging from 100 to 2000 variables), the performance of CCPSO2 compared favorably against a state-of-the-art evolutionary algorithm sep-CMA-ES, two existing PSO algorithms, and a cooperative coevolving differential evolution algorithm. In particular, CCPSO2 performed significantly better than sep-CMA-ES and two existing PSO algorithms on more complex multimodal problems (which more closely resemble real-world problems), though not as well as the existing algorithms on unimodal functions. Our experimental results and analysis suggest that CCPSO2 is a highly competitive optimization algorithm for solving large-scale and complex multimodal optimization problems.

Online learning algorithms often have to operate in the presence of concept drifts. A recent study revealed that different diversity levels in an ensemble of learning machines are required in order to maintain high generalization on both old and new concepts. Inspired by this study and based on a further study of diversity with different strategies to deal with drifts, we propose a new online ensemble learning approach called Diversity for Dealing with Drifts (DDD). DDD maintains ensembles with different diversity levels and is able to attain better accuracy than other approaches. Furthermore, it is very robust, outperforming other drift handling approaches in terms of accuracy when there are false positive drift detections. In all the experimental comparisons we have carried out, DDD always performed at least as well as other drift handling approaches under various conditions, with very few exceptions.

Semisupervised classification (SSC) learns, from cheap unlabeled data and labeled data, to predict the labels of test instances. In order to make use of the information from unlabeled data, there should be an assumed relationship between the true class structure and the data distribution. One assumption is that data points clustered together are likely to have the same class label. In this paper, we propose a new algorithm, namely, cluster-based regularization (ClusterReg) for SSC, that takes the partition given by a clustering algorithm as a regularization term in the loss function of an SSC classifier. ClusterReg makes predictions according to the cluster structure together with limited labeled data. The experiments confirmed that ClusterReg has a good generalization ability for real-world problems. Its performance is excellent when data follows this cluster assumption. Even when these clusters have misleading overlaps, it still outperforms other state-of-the-art algorithms.

Interactions between multiple tunable protocol parameters and multiple performance metrics are generally complex and unknown; finding optimal solutions is generally difficult. However, protocol tuning can yield significant gains in energy efficiency and resource requirements, which is of particular importance for sensornet systems in which resource availability is severely restricted. We address this multi-objective optimization problem for two dissimilar routing protocols and by two distinct approaches. First, we apply factorial design and statistical model fitting methods to reject insignificant factors and locate regions of the problem space containing near-optimal solutions by principled search. Second, we apply the Strength Pareto Evolutionary Algorithm 2 and Two-Archive evolutionary algorithms to explore the problem space, with each iteration potentially yielding solutions of higher quality and diversity than the preceding iteration. Whereas a principled search methodology yields a generally applicable survey of the problem space and enables performance prediction, the evolutionary approach yields viable solutions of higher quality and at lower experimental cost. This is the first study in which sensornet protocol optimization has been explicitly formulated as a multi-objective problem and solved with state-of-the-art multi-objective evolutionary algorithms.

Class imbalance problems have drawn growing interest recently because of their classification difficulty caused by the imbalanced class distributions. In particular, many ensemble methods have been proposed to deal with such imbalance. However, most efforts so far are only focused on two-class imbalance problems. There are unsolved issues in multiclass imbalance problems, which exist in real-world applications. This paper studies the challenges posed by the multiclass imbalance problems and investigates the generalization ability of some ensemble solutions, including our recently proposed algorithm AdaBoost.NC, with the aim of handling multiclass and imbalance effectively and directly. We first study the impact of multiminority and multimajority on the performance of two basic resampling techniques. They both present strong negative effects. "Multimajority" tends to be more harmful to the generalization performance. Motivated by the results, we then apply AdaBoost.NC to several real-world multiclass imbalance tasks and compare it to other popular ensemble methods. AdaBoost.NC is shown to be better at recognizing minority class examples and balancing the performance among classes in terms of G-mean without using any class decomposition.

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.

Markets are useful mechanisms for performing resource allocation in fully decentralised computational and other systems, since they can possess a range of desirable properties, such as efficiency, decentralisation, robustness and scalability. In this paper we investigate the behaviour of co-evolving evolutionary market agents as adaptive offer generators for sellers in a multi-attribute posted-offer market. We demonstrate that the evolutionary approach enables sellers to automatically position themselves in market niches, created by heterogeneous buyers. We find that a trade-off exists for the evolutionary sellers between maintaining high population diversity to facilitate movement between niches and low diversity to exploit the current niche and maximise cumulative payoff. We characterise the trade-off from the perspective of the system as a whole, and subsequently from that of an individual seller. Our results highlight a decision on risk aversion for resource providers, but crucially we show that rational self-interested sellers would not adopt the behaviour likely to lead to the ideal result from the system point of view.

We propose a novel method for allocating multi-attribute computational resources via competing marketplaces. Trading agents, working on behalf of resource consumers and providers, choose to trade in resource markets where the resources being traded best align with their preferences and constraints. Market-exchange agents, in competition with each other, attempt to provide resource markets that attract traders, with the goal of maximising their profit. Because exchanges can only partially observe global supply and demand schedules, novel strategies are required to automate their search for market niches. Novel attribute-level selection (ALS) strategies are empirically analysed in simulated competitive market environments, and results suggest that using these strategies, market-exchanges can seek out market niches under a variety of environmental conditions.

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.

Computational performance increasingly depends on parallelism, and many systems rely on heterogeneous resources such as GPUs and FPGAs to accelerate computationally intensive applications. However, implementations for such heterogeneous systems are often hand-crafted and optimised to one computation scenario, and it can be challenging to maintain high performance when application parameters change. In this paper, we demonstrate that machine learning can help to dynamically choose parameters for task scheduling and load-balancing based on changing characteristics of the incoming workload. We use a financial option pricing application as a case study. We propose a simulation of processing financial tasks on a heterogeneous system with GPUs and FPGAs, and show how dynamic, on-line optimisations could improve such a system. We compare on-line and batch processing algorithms, and we also consider cases with no dynamic optimisations.

Body morphology is thought to have heavily influenced the evolution of neural architecture. However, the extent of this interaction and its underlying principles are largely unclear. To help us elucidate these principles, we examine the artificial evolution of a hypothetical nervous system embedded in a fish-inspired animat. The aim is to observe the evolution of neural structures in relation to both body morphology and required motor primitives. Our investigations reveal that increasing the pressure to evolve a wider range of movements also results in higher levels of neural symmetry. We further examine how different body shapes affect the evolution of neural structure; we find that, in order to achieve optimal movements, the neural structure integrates and compensates for asymmetrical body morphology. Our study clearly indicates that different parts of the animat - specifically, nervous system and body plan - evolve in concert with and become highly functional with respect to the other parts. The autonomous emergence of morphological and neural computation in this model contributes to unveiling the surprisingly strong coupling of such systems in nature.

Standard Cooperative Co-evolution uses a round-robin method to select subcomponents to undergo optimization. In a non-separable (epistatic) optimization problem, dividing the computational budget equally between all of the subcomponents is not necessarily the best strategy. When dealing with non-separable problems, there is usually an imbalance between the contribution of various subcomponents to the global fitness of the individuals. Using a round-robin fashion treats all of the subcomponents equally and wastes the computational budget. In this paper, we propose a Contribution Based Cooperative Co-evolution (CBCC) that selects the subcomponents based on their contributions to the global fitness. This alleviates the imbalance issue and allows the computational resources to be used more efficiently. Experiments on several benchmark functions with the "imbalance issue" show that this new scheme is promising, especially when it is combined with a grouping algorithm that captures interacting variables in common subcomponents.

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.

Software module clustering is the problem of automatically organizing software units into modules to improve program structure. There has been a great deal of recent interest in search-based formulations of this problem in which module boundaries are identified by automated search, guided by a fitness function that captures the twin objectives of high cohesion and low coupling in a single-objective fitness function. This paper introduces two novel multi-objective formulations of the software module clustering problem, in which several different objectives (including cohesion and coupling) are represented separately. In order to evaluate the effectiveness of the multi-objective approach, a set of experiments was performed on 17 real-world module clustering problems. The results of this empirical study provide strong evidence to support the claim that the multi-objective approach produces significantly better solutions than the existing single-objective approach.

In the application of evolutionary algorithms (EAs) to complex problem solving, it is essential to maintain proper balance between global exploration and local exploitation to achieve a good near-optimum solution to the problem. This paper presents a recurring two-stage evolutionary programming (RTEP) to balance the explorative and exploitative features of the conventional EAs. Unlike most previous works, RTEP is based on repeated and alternated execution of two different stages, namely, the exploration and exploitation stages, each with its own mutation operator, selection strategy, and explorative/exploitative objective. Both analytical and empirical studies have been carried out to understand the necessity of repeated and alternated exploration and exploitation operations in EAs. A suite of 48 benchmark numerical optimization problems has been used in the empirical studies. The experimental results show the remarkable effectiveness of the repeated exploration and exploitation operations employed by RTEP.

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

The capacitated arc routing problem (CARP) is representative of numerous practical applications, and in order to widen its scope, we consider an extended version of this problem that entails both total service time and fixed investment costs. We subsequently propose a hybrid ant colony optimization (ACO) algorithm (HACOA) to solve instances of the extended CARP. This approach is characterized by the exploitation of heuristic information, adaptive parameters, and local optimization techniques: Two kinds of heuristic information, arc cluster information and arc priority information, are obtained continuously from the solutions sampled to guide the subsequent optimization process. The adaptive parameters ease the burden of choosing initial values and facilitate improved and more robust results. Finally, local optimization, based on the two-opt heuristic, is employed to improve the overall performance of the proposed algorithm. The resulting HACOA is tested on four sets of benchmark problems containing a total of 87 instances with up to 140 nodes and 380 arcs. In order to evaluate the effectiveness of the proposed method, some existing capacitated arc routing heuristics are extended to cope with the extended version of this problem; the experimental results indicate that the proposed ACO method outperforms these heuristics.

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.

Many evolutionary algorithms have been proposed for large scale optimization. Parameter interaction in non-separable problems is a major source of performance loss specially on large scale problems. Cooperative Co-evolution(CC) has been proposed as a natural solution for large scale optimization problems, but lack of a systematic way of decomposing large scale non-separable problems is a major obstacle for CC frameworks. The aim of this paper is to propose a systematic way of capturing interacting variables for a more effective problem decomposition suitable for cooperative co-evolutionary frameworks. Grouping interacting variables in different subcomponents in a CC framework imposes a limit to the extent interacting variables can be optimized to their optimum values, in other words it limits the improvement interval of interacting variables. This is the central idea of the newly proposed technique which is called delta method. Delta method measures the averaged difference in a certain variable across the entire population and uses it for identifying interacting variables. The experimental results show that this new technique is more effective than the existing random grouping method.

In this paper we propose three techniques to improve the performance of one of the major algorithms for large scale continuous global function optimization. Multilevel Cooperative Co-evolution (MLCC) is based on a Cooperative Co-evolutionary framework and employs a technique called random grouping in order to group interacting variables in one subcomponent. It also uses another technique called adaptive weighting for co-adaptation of subcomponents. We prove that the probability of grouping interacting variables in one subcomponent using random grouping drops significantly as the number of interacting variables increases. This calls for more frequent random grouping of variables. We show how to increase the frequency of random grouping without increasing the number of fitness evaluations. We also show that adaptive weighting is ineffective and in most cases fails to improve the quality of found solution, and hence wastes considerable amount of CPU time by extra evaluations of objective function. Finally we propose a new technique for self-adaptation of the subcomponent sizes in CC. We demonstrate how a substantial improvement can be gained by applying these three techniques.

The field of evolutionary dynamic optimisation is concerned with the application of evolutionary algorithms to dynamic optimisation problems. In recent years, numerous new algorithms have been proposed to track the problem's potentially moving global optimum as closely as possible. A large proportion of these techniques attempts to exploit possible similarities between successive problem instances, primarily using previously found solutions as starting points for future instances: If the previous global optimum is in close proximity to the new global optimum (in the genotype space), such transfer of knowledge should allow the algorithm to locate the new global optimum in less time than a random restart may require. However, it is clear that distance alone may be insufficient to guarantee such computational savings. In this paper, we propose a simple framework that may be used to create bi-modular problems with a variable degree of epistasis. We subsequently study how the dependencies between the two modules may affect the difficulty (number of function evaluation required) of relocating the new global optimum. We find that, given a simple (1+1) EA, even a modest degree of linkage between the problem's otherwise independent modules may have a significant impact on these attributes.

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.

This paper proposes a new negative correlation learning (NCL) algorithm, called AdaBoost.NC, which uses an ambiguity term derived theoretically for classification ensembles to introduce diversity explicitly. All existing NCL algorithms, such as CELS and NCCD, and their theoretical backgrounds were studied in the regression context. We focus on classification problems in this paper. First, we study the ambiguity decomposition with the 0-1 error function, which is different from the one proposed by Krogh et al.. It is applicable to both binary-class and multi-class problems. Then, to overcome the identified drawbacks of the existing algorithms, AdaBoost.NC is proposed by exploiting the ambiguity term in the decomposition to improve diversity. Comprehensive experiments are performed on a collection of benchmark data sets. The results show AdaBoost.NC is a promising algorithm to solve classification problems, which gives better performance than the standard AdaBoost and NCCD, and consumes much less computation time than CELS.

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.

The capacitated arc routing problem (CARP) is a challenging vehicle routing problem with numerous real world applications. In this paper, an extended version of CARP, the multidepot capacitated arc routing problem (MCARP), is presented to tackle practical requirements. Existing CARP heuristics are extended to cope with MCARP and are integrated into a novel evolutionary framework: the initial population is constructed either by random generation, the extended random path-scanning heuristic, or the extended random Ulusoy's heuristic. Subsequently, multiple distinct operators are employed to perform selection, crossover, and mutation. Finally, the partial replacement procedure is implemented to maintain population diversity. The proposed evolutionary approach (EA) is primarily characterized by the exploitation of attributes found in near-optimal MCARP solutions that are obtained throughout the execution of the algorithm. Two techniques are employed toward this end: the performance information of an operator is applied to select from a range of operators for selection, crossover, and mutation. Furthermore, the arc assignment priority information is employed to determine promising positions along the genome for operations of crossover and mutation. The EA is evaluated on 107 instances with up to 140 nodes and 380 arcs. The experimental results suggest that the integrated evolutionary framework significantly outperforms these individual extended heuristics.

Negative Correlation Learning (NCL) [CHECK END OF SENTENCE], [CHECK END OF SENTENCE] is a neural network ensemble learning algorithm which introduces a correlation penalty term to the cost function of each individual network so that each neural network minimizes its mean-square-error (MSE) together with the correlation. This paper describes NCL in detail and observes that the NCL corresponds to training the entire ensemble as a single learning machine that only minimizes the MSE without regularization. This insight explains that NCL is prone to overfitting the noise in the training set. The paper analyzes this problem and proposes the multiobjective regularized negative correlation learning (MRNCL) algorithm which incorporates an additional regularization term for the ensemble and uses the evolutionary multiobjective algorithm to design ensembles. In MRNCL, we define the crossover and mutation operators and adopt nondominated sorting algorithm with fitness sharing and rank-based fitness assignment. The experiments on synthetic data as well as real-world data sets demonstrate that MRNCL achieves better performance than NCL, especially when the noise level is nontrivial in the data set. In the experimental discussion, we give three reasons why our algorithm outperforms others.

Online learning algorithms often have to operate in the presence of concept drift (i.e., the concepts to be learned can change with time). This paper presents a new categorization for concept drift, separating drifts according to different criteria into mutually exclusive and nonheterogeneous categories. Moreover, although ensembles of learning machines have been used to learn in the presence of concept drift, there has been no deep study of why they can be helpful for that and which of their features can contribute or not for that. As diversity is one of these features, we present a diversity analysis in the presence of different types of drifts. We show that, before the drift, ensembles with less diversity obtain lower test errors. On the other hand, it is a good strategy to maintain highly diverse ensembles to obtain lower test errors shortly after the drift independent on the type of drift, even though high diversity is more important for more severe drifts. Longer after the drift, high diversity becomes less important. Diversity by itself can help to reduce the initial increase in error caused by a drift, but does not provide the faster recovery from drifts in long-term.

Recently, sparse approximation has become a preferred method for learning large scale kernel machines. This technique attempts to represent the solution with only a subset of original data points also known as basis vectors, which are usually chosen one by one with a forward selection procedure based on some selection criteria. The computational complexity of several resultant algorithms scales as O(NM(2)) in time and O(NM) in memory, where N is the number of training points and M is the number of basis vectors as well as the steps of forward selection. For some large scale data sets, to obtain a better solution, we are sometimes required to include more basis vectors, which means that M is not trivial in this situation. However, the limited computational resource (e.g., memory) prevents us from including too many vectors. To handle this dilemma, we propose to add an ensemble of basis vectors instead of only one at each forward step. The proposed method, closely related to gradient boosting, could decrease the required number M of forward steps significantly and thus a large fraction of computational cost is saved. Numerical experiments on three large scale regression tasks and a classification problem demonstrate the effectiveness of the proposed approach.

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.

One of the main tasks software testing involves is the generation of the test inputs to be used during the test. Due to its expensive cost, the automation of this task has become one of the key issues in the area. Recently, this generation has been explicitly formulated as the resolution of a set of constrained optimisation problems. Differential Evolution (DE) is a population based evolutionary algorithm which has been successfully applied in a number of domains, including constrained optimisation. We present a test data generator employing DE to solve each of the constrained optimisation problems, and empirically evaluate its performance for several DE models. With the aim of comparing this technique with other approaches, we extend the experiments to the Breeder Genetic Algorithm and face it to DE, and compare different test data generators in the literature with the DE approach. The results present DE as a promising solution technique for this real-world problem.

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.

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.

In future massively distributed service-based computational systems, resources will span many locations, organisations and platforms. In such systems, the ability to allocate resources in a desired configuration, in a scalable and robust manner, will be essential.We build upon a previous evolutionary market-based approach to achieving resource allocation in decentralised systems, by considering heterogeneous providers. In such scenarios, providers may be said to value their resources differently. We demonstrate how, given such valuations, the outcome allocation may be predicted. Furthermore, we describe how the approach may be used to achieve a stable, uneven load-balance of our choosing. We analyse the system's expected behaviour, and validate our predictions in simulation. Our approach is fully decentralised; no part of the system is weaker than any other. No cooperation between nodes is assumed; only self-interest is relied upon. A particular desired allocation is achieved transparently to users, as no modification to the buyers is required.

This paper attempts to address the question of scaling up particle swarm optimization (PSO) algorithms to high dimensional optimization problems. We present a cooperative coevolving PSO (CCPSO) algorithm incorporating random grouping and adaptive weighting, two techniques that have been shown to be effective for handling high dimensional nonseparable problems. The proposed CCPSO algorithms out-performed a previously developed coevolving PSO algorithm on nonseparable functions of 30 dimensions. Furthermore, the scalability of the proposed algorithm to high dimensional nonseparable problems (of up to 1000 dimensions) is examined and compared with two existing coevolving differential evolution (DE) algorithms, and new insights are obtained. Our experimental results show the proposed CCPSO algorithms can perform reasonably well with only a small number of evaluations. The results also suggest that both the random grouping and adaptive weighting schemes are viable approaches that can be generalized to other evolutionary optimization methods.

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.

Many real-world dynamic optimisation problems have constraints, and in certain cases not only the objective function changes over time, but the constraints also change as well. However, in academic research there is not many research on continuous dynamic constrained optimization, and particularly there is little research on whether current numerical dynamic optimization algorithms would work well in dynamic constrained environments nor there is any numerical dynamic constrained benchmark problems. In this paper, we firstly investigate the characteristics that might make a dynamic constrained problems difficult to solve by existing dynamic optimization algorithms. We then introduce a set of numerical dynamic benchmark problems with these characteristics. To verify our hypothesis about the difficulty of these problems, we tested several canonical dynamic optimization algorithms on the proposed benchmarks. The test results confirm that dynamic constrained problems do have special characteristics that might not be solved effectively by some of the current dynamic optimization algorithms. Based on the analyses of the results, we propose a new algorithm to improve the performance of current dynamic optimization methods in solving numerical dynamic constrained problems. The test results show that the proposed algorithm achieves superior results compared to the tested existing dynamic optimization algorithms.

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.

A cooperative coevolutionary algorithm (CCEA) is an extension to an evolutionary algorithm (EA); it employs a divide and conquer strategy to solve an optimization problem. In its basic form, a CCEA splits the variables of an optimization problem into multiple smaller subsets and evolves them independently in different subpopulations. The dynamics of a CCEA is far more complex than an EA and its performance can vary from good to bad depending on the separability of the optimization problem. This paper provides some insights into why CCEA in its basic form is not suitable for nonseparable problems and introduces a cooperative coevolutionary algorithm with correlation based adaptive variable partitioning (CCEA-AVP) to deal with such problems. The performance of CCEA-AVP is compared with CCEA and EA to highlight its benefits. CCEA-AVP offers the possibility to deal with problems where separability among variables might vary in different regions of the search space.

A number of population based optimization algorithms have been proposed in recent years to solve unconstrained and constrained single and multi-objective optimization problems. Most of such algorithms inherently prefer a feasible solution over an infeasible one during the course of search, which translates to approaching the constraint boundary from the feasible side of the search space. Previous studies [1], [2] have already demonstrated the benefits of explicitly maintaining a fraction of infeasible solutions in Infeasiblity Driven Evolutionary Algorithm (IDEA) for single and multiobjective constrained optimization problems. In this paper, the benefits of IDEA as a sub-evolve mechanism are highlighted for dynamic, constrained single objective optimization problems. IDEA is particularly attractive for such problems as it offers a faster rate of convergence over a conventional EA, which is of significant interest in dynamic optimization problems. The algorithm is tested on two new dynamic constrained test problems. For both the problems, the performance of IDEA is found to be significantly better than conventional EA.