基因块编码的并行遗传算法及其在TSP中的应用

针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象,提出了一种用基因块编码的并行遗传算法(Building-block Coded Parallel GA,BCPGA).该方法以粗粒度并行遗传算法为基本框架,在染色体群体中识别出可能的基因块,然后用基因块作为新的基因单位对染色体重新编码,产生长度较短的染色体,再用重新编码的染色体群体作为下一轮以相同方式演化的初始群体.将BCPGA应用于一个100城市的旅行商问题(TSP)中,结果表明本方法可以提高遗传算法的搜索效率,并且在相同条件下,BCPGA明显优于单纯的粗粒度并行遗传算法.

A Building Block Coded Parallel Genetic Algorithm and Its Application in TSP

If the building blocks can be found and treated as the gene units that compose the chromosomes, shorter chromosomes can be produced in evolution. In this article, the Building-block Coded Parallel Genetic Algorithm (BCPGA) was introduced, which is based on the coarse-grained parallel GA. In this approach, the best individuals are collected from the distributed groups every after a period of evolution. From these elites the possible building blocks are identified and treated as gene units to recode the elites. Then the building block coded elites become the initial group of a new period of evolution. The procedure is recycled in the evolution process. A 100-city Travlling Salesman Problem (TSP) was used in the experiement that confirms the improved efficiency of the BCPGA.