Browsing by Author "Chuang, Chung-Yao"

Now showing 1 - 3 of 3

Inductive linkage identification on building blocks of different sizes and types
(2012)
Chen, Ying-ping
;
Chuang, Chung-Yao
;
Huang, Yuan-Wei
;
資訊工程學系
;
Department of Computer Science
The goal of linkage identification is to obtain the dependencies among decision variables. Such information or knowledge can be applied to design crossover operators and/or the encoding schemes in genetic and evolutionary methods. Thus, promising sub-solutions to the problem will be disrupted less likely, and successful convergence may be achieved more likely. To obtain linkage information, a linkage identification technique, called Inductive Linkage Identification (ILI), was proposed recently. ILI was established upon the mechanism of perturbation and the idea of decision tree learning. By constructing a decision tree according to decision variables and fitness difference values, the interdependent variables will be determined by the adopted decision tree learning algorithm. In this article, we aim to acquire a better understanding on the characteristics of ILI, especially its behaviour under problems composed of different-sized and different-type building blocks (BBs) which are not overlapped. Experiments showed that ILI can efficiently handle BBs of different sizes and is insensitive to BB types. Our experimental observations indicate the flexibility and the applicability of ILI on various elementary BB types that are commonly adopted in related experiments.
Linkage identification by perturbation and decision tree induction
(2007)
Chuang, Chung-Yao
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
The purpose of linkage identification in genetic and evolutionary algorithms is to detect the strongly related variables of the fitness function. If such linkage information can be acquired, the crossover or recombination operator can accordingly mix the discovered sub-solutions effectively without disrupting them. In this paper, we propose a new linkage identification technique, called inductive linkage identification (ILI), employing perturbation with decision tree induction. With the proposed scheme, the linkage information can be obtained by first constructing an ID3 decision tree to learn the mapping from the population of solutions to their corresponding fitness differences caused by perturbations and then inspecting the constructed decision tree for variables exhibiting strong interdependencies with one another. The numerical results show that the proposed technique can accomplish the identical linkage identification task with a lower number of function evaluations compared to similar methods proposed in the literature. Moreover, the proposed technique is also shown being able to handle both uniformly scaled and exponentially scaled problems.
Sensibility of Linkage Information and Effectiveness of Estimated Distributions
(2010-12-01)
Chuang, Chung-Yao
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
The probabilistic model building performed by estimation of distribution algorithms (EDAs) enables these methods to use advanced techniques of statistics and machine learning for automatic discovery of problem structures. However, in some situations, it may not be possible to completely and accurately identify the whole problem structure by probabilistic modeling due to certain inherent properties of the given problem. In this work, we illustrate one possible cause of such situations with problems consisting of structures with unequal fitness contributions. Based on the illustrative example, we introduce a notion that the estimated probabilistic models should be inspected to reveal the effective search directions and further propose a general approach which utilizes a reserved set of solutions to examine the built model for likely inaccurate fragments. Furthermore, the proposed approach is implemented on the extended compact genetic algorithm (ECGA) and experiments are performed on several sets of additively separable problems with different scaling setups. The results indicate that the proposed method can significantly assist ECGA to handle problems comprising structures of disparate fitness contributions and therefore may potentially help EDAs in general to overcome those situations in which the entire problem structure cannot be recognized properly due to the temporal delay of emergence of some promising partial solutions.