Quantum computers have made significant progress in the last two decades showing great potential in tackling some of the most challenging problems in computing. This ongoing progress creates an opportunity to implemen...
详细信息
Quantum computers have made significant progress in the last two decades showing great potential in tackling some of the most challenging problems in computing. This ongoing progress creates an opportunity to implement and evaluate quantum-inspired metaheuristics on real quantum devices, with the aim of uncovering potential computational advantages. Additionally, the practical constraints associated with current quantum computers have highlighted a critical need for classical heuristic methods to optimize the tunable parameters of quantum circuits. Nature-inspired metaheuristics have emerged as promising candidates for fulfilling this optimization role. In this paper, we discuss both of these potential directions at the intersection of evolutionary computing and quantum computing while surveying some of the most promising advancements in these directions. We start with the review of quantum-inspired metaheuristics and then explore implementations of some of these quantum-inspired algorithms on physical quantum devices, capitalizing on the progress in quantum computing technology. Furthermore, we investigate the role of nature-inspired metaheuristics in enhancing the performance of noisy intermediate-scale quantum computers by fine-tuning their parameters. Finally, we discuss some of the recent progress at the intersection of both computing frameworks to highlight the current status and potential of the currently available quantum computing hardware. Synergies between these two computing frameworks demonstrate the potential of a strongly symbiotic relation that can contribute to the simultaneous advancements in both of these computing paradigms.
Large-scale many-objective optimization problems (LSMaOPs) pose great difficulties for traditional evolutionary algorithms due to their slow search for Pareto-optimal solutions in huge decision space and struggle to b...
详细信息
Large-scale many-objective optimization problems (LSMaOPs) pose great difficulties for traditional evolutionary algorithms due to their slow search for Pareto-optimal solutions in huge decision space and struggle to balance diversity and convergence among numerous locally optimal solutions. An objective space linear inverse mapping method has successfully achieved great saving in execution time in solving LSMaOPs. Linear mapping is a fast and straightforward way, but fails to characterize a complex functional relationship. If we can enhance the expressive capacity of a mapping model, and further obtain a more general function approximator, can the evolutionary search based on objective space mapping be more efficient? To answer this interesting question, this work proposes to employ nonlinear activation functions widely used in neural networks so as to enhance the efficiency of objective space inverse mapping, thus efficiently generating excellent offspring population. A new evolutionary optimization framework based on decision variable analysis is proposed to solve LSMaOPs. In order to demonstrate its performance, this work carries out empirical experiments involving massive decision variables and many objectives. Experimental results prove its superiority over some representative and updated ones.
Distributed assembly permutation flowshop scheduling problem (DAPFSP) have aroused extensive interests in both academia and industry due to its wide range of applications in manufacturing systems. However, the existin...
详细信息
Distributed assembly permutation flowshop scheduling problem (DAPFSP) have aroused extensive interests in both academia and industry due to its wide range of applications in manufacturing systems. However, the existing literature on this topic is comparatively insufficient. This study investigated the considered problem with total flowtime (TF) criterion by developing three evolutionary algorithms (EAs) and their reinforcement learning (RL) based variants. First, two heuristic rules are proposed to initialize population with diversity. Second, six elaborated local search operators are incorporate with the basic EAs considering the problem's characteristics. Then, the RL algorithms e.g., Q-Learning and Sarsa, are employed to select high-quality local search operators during algorithms' iterations to improve their performance. Three problem characteristic based RL strategies are designed for mapping the RL algorithms and local search operators. Finally, detailed calibration according to 81 large-scale instances is performed to illustrate the effectiveness of the proposed algorithms for solving the DAPFSP.
Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized co...
详细信息
Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multi-objective algorithms for the W-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most W vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution OPT and W. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the W-separator uses linear programming methods and requires non-trivial post-processing steps to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the W-separator problem.
In this paper, we propose a method for solving a real-world timetabling problem at Mandarine Academy. The primary motivation for this work is to provide an automated professional course scheduling tool to replace the ...
详细信息
In this paper, we propose a method for solving a real-world timetabling problem at Mandarine Academy. The primary motivation for this work is to provide an automated professional course scheduling tool to replace the time-consuming task of manually creating timetables that are constantly incorrect. Following a review of both scientific literature and company requirements, a mathematical model of the problem is provided, which includes 18 constraints (hard/soft) and five objectives, two of which are competing. We test a handful of multi-objective evolutionary algorithms (MOEA's) starting with the non-dominated sorting genetic algorithm (NSGA II and NSGA III), the multi-objective evolutionary algorithm based on decomposition (MOEA/D), the indicator-based evolutionary algorithm and finally the strength Pareto evolutionary algorithm . Two custom genetic operators (mutation and crossover) are proposed and compared to conventional operators (PMX and swap mutation). To obtain elite configurations, a tuning phase involving all of the aforementioned algorithms is carried out. Experiments were divided by problem size, with three to five objectives tested. Experiments include the use of real-world data from the company's catalog. This dataset was made available to the scientific community to serve as a testing ground for professional course scheduling, an underexploited field of scheduling. We discuss findings, including a comparison of each algorithm's performance using various metrics, as well as convergence graphs and population evolution.
The present study hybridizes the new-generation evolutionary algorithms and the nonlinear regression technique for stream temperature modeling and compares this approach with conventional gray and black box approaches...
详细信息
The present study hybridizes the new-generation evolutionary algorithms and the nonlinear regression technique for stream temperature modeling and compares this approach with conventional gray and black box approaches under natural flow conditions, providing a comprehensive assessment. The nonlinear equation for water temperature modeling was optimized using biogeography-based optimization (BBO) and invasive weed optimization (IWO), simulated annealing algorithm (SA) and particle swarm optimization (PSO). Two black box approaches, a feedforward neural network (FNN) and a long short-term memory (LSTM) network, were also employed for comparison. Additionally, an adaptive neuro-fuzzy inference system (ANFIS) served as a gray box model for river thermal regimes. The models were evaluated based on accuracy, complexity, generality and interpretability. Performance metrics, such as the Nash-Sutcliffe efficiency (NSE), showed that the LSTM model achieved the highest accuracy (NSE = 0.96) but required significant computational resources. In contrast, evolutionary algorithm-based models offered acceptable performance while reducing the computational complexities of LSTM, with all models achieving NSE values above 0.5. Considering interpretability, accuracy and complexity, evolutionary-based nonlinear models are recommended for general applications, such as assessing thermal river habitats. For tasks requiring very high accuracy, the LSTM model is preferred, while ANFIS provides a balanced trade-off between accuracy and interpretability, making it suitable for engineers and ecologists. While all models demonstrate similar generality, this model is developed for a specific location. For other locations, independent models with a similar architecture would need to be developed. Ultimately, the choice of model depends on specific objectives and available resources.
The allocation of heterogeneous battlefield resources is crucial in Command and Control (C2). Balancing multiple competing objectives under complex constraints so as to provide decision-makers with diverse feasible ca...
详细信息
The allocation of heterogeneous battlefield resources is crucial in Command and Control (C2). Balancing multiple competing objectives under complex constraints so as to provide decision-makers with diverse feasible candidate decision schemes remains an urgent challenge. Based on these requirements, a constrained multi-objective multi-stage weapon-target assignment (CMOMWTA) model is established in this paper. To solve this problem, three constraint-feature-guided multi-objective evolutionary algorithms (CFG-MOEAs) are proposed under three typical multi-objective evolutionary frameworks (i.e., NSGA-II, NSGA-III, and MOEA/D) to obtain various high-quality candidate decision schemes. Firstly, a constraint-feature-guided reproduction strategy incorporating crossover, mutation, and repair is developed to handle complex constraints. It extracts common row and column features from different linear constraints to generate the feasible offspring population. Then, a variable-length integer encoding method is adopted to concisely denote the decision schemes. Moreover, a hybrid initialization method incorporating both heuristic methods and random sampling is designed to better guide the population. Systemic experiments are conducted on three CFG-MOEAs to verify their effectiveness. The superior algorithm CFG-NSGA-II among three CFG-MOEAs is compared with two state-of-the-art CMOMWTA algorithms, and extensive experimental results demonstrate the effectiveness and superiority of CFG-NSGA-II.
Doubly-stochastic matrices play a vital role in modern applications of complex networks such as tracking and decentralized state estimation, coordination and control of autonomous agents. A central theme in all of the...
详细信息
Doubly-stochastic matrices play a vital role in modern applications of complex networks such as tracking and decentralized state estimation, coordination and control of autonomous agents. A central theme in all of the above is consensus, that is, nodes reaching agreement about the value of an underlying variable (e.g. the state of the environment). Despite the fact that complex networks have been studied thoroughly, the communication graphs are usually described by symmetric matrices due to their advantageous theoretical properties. We do not yet have methods for optimizing generic doubly-stochastic matrices. In this paper, we propose a novel formulation and framework, EvoDSM, for achieving fast linear distributed averaging by: (a) optimizing the weights of a fixed graph topology, and (b) optimizing for the topology itself. We are concerned with graphs that can be described by positive doubly-stochastic matrices. Our method relies on swarm and evolutionary optimization algorithms and our experimental results and analysis showcase that our method (1) achieves comparable performance with traditional methods for symmetric graphs, (2) is applicable to non-symmetric network structures and edge weights, and (3) is scalable and can operate effectively with moderately large graphs without engineering overhead.
Quantum error correction and the use of quantum error correction codes are likely to be essential for the realization of practical quantum computing. Because the error models of quantum devices vary widely, quantum co...
详细信息
Quantum error correction and the use of quantum error correction codes are likely to be essential for the realization of practical quantum computing. Because the error models of quantum devices vary widely, quantum codes that are tailored for a particular error model may have much better performance. In this work, we present a novel evolutionary algorithm that searches for an optimal stabilizer code for a given error model, number of physical qubits, and number of encoded qubits. We demonstrate an efficient representation of stabilizer codes as binary strings, which allows for random generation of valid stabilizer codes as well as mutation and crossing of codes. Our algorithm finds stabilizer codes whose distance closely matches the best-known-distance codes of Grassl (2007) for n <= 20 physical qubits. We perform a search for optimal distance Calderbank-Steane-Shor codes and compare their distance to the best known codes. Finally, we show that the algorithm can be used to optimize stabilizer codes for biased error models, demonstrating a significant improvement in the undetectable error rate for [[12,1]](2) codes versus the best-known-distance code with the same parameters. As part of this work, we also introduce an evolutionary algorithm QDistEvol for finding the distance of quantum error correction codes.
暂无评论