Property | Value |
Name | NCL-TR-2008003 |
Description |
Recognizing Problem Decomposition with Inductive Linkage Identification: Population Requirement vs. Subproblem Complexity
Abstract: In genetic and evolutionary algorithms, the goal of linkage identification is to detect strong relationships among the decision variables of the objective function. If such relations can be identified, the crossover operator can accordingly mix and recombine the identified sub-solutions without destroying them. In our previous study, we have proposed a linkage identification technique, called inductive linkage identification (ILI), which integrates the mechanisms of perturbation and decision tree induction. With the proposed technique, linkage information of the objective function can be acquired via constructing an ID3 decision tree to model the mapping from solution strings to their corresponding fitness changes caused by perturbations and then inspecting the constructed decision tree for the decision variables exhibiting strong interdependencies with one another. In this study, we observe the behavior of ILI on decomposable problems of different subproblem complexities and make an attempt to understand the population requirement of the proposed linkage identification technique. The experimental results demonstrate that the population size required by ILI to correctly learn linkage grows sub-linearly with the problem size while grows exponentially with the complexity of constituting subproblems. |
Filename | NCL-TR-2008003.pdf |
Filesize | 197.37 kB |
Filetype | pdf (Mime Type: application/pdf) |
Creator | ypchen |
Created On: | 07/24/2008 18:01 |
Viewers | Everybody |
Maintained by | Editor |
Hits | 2664 Hits |
Last updated on | 12/09/2010 14:04 |
Homepage |