Implementing Evolutionary Self-Organizing Maps with the Genetic Operations of Graph Evolution Theory
Maiga Chang, Jia‐Sheng Heh, Chung Yuan, Chung Li · 2003
This paper analyzes the genetic operations of a new evolution mechanism proposed by us for improving the capability to deal with graph-form solutions in the real world of genetic algorithms based on the theories of GAs and GPs. A prototype of graph evolution with genetic operations is implemented and applied to some graph-related systems with the Irish-student classification data. Evaluation between conventional optimization mechanisms and graph evolution theory is also made for proving the advantage of using graph evolution. Be notable is the graph evolution theory proposed in this paper can cover most applications of GAs and GPs. I. INTRODUCTION Conventional optimization techniques are always designed for specific problems, and the results made from these sorts of optimization techniques might be not accurately enough if there are minor changes applied to the current solved problem. (28)(18) There are several issues involved for the considerations and limitations of those conventional optimization techniques, such as learning speed and local minimum/maximum. On the contrast, with the characteristics of adapting to env ironment (adapting to problem) and evolving from generation to generation (finding global optima), evolutionary algorithms are much easier to fit different problem domains. (1) Recently, genetic algorithms provide the most considerable solving mechanism o f evolutionary algorithms as applied in the area of industrial engineering. (14) Genetic algorithms (and its derived - genetic programming) translate any possible solution for a problem into a string (either tree-form) chromosome. (17)(20) Unfortunately, not all of solutions in the real world can be formulated as the list chromosomes simply. Many researchers before used some tree-like or mesh-like chromosomes to replace the list chromosomes for solving problems in the real world. (22)(9) Although the graph chromosomes are possible to provide more general solutions for problems ( (10)(25)), there is not a complete and systematic theoretical analysis made for the graph evolution. (15)(16)(7) For graph-form solutions, this paper presents a prototype of evolutionary algorithm, which is so-called Graph Evolution. Consistent formulations for genetic phase in the evolutionary algorithms are analyzed and designed between graph evolution and genetic algorithm. However, since the paper length is restricted, some of detailed proves are ignored and will be discussed in the complete paper. Finally, this paper tries to apply the prototype of graph evolution to graph-related system such as Kohonen's SOM. (22) Evaluation of the modified systems is made for proving the advantage of using graph evolution instead of traditional problem-solving mechanisms.