Fine-grained parallel genetic algorithm:a global convergence criterion

Abstract

This paper presents a fine-grained parallel genetic algorithm with mutation rate as a control parameter. The function of the mutation rate is similar to the temperature parameter in the simulated annealing [3,8,10]. The motivation behind this research is to develop a global convergence theory for the fine-grained parallel genetic algorithms based on the simulated annealing model There is a mathematical difficulty associated with the genetic algorithms as they do not strictly come under die definition of an algorithm. Algorithms normally have a starting point and a defined point of termination which genetic algorithms lack. The parallel genetic algorithm presented here is a stochastic process based on Markov chain [2] model It has been proven that fine-grained parallel genetic algorithm is an ergodic Markov chain and that it converges to the stationary distribution. The theoretical result has been applied to in the context of optimisation of a deceptive function of 4-th order.

Keywords:

• Stochastic optimisation
• parallel model
• Markov chain
• global convergence

C.R. Categories:

• I2.8
• G1.6
• G.3
• I6.4
• C1.2