Dependency Structure Matrix Genetic algorithm-II (DSMGA-II) is a recently proposed optimization method that builds the linkage model on the base of the Dependency Structure Matrix (DSM). This model is used during the ...
详细信息
ISBN:
(纸本)9781450371285
Dependency Structure Matrix Genetic algorithm-II (DSMGA-II) is a recently proposed optimization method that builds the linkage model on the base of the Dependency Structure Matrix (DSM). This model is used during the Optimal Mixing (OM) operators, such as the Restricted Mixing (RM) and the Back Mixing (BM). DSMGA-II was shown to solve theoretical and real-world optimization problems effectively. In this paper, we show that the effectiveness of DSMGA-II and its improved version, namely Two-edge Dependency Structure Matrix Genetic algorithm-II (DSMGA-IIe), is relatively low for NK-landscape problems. Thus, we propose the Comparative Mixing (CM) operator that extends the RM operator. The CM operator modifies the linkage information obtained from the DSM-based linkage model by comparing the receiver individual with a randomly selected member of the population. Such modification enables DSMGA-II to solve NK-landscape problems effectively and does not limit DSMGA-II performance on most problems for which it was already shown effective.
In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distributionalgorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceivingLeadingBlocks (DLB) pro...
详细信息
ISBN:
(数字)9783030436803
ISBN:
(纸本)9783030436797;9783030436803
In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distributionalgorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceivingLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most lambda(n(2) +2e ln n) fitness evaluations. Since an offspring population size lambda of order n log n can prevent genetic drift, the UMDA can solve the DLB problem with O(n(2) log n) fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than O(n(3)) is known, so our result rather suggests that the UMDA can cope well with deception and epistatis. Together with the result of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.
Linkage learning is frequently employed in modern evolutionary algorithms. High linkage quality may be the key to an evolutionary method's effectiveness. Similarly, the faulty linkage may be the reason for its poo...
详细信息
ISBN:
(纸本)9781450371285
Linkage learning is frequently employed in modern evolutionary algorithms. High linkage quality may be the key to an evolutionary method's effectiveness. Similarly, the faulty linkage may be the reason for its poor performance. Many state-of-the-art evolutionary methods use a Dependency Structure Matrix (DSM) to obtain linkage. In this paper, we propose a quality measure for DSM. Based on this measure, we analyze the behavior of modern evolutionary methods. We show the dependency between the linkage and the effectiveness of the considered methods. Finally, we propose a framework that improves the quality of the linkage.
We prove that the compact genetic algorithm (cGA) with hypothetical population size mu = Omega(root n log n) boolean AND poly(n) with high probability finds the optimum of any n-dimensional jump function with jump siz...
详细信息
ISBN:
(纸本)9781450361118
We prove that the compact genetic algorithm (cGA) with hypothetical population size mu = Omega(root n log n) boolean AND poly(n) with high probability finds the optimum of any n-dimensional jump function with jump size k < 1/20 In n in O(mu root n) iterations. Since it is known that the cGA with high probability needs at least Omega(mu root n +n log n) iterations to optimize the unimodal ONEMAX function, our result shows that the cGA in contrast to most classic evolutionary algorithms here is able to cross moderate-sized valleys of low fitness at no extra cost. Our runtime guarantee improves over the recent upper bound 0(mu n(1.5) log n) valid for mu= Omega(n(3.5+epsilon)) of Hasenohrl and Sutton (GECCO 2018). For the best choice of the hypothetical population size, this result gives a runtime guarantee of O(n(5+epsilon)), whereas ours gives O(n log n). We also provide a simple general method based on parallel runs that, under mild conditions, (i) overcomes the need to specify a suitable population size, but gives a performance close to the one stemming from the best-possible population size, and (ii) transforms EDAs with high-probability performance guarantees into EDAs with similar bounds on the expected runtime.
DSMGA-II, a model-based genetic algorithm, is capable of solving optimization problems via exploiting sub-structures of the problem. In terms of number of function evaluations (NFE), DSMGA-II has shown superior optimi...
详细信息
ISBN:
(纸本)9781450349208
DSMGA-II, a model-based genetic algorithm, is capable of solving optimization problems via exploiting sub-structures of the problem. In terms of number of function evaluations (NFE), DSMGA-II has shown superior optimization ability to LT-GOMEA and hBOA on various benchmark problems as well as real-world problems. This paper proposes a two-edge graphical linkage model, which customizes recombination masks for each receiver according to its alleles, to further improve the performance of DSMGA-II. The new linkage model is more expressive than the original dependency structure matrix (DSM), providing far more possible linkage combinations than the number of solutions in the search space. To reduce unnecessary function evaluations, the two-edge model is used along with the supply bounds from the original DSM. Some new techniques are also proposed to enhance the model selection efficiency. Combining these proposed techniques, the empirical results show an average of 12.2% NFE reduction on eight benchmark problems compared with the original DSMGA-II.
This paper proposes a new evolutionary algorithm, called DSMGA-II, to efficiently solve optimization problems via exploiting problem substructures. The proposed algorithm adopts pairwise linkage detection and stores t...
详细信息
ISBN:
(纸本)9781450334723
This paper proposes a new evolutionary algorithm, called DSMGA-II, to efficiently solve optimization problems via exploiting problem substructures. The proposed algorithm adopts pairwise linkage detection and stores the information in the form of dependency structure matrix (DSM). A new linkage model, called the incremental linkage set, is then constructed by using the DSM. Inspired by the idea of optimal mixing, the restricted mixing and the back mixing are proposed. The former aims at efficient exploration under certain constrains. The latter aims at exploitation by refining the DSM so as to reduce unnecessary evaluations. Experimental results show that DSMGA-II outperforms LT-GOMEA and hBOA in terms of number of function evaluations on the concatenated/folded/cyclic trap problems, NK-landscape problems with various degrees of overlapping, 2D Ising spin-glass problems, and MAX-SAT. The investigation of performance comparison with P3 is also included.
We consider the problem of high dimensional black-box optimisation via estimation of distributionalgorithms (EDA). The Gaussian distribution is commonly used as a search operator in most of the EDA methods. However t...
详细信息
ISBN:
(纸本)9781479942749
We consider the problem of high dimensional black-box optimisation via estimation of distributionalgorithms (EDA). The Gaussian distribution is commonly used as a search operator in most of the EDA methods. However there are indications in the literature that heavy tailed distributions may perform better due to their higher exploration capabilities. Univariate heavy tailed distributions were already proposed for high dimensional problems. In 2D problems it has been reported that a multivariate heavy tailed (such as Cauchy) search distribution is able to blend together the strengths of multivariate modelling with a high exploration power. In this paper, we study whether a similar scheme would work well in high dimensional search problems. To get around of the difficulty of multivariate model building in high dimensions we employ a recently proposed random projections (RP) ensemble based approach which we modify to get samples from a multivariate Cauchy using the scale-mixture representation of the Cauchy distribution. Our experiments show that the resulting RP-based multivariate Cauchy EDA consistently improves on the performance of the univariate Cauchy search distribution. However, intriguingly, the RP-based multivariate Gaussian EDA has the best performance among these methods. It appears that the highly explorative nature of the multivariate Cauchy sampling is exacerbated in high dimensional search spaces and the population based search loses its focus and effectiveness as a result. Finally, we present an idea to increase exploration while maintaining exploitation and focus by using the RP-based multivariate Gaussian EDA in which the RP matrices are drawn with i.i.d. heavy tailed entries. This achieves improved performance and is competitive with the state of the art.
In this paper, a novel hybrid evolutionary algorithm combining a Hopfield net and a local search strategy is proposed to solve maximum clique problem. The algorithm makes full use of powerful searching capability of H...
详细信息
ISBN:
(纸本)9781479938414
In this paper, a novel hybrid evolutionary algorithm combining a Hopfield net and a local search strategy is proposed to solve maximum clique problem. The algorithm makes full use of powerful searching capability of Hopfield net and probabilistic statistic feature of estimation of distributionalgorithm to produce wider search in global solution domain. In particular, a possible extension way correlated with local search optimization is introduced to affect the mutation probability thus to produce guided evolution. Experiments on the popular DIMACS benchmark demonstrate that the hybrid evolutionary algorithm produces comparable and better results than other compared algorithms, including EA/G which is a state-of-the-art algorithm in the field of evolutionary computation.
In this paper, we address a user scheduling (selection) problem in the uplink multiuser multiple input multiple output (MIMO) wireless communication system. For this problem, the computational complexity of exhaustive...
详细信息
In this paper, we address a user scheduling (selection) problem in the uplink multiuser multiple input multiple output (MIMO) wireless communication system. For this problem, the computational complexity of exhaustive search grows exponentially with the number of users. We present an iterative, low-complexity, sub-optimal algorithm for this problem. We apply an estimation of distributionalgorithm (EDA) for the user scheduling problem. An EDA is an evolutionary algorithm and updates its chosen population at each iteration on the basis of the probability distribution learned from the population of superior candidate solutions chosen at the previous iterations. The proposed EDA has a low computational complexity and can find a nearly optimal solution in real time for the user scheduling problem. Beyond applying the general EDA to user scheduling, we also present specific improvements that reduce computation for obtaining an acceptable solution. These improvements include the idea of generating an initial population by cyclically shifting a candidate solution. The simulation results show that our proposed algorithm performs better than other scheduling algorithms with comparable complexity.
estimation-of-distribution algorithm using Cauchy sampling distribution is compared with the iterative prototype optimization algorithm with evolved improvement steps. While Cauchy EDA is better on unimodal functions,...
详细信息
ISBN:
(纸本)9781450300735
estimation-of-distribution algorithm using Cauchy sampling distribution is compared with the iterative prototype optimization algorithm with evolved improvement steps. While Cauchy EDA is better on unimodal functions, iterative prototype optimization is more suitable for multimodal functions. This paper compares the results for both algorithms in more detail and adds to the understanding of their key features and differences.
暂无评论