一种基于有性繁殖的遗传算法

A Genetic Algorithms With Sexual Reproduction

为了更有效地抑制标准遗传算法 (SGA)中的早熟收敛现象和提高收敛速度 ,提出了一种基于有性繁殖的遗传算法 .该算法借鉴了自然界最常见的有性繁殖现象 ,首先将每个个体编码为配对的双染色体码串 ,并增加性别染色体编码 ,以建立遗传个体的性别特征 ;然后 ,通过建立有性遗传进化算子来对不同性别的个体赋予不同的进化控制参数 ,以使得雄性个体具有较强的全局探索能力 ,而使雌性个体具有较强的局部快速寻优能力 ,最后通过建立对应的有性遗传交叉、变异算子 ,使得这种基于有性繁殖的遗传算法具有更强的全局寻优能力和快速收敛能力 .用该算法对一系列典型函数和其他优化问题进行了优化计算试验 ,结果证明 ,该算法不易陷入早熟收敛 ,且全局搜索能力和局部搜索能力平衡较好 ,收敛速度快 ,同时也验证了这种基于有性繁殖的遗传算法的有效性和优良性能 .

In this paper, a novel genetic algorithms with sexual reproduction is proposed to combat premature convergence inherent in Standard Genetic Algorithms(SGA) and speed up convergence. It imitates the sexual reproduction that is very popular in nature: (1) Each individual is encoded using diploid chromosomes which can save more information so as to memorize more good patterns, (2) There is a pair of sexual chromosome that reflects the sexual feature of each individual, so there are two kinds of individuals—male and female individuals, (3) During the reproduction procedure, each individual can only be matched with another individual with different sexual feature, and (4) Dominant genes decide the individual characters. Also, the corresponding crossover, mutation and selection operators for the sexual reproduction are developed in this paper. In the evolutionary procedure, the male individuals reserve higher mutation rate to obtain better global exploring ability while the female individuals have lower mutation rate to enhance local searching ability. As a result, the male individuals possess strong global exploring ability and the female individuals possess strong local searching ability. At the same time, the diploid encoding and dominance law diversify the gene pool. So the algorithm can help the evolutionary procedure to escape from possible local entrapment and obtain good tradeoff between exploration ability and exploitation ability. The experiments are taken on two types of optimization problems, (1) find maximum of minimum values of a series of classical and typical complex multi-modal functions, and (2) find the optimized rout for TSP problem. The experimental results have shown the good performance of genetic algorithms with sexual reproduction.