Evolutionary Self-Organizing Map

ABSTRACT: An evolutionary self-organizing map is presented. The evolutionary training algorithm operates on a two-dimensional population grid that has sample points to guide the search. As a result of competition and locally guided evolution the network is

Evolutionary Self-Organizing Map

Ari S. Nissinen, Heikki Hyotyniemi Control Engineering Laboratory, Helsinki University of Technology Espoo, Finland Phone:+358-9-451 3322, Fax:+358-9-451 3333 Email: ari.nissinen@hut., heikki.hyotyniemi@hut.ABSTRACT: An evolutionary self-organizing map is presented. The evolutionary training algorithm operates on a two-dimensional population grid that has sample points to guide the search. As a result of competition and locally guided evolution the network is able to create organization among inpiduals. For visual validation of the algorithm, a two-dimensional data example is presented.

I INTRODUCTIONCompetitive learning is a powerful paradigm. For example, self-organizing maps (SOM) Kohonen 1995] use competitive learning to cause organization between prototypes. On the other hand, in evolutionary computing competitive learning causes structural optimization in a population of inpiduals Goldberg 1989], Michalewicz 1992]. Now a question arises: Can these ideas be put together to form an algorithm causing both structural optimization, and self-organization of alternative structures at the same time? What would be the bene ts of this kind of an algorithm? In complex cases there is rarely just one correct optimal solution to a problem. Rather there are several good solutions for di erent conditions. A good example would be indenti cation of nonlinear processes using time-series modeling Ljung 1987]: models with di erent model orders and delays are needed for di erent operating conditions. Rather than having just one model, one needs a collection of models to represent the whole operation regime of the process. In short, the objective is to have an algorithm that is able to carry out structural optimization of complex objects and create organization among them. The objectives of previous work combining SOM and evolutionary computing ( Polani 1992], Polani 1993], Huang 1995], Chang 1998]) seem to have been di erent, i.e. evolutionary computing has been used to optimize the topological structure of the SOM, and standard learning algorithm has been used to train the self-organizing map. A short suggestion to the direction of evolutionary learning of SOM can be found in Kohonen 1995, p. 159]. However, no exact algorithm or examples are given. In this work the fundamental idea is to use the spatial grid structure of the SOM as an evolutionary platform where inpiduals are interacting and evolving, thus creating organization. The organization is directed by the scalar tness values of the inpiduals. The structure of the inpiduals is of no concern, making it possible to extend the applications of self-organizing maps. An application of the idea to dynamic modeling can be found in Nissinen 1998], for example. The paper is organized as follows: The Section II presents the data structure of the algorithm. In Section III the training algorithm is given, whose performance is demonstrated in Section IV. A simple two-

dimensional example case has been selected on purpose in oder to give the reader a visual con rmation that the algorithm causes self-organization. Simulation studies are necessary, because the convergence properties of the algorithm are di cult to prove mathematically. Section V discusses the meaning of the training parameters and lists some observations. Section VI concludes the paper.

II DATA STRUCTURE OF THE MAPThe network consists of a population of inpiduals pj, where j= 1;:::; Ni . The Ni inpiduals form a oneor two-dimensional grid. A group of inpiduals is selected to represent local subsets of the population. These inpiduals, or`nodes' nj, where j= 1;:::; Nn, stand for the code book vectors in a traditional self-organizing map. Vertices connecting representative inpiduals de ne a grid topology, and the Manhattan distance is used in neighborhood calculations. An example con guration is shown in Figure 1.

ABSTRACT: An evolutionary self-organizing map is presented. The evolutionary training algorithm operates on a two-dimensional population grid that has sample points to guide the search. As a result of competition and locally guided evolution the network is

Figure 1: A sample data structure. White circles represent inpiduals, and the lled circles are nodes connected to each other with vertices.

III TRAINING ALGORITHMThe training algorithm is based on stochastic selection of a node whose prototype vector is updated to better represent the data Hyotyniemi 1994]. In the algorithm presented here (EVSOM), the update is carried out using evolutionary computing. The pseudocode of the algorithm is presented in Figure 2. The winning node c(k) with the highest value of the tness function is chosen asc(k )= argminff (x(k ); pi (k ))g;i

(1)

where f ( ) is the tness function, x(k) represents the data sample, and pi (k) is the prototype object associated with ith node. In standard SOM the tness function is directly determined by the Euclidean distance (or other vector norm) between the prototype vector and the input data, whereas in the formulation above the tness value f ( ) is independent on the vector presentation and structure of the prototypes. It should re ect the goodness of the prototype with respect to the input. In a simple static case it can be the vector di erence between the data sample and the node reference vector, like in the example presented in this paper. A more complex example is a dynamic model, and then the tness function can be the sum squared error of the output of the model. In the Step 2 of the algorithm, the node whose environment is evolved, is selected. The probability of the

LOOP until k= Niter Step 1: Fi …… 此处隐藏：14043字，全部文档内容请下载后查看。喜欢就下载吧 ……