On convergence measures for order-based forking genetic algorithms

There are two types of genetic algorithms (GAs) which differ in the representation of the chromosomal strings. They are the binary coded GA and the order-based GA. We have proposed a new type of binary coded GA, called the forking GA (fGA), as a kind of multi-population GA, and showed that the searching power of the fGA is superior to that of the standard GA. The distinguishing feature of the fGA is that it does population forking and different sub-populations search different non-overlapping sub-spaces of the entire search space in parallel. In this paper, the concept of population forking is extended to ordered representation based GAs with an aim to handle permutational problems. We call this new scheme o-fGA. In this context, we define two measures (bias and salient schema) to detect the state of convergence for the ordered representation based GAs. Experimental results for the blind traveling salesperson problem (TSP) and two job-shop scheduling problems show that population forking is also effective for this sort of problem