A new genetic algorithm based on primal-dual chromosomes for royal road functions

Genetic algorithms (GAs) have been broadly studied by a huge amount of researchers and there have been many variations developed based on Holland's simple genetic algorithm (SGA). Inspired by the phenomenon of diploid genotype and dominance mechanism that broadly exist in nature, in this paper we propose a new genetic algorithm - primal-dual genetic algorithm (PDGA). PDGA operates on a pair of chromosomes that are primal-dual to each other through the primal-dual mapping, which works in the sense of Hamming distance in genotype. The primal-dual mapping improves the exploration capacity of PDGA and thus its searching efficiency in the search space. We compare the performance of PDGA over SGA based on the Royal Road functions, which are especially designed for testing GA's performance. The experiment results show that PDGA outperforms SGA for different performance measures.