Hybrid Multipopulation Cellular Genetic Algorithm and Its Performance

Li Ming（黎明），Lu Yuming（魯宇明）＊，Jie Lilin（揭麗琳）

1.Key Laboratory of Nondestructive Testing，Ministry of Education，Nanchang Hangkong University，Nanchang，330063，P.R.China；2.College of Automation Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing，210016，P.R.China

1 Introduction

Intelligent algorithms proposed in recent years are grounded in various biological phenomena and laws.These intelligent algorithms are widely used to solve optimization problems in science and engineering.In practice，however，these optimization problems by themselves are inadequate for solving complex problems，and the results are often deficient.Therefore hybrid algorithms，which combine the desirable features of different algorithms，have attracted much interest.

The cellular genetic algorithm （CGA）is a type of decentralized GA in which each individual is fixed in a tutorial grid，usually of dimension 2，regardless of parallel execution.Genetic operators are applied locally to the neighborhood of each individual，which enables slow diffusion of favorable individuals.While CGA encourages diversity in the population，it can delay the convergence speed of the algorithm.The CGA exhibits higher global exportation ability than GA，but converges more slowly.

Particle swarm optimization（PSO），an optimized algorithm based on swarm intelligence，simulates the social behavior of cooperative groups such as ants，fishes and birds.The swarm develops a collective intelligence that facilitates its search for a global optimum.Desirable features of the PSO algorithm are simple rules，few parameters and rapid convergence speed.However，global search ability of the algorithm is poor.

The evolutionary rules of cellular automata have been extensively documented［1－2］.An extension of cellular automata，namely，genetic algorithms with evolutionary rules can improve population diversity.Li，et al［3］analyzed the convergence rate of canonical CGA using absorbing－state Markov chain.Many widely－used neighbor structures have been analyzed and researched in detail［4－6］.Spatial states with a cell having four different types of neighbors were simulated and the effects of each neighbor were analyzed［7］.Some algorithms introduced disastrous events into CGA［8－10］and proposed a hierarchical CGA，while a hybrid CGA／distribution estimation algorithm was proposed in Ref.［11］.Hybrid algorithms combining GA with local searching proved effective in solving multi－objective optimization problems［12－13］.From the above citations，it is apparent that improving the local search ability and convergence speed of CGA was neglected.

The GA is based on the tradeoff between global exploration and local exploitation，which reflects selection pressure.Refs.［14－16］investigated the selection pressure of CGA on neighborhood structure，breeding strategies and selecting operation.The selection pressure imposed by CGA with disaster on size and period of disasters is also investigated［17］.Selection pressure was found to be lower following a large disaster，and to occur over a shorter time period.Ref.［18］proposed a new adaptive algorithm that aims to dynamically control the exploration／exploitation trade－off，based on three－dimensional CGAs.According to their results，selection pressure varied if certain parameters were varied.This finding provides valuable insights into the tradeoff between global exploration and local exploitation.

Recognizing that PSO possesses strong local searching ability，this paper proposes a hybrid multipopulation cellular genetic algorithm （HCGA）that combines GA with PSO.The perform－ance of the algorithm is evaluated on four typical test functions.Selection pressure and population diversity are assessed by varying the population size and the number of subpopulations.We demonstrate the superiority of HCGA in terms of global convergence rate and convergence speed.The algorithm operates most effectively when the number of subpopulation is n＝2m（m＝3）.

2 Description of Cellular Genetic Algorithm and Particle Swarm Optimization

2.1 Cellular genetic algorithm description

In CGAs，individuals are placed on a toroidal d－dimensional grid （the algorithm is usually implemented in two dimensions）.Each occupied grid element（or cell）contains a single individual.Genetic reproduction and crossover can occur only between an individual and its nearest neighbors（see Fig.1）.

Fig.1 Structure of a neighborhood

We adopt the CGA presented in Ref.［2］.In the CGA，individuals are randomly classified as“active”or “inactive”（see Fig.2）.Under an evaluative rule，all individuals simultaneously change state.An“active”cell is the one that can interact with its neighborhood to select and crossover.

Fig.2 Distribution of individuals in CGA

The pseudo－code of the CGA algorithm is provided below：

Step 1 To classify an individual as living or dead on the L×Lgrid at random.

Step 2 To set the stop condition.

Step 3 To calculate fitness of individuals.

Step 4 To select the living individual and obtain its neighborhood as parents.

Step 5 To implement parents’recombination.

Step 6 To evaluate fitness and replace existing individual if fitness is improved.

Step 7 To implement individual mutation.

Step 8 To update states synchronously according to evolution rule.

Step 9 When the stop condition is satisfied，end.

In the above algorithm，the current population is replaced after synchronously applying crossover and mutation to all individuals.

2.2 Particle swarm optimization description

The PSO searches a global optimum by simulating movement and interaction of swarming particles.A population of particles is initialized with random position and velocities.The position of a particle corresponds to one possible solution of the problem.The objective value of each particle is computed by an objective function.In the next iteration，the position and velocity of each particle is updated through tracking its own experience and that of other particles.

3 Hybrid Multipopulation Cellular Genetic Algorithm

3.1 Population division and immigration of individuals

Population diversity can be maintained by dividing the population into several equally－proportioned subpopulations that do not depend on each other.Each subpopulation evolves independently，i.e.，genetic operations cannot occur between subpopulations.

Population division usually causes isolated islands that cannot interact with other islands.To enable information exchange between subpopulations，one or a few reproductive individuals in a subpopulation are allowed to immigrate to another island according to the immigration rate when the interval generationΔT meets a specified value.Here in this paper，ΔTis 20.

3.2 Construction of new operations

The existing CGA imposes random mutations that are irrelevant to past and present individual states，thereby ignoring the distance between each individual and the fittest individual.Furthermore，excessively high mutation rates will destroy favorable genes，while low rates will reduce the search speed.Very low rates will stagnate the evolutionary process.In addition，since mutation is directional，the probability of low fitness will be increased.

In this study，mutation in CGA （Step 7）is replaced by a new operation based on neighboring structures in PSO.Following the operation，the individual in the next iteration is calculated as

where t is the generation，nthe population size，i the position order of the individual in the cell space，and xitthe gene of the ith individual.The population is denoted as Qt＝｛x1t，x2t，…，xit，…，xnt｝（1≤i≤n），and vi（t＋1）is calculated as

where wis the inertia coefficient，the fittest gene acquired by an individual，andthe fittest neighboring gene identified by the individual.r1and r2are the uniformly distributed random numbers in the interval［0，1］.c1，c2are the cognitive and social learning factors，respectively.vitis the mutating velocity at generation t，calculated as

Since Eq.（2）uses amplitude and directional information to forecast mutation of an individual，it improves the local searching ability，and eliminates the indiscriminate mutating operations that occur in CGA.

4 Computational Experiments

4.1 Test problems

The algorithm is evaluated on four test functions，as summarized below：

（1）F1Schaffer′s f6function

Eq.（4）has a single maximum at 1.This global optimum is surrounded by a few local optima，including one at 0.990 284and another at 0.962 776.Implemented on F1，most algorithms easily reach a local optimum from which they cannot escape.

（2）F2Needle function

Function F2is similar to F1.One of its local maxima（at 1.128 4）is extremely close to the global maximum （at 1.151 1）.Most algorithms reach the local optimum at 1.128 4.

（3）F3Griewank′s function

This paper adopts 30－d.Function F3，which is a multimodal function with a single global optimum surrounded by many nearby local optima.

（4）F4Sphere function

F4is a unimodal function with a minimum of 0at（0，0，…，0）.Its dimension is the same as F3.High－dimensional versions of this function are more difficult to solve because of the strong constraints between variables.

4.2 Parameter setting

The parameters are as follows：number of runs is 100，cellular space size 20×20，population size 400，crossing rate 0.8，mutation 0.05.In HCGA，learning factors c1and c2are both set to be 2.Immigration rate is 0.2and the inertial weight is 1.

5 Experimental Results

5.1 Analysis of selection pressure

To some extent，selection pressure represents the balance between exploration and exploitation.Selection pressure is measured by the takeover time［3］，defined as the required time for a single （best）individual to occupy the entire population using the selection operator only，and ignoring crossovers and mutation.The shorter the takeover time，the higher the selection pressure.

Fig.3plots the proportion of the best individual in the population as a function of time in CGA.Fig.4is an equivalent plot generated by HCGA，but varying the subpopulation number and population size.

Fig.3 Growth curve of the best individual（CGA）

In Fig.3，the curve gradually ascends to 1 and remains constant thereafter.When the proportion of the best individual reaches 1，information of the best individual cannot be spread.Then the selection pressure demonstrates the saturated condition.

The curve of Fig.4similarly ascends but less smoothly.The proportion of the best individuals firstly gradually ascends to 1／n before 10generations，then stays stable for a period of time and goes up after 20generations.Furthermore，the similar curve jump can be observed in the later evolution，such as 40generations.The jumps are observed whenΔT＝20.The phenomenon is caused by individual migration strategy，which provides potential for the best individual information in a subpopulation exchanging into other subpopulations.Information is thus disseminated between subpopulations.In this way，a fit individual can spread its genes into other subpopulations，and thereby spread more widely.But when the proportion of the best individuals is 1，the best individual cannot spread.

Fig.4 Growth curve of the best individual（HCGA）

Varying subpopulation numbers The population size is retained at 20×20and the subpopulation number is set to 2，4，8and 16.The resulting selection pressure is displayed in Fig.4（a）.In Fig.4（a），the proportion of best individuals in the population increases more slowly when more subpopulations exist.Namely，the proportion of fittest individuals decreases as subpopulation number increases；equivalently，the selection pressure decreases as the number of subpopulations increases.

Varying population size Retaining the sub－population number at 8，the population size is set to 200，400，800and 1 600，respectively.The results are plotted in Fig.4（b）.From Fig.4（b），we observe that selection pressure decreases as population size increases，up to the 10th generation.Between generations 10and 20，it is relatively constant，because the fittest individual is not spread until the conditions favor migration.Beyond the 20th generation，selection pressure again increases with population size.

The above analysis reveals that by segmenting the population，HCGA reduces the selection pressure relative to CGA，and improves the global convergence of the algorithm.

5.2 Performance of HCGA and CGA

HCGA is compared with CGA with respect to global convergence rate（P），average convergence generation（G），average run time（T），and the average and standard deviation（STD）of the best value.

The results implemented on F1—F4are shown in Table 1.The global convergence of HCGA on F1and F2is 100%and the algorithm never becomes trapped in local optima.The convergence generation of HCGA is lower than CGA and the algorithm converges more quickly.Especially on F2，CGA converges to the global optimum in only 17%of trials，and its convergence speed is three times slower than that of HCGA.On F3，CGA never converges to the global optimum，while HCGA converges in 100%of trials.On F4，although both algorithms converge 100%of the time，the convergence speed of HCGA far exceeds that of CGA.The convergence rate of HCGA is attributed to the population segmentation and individual migration，which reduces selection pressure，slows down information dissemination and avoids premature convergence.Moveover，the new operation is directional，and the convergence speed is thus improved.

5.3 Performance under varying population segment number

The number of subpopulations is an impor－tant parameter in HCGA.This section compares the algorithm performance for different subpopulations n，where n＝2m（m＝1，2，3，4）.Population size is retained constant at 400.The other parameters are as specified in Section 4.2.

Table 2compares the global convergence rate（P），average convergence generation （G），average run time（t），and average and the standard deviation（STD）of the best value.

The larger the number of subpopulations，the lower the selection pressure （see Fig.4）.Hence，on each of the four test functions，the global convergence rate increases as the number of subpopulations increases.Initially，the spending time decreases as the number of subpopulations increases and later increases，except on F1.When the number of subpopulations is too large，the selection pressure will be too low.It is unfavorable for information dissemination，which can reduce the performance of HPCGA.The STD of the fittest individual is also improved as subpopulation increases，and later decreases.

Table 1 Comparison of performance in terms of HCGA and CGA

Table 2 Comparisons of performance of different numbers with sub－population

5.4 Diversity performance

Population diversity is crucial in evolutionary algorithms.Only in a diverse population can the algorithm seek a global optimum.Therefore，maintaining population diversity is guaranteed to improve algorithm performance.This section investigates changes in diversity over time，while varying the number of subpopulations.Diversity is measured as the ratio of population entropy to the maximum of population entropy［17］.

The CGA and HCGA algorithms are implemented 100times on F1and F3.Figs.5，6plot the evolution of diversity calculated by CGA and HCGA，respectively，for the four population segmentation numbers.The population diversity drops dramatically with the increasing generation in CGA.On F1and F4，population diversity is very low at generations 500and 1 000，respectively.However，in HCGA，the population diversity declines slowly and maintains high over a long period.Most importantly，population diversity is strengthened as subpopulation number increases，up to m＝3.When m＝3and 4，the algorithm can keep population diversity better than that of the case with m＝1or 2.

Fig.5 Diversity change of F1on HCGA with different subpopulation numbers

Fig.6 Diversity change of F4on HCGA with different subpopulation numbers

6 Conclusions

The HCGA is proposed，in which GA is combined with a new operation inspired by PSO.The new operation replaces mutation in standard CGA，and enables population segmentation and genetic migration.By enhancing population diversity and reducing selection pressure，HCGA achieves a favorable global exploration／local exploitation balance.It improves not only the convergence rate and speed of conventional CGA，but also its stability.This paper also investigates the effect of subpopulation number on HCGA performance.The algorithm performs most effectively at a critical number of subpopulations.The result demonstrates that HGCA performance can be optimized by selecting an appropriate number of subpopulations.On each of the four test functions，the algorithm performance is optimized at the population segmentation number of 8（m＝3）.

［1］ Billings S A，Yang Y.Identification of the neighborhood and CA rules from station－temporal CA patterns［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2003，33（2）：332－339.

［2］ Lu Y M，Li M，Li L.The cellular genetic algorithm with evolutionary rule［J］.Acta Electronica Sinica，2010，38（7）：1603－1607.（in Chinese）

［3］ Li J H，Li M.Convergence analysis and convergence rate estimate of cellular genetic algorithms ［J］.Moshi Shibie yu Rengong Zhineng／Pattern Recognition and Artificial Intelligence，2012，25（5）：874－878.（in Chinese）

［4］ Alba E，Dorronsoro B.Cellular genetic algorithms［M］.USA：Springer Science and Business Media，LLC，2008，21－34.

［5］ Ishibuchi H，Sakane Y，Tsukamoto N，NojimaA Y.Implementation of cellular genetic algorithms with two neighborhood structures for single－objective and multi－objective optimization［J］.Soft Computing，2011，15（9）：1749－1767.

［6］ Alba E，Dorronsoro B.The exploration／exploitation tradeoff in dynamic cellular genetic algorithms［J］.IEEE Transactions on Evolutionary Computation，2005，9（2）：126－142.

［7］ Billings S，Yang Y.Identification of probabilistic cellular automata［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2003，33（2）：225－236.

［8］ Kirley M.A cellular genetic algorithm with disturbance：optimization using dynamic spatial interactions［J］.Journal of Heuristics，2002，8（3）：321－342.

［9］ Lu Y，Li M，Li L.Improved genetic algorithm based on migration differential individuals ［J］.Systems Engineering and Electronics，2011，33（3）：1－4.（in Chinese）

［10］Liu Nan，Huang Jinquan.Performance seeking of turbo－shaft engines based on improved particle swarm optimization algorithm［J］.Journal of Nanjing University of Aeronautics and Astronautics，2013，45（3），303－308.

［11］Keedwele E，Khu S T.A hybrid genetic algorithm for the design of water distribution networks ［J］.Engineering Applications of Artificial Intelligence，2005，18（4）：461－472.

［12］Jiang Yu，Yang Yingbao，Zhou Hang.Innovative predatory search algorithm for aircraft arrival sequencing and scheduling problems［J］.Transactions of Nanjing University of Aeronautics and Astronautics，2010，27（4）：361－364.

［13］Rezaeian J，Javadian N，Tavakkoli M R，Jolai F.A hybrid approach based on the genetic algorithm and neural network to design an incremental cellular manufacturing system［J］.Applied Soft Computing Journal，2011，11（6）：4195－4202.

［14］Jiradej V，Nasimul N，Hitoshi I.Polynomial selection：A new way to tune selective pressure［C］∥Proceedings of The 2nd World Congress on Nature and Biologically Inspired Computing.Fukuoka，Japan：IEEE，2010，597－602.

［15］Kaveh A，SHahrouzi M.Dynamic selective pressure using hybrid evolutionary and ant system strategies for structural optimization［J］.International Journal for Numerical Methods in Engineering，2008，73（4）：544－563.

［16］Camargo G，Camargo J，Naufal J，Matiussi G.Definition of selective pressure control methods for optimization of genetic algorithms in air traffic control［C］∥Proceedings of the 10th IASTED International Conference on Artificial Intelligence and Soft Computing.［S.l.］.ASC，2006，304－311.

［17］Chen S，Lu Y，Yang H，et al.Selection pressure study of cellular genetic with disturbances［J］.Computer Engineering and Applications，2011，47（27）：32－35.（in Chinese）

［18］Asmaa Al－Naqi，Erdogan A T，Arslan T.Adaptive three－dimensional cellular genetic algorithm for balancing exploration and exploitation processes［J］.Soft Computing，2013，17（4）：1－13.