Search

Layout synthesis, an important step in quantum computing, processes quantum circuits to satisfy device layout constraints. In this paper, we construct QUEKO benchmarks for this problem, which have known optimal depths and gate counts. We use QUEKO to evaluate the optimality of current layout synthesis tools, including Cirq from Google, Qiskit from IBM, ⟨t|ket〉 from Cambridge Quantum Computing, and a recent academic work. To our surprise, despite over a decade of research and development by academia and industry on compilation and synthesis for quantum circuits, we are still able to demonstrate large optimality gaps: 1.5-12x on average on a smaller device and 5-45x on average on a larger device. This suggests substantial room for improvement of the efficiency of quantum computer by better layout synthesis tools. Finally, we also prove the NP-completeness of the layout synthesis problem for quantum computing. We have made the QUEKO benchmarks open-source. [ABSTRACT FROM AUTHOR]

To overcome the absence of concrete supervisory signals, deep clustering models construct their own labels based on self-supervision and pseudo-supervision. However, applying these techniques can cause Feature Randomness and Feature Drift. In this paper, we formally characterize these two new concepts. On one hand, Feature Randomness takes place when a considerable portion of the pseudo-labels is deemed to be random. In this regard, the trained model can learn non-representative features. On the other hand, Feature Drift takes place when the pseudo-supervised and the reconstruction losses are jointly minimized. While penalizing the reconstruction loss aims to preserve all the inherent data information, optimizing the embedded-clustering objective drops the latent between-cluster variances. Due to this compromise, the clustering-friendly representations can be easily drifted. In this context, we propose ADEC (Adversarial Deep Embedded Clustering) a novel autoencoder-based clustering model, which relies on a discriminator network to reduce random features while avoiding the drifting effect. Our new metrics $\Delta _{FR}$ Δ F R and $\Delta _{FD}$ Δ F D allows to, respectively, assess the level of Feature Randomness and Feature Drift. We empirically demonstrate the suitability of our model on handling these problems using benchmark real datasets. Experimental results validate that our model outperforms state-of-the-art autoencoder-based clustering methods. [ABSTRACT FROM AUTHOR]

Benchmarking provides an essential ground base for adequately assessing and comparing evolutionary computation methods and other optimization algorithms. It allows us to gain insights into strengths and weaknesses of different existing techniques, and consequently design more efficient optimization approaches. The need for good benchmarking practices opens up a broad range of complementary research questions, arising as a byproduct of challenges encountered when optimization methods are assessed. From the selection of representative benchmark problem instances, different algorithms, and suitable performance metrics, over efficient experimentation, to a sound evaluation of the benchmark data, these research questions lie at the core of establishing a well-designed and standardized benchmarking procedure. [ABSTRACT FROM AUTHOR]

Diversity preservation is a crucial technique in multiobjective evolutionary algorithms (MOEAs), which aims at evolving the population toward the Pareto front (PF) with a uniform distribution and a good extensity. In spite of many diversity preservation approaches in existing MOEAs, most of them encounter difficulties in tackling complex PFs. This article gives a detail introduction to existing diversity preservation approaches, as well as a revelation of the limitations of them. To address the limitations of existing diversity preservation approaches, this article proposes a multistage MOEA for better diversity performance. The proposed MOEA divides the optimization process into multiple stages according to the population in each generation, and updates the population by different steady-state selection schemes in different stages. According to the experimental results on 21 benchmark problems, the proposed MOEA exhibits better diversity performance than 11 existing MOEAs. [ABSTRACT FROM AUTHOR]

Traditionally, visualizing benchmark problems is an integral task in the domain of evolutionary algorithms development. Researchers get inspired for new search heuristics by challenges observed in functional landscapes. Moreover, landscape characteristics, features, and even terminology to describe them are derived from visualizations. And most importantly, benchmark designers need visualizations for identifying diverse problems that potentially challenge different aspects of optimization algorithms. As easy as it is to visualize single-objective problems, until recently there were hardly any approaches for gaining similar insights for multi-objective problems. Also, there have been no seamlessly accessible tools to support such visualizations. This article presents a comprehensive overview of the available visualization techniques from literature, including two interactive techniques to visualize 3-D problems, as well as two novel techniques which are suitable to scale some visualization properties to even higher-dimensional spaces. All presented techniques are integrated into a single tool, the moPLOT-dashboard, which enables users to perform landscape analyses in an interactive manner. Finally, the value of the tool and the visualizations is demonstrated in a series of usage scenarios on well-known benchmark problems. [ABSTRACT FROM AUTHOR]

This work assesses the efficacy of evolutionary algorithms (EAs) using an intuitive multidimensional scaling (MDS) visualization of the evolution of a population. We propose the use of landmark MDS (LMDS) to overcome computational challenges inherent to visualizing many-objective and complex problems with MDS. For the benchmark problems we tested, LMDS is akin to MDS visually, whilst requiring less than 1% of the time and memory necessary to produce an MDS visualization of the same objective space solutions, leading to the possibility of online visualizations for multi- and many-objective optimization evaluation. Using multi- and many-objective problems from the DTLZ and WFG benchmark test suites, we analyze how Landmark MDS visualizations can offer far greater insight into algorithm performance than using traditional algorithm performance metrics such as hypervolume alone, and can be used to complement explicit performance metrics. Ultimately, this visualization allows the visual identification of problem features and assists the decision maker in making intuitive recommendations for algorithm parameters/operators for creating and testing better EAs to solve multi- and many-objective problems. [ABSTRACT FROM AUTHOR]

The divide-and-conquer strategy has been widely used in cooperative co-evolutionary algorithms to deal with large-scale global optimization problems, where a target problem is decomposed into a set of lower-dimensional and tractable subproblems to reduce the problem complexity. However, such a strategy usually demands a large number of function evaluations to obtain an accurate variable grouping. To address this issue, a merged differential grouping (MDG) method is proposed in this article based on the subset–subset interaction and binary search. In the proposed method, each variable is first identified as either a separable variable or a nonseparable variable. Afterward, all separable variables are put into the same subset, and the nonseparable variables are divided into multiple subsets using a binary-tree-based iterative merging method. With the proposed algorithm, the computational complexity of interaction detection is reduced to $O(\max \{n,n_{ns}\times \log _{2} k\})$ , where $n$ , $n_{ns}(\leq n)$ , and $k(< n)$ indicate the numbers of decision variables, nonseparable variables, and subsets of nonseparable variables, respectively. The experimental results on benchmark problems show that MDG is very competitive with the other state-of-the-art methods in terms of efficiency and accuracy of problem decomposition. [ABSTRACT FROM AUTHOR]

Handling nonlinear constraints in continuous optimization is challenging, and finding a feasible solution is usually a difficult task. In the past few decades, various techniques have been developed to deal with linear and nonlinear constraints. However, reaching feasible solutions has been a challenging task for most of these methods. In this article, we adopt the framework of estimation of distribution algorithms (EDAs) and propose a new algorithm (EDA++) equipped with some mechanisms to deal with nonlinear constraints. These mechanisms are associated with different stages of the EDA, including seeding, learning, and mapping. It is shown that, besides increasing the quality of the solutions in terms of objective values, the feasibility of the final solutions is guaranteed if an initial population of feasible solutions is seeded to the algorithm. The EDA with the proposed mechanisms is applied to two suites of benchmark problems for constrained continuous optimization and its performance is compared with some state-of-the-art algorithms and constraint-handling methods. Conducted experiments confirm the speed, robustness, and efficiency of the proposed algorithm in tackling various problems with linear and nonlinear constraints. [ABSTRACT FROM AUTHOR]

Multiobjective optimization evolutionary algorithms (MOEAs) have received significant achievements in recent years. However, they encounter many difficulties in dealing with many-objective optimization problems (MaOPs) due to the weak selection pressure. One possible way to improve the ability of MOEAs for these MaOPs is to balance the convergence and diversity in the high-dimensional objective space. Based on this consideration, this article proposes a novel generic two-stage (TS) framework for MaOPs. The entire evolutionary search process is divided into two stages: in the first stage, a new subregion dominance and a modified subregion density-based mating selection mainly purse the convergence and in the second stage, a novel level-based Pareto dominance cooperates with the traditional Pareto dominance that mainly promotes diversity. Integrated into NSGA-II, the TS NSGA-II, referred to as TS-NSGA-II, is proposed. To extensively evaluate the performance of our approach, 29 benchmark problems were used as the test suite. The experimental results demonstrate our approach obtained superior or competitive performance compared with eight state-of-the-art many-objective optimization evolutionary algorithms. To study its generality, the proposed TS strategy was also combined with four other advanced methods for MaOPs. The results show that it can also improve the performance of these four methods in terms of convergence and diversity. [ABSTRACT FROM AUTHOR]

When a fuzzy system is presented with an incomplete (or sparse) rule base, fuzzy rule interpolation (FRI) offers a useful mechanism to infer conclusions for unmatched observations. However, most existing FRI methodologies are established for Mamdani inference models, but not for Takagi–Sugeno–Kang (TSK) ones. This article presents a novel approach for computing interpolated outcomes with TSK models, using only a small number of neighboring rules to an unmatched observation. Compared with existing methods, the new approach helps improve the computational efficiency of the overall interpolative reasoning process, while minimizing the adverse impact on accuracy induced by firing those rules of low similarities with the new observation. For problems that involve a rule base of a large size, where closest neighboring rules may be rather alike to one another, a rule-clustering-based method is introduced. It derives an interpolated conclusion by first clustering rules into different groups with a clustering algorithm and then, by utilizing only those rules that are each selected from one of a given, small number of closest rule clusters. Systematic experimental examinations are carried out to verify the efficacy of the introduced techniques, in comparison with state-of-the-art methods, over a range of benchmark regression problems, while employing different clustering algorithms (which also shows the flexibility in ways of implementing the novel approach). [ABSTRACT FROM AUTHOR]

Adaptive boosting (AdaBoost) is a widely used technique to construct a stronger ensemble classifier by combining a set of weaker ones. Zero-order fuzzy inference systems (FISs) are very powerful prototype-based predictive models for classification, offering both great prediction precision and high user interpretability. However, the use of zero-order FISs as base classifiers in AdaBoost has not been explored yet. To bridge the gap, in this article, a novel multiclass fuzzily weighted AdaBoost (FWAdaBoost)-based ensemble system with a self-organizing fuzzy inference system (SOFIS) as the ensemble component is proposed. To better incorporate the SOFIS, FWAdaBoost utilizes the confidence scores produced by the SOFIS in both sample weight updating and ensemble output generation, resulting in more accurate classification boundaries and greater prediction precision. Numerical examples on a wide range of benchmark classification problems demonstrate the efficacy of the proposed approach. [ABSTRACT FROM AUTHOR]

Random forest (RF) is a type of ensemble-based machine learning method that has been applied to a variety of machine learning tasks in recent years. This article proposes an evolutionary approach to generate an oblique RF for regression problems. More specifically, our method induces an oblique RF by transforming the original feature space to a new feature space through the evolutionary feature construction method. To speed up the searching process, the proposed method evaluates each set of features based on a decision tree (DT) rather than an RF. In order to obtain an RF, we archive top-performing features and corresponding trees during the search. In this way, both the features and the forest can be constructed simultaneously in a single run. The proposed evolutionary forest is applied to 117 benchmark problems with different characteristics and compared with some state-of-the-art regression methods, including several variants of the RF and gradient boosted DTs (GBDTs). The experimental results suggest that the proposed method outperforms the existing RF and GBDT methods. [ABSTRACT FROM AUTHOR]

Knowledge transfer plays a vastly important role in solving multitask optimization problems (MTOPs). Many existing methods transfer task-specific knowledge, such as the high-quality solution from one task to other tasks to enhance the optimization ability, which, however, may not work well or even have a negative effect if the tasks have very different task-specific knowledge. Hence, this article proposes a meta-knowledge transfer (MKT)-based differential evolution (MKTDE) algorithm by using a more general MKT method to solve MTOPs more efficiently. The meta-knowledge defined in this article refers to the knowledge that can evolve task-specific knowledge during the evolutionary search. That is, the meta-knowledge is a kind of “knowledge of knowledge,” which denotes the knowledge of “how to solve problem via evolution” and “the feature/way/method of evolving high-quality solution.” The evolutionary search for solving different tasks can share common meta-knowledge even though these tasks involve heterogeneous data and have very different task-specific knowledge. Therefore, the MKT can associate the heterogeneous multisource data of different tasks via transferring the meta-knowledge to help solve MTOPs more efficiently in a more general way. Moreover, to further enhance the MKTDE, two novel and efficient methods are proposed. One is multiple populations for the multiple tasks framework using a unified search space for making knowledge transfer flexibly. The other is an elite solution transfer method for achieving positive high-quality solution transfer. The superior performance of the proposed MKTDE is verified via extensive numerical experiments on both widely used MTOP benchmark problems and real-world robot navigation problems, with comparisons with some state-of-the-art and the latest well-performing algorithms. [ABSTRACT FROM AUTHOR]

Cyber-physical systems (CPSs) are complex and exhibit both continuous and discrete dynamics, hence it is difficult to guarantee that they satisfy given specifications, i.e., the properties that must be fulfilled by the system. Falsification of temporal logic properties is a testing approach that searches for counterexamples of a given specification that can be used to increase the confidence that a CPS does fulfill its specifications. Falsification can be done using random search methods or optimization methods, both of which have their own benefits and drawbacks. This article introduces two methods that exploit randomness to different degrees: 1) the optimization-free Hybrid-Corner-Random (HCR) and 2) the direct-search method Line-Search Falsification (LSF). HCR combines randomly chosen parameter values with extreme parameter values, which performs surprisingly well on benchmark evaluations. The gradient-free optimization-based LSF optimizes over line segments through a vector of inputs in the $n$ -dimensional parameter space. The two methods are compared to the Nelder-Mead and SNOBFIT methods, using a well-known set of benchmark problems and LSF shows better performance than any of the evaluated methods. [ABSTRACT FROM AUTHOR]

Surrogate-assisted evolutionary algorithms (SAEAs) are well suited for computationally expensive optimization. However, most existing SAEAs only focus on low- or medium-dimensional expensive optimization. Thus, a novel SAEA for high-dimensional expensive optimization, denoted as surrogate-assisted multipopulation particle swarm optimizer (SA-MPSO), is proposed and fully investigated in this work. The proposed algorithm employs a parameter-free clustering technique, denoted as affinity propagation clustering, to generate several subswarms. A surrogate-assisted learning strategy-based particle swarm optimizer is proposed for guiding the search of each subswarm. Furthermore, a model management strategy is adapted to choose the promising particles for real fitness evaluations. Finally, a subswarm diversity maintenance scheme and a surrogate-based trust region local search technique are introduced to enhance both exploration and exploitation. The experimental results on commonly used benchmark test problems with dimensions varying from 30 to 100 and airfoil design problem have shown that SA-MPSO outperforms some state-of-the-art methods. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Solving constrained multiobjective optimization problems brings great challenges to an evolutionary algorithm, since it simultaneously requires the optimization among several conflicting objective functions and the satisfaction of various constraints. Hence, how to adjust the tradeoff between objective functions and constraints is crucial. In this article, we propose a dynamic selection preference-assisted constrained multiobjective differential evolutionary (DE) algorithm. In our approach, the selection preference of each individual is suitably switching from the objective functions to constraints as the evolutionary process. To be specific, the information of objective function, without considering any constraints, is extracted based on Pareto dominance to maintain the convergence and diversity by exploring the feasible and infeasible regions; while the information of constraint is used based on constrained dominance principle to promote the feasibility. Then, the tradeoff in these two kinds of information is adjusted dynamically, by emphasizing the utilization of objective functions at the early stage and focusing on constraints at the latter stage. Furthermore, to generate the promising offspring, two DE operators with distinct characteristics are selected as components of the search algorithm. Experiments on four test suites including 56 benchmark problems indicate that the proposed method exhibits superior or at least competitive performance, in comparison with other well-established methods. [ABSTRACT FROM AUTHOR]

Gaussian processes (GPs) are widely used in surrogate-assisted evolutionary optimization of expensive problems mainly due to the ability to provide a confidence level of their outputs, making it possible to adopt principled surrogate management methods, such as the acquisition function used in the Bayesian optimization. Unfortunately, GPs become less practical for high-dimensional multiobjective and many-objective optimization as their computational complexity is cubic in the number of training samples. In this article, we propose a computationally efficient dropout neural network (EDN) to replace the Gaussian process and a new model management strategy to achieve a good balance between convergence and diversity for assisting evolutionary algorithms to solve high-dimensional multiobjective and many-objective expensive optimization problems. While the conventional dropout neural network needs to save a large number of network models during the training for calculating the confidence level, only one single network model is needed in the EDN to estimate the fitness and its confidence level by randomly ignoring neurons in both training and testing the neural network. Extensive experimental studies on benchmark problems with up to 100 decision variables and 20 objectives demonstrate that, compared to state of the art, the proposed algorithm is not only highly competitive in performance but also computationally more scalable to high-dimensional many-objective optimization problems. Finally, the proposed algorithm is validated on an operational optimization problem of crude oil distillation units, further confirming its capability of handling expensive problems given a limited computational budget. [ABSTRACT FROM AUTHOR]

We propose a new surrogate-assisted evolutionary algorithm for expensive multiobjective optimization. Two classification-based surrogate models are used, which can predict the Pareto dominance relation and $\theta $ -dominance relation between two solutions, respectively. To make such surrogates as accurate as possible, we formulate dominance prediction as an imbalanced classification problem and address this problem using deep learning techniques. Furthermore, to integrate the surrogates based on dominance prediction with multiobjective evolutionary optimization, we develop a two-stage preselection strategy. This strategy aims to select a promising solution to be evaluated among those produced by genetic operations, taking proper account of the balance between convergence and diversity. We conduct an empirical study on a number of well-known multiobjective and many-objective benchmark problems, over a relatively small number of function evaluations. Our experimental results demonstrate the superiority of the proposed algorithm compared with several representative surrogate-assisted algorithms. [ABSTRACT FROM AUTHOR]

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

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