Comparison 2: Brudaru's Cellular Genetic Algorithm With Communicating Grids and SOM

Brudaru, O. (2011) Cellular Genetic Algorithm With Communicating Grids For A Delivery Problem (pdf) Quick introduction to Cellular GA (CGA) It is a kind of evolutionary algorithm in which each individual crosses over with it closest neighbor The algorithm normally involves a structured 2D grid (can be 1D and 3D) of individuals. Clusters of similar individuals are naturally evolved. The set of potential mates of an individual is called its neighbourhood : Advantages of traditional CGA: - avoids premature convergence as the algorithm uses 2D grid and therefore "the occurring of multiple copies of the best chromosome is improbable" - spatial structure based on similarity Brudaru's proposed CGA: - algorithm has many communicating grids acting in parallel and synchronized by the stages of the evolution - clustering method based on Kohonen's SOM organises the population of individuals on each grid - communication protocol that interchanges the best individuals belonging to similar clusters placed on different grids, therefore preserving the similarity between some clusters in different grids. Grid space organisation using SOM: All chromosomes are placed in a grid of NxN locations which appear as a matrix size KxK. In the example below N=18 and K=3: Each location on tho grid has two possible states: free/occupied node where a chromosome can be placed/ is already placed. This network is trained using the neighborhood function. Each cluster has a centroid and only individuals within certain distance from the center are retained in the cluster and the remaining chromosomes are redistributed to the closest clusters that are not yet filled. The members of each non-empty cluster are placed on the square shaped subset diagrammed below, in the increasing order of their fitness, starting from the center of the squared spiral to outside.

the positional clustering captures the similarity of the individuals. It transforms the intrinsic structural similarity into a position based similarity, avoiding a time consuming management (creating and maintaining) of the clustering based on explicit structural similarity.