Cellular Genetic Algorithm with Communicating Grids for a Delivery Problem

摘要

This paper describes a cellular genetic algorithm with communicating grids for solving a delivery problem. Specific operators for mutation and crossover are described. The GA is hybridized using a heuristic that is acting as a hyper-mutation operator. It is inspired from a very efficient dynamic programming algorithm. A similarity vector is associated to each solution. A Kohonen self-organizing map is used to place the initial population on the grid and specific placement techniques are applied during the whole activity. These techniques favor the groups based on similarity. The position of groups on the grid and their contents are dynamic. A similarity based communication protocol is used to change a given percent of the best individuals of the clusters and a given threshold is used to tune the communication scheme. The performance of the algorithm is experimentally analyzed: the capacity of the cellular algorithm to find known optimal solutions, its stability in terms of the unitized risk values, the way to obtain good values of the parameters is described, different similarity function are compared between them and the threshold values for optimal clustering and communication protocol are obtained. Also, the effect of communication period and the percent of changed individuals on the quality of the found solution are analyzed. The results show that the cellular algorithm dominates the canonical counterpart hybrid genetic algorithms.