遗传算法程序设计探讨(2)

 

图1  遗传算法的收敛过程

    1)主程序代码

//接收各个从程序的最优个体

for(i=0；i<slave；i++)

{

MPI_Recv(Rchrom[i]，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；

}

//计算接收各个从程序的最优个体的回路距离

for(i=0；i<slave；i++)

{

        fitness[i]=0.0；

        for(int j=0；j<chrom-1；j++)

        fitness[i]=fitness[i]+distance[Rchrom[i][j]][Rchrom [i][j+1]]；

        fitness[i]=fitness[i]+distance[Rchrom[i][0]][Rchrom [i][chrom-1]]；           

}

//找到最优的个体并把它记录到文件里

        for(i=0；i<slave；i++)

        {

            if(1/fitness[i]>min)

            {

                 sign=i；

                 min=1/fitness[i]；

            }

        }

        fwrite(&gen，sizeof(int)，1，out)；

        for(i=0；i<chrom；i++)

        fwrite(&Rchrom[sign][i]，sizeof(unsigned)，1，out)；

        fwrite(&fitness[sign]，sizeof(double)，1，out)；

        //每九代向从程序发送一个最优个体

        if(gen%9==0)

        MPI_Bcast(Rchrom[sign]，chrom，MPI_ UNSIGNED，0，MPI_COMM_WORLD)；

    2)从程序代码

//将上一代的最优个体传回主程序

MPI_Send(Rchrom1，chrom，MPI_UNSIGNED，0，gen，MPI_COMM_WORLD)；

//每九代接收一个最优个体并将其加入种群中替换掉最差个体

if(gen%9==0)

{

    PI_Bcast(Rchrom2，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；

    Tsp.IndiAlternate(Rchrom2)；

}

//进行下一代的计算

Tsp.Aternate()；

Tsp.Generation()；    

Tsp.Statistics()；        

    3)并行遗传算法的性能

    笔者在MPI并行环境下，用C^＋＋语言实现了一个解决TSP问题的粗粒度模型的并行遗传算法。该程序采用的是主从式的MPI程序设计，通过从硬盘的文件中读取数据来设置染色体长度、种群的规模、交叉概率和变异概率等参数。试验环境为曙光TC1700机，测试的对象是Oliver TSP问题的30个城市的TSP问题。

    正如在测试串行遗传算法所提到的数据结果，并行遗传算法也没有达到目前所记录的最好解，但是它提高了算法的收敛性，并行遗传算法的收敛趋势如图2所示^[4]。

 

图2  遗传算法的收敛过程

    本文通过对基本遗传算法的不断改进，证明了添加启发信息、改进遗传算子和利用遗传算法固有的并行性都可以提高遗传算法的收敛性，其中对遗传算法交叉算子的改进可以大大提高遗传算法的寻优能力。

[1] 刘勇、康立山，陈毓屏著． 非数值并行算法－遗传算法．北京：科学出版社 1995.1

[2] I M Oliver D J Smith and J R C Holland，A study of permutation crossover operators on the traveling salesman[C]// Problem of the second International Conference on Genetic Algorithms and Their Application，Erlbaum 1897： 224-230

[3] 于海斌，王浩波，徐心和． 两代竞争遗传算法及其应用研究 ．信息与控制，2000 Vol.29，No.4：309-314

[4]穆艳玲，李学武，高润泉． 遗传算法解TSP问题的并行实现．北京联合大学学报(自然科学版)，2006 Vol.20 No.2： 40-43