linkage tree genetic algorithm (LTGA) is an effective Evolutionary algorithm (EA) to solve complex problems using the linkage information between problem variables. LTGA performs well in various kinds of single-task o...
详细信息
linkage tree genetic algorithm (LTGA) is an effective Evolutionary algorithm (EA) to solve complex problems using the linkage information between problem variables. LTGA performs well in various kinds of single-task optimization and yields promising results in comparison with the canonical geneticalgorithm. However, LTGA is an unsuitable method for dealing with multi-task optimization problems. On the other hand, Multifactorial Optimization (MFO) can simultaneously solve independent optimization problems, which are encoded in a unified representation to take advantage of the process of knowledge transfer. In this paper, we introduce geneticalgorithm (MF-LTGA) by combining the main features of both LTGA and MFO. MF-LTGA is able to tackle multiple optimization tasks at the same time, each task learns the dependency between problem variables from the shared representation. This knowledge serves to determine the high-quality partial solutions for supporting other tasks in exploring the search space. Moreover, MF-LTGA speeds up convergence because of knowledge transfer of relevant problems. We demonstrate the effectiveness of the proposed algorithm on two benchmark problems: Clustered Shortest-Path tree Problem and Deceptive Trap Function. In comparison to LTGA and existing methods, MF-LTGA outperforms in quality of the solution or in computation time. (C) 2020 Elsevier Inc. All rights reserved.
Hierarchical problems represent an important class of nearly decomposable problems. The concept of near decomposability is central to the study of complex systems. When little a priori information is available, a blac...
详细信息
ISBN:
(纸本)9781450319638
Hierarchical problems represent an important class of nearly decomposable problems. The concept of near decomposability is central to the study of complex systems. When little a priori information is available, a black box problem solver is needed to optimize these hierarchical problems. The solver should be able to learn linkage information, and to preserve and test partial solutions at different levels in the hierarchy. Two well known benchmark functions - shuffled Hierarchical If-And-Only-If (HIFF) and shuffled Hierarchical Trap (HTRAP) functions - exemplify the challenges posed by hierarchical problems. Standard geneticalgorithms are unable to solve these problems, and specific methods, like SEAM and hBOA, have been designed to address them. In this paper, we investigate how the recently developed linkage tree genetic algorithm (LTGA) performs on these hierarchical problems. We compare LTGA with SEAM and hBOA on HIFF and HTRAP functions. Results show that, although LTGA is a simple algorithm compared to SEAM and hBOA, it nevertheless is a very efficient, reliable, and scalable algorithm for solving the randomly shuffled versions of HIFF and HTRAP, two hard, hierarchical problems.
The linkage tree genetic algorithm (LTGA) identifies linkages between problem variables using an agglomerative hierarchical clustering algorithm and linkagetrees. This enables LTGA to solve many decomposable problems...
详细信息
ISBN:
(纸本)9781450305570
The linkage tree genetic algorithm (LTGA) identifies linkages between problem variables using an agglomerative hierarchical clustering algorithm and linkagetrees. This enables LTGA to solve many decomposable problems that are difficult with more conventional geneticalgorithms. The goal of this paper is two-fold: (1) Present a thorough empirical evaluation of LTGA on a large set of problem instances of additively decomposable problems and (2) speed up the clustering algorithm used to build the linkagetrees in LTGA by using a pairwise and a problem-specific metric.
We introduce the linkage tree genetic algorithm (LTGA), a competent geneticalgorithm that learns the linkage between the problem variables. The LTGA builds each generation a linkagetree using a hierarchical clusteri...
详细信息
ISBN:
(纸本)9781450300735
We introduce the linkage tree genetic algorithm (LTGA), a competent geneticalgorithm that learns the linkage between the problem variables. The LTGA builds each generation a linkagetree using a hierarchical clustering algorithm. To generate new offspring solutions, the LTGA selects two parent solutions and traverses the linkagetree starting from the root. At each branching point, the parent pair is recombined using a crossover mask represented by the clusters that are merged at that particular tree node. The parent pair competes with the offspring pair, and the LTGA continues traversing the linkagetree with the pair that has the most fit solution. Once the entire tree is traversed, the best solution of the current pair is copied to the next generation. In this paper we use the normalized variation of information metric as distance measure for the clustering process. Experimental results for the classical fully deceptive function show that the LTGA only requires very small, minimal population sizes, and executes a similar number of function evaluations as existing linkage learning geneticalgorithms.
A key search mechanism in Evolutionary algorithms is the mixing or juxtaposing of partial solutions present in the parent solutions. In this paper we look at the efficiency of mixing in geneticalgorithms (GAs) and es...
详细信息
ISBN:
(纸本)9781450305570
A key search mechanism in Evolutionary algorithms is the mixing or juxtaposing of partial solutions present in the parent solutions. In this paper we look at the efficiency of mixing in geneticalgorithms (GAs) and estimation-of-distribution algorithms (EDAs). We compute the mixing probabilities of two partial solutions and discuss the effect of the covariance build-up in GAs and EDas. Moreover, we propose two new Evolutionary algorithms that maximize the juxtaposing of the partial solutions present in the parents: the Recombinative Optimal Mixing Evolutionary algorithm (ROMEA) and the Gene-pool Optimal Mixing Evolutionary algorithm (GOMEA).
暂无评论