In dynamic environments, the main aim of an optimization algorithm is to track the changes and to adapt the search process. In this paper, we propose an approach called the Bayesian Immigrant Diploid Genetic Algorithm...
详细信息
ISBN:
(数字)9783030457150
ISBN:
(纸本)9783030457150
In dynamic environments, the main aim of an optimization algorithm is to track the changes and to adapt the search process. In this paper, we propose an approach called the Bayesian Immigrant Diploid Genetic Algorithm (BIDGA). BIDGA uses implicit memory in the form of diploid chromosomes, combined with the Bayesian Optimization Algorithm (BOA), which is a form of estimation of distribution algorithms (EDAs). Through the use of BOA, BIDGA is able to take into account epistasis in the form of binary relationships between the variables. Experiments show that the proposed approach is efficient and also indicates that exploiting interactions between variables is important to adapt to the newly formed environments.
We propose and investigate new rotation gates for two modified Quantum Inspired Evolutionary methods for solving high dimension optimisation problems. The Quantum Inspired Evolutionary algorithms (QIEA) were originall...
详细信息
We propose and investigate new rotation gates for two modified Quantum Inspired Evolutionary methods for solving high dimension optimisation problems. The Quantum Inspired Evolutionary algorithms (QIEA) were originally used for solving binary encoded problems and their signature features follow superposition of multiple states on a quantum bit and a rotation gate. In order to apply this paradigm to high dimension problems, we propose two quantum methods Half Significant Bit (HSB) and Stepwise Real QEA (SRQEA), developed using binary and real encoding, respectively, while keeping close to the original quantum computing metaphor. We introduce five performance metrics and use them to evaluate the proposed approaches against sets of multimodal mathematical test functions and real world problems of high dimensionality. We report issues found while implementing some of the published real QIEA techniques which were the motivation for developing our real algorithm modifications. Our methods focus on introducing and implementing new rotation gate operators used for evolution, including a novel mechanism for preventing premature convergence in the binary algorithm. The applied performance metrics show superior results for our quantum methods on most of the test problems (particularly with high dimension problems), demonstrating faster convergence and accuracy. (C) 2017 Elsevier B.V. All rights reserved.
estimation of distribution algorithms (EDAs) are stochastic heuristics that search for optimal solutions by learning and sampling from probabilistic models. Despite their popularity in real-world applications, there i...
详细信息
estimation of distribution algorithms (EDAs) are stochastic heuristics that search for optimal solutions by learning and sampling from probabilistic models. Despite their popularity in real-world applications, there is little rigorous understanding of their performance. Even for the Univariate Marginal distribution Algorithm (UMDA)-a simple population-based EDA assuming independence between decision variables-the optimisation time on the linear problem OneMaxwas until recently undetermined. The incomplete theoretical understanding of EDAs is mainly due to the lack of appropriate analytical tools. We show that the recently developed level-based theorem for non-elitist populations combined with anti-concentration results yield upper bounds on the expected optimisation time of the UMDA. This approach results in the bound O(n lambda log lambda + n(2))on the LeadingOnes and BinVal problems for population sizes lambda > mu = Omega(log n), where mu and lambda are parameters of the algorithm. We also prove that the UMDA with population sizes mu is an element of O (root n) boolean AND Omega (log n) optimises OneMax in expected time O(lambda n), and for larger population sizes mu = Omega(root n log n), in expected time O (lambda root n) The facility and generality of our arguments suggest that this is a promising approach to derive bounds on the expected optimisation time of EDAs.
estimation of distribution algorithms (EDAs) maintain and iteratively update a probabilistic model to tackle optimization problems. The Boltzmann Probability distribution Function (Boltzmann-PDF) provides advantages w...
详细信息
estimation of distribution algorithms (EDAs) maintain and iteratively update a probabilistic model to tackle optimization problems. The Boltzmann Probability distribution Function (Boltzmann-PDF) provides advantages when used in energy based EDAs. However, direct sampling from the Boltzmann-PDF to update the probabilistic model is unpractical, and several EDAs employ an approximation to the Boltzmann-PDF by means of a Gaussian distribution that is usually derived by the minimization of the Kullback-Leibler divergence (KL-divergence) computed between the Gaussian and the Boltzmann-PDFs. The KL-divergence measure is not symmetric, and this causes the Gaussian approximation to fail at correctly modeling the target function for the EDAs, because the parameters of the Gaussian are not optimally estimated. In this paper, we derive an approximation to the Boltzmann-PDF using Jeffreys' divergence (a symmetric measure) in lieu of the KL-divergence and thus improve the performance of the optimization algorithm. Our approach is termed Symmetric-approximation Energy-based estimation of distribution (SEED) algorithm. The SEED algorithm is experimentally compared under a univariate approach against two other EDAs (UMDAc and BUMDA) on several benchmark optimization problems. The results show that the SEED algorithm is more effective and more efficient than the other algorithms.
The Hybrid Multi-objective Bayesian estimation of distribution Algorithm (HMOBEDA) has shown to be very competitive for Many Objective Optimization Problems (MaOPs). The Probabilistic Graphic Model (PGM) of HMOBEDA ex...
详细信息
The Hybrid Multi-objective Bayesian estimation of distribution Algorithm (HMOBEDA) has shown to be very competitive for Many Objective Optimization Problems (MaOPs). The Probabilistic Graphic Model (PGM) of HMOBEDA expands the possibilities for exploration as it provides the joint probability of decision variables, objectives, and configuration parameters of an embedded local search. This work investigates different sampling mechanisms of HMOBEDA, applying the considered approaches to two different combinatorial MaOPs. Moreover, the paper provides a broad set of statistical analyses on its PGM model. These analyses have been carried out to evaluate how the interactions among variables, objectives and local search parameters are captured by the model and how information collected from different runs can be aggregated and explored in a Probabilistic Pareto Front. In experiments, two variants of HMOBEDA are compared with the original version, each one with a different set of evidences fixed during the sampling process. Results for instances of multi-objective knapsack problem with 2-5 and 8 objectives show that the best variant outperforms the original HMOBEDA in terms of convergence and diversity in the solution set. This best variant is then compared with five state-of-the-art evolutionary algorithms using the knapsack problem instances as well as a set of MNK-landscape instances with 2, 3, 5 and 8 objectives. HMOBEDA outperforms all of them.
In this paper, we developed an evolutionary algorithm with guided mutation (EA/G) based hyper-heuristic for solving the job-shop scheduling problem with no-wait constraint (JSPNW). The JSPNW is an extension of well-kn...
详细信息
ISBN:
(纸本)9789811307614;9789811307607
In this paper, we developed an evolutionary algorithm with guided mutation (EA/G) based hyper-heuristic for solving the job-shop scheduling problem with no-wait constraint (JSPNW). The JSPNW is an extension of well-known job-shop scheduling problem subject to the constraint that no waiting time is allowed between operations for a given job. This problem is a typical NP-hard problem. The hyper-heuristic algorithm comprises of two level frameworks. In the high-level, an evolutionary algorithm is employed to explore the search space. The low-level, which is comprised of generic as well as problem-specific heuristics such as guided mutation, multi-insert points and multi-swap. EA/G is a recent addition to the class of evolutionary algorithm that can be considered as a hybridization of genetic algorithms (GAs) and estimation of distribution algorithms (EDAs), and which tries to overcome the shortcomings of both. In GAs, the location information of the solutions found so far is directly used to generate offspring. On the other hand, EDAs use global statistical information to generate new offspring. In EDAs the global statistical information is stored in the form probability vector, and a new offspring is generated by sampling this probability vector. We have compared our approach with the state-of-the-art approaches. The computational results show the effectiveness of our approach.
Model-based evolutionary algorithms (MBEAs) are praised for their broad applicability to black-box optimization problems. In practical applications however, they are mostly used to repeatedly optimize different instan...
详细信息
ISBN:
(纸本)9781450367486
Model-based evolutionary algorithms (MBEAs) are praised for their broad applicability to black-box optimization problems. In practical applications however, they are mostly used to repeatedly optimize different instances of a single problem class, a setting in which specialized algorithms generally perform better. In this paper, we introduce the concept of a new type of MBEA that can automatically specialize its behavior to a given problem class using tabula rasa self-learning. For this, reinforcement learning is a naturally fitting paradigm. A proof-of-principle framework, called SL-ENDA, based on estimation of normal distributionalgorithms in combination with reinforcement learning is defined. SL-ENDA uses an RL-agent to decide upon the next population mean while approaching the rest of the algorithm as the environment. A comparison of SL-ENDA to AMaLGaM and CMA-ES on unimodal noiseless functions shows mostly comparable performance and scalability to the broadly used and carefully manually crafted algorithms. This result, in combination with the inherent potential of self-learning model-based evolutionary algorithms with regard to specialization, opens the door to a new research direction with great potential impact on the field of model-based evolutionary algorithms.
Genetic algorithms using optimal mixing have shown promising results, while lack of theoretical supports. This paper investigates population sizing from the supply aspect under the optimal mixing scenario. Specificall...
详细信息
ISBN:
(纸本)9781450361118
Genetic algorithms using optimal mixing have shown promising results, while lack of theoretical supports. This paper investigates population sizing from the supply aspect under the optimal mixing scenario. Specifically, more precise analyses on supply, including the expectation and the lower bound, are made. In addition, considering recombining one randomly generated chromosome with the rest of the population to achieve the global optimum, the tight bounds of the size of the population providing proper fragments chosen by restricted oracles are derived. Tight bounds on problems with ring topologies where a subfunction overlaps two other subfunctions are also derived. Finally, experiments are conducted and well match the derivations.
In this paper we evaluate a new estimation of distribution Algorithm (EDA) constructed on top of a very successful Bayesian network learning procedure, Max-Min Hill-Climbing (MMHC). The aim of this paper is to check w...
详细信息
ISBN:
(纸本)9783030011321;9783030011314
In this paper we evaluate a new estimation of distribution Algorithm (EDA) constructed on top of a very successful Bayesian network learning procedure, Max-Min Hill-Climbing (MMHC). The aim of this paper is to check whether the excellent properties reported for this algorithm in machine learning papers, have some impact on the efficiency and efficacy of EDA based optimization. Our experiments show that the proposed algorithm outperform wellknown state of the art EDA like BOA and EBNA in a test bed based on B-functions. On the basis of these results we conclude that the proposed scheme is a promising candidate for challenging real-world applications, specifically, problems related to the areas of Data Mining, Patter Recognition and Artificial Intelligence.
The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial optimization problem, which is of great significance in both theory and application. Evolutionary algorithms and local search algorithms have...
详细信息
ISBN:
(纸本)9783030368081;9783030368074
The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial optimization problem, which is of great significance in both theory and application. Evolutionary algorithms and local search algorithms have proved to be two important methods to solve this problem. However, the combination of these two methods does not perform well. In order to acquire an effective hybrid evolutionary algorithm, two new control strategies are proposed, which are taboo of solution-distance and intensive competition of individuals. A hybrid evolutionary algorithm for the MVC problem, referred to HETC, is proposed in this paper using these two strategies. The effectiveness of the proposed scheme is validated by conducting deep simulations. The results obtained by the proposed scheme are compared with results obtained by EWSL, the state-of-the-art algorithm, and NuMVC.
暂无评论