Parametric multi-objective optimization (PMO) addresses the challenge of solving an infinite family of multi-objective optimization problems, where optimal solutions must adapt to varying parameters. Traditional methods require re-execution for each parameter configuration, leading to prohibitive costs when objective evaluations are computationally expensive. To address this issue, we propose Parametric Pareto Set Learning with multi-objective Bayesian Optimization (PPSL-MOBO), a novel framework that learns a unified mapping from both preferences and parameters to Pareto-optimal solutions. PPSL-MOBO leverages a hypernetwork with Low-Rank Adaptation (LoRA) to efficiently capture parametric variations, while integrating Gaussian process surrogates and hypervolume-based acquisition to minimize expensive function evaluations. We demonstrate PPSL-MOBO's effectiveness on two challenging applications: multi-objective optimization with shared components, where certain design variables must be identical across solution families due to modular constraints, and dynamic multi-objective optimization, where objectives evolve over time. Unlike existing methods that cannot directly solve PMO problems in a unified manner, PPSL-MOBO learns a single model that generalizes across the entire parameter space. By enabling instant inference of Pareto sets for new parameter values without retraining, PPSL-BO provides an efficient solution for expensive PMO problems.

The discovery of symbolic solutions—mathematical expressions, logical rules, and algorithmic structures—is fundamental to advancing scientific and engineering progress. However, traditional methods often struggle with search efficiency and fail to integrate knowledge effectively. While recent large language model-based (LLM-based) approaches have demonstrated improvements in search efficiency, they lack the ability to continually refine and expand upon discovered solutions and their underlying knowledge, limiting their potential for \textit{open-ended innovation}. To address these limitations, we introduce CoEvo, a novel framework that leverages large language models within an evolutionary search methodology to continually generate and refine symbolic solutions. CoEvo integrates a dynamic knowledge library, enabling open-ended innovation of solutions through effective knowledge management. Additionally, CoEvo leverages multiple representations of solutions—including natural language, mathematical expressions, and code—to further enhance search efficiency. By combining the reasoning capabilities of LLMs with the exploratory power of evolutionary algorithms, CoEvo significantly improves the efficiency and scope of symbolic discovery. Our experimental results demonstrate that this method not only enhances the efficiency of searching for symbolic solutions but also supports the ongoing discovery process, akin to human scientific endeavors. This study represents a first effort in conceptualizing the search for symbolic solutions as a lifelong, iterative process, marking a significant step towards harnessing LLMs in the perpetual pursuit of scientific and engineering breakthroughs.

Automated Heuristic Design (AHD) using Large Language Models (LLMs) has achieved notable success in the past two years. Despite the effectiveness of existing approaches, they only design a single heuristic to serve all problem instances, often inducing poor generalization across different distributions or sizes. To address this issue, we propose Automated Heuristic Set Design (AHSD), a new methodology for LLM-driven AHD. The aim of AHSD is to automatically design a small-sized complementary heuristic set to serve diverse problem instances, such that each problem instance could be optimized by at least one heuristic in this set. We propose Evolution of Heuristic Set (EoH-S), which realizes AHSD using an evolutionary search framework. It incorporates a complementary population management and a memetic search to design a set of heuristics. Extensive experiments on online bin packing, traveling salesman problem, and capacitated vehicle routing problem show that EoH-S consistently outperforms existing AHD methods. The resulting heuristics exhibit complementary performance across instances of varying sizes and distributions.

In multi-objective decision-making with hierarchical preferences, lexicographic bandits provide a natural framework for optimizing multiple objectives in a prioritized order. In this setting, a learner repeatedly selects arms and observes reward vectors, aiming to maximize the reward for the highest-priority objective, then the next, and so on. While previous studies have primarily focused on regret minimization, this work bridges the gap between regret minimization and best arm identification under lexicographic preferences. We propose two elimination-based algorithms to address this joint objective. The first algorithm eliminates suboptimal arms sequentially, layer by layer, in accordance with the objective priorities, and achieves sample complexity and regret bounds comparable to those of the best single-objective algorithms. The second algorithm simultaneously leverages reward information from all objectives in each round, effectively exploiting cross-objective dependencies. Remarkably, it outperforms the known lower bound for the single-objective bandit problem, highlighting the benefit of cross-objective information sharing in the multi-objective setting. Empirical results further validate their superior performance over baselines.

Detecting and identifying complex association patterns between two variables is a fundamental task. This requires association measures that satisfy both generality (the ability to capture a wide range of association structures) and equitability (the absence of bias toward specific association types). Designing such measures is challenging due to the distributional uncertainty, structural diversity, and mixture of association types found in large datasets. Granular computing offers a promising direction, as local neighborhood structures naturally encode multi-scale association information. Inspired by this insight, we introduce the maximal neighborhood coefficient (MNC), an association measure based on $k$k-NN granulation. MNC captures a broad range of associations without empirical bias while retaining local structural details often missed by existing measures. Extending this idea, we develop a family of maximal neighborhood nonparametric exploration (MNNE) statistics that supply richer auxiliary information for characterizing associations. Together, MNC and MNNE form a data-driven exploration toolkit that offers strong empirical performance and a new perspective on mining complex association patterns.

Disagreement optimization is an emerging research issue in social networks. Although leaders are often selected to shape the opinions of followers, little effort has been made to investigate how to optimize the disagreement between them. This paper aims to address this issue by proposing and solving the following subset selection problem called leader-follower disagreement minimization (LFDMP): given a social network with n vertices and m edges, how to select k (kn) vertices as leaders such that the disagreement between leaders and followers is minimized. We show that the objective function of LFDMP is monotone and supermodular, and the state-of-the-art algorithm called Pareto optimization for subset selection (POSS) can solve this problem with (1-1/e) approximation in O(k2n4) expected time. To address the computational challenge faced by POSS while maintaining its theoretical advantage, we further develop a fast algorithm called Pareto optimization for leader selection (POLS) within its framework. We demonstrate that POLS can solve LFDMP with -related approximation in O(k2mn) expected time, where is an error parameter. Extensive experiments on various real-world social networks illustrate both the effectiveness and efficiency of POLS.

Evolutionary algorithms have been proven effective in solving complex optimization problems. This paper proposes a production shape optimization framework, and a data-driven and decomposition-based multiobjective multitask evolutionary algorithm with multiple neighbor structures and knowledge types, called MTEA/D-MNK, for complex shape optimization problems. Initially, a 3D point cloud autoencoder is trained via unsupervised learning to extract key design variables across tasks. Subsequently, each task is decomposed into a series of single-objective subproblems using weight vectors. We constructed diverse neighbors and knowledge types for each subproblem to fully exploit beneficial information in both the objective and decision spaces, accelerating the optimization process. Additionally, we proposed an adaptive parameter adjustment strategy to dynamically manage the type and amount of transferred knowledge during different evolutionary stages. The proposed MTEA/D-MNK effectively addresses the critical issues in knowledge transfer: which knowledge to transfer, how to transfer it, and how much to transfer. Finally, we comprehensively test MTEA/D-MNK on nineteen multiobjective multitask optimization (MO-MTO) benchmark instances and apply it to a practical automotive topology shape design problem, using computer simulations to optimize wind resistance coefficients and volumes of both sedan and SUV simultaneously. Experimental results demonstrate that the proposed algorithm significantly outperforms the other five state-of-the-art algorithms, chieving the best performance metrics on 18 of 20 CEC2017 benchmark instances, all 20 CEC2019 instances, and one case study of automotive shape design, as well as the highest rank in the Friedman rank test.

Most of the current expensive multiobjective optimization (MOO) algorithms focus on identifying Pareto optimal solutions. However, in some applications such as multiobjective modular design, decision-makers often prefer a set of optimal solutions that share common components in the decision space, which may conflict with Pareto optimality. Existing expensive MOO algorithms are not specifically designed to address this preference. To bridge this gap, we propose modeling the component-sharing preference in MOO as a special bi-level multiobjective optimization problem. Specifically, the upper-level is a single-objective optimization problem that seeks the optimal shared variables, while the lower-level is a multiobjective optimization problem aimed at identifying trade-off solutions for given shared variable values. Moreover, the lower-level objective is expensive-to-evaluate and can only be evaluated for a limited number of times. To efficiently solve this problem, we introduce a data-efficient algorithm called Bayesian Bi-level Search (BBS). The effectiveness of BBS is validated through six new benchmark problems and a real-world application involving the planform shape design of Blended-Wing-Body underwater glider. The results show that our method effectively identifies solutions with shared components within limited computational budgets.

Localized feature selection (LFS) methods divide the whole sample space to determine region-specific subsets for classification which outperform traditional feature selection with a global feature subset for the entire sample space. However, existing LFS algorithms decompose the local regions by impurity level of samples, which can misplace critical samples and impair feature selection results. To tackle this issue, this paper proposes a novel Fuzzy Localized Feature Selection (Fuzzy-LFS) algorithm, which divides local regions around each sample based on Gaussian fuzzy membership to enhance the coherence of region-specific information. Besides, to handle data fuzziness and uncertainty, Fuzzy-LFS establishes a Local Neighborhood Rough Set Model with forward greedy optimization to search the feature subsets. A novel local classifier is subsequently developed, overcoming the limitations of global classifiers unsuited for LFS while mitigating the excessive dependency on impurity level in traditional local classifiers. Specifically, for high-dimensional datasets, we introduce a Localized Feature Relevance Pre-Selection strategy, assigning sample-specific feature subsets according to local relevance to assist in dividing local regions and enhance classification performance. Through comprehensive experiments on 11 low-dimensional and 13 high-dimensional datasets, Fuzzy-LFS achieves superior classification accuracy to state-of-the-art LFS methods, demonstrating its effectiveness.

In modern intelligent transportation systems (ITS), particularly in freight transportation and logistics, real-time route planning is crucial. It presents unique challenges driven by high uncertainty in service requests, where the number of service customers can vary drastically, ranging from hundreds to thousands. Existing neural methods struggle to maintain performance under such significant variations, which severely limits their practical applicability. To address this crucial shortcoming, this work proposes a novel Instance-Conditioned Adaptation Model (ICAM) designed for better large-scale generalization. In particular, we design a simple yet efficient instance-conditioned adaptation function that adjusts the policy based on the specific geometry and density of the current traffic scenario to improve model adaptability with minimal computational overhead. Furthermore, we propose a powerful yet low-complexity instance-conditioned adaptation module to generate better solutions for instances across various scales. Extensive experiments on synthetic, benchmark, and real-world instances demonstrate that ICAM can consistently achieve promising generalization performance across four widely studied large-scale route planning scenarios. Notably, our proposed method delivers high-quality solutions with remarkably fast inference speed, providing a scalable and efficient solution for real-time intelligent transportation operations. Our code is available at <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://github.com/CIAM-Group/ICAM</uri>

This article focuses on indoor antenna layout optimization, aiming to minimize the number of antennas while maximizing the network coverage rate by optimizing the number and locations of antennas. This optimization problem exhibits three key characteristics: 1)Expensive evaluation:Indoor scenarios often require expensive propagation models to evaluate the network coverage rate; 2)Permutation invariance:Rearranging antenna locations does not change the network coverage rate; and 3)Variable dimension:The variable number of antennas leads to variable-dimensional solutions. Although surrogate models can be adopted for existing data-driven evolutionary algorithms to replace expensive propagation models, thereby reducing evaluation costs, they overlook permutation invariance and struggle to handle variable-dimensional solutions. To this end, this article proposes a novel$d$ata-driven$e$volutionary algorithm for indoor$a$ntenna$l$ayout optimization, called DEAL. Since the indoor antenna layout consists of a set of antenna locations, DEAL leverages a neural network that operates on sets as a surrogate model. For this surrogate model, the inherent invariance of set elements to permutations is leveraged, enabling DEAL to effectively achieve permutation invariance. Furthermore, due to the variable number of set elements, DEAL can adapt to variable-dimensional solutions. DEAL also incorporates a clustering-based strategy to generate initial antenna layouts and a local search method to further improve the performance of promising solutions. Extensive experiments on eight test scenarios demonstrate that DEAL outperforms five other algorithms in terms of the network coverage rate.

Fast simulation of elastic bodies is fundamental to computer graphics, yet current leading methods have a key limitation: they require fixed mesh connectivity. Existing methods leverage this assumption to achieve high performance but fail during topological changes such as cutting, fracturing, or merging. We present CAN, a novel optimizer that fundamentally decouples simulation acceleration from mesh topology. CAN introduces two Hessian-free, curvature-aware components: a Curvature-Aware Momentum (CAM) scheme that prevents overshooting by adaptively decaying momentum based on local gradient variations, and a Curvature-Aware Line Search (CALS) that provides high-quality step sizes via efficient directional curvature approximations. Since CAN relies solely on per-vertex, historical information, it is inherently parallel and topology-agnostic. We demonstrate that CAN achieves superior convergence compared to prior works across a wide range of dynamic-topology scenarios without any precomputation tied to connectivity, establishing a new paradigm for robust and efficient physics-based animation.

Fluid antenna is a new reconfigurable antenna technology that can dynamically adjust the positions or ports of radiating elements and therefore provides a new degree of freedom for wireless communications. However, the associated port selection is a challenging large-scale combinatorial optimization problem and difficult to solve. Existing manually designed heuristic algorithms are not only labor-intensive, but cannot achieve satisfactory performance. In this paper, we propose a novel paradigm that leverages large language models (LLMs) for automated design of optimization algorithms for fluid antenna systems without manual hyperheuristic tuning. Specifically, we study the problem of maximizing the minimum signal-to-interference-plus-noise ratio (SINR) in the downlink to ensure fairness among users by optimizing port selection and beamforming. We investigate two LLM-enabled algorithm optimization strategies. The first is to optimize the crossover and mutation operations to enhance the performance of the well-known genetic algorithm and the second is to design AutoPort, a new heuristic from scratch by LLM, to solve the optimization problem. Simulation results verify that the proposed method can achieve near-optimal performance and significant improvement over the conventional genetic algorithm and the deep learning approach.

This paper studies lexicographic online learning within the framework of multiobjective stochastic linear bandits (MOSLB), where the agent aims to simultaneously maximize multiple objectives in a hierarchical manner. Previous literature has investigated lexicographic online learning in multiobjective multi-armed bandits, a special case of MOSLB. They provided a suboptimal algorithm whose regret bound is approximately O(T^(2/3)) based on a priority-based regret metric. In this paper, we propose an algorithm for lexicographic online learning in the MOSLB model, achieving an almost optimal regret bound of approximately O(dT^(1/2)) when evaluated by the general regret metric. Here, d is the dimension of arm vectors, and T is the time horizon. Our method introduces a new arm filter and a multiple trade-offs approach to effectively balance exploration and exploitation across different objectives. Experiments confirm the merits of our algorithms and provide compelling evidence to support our analysis.

Multi-objective Bayesian optimization (MOBO) aims to optimize multiple competing objective functions in the expensive-to-evaluate scenario. The Expected Hypervolume Improvement (EHVI) is a commonly used acquisition function for MOBO and shows a good performance. However, the computation of EHVI becomes challenging as the number of objective functions grows. In this paper, we revisit the formulation of EHVI, as well as its multi-point counterpart qEHVI, and derive much simpler analytic expressions for them. The main contributions of this paper include: (1) first formulating EHVI as a particular hypervolume improvement, and thus immediately obtaining a formal proof of its NP-hardness, faster algorithms in both theory and practice, and more results on its derivatives; (2) first obtaining the analytic expressions of qEHVI for any q > 1 and m ≥ 2 where m is the number of objectives; and (3) demonstrating the advantages of our formulation over existing exact and approximation methods for computing EHVI and qEHVI through a large number of numerical experiments.

Continual learning aims to learn multiple tasks sequentially. A key challenge in continual learning is balancing between two objectives: retaining knowledge from old tasks (stability) and adapting to new tasks (plasticity). Experience replay methods, which store and replay past data alongside new data, have become a widely adopted approach to mitigate catastrophic forgetting. However, these methods neglect the dynamic nature of the stability-plasticity trade-off and aim to find a fixed and unchanging balance, resulting in suboptimal adaptation during training and inference. In this paper, we propose Pareto Continual Learning (ParetoCL), a novel framework that reformulates the stability-plasticity trade-off in continual learning as a multi-objective optimization (MOO) problem. ParetoCL introduces a preference-conditioned model to efficiently learn a set of Pareto optimal solutions representing different trade-offs and enables dynamic adaptation during inference. From a generalization perspective, ParetoCL can be seen as an objective augmentation approach that learns from different objective combinations of stability and plasticity. Extensive experiments across multiple datasets and settings demonstrate that ParetoCL outperforms state-of-the-art methods and adapts to diverse continual learning scenarios.

Recent advancements in Neural Combinatorial Optimization (NCO) have shown promise in solving routing problems like the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) without handcrafted designs. Research in this domain has explored two primary categories of methods: iterative and non-iterative. While non-iterative methods struggle to generate near-optimal solutions directly, iterative methods simplify the task by learning local search steps. However, existing iterative methods are often limited by restricted neighborhood searches, leading to suboptimal results. To address this limitation, we propose a novel approach that extends the search to larger neighborhoods by learning a destroy-and-repair strategy. Specifically, we introduce a Destroy-and-Repair framework based on Hyper-Graphs (DRHG). This framework reduces consecutive intact edges to hyper-edges, allowing the model to pay more attention to the destroyed part and decrease the complexity of encoding all nodes. Experiments demonstrate that DRHG achieves state-of-the-art performance on TSP with up to 10,000 nodes and shows strong generalization to real-world TSPLib and CVRPLib problems.

Heuristics are commonly used to tackle various search and optimization problems. Design heuristics usually require tedious manual crafting with domain knowledge. Recent works have incorporated Large Language Models (LLMs) into automatic heuristic search, leveraging their powerful language and coding capacity. However, existing research focuses on the optimal performance on the target problem as the sole objective, neglecting other criteria such as efficiency and scalability, which are vital in practice. To tackle this challenge, we propose to model the heuristic search as a multi-objective optimization problem and consider introducing additional practical criteria beyond optimal performance. Due to the complexity of the search space, conventional multi-objective optimization methods struggle to effectively handle LLM-based multi-objective heuristic search. We propose the first LLM-based multi-objective heuristic search framework, Multi-objective Evolution of Heuristic (MEoH), which integrates LLMs in a zero-shot manner to generate a non-dominated set of heuristics to meet multiple design criteria. We design a new dominance-dissimilarity mechanism for effective population management and selection, which incorporates both code dissimilarity in the search space and dominance in the objective space. MEoH is demonstrated in two well-known combinatorial optimization problems: the online Bin Packing Problem (BPP) and the Traveling Salesman Problem (TSP). The results indicate that a variety of elite heuristics are automatically generated in a single run, offering more trade-off options than the existing methods. It successfully achieves competitive or superior performance while improving efficiency up to 10 times. Moreover, we also observe that the multi-objective search introduces novel insights into heuristic design and leads to the discovery of diverse heuristics.

As the initial phase of evolutionary multi-objective optimization (EMO), population initialization is always essential for subsequent evolutionary processes aimed at solving multi-objective optimization problems. While random initialization (i.e., random sampling) remains the most frequently used initialization method in EMO algorithms, many studies have indicated that the utilization of alternative initialization methods instead of random initialization can significantly improve the performance of the original EMO algorithms. Some studies have also investigated the effects of different initialization techniques or parameters (e.g., methods and population size). However, there is a scarcity of recent reviews focusing on population initialization for EMO algorithms. To bridge this research gap in the EMO research community, this paper provides a short review on this crucial topic. Specifically, the current choice of initialization methods is briefly summarized by using some representative EMO algorithms. The effects of population initialization and new initialization method design are then extensively reviewed. Insights into population initialization are also provided. This study aims to provide a comprehensive understanding of population initialization for newcomers to the EMO community.

Handcrafting heuristics often demands extensive domain knowledge and significant development effort. Recently, heuristic search powered by large language models (LLMs) has emerged as a new approach, offering enhanced automation and promising performance. Existing methods rely on an evolutionary computation (EC) framework with carefully designed prompt strategies. However, the large heuristic search space poses significant challenges for these EC-based methods. This paper proposes a simple yet effective LLM-driven Heuristic Neighborhood Search (LHNS) paradigm to iteratively search in the heuristic neighborhood in a principled way for efficient heuristic design. Three distinct methods are designed under this neighborhood search paradigm and demonstrated on three widely studied problems. Results indicate that LHNS exhibits very competitive performance and surpasses existing EC-based methods in efficiency. It also demonstrates sufficient robustness in the absence of problem-specific knowledge regarding the target problem. The efficiency and robust adaptability make it a practical new solution for efficient heuristic design.

Crafting adversarial examples is crucial for evaluating and enhancing the robustness of Deep Neural Networks (DNNs), presenting a challenge equivalent to maximizing a non-differentiable 0-1 loss function. However, existing single objective methods, namely adversarial attacks focus on a surrogate loss function, do not fully harness the benefits of engaging multiple loss functions, as a result of insufficient understanding of their synergistic and conflicting nature. To overcome these limitations, we propose the Multi-Objective Set-Based Attack (MOS Attack), a novel adversarial attack framework leveraging multiple loss functions and automatically uncovering their interrelations. The MOS Attack adopts a set-based multi-objective optimization strategy, enabling the incorporation of numerous loss functions without additional parameters. It also automatically mines synergistic patterns among various losses, facilitating the generation of potent adversarial attacks with fewer objectives. Extensive experiments have shown that our MOS Attack outperforms single-objective attacks. Furthermore, by harnessing the identified synergistic patterns, MOS Attack continues to show superior results with a reduced number of loss functions. Our code is available at https://github.com/pgg3/MOS-Attack.

Recently, performance comparison results of evolutionary multi-objective optimization (EMO) algorithms have been reported in many studies. However, EMO algorithms have not been compared with mathematical programming-based methods in those studies. To demonstrate the usefulness of EMO algorithms, it is needed to clearly show their advantages over mathematical programming-based methods in solving multi-objective optimization problems since those methods are usually highly efficient and effective. In this paper, a novel improved linear programming-based relaxation method, named ILP-R, is proposed for addressing multi-objective knapsack problems (MOKP), which are used as the test problems for performance comparison. Extensive experimental results show that ILP-R outperforms a basic linear programming-based relaxation method and EMO algorithms. Nevertheless, EMO algorithms exhibit the ability to further improve the solutions generated by the ILP-R method. Furthermore, a knowledge-based mutation method is explored to demonstrate its effectiveness in further improving the performance of EMO algorithms that use the heuristic ILP-R solutions as the initial population.

Multi-objective optimization can be found in many real-world applications where some conflicting objectives can not be optimized by a single solution. Existing optimization methods often focus on finding a set of Pareto solutions with different optimal trade-offs among the objectives. However, the required number of solutions to well approximate the whole Pareto optimal set could be exponentially large with respect to the number of objectives, which makes these methods unsuitable for handling many optimization objectives. In this work, instead of finding a dense set of Pareto solutions, we propose a novel Tchebycheff set scalarization method to find a few representative solutions (e.g., 5) to cover a large number of objectives (e.g., $>100$) in a collaborative and complementary manner. In this way, each objective can be well addressed by at least one solution in the small solution set. In addition, we further develop a smooth Tchebycheff set scalarization approach for efficient optimization with good theoretical guarantees. Experimental studies on different problems with many optimization objectives demonstrate the effectiveness of our proposed method.

Neural Combinatorial Optimization (NCO) methods have exhibited promising performance in solving Vehicle Routing Problems (VRPs). However, most NCO methods rely on the conventional self-attention mechanism that induces excessive computational complexity, thereby struggling to contend with large-scale VRPs and hindering their practical applicability. In this paper, we propose a lightweight cross-attention mechanism with linear complexity, by which a Transformer network is developed to learn efficient and favorable solutions for large-scale VRPs. We also propose a Self-Improved Training (SIT) algorithm that enables direct model training on large-scale VRP instances, bypassing extensive computational overhead for attaining labels. By iterating solution reconstruction, the Transformer network itself can generate improved partial solutions as pseudo-labels to guide the model training. Experimental results on the Travelling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP) with up to 100K nodes indicate that our method consistently achieves superior performance for synthetic and real-world benchmarks, significantly boosting the scalability of NCO methods.

Reinforcement Learning (RL) with linear transition kernels and reward functions has recently attracted growing attention due to its computational efficiency and theoretical advancements. However, prior theoretical research in RL has primarily focused on single-objective problems, resulting in limited theoretical development for multi-objective reinforcement learning (MORL). To bridge this gap, we examine MORL under lexicographic reward structures, where rewards comprise $m$ hierarchically ordered objectives. In this framework, the agent the agent maximizes objectives sequentially, prioritizing the highest-priority objective before considering subsequent ones. We introduce the first MORL algorithm with provable regret guarantees. For any objective $i \in \\{1, 2, \ldots, m\\}$, our algorithm achieves a regret bound of $\widetilde{O}(\Lambda^i(\lambda) \cdot \sqrt{d^2H^4 K})$, where $\Lambda^i(\lambda) = 1 + \lambda + \cdots + \lambda^{i-1}$, $\lambda$ quantifies the trade-off between conflicting objectives, $d$ is the feature dimension, $H$ is the episode length, and $K$ is the number of episodes. Furthermore, our algorithm can be applied in the misspecified setting, where the regret bound for the $i$-th objective becomes $\widetilde{O}(\Lambda^i(\lambda)\cdot(\sqrt{d^2H^4K}+\epsilon dH^2K))$, with $\epsilon$ denoting the degree of misspecification.

Long-tailed distribution datasets are prevalent in many machine learning tasks, yet existing neural network models still face significant challenges when handling such data. This paper proposes a novel adaptive pruning strategy, LTAP (Long-Tailed Adaptive Pruner), aimed at balancing model efficiency and performance to better address the challenges posed by long-tailed data distributions. LTAP introduces multi-dimensional importance scoring criteria and designs a dynamic weight adjustment mechanism to adaptively determine the pruning priority of parameters for different classes. By focusing on protecting parameters critical for tail classes, LTAP significantly enhances computational efficiency while maintaining model performance. This method combines the strengths of long-tailed learning and neural network pruning, overcoming the limitations of existing approaches in handling imbalanced data. Extensive experiments demonstrate that LTAP outperforms existing methods on various long-tailed datasets, achieving a good balance between model compression rate, computational efficiency, and classification accuracy. This research provides new insights into solving model optimization problems in long-tailed learning and is significant for improving the performance of neural networks on imbalanced datasets. The code is available at https://github.com/DataLab-atom/LT-VOTE.

In-context learning (ICL) has garnered significant attention for its ability to grasp functions/tasks from demonstrations. Recent studies suggest the presence of a latent task/function vector in LLMs during ICL. Merullo et al. (2024) showed that LLMs leverage this vector alongside the residual stream for Word2Vec-like vector arithmetic, solving factual-recall ICL tasks. Additionally, recent work empirically highlighted the key role of Question-Answer data in enhancing factual-recall capabilities. Despite these insights, a theoretical explanation remains elusive. To move one step forward, we propose a theoretical framework building on empirically grounded hierarchical concept modeling. We develop an optimization theory, showing how nonlinear residual transformers trained via gradient descent on cross-entropy loss perform factual-recall ICL tasks via vector arithmetic. We prove 0-1 loss convergence and show the strong generalization, including robustness to concept recombination and distribution shifts. These results elucidate the advantages of transformers over static embedding predecessors. Empirical simulations corroborate our theoretical insights.

Distribution matching is a key technique in machine learning, with applications in generative models, domain adaptation, and algorithmic fairness. A related but less explored challenge is generating a distribution that aligns with multiple underlying distributions, often with conflicting objectives, known as a Pareto optimal distribution. In this paper, we develop a general theory based on information geometry to construct the Pareto set and front for the entire exponential family under KL and inverse KL divergences. This formulation allows explicit derivation of the Pareto set and front for multivariate normal distributions, enabling applications like multiobjective variational autoencoders (MOVAEs) to generate interpolated image distributions. Experimental results on real-world images demonstrate that both algorithms can generate high-quality interpolated images across multiple distributions.

Multi-objective multi-armed bandit (MOMAB) problems are crucial for complex decision-making scenarios where multiple conflicting objectives must be simultaneously optimized. However, most existing works are based on the linear assumption of the feedback rewards, which significantly constrains their applicability and efficacy in capturing the intricate dynamics of real-world environments. This paper explores a multi-objective neural bandit (MONB) framework, which integrates the universal approximators, neural networks, with the classical MOMABs. We adopt random scalarization to accommodate the special needs of a practitioner by setting an appropriate distribution on the regions of interest. Using the trade-off capabilities of upper confidence bound (UCB) and Thompson sampling (TS) strategies, we propose two novel algorithms, MONeural-UCB and MONeural-TS. Theoretical and empirical analysis demonstrate the superiority of our methods in multi-objective or multi-task bandit problems, which makes great improvement over the classical linear MOMABs.

This paper studies lexicographic multi-armed bandits (MAB), where after selecting an arm, the agent observes a reward vector including multiple objectives, each with a different level of importance. Although previous literature has proposed the algorithm for lexicographic MAB, their algorithm suffers from several limitations: (1) it exhibits poor adversarial robustness due to its reliance on stochastic rewards, (2) its regret bound is suboptimal compared to single-objective counterparts, and (3) the regret bound does not adapt to specific problem instances. To address these limitations, we study lexicographic MAB with adversarial corruptions, where an adversary might corrupt the stochastic rewards with a corruption budget of C. First, when the value of C is known, we propose an algorithm achieving a problem-dependent regret bound of O(∑(log T / Δⁱ(a) + C)) for the i-th objective (i ∈ [M]), where Δⁱ(a) is the reward gap for arm a on the i-th objective, and M is the number of objectives. In the purely stochastic setting (C=0), this regret bound approaches optimality. Second, we introduce another algorithm that does not require value of C but incurs a less favorable regret bound of O(∑(γ_T / Δⁱ(a) + γ_T)) for the i-th objective, where γ_T = O((log T)² + KC(log T)²). Finally, we conduct experiments on both synthetic and real-world datasets to verify the effectiveness of our algorithms.

Causal structure learning (CSL) plays a pivotal role in causality and is often formulated as an optimization problem within score-and-search methods. Under the assumption of an infinite dataset and a predefined distribution, several well-established and consistent score functions have been shown to be both optimal and reliable for identifying ground-truth causal graphs. However, in practice, these idealized assumptions are often infeasible, which can result in CSL algorithms learning suboptimal structures. In this paper, we introduce L-SFE, a framework designed to automatically discover effective score functions by exploring the "score function space". L-SFE addresses this task from a bi-level optimization perspective. First, it leverages a Large Language Model (LLM) to interpret the characteristics of score functions and generate the corresponding code implementations. Next, L-SFE employs evolutionary algorithms along with carefully designed operators, to search for solutions with higher fitness. Additionally, we take the BIC as example and prove the consistency of the generated score functions. Experimental evaluations, conducted on discrete, continuous, and real datasets, demonstrate the high stability, generality and effectiveness of L-SFE.

In evolutionary multi-objective optimization (EMO), reproducing high-quality offspring solutions is a key factor in developing effective EMO algorithms (EMOAs). Many model-based methods have been proposed to generate high-quality offspring solutions. Almost all studies use the solutions in the current and previous generations as the training data. When using existing solutions as training data, the neural network is effective at identifying promising improvement directions for poor solutions. However, it does not perform well in determining effective improvement directions for solutions that are already good. In this paper, we propose a novel method that uses momentum moves to generate new solutions and includes the good new solutions in the training dataset. The momentum method offers a novel approach to enhancing the quality of the current solutions without incurring any additional computation costs. Our approach is demonstrated on both artificial and real-world problems, and compared with the algorithm using the traditional training dataset. Results show that including the momentum-based new solutions in the training dataset significantly improves the computational efficiency of the algorithm.

Combinatorial optimization (CO) is fundamental to several realworld applications, from logistics and scheduling to hardware design and resource allocation.Deep reinforcement learning (RL) has recently shown significant benefits in solving CO problems, reducing reliance on domain expertise and improving computational efficiency.However, the absence of a unified benchmarking framework leads to inconsistent evaluations, limits reproducibility, and increases engineering overhead, raising barriers to adoption for new researchers.To address these challenges, we introduce RL4CO, a unified and extensive benchmark with in-depth library coverage of 27 CO problem environments and 23 state-of-the-art baselines.Built on efficient software libraries and best practices in implementation, RL4CO features modularized implementation and flexible configurations of diverse environments, policy architectures, RL algorithms, and utilities with extensive documentation.RL4CO helps researchers build on existing successes while exploring and developing their own designs, facilitating the entire research process by decoupling science from heavy engineering.We finally provide extensive benchmark studies to inspire new insights and future work.RL4CO has already attracted numerous researchers in the community and is open-sourced at https://github.com/ai4co/rl4co 1 .

Large language model-assisted Evolutionary Search (LES) has emerged as a promising approach for Automated Algorithm Discovery (AAD). While many evolutionary search strategies have been developed for classic optimization problems, LES operates in abstract language spaces, presenting unique challenges for applying these strategies effectively. To address this, we propose a general LES framework that incorporates feature-assisted niche construction within abstract search spaces, enabling the seamless integration of niche-based search strategies from evolutionary computation. Building on this framework, we introduce PartEvo, an LES method that combines niche collaborative search and advanced prompting strategies to improve algorithm discovery efficiency. Experiments on both synthetic and real-world optimization problems show that PartEvo outperforms human-designed baselines and surpasses prior LES methods, such as Eoh and Funsearch. In particular, on resource scheduling tasks, PartEvo generates meta-heuristics with low design costs, achieving up to 90.1\% performance improvement over widely-used baseline algorithms, highlighting its potential for real-world applications.

Online Continual Learning (OCL) requires models to learn sequentially from data streams with limited memory. Rehearsal-based methods, particularly Experience Replay (ER), are commonly used in OCL scenarios. This paper revisits ER through the lens of $\epsilon$-constraint optimization, revealing that ER implicitly employs a soft constraint on past task performance, with its weighting parameter post-hoc defining a slack variable. While effective, ER's implicit and fixed slack strategy has limitations: it can inadvertently lead to updates that negatively impact generalization, and its fixed trade-off between plasticity and stability may not optimally balance current streaming with memory retention, potentially overfitting to the memory buffer. To address these shortcomings, we propose the \textbf{G}radient-Guided \textbf{E}psilon \textbf{C}onstraint (\textbf{GEC}) method for online continual learning. GEC explicitly formulates the OCL update as an $\epsilon$-constraint optimization problem, which minimize the loss on the current task data and transform the stability objective as constraints and propose a gradient-guided method to dynamically adjusts the update direction based on whether the performance on memory samples violates a predefined slack tolerance $\bar{\varepsilon}$: if forgetting exceeds this tolerance, GEC prioritizes constraint satisfaction; otherwise, it focuses on the current task while controlling the rate of increase in memory loss. Empirical evaluations on standard OCL benchmarks demonstrate GEC's ability to achieve a superior trade-off, leading to improved overall performance. Code is available at https://github.com/laisong-22004009/GEC_OCL.

Multi-objective optimization problems (MOPs) are prevalent in numerous real-world applications. Recently, Pareto Set Learning (PSL) has emerged as a powerful paradigm for solving MOPs. PSL can produce a neural network for modeling the set of all Pareto optimal solutions. However, applying PSL to black-box objectives, particularly those exhibiting non-separability, high dimensionality, and/or other complex properties, remains very challenging. To address this issue, we propose leveraging evolution strategies (ESs), a class of specialized black-box optimization algorithms, within the PSL paradigm. Traditional ESs capture the complex dimensional dependencies less efficiently, which can significantly hinder their performance in PSL. To tackle this issue, we suggest encapsulating the dependencies within a neural network, which is then trained using a novel gradient estimation method. The proposed method, termed Neural-ES, is evaluated using a bespoke benchmark suite for black-box PSL. Experimental comparisons with other methods demonstrate the efficiency of Neural-ES, underscoring its ability to learn the Pareto sets of challenging black-box MOPs.

Neural Combinatorial Optimisation (NCO) is a promising learning-based approach for solving Vehicle Routing Problems (VRPs) without extensive manual design. While existing constructive NCO methods typically follow an appending-based paradigm that sequentially adds unvisited nodes to partial solutions, this rigid approach often leads to suboptimal results. To overcome this limitation, we explore the idea of the insertion-based paradigm and propose Learning to Construct with Insertion-based Paradigm (L2C-Insert), a novel learning-based method for constructive NCO. Unlike traditional approaches, L2C-Insert builds solutions by strategically inserting unvisited nodes at any valid position in the current partial solution, which can significantly enhance the flexibility and solution quality. The proposed framework introduces three key components: a novel model architecture for precise insertion position prediction, an efficient training scheme for model optimization, and an advanced inference technique that fully exploits the insertion paradigm's flexibility. Extensive experiments on both synthetic and real-world instances of the Travelling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that L2C-Insert consistently achieves superior performance across various problem sizes. The code is available at [https://github.com/CIAM-Group/L2C\_Insert](https://github.com/CIAM-Group/L2C\_Insert).

Optimizing Register Transfer Level (RTL) code is crucial for improving the efficiency and performance of digital circuits in the early stages of synthesis. Manual rewriting, guided by synthesis feedback, can yield high-quality results but is time-consuming and error-prone. Most existing compiler-based approaches have difficulty handling complex design constraints. Large Language Model (LLM)-based methods have emerged as a promising alternative to address these challenges. However, LLM-based approaches often face difficulties in ensuring alignment between the generated code and the provided prompts. This paper introduces SymRTLO, a neuron-symbolic framework that integrates LLMs with symbolic reasoning for the efficient and effective optimization of RTL code. Our method incorporates a retrieval-augmented system of optimization rules and Abstract Syntax Tree (AST)-based templates, enabling LLM-based rewriting that maintains syntactic correctness while minimizing undesired circuit behaviors. A symbolic module is proposed for analyzing and optimizing finite state machine (FSM) logic, allowing fine-grained state merging and partial specification handling beyond the scope of pattern-based compilers. Furthermore, a fast verification pipeline, combining formal equivalence checks with test-driven validation, further reduces the complexity of verification. Experiments on the RTL-Rewriter benchmark with Synopsys Design Compiler and Yosys show that SymRTLO improves power, performance, and area (PPA) by up to 43.9%, 62.5%, and 51.1%, respectively, compared to the state-of-the-art methods. We will release the code as open source upon the paper's acceptance.

Long-Tailed Recognition (LTR) presents a significant challenge due to extreme class imbalance, where existing methods often struggle to balance performance across head and tail classes. Directly applying multi-objective optimization (MOO) to leverage multiple LTR strategies can be complex and unstable. To address this, we propose TS-MOF (Two-Stage Multi-Objective Fine-tuning), a novel framework that strategically decouples feature learning from classifier adaptation. After standard pre-training, TS-MOF freezes the feature backbone and focuses on an efficient multi-objective fine-tuning of specialized classifier heads. The core of TS-MOF's second stage lies in two innovations: Refined Performance Level Agreement for adaptive task weighting based on real-time per-class performance, and Robust Deterministic Projective Conflict Gradient for stable gradient conflict resolution and constructive fusion. This approach enables effective synergy between diverse LTR strategies, leading to significant and balanced performance improvements. Extensive experiments on CIFAR100-LT, ImageNet-LT, and iNaturalist 2018 demonstrate that TS-MOF achieves state-of-the-art results, particularly enhancing tail class accuracy (e.g., +3.3\% on CIFAR100-LT IR=100 tail) while improving head class performance, all within a remarkably short fine-tuning period of 20 epochs.

Scientific discovery across diverse fields increasingly grapples with datasets exhibiting pathological long-tailed distributions: a few common phenomena overshadow a multitude of rare yet scientifically critical instances. Unlike standard benchmarks, these scientific datasets often feature extreme imbalance coupled with a modest number of classes and limited overall sample volume, rendering existing long-tailed recognition (LTR) techniques ineffective. Such methods, biased by majority classes or prone to overfitting on scarce tail data, frequently fail to identify the very instances—novel materials, rare disease biomarkers, faint astronomical signals—that drive scientific breakthroughs. This paper introduces a novel, end-to-end framework explicitly designed to address pathological long-tailed recognition in scientific contexts. Our approach synergizes a Balanced Supervised Contrastive Learning (B-SCL) mechanism, which enhances the representation of tail classes by dynamically re-weighting their contributions, with a Smooth Objective Regularization (SOR) strategy that manages the inherent tension between tail-class focus and overall classification performance. We introduce and analyze the real-world ZincFluor chemical dataset ($\mathcal{T}=137.54$) and synthetic benchmarks with controllable extreme imbalances (CIFAR-LT variants). Extensive evaluations demonstrate our method's superior ability to decipher these extremes. Notably, on ZincFluor, our approach achieves a Tail Top-2 accuracy of $66.84\%$, significantly outperforming existing techniques. On CIFAR-10-LT with an imbalance ratio of $1000$ ($\mathcal{T}=100$), our method achieves a tail-class accuracy of $38.99\%$, substantially leading the next best. These results underscore our framework's potential to unlock novel insights from complex, imbalanced scientific datasets, thereby accelerating discovery.

Momentum is a technique that adds the momentum moves from the earlier iterations into the current update to accelerate convergence. While the momentum technique has been widely used in single-objective optimization, its application in evolutionary multi-objective optimization (EMO) has not gained much attention. Since EMO algorithms are population-based algorithms, how to choose solutions for applying momentum becomes an important issue. Inspired by Polyak’s momentum method and Nesterov’s momentum method in single-objective optimization, we propose four different momentum methods for EMO. Our findings demonstrate that the performance of EMOAs with momentum is strongly affected by the choice of solutions to which momentum moves are applied.

A method based on deep neural network (DNN) optimized model predictive control (MPC) and standoff fusion is proposed to address the problem of tracking moving target trajectory planning for uncrewed aerial vehicle (UAV) swarms in uncertain environments. First, online UAV trajectory planning is carried out based on the optimised MPC algorithm, and the standoff algorithm is introduced to achieve formation keeping and online obstacle avoidance targets, which in turn solves the problem of high probability of tracking target loss due to the limitation of the detection range of the UAV swarm. To avoid the local saturation problem of the control method, an improved MPC model is constructed by combining anti-windup algorithms. At the same time, the integration of DNN with the improved MPC algorithm effectively addresses the large-scale, multiconstraint optimization problem of UAV swarm control. Based on an approximate optimal control strategy, a dynamic control system model is constructed, which can rapidly adapt to external disturbances and adjust the control inputs. This approach compensates for the limitations of traditional MPC, which relies on precise prior models. Simulation results show that the improved MPC fusion algorithm is more stable in formation maintenance, faster in convergence, and more effective in monitoring targets compared to the single MPC algorithm. It enables more precise control with higher robustness. This approach is more aligned with the real-world flight requirements of UAV swarms and serves as an effective pathway for applying improved MPC methods to multiagent control.

This paper studies a multiobjective bandit problem under lexicographic ordering, wherein the learner aims to maximize $m$ objectives, each with different levels of importance. First, we introduce the local trade-off, $\lambda_*$, which depicts the trade-off between different objectives. For the case when an upper bound of $\lambda_*$ is known, i.e., $\lambda\geq\lambda_*$, we develop an algorithm that achieves a general regret bound of $\widetilde{O}(\Lambda^i(\lambda)T^{(d_z^i+1)/(d_z^i+2)})$ for the $i$-th objective, where $i\in\{1,2,\ldots,m\}$, $\Lambda^i(\lambda)=1+\lambda+\cdots+\lambda^{i-1}$, $d_z^i$ is the zooming dimension for the $i$-th objective, and $T$ is the time horizon. Next, we provide a matching lower bound for the lexicographic Lipschitz bandit problem, proving that our algorithm is optimal in terms of $\lambda_*$ and $T$. Finally, for the case where $m=2$, we remove the dependence on the knowledge about $\lambda_*$, albeit at the cost of increasing the regret bound to $\widetilde{O}(\Lambda^i(\lambda_*)T^{(3d_z^i+4)/(3d_z^i+6)})$, which remains optimal in terms of $\lambda_*$. Compared to existing work on lexicographic multi-armed bandits, our approach improves the current regret bound of $\widetilde{O}(T^{2/3})$ and extends the number of arms to infinity. Numerical experiments confirm the effectiveness of our algorithms.

Logistics transportation plays a critical role in real-world applications. The heterogeneous fleet vehicle routing problem (HFVRP), characterized by varying vehicle capacities and costs, are the key optimization challenges in many logistic scenarios. Despite its importance, it presents substantial challenges due to its NP-hard nature and large scale. Existing methods only study HFVRP instances of moderate size (i.e., about 300 nodes), which is insufficient for real-world application. In this article, we introduce large language model-multipopulation (MP-LLM), a novel MP optimization method with LLM-driven knowledge discovery. MP-LLM employs multiple populations with iterated local search (ILS) and dynamic updating to balance exploration and exploitation. An LLM-driven knowledge discovery is adopted to design a parameter adjustment strategy to pinpoint features specific to each instance, thereby facilitating a more effective dynamic parameter adjustment. We comprehensively evaluate MP-LLM on four benchmark test sets with 170 instances of diverse distributions and sizes. Our results show that when compared to stat-of-the-art methods, MP-LLM not only achieves superior solution quality but also significantly enhances efficiency. Notably, MP-LLM generates new best-known solutions on 18 out of 90 classic instances. It significantly expands HFVRP-solving capabilities from approximately 300 nodes to instances with up to 3000 nodes.

In the realm of evolutionary multiobjective optimization, the hypervolume indicator serves as a crucial metric for assessing the quality of solution sets. Due to the high costs in hypervolume computation, hypervolume-based optimization algorithms always meet the challenge of finding a certain number of points in a given point set to maximize the hypervolume indicator, especially when there are many objectives. In response, the greedy decremental algorithm for hypervolume subset selection problem (gHSSD) has emerged as a noteworthy alternative. This paper introduces a general algorithm for gHSSD, applicable in any dimensionality above two. The proposed algorithm leverages a space partition tree and incorporates a once-build-multiple-use strategy, effectively reducing time complexity. We prove that the proposed algorithm has a time complexity of O((n-k+n)nd-12logn) where n is the number of points, k is the number of points to be reserved, and d the dimensionality. Theoretically, this complexity is competitive with the current best algorithms for d=3,4 and better than them for all 5≤d≤7. To validate our algorithm, we have conducted extensive tests on various random point sets and multiobjective optimization benchmarks. Experimental results suggest that our implementation is more efficient than or competitive with state-of-the-art algorithms on many instances as n increases for d=3,4.

Hypervolume subset selection (HSS) has received significant attention since it has a strong connection with evolutionary multiobjective optimization (EMO), such as environment selection and post-processing to identify representative solutions for decision-makers. The goal of HSS is to find the optimal subset that maximizes the hypervolume (HV) indicator subject to a given cardinality constraint. However, existing HSS algorithms or related methods are not efficient in achieving good performance in high-dimensional objective spaces. This is primarily because HSS problems become NP-hard when the number of objectives exceeds two, and the calculation of HV contribution (HVC) is very time-consuming. To efficiently solve HSS problems while maintaining a good solution quality, we propose a fast and scalable HSS method for many-objective optimization based on the determinantal point process (DPP), named DPP-HSS, which is fully free of HVC calculation. Specifically, DPP-HSS constructs an HV kernel matrix by extracting the convergence and diversity representations of each solution for a given HSS problem. This matrix is then used to build a DPP model. Subsequently, the original HSS problem is reformulated as a new maximization optimization problem based on the constructed model. A greedy DPP-based HSS algorithm is implemented to solve this transformed problem. Extensive experiments show that the proposed DPP-HSS achieves significant speedup and good HV performance in comparison with state-of-the-art HSS algorithms on benchmark problems. Furthermore, DPP-HSS demonstrates very good scalability with respect to the number of objectives.

In the past few decades, many multiobjective evolutionary optimization algorithms (MOEAs) have been proposed to find a finite set of approximate Pareto solutions for a given problem in a single run. However, in many real-world applications, it could be desirable to have structure constraints on the entire optimal solution set, which define the patterns shared among all solutions. The current population-based MOEAs cannot properly handle such requirements. In this work, we make a first attempt to incorporate the structure constraints into the whole solution set. Specifically, we propose to model such a multiobjective optimization problem as a set optimization problem with structure constraints. The structure constraints define some patterns that all the solutions are required to share. Such patterns can be fixed components shared by all solutions, specific relations among decision variables, and the required shape of the Pareto set. In addition, we develop a simple yet efficient evolutionary stochastic optimization method to learn the set model, which only requires a low computational budget similar to classic MOEAs. With our proposed method, the decision-makers can easily tradeoff the Pareto optimality with preferred structures, which is not supported by other MOEAs. A set of experiments on benchmark test suites and real-world application problems demonstrates that our proposed method is effective.

Maximizing the influence of opinions is an emerging research topic in social networks. Although the community is a key structure of social networks, little effort has been made to investigate how to maximize the influence of opinions on all communities. This article proposes a systematic approach to address this issue. First, we construct a multifaceted opinion evolution (MFOE) model with three critical influence factors, namely, individuals, neighbors, and communities, to describe the opinion evolution process in social networks. The convergence analysis confirms its ability to reveal the influence of opinions. Then, we define the overall community opinion to measure the influence of opinions on all communities and employ it as the objective function to formulate an optimization problem called community opinion maximization (COM). We show that the COM problem is NP-hard. To optimize this problem, a memetic algorithm with three problem-specific schemes is developed and termed MACOM. Extensive experimental studies on real-world social networks demonstrate the plausibility of the MFOE model and the effectiveness of MACOM.

Many combinatorial multiobjective optimization problems involve very costly-to-evaluate objectives and constraints. It is very difficult, if not impossible, for traditional heuristics to solve these problems with an acceptable amount of computational time. In this paper, we show that offline machine learning can be very useful to assist multiobjective evolutionary algorithms to tackle this kind of problem. We take a complicated real-life multiobjective routing-packing problem as the test bed. We propose to use offline machine learning methods to replace time-consuming packing heuristics for packing feasibility prediction. Experiments show that the machine learning models can be 1,000 times faster than some commonly used packing heuristics and their accuracy can be as high as 98%. We adopt MOEA/D to decompose the problem into a number of single objective subproblems and solve them in a collaborative manner. We propose an encoding strategy to represent each routing scheme and use genetic operators to generate new routes. Experimental studies have been conducted on 100 instances from HUAWEI’s real-world logistics application and two test suites from the literature. Our proposed method can solve each HUAWEI instance in around one minute. Our solutions on the two test suites are comparable to other existing algorithms, and the overall computational cost of our method is significantly lower than others.

With the rise of globalization and environmental concerns, distributed scheduling and energy-efficient scheduling have become crucial topics in the informational manufacturing system. Additionally, the growing consideration about realistic constraints, such as transportation time and finite transportation resources, has made the scheduling problem increasingly complex. Facing these challenges, special mechanisms are required to improve the efficiency of solving algorithms. In this paper, a bi-learning evolutionary algorithm (BLEA) is proposed to solve the distributed energy-efficient flexible job shop problem with transportation constraints (DEFJSP-T). Firstly, we integrate statistical learning (SL) and evolutionary learning (EL) in the framework, while decomposition and Pareto dominance methods are employed in different stages to handle conflicting objectives. During the SL stage, probability models are established to statistically search for advantageous substructures on each weight vector, and an update mechanism is devised to improve the exploration. In the EL stage, the genetic operators are introduced and an improved local search that takes into account the problem properties is proposed to realize sufficient exploitation. Finally, according to the performance of the SL, a novel switching mechanism between SL and EL is designed to ensure the rational allocation of computing resources. Extensive experiments are conducted to test the performances of the BLEA. The statistical comparison shows that the BLEA is superior in solving the DEFJSP-T in terms of efficiency and effectiveness.

In multiobjective optimization, the R2 indicator is widely used for designing the indicator-based algorithms, and the Tchebycheff approach is commonly employed in the decomposition-based algorithms. Despite their wide use, the connection between these two different paradigms is still not well understood, particularly in the field of multiobjective efficient global optimization (MOEGO). Considering that expected improvement (EI) is a cornerstone in efficient global optimization (EGO), this article first studies the relationship between R2-based EI and Tchebycheff-based EI. Then, we introduce a many-to-few (M2F) decomposition framework, offering a new perspective for linking the R2-based method and the Tchebycheff decomposition approach. By incorporating M2F decomposition into MOEGO, a new algorithm called R2/D-EGO is proposed. At each iteration, R2/D-EGO utilizes the Tchebycheff decomposition paradigm to generate a set of candidate solutions, each one corresponding to a different weight vector. Subsequently, a subset of query points is selected from the candidates based on the lower bound of R2-based EI. Empirical results indicate that the proposed R2/D-EGO is highly competitive in comparison with both the R2-based and decomposition-based MOEGO algorithms in the parallel (or batch) setting.

Neural combinatorial optimization (NCO) is a promising learning-based approach to solving complex combinatorial optimization problems such as the traveling salesman problem (TSP), the vehicle routing problem (VRP), and the orienteering problem (OP). However, how to efficiently train a powerful NCO solver for routing problems remains a crucial challenge. The widely used reinforcement learning method suffers from sparse rewards and low data efficiency, while the supervised learning approach requires a large number of high-quality solutions (i.e., labels) that could be costly to obtain. In this work, we find that simple data augmentation operations can drastically reduce the number of required high-quality solutions for supervised learning. Moreover, simple boosting strategies that leverage the property of multiple optima can significantly improve training efficiency. With only a small set of \(50{,}000\) labeled instances, supervised learning can achieve a competitive in-distribution performance with the widely used reinforcement learning counterpart. Furthermore, we also investigate the generalization ability for larger out-of-distribution problems. We believe the findings from this work may lead to a rethinking of the value of data-efficient supervised learning for NCO solver training.

The main challenge of multimodal change detection (MCD) is that multimodal bitemporal images (MBIs) cannot be compared directly to identify changes. To overcome this problem, this paper proposes a novel commonality feature representation learning (CFRL) and constructs a CFRL-based unsupervised MCD framework. The CFRL is composed of a Siamese-based encoder and two decoders. First, the Siamese-based encoder can map original MBIs in the same feature space for extracting the representative features of each modality. Then, the two decoders are used to reconstruct the original MBIs by regressing themselves, respectively. Meanwhile, we swap the decoders to reconstruct the pseudo-MBIs to conduct modality alignment. Subsequently, all reconstructed images are input to the Siamese-based encoder again to map them in a same feature space, by which representative features are obtained. On this basis, latent commonality features between MBIs can be extracted by minimizing the distance between these representative features. These latent commonality features are comparable and can be used to identify changes. Notably, the proposed CFRL can be performed simultaneously in two modalities corresponding to MBIs. Therefore, two change magnitude images (CMIs) can be generated simultaneously by measuring the difference between the commonality features of MBIs. Finally, a simple threshold algorithm or a clustering algorithm can be employed to divide CMIs into binary change maps. Extensive experiments on six publicly available MCD datasets show that the proposed CFRL-based framework can achieve superior performance compared with other state-of-the-art approaches.

Learning graphical causal models from observational data can effectively elucidate the underlying causal mechanism behind the variables. In the context of limited datasets, modelers often incorporate prior knowledge, which is assumed to be correct, as a penalty in single-objective optimization. However, this approach struggles to adapt complex and uncertain priors effectively. This paper introduces UpCM, which tackles the issue from a multi-objective optimization perspective. Instead of focusing exclusively on the DAG as the optimization goal, UpCM methodically evaluate the effect of uncertain priors on specific structures, merging data-driven and knowledge-driven objectives. Utilizing the MOEA/D framework, it achieve a balanced tradeoff between these objectives. Furthermore, since uncertain priors may introduce erroneous constraints, resulting in PDAGs lacking consistent extensions, the minimal non-consistent extension is explored. This extension, which separately incorporates positive and negative constraints, aims to approximate the true causality of the PDAGs. Experimental results demonstrate that UpCM achieves significant structural accuracy improvements compared to baseline methods. It reduces the SHD by 7.94%, 13.23%, and 12.8% relative to PC stable, GES, and MAHC, respectively, when incorporating uncertain priors. In downstream inference tasks, UpCM outperforms domain-expert knowledge graphs, owing to its ability to learn explainable causal relationships that balance data-driven evidence with prior knowledge

Pre-training GNNs to extract transferable knowledge and apply it to downstream tasks has become the de facto standard of graph representation learning. Recent works focused on designing self-supervised pre-training tasks to extract useful and universal transferable knowledge from large-scale unlabeled data. However, they have to face an inevitable question: traditional pre-training strategies that aim at extracting useful information about pre-training tasks, may not extract all useful information about the downstream task. In this paper, we reexamine the pre-training process within traditional pre-training and fine-tuning frameworks from the perspective of Information Bottleneck (IB) and confirm that the forgetting phenomenon in pre-training phase may cause detrimental effects on downstream tasks. Therefore, we propose a novelDelayedBottleneckingPre-training (DBP) framework which maintains as much as possible mutual information between latent representations and training data during pre-training phase by suppressing the compression operation and delays the compression operation to fine-tuning phase to make sure the compression can be guided with labeled fine-tuning data and downstream tasks. To achieve this, we design two information control objectives that can be directly optimized and further integrate them into the actual model design. Extensive experiments on both chemistry and biology domains demonstrate the effectiveness of DBP.

Transforming a constrained optimization problem (COP) into a multi/many-objective optimization problem (MOP/MaOP) represents a practical approach for solving COPs. This article introduces an adaptive multi/many-objective transformation technique, termed adaptive many-objective transformation technique (AMaOTCO), designed to effectively address COPs. The transformed many-objective optimization problem (MaOP) defines an objective using a convex combination of the objective function (or constraint violation function) and an auxiliary function. This auxiliary function is constructed through a convex combination of the objective function and a weighted constraint violation function. The adaptive tuning of all combination coefficients is based on population information. This adaptive tuning ensures an intelligent balance between minimizing various constraint violations and managing the tradeoff between objective function minimization and constraint violation reduction. The effectiveness of the proposed AMaOTCO is demonstrated through comparisons with state-of-the-art constrained evolutionary algorithms (CEAs) on a set of real-world COPs.

Multi-objective Stochastic Linear bandit (MOSLB) plays a critical role in the sequential decision-making paradigm, however, most existing methods focus on the Pareto dominance among different objectives without considering any priority. In this paper, we study bandit algorithms under mixed Pareto-lexicographic orders, which can reflect decision makers' preferences. We adopt the Grossone approach to deal with these orders and develop the notion of Pareto-lexicographic optimality to evaluate the learners' performance. Our work represents a first attempt to address these important and realistic orders in bandit algorithms. To design algorithms under these orders, the upper confidence bound (UCB) policy and the prior free lexicographical filter are adapted to approximate the optimal arms at each round. Moreover, the framework of the algorithms involves two stages in pursuit of the balance between exploration and exploitation. Theoretical analysis as well as numerical experiments demonstrate the effectiveness of our algorithms.

This paper studies the multiobjective bandit problem under lexicographic ordering, wherein the learner aims to simultaneously maximize ? objectives hierarchically. The only existing algorithm for this problem considers the multi-armed bandit model, and its regret bound is O((KT)^(2/3)) under a metric called priority-based regret. However, this bound is suboptimal, as the lower bound for single objective multi-armed bandits is Omega(KlogT). Moreover, this bound becomes vacuous when the arm number K is infinite. To address these limitations, we investigate the multiobjective Lipschitz bandit model, which allows for an infinite arm set. Utilizing a newly designed multi-stage decision-making strategy, we develop an improved algorithm that achieves a general regret bound of O(T^((d_z^i+1)/(d_z^i+2))) for the i-th objective, where d_z^i is the zooming dimension for the i-th objective, with i in {1,2,...,m}. This bound matches the lower bound of the single objective Lipschitz bandit problem in terms of T, indicating that our algorithm is almost optimal. Numerical experiments confirm the effectiveness of our algorithm.

Multi-task learning deals with multiple related tasks simultaneously by sharing knowledge. In a typical deep multi-task learning model, all tasks use the same feature space and share the latent knowledge. If the tasks are weakly correlated or some features are negatively correlated, sharing all knowledge often leads to negative knowledge transfer among. To overcome this issue, this paper proposes a Fisher sparse multi-task learning method. It can obtain a sparse sharing representation for each task. In such a way, tasks share features on a sparse subspace. Our method can ensure that the knowledge transferred among tasks is beneficial. Specifically, we first propose a sparse deep multi-task learning model, and then introduce Fisher sparse module into traditional deep multi-task learning to learn the sparse variables of task. By alternately updating the neural network parameters and sparse variables, a sparse sharing representation can be learned for each task. In addition, in order to reduce the computational overhead, an heuristic method is used to estimate the Fisher information of neural network parameters. Experimental results show that, comparing with other methods, our proposed method can improve the performance for all tasks, and has high sparsity in multi-task learning.

Recently, multi-objective evolutionary algorithms (MOEAs) with an unbounded external archive (UEA) have received increasing attention in the evolutionary multi-objective optimization community. Its basic idea is to store all examined solutions during the optimization process and select representative solutions as the final output for the decision-maker (DM). Although many studies have investigated MOEAs with UEA, there is a lack of studies focusing on the final solution selection. Actually, selecting a good solution from UEA that meets the requirements of the DM is a challenging task due to the limited information processing capacity of the human decision-maker. Moreover, in many real-world scenarios, decision-makers often prefer not to evaluate a large number of solutions and may not have clear preferences over objectives. To fill this gap in post-processing for MOEAs with UEA, this paper proposes an interactive final solution selection (IFSS) method for multi-objective optimization. The proposed IFSS method aims to provide a good final solution through several interactions with the DM. In other words, the DM can obtain a satisfying solution after evaluating only a small number of solutions even without providing clearly specific preferences. Furthermore, a calibration strategy is introduced to significantly improve the performance of IFSS by slightly increasing the number of interactions. Extensive experiments are conducted on various test problems to demonstrate the effectiveness of the proposed IFSS method.

Integrating non-elitist evolution strategies into MOEA/D is challenging because the former usually requires many samples for updates, which is costly for MOEAID. In contrast, we suggest using (1+ 1)-ES for three reasons: fewer samples needed for updates, lower computational overhead, and better flexibility for subproblem collaboration. To verify this, we introduce (1+1)-MOEA/D-CMA, where each subproblem is solved by a different (1+1)-ES solver, and the solvers collaborate through a novel solution injection scheme. Comprehensive experiments show that the proposed algorithm performs better than several widely used algorithms. More importantly, owing to the lightweight nature of (1+1)-CMA-ES, the algorithm is shown to run faster and scale better to large population sizes, than other MOEA/D variants based on (µ/µw, λ)-CMA-ES.

The hardness of the Unconstrained Binary Quadratic Program (UBQP) problem is due its rugged landscape. Various algorithms have been proposed for UBQP, including the Landscape Smoothing Iterated Local Search (LSILS). Different from other UBQP algorithms, LSILS tries to smooth the rugged landscape by building a convex combination of the original UBQP and a toy UBQP. In this paper, our study further investigates the impact of smoothing rugged landscapes using different toy UBQP problems, including a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{1}$(construct by “$+/-1$‘), a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{2}$(construct by “$+/-\mathrm{i}$’) and a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{3}$(construct randomly). We first assess the landscape flatness of the three toy UBQPs. Subsequently, we test the efficiency of LSILS with different toy UBQPs. Results reveal that the toy UBQP with$\hat{\boldsymbol{Q}}^{1}$(construct by “$+/-1$”) exhibits the flattest landscape among the three, while the toy UBQP with$\hat{Q}^{3}$(construct randomly) presents the most non-flat landscape. Notably, LSILS using the toy UBQP with$\hat{\boldsymbol{Q}}^{2}$(construct by “$+/\cdot \mathbf{i})$emerges as the most effective, while$\hat{\boldsymbol{Q}}^{3}$(construct randomly) has the poorest result. These findings contribute to a detailed understanding of landscape smoothing techniques in optimizing UBQP.

Optimizing antenna placement in in-building distributed antenna systems is critical for achieving comprehensive 5G coverage. Due to the utilization of high-frequency signal bands, the propagation of 5G signals is significantly influenced by distance and obstacles in indoor environments. Consequently, devising effective placement schemes faces challenges in complex indoor scenarios. This paper presents a multiobjective genetic algorithm for antenna placement optimization. It tracks the signal propagation by introducing the ray-tracing propagation model. Although the ray-tracing propagation model provides high simulation accuracy, it also incurs substantial computation costs, rendering the antenna placement problem expensive. To tackle this challenge, the algorithm introduces the idea of Bayesian optimization, where a surrogate model replaces certain calculations in the ray tracing propagation model, thereby reducing the computational burden. Experimental results demonstrate the superior performance of the proposed algorithm compared to other algorithms in two real-world scenarios, as evidenced by evaluations based on hypervolume and inverted generational distance metrics.

When gradient information is available, multi-objective Bayesian optimization (MOBO) algorithm using gradient-enhanced Gaussian process (GradGP) models has been proven to be an efficient method. However, the intractable training and inference complexity hinders its scalability in high-throughput scenarios with large batch sizes and increasing data volume. To address this issue, we develop an efficient high-throughput MOBO algorithm using gradient information named MOEAID-DSVGP, which integrates stochastic variational GP models using directional derivatives (DSVGP) within the decomposition-based MOBO framework. In this algorithm, DSVGP model is trained for each objective function by optimizing a small set of inducing inputs and inducing directions as variational parameters, the complexity is independent of sample size and input dimension. MOEAID is employed as the inner optimizer for high-throughput solution generation. Experimental studies with varying batch sizes and input dimensions show that compared to GradGP-based MOBO method, the proposed algorithm exhibits superior scalability and allows more optimization iterations to yield better outcome in most cases. We further investigate and analyze the influence of increasing the number of inducing directions on the performance improvement in problems with different features.

To improve the convergence ability of evolutionary multi-objective optimization algorithms (EMOAs), various strategies have been proposed. One effective strategy is to use good momentum from the previous generations to create new solutions. However, the definition of good momentum has not been carefully studied. In this paper, we propose five different definitions of good momentum for EMOAs. Then, we explain their integration into popular EMOAs such as NSGA-II, MOEA/D, and SMS-EMOA. Through computational experiments, we demonstrate that the use of an appropriate definition of good momentum greatly accelerates the convergence of EMOAs on both artificial test problems and real-world problems, particularly on large-scale problems.

Recently, there has been a growing interest in large-scale multiobjective optimization problems within the evolutionary multiobjective optimization (EMO) community. These problems involve hundreds or thousands of decision variables and multiple conflicting objectives, which pose significant challenges for conventional EMO algorithms (EMOAs). It is generally believed that EMOAs have difficulty in efficiently finding good non-dominated solutions as the number of decision variables increases. To address this issue, in this paper, we propose a novel method that incorporates heuristic initialization and knowledge-based mutation into EMOAs for solving large-scale multi-objective 0-1 knapsack problems. Various large-scale multi-objective 0-1 knapsack problems with an arbitrary number of constraints are generated as test problems to evaluate the effectiveness of the proposed method. Experimental results show that the proposed novel initialization and mutation method significantly improves the performance of the original EMOAs in terms of both the convergence speed in early generations and the quality of the final population.

Newly proposed many-objective algorithms have been almost always compared with NSGA-III for performance evaluation. Since the authors of the NSGA-III paper have not provided any source code, researchers usually use an available implementation in popular optimization platforms. This can lead to unreliable comparison results if different performance of NSGA-III is obtained depending on the choice of a platform. In this paper, we show that the implementations of NSGA-III are slightly different between the two most frequently used EMO optimization platforms: PlatEMO and pymoo. Then, we examine the effect of the implementation difference on the performance of NSGA-III in each platform. Our experimental results show that almost the same results are obtained from the two implementations on the frequently-used DTLZ test problems. However, our experimental results also show that clearly different results are obtained from the two implementations on multi-objective combinatorial optimization problems. Finally, we demonstrate that the weaker performance of the PlatEMO implementation of NSGA-III can be improved by replacing its normalization mechanism with the corresponding mechanism in Pymoo. That is, our experimental results show that small differences in the normalization mechanisms of the two implementations lead to large differences in their performance on multi-objective combinatorial optimization problems.

Multi-objective optimization problems can be found in many real-world applications, where the objectives often conflict each other and cannot be optimized by a single solution. In the past few decades, numerous methods have been proposed to find Pareto solutions that represent optimal trade-offs among the objectives for a given problem. However, these existing methods could have high computational complexity or may not have good theoretical properties for solving a general differentiable multi-objective optimization problem. In this work, by leveraging the smooth optimization technique, we propose a lightweight and efficient smooth Tchebycheff scalarization approach for gradient-based multi-objective optimization. It has good theoretical properties for finding all Pareto solutions with valid trade-off preferences, while enjoying significantly lower computational complexity compared to other methods. Experimental results on various real-world application problems fully demonstrate the effectiveness of our proposed method.

Heuristics are widely used for dealing with complex search and optimization problems. However, manual design of heuristics can be often very labour extensive and requires rich working experience and knowledge. This paper proposes Evolution of Heuristic (EoH), a novel evolutionary paradigm that leverages both Large Language Models (LLMs) and Evolutionary Computation (EC) methods for Automatic Heuristic Design (AHD). EoH represents the ideas of heuristics in natural language, termed thoughts. They are then translated into executable codes by LLMs. The evolution of both thoughts and codes in an evolutionary search framework makes it very effective and efficient for generating high-performance heuristics. Experiments on three widely studied combinatorial optimization benchmark problems demonstrate that EoH outperforms commonly used handcrafted heuristics and other recent AHD methods including FunSearch. Particularly, the heuristic produced by EoH with a low computational budget (in terms of the number of queries to LLMs) significantly outperforms widely-used human hand-crafted baseline algorithms for the online bin packing problem.

Neural Network-based active learning (NAL) is a cost-effective data selection technique that utilizes neural networks to select and train on a small subset of samples. While existing work successfully develops various effective or theory-justified NAL algorithms, the understanding of the two commonly used query criteria of NAL: uncertainty-based and diversity-based, remains in its infancy. In this work, we try to move one step forward by offering a unified explanation for the success of both query criteria-based NAL from a feature learning view. Specifically, we consider a feature-noise data model comprising easy-to-learn or hard-to-learn features disrupted by noise, and conduct analysis over 2-layer NN-based NALs in the pool-based scenario. We provably show that both uncertainty-based and diversity-based NAL are inherently amenable to one and the same principle, i.e., striving to prioritize samples that contain yet-to-be-learned features. We further prove that this shared principle is the key to their success-achieve small test error within a small labeled set. Contrastingly, the strategy-free passive learning exhibits a large test error due to the inadequate learning of yet-to-be-learned features, necessitating resort to a significantly larger label complexity for a sufficient test error reduction. Experimental results validate our findings.

Real-world data generally follows a long-tailed distribution, which makes traditional high-performance training strategies unable to show their usual effects. Various insights have been proposed to alleviate this challenging distribution. However, some observations indicate that models trained on long-tailed distributions always show a trade-off between the performance of head and tail classes. For a profound understanding of the trade-off, we first theoretically analyze the trade-off problem in long-tailed learning and creatively transform the trade-off problem in long-tailed learning into a multi-objective optimization (MOO) problem. Motivated by these analyses, we propose the idea of strategy fusion for MOO long-tailed learning and point out the potential conflict problem. We further design a Multi-Objective Optimization based Strategy Fusion (MOOSF), which effectively resolves conflicts, and achieves an efficient fusion of heterogeneous strategies. Comprehensive experiments on mainstream datasets show that even the simplest strategy fusion can outperform complex long-tailed strategies. More importantly, it provides a new perspective for generalized long-tailed learning. The code is available in the accompanying supplementary materials.

To improve meta-generalization, i.e., accommodating out-of-domain meta-testing tasks beyond meta-training ones, is of significance to extending the success of meta-learning beyond standard benchmarks. Previous heterogeneous meta-learning algorithms have shown that tailoring the global meta-knowledge by the learned clusters during meta-training promotes better meta-generalization to novel meta-testing tasks. Inspired by this, we propose a novel multi-objective perspective to sharpen the compositionality of the meta-trained clusters, through which we have empirically validated that the meta-generalization further improves. Grounded on the hierarchically structured meta-learning framework, we formulate a hypervolume loss to evaluate the degree of conflict between multiple cluster-conditioned parameters in the two-dimensional loss space over two randomly chosen tasks belonging to two clusters and two mixed tasks imitating out-of-domain tasks. Experimental results on more than 16 few-shot image classification datasets show not only improved performance on out-of-domain meta-testing datasets but also better clusters in visualization.

Vehicle routing problems (VRP) are very important in many realworld applications and has been studied for several decades.Recently, neural combinatorial optimization (NCO) has attracted growing research effort.NCO is to train a neural network model to solve an optimization problem in question.However, existing NCO methods often build a different model for each routing problem, which significantly hinders their application in some areas where there are many different VRP variants to solve.In this work, we make a first attempt to tackle the crucial challenge of cross-problem generalization in NCO.We formulate VRPs as different combinations of a set of shared underlying attributes and solve them simultaneously via a single model through attribute composition.In this way, our proposed model can successfully solve VRPs with unseen attribute combinations in a zero-shot generalization manner.In our experiments, the neural model is trained on five VRP variants and its performance is tested on eleven VRP variants.The experimental results show that the model demonstrates superior performance on these eleven VRP variants, reducing the average gap to around 5% from over 20% and achieving a notable performance boost on both benchmark datasets and real-world logistics scenarios.

Transformer-based large language models (LLMs) have displayed remarkable creative prowess and emergence capabilities. Existing empirical studies have revealed a strong connection between these LLMs' impressive emergence abilities and their in-context learning (ICL) capacity, allowing them to solve new tasks using only task-specific prompts without further fine-tuning. On the other hand, existing empirical and theoretical studies also show that there is a linear regularity of the multi-concept encoded semantic representation behind transformer-based LLMs. However, existing theoretical work fail to build up an understanding of the connection between this regularity and the innovative power of ICL. Additionally, prior work often focuses on simplified, unrealistic scenarios involving linear transformers or unrealistic loss functions, and they achieve only linear or sub-linear convergence rates. In contrast, this work provides a fine-grained mathematical analysis to show how transformers leverage the multi-concept semantics of words to enable powerful ICL and excellent out-of-distribution ICL abilities, offering insights into how transformers innovate solutions for certain unseen tasks encoded with multiple cross-concept semantics. Inspired by empirical studies on the linear latent geometry of LLMs, the analysis is based on a concept-based low-noise sparse coding prompt model. Leveraging advanced techniques, this work showcases the exponential 0-1 loss convergence over the highly non-convex training dynamics, which pioneeringly incorporates the challenges of softmax self-attention, ReLU-activated MLPs, and cross-entropy loss. Empirical simulations corroborate the theoretical findings.

The long-tailed distribution is the underlying nature of real-world data, and it presents unprecedented challenges for training deep learning models. Existing long-tailed learning paradigms based on re-balancing or data augmentation have partially alleviated the long-tailed problem. However, they still have limitations, such as relying on manually designed augmentation strategies, having a limited search space, and using fixed augmentation strategies. To address these limitations, this paper proposes a novel LLM-based long-tailed data augmentation framework called LLM-AutoDA, which leverages large-scale pretrained models to automatically search for the optimal augmentation strategies suitable for long-tailed data distributions. In addition, it applies this strategy to the original imbalanced data to create an augmented dataset and fine-tune the underlying long-tailed learning model. The performance improvement on the validation set serves as a reward signal to update the generation model, enabling the generation of more effective augmentation strategies in the next iteration. We conducted extensive experiments on multiple mainstream long-tailed learning benchmarks. The results show that LLM-AutoDA outperforms state-of-the-art data augmentation methods and other re-balancing methods significantly.

Multiobjective optimization (MOO) plays a critical role in various real-world domains. A major challenge therein is generating $K$ uniform Pareto-optimal solutions to represent the entire Pareto front. To address this issue, this paper firstly introduces \emph{fill distance} to evaluate the $K$ design points, which provides a quantitative metric for the representativeness of the design. However, directly specifying the optimal design that minimizes the fill distance is nearly intractable due to the nested $\min-\max-\min$ optimization problem. To address this, we propose a surrogate ``max-packing'' design for the fill distance design, which is easier to optimize and leads to a rate-optimal design with a fill distance at most $4\times$ the minimum value. Extensive experiments on synthetic and real-world benchmarks demonstrate that our proposed paradigm efficiently produces high-quality, representative solutions and outperforms baseline methods.

Multiobjective optimization problems (MOPs) are prevalent in machine learning, with applications in multi-task learning, learning under fairness or robustness constraints, etc. Instead of reducing multiple objective functions into a scalar objective, MOPs aim to optimize for the so-called Pareto optimality or Pareto set learning, which involves optimizing more than one objective function simultaneously, over models with thousands to millions of parameters. Existing benchmark libraries for MOPs mainly focus on evolutionary algorithms, most of which are zeroth-order or meta-heuristic methods that do not effectively utilize higher-order information from objectives and cannot scale to large-scale models with millions of parameters. In light of the above challenges, this paper introduces \algoname, the first multiobjective optimization library that supports state-of-the-art gradient-based methods, provides a fair and comprehensive benchmark, and is open-sourced for the community.

Traditional long-tailed learning methods often perform poorly when dealing with inconsistencies between training and test data distributions, and they cannot flexibly adapt to different user preferences for trade-offs between head and tail classes. To address this issue, we propose a novel long-tailed learning paradigm that aims to tackle distribution shift in real-world scenarios and accommodate different user preferences for the trade-off between head and tail classes. We generate a set of diverse expert models via hypernetworks to cover all possible distribution scenarios, and optimize the model ensemble to adapt to any test distribution. Crucially, in any distribution scenario, we can flexibly output a dedicated model solution that matches the user's preference. Extensive experiments demonstrate that our method not only achieves higher performance ceilings but also effectively overcomes distribution shift while allowing controllable adjustments according to user preferences. We provide new insights and a paradigm for the long-tailed learning problem, greatly expanding its applicability in practical scenarios. The code can be found here: https://github.com/DataLab-atom/PRL.

Current methods for large language model alignment typically use scalar human preference labels. However, this convention tends to oversimplify the multi-dimensional and heterogeneous nature of human preferences, leading to reduced expressivity and even misalignment. This paper presents Panacea, an innovative approach that reframes alignment as a multi-dimensional preference optimization problem. Panacea trains a single model capable of adapting online and Pareto-optimally to diverse sets of preferences without the need for further tuning. A major challenge here is using a low-dimensional preference vector to guide the model's behavior, despite it being governed by an overwhelmingly large number of parameters. To address this, Panacea is designed to use singular value decomposition (SVD)-based low-rank adaptation, which allows the preference vector to be simply injected online as singular values. Theoretically, we prove that Panacea recovers the entire Pareto front with common loss aggregation methods under mild conditions. Moreover, our experiments demonstrate, for the first time, the feasibility of aligning a single LLM to represent an exponentially vast spectrum of human preferences through various optimization methods. Our work marks a step forward in effectively and efficiently aligning models to diverse and intricate human preferences in a controllable and Pareto-optimal manner.

In some industrial applications, it is required to do off-line multiobjective optimization in embedded systems. Due to their limited computing and memory capability, embedded processor may not be able to run conventional multiobjective optimization evolutionary algorithms (MOEAs). This article proposes a micro MOEA with piecewise strategy (μ MOEA) for industrial optimization in embedded processor. μ MOEA introduces an improved piecewise strategy based on the MOEA/D framework, which serially optimizes subclusters to be compatible with embedded processor under limited computing power. For the purpose of further enhancing μ MOEA, a dynamic and flexible weight vector update trigger mechanism is proposed, so that the algorithm can save and utilize the computing resources of the embedded processor as much as possible. Abundant artificial test problems are carrying out to test the performance of μ MOEA. Through various experiments, it can be found that μ MOEA has outstanding performance in ZDT, DTLZ, SMOP, and MaF problems. Last and most importantly, μ MOEA is successfully applied to two specific application scenarios of industrial optimization on embedded processor for simulation, such as two different types of semi-autogenous grinding optimization problems and micro-grid energy optimization problem, which prove the feasibility of applying MOEA to embedded processor.

Pareto local search (PLS) is a natural extension of local search for multiobjective combinatorial optimization problems (MCOPs). In our previous work, we improved the anytime performance of PLS using parallel computing techniques and proposed a parallel PLS based on decomposition (PPLS/D). In PPLS/D, the solution space is searched by multiple independent parallel processes simultaneously. This article further improves PPLS/D by introducing two new cooperative process techniques, namely, a cooperative search mechanism and a cooperative subregion-adjusting strategy. In the cooperative search mechanism, the parallel processes share high-quality solutions with each other during the search according to a distributed topology. In the proposed subregion-adjusting strategy, a master process collects useful information from all processes during the search to approximate the Pareto front (PF) and redivide the subregions evenly. In the experimental studies, three well-known NP-hard MCOPs with up to six objectives were selected as test problems. The experimental results on the Tianhe-2 supercomputer verified the effectiveness of the proposed techniques.

This article proposes utilizing a single deep reinforcement learning model to solve combinatorial multiobjective optimization problems. We use the well-known multiobjective traveling salesman problem (MOTSP) as an example. Our proposed method employs an encoder-decoder framework to learn the mapping from the MOTSP instance to its Pareto-optimal set. Specifically, it leverages a novel routing encoder to extract information for both the entire multiobjective aspect and every individual objective from the MOTSP instance. The global embeddings and each objective's embeddings are adaptively aggregated via a routing network to form the subproblems' embedding that can well represent the MOTSP features. Using a modified context embedding, the subproblems' embeddings are fed into a decoder to produce a set of approximate Pareto-optimal solutions in parallel. Additionally, we develop a Top-k baseline to enable more efficient data utilization and lightweight training for our proposed method. We compare our method with heuristic-based and learning-based ones on various types of MOTSP instances, and the experimental results show that our method can solve MOTSP instances in real-time and outperform the other algorithms, especially on large-scale problem instances.

The hypervolume contribution is widely used in indicator-based multiobjective algorithms. We propose an algorithm to compute exact 4-D hypervolume contributions for a set of n points in O(n32logn) time. Our algorithm improves the currently best time complexity O(n2) by O(nlogn), and it is the first algorithm of subquadratic time for this problem. Our algorithm is built upon a space partition method in computational geometry and a geometric structure called the anchored gradient. We also propose a new space partition strategy to reduce the practical running time and the space overhead of this algorithm. Experimental results on a variety of test instances show that our proposed algorithm performs better than the existing state-of-the-art algorithm especially on point sets with cliff or other irregular properties.

High quality product quality prediction is very important for iron and steel enterprises to ensure stable production. However, most existing prediction methods are manually designed learning models. These methods consider only macroscopic data while ignoring mesoscopic data that also have a significant impact on product quality. Thus, they are often poor at accuracy and generalization performance in practice. To address this issue, a multi-objective convolutional neural networks ensemble learning method with multi-scale data fusion (MOCNNEL-MSDF) is developed. Using data fusion of macro/meso data derived from kinetic models, MOCNNEL-MSDF first evolves a swarm of convolutional neural networks (CNNs) by knowledge-transferring based reproduction and adaptive weights initialization adjustment to improve learning performance, and then a sparse ensemble approach based on differential evolution is applied to achieve the final prediction model from the evolved CNNs. Experimental results on both benchmark data and practical data of continuous annealing show that MOCNNEL-MSDF achieves competitive or better accuracy and robustness compared with other powerful learning methods, and outperforms the existing strip quality prediction models. The proposed method can be used in the product quality modeling of each process in the iron and steel industry, where it is desirable to combine mechanism models with production process data to construct a product quality prediction model with higher accuracy and generalization.

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

The hypervolume metric is widely used to guide the search in multiobjective optimization. However, in parallel expensive multiobjective optimization, the hypervolume-based multipoint expected improvement (EI) suffers from high computational overhead and scales poorly with the batch size. To address this issue, we integrate hypervolume-based EI with the MOEA/D framework and propose a novel EI, named the expected direction-based hypervolume improvement (DirHV-EI). The DirHV-EI only measures the hypervolume improvement within each axis-parallel box induced by the modified Tchebycheff scalarization. Thus, it has a simple analytical expression that can be easily computed. Theoretical analysis indicates that the maximization of our proposed improvement function can help to maximize both the weighted hypervolume and the Tchebycheff improvement metrics. Using DirHV-EI, we design a decomposition-based Bayesian optimization algorithm for solving expensive multiobjective optimization problems. At each iteration, the MOEA/D is used to maximize the DirHV-EI values with respect to a number of direction vectors in a collaborative manner, and a number of candidate solutions can be obtained. Then, a submodularity-based greedy selection strategy is used to select multiple query points from the candidates. Experimental results on both benchmark instances and real-world problems show that our proposed algorithm is an efficient and effective method for parallel expensive multiobjective optimization.

A novel nanobiosensing framework named “in vivo computation” has been proposed recently, where the challenge of early tumor detection is overcome from an optimization perspective. The biological gradient field (BGF) triggered by the tumor lesion is viewed as the optimizable objective function with the tumor site being the global optimum. The externally manipulable nanorobots playing the role of agents are manipulated in the search space (i.e., the vascular network of high-risk tissue). Several computational strategies have been proposed to realize tumor targeting by overcoming the in vivo constraints which focused on the tumor detection process without any emphasis on the nanorobots aggregation at the tumor. In this paper, we focus on the utilization rate of agents, which means to improve the percentage of nanorobots that detect the tumor site after it has been found by the first arrival agent (i.e., the nanorobot that detects the tumor at the earliest), and the solution set search, which means to find the tumor region as whole as possible. This process is interpreted as the exploitation process of in vivo computation. An exploitation approach named center-aided weak priority evolution strategy (CWP-ES) is developed for the setting of nanorobot moving direction in this paper. In the approach, a direction generated by the center of agents that have found the tumor mixed with the direction generated by the weak priority evolution strategy (WP-ES) proposed in the previous work is used to steer the motion of nanorobots that have not detected the tumor. Several numerical experiments are performed in a 3D search space to show the effectiveness of this novel computational nanobiosensing approach in three BGF landscapes with different degrees of optimization complexity.

The research on expensive multiobjective optimization has attracted particular attention in the area of multiobjective evolutionary computation. Many existing multiobjective evolutionary algorithms (MOEAs) are only suited for small-scale expensive multiobjective optimization problems (MOPs) with less than ten decision variables. The main reason lies in the fact that some optimization techniques used in expensive MOEAs, such as Gaussian Process (GP), are not applicable for exploring high-dimensional search space. The naive way to overcome this difficulty is to convert a high-dimensional expensive MOP into a low-dimensional MOP, which can be solved by existing expensive MOEAs efficiently. In this paper, we investigate the combination of MOEA/D with a weighted optimization framework (WOF) and GP, denoted by MOEA/D-WOFGP, for solving high-dimensional expensive MOPs, where the WOF converts a high-dimensional MOP into a low-dimensional search space of weight variables, and the GP-based learning method is used to predict high-quality solutions within a limited number of function evaluations. Some experiments are conducted to compare the performance of MOEA/D-WOFGP with other expensive MOEAs assisted by variable grouping. Our experimental results show that MOEA/D-WOFGP is advantageous when dealing with high-dimensional expensive MOPs.

The Vehicle routing problems (VRP) are one of the most studied combinatorial optimization problems. This paper targets an important and challenging VRP variant, named multi-objective vehicle routing problems with time windows. We propose to use a multi-objective evolutionary algorithm based on decomposition (MOEA/D) to decompose the problem into a set of single-objective sub-problems. For each sub-problem, efficient crossover and local search heuristics are adopted to generate and improve new solutions. We design two new strategies to decrease the number of vehicles, a population management method with infeasible solutions and a multi-split strategy. Experimental studies are carried out on the well-known Solomon's dataset. Results suggest that our proposed algorithm is very competitive compared to two state-of-the-art algorithms. It generates better solutions on 90% of the test instances.

Expected improvement (EI) is a widely used acqui-sition function in single-objective Bayesian optimization (BO). To deal with expensive multiobjective optimization problems, many extensions of EI have been proposed. Among them, expected Tchebycheff improvement (ETI) is a representative approach. Unfortunately, the calculation of exact ETI values remains a challenging task when leveraging Gaussian process models to model each objective. Therefore, approximation methods are commonly employed. However, the estimation error of these methods cannot be fully determined without the aid of exact formulas. Borrowing the idea of the exact formulas previously developed for the computation of multi-point EI in single-objective BO, this article gives an exact formula for the computation of ETI with any number of objectives. Numerical experiments are conducted to compare the performance of our exact formula and a commonly- used approximation method. Considering the similarity of ETI and multi-point EI, we also extend the approximation method designed for ETI to estimate the values of multi-point EI efficiently.

A long-standing question in the evolutionary multi-objective (EMO) community is how to generate a good initial population for EMO algorithms. Intuitively, as the starting point of optimization, a good initial population can have positive effects on the performance of EMO algorithms. However, in most existing EMO algorithms, one of the commonly-used initialization methods is to randomly generate a set of solutions as an initial population. One possible approach to improve random initialization is to include one or more Pareto optimal (near Pareto optimal) solution(s) in the initial population, which are expected to provide useful information and knowledge on the optimized problem. In this paper, to investigate the effectiveness of this initialization idea, we examine and quantify the effects of including one or more Pareto optimal solution(s) in the initial population on the performance of EMO algorithms. Experimental results demonstrate that it is worthwhile to first obtain and then include some Pareto optimal solutions in the initial population. Through a number of experiments and algorithm behavior analysis, this study provides supports and insights into EMO algorithm design and motivates further research on population initialization for EMO algorithms.

We present Neural Radiance Fields (NeRF) with Template, dubbed Template-NeRF, for modeling 3D appearance and geometry and generating dense shape correspondence simultaneously among objects of the same category from only multi-view posed images. No 3D supervision or ground-truth correspondence knowledge is required. The learned dense correspondence can be directly used for various image-based tasks such as keypoint detection, part segmentation, and texture transfer that previously required specific model designs. Our method can also accommodate annotation transfer in a one or few-shot manner. Given only one or a few annotated instances of the category, our model can transfer to many others. We introduce deep implicit templates on 3D data into the 3D-aware image synthesis pipeline NeRF using periodic activation and feature-wise linear modulation (FiLM) conditioning. By representing object instances within the same category as shape and appearance variation of a shared NeRF template, our proposed method can achieve dense shape correspondence reasoning on images for a wide range of object classes.

Homotopy optimization is a traditional method to deal with a complicated optimization problem by solving a sequence of easy-to-hard surrogate subproblems. However, this method can be very sensitive to the continuation schedule design and might lead to a suboptimal solution to the original problem. In addition, the intermediate solutions, often ignored by classic homotopy optimization, could be useful for many real-world applications. In this work, we propose a novel model-based approach to learn the whole continuation path for homotopy optimization, which contains infinite intermediate solutions for any surrogate subproblems. Rather than the classic unidirectional easy-to-hard optimization, our method can simultaneously optimize the original problem and all surrogate subproblems in a collaborative manner. The proposed model also supports the real-time generation of any intermediate solution, which could be desirable for many applications. Experimental studies on different problems show that our proposed method can significantly improve the performance of homotopy optimization and provide extra helpful information to support better decision-making.

Compositionality facilitates the comprehension of novel objects using acquired concepts and the maintenance of a knowledge pool. This is particularly crucial for continual learners to prevent catastrophic forgetting and enable compositionally forward transfer of knowledge. However, the existing state-of-the-art benchmarks inadequately evaluate the capability of compositional generalization, leaving an intriguing question unanswered. To comprehensively assess this capability, we introduce two vision benchmarks, namely Compositional GQA (CGQA) and Compositional OBJects365 (COBJ), along with a novel evaluation framework called Compositional Few-Shot Testing (CFST). These benchmarks evaluate the systematicity, productivity, and substitutivity aspects of compositional generalization. Experimental results on five baselines and two modularity-based methods demonstrate that current continual learning techniques do exhibit somewhat favorable compositionality in their learned feature extractors. Nonetheless, further efforts are required in developing modularity-based approaches to enhance compositional generalization. We anticipate that our proposed benchmarks and evaluation protocol will foster research on continual learning and compositionality.

Neural combinatorial optimization (NCO) is a promising learning-based approach for solving challenging combinatorial optimization problems without specialized algorithm design by experts. However, most constructive NCO methods cannot solve problems with large-scale instance sizes, which significantly diminishes their usefulness for real-world applications. In this work, we propose a novel Light Encoder and Heavy Decoder (LEHD) model with a strong generalization ability to address this critical issue. The LEHD model can learn to dynamically capture the relationships between all available nodes of varying sizes, which is beneficial for model generalization to problems of various scales. Moreover, we develop a data-efficient training scheme and a flexible solution construction mechanism for the proposed LEHD model. By training on small-scale problem instances, the LEHD model can generate nearly optimal solutions for the Travelling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP) with up to 1000 nodes, and also generalizes well to solve real-world TSPLib and CVRPLib problems. These results confirm our proposed LEHD model can significantly improve the state-of-the-art performance for constructive NCO.

This paper presents a novel approach to multiobjective algorithms aimed at modeling the Pareto set using neural networks. Whereas previous methods mainly focused on identifying a finite number of solutions, our approach allows for the direct modeling of the entire Pareto set. Furthermore, we establish an equivalence between learning the complete Pareto set and maximizing the associated hypervolume, which enables the convergence analysis of hypervolume (as a new metric) for Pareto set learning. Specifically, our new analysis framework reveals the connection between the learned Pareto solution and its representation in a polar coordinate system. We evaluate our proposed approach on various benchmark problems and real-world problems, and the encouraging results make it a potentially viable alternative to existing multiobjective algorithms. Code is available at \url{https://github.com/xzhang2523/hvpsl/tree/master}.

Population initialization is always needed in evolutionary multi-objective optimization (EMO) algorithms. Intuitively, a well-designed initialization method can help facilitate the evolutionary process and improve the performance of EMO algorithms. However, very few studies have investigated the effects of initialization methods on the performance of EMO algorithms. Many existing EMO algorithms randomly generate an initial population to start the evolutionary process. To fill this research gap and attract more attention from EMO researchers to this important yet under-explored issue, in this paper, we examine the effects of various initialization methods that may become promising alternatives to the commonly-used random initialization method. Each initialization method is evaluated through computational experiments on test problems of various sizes with 5–1000 decision variables. Experimental results clearly demonstrate the advantage of well-designed initialization methods over the random initialization method. This study provides useful insights into EMO algorithm design and motivates further research on population initialization.

The pure accuracy measure is used to eliminate random consistency from the accuracy measure. Biases to both majority and minority classes in the pure accuracy are lower than that in the accuracy measure. In this paper, we demonstrate that compared with the accuracy measure and F-measure, the pure accuracy measure is class distribution insensitive and discriminative for good classifiers. The advantages make the pure accuracy measure suitable for traditional classification. Further, we mainly focus on two points: exploring a tighter generalization bound on pure accuracy based learning paradigm and designing a learning algorithm based on the pure accuracy measure. Particularly, with the self-bounding property, we build an algorithm-independent generalization bound on the pure accuracy measure, which is tighter than the existing bound of an order O(1/√N) (N is the number of instances). The proposed bound is free from making a smoothness or convex assumption on the hypothesis functions. In addition, we design a learning algorithm optimizing the pure accuracy measure and use it in the selective ensemble learning setting. The experiments on sixteen benchmark data sets and four image data sets demonstrate that the proposed method statistically performs better than the other eight representative benchmark algorithms.

This article studies an intelligent reflecting surface (IRS)-aided communication system under the time-varying channels and stochastic data arrivals. In this system, we jointly optimize the phase-shift coefficient and the transmit power in sequential time slots to maximize the long-term energy consumption for all mobile devices while ensuring queue stability. Due to the dynamic environment, it is challenging to ensure queue stability. In addition, making real-time decisions in each short time slot also needs to be considered. To this end, we propose a method (called LETO) that combines Lyapunov optimization with evolutionary transfer optimization (ETO) to solve the above optimization problem. LETO first adopts Lyapunov optimization to decouple the long-term stochastic optimization problem into deterministic optimization problems in sequential time slots. As a result, it can ensure queue stability since the deterministic optimization problem in each time slot does not involve future information. After that, LETO develops an evolutionary transfer method to solve the optimization problem in each time slot. Specifically, we first define a metric to identify the optimization problems in past time slots similar to that in the current time slot, and then transfer their optimal solutions to construct a high-quality initial population in the current time slot. Since ETO effectively accelerates the search, we can make real-time decisions in each short time slot. Experimental studies verify the effectiveness of LETO by comparison with other algorithms.

In dealing with the expensive multiobjective optimization problem, some algorithms convert it into a number of single-objective subproblems for optimization. At each iteration, these algorithms conduct surrogate-assisted optimization on one or multiple subproblems. However, these subproblems may be unnecessary or resolved. Operating on such subproblems can cause server inefficiencies, especially in the case of expensive optimization. To overcome this shortcoming, we propose an adaptive subproblem selection (ASS) strategy to identify the most promising subproblems for further modeling. To better leverage the cross information between the subproblems, we use the collaborative multioutput Gaussian process surrogate to model them jointly. Moreover, the commonly used acquisition functions (also known as infill criteria) are investigated in this article. Our analysis reveals that these acquisition functions may cause severe imbalances between exploitation and exploration in multiobjective optimization scenarios. Consequently, we develop a new acquisition function, namely, adaptive lower confidence bound (ALCB), to cope with it. The experimental results on three different sets of benchmark problems indicate that our proposed algorithm is competitive. Beyond that, we also quantitatively validate the effectiveness of the ASS strategy, the CoMOGP model, and the ALCB acquisition function.

Detecting overlapping communities of an attribute network is a ubiquitous yet very difficult task, which can be modeled as a discrete optimization problem. Besides the topological structure of the network, node attributes and node overlapping aggravate the difficulty of community detection significantly. In this article, we propose a novel continuous encoding method to convert the discrete-natured detection problem to a continuous one by associating each edge and node attribute in the network with a continuous variable. Based on the encoding, we propose to solve the converted continuous problem by a multiobjective evolutionary algorithm (MOEA) based on decomposition. To find the overlapping nodes, a heuristic based on double-decoding is proposed, which is only with linear complexity. Furthermore, a postprocess community merging method in consideration of node attributes is developed to enhance the homogeneity of nodes in the detected communities. Various synthetic and real-world networks are used to verify the effectiveness of the proposed approach. The experimental results show that the proposed approach performs significantly better than a variety of evolutionary and nonevolutionary methods on most of the benchmark networks.

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

Bilevel metaheuristics have been widely used for bilevel optimization. However, recent studies have indicated that most bilevel metaheuristics are inefficient since they perform the lower-level optimization task for each upper-level solution independently and neglect the relationship among lower-level optimization tasks. In this article, we develop a bilevel metaheuristic with the collaborations among lower-level optimization tasks. Specifically, a population is evolved to solve the lower-level optimization tasks for all upper-level solutions collaboratively at each generation. In the population, each solution is associated with a lower-level optimization task. In such a way, all lower-level optimization tasks can be solved in a single run. To capture the individual features of different lower-level optimization tasks, we construct a lower-level search distribution for each lower-level optimization task based on all solutions in the population. In addition, an information-sharing mechanism is proposed to share good solutions among lower-level optimization tasks. Experiments on two sets of test problems and three practical applications demonstrate that our proposed algorithm performs better than other bilevel metaheuristics in comparison.

The objective reduction has been regarded as a basic issue in many-objective optimization. Existing objective reduction methods identify one set of essential objectives using an approximate nondominated front. However, if the Pareto front (PF) of a many-objective optimization problem (MaOP) is irregular, one single set of essential objectives may not be efficient for objective reduction. This article proposes to produce several different sets of essential objectives in objective reduction. More specifically, we use the Gaussian mixture model clustering to classify the obtained nondominated front into different subsets and perform objective reduction on each subset. Both an offline objective reduction method and an online objective reduction method are developed. The experimental results indicate that our proposed methods work well for MaOPs with degenerate or nondegenerate PFs.

We have recently proposed a framework of in vivo computation (IVC) which transforms the early tumor sensing problem into a computational problem. In the framework, a tumor-triggered biological gradient field (BGF) guides the swarm-intelligence-assisted targeting process, where externally manipulable and trackable magnetic nanorobots act as computational agents for the optimization procedure. As BGF can be viewed as an objective function which is utilized to define the fitness landscape for the agents, the inherent attributes of BGF are critical to the IVC process. All our previous investigations are based on the hypothesis that the BGF landscape remains time invariant during the tumor-targeting process, which results in a static function optimization problem. However, the properties of internal environment, such as the flow state of body fluid, will naturally lead to time-dependent variation of BGF, which means that the targeting process should be modeled as a dynamic function optimization problem. Based on this consideration, we focus on dynamic IVC by considering different variation patterns of BGF in this article. Two computational intelligence strategies named “swarm-based learning” and “individual-based learning” are proposed for dealing with the turbulence of the fitness estimation caused by the BGF variation. The in silico experiments and statistical results demonstrate the effectiveness of the proposed strategies. In addition, the above process is conducted in a 3-D search space, where the tumor vascular network is generated by an invasion percolation algorithm, which is more realistic compared to the 2-D search space in our previous works.

The implicit parallelism of a population in evolutionary algorithms (EAs) provides an ideal platform for dealing with multiple tasks simultaneously. However, little effort has been made to explore what information among different tasks can be used as valuable knowledge to help the optimization of different tasks. This article proposes a multiobjective multitask optimization (MO-MTO) EA based on decomposition with dual neighborhoods (MTEA/D-DN), in which the neighborhood is used as a bridge to achieve knowledge transfer among different tasks. In MTEA/D-DN, each subproblem not only maintains a neighborhood (internal neighborhood) within its own task based on the Euclidean distance between weight vectors but also keeps a neighborhood (external neighborhood) with the subproblems of other tasks via gray relation analysis in order to mine valuable information and communicate among tasks. The experimental studies show that our proposed algorithm outperforms five other state-of-the-art algorithms on a set of benchmark test instances and a real-world problem in steel plant.

Most current data is multivariable, exploring and identifying valuable information in these datasets has far-reaching impacts. In particular, discovering meaningful hidden association patterns in multivariate plays an important role. Plenty of measures for multivariate association have been proposed, yet it is still an open research challenge for effectively capturing association patterns among three or more variables, especially the scenario without any prior knowledge about those relationships. To do so, we desire a distribution-free, association type-independent and non-parametrical measure. For practical applications, such a measure should comparable, interpretable,scalable, intuitive, reliability, and robust. However, no exiting measures fulfill all of these desiderata. In this paper, taking advantage of the neighborhood information of a sample, we propose MNA, a maximal neighborhood multivariate association measure that satisfies all the above criteria. Extensive experiments on synthetic and real data show it outperforms state-of-the-art multivariate association measures.

We have recently proposed a novel framework of in vivo computation by transforming the early tumor detection into an optimization problem. In the framework, the tumor-triggered biological gradient field (BGF) provides aided knowledge for the swarm-intelligence-assisted tumor targeting process. Our previous investigations are based on the hypothesis that the BGF landscape is time-invariant, which results in a static function optimization problem. However, the properties of internal environment, such as the flow state of body fluid, will bring about time-dependent variation of BGF. Thus, we focus on dynamic in vivo computation by considering different variation patterns of BGF in this paper. A computational intelligence strategy named “swarm-based learning strategy” is proposed for overcoming the turbulence of the fitness estimation caused by the BGF variation. The in silico experiments and statistical results demonstrate the effectiveness of the proposed strategy. In addition, the above process is conducted in a three-dimensional search space, which is more realistic compared to the two-dimensional search space in our previous work.

The design of effective features enabling the development of automated landscape-aware techniques requires to address a number of inter-dependent issues. In this paper, we are interested in contrasting the amount of budget devoted to the computation of features with respect to: (i) the effectiveness of the features in grasping the characteristics of the landscape, and (ii) the gain in accuracy when solving an unknown problem instance by means of a feature-informed automated algorithm selection approach. We consider multi-objective combinatorial landscapes where, to the best of our knowledge, no in depth investigations have been conducted so far. We study simple cost-adjustable sampling strategies for extracting different state-of-the-art features. Based on extensive experiments, we report a comprehensive analysis on the impact of sampling on landscape feature values, and the subsequent automated algorithm selection task. In particular, we identify different global trends of feature values leading to non-trivial cost-vs-accuracy trade-off(s). Besides, we provide evidence that the sampling strategy can improve the prediction accuracy of automated algorithm selection. Interestingly, this holds independently of whether the sampling cost is taken into account or not in the overall solving budget.

Expensive multi-objective optimization problems can be found in many real-world applications, where their objective function evaluations involve expensive computations or physical experiments. It is desirable to obtain an approximate Pareto front with a limited evaluation budget. Multi-objective Bayesian optimization (MOBO) has been widely used for finding a finite set of Pareto optimal solutions. However, it is well-known that the whole Pareto set is on a continuous manifold and can contain infinite solutions. The structural properties of the Pareto set are not well exploited in existing MOBO methods, and the finite-set approximation may not contain the most preferred solution(s) for decision-makers. This paper develops a novel learning-based method to approximate the whole Pareto set for MOBO, which generalizes the decomposition-based multi-objective optimization algorithm (MOEA/D) from finite populations to models. We design a simple and powerful acquisition search method based on the learned Pareto set, which naturally supports batch evaluation. In addition, with our proposed model, decision-makers can readily explore any trade-off area in the approximate Pareto set for flexible decision-making. This work represents the first attempt to model the Pareto set for expensive multi-objective optimization. Experimental results on different synthetic and real-world problems demonstrate the effectiveness of our proposed method.

Symmetric nonnegative matrix factorization (SNMF) has demonstrated to be a powerful method for data clustering. However, SNMF is mathematically formulated as a non-convex optimization problem, making it sensitive to the initialization of variables. Inspired by ensemble clustering that aims to seek a better clustering result from a set of clustering results, we propose self-supervised SNMF (S3NMF), which is capable of boosting clustering performance progressively by taking advantage of the sensitivity to initialization characteristic of SNMF, without relying on any additional information. Specifically, we first perform SNMF repeatedly with a random positive matrix for initialization each time, leading to multiple decomposed matrices. Then, we rank the quality of the resulting matrices with adaptively learned weights, from which a new similarity matrix that is expected to be more discriminative is reconstructed for SNMF again. These two steps are iterated until the stopping criterion/maximum number of iterations is achieved. We mathematically formulate S3NMF as a constrained optimization problem, and provide an alternative optimization algorithm to solve it with the theoretical convergence guaranteed. Extensive experimental results on 10 commonly used benchmark datasets demonstrate the significant advantage of our S3NMF over 14 state-of-the-art methods in terms of 5 quantitative metrics. The source code is publicly available athttps://github.com/jyh-learning/SSSNMF.

This paper explores the problem of recovering the discriminative representation of a hyperspectral remote sensing image (HRSI), which suffers from spectral variations, to boost its classification accuracy. To tackle this challenge, we propose a new method, namely local-global balanced low-rank approximation (GLB-LRA), which can increase the similarity between pixels belonging to an identical category while promoting the discriminability between pixels of different categories. Specifically, by taking advantage of the particular structural spatial information of HRSIs, we exploit the low-rankness of an HRSI robustly in both spatial and spectral domains from the perspective of local and global balance. We mathematically formulate GLB-LRA as an explicit optimization problem and propose an iterative algorithm to solve it efficiently. Experimental results over three commonly-used benchmark datasets demonstrate the significant superiority of our method over state-of-the-art methods.

In this paper, we propose a new semi-supervised graph construction method, which is capable of adaptively learning the similarity relationship between data samples by fully exploiting the potential of pairwise constraints, a kind of weakly supervisory information. Specifically, to adaptively learn the similarity relationship, we linearly approximate each sample with others under the regularization of the low-rankness of the matrix formed by the approximation coefficient vectors of all the samples. In the meanwhile, by taking advantage of the underlying local geometric structure of data samples that is empirically obtained, we enhance the dissimilarity information of the available pairwise constraints via propagation. We seamlessly combine the two adversarial learning processes to achieve mutual guidance. We cast our method as a constrained optimization problem and provide an efficient alternating iterative algorithm to solve it. Experimental results on five commonly-used benchmark datasets demonstrate that our method produces much higher classification accuracy than state-of-the-art methods, while running faster.

Deep subspace clustering networks have attracted much attention in subspace clustering, in which an auto-encoder non-linearly maps the input data into a latent space, and a fully connected layer named self-expressiveness module is introduced to learn the affinity matrix via a typical regularization term (e.g., sparse or low-rank). However, the adopted regularization terms ignore the connectivity within each subspace, limiting their clustering performance. In addition, the adopted framework suffers from the coupling issue between the auto-encoder module and the self-expressiveness module, making the network training non-trivial. To tackle these two issues, we propose a novel deep subspace clustering method named Maximum Entropy Subspace Clustering Network (MESC-Net). Specifically, MESC-Net maximizes the entropy of the affinity matrix to promote the connectivity within each subspace, in which its elements corresponding to the same subspace are uniformly and densely distributed. Meanwhile, we design a novel framework to explicitly decouple the auto-encoder module and the self-expressiveness module. Besides, we also theoretically prove that the learned affinity matrix satisfies the block-diagonal property under the assumption of independent subspaces. Extensive quantitative and qualitative results on commonly used benchmark datasets validate MESC-Net significantly outperforms state-of-the-art methods. The code is publicly available athttps://github.com/ZhihaoPENG-CityU/MESC.

This article explores the problem of semisupervised affinity matrix learning, that is, learning an affinity matrix of data samples under the supervision of a small number of pairwise constraints (PCs). By observing that both the matrix encoding PCs, called pairwise constraint matrix (PCM) and the empirically constructed affinity matrix (EAM), express the similarity between samples, we assume that both of them are generated from a latent affinity matrix (LAM) that can depict the ideal pairwise relation between samples. Specifically, the PCM can be thought of as a partial observation of the LAM, while the EAM is a fully observed one but corrupted with noise/outliers. To this end, we innovatively cast the semisupervised affinity matrix learning as the recovery of the LAM guided by the PCM and EAM, which is technically formulated as a convex optimization problem. We also provide an efficient algorithm for solving the resulting model numerically. Extensive experiments on benchmark datasets demonstrate the significant superiority of our method over state-of-the-art ones when used for constrained clustering and dimensionality reduction. The code is publicly available at https://github.com/jyh-learning/LAM.

This article proposes a three-level radial basis function (TLRBF)-assisted optimization algorithm for expensive optimization. It consists of three search procedures at each iteration: 1) the global exploration search is to find a solution by optimizing a global RBF approximation function subject to a distance constraint in the whole search space; 2) the subregion search is to generate a solution by minimizing an RBF approximation function in a subregion determined by fuzzy clustering; and 3) the local exploitation search is to generate a solution by solving a local RBF approximation model in the neighborhood of the current best solution. Compared with some other state-of-the-art algorithms on five commonly used scalable benchmark problems, ten CEC2015 computationally expensive problems, and a real-world airfoil design optimization problem, our proposed algorithm performs well for expensive optimization.

Multiple-related tasks can be learned simultaneously by sharing information among tasks to avoid tabula rasa learning and to improve performance in the no transfer case (i.e., when each task learns in isolation). This study investigates multitask learning with conditional neural process (CNP) networks and proposes two multitask learning network models on the basis of CNPs, namely, the one-to-many multitask CNP (OMc-MTCNP) and the many-to-many MTCNP (MMc-MTCNP). Compared with existing multitask models, the proposed models add an extensible correlation learning layer to learn the correlation among tasks. Moreover, the proposed multitask CNP (MTCNP) networks are regarded as surrogate models and applied to a Bayesian optimization framework to replace the Gaussian process (GP) to avoid the complex covariance calculation. The proposed Bayesian optimization framework simultaneously infers multiple tasks by utilizing the possible dependencies among them to share knowledge across tasks. The proposed surrogate models augment the observed dataset with a number of related tasks to estimate model parameters confidently. The experimental studies under several scenarios indicate that the proposed algorithms are competitive in performance compared with GP-, single-task-, and other multitask model-based Bayesian optimization methods.

This article proposes a novel landscape smoothing method for the symmetric traveling salesman problem (TSP). We first define the homotopic convex (HC) transformation of a TSP as a convex combination of a well-constructed simple TSP and the original TSP. The simple TSP, called the convex-hull TSP, is constructed by transforming a known local or global optimum. We observe that controlled by the coefficient of the convex combination, with local or global optimum: 1) the landscape of the HC transformed TSP is smoothed in terms that its number of local optima is reduced compared to the original TSP and 2) the fitness distance correlation of the HC transformed TSP is increased. Furthermore, we observe that the smoothing effect of the HC transformation depends highly on the quality of the used optimum. A high-quality optimum leads to a better smoothing effect than a low-quality optimum. We then propose an iterative algorithmic framework in which the proposed HC transformation is combined within a heuristic TSP solver. It works as an escaping scheme from local optima aiming to improve the global searchability of the combined heuristic. Case studies using the 3-Opt and the Lin-Kernighan local search as the heuristic solver show that the resultant algorithms significantly outperform their counterparts and two other smoothing-based TSP heuristic solvers on most of the test instances with up to 20 000 cities.

In this article, we first propose a graph neural network encoding method for the multiobjective evolutionary algorithm (MOEA) to handle the community detection problem in complex attribute networks. In the graph neural network encoding method, each edge in an attribute network is associated with a continuous variable. Through nonlinear transformation, a continuous valued vector (i.e., a concatenation of the continuous variables associated with the edges) is transferred to a discrete valued community grouping solution. Further, two objective functions for the single-attribute and multiattribute network are proposed to evaluate the attribute homogeneity of the nodes in communities, respectively. Based on the new encoding method and the two objectives, a MOEA based upon NSGA-II, called continuous encoding MOEA, is developed for the transformed community detection problem with continuous decision variables. Experimental results on single-attribute and multiattribute networks with different types show that the developed algorithm performs significantly better than some well-known evolutionary- and nonevolutionary-based algorithms. The fitness landscape analysis verifies that the transformed community detection problems have smoother landscapes than those of the original problems, which justifies the effectiveness of the proposed graph neural network encoding method.

This work is geared toward a real-world manufacturing planning (MP) task, whose two objectives are to maximize the order fulfillment rate and minimize the total cost. More important, the requirements and constraints in real manufacturing make the MP task very challenging in several aspects. For example, the MP needs to cover many production components of multiple plants over a 30-day horizon, which means that it involves a large number of decision variables. Furthermore, the MP task's two objectives have extremely different magnitudes, and some constraints are difficult to handle. Facing these uncompromising practical requirements, we introduce an interactive multiobjective optimization-based MP system in this article. It can help the decision maker reach a satisfactory tradeoff between the two objectives without consuming massive calculations. In the MP system, the submitted MP task is modeled as a multiobjective integer programming (MOIP) problem. Then, the MOIP problem is addressed via a two-stage multiobjective optimization algorithm (TSMOA). To alleviate the heavy calculation burden, TSMOA transforms the optimization of the MOIP problem into the optimization of a series of single-objective problems (SOPs). Meanwhile, a new SOP solving strategy is used in the MP system to further reduce the computational cost. It utilizes two sequential easier SOPs as the approximator of the original complex SOP for optimization. As part of the MP system, TSMOA and the SOP solving strategy are demonstrated to be efficient in real-world MP applications. In addition, the effectiveness of TSMOA is also validated on benchmark problems. The results indicate that TSMOA as well as the MP system are promising.

It is very difficult to locate multiple global optimal solutions (GOSs) of multimodal optimization problems (MMOPs). To deal with this issue, a penalty-based multimodal optimization differential evolution (DE), called PMODE, is developed in this article. In PMODE, a penalty strategy with a dynamic penalty radius is constructed to solve MMOPs. An elite selection mechanism is designed to identify and select elite solutions. The neighboring areas of these elite solutions are penalized. PMODE uses a popular DE variant-JADE as its search engine. The proposed PMODE is compared with several other state-of-the-art multimodal optimization algorithms on 20 MMOPs used in the IEEE CEC2013 special session. The experimental results show that PMODE performs better than other state-of-the-art methods.

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

This article introduces a special multitasking optimization problem (MTOP) called the competitive MTOP (CMTOP). Its distinctive characteristics are that all tasks’ objectives are comparable, and its optimal solution is the best one among the optimal solutions of all the individual problems. This article proposes an evolutionary algorithm with an online resource allocation strategy and an adaptive information transfer mechanism to solve the CMTOP. The experimental results on benchmark and real-world problems show that our proposed algorithm is effective and efficient.

Building change detection (BCD) for very-high-spatial-resolution (VHR) remote sensing images is very important and challenging in the field of remote sensing, as the building is one of the most significant and valuable man-made ground targets. This article proposes a local–global pyramid network (LGPNet) that combines a local feature pyramid module (LFPM) and a global spatial pyramid module (GSPM) for various building feature extraction. The LFPM is constructed using the convolutional kernel with three different pyramid scales, and then, the local pyramid features are obtained by adding features of each scale. In the GSPM, the global spatial pyramid features are extracted by adaptive average pooling to acquire global contextual information from different fields of view on deep features. The LFPM and the GSPM work in a parallel and complementary manner to capture discriminative features of various buildings. In addition to the LFPM and the GSPM, the proposed LGPNet also employs two general attention mechanisms, i.e., the position attention module and the channel attention module, which can select and emphasize adaptively some building features with high semantic responses. Besides, in order to mitigate the influence of other ground targets to a certain extent, a cross-task transfer learning strategy is introduced to make the LGPNet focus on the building, which significantly improves the performance of our method. Extensive experiments on two public available BCD datasets show that the proposed LGPNet can achieve significant improvement compared with eight other state-of-the-art methods. The source code and the pretrained model will be released athttps://github.com/TongfeiLiu/LGPNet.

Crowd counting is critical for numerous video surveillance scenarios. One of the main issues in this task is how to handle the dramatic scale variations of pedestrians caused by the perspective effect. To address this issue, this paper proposes a novel convolution neural network-based crowd counting method, termed Perspective-guided Fractional-Dilation Network (PFDNet). By modeling the continuous scale variations, the proposed PFDNet is able to select the proper fractional-dilation kernels for adapting to different spatial locations. It significantly improves the flexibility of the state-of-the-arts that only consider the discrete representative scales. In addition, by avoiding the multi-scale or multi-column architecture that used in other methods, it is computationally more efficient. In practice, the proposed PFDNet is constructed by stacking multiple Perspective-guided Fractional-Dilation Convolutions (PFC) on a VGG16-BN backbone. By introducing a novel generalized dilation convolution operation, the PFC can handle fractional dilation ratios in the spatial domain under the guidance of perspective annotations, achieving continuous scales modeling of pedestrians. To deal with the problem of unavailable perspective information in some cases, we further introduce an effective perspective estimation branch to the proposed PFDNet, which can be trained in either supervised or weakly-supervised setting once the branch has been pre-trained. Extensive experiments show that the proposed PFDNet outperforms state-of-the-art methods on ShanghaiTech A, ShanghaiTech B, WorldExpo’10, UCF-QNRF, UCF_CC_50 and TRANCOS dataset, achieving MAE 53.8, 6.5, 6.8, 84.3205.8, and 3.06 respectively.

In this article, we consider the dynamic allocation of bursty requests stochastically arriving at heterogeneous servers with uncertain setup times. Lower expected response time and less power consumption are desirable objectives of users and service providers respectively. However, sudden increase and decrease of cloud servers caused by bursty requests are rather challenging to get an appropriate trade-off between the two conflicting objectives which are closely related to the launched servers. The heterogeneity of the cloud servers further makes it more difficult to decide how to switch on and off servers and effectively and efficiently allocate bursty requests with balanced objectives. Based on a Markov decision process, a real-time bilevel decision-making model is constructed for unallocated requests which includes: whether to launch a server and which type of server to launch. A learn-and-deploy algorithm framework is proposed which contains two complementary stages. In the first stage, an effective offline bi-objective optimization algorithm is proposed to learn a set of policies, which provides helpful trade-off information for a decision-maker to choose a preferred policya posteriori. In terms of the system status, a policy decides whether to launch a server according to a state-action table and which server to launch using a server priority sequence. In the second stage, a computationally efficient policy deployment method is proposed to search the corresponding action in the selected policy based on the current system status and apply it to the real-time system. Experimental studies over a large number of random and real instances have been conducted to validate the effectiveness of the proposed bilevel model and algorithm. Compared to the most recent existing method, the performance of the proposed approach can at most achieve an 80% improvement on power consumption and 20% improvement on response time.

Optimization modeling of real-world application problems usually involves noise from various sources. Noisy optimization imposes challenges to optimization methods since the objective values can be different for multiple evaluations. In this article, we propose a novel online population size learning (OPL) technique of evolution strategies for handling noisy optimization problems. By re-evaluating a fraction of the candidates, we measure the strength of noise level of the re-evaluated candidate solutions and adapt the population size according to the noise level. The proposed OPL combines the advantages of both explicit averaging by re-evaluations and the implicit averaging by large population size and overcomes their limitations. We incorporate it with the covariance matrix adaptation evolution strategy (CMA-ES) and obtain OPL-CMA-ES. Compared with the existing noise handling technique, the proposed OPL is much simpler in both concepts and computation. We conduct comprehensive experiments to evaluate the algorithm’s performance on standard problems with Gaussian noise. We further evaluate the performance of OPL-CMA-ES on the black-box optimization benchmarks (BBOBs) noisy testbed, which is a standard platform for comparing black-box optimization algorithms, compared with the state-of-the-art noise-handling algorithms. The experimental results show that OPL-CMA-ES achieves remarkable performance and outperforms the compared variants.

Convergence, diversity and feasibility are three important issues when solving constrained multiobjective optimization problems (CMOPs). To deal with the balance among convergence, diversity and feasibility well, this article proposes a cooperative multiobjective evolutionary algorithm with propulsive population (CMOEA-PP) for solving CMOPs. CMOEA-PP has two populations, including propulsive population and normal population, and these two populations work cooperatively. Specifically, propulsive population focuses on convergence. Normal population gives priority to feasibility and is obligated to maintain diversity. To cross through the infeasible region and reach the Pareto front (PF), propulsive population does not consider constraints in the early stage and only considers constraints in the later stage. To further accelerate the speed of convergence, propulsive population only searches for corner solutions and center solutions, while normal population searches for the whole PF. As a result, propulsive population can cross through the infeasible region because of the lack of attention to feasibility. In addition, propulsive population also can guide and accelerate the convergence of the evolutionary process. Comprehensive experiment results on several sets of benchmark problems demonstrate that CMOEA-PP is better than existing state-of-the-art competitors.

This paper explores the problem of clustering ensemble, which aims to combine multiple base clusterings to produce better performance than that of the individual one. The existing clustering ensemble methods generally construct a co-association matrix, which indicates the pairwise similarity between samples, as the weighted linear combination of the connective matrices from different base clusterings, and the resulting co-association matrix is then adopted as the input of an off-the-shelf clustering algorithm, e.g., spectral clustering. However, the co-association matrix may be dominated by poor base clusterings, resulting in inferior performance. In this paper, we propose a novel low-rank tensor approximation based method to solve the problem from a global perspective. Specifically, by inspecting whether two samples are clustered to an identical cluster under different base clusterings, we derive a coherent-link matrix, which contains limited but highly reliable relationships between samples. We then stack the coherent-link matrix and the co-association matrix to form a three-dimensional tensor, the low-rankness property of which is further explored to propagate the information of the coherent-link matrix to the co-association matrix, producing a refined co-association matrix. We formulate the proposed method as a convex constrained optimization problem and solve it efficiently. Experimental results over 7 benchmark data sets show that the proposed model achieves a breakthrough in clustering performance, compared with 12 state-of-the-art methods. To the best of our knowledge, this is the first work to explore the potential of low-rank tensor on clustering ensemble, which is fundamentally different from previous approaches. Last but not least, our method only contains one parameter, which can be easily tuned.

This paper investigates the problem of reconstructing hyperspectral (HS) images from single RGB images captured by commercial cameras, without using paired HS and RGB images during training. To tackle this challenge, we propose a new lightweight and end-to-end learning-based framework. Specifically, on the basis of the intrinsic imaging degradation model of RGB images from HS images, we progressively spread the differences between input RGB images and re-projected RGB images from recovered HS images via effective unsupervised camera spectral response function estimation. To enable the learning without paired ground-truth HS images as supervision, we adopt the adversarial learning manner and boost it with a simple yet effective ℒ1gradient clipping scheme. Besides, we embed the semantic information of input RGB images to locally regularize the unsupervised learning, which is expected to promote pixels with identical semantics to have consistent spectral signatures. In addition to conducting quantitative experiments over two widely-used datasets for HS image reconstruction from synthetic RGB images, we also evaluate our method by applying recovered HS images from real RGB images to HS-based visual tracking. Extensive results show that our method significantly outperforms state-of-the-art unsupervised methods and even exceeds the latest supervised method under some settings. The source code is public available at https://github.com/zbzhzhy/Unsupervised-Spectral-Reconstruction.

An objective normalization strategy is essential in any evolutionary multiobjective or many-objective optimization (EMO or EMaO) algorithm, due to the distance calculations between objective vectors required to compute diversity and convergence of population members. For the decomposition-based EMO/EMaO algorithms involving the Penalty Boundary Intersection (PBI) metric, normalization is an important matter due to the computation of two distance metrics. In this article, we make a theoretical analysis of the effect of instabilities in the normalization process on the performance of PBI-based MOEA/D and a proposed PBI-based NSGA-III procedure. Although the effect is well recognized in the literature, few theoretical studies have been done so far to understand its true nature and the choice of a suitable penalty parameter value for an arbitrary problem. The developed theoretical results have been corroborated with extensive experimental results on three to 15-objective convex and non-convex instances of DTLZ and WFG problems. The article, makes important theoretical conclusions on PBI-based decomposition algorithms derived from the study.

This paper explores the problem of multi-view spectral clustering (MVSC) based on tensor low-rank modeling. Unlike the existing methods that all adopt an off-the-shelf tensor low-rank norm without considering the special characteristics of the tensor in MVSC, we design a novel structured tensor low-rank norm tailored to MVSC. Specifically, we explicitly impose a symmetric low-rank constraint and a structured sparse low-rank constraint on the frontal and horizontal slices of the tensor to characterize the intra-view and inter-view relationships, respectively. Moreover, the two constraints could be jointly optimized to achieve mutual refinement. On basis of the novel tensor low-rank norm, we formulate MVSC as a convex low-rank tensor recovery problem, which is then efficiently solved with an augmented Lagrange multiplier-based method iteratively. Extensive experimental results on seven commonly used benchmark datasets show that the proposed method outperforms state-of-the-art methods to a significant extent. Impressively, our method is able to produce perfect clustering. In addition, the parameters of our method can be easily tuned, and the proposed model is robust to different datasets, demonstrating its potential in practice. The code is available athttps://github.com/jyh-learning/MVSC-TLRR.

The decomposition-based algorithms [e.g., multiobjective evolutionary algorithm based on decomposition (MOEA/D)] transform a multiobjective optimization problem (MOP) into a number of single-objective optimization subproblems and solve them in a collaborative manner. It is a natural framework for using single-objective local search (LS) to solve combinatorial MOPs. However, commonly used decomposition methods, such as weighted sum (WS), Tchebycheff (TCH), and penalty-based boundary intersection (PBI) may not be good at maintaining the population diversity while providing diverse initial solutions for different LS procedures in a collaborative way. Based on our previous work on the constrained decomposition with grids (CDG), this article proposes a dynamic CDG (DCDG) framework used to design a multiobjective memetic algorithm (DCDG-MOMA). DCDG uses grids for maintaining diversity, supporting the collaborative LS. In addition, DCDG dynamically increases the number of grids for obtaining more nondominated solutions as well as the better collaborative search among them. DCDG-MOMA has been compared with several classical and state-of-the-art algorithms on multiobjective traveling salesman problem (MOTSP), multiobjective quadratic assignment problem (MOQAP), and multiobjective capacitated arc routing problem (MOCARP).

Batch-processing machines (BPMs) can process a number of jobs at a time, which can be found in many industrial systems. This article considers a single BPM scheduling problem with unequal release times and job sizes. The goal is to assign jobs into batches without breaking the machine capacity constraint and then sort the batches to minimize the makespan. A self-adaptive differential evolution algorithm is developed for addressing the problem. In our proposed algorithm, mutation operators are adaptively chosen based on their historical performances. Also, control parameter values are adaptively determined based on their historical performances. Our proposed algorithm is compared to CPLEX, existing metaheuristics for this problem and conventional differential evolution algorithms through comprehensive experiments. The experimental results demonstrate that our proposed self-adaptive algorithm is more effective than other algorithms for this scheduling problem.

Facility layout problems (FLPs) in hospitals are typically to arrange facilities or rooms along both sides of a corridor to minimize some objectives. In a hospital, very often there are center-islands to decrease the flow cost among facilities or rooms. However, these islands have not been considered before. In this article, we propose an FLP with center-islands that involves two parallel rows and center-islands. A mixed-integer program formulation is established for modeling it. A methodology for combining a multiobjective evolutionary algorithm based on decomposition (MOEA/D) and linear program is proposed to solve this problem. MOEA/D optimizes the sequence of facilities on two rows and center-islands while the linear program is embedded into MOEA/D to optimize the exact locations of center-islands. A tabu search with a local search is also integrated into MOEA/D to enhance its search capability. Experiments show that our proposed methodology can effectively solve the problem.

This article proposes an evolutionary algorithm using multiple penalties and multiple local surrogates (MPMLS) for expensive constrained optimization. In each generation, MPMLS defines and optimizes a number of subproblems. Each subproblem penalizes the constraints in the original problem using a different penalty coefficient and has its own search subregion. A local surrogate is built for optimizing each subproblem. Two major advantages of MPMLS are: 1) it can maintain good population diversity so that the search can approach the optimal solution of the original problem from different directions and 2) it only needs to build local surrogates so that the computational overhead of the model building can be reduced. Numerical experiments demonstrate that our proposed algorithm performs much better than some other state-of-the-art evolutionary algorithms.

Feature extraction is a critical issue in many machine learning systems. A number of basic fusion operators have been proposed and studied. This article proposes an evolutionary algorithm, called evolutionary deep fusion method, for searching an optimal combination scheme of different basic fusion operators to fuse multiview features. We apply our proposed method to chemical structure recognition. Our proposed method can directly take images as inputs, and users do not need to transform images to other formats. The experimental results demonstrate that our proposed method can achieve a better performance than those designed by human experts on this real-life problem.

This article investigates the properties of ratio and difference-based indicators under the Minkovsky distance and demonstrates that a ratio-based indicator with infinite norm is the best for solution evaluation among these indicators. Accordingly, a promising-region-based evolutionary many-objective algorithm with the ratio-based indicator is proposed. In our proposed algorithm, a promising region is identified in the objective space using the ratio-based indicator with infinite norm. Since the individuals outside the promising region are of poor quality, we can discard these solutions from the current population. To ensure the diversity of population, a strategy based on the parallel distance is introduced to select individuals in the promising region. In this strategy, all individuals in the promising region are projected vertically onto the normal plane so that crowded distances between them can be calculated. Afterward, two solutions with a smaller distance are selected from the candidate solutions each time, and the solution with the smaller indicator fitness value is removed from the current population. Empirical studies on various benchmark problems with 3-20 objectives show that the proposed algorithm performs competitively on all test problems. Compared with a number of other state-of-the-art evolutionary algorithms, the proposed algorithm is more robust on these problems with various Pareto fronts.

A two-phase evolutionary algorithm is developed to find multiple solutions of a nonlinear equations system. It transforms a nonlinear equations system into a multimodal optimization problem. In phase one of the proposed algorithm, a strategy combines a multiobjective optimization technique and a niching technique to maintain the population diversity. Phase two consists of a detection method and a local search method for encouraging the convergence. The detection method finds several promising subregions and the local search method locates the corresponding optimal solutions in each promising subregion. The experiments on a set of 30 nonlinear equation systems demonstrate that the proposed algorithm is better than other state-of-the-art algorithms.

Pareto dominance-based multiobjective optimization has been successfully applied to constrained evolutionary optimization during the last two decades. However, as another famous multiobjective optimization framework, decomposition-based multiobjective optimization has not received sufficient attention from constrained evolutionary optimization. In this paper, we make use of decomposition-based multiobjective optimization to solve constrained optimization problems (COPs). In our method, first of all, a COP is transformed into a biobjective optimization problem (BOP). Afterward, the transformed BOP is decomposed into a number of scalar optimization subproblems. After generating an offspring for each subproblem by differential evolution, the weighted sum method is utilized for selection. In addition, to make decomposition-based multiobjective optimization suit the characteristics of constrained evolutionary optimization, weight vectors are elaborately adjusted. Moreover, for some extremely complicated COPs, a restart strategy is introduced to help the population jump out of a local optimum in the infeasible region. Extensive experiments on three sets of benchmark test functions, namely, 24 test functions from IEEE CEC2006, 36 test functions from IEEE CEC2010, and 56 test functions from IEEE CEC2017, have demonstrated that the proposed method shows better or at least competitive performance against other state-of-the-art methods.

A challenge in engineering design optimization is that sufficient information may not be available to define the exact specifications beforehand. While iterative trial optimization using different specifications is widely used in industry, multiobjective optimization is attracting much attention in the academic field. However, off-the-shelf methods in both categories are time-consuming due to the involved computationally expensive simulations. In this paper, the characteristics of the targeted problem are summarized; the gap between off-the-shelf methods and the practical need is then analyzed. A simple yet effective framework, called two-stage multi-fidelity surrogate model-assisted optimization (TMSO), is proposed to improve efficiency. TSMO is implemented by two state-of-the-art optimization algorithms and two real-world design cases demonstrate its effectiveness in practice. The research topics in multiobjective optimization and surrogate model-assisted optimization inspired by the TSMO framework is finally discussed.

On the one hand, surrogate-assisted evolutionary algorithms are established as a method of choice for expensive black-box optimization problems. On the other hand, the growth in computing facilities has seen a massive increase in potential computational power, granted the users accommodate their approaches with the offered parallelism. While a number of studies acknowledge the impact of parallelism for single-objective expensive optimization assisted by surrogates, extending such techniques to the multi-objective setting has not yet been properly investigated, especially within the state-of-the-art decomposition framework. We first highlight the different degrees of parallelism in existing surrogate-assisted multi-objective evolutionary algorithms based on decomposition (S-MOEA/D). We then provide a comprehensive analysis of the key steps towards a successful parallel S-MOEA/D approach. Through an extensive benchmarking effort relying on the well-established bbob-biobj test functions, we analyze the performance of the different algorithm designs with respect to the problem dimensionality and difficulty, the amount of parallel cores available, and the supervised learning models considered. In particular, we show the difference in algorithm scalability based on the selected surrogate-assisted approaches, the performance impact of distributing the model training task and the efficacy of the designed parallel-surrogate methods.

We consider the design and analysis of surrogate-assisted algorithms for expensive multi-objective combinatorial optimization. Focusing on pseudo-boolean functions, we leverage existing techniques based on Walsh basis to operate under the decomposition framework of MOEA/D. We investigate two design components for the cheap generation of a promising pool of offspring and the actual selection of one solution for expensive evaluation. We propose different variants, ranging from a filtering approach that selects the most promising solution at each iteration by using the constructed Walsh surrogates to discriminate between a pool of offspring generated by variation, to a substitution approach that selects a solution to evaluate by optimizing the Walsh surrogates in a multi-objective manner. Considering bi-objective NK landscapes as benchmark problems offering different degree of non-linearity, we conduct a comprehensive empirical analysis including the properties of the achievable approximation sets, the anytime performance, and the impact of the order used to train the Walsh surrogates. Our empirical findings show that, although our surrogate-assisted design is effective, the optimal integration of Walsh models within a multi-objective evolutionary search process gives rise to particular questions for which different trade-off answers can be obtained.

Multiobjective evolutionary algorithms (MOEAs) have progressed significantly in recent decades, but most of them are designed to solve unconstrained multiobjective optimization problems. In fact, many real-world multiobjective problems contain a number of constraints. To promote research on constrained multiobjective optimization, we first propose a problem classification scheme with three primary types of difficulty, which reflect various types of challenges presented by real-world optimization problems, in order to characterize the constraint functions in constrained multiobjective optimization problems (CMOPs). These are feasibility-hardness, convergence-hardness, and diversity-hardness. We then develop a general toolkit to construct difficulty adjustable and scalable CMOPs (DAS-CMOPs, or DAS-CMaOPs when the number of objectives is greater than three) with three types of parameterized constraint functions developed to capture the three proposed types of difficulty. In fact, the combination of the three primary constraint functions with different parameters allows the construction of a large variety of CMOPs, with difficulty that can be defined by a triplet, with each of its parameters specifying the level of one of the types of primary difficulty. Furthermore, the number of objectives in this toolkit can be scaled beyond three. Based on this toolkit, we suggest nine difficulty adjustable and scalable CMOPs and nine CMaOPs, to be called DAS-CMOP1-9 and DAS-CMaOP1-9, respectively. To evaluate the proposed test problems, two popular CMOEAs-MOEA/D-CDP (MOEA/D with constraint dominance principle) and NSGA-II-CDP (NSGA-II with constraint dominance principle) and two popular constrained many-objective evolutionary algorithms (CMaOEAs)-C-MOEA/DD and C-NSGA-III-are used to compare performance on DAS-CMOP1-9 and DAS-CMaOP1-9 with a variety of difficulty triplets, respectively. The experimental results reveal that mechanisms in MOEA/D-CDP may be more effective in solving convergence-hard DAS-CMOPs, while mechanisms of NSGA-II-CDP may be more effective in solving DAS-CMOPs with simultaneous diversity-, feasibility-, and convergence-hardness. Mechanisms in C-NSGA-III may be more effective in solving feasibility-hard CMaOPs, while mechanisms of C-MOEA/DD may be more effective in solving CMaOPs with convergence-hardness. In addition, none of them can solve these problems efficiently, which stimulates us to continue to develop new CMOEAs and CMaOEAs to solve the suggested DAS-CMOPs and DAS-CMaOPs.

Covariance matrix adaptation evolution strategy (CMA-ES) is a successful gradient-free optimization algorithm. Yet, it can hardly scale to handle high-dimensional problems. In this paper, we propose a fast variant of CMA-ES (Fast CMA-ES) to handle large-scale black-box optimization problems. We approximate the covariance matrix by a low-rank matrix with a few vectors and use two of them to generate each new solution. The algorithm achieves linear internal complexity on the dimension of search space. We illustrate that the covariance matrix of the underlying distribution can be considered as an ensemble of simple models constructed by two vectors. We experimentally investigate the algorithm's behaviors and performances. It is more efficient than the CMA-ES in terms of running time. It outperforms or performs comparatively to the variant limited memory CMA-ES on large-scale problems. Finally, we evaluate the algorithm's performance with a restart strategy on the CEC'2010 large-scale global optimization benchmarks, and it shows remarkable performance and outperforms the large-scale variants of the CMA-ES.

Pareto local search (PLS) is a basic building block in many metaheuristics for a multiobjective combinatorial optimization problem. In this paper, an enhanced PLS variant called parallel PLS based on decomposition (PPLS/D) is proposed. PPLS/D improves the efficiency of PLS using the techniques of parallel computation and problem decomposition. It decomposes the original search space into L subregions and executes L parallel processes searching in these subregions simultaneously. Inside each subregion, the PPLS/D process is guided by a unique scalar objective function. PPLS/D differs from the well-known two phase PLS in that it uses the scalar objective function to guide every move of the PLS procedure in a fine-grained manner. In the experimental studies, PPLS/D is compared against the basic PLS and a recently proposed PLS variant on the multiobjective unconstrained binary quadratic programming problems and the multiobjective traveling salesman problems with, at most, four objectives. The experimental results show that regardless of whether the initial solutions are randomly generated or generated by heuristic methods, PPLS/D always performs significantly better than the other two PLS variants.

The decomposition-based evolutionary algorithm has become an increasingly popular choice for posterior multiobjective optimization. Facing the challenges of an increasing number of objectives, many techniques have been developed which help to balance the convergence and diversity. Nevertheless, according to a recent study by Ishibuchi et al., due to the predefined search directions toward the ideal point, their performance strongly depends on the Pareto front (PF) shapes, especially the orientation of the PFs. To balance the convergence and diversity for decomposition-based methods and to alleviate their performance dependence on the orientation of the PFs, this paper develops an adversarial decomposition method for many-objective optimization, which leverages the complementary characteristics of different subproblem formulations within a single paradigm. More specifically, two populations are co-evolved by two subproblem formulations with different contours and adversarial search directions. To avoid allocating redundant computational resources to the same region of the PF, the two populations are matched into one-to-one solution pairs according to their working regions upon the PF. Each solution pair can at most contribute one principal mating parent during the mating selection process. When comparing nine state-of-the-art many-objective optimizers, we have witnessed the competitive performance of our proposed algorithm on 130 many-objective test problems with various characteristics, including regular and inverted PFs.

The computation of hypervolume is a key issue in multiobjective optimization, particularly, multiobjective evolutionary optimization. However, it is NP-hard to compute the exact hypervolume value. Monte Carlo methods have been widely used for approximating the hypervolume. Observing that the basic Monte Carlo method and the fully polynomial-time randomized approximation scheme (FPRAS) suit different solution sets, we propose a combination of these two methods and show that it performs very well on a number of solution sets.

Overall constraint violation functions are commonly used in multiobjective evolutionary algorithms (MOEAs) for handling constraints. Constraints could cause these algorithms stuck in two stagnation states: 1) since the feasible region of a multiobjective optimization problem can consist of several disconnected feasible subregions, the search can be easily trapped in a feasible subregion which does not contain all the global Pareto optimal solutions and 2) an overall constraint violation function may have many nonzero minimal points, it can make the search stuck in an unfeasible area. To address these two issues, this article proposes a strategy to detect whether or not the search is stuck in these two stagnation states and then escape from them. Our proposed detect-and-escape strategy uses the feasible ratio and the change rate of overall constraint violation to detect stagnation, and adjusts the weight of the constraint violation for guiding the search to escape from stagnation states. We develop and implement a decomposition-based constrained MOEA with this strategy. Extensive experiments on a number of benchmark problems demonstrate the competitiveness of our proposed algorithm when compared to five other state-of-the-art constrained evolutionary algorithms.

For real-world engineering design optimizations, it is of great significance to find approximate optimal designs with least number of expensive functional evaluations. This paper proposes to use a surrogate-based multi-objective evolutionary algorithm (SBMO) to address this type of problems. The basic idea is to decompose a multi-objective optimization problem into a number of scalar optimization subproblems and to optimize them simultaneously in a simple-to-implement manner, in which global surrogate models are used to enable full cooperation between subproblems. First, initial samples are selected by design of experiments and expensive simulations are conducted to evaluate them. Second, global surrogate models for objective (and constraint) functions are built through the sampled data and the optimization subproblems are solved simultaneously to suggest new samples. Third, the surrogate models are updated and the optimization proceeds to the next generation. This process is repeated until satisfactory Pareto-front solutions are found. Thanks to decomposition strategy, the infill-sampling criteria and constraint handling dedicated for a single-objective optimization can be directly used in a SBMO. The difference between SBMO and the existing methods such as MOEA/D-EGO is that a combined infill-sampling strategy and dedicated constraint handling are used. Benchmark test cases have demonstrated that SBMO is efficient, robust and has good capability of constraint handling. SBMO has been applied to multi-objective aerodynamic shape optimization of a transonic airfoil. It has been shown that SBMO is well suited for engineering design problems where expensive numerical simulations are employed.

The surrogate-assisted optimization algorithms (SAOAs) are very promising for solving computationally expensive optimization problems (EOPs). Generally, the performance of a SAOA is determined by the quality of its surrogate model and the infill sampling criterion. In this paper, we propose a radial basis function (RBF) assisted optimization algorithm with batch infill sampling criterion for solving EOPs (short for RBFBS). In RBFBS, the quality of RBF model is adjusted by choosing a good shape parameter via solving a sub-expensive hyperparameter optimization problem. Moreover, a batch infill sampling criterion that includes a bi-objective-based sampling approach and a single-objective-based sampling approach is proposed to get a batch of samples for expensive evaluation. The experimental results on various benchmark problems show that RBFBS is very promising for expensive optimization.

In this paper, we propose a computationally efficient variant of elitist covariance matrix evolution strategy for continuous local search in high dimensional space. It focuses on searching in a low-dimensional subspace expanded by a small number of promising search directions. This leads to the linear internal computational complexity of each iteration, which enables the algorithm to scale to high dimensional problems. We conduct comprehensive experiments to evaluate the parameter sensitivity and the algorithm’s performance. The experimental results validate that the proposed algorithm reduces the running time by a factor of ten, and it can be easily scaled up to n>1000 on a set of commonly used test functions.

Decomposition-based constrained multiobjective evolutionary algorithms decompose a constrained multiobjective problem into a set of constrained single-objective subproblems. For each subproblem, the aggregation function and the overall constraint violation need to be minimized simultaneously, which however may conflict with each other during the evolutionary process. To solve this issue, this paper proposes a novel decomposition-based constrained multiobjective evolutionary algorithm with two types of weight vectors, respectively emphasizing convergence and diversity. The solutions associated to the convergence weight vectors are updated only considering the aggregation function in order to search the whole search space freely, while the ones associated to the diversity weight vectors are renewed by considering both the aggregation function and the overall constraint violation, which encourages to search around the feasible region found so far. Once the replacement of solutions does not happen for the diversity weight vectors in a period, the corresponding diversity weight vectors will be transferred to convergence one. Thereafter, all solutions will finally search around the feasible region, which helps to find more feasible or superior solutions. The proposed constraint handling technique can have a good balance to search the feasible and infeasible regions and show the promising performance, which is validated when tackling several constrained multi-objective problems.

Pairwise constraint propagation (PCP) aims to propagate a limited number of initial pairwise constraints (PCs, including must-link and cannot-link constraints) from the constrained data samples to the unconstrained ones to boost subsequent PC-based applications. The existing PCP approaches always suffer from the imbalance characteristic of PCs, which limits their performance significantly. To this end, we propose a novel imbalance-aware PCP method, by comprehensively and theoretically exploring the intrinsic structures of the underlying PCs. Specifically, different from the existing methods that adopt a single representation, we propose to use two separate carriers to represent the two types of links. And the propagation is driven by the structure embedded in data samples and the regularization of the local, global, and complementary structures of the two carries. Our method is elegantly cast as a well-posed constrained optimization model, which can be efficiently solved. Experimental results demonstrate that the proposed PCP method is capable of generating more high-fidelity PCs than the recent PCP algorithms. In addition, the augmented PCs by our method produce higher accuracy than state-of-the-art semi-supervised clustering methods when applied to constrained clustering. To the best of our knowledge, this is the first PCP method taking the imbalance property of PCs into account.

Multi-task learning is a powerful method for solving multiple correlated tasks simultaneously. However, it is often impossible to find one single solution to optimize all the tasks, since different tasks might conflict with each other. Recently, a novel method is proposed to find one single Pareto optimal solution with good trade-off among different tasks by casting multi-task learning as multiobjective optimization. In this paper, we generalize this idea and propose a novel Pareto multi-task learning algorithm (Pareto MTL) to find a set of well-distributed Pareto solutions which can represent different trade-offs among different tasks. The proposed algorithm first formulates a multi-task learning problem as a multiobjective optimization problem, and then decomposes the multiobjective optimization problem into a set of constrained subproblems with different trade-off preferences. By solving these subproblems in parallel, Pareto MTL can find a set of well-representative Pareto optimal solutions with different trade-off among all tasks. Practitioners can easily select their preferred solution from these Pareto solutions, or use different trade-off solutions for different situations. Experimental results confirm that the proposed algorithm can generate well-representative solutions and outperform some state-of-the-art algorithms on many multi-task learning applications.

Combinatorial multiobjective optimization problems (CMOPs) are very popular due to their widespread applications in the real world. One common method for CMOPs is Pareto local search (PLS), a natural extension of single-objective local search (LS). However, classical PLS tends to reserve all of the nondominated solutions for LS, which causes the inefficient LS, as well as unbearable computational and space cost. Due to the aforementioned reasons, most PLS approaches can only handle CMOPs with no more than two objectives. In this paper, by combining the Pareto dominance and weighted sum (WS) approach in a grid system, the grid weighted sum dominance (gws-dominance) is proposed and integrated into PLS for CMOPs with multiple objectives. In the grid system, at most one representative solution is maintained in each grid for more efficient LS, thus largely reducing the computational and space complexity. The grid-based WS approach can further guide the LS in different grids for maintaining more widely and uniformly distributed Pareto front approximations. In the experimental studies, the grid WS PLS is compared with the classical PLS, three decomposition-based LS approaches [multiobjective evolutionary algorithm based on decomposition-LS (WS, Tchebycheff, and penalty-based boundary intersection)], a grid-based algorithm ( ϵ -MOEA), and a state-of-the-art hybrid approach (multiobjective memetic algorithm based on decomposition) on two sets of benchmark CMOPs. The experimental results show that the grid weighted sum Pareto local search significantly outperforms the compared algorithms and remains effective and efficient on combinatorial multiobjective and even many-objective optimization problems.

This paper proposes a multiobjective multidepot vehicle routing problem with time windows and designs some real-world test instances. It develops a two-stage multiobjective evolutionary algorithm (TS-MOEA) for dealing with the problem. Stage I of our proposed algorithm focuses on finding extreme solutions, and forms a coarse Pareto front, while stage II extends the found extreme solutions for approximating the whole Pareto front. The two-stage strategy provides a new method to balance convergence and diversity. Moreover, a hybrid neighborhood structure is designed for solution improvement. Experimental result shows that TS-MOEA significantly outperforms two other representative algorithms.

The hypervolume and hypervolume contributions are widely used in multiobjective evolutionary optimization. However, their exact calculation is NP-hard. By definition, hypervolume is an m-D integral (where m is the number of objectives). Using polar coordinate, this paper transforms the hypervolume into an (m - 1)-D integral, and then proposes two approximation methods for computing the hypervolume and hypervolume contributions. Numerical experiments have been conducted to investigate the performance of our proposed methods.

Decomposition-based many-objective evolutionary algorithms generally decompose the objective space into multiple subregions with the help of a set of reference vectors. The resulting subregions are fixed since the reference vectors are usually predefined. When the optimization problem has a complicated Pareto front (PF), this decomposition may decrease the algorithm performance. To deal with this problem, this paper proposes a dynamical decomposition strategy. Instead of using predefined reference vectors, solution themselves are used as reference vectors. Thus, they are adapted to the shape of PF automatically. Besides, the subregions are produced one by one through successively bipartitioning the objective space. The resulting subregions are not fixed but dynamically determined by the population solutions as well as the subregions produced previously. Based on this strategy, a solution ranking method, named dynamical-decomposition-based ranking method (DDR), is proposed which can be employed in the mating selection and environmental selection in commonly used algorithm frameworks. Compared with those in the other decomposition-based algorithms, DDR has the following properties: 1) no predefined reference vectors are required; 2) less parameters are involved; and 3) the ranking results can not only be utilized directly to select solutions but also serve as a secondary criterion in traditional Pareto-based algorithms. In this paper, DDR is equipped in two algorithm frameworks for handling many-objective optimization problems. Comparisons with five state-of-the-art algorithms on 31 widely used test problems are carried out to test the performance of the proposed approach. The experimental results have shown the effectiveness of the proposed approach in keeping a good tradeoff between convergence and diversity.

Optimization problems with variable-length decision space are a class of challenging optimization problems derived from some real-world applications, such as the composite laminate stacking problem and the sensor coverage problem. Unlike other optimization problems, the solutions in these problems might be represented as the vectors with different variable size (i.e., dimensionality). So far, some research efforts have been done on the use of evolutionary algorithms (EAs) for solving single objective variable-length optimization problems. In fact, the variable-length problem difficulty can also exist in multiobjective optimization. However, such challenging problems have not yet gained much attention in the area of evolutionary multiobjective optimization. To facilitate the research on the variable-length Pareto optimization, we first suggest a systematic toolkit for constructing benchmark multiobjective test problems with variable-length feature in this paper. Then, we also propose a variable-length multiobjective EA based on a two-level decomposition strategy, which decomposes a multiobjective optimization problem in terms of the penalty boundary intersection search directions and the dimensionality of variables. The performance of our proposed algorithm and the other three state-of-the-art algorithms on these problems are compared. To further show the effectiveness of our proposed algorithm, some experimental results on a bi-objective laminate stacking optimization problem are also reported and analyzed.

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

Combining machine learning techniques has shown great potentials in evolutionary optimization since the domain knowledge of an optimization problem, if well learned, can be a great help for creating high-quality solutions. However, existing learning-based multiobjective evolutionary algorithms (MOEAs) spend too much computational overhead on learning. To address this problem, we propose a learning-based MOEA where an online learning algorithm is embedded within the evolutionary search procedure. The online learning algorithm takes the stream of sequentially generated solutions along the evolution as its training data. It is noted that the stream of solutions are temporal, dependent, nonstationary, and nonstatic. These data characteristics make existing online learning algorithm not suitable for the evolution data. We hence modify an existing online agglomerative clustering algorithm to accommodate these characteristics. The modified online clustering algorithm is applied to adaptively discover the structure of the Pareto optimal set; and the learned structure is used to guide new solution creation. Experimental results have shown significant improvement over four state-of-the-art MOEAs on a variety of benchmark problems.

In some real-world applications, it has been found that the performance of multiobjective optimization evolutionary algorithms (MOEAs) may deteriorate when boundary solutions in the Pareto front (PF) are more difficult to approximate than others. Such a problem feature, referred to as difficult-to-approximate (DtA) PF boundaries, is seldom considered in existing multiobjective optimization test problems. To fill this gap and facilitate possible systematic studies, we introduce a new test problem generator. The proposed generator enables the design of test problems with controllable difficulties regarding the feature of DtA PF boundaries. Three representative MOEAs, NSGA-II, SMS-EMOA, and MOEA/D-DRA, are performed on a series of test problems created using the proposed generator. Experimental results indicate that all the three algorithms perform poorly on the new test problems. Meanwhile, a modified variant of MOEA/D-DRA, denoted as MOEA/D-DRA-UT, is validated to be more effective in dealing with these problems. Subsequently, it is concluded that the rational allocation of computational resources between different PF parts is crucial for MOEAs to handle the problems with DtA PF boundaries.

This paper proposes an effective ensemble framework (EF) for tackling multiobjective optimization problems, by combining the advantages of various evolutionary operators and selection criteria that are run on multiple populations. A simple ensemble algorithm is realized as a prototype to demonstrate our proposed framework. Two mechanisms, namely competition and cooperation, are employed to drive the running of the ensembles. Competition is designed by adaptively running different evolutionary operators on multiple populations. The operator that better fits the problem’s characteristics will receive more computational resources, being rewarded by a decomposition-based credit assignment strategy. Cooperation is achieved by a cooperative selection of the offspring generated by different populations. In this way, the promising offspring from one population have chances to migrate into the other populations to enhance their convergence or diversity. Moreover, the population update information is further exploited to build an evolutionary potentiality model, which is used to guide the evolutionary process. Our experimental results show the superior performance of our proposed ensemble algorithms in solving most cases of a set of 31 test problems, which corroborates the advantages of our EF.

The decomposition-based evolutionary multiobjective optimization (EMO) algorithm has become an increasingly popular choice for a posteriori multiobjective optimization. However, recent studies have shown that their performance strongly depends on the Pareto front (PF) shapes. This can be attributed to the decomposition method, of which the reference points and subproblem formulation settings are not well adaptable to various problem characteristics. In this paper, we develop a learning-to-decompose (LTD) paradigm that adaptively sets the decomposition method by learning the characteristics of the estimated PF. Specifically, it consists of two interdependent parts, i.e., a learning module and an optimization module. Given the current nondominated solutions from the optimization module, the learning module periodically learns an analytical model of the estimated PF. Thereafter, useful information is extracted from the learned model to set the decomposition method for the optimization module: 1) reference points compliant with the PF shape and 2) subproblem formulations whose contours and search directions are appropriate for the current status. Accordingly, the optimization module, which can be any decomposition-based EMO algorithm in principle, decomposes the multiobjective optimization problem into a number of subproblems and optimizes them simultaneously. To validate our proposed LTD paradigm, we integrate it with two decomposition-based EMO algorithms, and compare them with four state-of-the-art algorithms on a series of benchmark problems with various PF shapes.

The working principles of the well-established multi-objective evolutionary algorithm Moea/d relies on the iterative and cooperative improvement of a number of single-objective sub-problems obtained by decomposition. Besides the definition of sub-problems, selection and replacement are, like in any evolutionary algorithm, the two core elements of Moea/d. We argue that these two components are however loosely coupled with the maintained population. Thereby, we propose to re-design the working principles of Moea/d by adopting a set-oriented perspective, where a many-to-one mapping between sub-problems and solutions is considered. Selection is then performed by defining a neighborhood relation among solutions in the population set, depending on the corresponding sub-problem mapping. Replacement is performed following an elitist mechanism allowing the population to have a variable, but bounded, cardinality during the search process. By conducting a comprehensive empirical analysis on a range of combinatorial multi- and many-objective NK-landscapes, we show that the proposed approach leads to significant improvements, especially when dealing with an increasing number of objectives. Our findings indicate that a set-oriented design can constitute a sound alternative for strengthening the practice of multi- and many-objective evolutionary optimization based on decomposition.

Pareto Local Search (PLS) is a simple, yet effective optimization approach dedicated to multi-objective combinatorial optimization. It can however suffer from a high computational cost, especially when the size of the Pareto optimal set is relatively large. Recently, incorporating decomposition in PLS had revealed a high potential, not only in providing high-quality approximation sets, but also in speeding-up the search process. Using the bi-objective Unconstrained Binary Quadratic Programming (bUBQP) problem as an illustrative benchmark, we demonstrate some shortcomings in the resulting decomposition-guided Parallel Pareto Local Search (PPLS), and we propose to revisit the PPLS design accordingly. For instances with a priori unknown Pareto front shape, we show that a simple pre-processing technique to estimate the scale of the Pareto front can help PPLS to better balance the workload. Furthermore, we propose a simple technique to deal with the critically-important scalability issue raised by PPLS when deployed over a large number of computing nodes. Our investigations show that the revisited version of PPLS provides a consistent performance, suggesting that decomposition-guided PPLS can be further generalized in order to improve both parallel efficiency and approximation quality.

Decomposition-based multiobjective evolutionary algorithms (MOEAs) decompose a multiobjective optimization problem (MOP) into a set of scalar objective subproblems and solve them in a collaborative way. Commonly used decomposition approaches originate from mathematical programming and the direct use of them may not suit MOEAs due to their population-based property. For instance, these decomposition approaches used in MOEAs may cause the loss of diversity and/or be very sensitive to the shapes of Pareto fronts (PFs). This paper proposes a constrained decomposition with grids (CDG) that can better address these two issues thus more suitable for MOEAs. In addition, different subproblems in CDG defined by the constrained decomposition constitute a grid system. The grids have an inherent property of reflecting the information of neighborhood structures among the solutions, which is a desirable property for restricted mating selection in MOEAs. Based on CDG, a constrained decomposition MOEA with grid (CDG-MOEA) is further proposed. Extensive experiments are conducted to compare CDG-MOEA with the domination-based, indicator-based, and state-of-the-art decomposition-based MOEAs. The experimental results show that CDG-MOEA outperforms the compared algorithms in terms of both the convergence and diversity. More importantly, it is robust to the shapes of PFs and can still be very effective on MOPs with complex PFs (e.g., extremely convex, or with disparately scaled objectives).

We propose an evolution strategy algorithm using a sparse plus low rank model for large-scale optimization in this paper. We first develop a rank one evolution strategy using a single principal search direction. It is of linear complexity. Then we extend it to multiple search directions, and develop a rank-${m}$evolution strategy. We illustrate that the principal search direction accumulates the natural gradients with respect to the distribution mean, and acts as a momentum term. Further, we analyze the optimal low rank approximation to the covariance matrix, and experimentally show that the principal search direction can effectively learn the long valley of the function with predominant search direction. Then we investigate the effects of Hessian on the algorithm performance. We conduct experiments on a class of test problems and the CEC’2010 LSGO benchmarks. The experimental results validate the effectiveness of our proposed algorithms.

An effective allocation of search effort is important in multiobjective optimization, particularly in many-objective optimization problems (MaOPs). This paper presents a new adaptive search effort allocation strategy for multiobjective evolutionary algorithm based on decomposition MOEA/D-M2M, a recent MOEA/D algorithm for challenging MaOPs. This proposed method adaptively adjusts the subregions of its subproblems by detecting the importance of different objectives in an adaptive manner. More specifically, it periodically resets the subregion setting based on the distribution of the current solutions in the objective space such that the search effort is not wasted on unpromising regions. The basic idea is that the current population can be regarded as an approximation to the Pareto front (PF) and thus one can implicitly estimate the shape of the PF and such estimation can be used for adjusting the search focus. The performance of proposed algorithm has been verified by comparing it with eight representative and competitive algorithms on a set of degenerated MaOPs with disconnected and connected PFs. Performances of the proposed algorithm on a number of nondegenerated test instances with connected and disconnected PFs are also studied.

Tchebycheff decomposition represents one of the most widely used decomposition approaches that can convert a multiobjective optimization problem into a set of scalar optimization subproblems. Nevertheless, the geometric properties of the subproblem objective functions in Tchebycheff decomposition have not been explicitly studied. This paper proposes a Tchebycheff decomposition with lp-norm constraint on direction vectors in which the subproblem objective functions are endowed with clear geometric property. Especially, the Tchebycheff decomposition with l2-norm constraint on direction vectors is taken as an example to illustrate its advantage. A new unary R2indicator is also introduced to approximate the hyper-volume metric and justify the efficiency of the proposed Tchebycheff decomposition. A resultant Tchebycheff decomposition-based multiobjective evolutionary algorithm (MOEA) with l2-norm constraint and a new population update strategy is proposed to solve multiobjective optimization problems. The experimental results on both benchmark and real-world multiobjective optimization problems show that the proposed algorithm is capable of obtaining high quality solutions compared with other state-of-the-art MOEAs.

Iterative thresholding is a dominating strategy for sparse optimization problems. The main goal of iterative thresholding methods is to find a so-called -sparse solution. However, the setting of regularization parameters or the estimation of the true sparsity are nontrivial in iterative thresholding methods. To overcome this shortcoming, we propose a preference-based multiobjective evolutionary approach to solve sparse optimization problems in compressive sensing. Our basic strategy is to search the knee part of weakly Pareto front with preference on the true -sparse solution. In the noiseless case, it is easy to locate the exact position of the -sparse solution from the distribution of the solutions found by our proposed method. Therefore, our method has the ability to detect the true sparsity. Moreover, any iterative thresholding methods can be used as a local optimizer in our proposed method, and no prior estimation of sparsity is required. The proposed method can also be extended to solve sparse optimization problems with noise. Extensive experiments have been conducted to study its performance on artificial signals and magnetic resonance imaging signals. Our experimental results have shown that our proposed method is very effective for detecting sparsity and can improve the reconstruction ability of existing iterative thresholding methods.

Decomposition based approaches are increasingly being used to solve many-objective optimization problems (MaOPs). In such approaches, the MaOP is decomposed into several single-objective sub-problems and solved simultaneously guided by a set of predefined, uniformly distributed reference vectors. The reference vectors are constructed by joining a set of uniformly sampled points to the ideal point. Use of such reference vectors originating from the ideal point has so far performed reasonably well on common benchmarks such as DTLZs and WFGs, since the geometry of their Pareto fronts can be easily mapped using these reference vectors. However, the approach may not deliver a set of well distributed solutions for problems with Pareto fronts which are convex/concave or where the shape of the Pareto front is not best suited for such set of reference vectors (e.g. minus series of DTLZ and WFG test problems). While the notion of reference vectors originating from the nadir point has been suggested in the literature in the past, they have rarely been used in decomposition based algorithms. Such reference vectors are complementary in nature with the ones originating from the ideal point. Therefore, in this paper, we introduce a decomposition based approach which attempts to use both these two sets of reference vectors and chooses the most appropriate set at each generation based on the s-energy metric. The performance of the approach is presented and objectively compared with a number of recent algorithms. The results clearly highlight the benefits of such an approach especially when the nature of the Pareto front is not known a priori.

Covariance matrix adaptation evolution strategies (CMA-ES) is a powerful optimizer. In this paper, we propose an efficient rank-1 update for the Cholesky covariance matrix adaptation evolution strategy (Cholesky CMA-ES) using an auxiliary evolution path. It accumulates the average mutation vector corresponding to the current search direction, which is used to update the evolution path. It is used to update the Cholesky factor. It avoids to maintain the additional inverse Cholesky factor, and reduces the computational complexity in the update procedure to a half. Further, we experimentally show that the auxiliary evolution path approximates to the inverse vector of the evolution path in terms of inverse Cholesky factor in the procedure. We experimentally show that the proposed method achieves comparative or even better performances on the test problems.

This paper proposes a novel surrogate-model-based multi-objective evolutionary algorithm, which is called Multi-objective Bayesian Optimization Algorithm based on Decomposition (MOBO/D). In this algorithm, a multi-objective problem is decomposed into several subproblems which will be solved simultaneously. MOBO/D builds Gaussian process model for each objective to learn the optimization surface, and defines utility function for each subproblem to guide the searching process. At each generation, MOEA/D algorithm is called to locate a set of candidate solutions which maximize all utility functions respectively, and a subset of those candidate solutions is selected for parallel batch evaluation. Experimental study on different test instances validates that MOBO/D can efficiently solve expensive multi-objective problems in parallel. The performance of MOBO/D is also better than several classical expensive optimization methods.

Although several sequential heuristics have been proposed for dealing with the Unconstrained Binary Quadratic Programming (UBQP), very little effort has been made for designing parallel algorithms for the UBQP. This paper propose a novel decentralized parallel search algorithm, called Parallel Elite Biased Tabu Search (PEBTS). It is based on D2TS, a state-of-the-art sequential UBQP metaheuristic. The key strategies in the PEBTS algorithm include: (i) a lazy distributed cooperation procedure to maintain diversity among different search processes and (ii) finely tuned bit-flip operators which can help the search escape local optima efficiently. Our experiments on the Tianhe-2 supercomputer with up to 24 computing cores show the accuracy of the efficiency of PEBTS compared with a straightforward parallel algorithm running multiple independent and non-cooperating D2TS processes.

By transforming a multi-objective optimization problem into a number of single-objective optimization problems and optimizing them simultaneously, decomposition-based evolutionary multi-objective optimization algorithms have attracted much attention in the field of multi-objective optimization. In decomposition-based algorithms, the population diversity is maintained using a set of predefined weight vectors, which are often evenly sampled on a unit simplex. However, when the Pareto front of the problem is not a hyperplane but more complex, the distribution of the final solution set will not be that uniform. In this paper, we propose an adaptive method to periodically regenerate the weight vectors for decomposition-based multi-objective algorithms according to the geometry of the estimated Pareto front. In particular, the Pareto front is estimated via Gaussian process regression. Thereafter, the weight vectors are reconstructed by sampling a set of points evenly distributed on the estimated Pareto front. Experimental studies on a set of multi-objective optimization problems with different Pareto front geometries verify the effectiveness of the proposed adaptive weights generation method.

The Steiner tree problem (STP) aims to determine some Steiner nodes such that the minimum spanning tree over these Steiner nodes and a given set of special nodes has the minimum weight, which is NP-hard. STP includes several important cases. The Steiner tree problem in graphs (GSTP) is one of them. Many heuristics have been proposed for STP, and some of them have proved to be performance guarantee approximation algorithms for this problem. Since evolutionary algorithms (EAs) are general and popular randomized heuristics, it is significant to investigate the performance of EAs for STP. Several empirical investigations have shown that EAs are efficient for STP. However, up to now, there is no theoretical work on the performance of EAs for STP. In this article, we reveal that the (1+1) EA achieves 3/2-approximation ratio for STP in a special class of quasi-bipartite graphs in expected runtime [Formula: see text], where [Formula: see text], [Formula: see text], and [Formula: see text] are, respectively, the number of Steiner nodes, the number of special nodes, and the largest weight among all edges in the input graph. We also show that the (1+1) EA is better than two other heuristics on two GSTP instances, and the (1+1) EA may be inefficient on a constructed GSTP instance.

Multiobjective evolutionary algorithm based on decomposition (MOEA/D) decomposes a multiobjective optimization problem (MOP) into a number of scalar optimization subproblems and then solves them in parallel. In many MOEA/D variants, each subproblem is associated with one and only one solution. An underlying assumption is that each subproblem has a different Pareto-optimal solution, which may not be held, for irregular Pareto fronts (PFs), e.g., disconnected and degenerate ones. In this paper, we propose a new variant of MOEA/D with sorting-and-selection (MOEA/D-SAS). Different from other selection schemes, the balance between convergence and diversity is achieved by two distinctive components, decomposition-based-sorting (DBS) and angle-based-selection (ABS). DBS only sorts L closest solutions to each subproblem to control the convergence and reduce the computational cost. The parameter L has been made adaptive based on the evolutionary process. ABS takes use of angle information between solutions in the objective space to maintain a more fine-grained diversity. In MOEA/D-SAS, different solutions can be associated with the same subproblems; and some subproblems are allowed to have no associated solution, more flexible to MOPs or many-objective optimization problems (MaOPs) with different shapes of PFs. Comprehensive experimental studies have shown that MOEA/D-SAS outperforms other approaches; and is especially effective on MOPs or MaOPs with irregular PFs. Moreover, the computational efficiency of DBS and the effects of ABS in MOEA/D-SAS are also investigated and discussed in detail.

Nondominated sorting (NDS), which divides a population into several nondomination levels (NDLs), is a basic step in many evolutionary multiobjective optimization (EMO) algorithms. It has been widely studied in a generational evolution model, where the environmental selection is performed after generating a whole population of offspring. However, in a steady-state evolution model, where a population is updated right after the generation of a new candidate, the NDS can be extremely time consuming. This is especially severe when the number of objectives and population size become large. In this paper, we propose an efficient NDL update method to reduce the cost for maintaining the NDL structure in steady-state EMO. Instead of performing the NDS from scratch, our method only updates the NDLs of a limited number of solutions by extracting the knowledge from the current NDL structure. Notice that our NDL update method is performed twice at each iteration. One is after the reproduction, the other is after the environmental selection. Extensive experiments fully demonstrate that, comparing to the other five state-of-the-art NDS methods, our proposed method avoids a significant amount of unnecessary comparisons, not only in the synthetic data sets, but also in some real optimization scenarios. Last but not least, we find that our proposed method is also useful for the generational evolution model.

The bias feature is a major factor that makes a multiobjective optimization problem (MOP) difficult for multiobjective evolutionary algorithms (MOEAs). To deal with this problem feature, an algorithm should carefully balance between exploration and exploitation. The decomposition-based MOEA decomposes an MOP into a number of single objective subproblems and solves them in a collaborative manner. Single objective optimizers can be easily used in this algorithm framework. Covariance matrix adaptation evolution strategy (CMA-ES) has proven to be able to strike good balance between the exploration and the exploitation of search space. This paper proposes a scheme to use both differential evolution (DE) and covariance matrix adaptation in the MOEA based on decomposition. In this scheme, single objective optimization problems are clustered into several groups. To reduce the computational overhead, only one subproblem from each group is selected to optimize by CMA-ES while other subproblems are optimized by DE. When an evolution strategy procedure meets some stopping criteria, it will be reinitialized and used for solving another subproblem in the same group. A set of new multiobjective test problems with bias features are constructed in this paper. Extensive experimental studies show that our proposed algorithm is suitable for dealing with problems with biases.

Barrier coverage with wireless sensors aims at detecting intruders who attempt to cross a specific area, where wireless sensors are distributed remotely at random. This paper considers limited-power sensors with adjustable ranges deployed along a linear domain to form a barrier to detect intruding incidents. We introduce three objectives to minimize: 1) total power consumption while satisfying full coverage; 2) the number of active sensors to improve the reliability; and 3) the active sensor nodes' maximum sensing range to maintain fairness. We refer to the problem as the tradeoff barrier coverage (TBC) problem. With the aim of obtaining a better tradeoff among the three objectives, we present a multiobjective optimization framework based on multiobjective evolutionary algorithm (MOEA)/D, which is called problem specific MOEA/D (PS-MOEA/D). Specifically, we define a 2-tuple encoding scheme and introduce a cover-shrink algorithm to produce feasible and relatively optimal solutions. Subsequently, we incorporate problem-specific knowledge into local search, which allows search procedures for neighboring subproblems collaborate each other. By considering the problem characteristics, we analyze the complexity and incorporate a strategy of computational resource allocation into our algorithm. We validate our approach by comparing with four competitors through several most-used metrics. The experimental results demonstrate that PS-MOEA/D is effective and outperforms the four competitors in all the cases, which indicates that our approach is promising in dealing with TBC.

Sparse signal reconstruction can be regarded as a problem of locating the nonzero entries of the signal. In presence of measurement noise, conventional methods such as l1norm relaxation methods and greedy algorithms, have shown their weakness in finding the nonzero entries accurately. In order to reduce the impact of noise and better locate the nonzero entries, in this paper, we propose a two-phase algorithm which works in a coarse-to-fine manner. In phase 1, a decomposition-based multiobjective evolutionary algorithm is applied to generate a group of robust solutions by optimizing l1norm of the solutions. To remove the interruption of noise, the statistical features with respect to each entry among these solutions are extracted and an initial set of nonzero entries are determined by clustering technique. In phase 2, a forward-based selection method is proposed to further update this set and locate the nonzero entries more precisely based on these features. At last, the magnitudes of the reconstructed signal are obtained by the method of least squares. We conduct the comparison of our proposed method with several state-of-the-art compressive sensing recover methods, the best result in phase 1 and the approach combining phases 1 and 2 without the statistical features. Experimental results on benchmark signals as well as randomly generated signals demonstrate that our proposed method outperforms the above methods, achieving higher recover precision and maintaining larger sparsity.

The balance between convergence and diversity is the cornerstone of evolutionary multiobjective optimization (EMO). The recently proposed stable matching-based selection provides a new perspective to handle this balance under the framework of decomposition multiobjective optimization. In particular, the one-one stable matching between subproblems and solutions, which achieves an equilibrium between their mutual preferences, is claimed to strike a balance between convergence and diversity. However, the original stable marriage model has a high risk of matching a solution with an unfavorable subproblem, which finally leads to an imbalanced selection result. In this paper, we introduce the concept of incomplete preference lists into the stable matching model to remedy the loss of population diversity. In particular, each solution is only allowed to maintain a partial preference list consisting of its favorite subproblems. We implement two versions of stable matching-based selection mechanisms with incomplete preference lists: one achieves a two-level one-one matching and the other obtains a many-one matching. Furthermore, an adaptive mechanism is developed to automatically set the length of the incomplete preference list for each solution according to its local competitiveness. The effectiveness and competitiveness of our proposed methods are validated and compared with several state-of-the-art EMO algorithms on 62 benchmark problems.

Real-world computationally expensive design optimization problems with discrete variables pose challenges to surrogate-based optimization methods in terms of both efficiency and search ability. In this paper, a new method is introduced, called surrogate model-aware differential evolution with neighbourhood exploration, which has two phases. The first phase adopts a surrogate-based optimization method based on efficient surrogate model-aware search framework, the goal of which is to reach at least the neighbourhood of the global optimum. In the second phase, a neighbourhood exploration method for discrete variables is developed and collaborates with the first phase to further improve the obtained solutions. Empirical studies on various benchmark problems and a real-world network-on-chip design optimization problem show the combined advantages in terms of efficiency and search ability: when only a very limited number of exact evaluations are allowed, the proposed method is not slower than one of the most efficient methods for the targeted problem; when more evaluations are allowed, the proposed method can obtain results with comparable quality compared to standard differential evolution, but it requires only 1% to 30% of exact function evaluations.

To deal with real-life black-box expensive multiobjective optimization problems, we investigated the application of an optimization framework expanded from MOEA/D-EGO. As MOEA/D-EGO, Gaussian process modeling techniques are used to subtittute the evaluation of the problem itself. Apart from the expected improvement (EI) in-fill rule in the original MOEA/D-EGO, we define a process that adaptively selects of in-fill rule in each iteration from seven different in-fill rules, including confidence limit of different probability (CLp), probability of improvement (PI), and EI. The initial probabilities of selecting a specific in-fill rule are derived from applying the algorithm on ZDT test suite. The practical problem set-up and optimization results and lesson learned in the process are reported.

Solving sparse optimization problems via regularization frameworks is the dominant methodology for reconstructing sparse signals in the area of compressive sensing. In recent a few years, the use of multiobjective evolutionary algorithms (MOEAs) for sparse optimization has also attracted some research interests. Under the multiobjective framework, the loss term (error) and the regularization term (sparsity) are treated as two separate objective functions. So far, two popular multiobjective frameworks, NSGA-II and MOEA/D, have been used for sparse optimization. In this paper, we further develop a new MOEA/D variant for sparse reconstruction and sparsity detection, which involves three phases - approximating Pareto front (PF) in a chain order (phase 1) and in a random order (phase 2), and exploiting a knee region (phase 3 - optional). Our experimental results show that our proposed method is more effective than the earlier version of MOEA/D and the HALF solver in sparse signal reconstruction and sparsity detection.

This paper investigates how to use a pre-selection approach to improve the performance of the multiobjective evolutionary algorithm based on decomposition (MOEA/D). It proposes a novel MOEA/D algorithm with classification to serve this purpose. The proposed algorithm builds a classification model on the search space to filter all new generated solutions, and mainly evaluates those promising solutions for reducing real function evaluation costs during the search process. Experimental study on different test instances validates that the pre-selection approach can significantly improve the performance of a classical MOEA/D.

When optimizing an multiobjective optimization problem, the evolution of population can be regarded as a approximation to the Pareto Front (PF). Motivated by this idea, we propose an adaptive region decomposition framework: MOEA/D-AM2M for the degenerated Many-Objective optimization problem (MaOP), where degenerated MaOP refers to the optimization problem with a degenerated PF in a subspace of the objective space. In this framework, a complex MaOP can be adaptively decomposed into a number of many-objective optimization subproblems, which is realized by the adaptively direction vectors design according to the present population's distribution. A new adaptive weight vectors design method based on this adaptive region decomposition is also proposed for selection in MOEA/D-AM2M. This strategy can timely adjust the regions and weights according to the population's tendency in the evolutionary process, which serves as a remedy for the inefficiency of fixed and evenly distributed weights when solving MaOP with a degenerated PF. Five degenerated MaOPs with disconnected PFs are generated to identify the effectiveness of proposed MOEA/D-AM2M. Contrast experiments are conducted by optimizing those MaOPs using MOEA/D-AM2M, MOEA/D-DE and MOEA/D-M2M. Simulation results have shown that the proposed MOEA/D-AM2M outperforms MOEA/D-DE and MOEA/D-M2M.

A cone order sequence based MOEA (CS-MOEA) is proposed to deal with the multi-objective optimization problems. Instead of only using the Pareto dominance, it constructs a sequence of cone order to balance the search diversity and convergence. By gradually increasing the open angle of the cone order, it approximates the Pareto cone gradually. A simple formula for judging the θ-cone dominance is derived, which is easy to be computed. Moreover, an energy model is introduced for the selection of individuals to maintain population diversity. Experiments on more than 10 problems (i.e. zdt and dtlz benchmark problem sets) demonstrate that the proposed method is competitive, compared with Stable Matching MOEA/D (STM-MOEA/D) and MOEA/D-DE.

Due to the extensive and various information that natural images contain, it is very challenging to estimate the sparsity for an image. In this paper, we propose an adaptive sparsity estimation model for image patches, which consists of an offline training phase and online estimation phase. In offline training, for the training patch, MOEA/D is applied to obtain a group of Pareto solutions and determine a sparsity range. By processing a reduced number of representative training patches, all the sparsity ranges are stored in a look-up table (LUT) for reuse. In the online estimation phase, for a query patch, its sparsity range is set to that of the most similar training patch. And the corresponding sparse representation vector can be obtained by a sparsity-restricted greedy algorithm (SRGA) constrained by this range. Thus, the sparsity is adaptively determined by this sparse representation vector within this range. By comparing with the state-of-the-art greedy algorithms with fixed sparsity and one adaptive method, experimental studies on benchmark dataset demonstrate that our proposed approach is able to achieve better sparse representation quality in terms of PSNR and coding efficiency.

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.

Multiobjective evolutionary algorithms based on decomposition (MOEA/D) decompose a multiobjective optimization problem into a set of simple optimization subproblems and solve them in a collaborative manner. A replacement scheme, which assigns a new solution to a subproblem, plays a key role in balancing diversity and convergence in MOEA/D. This paper proposes a global replacement scheme which assigns a new solution to its most suitable subproblems. We demonstrate that the replacement neighborhood size is critical for population diversity and convergence, and develop an approach for adjusting this size dynamically. A steady-state algorithm and a generational one with this approach have been designed and experimentally studied. The experimental results on a number of test problems have shown that the proposed algorithms have some advantages.

Multiobjective evolutionary algorithms evolve a population of solutions through successive generations toward the Pareto-optimal front (POF). One of the most critical questions faced by the researchers and practitioners in this domain relates to the number of generations that may be sufficient for an algorithm to offer a good approximation of the POF for a given problem. Ironically, to date, this question largely remains unanswered and the number of generations are arbitrarily fixed a priori, with potentially punitive implications. If the a priori fixed generations are insufficient, then the algorithm reports suboptimal solutions. In contrast, if the a priori fixed generations are far too many, it implies waste of computational resources. This paper proposes a novel entropy-based dissimilarity measure that helps identify on the fly the number of generations beyond which an algorithm stabilizes, implying that either a good approximation has been obtained or that it cannot be obtained due to the stagnation of the algorithm in the search space. Given that in either case no further improvement in the approximation can be obtained, despite additional computational expense, the proposed dissimilarity measure provides a termination criterion and facilitates a termination detection algorithm. The generality, on-the-fly implementation, low-computational complexity, and the demonstrated efficacy of the proposed termination detection algorithm, on a wide range of multiobjective and many-objective test problems, define the novel contribution of this paper.

Decomposition-based algorithms have become increasingly popular for evolutionary multiobjective optimization. However, the effect of scalarizing methods used in these algorithms is still far from being well understood. This paper analyzes a family of frequently used scalarizing methods, the Lpmethods, and shows that the p value is crucial to balance the selective pressure toward the Pareto optimal and the algorithm robustness to Pareto optimal front (PF) geometries. It demonstrates that an Lpmethod that can maximize the search ability of a decomposition-based algorithm exists and guarantees that, given some weight, any solution along the PF can be found. Moreover, a simple yet effective method called Pareto adaptive scalarizing (PaS) approximation is proposed to approximate the optimal p value. In order to demonstrate the effectiveness of PaS, we incorporate PaS into a state-of-the-art decomposition-based algorithm, i.e., multiobjective evolutionary algorithm based on decomposition (MOEA/D), and compare the resultant MOEA/D-PaS with some other MOEA/D variants on a set of problems with different PF geometries and up to seven conflicting objectives. Experimental results demonstrate that the PaS is effective.

A decomposition approach decomposes a multiobjective optimization problem into a number of scalar objective optimization subproblems. It plays a key role in decomposition-based multiobjective evolutionary algorithms. However, many widely used decomposition approaches, originally proposed for mathematical programming algorithms, may not be very suitable for evolutionary algorithms. To help decomposition-based multiobjective evolutionary algorithms balance the population diversity and convergence in an appropriate manner, this letter proposes to impose some constraints on the subproblems. Experiments have been conducted to demonstrate that our proposed constrained decomposition approach works well on most test instances. We further propose a strategy for adaptively adjusting constraints by using information collected from the search. Experimental results show that it can significantly improve the algorithm performance.

Under mild conditions, the Pareto front (Pareto set) of a continuous m-objective optimization problem forms an (m - 1)-dimensional piecewise continuous manifold. Based on this property, this paper proposes a self-organizing multiobjective evolutionary algorithm. At each generation, a self-organizing mapping method with (m - 1) latent variables is applied to establish the neighborhood relationship among current solutions. A solution is only allowed to mate with its neighboring solutions to generate a new solution. To reduce the computational overhead, the self-organizing training step and the evolution step are conducted in an alternative manner. In other words, the self-organizing training is performed only one single step at each generation. The proposed algorithm has been applied to a number of test instances and compared with some state-of-the-art multiobjective evolutionary methods. The results have demonstrated its advantages over other approaches.

Decomposition-based multiobjective evolutionary algorithms (MOEAs) decompose a multiobjective optimization problem into a set of scalar objective subproblems and solve them in a collaborative way. A naïve way to distribute computational effort is to treat all the subproblems equally and assign the same computational resource to each subproblem. This paper proposes a generalized resource allocation (GRA) strategy for decomposition-based MOEAs by using a probability of improvement vector. Each subproblem is chosen to invest according to this vector. An offline measurement and an online measurement of the subproblem hardness are used to maintain and update this vector. Utility functions are proposed and studied for implementing a reasonable and stable online resource allocation strategy. Extensive experimental studies on the proposed GRA strategy have been conducted.

Real world optimization often involves noises and uncertainty. Most current research on evolutionary multiobjective optimization does not consider the effect of noise. This paper studies the performance of decomposition based multiobjective optimization evolutionary algorithm (MOEA/D) in noisy environment. Experiments are carried out to compare the performance of MOEA/D and NSGA II under different levels of noise in objective functions evaluation. Statistical analysis has been made to understand the behaviour of MOEA/D. Based on the comparison and analysis, we discuss possible improvement methods on MOEA/D for noisy optimization.

MOEA/D is a decomposition-based multiobjective evolutionary algorithm that has attracted much attention in recent years. Its performance depends on the setting of weight vectors which are used for defining subproblems. In the case of irregular Pareto fronts (e.g, disconnected or degenerated), fixed setting of weight vectors in MOEA/D may not work well. In this paper, we propose an improved MOEA/D with both random and fixed weight vectors. Moreover, an external archive based on a modified ε-dominance strategy is used for storing nondominated solutions found by the proposed algorithm and assisting the generation of random weight vectors. Some experiments have been conducted to verify the efficiency and effectiveness of the improved MOEA/D on benchmark multiobjective test problems with irregular Pareto fronts. The experimental results show that the overall performance of the proposed algorithm is better than baseline MOEA/D and NSGA-II.

Achieving balance between convergence and diversity is a basic issue in evolutionary multiobjective optimization (EMO). In this paper, we propose a hybrid EMO algorithm that assigns different selection principles to two separate and co-evolving archives. Particularly, one archive maintains a repository with a competitive selection pressure towards the Pareto-optimal front (PF), the other preserves a population with a satisfied distribution in the objective space. Furthermore, to exploit guidance information towards the Pareto-optimal set (PS), we develop a restricted mating selection mechanism to select mating parents from each archive for offspring generation. Empirical studies are conducted on a set of benchmark problems with complicated PSs. Experimental results demonstrate the effectiveness and competitiveness of our proposed algorithm in balancing convergence and diversity.

This paper studies how to use two reproduction operators with different characteristics for balancing the convergence and the diversity in MOEA/D. We consider two operators. One is a differential evolution and polynomial mutation, and the other is a neighbor learning and inversion mutation. We show that these two operators have different search abilities. Then we propose a scheme to use these two operators in our recently proposed MOEA/D-GR framework. We test the proposed algorithm on some benchmark problems to demonstrate its effectiveness.

Stable matching-based selection models the selection process in MOEA/D as a stable marriage problem. By finding a stable matching between the sub problems and solutions, the solutions are assigned to sub problems to balance the convergence and the diversity. In this paper, a two-level stable matching-based selection is proposed to further guarantee the diversity of the population. More specifically, the first level of stable matching only matches a solution to one of its most preferred sub problems and the second level of stable matching is responsible for matching the solutions to the remaining sub problems. Experimental studies demonstrate that the proposed selection scheme is effective and competitive comparing to other state-of-the-art selection schemes for MOEA/D.

Multiobjective evolutionary algorithm based on decomposition (MOEA/D), which bridges the traditional optimization techniques and population-based methods, has become an increasingly popular framework for evolutionary multiobjective optimization. It decomposes a multiobjective optimization problem (MOP) into a number of optimization subproblems. Each subproblem is handled by an agent in a collaborative manner. The selection of MOEA/D is a process of choosing solutions by agents. In particular, each agent has two requirements on its selected solution: one is the convergence toward the efficient front, the other is the distinction with the other agents' choices. This paper suggests addressing these two requirements by defining mutual-preferences between subproblems and solutions. Afterwards, a simple yet effective method is proposed to build an interrelationship between subproblems and solutions, based on their mutual-preferences. At each generation, this interrelationship is used as a guideline to select the elite solutions to survive as the next parents. By considering the mutual-preferences between subproblems and solutions (i.e., the two requirements of each agent), the selection operator is able to balance the convergence and diversity of the search process. Comprehensive experiments are conducted on several MOP test instances with complicated Pareto sets. Empirical results demonstrate the effectiveness and competitiveness of our proposed algorithm.

Domination-based sorting and decomposition are two basic strategies used in multiobjective evolutionary optimization. This paper proposes a hybrid multiobjective evolutionary algorithm integrating these two different strategies for combinatorial optimization problems with two or three objectives. The proposed algorithm works with an internal (working) population and an external archive. It uses a decomposition-based strategy for evolving its working population and uses a domination-based sorting for maintaining the external archive. Information extracted from the external archive is used to decide which search regions should be searched at each generation. In such a way, the domination-based sorting and the decomposition strategy can complement each other. In our experimental studies, the proposed algorithm is compared with a domination-based approach, a decomposition-based one, and one of its enhanced variants on two well-known multiobjective combinatorial optimization problems. Experimental results show that our proposed algorithm outperforms other approaches. The effects of the external archive in the proposed algorithm are also investigated and discussed.

Achieving balance between convergence and diversity is a key issue in evolutionary multiobjective optimization. Most existing methodologies, which have demonstrated their niche on various practical problems involving two and three objectives, face significant challenges in many-objective optimization. This paper suggests a unified paradigm, which combines dominance- and decomposition-based approaches, for many-objective optimization. Our major purpose is to exploit the merits of both dominance- and decomposition-based approaches to balance the convergence and diversity of the evolutionary process. The performance of our proposed method is validated and compared with four state-of-the-art algorithms on a number of unconstrained benchmark problems with up to 15 objectives. Empirical results fully demonstrate the superiority of our proposed method on all considered test instances. In addition, we extend this method to solve constrained problems having a large number of objectives. Compared to two other recently proposed constrained optimizers, our proposed method shows highly competitive performance on all the constrained optimization problems.

In an estimation of distribution algorithm (EDA), global population distribution is modeled by a probabilistic model, from which new trial solutions are sampled, whereas individual location information is not directly and fully exploited. In this paper, we suggest to combine an EDA with cheap and expensive local search (LS) methods for making use of both global statistical information and individual location information. In our approach, part of a new solution is sampled from a modified univariate histogram probabilistic model and the rest is generated by refining a parent solution through a cheap LS method that does not need any function evaluation. When the population has converged, an expensive LS method is applied to improve a promising solution found so far. Controlled experiments have been carried out to investigate the effects of the algorithm components and the control parameters, the scalability on the number of variables, and the running time. The proposed algorithm has been compared with two state-of-the-art algorithms on two test suites of 27 test instances. Experimental results have shown that, for simple test instances, our algorithm can produce better or similar solutions but with faster convergence speed than the compared methods and for some complicated test instances it can find better solutions.

Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D) decomposes a multiobjective optimisation problem into a number of single-objective problems and optimises them in a collaborative manner. This paper investigates how to use Tabu Search (TS), a well-studied single objective heuristic to enhance MOEA/D performance. In our proposed approach, the TS is applied to these subproblems with the aim to escape from local optimal solutions. The experimental studies have shown that MOEA/D with TS outperforms the classical MOEA/D on multiobjective permutation flow shop scheduling problems. It also have demonstrated that use of problem specific knowledge can significantly improve the algorithm performance.

The team orienteering problem with time windows (TOPTW) is a well studied routing problem. In this paper, a cooperative algorithm is proposed. It collaborates metaheuristic and branch-and-price. A restricted master problem and subproblem are defined. It uses a heuristic to obtain an integral solution for the restricted master problem and a metaheuristic to generate new columns for the subproblem. Experimental study shows that this algorithm can find new better solutions for several instances in short time, which supports the effectiveness of the cooperative mechanism between metaheuristic and branch-and-price.

In this paper, we propose a decomposition based multiobjective evolutionary algorithm that extracts information from an external archive to guide the evolutionary search for continuous optimization problem. The proposed algorithm used a mechanism to identify the promising regions(subproblems) through learning information from the external archive to guide evolutionary search process. In order to demonstrate the performance of the algorithm, we conduct experiments to compare it with other decomposition based approaches. The results validate that our proposed algorithm is very competitive.

It is well-established that the shapes of Pareto-optimal fronts (POFs) can affect the performance of some multiobjective optimization methods. The most well-known characteristics on the shape of POFs are convexity and discontinuity. In this paper, we investigate the construction of multiobjective test problems with complicated POFs, of which its local parts could have mixed dimensionalities. For example, in the case of 3 objectives, some parts of POFs can be 1-D curves while others could be 2-D surfaces. We formulate eight test problems, called CPFT1-8, with such a feature. To study the difficulties of these test problems, we conducted some experiments with two state-of-the-art algorithms MOEA/D and NSGA-II, and analyzed their performances.

The surrogate model-aware evolutionary search (SMAS) framework is an emerging model management method for surrogate model assisted evolutionary algorithms (SAEAs). SAEAs based on SMAS outperform several state-of-the-art SAEAs using other model management methods and show promising results in real-world computationally expensive optimization problems. However, there is little behavioral study of the SMAS framework, and appropriate rules for its search strategy, training data selection and key parameter selection for different types of problems have not been provided yet. In this paper, with a newly proposed training data selection method, the SMAS framework's behaviour with different search strategies and training data selection methods is investigated. The empirical rules in terms of problem characteristics are obtained and the method to construct an SAEA based on the SMAS framework is updated. Experiments using 24 widely used benchmark test problems and the test problems in the CEC 2014 competition of computationally expensive optimization are carried out, which validate the proposed empirical rules.

This paper studies the replacement schemes in MOEA/D and proposes a new replacement named global replacement. It can improve the performance of MOEA/D. Moreover, trade-offs between convergence and diversity can be easily controlled in this replacement strategy. It also shows that different problems need different trade-offs between convergence and diversity. We test the MOEA/D with this global replacement on three sets of benchmark problems to demonstrate its effectiveness.

Combining ideas from evolutionary algorithms, decomposition approaches, and Pareto local search, this paper suggests a simple yet efficient memetic algorithm for combinatorial multiobjective optimization problems: memetic algorithm based on decomposition (MOMAD). It decomposes a combinatorial multiobjective problem into a number of single objective optimization problems using an aggregation method. MOMAD evolves three populations: 1) population P(L) for recording the current solution to each subproblem; 2) population P(P) for storing starting solutions for Pareto local search; and 3) an external population P(E) for maintaining all the nondominated solutions found so far during the search. A problem-specific single objective heuristic can be applied to these subproblems to initialize the three populations. At each generation, a Pareto local search method is first applied to search a neighborhood of each solution in P(P) to update P(L) and P(E). Then a single objective local search is applied to each perturbed solution in P(L) for improving P(L) and P(E), and reinitializing P(P). The procedure is repeated until a stopping condition is met. MOMAD provides a generic hybrid multiobjective algorithmic framework in which problem specific knowledge, well developed single objective local search and heuristics and Pareto local search methods can be hybridized. It is a population based iterative method and thus an anytime algorithm. Extensive experiments have been conducted in this paper to study MOMAD and compare it with some other state-of-the-art algorithms on the multiobjective traveling salesman problem and the multiobjective knapsack problem. The experimental results show that our proposed algorithm outperforms or performs similarly to the best so far heuristics on these two problems.

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.

This paper investigates how to use prediction strategies to improve the performance of multiobjective evolutionary optimization algorithms in dealing with dynamic environments. Prediction-based methods have been applied to predict some isolated points in both dynamic single objective optimization and dynamic multiobjective optimization. We extend this idea to predict a whole population by considering the properties of continuous dynamic multiobjective optimization problems. In our approach, called population prediction strategy (PPS), a Pareto set is divided into two parts: a center point and a manifold. A sequence of center points is maintained to predict the next center, and the previous manifolds are used to estimate the next manifold. Thus, PPS could initialize a whole population by combining the predicted center and estimated manifold when a change is detected. We systematically compare PPS with a random initialization strategy and a hybrid initialization strategy on a variety of test instances with linear or nonlinear correlation between design variables. The statistical results show that PPS is promising for dealing with dynamic environments.

Adaptive operator selection (AOS) is used to determine the application rates of different operators in an online manner based on their recent performances within an optimization process. This paper proposes a bandit-based AOS method, fitness-rate-rank-based multiarmed bandit (FRRMAB). In order to track the dynamics of the search process, it uses a sliding window to record the recent fitness improvement rates achieved by the operators, while employing a decaying mechanism to increase the selection probability of the best operator. Not much work has been done on AOS in multiobjective evolutionary computation since it is very difficult to measure the fitness improvements quantitatively in most Pareto-dominance-based multiobjective evolutionary algorithms. Multiobjective evolutionary algorithm based on decomposition (MOEA/D) decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them simultaneously. Thus, it is natural and feasible to use AOS in MOEA/D. We investigate several important issues in using FRRMAB in MOEA/D. Our experimental results demonstrate that FRRMAB is robust and its operator selection is reasonable. Comparison experiments also indicate that FRRMAB can significantly improve the performance of MOEA/D.

Multiobjective evolutionary algorithm based on decomposition (MOEA/D) decomposes a multiobjective optimization problem into a set of scalar optimization subproblems and optimizes them in a collaborative manner. Subproblems and solutions are two sets of agents that naturally exist in MOEA/D. The selection of promising solutions for subproblems can be regarded as a matching between subproblems and solutions. Stable matching, proposed in economics, can effectively resolve conflicts of interests among selfish agents in the market. In this paper, we advocate the use of a simple and effective stable matching (STM) model to coordinate the selection process in MOEA/D. In this model, subproblem agents can express their preferences over the solution agents, and vice versa. The stable outcome produced by the STM model matches each subproblem with one single solution, and it tradeoffs convergence and diversity of the evolutionary search. Comprehensive experiments have shown the effectiveness and competitiveness of our MOEA/D algorithm with the STM model. We have also demonstrated that user-preference information can be readily used in our proposed algorithm to find a region that decision makers are interested in.

This letter suggests an approach for decomposing a multiobjective optimization problem (MOP) into a set of simple multiobjective optimization subproblems. Using this approach, it proposes MOEA/D-M2M, a new version of multiobjective optimization evolutionary algorithm-based decomposition. This proposed algorithm solves these subproblems in a collaborative way. Each subproblem has its own population and receives computational effort at each generation. In such a way, population diversity can be maintained, which is critical for solving some MOPs. Experimental studies have been conducted to compare MOEA/D-M2M with classic MOEA/D and NSGA-II. This letter argues that population diversity is more important than convergence in multiobjective evolutionary algorithms for dealing with some MOPs. It also explains why MOEA/D-M2M performs better.

Surrogate model assisted evolutionary algorithms (SAEAs) have recently attracted much attention due to the growing need for computationally expensive optimization in many real-world applications. Most current SAEAs, however, focus on small-scale problems. SAEAs for medium-scale problems (i.e., 20-50 decision variables) have not yet been well studied. In this paper, a Gaussian process surrogate model assisted evolutionary algorithm for medium-scale computationally expensive optimization problems (GPEME) is proposed and investigated. Its major components are a surrogate model-aware search mechanism for expensive optimization problems when a high-quality surrogate model is difficult to build and dimension reduction techniques for tackling the “curse of dimensionality.” A new framework is developed and used in GPEME, which carefully coordinates the surrogate modeling and the evolutionary search, so that the search can focus on a small promising area and is supported by the constructed surrogate model. Sammon mapping is introduced to transform the decision variables from tens of dimensions to a few dimensions, in order to take advantage of Gaussian process surrogate modeling in a low-dimensional space. Empirical studies on benchmark problems with 20, 30, and 50 variables and a real-world power amplifier design automation problem with 17 variables show the high efficiency and effectiveness of GPEME. Compared to three state-of-the-art SAEAs, better or similar solutions can be obtained with 12% to 50% exact function evaluations.

Optical networks have attracted much more attention in the last decades due to its huge bandwidth (Tbps). The Wavelength Division Multiplexing (WDM) is a technology that aims to make the most of this networks by dividing each single fiber link into several wavelengths of light or channels. Each channel operates in the range of Gbps; unfortunately, the requirements of the vast majority of current traffic connection requests are a few Mbps, causing a waste of bandwidth at each channel. We can solve this drawback by equipping each optical node with an access station for multiplexing or grooming several low-speed requests onto one single high-speed channel. This problem of grooming low-speed requests is known in the literature as the Traffic Grooming problem. In this work, we formulate the Traffic Grooming problem as a Multiobjective Optimization Problem, optimizing simultaneously the total throughput, the number of transceivers used, and the average propagation delay. We propose the use of the Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D). The experiments are conducted on three optical network topologies and diverse scenarios. The results report that the MOEA/D algorithm works more efficiently than other multiobjective approaches and other single-objective heuristics published in the literature.

In this paper, we propose a multi-restart memetic algorithm framework for box constrained global continuous optimisation. In this framework, an evolutionary algorithm (EA) and a local optimizer are employed as separated building blocks. The EA is used to explore the search space for very promising solutions (e.g., solutions in the attraction basin of the global optimum) through its exploration capability and previous EA search history, and local search is used to improve these promising solutions to local optima. An estimation of distribution algorithm (EDA) combined with a derivative free local optimizer, called NEWUOA (M. Powell, Developments of NEWUOA for minimization without derivatives. Journal of Numerical Analysis, 28:649-664, 2008), is developed based on this framework and empirically compared with several well-known EAs on a set of 40 commonly used test functions. The main components of the specific algorithm include: (1) an adaptive multivariate probability model, (2) a multiple sampling strategy, (3) decoupling of the hybridisation strategy, and (4) a restart mechanism. The adaptive multivariate probability model and multiple sampling strategy are designed to enhance the exploration capability. The restart mechanism attempts to make the search escape from local optima, resorting to previous search history. Comparison results show that the algorithm is comparable with the best known EAs, including the winner of the 2005 IEEE Congress on Evolutionary Computation (CEC2005), and significantly better than the others in terms of both the solution quality and computational cost.

Combining ant colony optimization (ACO) and the multiobjective evolutionary algorithm (EA) based on decomposition (MOEA/D), this paper proposes a multiobjective EA, i.e., MOEA/D-ACO. Following other MOEA/D-like algorithms, MOEA/D-ACO decomposes a multiobjective optimization problem into a number of single-objective optimization problems. Each ant (i.e., agent) is responsible for solving one subproblem. All the ants are divided into a few groups, and each ant has several neighboring ants. An ant group maintains a pheromone matrix, and an individual ant has a heuristic information matrix. During the search, each ant also records the best solution found so far for its subproblem. To construct a new solution, an ant combines information from its group's pheromone matrix, its own heuristic information matrix, and its current solution. An ant checks the new solutions constructed by itself and its neighbors, and updates its current solution if it has found a better one in terms of its own objective. Extensive experiments have been conducted in this paper to study and compare MOEA/D-ACO with other algorithms on two sets of test problems. On the multiobjective 0-1 knapsack problem,MOEA/D-ACO outperforms the MOEA/D with conventional genetic operators and local search on all the nine test instances. We also demonstrate that the heuristic information matrices in MOEA/D-ACO are crucial to the good performance of MOEA/D-ACO for the knapsack problem. On the biobjective traveling salesman problem, MOEA/D-ACO performs much better than the BicriterionAnt on all the 12 test instances. We also evaluate the effects of grouping, neighborhood, and the location information of current solutions on the performance of MOEA/D-ACO. The work in this paper shows that reactive search optimization scheme, i.e., the "learning while optimizing" principle, is effective in improving multiobjective optimization algorithms.

Fitness modeling has received growing interest from the evolutionary computation community in recent years. With a fitness model, one can improve evolutionary algorithm efficiency by directly sampling new solutions, developing hybrid guided evolutionary operators or using the model as a surrogate for an expensive fitness function. This paper addresses several issues on fitness modeling of discrete functions, particularly how modeling quality and efficiency can be improved. We define the Markov network fitness model in terms of Walsh functions. We explore the relationship between the Markov network fitness model and fitness in a number of discrete problems, showing how the parameters of the fitness model can identify qualitative features of the fitness function. We define the fitness prediction correlation, a metric to measure fitness modeling capability of local and global fitness models. We use this metric to investigate the effects of population size and selection on the tradeoff between model quality and complexity for the Markov network fitness model.

In engineering design and manufacturing optimization, the trade-off between a quality performance metric and the probability of satisfying all performance specifications (yield) of a product naturally leads to a chance-constrained bi-objective stochastic optimization problem (CBSOP). A new method, called MOOLP (multi-objective uncertain optimization with ordinal optimization (OO)), Latin supercube sampling and parallel computation), is proposed in this paper for dealing with the CBSOP. This proposed method consists of a constraint satisfaction phase and an objective optimization phase. In its constraint satisfaction phase, by using the OO technique, an adequate number of samples are allocated to promising solutions, and the number of unnecessary MC simulations for noncritical solutions can be reduced. This can achieve more than five times speed enhancement compared to the application of using an equal number of samples for each candidate solution. In its MOEA/D-based objective optimization phase, by using LSS, more than five times speed enhancement can be achieved with the same estimation accuracy compared to primitive MC simulation. Parallel computation is also used for speedup. A real-world problem of the bi-objective variation-aware sizing for an analog integrated circuit is used in this paper as a practical application. The experiments clearly demonstrate the advantages of MOOLP.

The difficulties faced by existing multiobjective evolutionary algorithms (MOEAs) in handling many-objective problems relate to the inefficiency of selection operators, high computational cost, and difficulty in visualization of objective space. While many approaches aim to counter these difficulties by increasing the fidelity of the standard selection operators, the objective reduction approach attempts to eliminate objectives that are not essential to describe the Pareto-optimal front (POF). If the number of essential objectives is found to be two or three, the problem could be solved by the existing MOEAs. It implies that objective reduction could make an otherwise unsolvable (many-objective) problem solvable. Even when the essential objectives are four or more, the reduced representation of the problem will have favorable impact on the search efficiency, computational cost, and decision-making. Hence, development of generic and robust objective reduction approaches becomes important. This paper presents a principal component analysis and maximum variance unfolding based framework for linear and nonlinear objective reduction algorithms, respectively. The major contribution of this paper includes: 1) the enhancements in the core components of the framework for higher robustness in terms of applicability to a range of problems with disparate degree of redundancy; mechanisms to handle input data that poorly approximates the true POF; and dependence on fewer parameters to minimize the variability in performance; 2) proposition of an error measure to assess the quality of results; 3) sensitivity analysis of the proposed algorithms for the critical parameter involved, and the characteristics of the input data; and 4) study of the performance of the proposed algorithms vis-à-vis dominance relation preservation based algorithms, on a wide range of test problems (scaled up to 50 objectives) and two real-world problems.

Surrogate model assisted evolutionary algorithms are receiving much attention for the solution of optimization problems with computationally expensive function evaluations. For small scale problems, the use of a Gaussian Process surrogate model and prescreening methods has proven to be effective. However, each commonly used prescreening method is only suitable for some types of problems, and the proper prescreening method for an unknown problem cannot be stated beforehand. In this paper, the four existing prescreening methods are analyzed and a new method, called self-adaptive lower confidence bound (ALCB), is proposed. The extent of rewarding the prediction uncertainty is adjusted on line based on the density of samples in a local area and the function properties. The exploration and exploitation ability of prescreening can thus be better balanced. Experimental results on benchmark problems show that ALCB has two main advantages: (1) it is more general for different problem landscapes than any of the four existing prescreening methods; (2) it typically can achieve the best result among all available prescreening methods.

Many real world applications require optimizing multiple objectives simultaneously. Multiobjective evolutionary algorithm based on decomposition (MOEA/D) is a new framework for dealing with such kind of multiobjective optimization problems (MOPs). MOEA/D focuses on how to maintain a set of scalarized sub-problems to approximate the optimum of a MOP. This paper addresses the offspring reproduction operator in MOEA/D. It is arguable that, to design efficient offspring generators, the properties of both the algorithm to use and the problem to tackle should be considered. To illustrate this idea, a generator based on multivariate Gaussian models is proposed under the MOEA/D framework in this paper. In the new generator, both the local and global population distribution information is extracted by a set of Gaussian distribution models; new trial solutions are sampled from the probability models. The proposed approach is applied to a set of benchmark problems with complicated Pareto sets. The comparison study shows that the offspring generator is promising for dealing with continuous MOPs.

The multiobjective evolutionary algorithm based on decomposition (MOEA/D) has demonstrated superior performance by winning the multiobjective optimization algorithm competition at the CEC 2009. For effective performance of MOEA/D, neighborhood size (NS) parameter has to be tuned. In this letter, an ensemble of different NSs with online self-adaptation is proposed (ENS-MOEA/D) to overcome this shortcoming. Our experimental results on the CEC 2009 competition test instances show that an ensemble of different NSs with online self-adaptation yields superior performance over implementations with only one fixed NS.

Which problems a search algorithm can effectively solve is a fundamental issue that plays a key role in understanding and developing algorithms. In order to study the ability limit of estimation of distribution algorithms (EDAs), this paper experimentally tests three different EDA implementations on a sequence of additively decomposable functions (ADFs) with an increasing number of interactions among binary variables. The results show that the ability of EDAs to solve problems could be lost immediately when the degree of variable interaction is larger than a threshold. We argue that this phase-transition phenomenon is closely related with the computational restrictions imposed in the learning step of this type of algorithms. Moreover, we demonstrate how the use of unrestricted Bayesian networks rapidly becomes inefficient as the number of sub-functions in an ADF increases. The study conducted in this paper is useful in order to identify patterns of behavior in EDAs and, thus, improve their performances.

In this paper, an interactive version of the decomposition based multiobjective evolutionary algorithm (iMOEA/D) is proposed for interaction between the decision maker (DM) and the algorithm. In MOEA/D, a multi-objective problem (MOP) can be decomposed into several single-objective sub-problems. Thus, the preference incorporation mechanism in our algorithm is implemented by selecting the preferred sub-problems rather than the preferred region in the objective space. At each interaction, iMOEA/D offers a set of current solutions and asks the DM to choose the most preferred one. Then, the search will be guided to the neighborhood of the selected. iMOEA/D is tested on some benchmark problems, and various utility functions are used to simulate the DM's responses. The experimental studies show that iMOEA/D can handle the preference information very well and successfully converge to the expected preferred regions.

We have recently proposed a Population-based Guided Local Search (P-GLS) framework for solving difficult combinatorial optimization problems. In P-GLS, several agents of guided local search (GLS) procedures are run in a parallel way. These agents exchange information acquired from their previous search to make their further search more rational. We suggested based on the well-known proximate optimality principle (POP) that the shared features between the current agents' local optimal solutions are more likely to be part of the best solution to the problem; therefore these features should not be penalized. However, sometimes some of these common features may not exhibit in a global optimal solution. In this paper, a new framework is proposed to improve the performance as well as overcome the limitations in P-GLS. It applies two new different penalization strategies that increase favouring common features based on their occurrences in the agents' local optimal solutions during the search. The performance of the new algorithm, examined on the Traveling Salesman Problem (TSP), is investigated and evaluated in terms of solution quality and the speed. The experimental results demonstrate that the new algorithm outperforms the parallel GLS algorithm without collaboration and other state-of-the-art algorithms.

Trial vector generation strategies and control parameters have a significant influence on the performance of differential evolution (DE). This paper studies whether the performance of DE can be improved by combining several effective trial vector generation strategies with some suitable control parameter settings. A novel method, called composite DE (CoDE), has been proposed in this paper. This method uses three trial vector generation strategies and three control parameter settings. It randomly combines them to generate trial vectors. CoDE has been tested on all the CEC2005 contest test instances. Experimental results show that CoDE is very competitive.

This paper presents a comparative study among three evolutionary and search based methods to solve the problem of channel selection for Brain-Computer Interface (BCI) systems. Multi-Objective Particle Swarm Optimization (MOPSO) method is compared to Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) and single objective Sequential Floating Forward Search (SFFS) method. The methods are tested on the first data set for BCI-Competition IV. The results show the usefulness of the multi-objective evolutionary methods in achieving accuracy results similar to the extensive search method with fewer channels and less computational time.

Mobile agents are often used in wireless sensor networks for distributed target detection with the goal of minimizing the transmission of non-critical data that negatively affects the performance of the network. A challenge is to find optimal mobile agent routes for minimizing the data path loss and the sensors energy consumption as well as maximizing the data accuracy. Existing approaches deal with the objectives individually, or by optimizing one and constraining the others or by combining them into a single objective. This often results in missing “good” tradeoff solutions. Only few approaches have tackled the Mobile Agent-based Distributed Sensor Network Routing problem as a Multiobjective Optimization Problem (MOP) using conventional Multi-Objective Evolutionary Algorithms (MOEAs). It is well known that the incorporation of problem specific knowledge in MOEAs is a difficult task. In this paper, we propose a problem-specific MOEA based on Decomposition (MOEA/D) for optimizing the three objectives. Experimental studies have shown that the proposed problem-specific approach performs better than two conventional MOEAs in several WSN test instances.

Recently, a multiobjective evolutionary algorithm based on decomposition (MOEA/D) and its extended version by using differential evolution (DE) as the main search engine (MOEA/D-DE) were proposed, which outperform several widely used multiobjective evolutionary algorithms. MOEA/D decomposes a multiobjective problem into a number of scalar optimization sub-problems with a neighborhood structure and optimizes them simultaneously to approximate the Pareto-optimal set. In this paper, two mechanisms are investigated to enhance the performance of MOEA/D-DE. Firstly, a new replacement mechanism is proposed to call for a balance between the diversity of the population and the employment of good information from neighbors. Secondly, the scaling factor in DE is randomized to enhance the search ability. Comparisons are carried out with MOEA/D-DE on ten benchmark problems, showing that the proposed method exhibits significant improvements. Finally, the enhanced MOEA/D-DE is applied to a real world problem, the sizing of a folded-cascode amplifier with four performance objectives.

Based on the Proximate Optimality Principle in metaheuristics, a Population Based Guided Local Search (P-GLS) framework for dealing with difficult combinatorial optimization problems is suggested in this paper. In P-GLS, several guided local search (GLS) procedures (agents) run in a parallel way. These agents exchange information during some time points in the search. The information exchanged is the best solutions found so far by these agents. Each agent use such information to adjust its search behavior for moving to a more promising search region. Some preliminary experiments have been conducted on the traveling salesman problem to study the effectiveness of P-GLS.

MOEA/D is a generic multiobjective evolutionary optimization algorithm. MOEA/D needs a approach to decompose a multiobjective optimization problem into a number of single objective optimization problems. The commonly-used weighted sum approach and the Tchebycheff approach may not be able to handle disparately scaled objectives. This paper suggests a new decomposition approach, called NBI-style Tchebycheff approach, for MOEA/D to deal with such objectives. A portfolio management MOP has been used as an example to test the effectiveness of MOEA/D with NBI-style Tchebycheff approach.

Minimax optimization requires to minimize the maximum output in all possible scenarios. It is a very challenging problem to evolutionary computation. In this paper, we propose a surrogate-assisted evolutionary algorithm, Minimax SAEA, for tackling minimax optimization problems. In Minimax SAEA, a surrogate model based on Gaussian process is built to approximate the mapping between the decision variables and the objective value. In each generation, most of the new solutions are evaluated based on the surrogate model and only the best one is evaluated by the actual objective function. Minimax SAEA is tested on six benchmark problems and the experimental results show that Minimax SAEA can successfully solve five of them within 110 function evaluations.

In some expensive multiobjective optimization problems (MOPs), several function evaluations can be carried out in a batch way. Therefore, it is very desirable to develop methods which can generate multipler test points simultaneously. This paper proposes such a method, called MOEA/D-EGO, for dealing with expensive multiobjective optimization. MOEA/D-EGO decomposes an MOP in question into a number of single-objective optimization subproblems. A predictive model is built for each subproblem based on the points evaluated so far. Effort has been made to reduce the overhead for modeling and to improve the prediction quality. At each generation, MOEA/D is used for maximizing the expected improvement metric values of all the subproblems, and then several test points are selected for evaluation. Extensive experimental studies have been carried out to investigate the ability of the proposed algorithm.

Structure learning is a crucial component of a multivariate Estimation of Distribution algorithm. It is the part which determines the interactions between variables in the probabilistic model, based on analysis of the fitness function or a population. In this paper we take three different approaches to structure learning in an EDA based on Markov networks and use measures from the information retrieval community (precision, recall and the F-measure) to assess the quality of the structures learned. We then observe the impact that structure has on the fitness modelling and optimisation capabilities of the resulting model, concluding that these results should be relevant to research in both structure learning and fitness modelling.

Multi-objective optimization is an essential and challenging topic in the domains of engineering and computation because real-world problems usually include several conflicting objectives. Current trends in the research of solving multi-objective problems (MOPs) require that the adopted optimization method provides an approximation of the Pareto set such that the user can understand the tradeoff between objectives and therefore make the final decision. Recently, an efficient framework, called MOEA/D, combining decomposition techniques in mathematics and optimization methods in evolutionary computation was proposed. MOEA/D decomposes a MOP to a set of single-objective problems (SOPs) with neighborhood relationship and approximates the Pareto set by solving these SOPs. In this paper, we attempt to enhance MOEA/D by proposing two mechanisms. To fully employ the information obtained from neighbors, we introduce a guided mutation operator to replace the differential evolution operator. Moreover, a update mechanism utilizing a priority queue is proposed for performance improvement when the SOPs obtained by decomposition are not uniformly distributed on the Pareto font. Different combinations of these approaches are compared based on the test problem instances proposed for the CEC 2009 competition. The set of problem instances include unconstrained and constrained MOPs with variable linkages. Experimental results are presented in the paper, and observations and discussion are also provided.

This paper proposed self-guided genetic algorithm, which is one of the algorithms in the category of evolutionary algorithm based on probabilistic models (EAPM), to solve strong NP-hard flowshop scheduling problems with the minimization of makespan. Most EAPM research explicitly used the probabilistic model from the parental distribution, then generated solutions by sampling from the probabilistic model without using genetic operators. Although EAPM is promising in solving different kinds of problems, self-guided GA doesn't intend to generate solution by the probabilistic model directly because the time complexity is high when we solve combinatorial problems, particularly the sequencing ones. As a result, the probabilistic model serves as a fitness surrogate which estimates the fitness of the new solution beforehand in this research. So the probabilistic model is used to guide the evolutionary process of crossover and mutation. This research studied the flowshop scheduling problems and the corresponding experiment were conducted. From the results, it shows that the self-guided GA outperformed other algorithms significantly. In addition, self-guided GA works more efficiently than previous EAPM. As a result, self-guided GA is promising in solving the flowshop scheduling problems.

In this paper, we propose a Subproblem-dependent Heuristic (SH) for MOEA/D to deal with the Deployment and Power Assignment Problem (DPAP) in Wireless Sensor Networks (WSNs). The goal of the DPAP is to assign locations and transmit power levels to sensor nodes for maximizing the network coverage and lifetime objectives. In our method, the DPAP is decomposed into a number of scalar subproblems. The subproblems are optimized in parallel, by using neighborhood information and problem-specific knowledge. The proposed SH probabilistically alternates between two DPAP-specific strategies based on the subproblems objective preferences. Simulation results have shown that MOEA/D performs better than NSGA-II in several WSN instances.

Gaussian process model is an effective and efficient method for approximating a continuous function. However, its computational cost increases exponentially with the size of training data set. A very popular way to alleviate this shortcoming is to cluster the whole training data set into a number of small clusters and then a local model is built for each cluster. However, widely used crisp clustering might not be accurate in the boundary areas among different clusters. This paper proposes a fuzzy clustering based method for improving approximation quality. Several clusters with overlaps are firstly obtained by Fuzzy C-Means clustering and then local models are built for these clusters. It has been demonstrated that this method can be used with evolutionary algorithms for dealing expensive optimization problems.

This paper describes the idea of MOEA/D and proposes a strategy for allocating the computational resource to different subproblems in MOEA/D. The new version of MOEA/D has been tested on all the CEC09 unconstrained MOP test instances.

The K-connected deployment and power assignment problem (DPAP) in WSNs aims at deciding both the sensor locations and transmit power levels, for maximizing both the network coverage and lifetime under K-connectivity constraints, in a single run. It is shown that the multi-objective evolutionary algorithm based on decomposition (MOEA/D) is a strong enough tool for dealing with unconstraint real life problems (such as DPAP), emphasizing the importance of incorporating problem specific knowledge for increasing its efficiency. Since the K-connected DPAP requires constraint handling, several techniques are investigated and compared, including a DPAP-specific repair heuristic (RH) that transforms an infeasible network design into a feasible one and maintains the MOEA/D's efficiency simultaneously. This is achieved by alternating between two repair strategies, which favor one objective each. Simulation results have shown that the MOEA/D-RH performs better than the popular constrained NSGA-II in several network instances.

Wireless sensor networks deployment and power assignment problems (DPAPs) for maximizing the network coverage and lifetime respectively, have received increasing attention recently. Classical approaches optimize these two objectives individually, or by combining them together in a single objective, or by constraining one and optimizing the other. In this paper, the two problems are formulated as a multi-objective DPAP and tackled simultaneously. Problem-specific encoding representation and genetic operators are designed for the DPAP and a multi-objective evolutionary algorithm based on decomposition (MOEA/D) is specialized. The multi-objective DPAP is decomposed into many scalar subproblems which are solved simultaneously by using neighborhood information and network knowledge. Simulation results have shown the effectiveness of the proposed evolutionary components by providing a high quality set of alternative solutions without any prior knowledge on the objectives preference, and the superiority of our problem-specific MOEA/D approach against a state of the art MOEA.

Partly due to lack of test problems, the impact of the Pareto set (PS) shapes on the performance of evolutionary algorithms has not yet attracted much attention. This paper introduces a general class of continuous multiobjective optimization test instances with arbitrary prescribed PS shapes, which could be used for studying the ability of multiobjective evolutionary algorithms for dealing with complicated PS shapes. It also proposes a new version of MOEA/D based on differential evolution (DE), i.e., MOEA/D-DE, and compares the proposed algorithm with NSGA-II with the same reproduction operators on the test instances introduced in this paper. The experimental results indicate that MOEA/D could significantly outperform NSGA-II on these test instances. It suggests that decomposition based multiobjective evolutionary algorithms are very promising in dealing with complicated PS shapes.

The three papers in this special issue focus on evolutionary algorithms based on probabilistic models.

Most existing multiobjective evolutionary algorithms aim at approximating the Pareto front (PF), which is the distribution of the Pareto-optimal solutions in the objective space. In many real-life applications, however, a good approximation to the Pareto set (PS), which is the distribution of the Pareto-optimal solutions in the decision space, is also required by a decision maker. This paper considers a class of multiobjective optimization problems (MOPs), in which the dimensionalities of the PS and the PF manifolds are different so that a good approximation to the PF might not approximate the PS very well. It proposes a probabilistic model-based multiobjective evolutionary algorithm, called MMEA, for approximating the PS and the PF simultaneously for an MOP in this class. In the modeling phase of MMEA, the population is clustered into a number of subpopulations based on their distribution in the objective space, the principal component analysis technique is used to estimate the dimensionality of the PS manifold in each subpopulation, and then a probabilistic model is built for modeling the distribution of the Pareto-optimal solutions in the decision space. Such a modeling procedure could promote the population diversity in both the decision and objective spaces. MMEA is compared with three other methods, KP1, Omni-Optimizer and RM-MEDA, on a set of test instances, five of which are proposed in this paper. The experimental results clearly suggest that, overall, MMEA performs significantly better than the three compared algorithms in approximating both the PS and the PF.

Selection is one of the defining characteristics of an evolutionary algorithm, yet inherent in the selection process is the loss of some information from a population. Poor solutions may provide information about how to bias the search toward good solutions. Many Estimation of Distribution Algorithms (EDAs) use truncation selection which discards all solutions below a certain fitness, thus losing this information. Our previous work on Distribution Estimation using Markov networks (DEUM) has described an EDA which constructs a model of the fitness function; a unique feature of this approach is that because selective pressure is built into the model itself selection becomes optional. This paper outlines a series of experiments which make use of this property to examine the effects of selection on the population. We look at the impact of selecting only highly fit solutions, only poor solutions, selecting a mixture of highly fit and poor solutions, and abandoning selection altogether. We show that in some circumstances, particularly where some information about the problem is already known, selection of the fittest only is suboptimal.

Many multiobjective evolutionary algorithms are based Pareto domination, among them NSGA II and SPEA 2 are two very popular ones. MOEA/D is a very recent multiobjective evolutionary algorithm using decomposition. In this paper, we implement MOEA/D for multi-objective flowshop scheduling problems. We study the replacement strategy of neighboring solutions, the determination of the reference point, and compare different decomposition methods. Experimental results demonstrate that MOEA/D outperforms NSGA II and SPEA 2 significantly for the 2-objective and 3-objective benchmark flowshop-scheduling instances.

Black-box expensive function is ubiquitous in real world problems. Much research has been done on scalar objective optimization for such problems with great success. Comparatively, very little work has been done in multi-objective optimization. In many cases, it is not straightforward to convert methods from scalar objective optimization to multi-objective optimization due to the complexities incurred by Pareto domination. In our pervious research, concept of model composition based on Gaussian Process metamodel and the powerful MOEA/D framework proved to be a successful approach for multi-objective optimization with black-box expensive functions. We derived Weighted-Sum and Tchebycheff model composition for bi-objective problems. However, due to the complexity of Tchebycheff decomposition structure, it is very hard, if not impossible, to extend the method to three or more objective problems in a nature way. In this paper, we propose an approximation method for Tchebycheff model composition which greatly simplify the derivation for three or more objective cases. Experiments show the approximation produces very similar performance as the Weighted-Sum and Tchebycheff without approximation. Thus, the new method enables us to tackle multi-objective problems with black-box expensive functions that could not be tackled effectively so far.

The Pareto front (Pareto set) of a continuous optimization problem with m objectives is a (m-1) dimensional piecewise continuous manifold in the objective space (the decision space) under some mild conditions. Based on this regularity property in the objective space, we have recently developed several multiobjective estimation of distribution algorithms (EDAs). However, this property has not been utilized in the decision space. Using the regularity property in both the objective and decision space, this paper proposes a simple EDA for multiobjective optimization. Since the location information has not efficiently used in EDAs, a combination of EDA and differential evolution (DE) is suggested for improving the algorithmic performance. The hybrid method and the pure EDA method proposed in this paper, and a DE based method are compared on several test instances. Experimental results have shown that the algorithm with the proposed strategy is very promising.

Wireless sensor networks design requires high quality location assignment and energy efficient power assignment for maximizing the network coverage and lifetime. Classical deployment and power assignment approaches optimize these two objectives individually or by combining them together in a single objective or by constraining one and optimizing the other. In this article a multi-objective deployment and power assignment problem (DPAP) is formulated and a multi-objective evolutionary algorithm based on decomposition (MOEA/D) is specialized. Following the MOEA/D's framework the above multiobjective optimization problem (MOP) is decomposed into many scalar single objective problems. The sub-problems are solved simultaneously by using neighborhood information. Additionally, unique problem-specific, parameter-rising, genetic operators and local search heuristics were designed specifically for the DPAP. In addition, a new encoding scheme is designed to represent a WSN based on the DPAP's design variables. Simulation results show that MOEA/D provides a high quality set of alternative solutions without any prior knowledge on the objectives preference.

This paper proposes a hybrid estimation of distribution algorithm (HyEDA) to address the design problem of code division multiple access cellular system configuration. Given a service area, the problem is to find a set of optimal locations of base stations, associated with their corresponding powers and antenna heights in the area, in order to maximize call quality and service coverage, at the same time, to minimize the total cost of the system configuration. HyEDA is a two-stage hybrid approach which integrates an estimation of distribution algorithm, a K-means clustering method, and a simple local search algorithm. We have compared HyEDA with a simulated annealing method on a number of instances. Our simulation results have demonstrated that HyEDA outperforms the simulated annealing method in terms of the solution quality and computational cost.

Under mild conditions, it can be induced from the Karush-Kuhn-Tucker condition that the Pareto set, in the decision space, of a continuous multiobjective optimization problem is a piecewise continuous (m - 1)-D manifold, where m is the number of objectives. Based on this regularity property, we propose a regularity model-based multiobjective estimation of distribution algorithm (RM-MEDA) for continuous multiobjective optimization problems with variable linkages. At each generation, the proposed algorithm models a promising area in the decision space by a probability distribution whose centroid is a (m - 1)-D piecewise continuous manifold. The local principal component analysis algorithm is used for building such a model. New trial solutions are sampled from the model thus built. A nondominated sorting-based selection is used for choosing solutions for the next generation. Systematic experiments have shown that, overall, RM-MEDA outperforms three other state-of-the-art algorithms, namely, GDE3, PCX-NSGA-II, and MIDEA, on a set of test instances with variable linkages. We have demonstrated that, compared with GDE3, RM-MEDA is not sensitive to algorithmic parameters, and has good scalability to the number of decision variables in the case of nonlinear variable linkages. A few shortcomings of RM-MEDA have also been identified and discussed in this paper.

In the above titled paper (ibid., vol. 12, no. 1, pp. 41-63, Feb. 08), Fig. 20 was wrong. Its replacement is presented here.

The Pareto optimal set of a continuous multiobjective optimization problem is a piecewise continuous manifold under some mild conditions.We have recently developed several multi-objective evolutionary algorithms based on this property. However, the modelling methods used in these algorithms are rather costly. In this paper, a cheap and effective modelling strategy is proposed for building the probabilistic models of promising solutions. A new criterion is proposed for measuring the convergence of the algorithm. The locality degree of each local model is adjusted according to the proposed convergence criterion. Experimental results show that the algorithm with the proposed strategy is very promising.

An Estimation of Distribution Algorithm (EDA) is proposed toapproach the Hybrid Flow Shop with Sequence Dependent Setup Times and Uniform Machines in parallel (HFS-SDST-UM) problem. The latter motivated by the needs of a real world company. The proposed EDA implements a fairly new mechanism to improve the search of more traditional EDAs. This is the Guided Mutation (GM). EDA-GM generates new solutions by using the information from a probability model, as all EDAs, and the local information from a good known solution. The approach is tested on several instances of HFS-SDST-UM and compared with adaptations of meta-heuristics designed for very similarproblems. Encouraging results are reported.

Multiobjective optimization problems with many local Pareto fronts is a big challenge to evolutionary algorithms. In this paper, two operators, biased initialization and biased crossover, are proposed to improve the global search ability of RM-MEDA, a recently proposed multiobjective estimation of distribution algorithm. Biased initialization inserts several globally Pareto optimal solutions into the initial population; biased crossover combines the location information of some best solutions found so far and globally statistical information extracted from current population. Experiments have been conducted to study the effects of these two operators.

Decomposition is a basic strategy in traditional multiobjective optimization. However, it has not yet been widely used in multiobjective evolutionary optimization. This paper proposes a multiobjective evolutionary algorithm based on decomposition (MOEA/D). It decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them simultaneously. Each subproblem is optimized by only using information from its several neighboring subproblems, which makes MOEA/D have lower computational complexity at each generation than MOGLS and nondominated sorting genetic algorithm II (NSGA-II). Experimental results have demonstrated that MOEA/D with simple decomposition methods outperforms or performs similarly to MOGLS and NSGA-II on multiobjective 0-1 knapsack problems and continuous multiobjective optimization problems. It has been shown that MOEA/D using objective normalization can deal with disparately-scaled objectives, and MOEA/D with an advanced decomposition method can generate a set of very evenly distributed solutions for 3-objective test instances. The ability of MOEA/D with small population, the scalability and sensitivity of MOEA/D have also been experimentally investigated in this paper.

An evolutionary algorithm (EA) can be used to tune the control parameters of a construction heuristic to an optimization problem and generate a nearly optimal solution. This approach is in the spirit of indirect encoding EAs. Its performance relies on both the heuristic and the EA. This paper proposes a three-phase parameterized construction heuristic for the shared-path protection problem in wavelength division multiplexing networks with shared-risk link group constraints and applies an EA for optimizing the control parameters of the proposed heuristics. The experimental results show that the proposed approach is effective on all the tested network instances. It was also demonstrated that an EA with guided mutation performs better than a conventional genetic algorithm for tuning the control parameters, which indicates that a combination of global statistical information extracted from the previous search and location information of the best solutions found so far could improve the performance of an algorithm.

Guided mutation uses the idea of estimation of distribution algorithms to improve conventional mutation operators. It combines global statistical information and the location information of good individual solutions for generating new trial solutions. This paper suggests using guided mutation in iterative local search. An experimental comparison between a conventional iterated local search (CILS) and an iterated local search with guided mutation has been conducted on four classes of the test instances of the quadratic assignment problem.

In our previous work [1], it has been shown that the performance of multi-objective evolutionary algorithms can be greatly enhanced if the regularity in the distribution of Pareto-optimal solutions is used. This paper suggests a new hybrid multi-objective evolutionary algorithm by introducing a convergence based criterion to determine when the model-based method and when the genetics-based method should be used to generate offspring in each generation. The basic idea is that the genetics-based method, i. e., crossover and mutation, should be used when the population is far away from the Pareto front and no obvious regularity in population distribution can be observed. When the population moves towards the Pareto front, the distribution of the individuals will show increasing regularity and in this case, the model-based method should be used to generate offspring. The proposed hybrid method is verified on widely used test problems and our simulation results show that the method is effective in achieving Pareto-optimal solutions compared to two state-of-the-art evolutionary multi-objective algorithms: NSGA-II and SPEA2, and our pervious method in [1].

Cost-effective topology control is critical in wireless sensor networks. While much research has been carried out in this aspect using various methods, no attention has been made on utilizing modern heuristics for this purpose. This paper proposes a memetic algorithm-based solution for energy-aware topology control for wireless sensor networks. This algorithm (called ToCMA), using a combination of problem-specific light-weighted local search and genetic algorithm, is able to solve the minimum energy network connectivity (MENC) this NP-hard problem in an approximated manner that performs better than the classical minimum spanning tree (MST) solution. The outcomes of ToCMA can also be utilized for various network optimization and fault-tolerant purposes.

The Pareto optimal solutions to a multi-objective optimization problem often distribute very regularly in both the decision space and the objective space. Most existing evolutionary algorithms do not explicitly take advantage of such a regularity. This paper proposed a model-based evolutionary algorithm (M-MOEA) for bi-objective optimization problems. Inspired by the ideas from estimation of distribution algorithms, M-MOEA uses a probability model to capture the regularity of the distribution of the Pareto optimal solutions. The local principal component analysis (local PCA) and the least-squares method are employed for building the model. New solutions are sampled from the model thus built. At alternate generations, M-MOEA uses crossover and mutation to produce new solutions. The selection in M-MOEA is the same as in non-dominated sorting genetic algorithm-II (NSGA-II). Therefore, MOEA can be regarded as a combination of EDA and NSGA-II. The preliminary experimental results show that M-MOEA performs better than NSGA-II.

Estimation of distribution algorithms sample new solutions (offspring) from a probability model which characterizes the distribution of promising solutions in the search space at each generation. The location information of solutions found so far (i.e., the actual positions of these solutions in the search space) is not directly used for generating offspring in most existing estimation of distribution algorithms. This paper introduces a new operator, called guided mutation. Guided mutation generates offspring through combination of global statistical information and the location information of solutions found so far. An evolutionary algorithm with guided mutation (EA/G) for the maximum clique problem is proposed in this paper. Besides guided mutation, EA/G adopts a strategy for searching different search areas in different search phases. Marchiori's heuristic is applied to each new solution to produce a maximal clique in EA/G. Experimental results show that EA/G outperforms the heuristic genetic algorithm of Marchiori (the best evolutionary algorithm reported so far) and a MIMIC algorithm on DIMACS benchmark graphs.

This work shows that we could describe the characteristics of easy and hard fitness landscapes in one-dimensional continuous space by drift analysis. The work expends the existing results in the discrete space into the continue space. A fitness landscape, here, is regarded as the behaviour of an evolutionary algorithm on fitness functions. Based on the drift analysis, easy fitness landscapes are thought to be a "short-distance" landscape, which is easy for the evolutionary algorithm to find the optimal point; and hard fitness landscapes then are as a far-distance landscape, which the evolutionary algorithm had to spend a long time to find the optimal point.

Aims to study the advantages of using higher order statistics in estimation distribution of algorithms (EDAs). We study two EDAs with two-tournament selection for discrete optimization problems. One is the univariate marginal distribution algorithm (UMDA) using only first-order statistics and the other is the factorized distribution algorithm (FDA) using higher order statistics. We introduce the heuristic functions and the limit models of these two algorithms and analyze stability of these limit models. It is shown that the limit model of UMDA can be trapped at any local optimal solution for some initial probability models. However, degenerate probability density functions (pdfs) at some local optimal solutions are unstable in the limit model of FDA. In particular, the degenerate pdf at the global optimal solution is the unique asymptotically stable point in the limit model of FDA for the optimization of an additively decomposable function. Our results suggest that using higher order statistics could improve the chance of finding the global optimal solution.

We investigate the global convergence of estimation of distribution algorithms (EDAs). In EDAs, the distribution is estimated from a set of selected elements, i.e., the parent set, and then the estimated distribution model is used to generate new elements. In this paper, we prove that: 1) if the distribution of the new elements matches that of the parent set exactly, the algorithms will converge to the global optimum under three widely used selection schemes and 2) a factorized distribution algorithm converges globally under proportional selection.

Hyvarinen et al. (2000) have developed an ICA based method for image denoising. The major advantage of their method is that the transformation matrix can by adjusted to suit the available data. However, in their method, the transformation matrix and shrinkage parameters need to be learned from noise-free data. In this paper, we propose a simplified shrinkage scheme, which has only one heuristic control parameter. Experimental results show that the ICA based method with this new shrinkage scheme achieves comparable performance to that of Hyvarinen et al.

Principal component analysis (PCA) and minor component analysis (MCA) are a powerful methodology for a wide variety of applications such as pattern recognition and signal processing. In this paper, we first propose a differential equation for the generalized eigenvalue problem.We prove that the stable points of this differential equation are the eigenvectors corresponding to the largest eigenvalue. Based on this generalized differential equation, a class of PCA and MCA learning algorithms can be obtained. We demonstrate that many existing PCA and MCA learning algorithms are special cases of this class, and this class includes some new and simpler MCA learning algorithms. Our results show that all the learning algorithms of this class have the same order of convergence speed, and they are robust to implementation error.

Principal component analysis (PCA) and minor component analysis (MCA) are a powerful methodology for a wide variety of applications such as pattern recognition and signal processing. In this paper, we first propose a differential equation for the generalized eigenvalue problem. We prove that the stable points of this differential equation are the eigenvectors corresponding to the largest eigenvalue. Based on this generalized differential equation, a class of PCA and MCA learning algorithms can be obtained. We demonstrate that many existing PCA and MCA learning algorithms are special cases of this class, and this class includes some new and simpler MCA learning algorithms. Our results show that all the learning algorithms of this class have the same order of convergence speed, and they are robust to implementation error.

Many multimedia communication applications require a source to send multimedia information to multiple destinations through a communication network. To support these applications, it is necessary to determine a multicast tree of minimal cost to connect the source node to the destination nodes subject to delay constraints on multimedia communication. This problem is known as multimedia multicast routing and has been proved to be NP-complete. The paper proposes an orthogonal genetic algorithm for multimedia multicast routing. Its salient feature is to incorporate an experimental design method called orthogonal design into the crossover operation. As a result, it can search the solution space in a statistically sound manner and it is well suited for parallel implementation and execution. We execute the orthogonal genetic algorithm to solve two sets of benchmark test problems. The results indicate that for practical problem sizes, the orthogonal genetic algorithm can find near optimal solutions within moderate numbers of generations.

The one-unit Oja algorithm plays a very important role in the study of principal component analysis neural networks. In this paper, we propose an energy function whose steepest descent direction (i.e., negative gradient direction) is the same as the average evolution direction of the one-unit Oja algorithm, and the energy function has two global minimal points corresponding to the two converged points of the one-unit Oja algorithm and it has no other local minimal points.