This work proposes an algorithm called Node Based Coincidence algorithm (NB-COIN) focusing on total flowtime minimization in the permutation flowshop scheduling problems. Many algorithms have been proved to be effecti...
详细信息
ISBN:
(纸本)9781479908066;9781479908059
This work proposes an algorithm called Node Based Coincidence algorithm (NB-COIN) focusing on total flowtime minimization in the permutation flowshop scheduling problems. Many algorithms have been proved to be effective for this problem. However, in the real situation, cost of computation becomes an important factor. NB-COIN produces reasonable solutions using a lot less computation power than other algorithms in consideration. Compared to a number of well-known algorithms, the results show that NB-COIN is an effective algorithm which generates less than 1.7% different from recently best known solutions from Taillard's benchmark instances.
The hierarchical Bayesian optimization algorithm (hBOA) can solve nearly decomposable and hierarchical problems of bounded difficulty in a robust and scalable manner by building and sampling probabilistic models of pr...
详细信息
ISBN:
(纸本)9781595936974
The hierarchical Bayesian optimization algorithm (hBOA) can solve nearly decomposable and hierarchical problems of bounded difficulty in a robust and scalable manner by building and sampling probabilistic models of promising solutions. This paper analyzes probabilistic models in hBOA on two common test problems: concatenated traps and 2D Ising spin glasses with periodic boundary conditions. We argue that although Bayesian networks with local structures can encode complex probability distributions, analyzing these models in hBOA is relatively straightforward and the results of such analyses may provide practitioners with useful information about their problems. The results show that the probabilistic models in hBOA closely correspond to the structure of the underlying problem, the models do not change significantly in subsequent iterations of BOA, and creating adequate probabilistic models by hand is not straightforward even with complete knowledge of the optimization problem.
作者：
Pelikan, MartinUniv Missouri
Dept Math & Comp Sci Missouri Estimat Distribut Algorithms Lab St Louis MO 63121 USA
Epistasis correlation is a measure that estimates the strength of interactions between problem variables. This paper presents an empirical study of epistasis correlation on a large number of random problem instances o...
详细信息
ISBN:
(纸本)9781450305570
Epistasis correlation is a measure that estimates the strength of interactions between problem variables. This paper presents an empirical study of epistasis correlation on a large number of random problem instances of NK landscapes with nearest neighbor interactions. The results are analyzed with respect to the performance of hybrid variants of two evolutionary algorithms: (1) the genetic algorithm with uniform crossover and (2) the hierarchical Bayesian optimization algorithm.
The ability of Gaussian Process to flexibly and accurately fit arbitrary, even highly nonlinear data sets has lead to considerable interest in their application to many areas. Firstly, the usefulness of Gaussian Proce...
详细信息
ISBN:
(纸本)9781424473281
The ability of Gaussian Process to flexibly and accurately fit arbitrary, even highly nonlinear data sets has lead to considerable interest in their application to many areas. Firstly, the usefulness of Gaussian Process models for application to complex systems metamodeling is proposed. Secondly, several approaches for training Gaussian Process models are examined, which include local optimization algorithm, Genetic algorithms and estimation of distribution algorithms. The results of these training methods are compared for several example problems, and guidance is provided in GP training methods.
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.
This paper extends the Boltzmann Selection, a method in EDA with theoretical importance, from discrete domain to the continuous one. The difficulty of estimating the exact Boltzmann distribution in continuous state sp...
详细信息
ISBN:
(纸本)9781595931863
This paper extends the Boltzmann Selection, a method in EDA with theoretical importance, from discrete domain to the continuous one. The difficulty of estimating the exact Boltzmann distribution in continuous state space is circumvented by adopting the multivariate Gaussian model, which is popular in continuous EDA, to approximate only the final sampling distribution. With the minimum Kullback-Leibeler divergence principle, both the mean vector and the covariance matrix of the Gaussian model can be calibrated to preserve the features of Boltzmann selection reflecting desired selection pressure. A method is proposed to adapt the selection pressure based on measuring the successfulness of the past evolution process. These works established a formal basis that helps to build probabilistic models in continuous EDA algorithms with adaptive parameters. The framework is incorporated in both the continuous UMDA and the EMNA algorithm, and tested in several benchmark problems. The experiment results are compared with some existing EDA versions and the benefit of the proposed approach is discussed.
k-order Markov models have been introduced to estimation of distribution algorithms (EDAs) to solve a particular class of optimization problems in which each variable depends on its previous k variables in a given, fi...
详细信息
ISBN:
(纸本)9781450305570
k-order Markov models have been introduced to estimation of distribution algorithms (EDAs) to solve a particular class of optimization problems in which each variable depends on its previous k variables in a given, fixed order. In this paper we investigate the use of regularization as a way to approximate k-order Markov models when k is increased. The introduced regularized models are used to balance the complexity and accuracy of the k-order Markov models. We investigate the behavior of the EDAs in several instances of the hydrophobic-polar (HP) protein problem, a simplified protein folding model. Our preliminary results show that EDAs that use regularized approximations of the k-order Markov models offer a good compromise between complexity and efficiency, and could be an appropriate choice when the number of variables is increased.
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.
Bayesian Optimization Algorithm (BOA) has been used with different local structures to represent more complex models and a variety of scoring metrics to evaluate Bayesian network. But the combinatorial effects of thes...
详细信息
ISBN:
(纸本)9781605583266
Bayesian Optimization Algorithm (BOA) has been used with different local structures to represent more complex models and a variety of scoring metrics to evaluate Bayesian network. But the combinatorial effects of these elements on the performance of BOA have not been investigated yet. In this paper the performance of BOA is studied using two criteria: Number of fitness evaluations and structural accuracy of the model. It is shown that simple exact local structures like CPT in conjunction with complexity penalizing BIC metric outperforms others in terms of model accuracy. But considering number of fitness evaluations (efficiency) of the algorithm, CPT with other complexity penalizing metric K2P performs better.
暂无评论