Schema Co-Evolutionary Algorithm for Solving SGA-Hard Problems and Its Applications

Kwee-Bo Sim: Artificial Life and Intelligent Information System Lab., School of Electrical and Electronics Engineering, Chung-Ang University, 221, Heukseok-Dong, Dongjak-Gu, Seoul, 156-756, KOREA Tel : +82-2-820-5319 Fax : +82-2-817-0553 Mobile Phone : +82-11-9997-1256 E-mail : kbsim@cau.ac.kr Homepage URL : http://alife.cau.ac.kr

Abstract

Simple genetic algorithm (SGA) is a population-based optimization method based on the Darwinian natural selection. The theoretical foundations of SGA are the Schema Theorem and the Building Block Hypothesis. Although SGA does well in many applications as an optimization method, it still does not guarantee the convergence of a global optimum in GA-hard problems and deceptive problems. As an alternative schema, therefore, there is a growing interest in a co-evolutionary system where two populations constantly interact and cooperate each other. In this paper we propose a schema co-evolutionary algorithm (SCEA) and show why the SCEA works better than SGA in terms of an extended schema theorem. The experimental analyses using the Walsh-Schema Transform show that the SCEA works well in GA-hard problems including deceptive problems.

Keywords: Simple genetic algorithm (SGA), schema co-evolutionary algorithm (SCEA), Schema Theorem, Building Block Hypothesis, Walsh-Schema Transform

Short Biography

Kwee-Bo Sim :

He received the B.S. and M.S. degrees in Department of Electronic Engineering from Chung-Ang University, Seoul, Korea, in 1984 and 1986 respectively, and Ph. D. degree in Department of Electronic Engineering from the University of Tokyo, Japan, in 1990. Since 1991, he has been a faculty member of the School of Electrical and Electronic Engineering at the Chung-Ang University, where he is currently a Professor. His research interests include Artificial Life, Neuro-Fuzzy and Soft Computing, Evolutionary Computation, Learning and Adaptation Algorithm, Autonomous Decentralized System, Intelligent Control and Robotic System, Artificial Immune System, Evolvable Hardware, Artificial Brain, Intelligent Home, Home Networking, Intelligent Sensor, and Ubiquitous Computing etc. He is a member of IEEE, SICE, RSJ, KITE, KIEE, KFIS, and ICASE Fellow.