Browsing by Author "Kuo, T"

Now showing 1 - 3 of 3

A genetic algorithm with disruptive selection
(1996-04-01)
Kuo, T
;
Hwang, SY
;
交大名義發表
;
資訊科學與工程研究所
;
National Chiao Tung University
Genetic algorithms are a class of adaptive search techniques based on the principles of population genetics. The metaphor underlying genetic algorithms is that of natural evolution. Applying the ''survival-of-the-fittest'' principle, traditional genetic algorithms allocate more trials to above-average schemata, However, increasing the sampling rate of schemata that are above average does not guarantee convergence to a global optimum; the global optimum could be a relatively isolated peak or located in schemata that have large variance in performance, In this paper we propose a novel selection method, disruptive selection. This method adopts a nonmonotonic fitness function that is quite different from traditional monotonic fitness functions, Unlike traditional genetic algorithms, this method favors both superior and inferior individuals. Experimental results show that GA's using the proposed method easily find the optimal solution of a function that is hard for traditional GA's to optimize, We also present convergence analysis to estimate the occurrence ratio of the optima of a deceptive function after a certain number of generations of a genetic algorithm, Experimental results show that GA's using disruptive selection in some occasions find the optima more quickly and reliably than GA's using directional selection, These results suggest that disruptive selection can be useful in solving problems that have large variance within schemata and problems that are GA-deceptive.
Using disruptive selection to maintain diversity in Genetic Algorithms
(1997-07-01)
Kuo, T
;
Hwang, SY
;
交大名義發表
;
資訊科學與工程研究所
;
National Chiao Tung University
Genetic algorithms are a class of adaptive search techniques based on the principles of population genetics. The metaphor underlying genetic algorithms is that of natural evolution. With their great robustness, genetic algorithms have proven to be a promising technique for many optimization, design, control, and machine learning applications. A novel selection method, disruptive selection, has been proposed. This method adopts a nonmonotonic fitness function that is quite different from conventional monotonic fitness functions. Unlike conventional selection methods, this method favors both superior and inferior individuals. Since genetic algorithms allocate exponentially increasing numbers of trials to the observed better parts of the search space, it is difficult to maintain diversity in genetic algorithms. We show that Disruptive Genetic Algorithms (DGAs) effectively alleviate this problem by first demonstrating that DGAs can be used to solve a nonstationary search problem, where the goal is to track time-varying optima. Conventional Genetic Algorithms (CGAs) using proportional selection fare poorly on nonstationary search problems because of their lack of population diversity after convergence. Experimental results show that DGAs immediately track the optimum after the change of environment. We then describe a spike function that causes CGAs to miss the optimum. Experimental results show that DGAs outperform CGAs in resolving a spike function.
Why DGAs work well on GA-hard functions?
(1996)
Kuo, T
;
Hwang, SY
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
What makes a problem easy or hard for a genetic algorithm (GA)? Much previous work has studied this question by applying Walsh analysis.(4)) In this paper, we demonstrate a function that is GA-hard by analyzing the Walsh coefficients of this function's Walsh decomposition. Then, we construct five functions with differing degrees of difficulty for genetic algorithms. Some are GA-easy and some are GA-hard. In a previous paper,(29)) wh have proposed a novel selection method, disruptive selection. This method devotes more trials to both better solutions and worse solutions than it does to moderate solutions, whereas the conventional method allocates its attention according to the performance of each solution. Experimental results show that DGAs (GAs using disruptive selection) perform very well on both GA-easy and GA-hard functions. Finally, we discuss why DGAs outperform conventional GAs.