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

    遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说来，遗传算法是按不依赖于问题本身的方式去求解问题。它的目标是搜索这个多维、高度非线性空间以找到具有最优适应值(即最小费用的)的点^[1]。

    基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子和变异算子作用于种群，最终可得到问题的最优解和近似最优解。

    本文研究的遗传算法及改进算法的实现是以C⁺⁺语言为基础，在Windows2000的版本上运行，其实现程序是在Microsoft Visual Stadio 6.0上编写及运行调试的。

    1) 遗传算法的执行代码

m_Tsp.Initpop()；            //种群的初始化

for(int i=0；i<m_Tsp.ReturnPop()；i++)

         m_Tsp.calculatefitness(i)；  //计算各个个体的适应值

m_Tsp.statistics()；         //统计最优个体

while(entropy>decen||variance>decvar)//m_Tsp.m_gen<100)

{

//将新种群更迭为旧种群，并进行遗传操作

m_Tsp.alternate()；         //将新种群付给旧种群

m_Tsp.generation()；        //对旧种群进行遗传操作，产生新种群

m_Tsp.m_gen++；

m_Tsp.statistics()；        //对新产生的种群进行统计

}

    2) 简单的遗传算法与分支定界法对TSP问题求解结果的对比

    遗传算法在解决NPC问题的领域内具有寻找最优解的能力。但随着城市个数的增加，已没有精确解，无法确定遗传算法求解的精度有多高。一般情况下，当迭代代数增大时，解的精度可能高，但是时间开销也会增大。因此可以通过改进遗传算法来提高搜索能力，提高解的精度。

表1  10个城市的TSP问题求解结果数据

算法 试验结果	简单遗传算法		分支定界法
	最佳解	时间	精确解	时间
试验1	2448.610037	5s	2448.610037	00：07：30
试验2	2448.610037	13s
试验3	2448.610037	9s
试验4	2459.543054	10s
试验5	2459.543054	7s

    1) 初始化启发信息

    在上述实验算法的基础上，对每一个初始化的个体的每五个相邻城市用分支界定法寻找最优子路径，然后执行遗传算法。

    2) 遗传算法与含有启发信息的遗传算法求解结果的对比

    当城市数增至20个时，用分支定界法已经不可能在可以接受的时间内得到精确的解了，只能通过近似算法获得其可接受的解。试验设计中算法的截止条件：固定迭代1000代。表2中的平均最优解为经过多次试验(10次以上)得到的最优解的平均值，最优解的出现时间为最优解出现的平均时间，交叉操作次数为最优解出现时交叉次数的平均值。

表2  20个城市的TSP问题求解结果数据

算法	交叉操作 次数	最优解 出现时间	平均 最优解
简单遗传算法	80244.4	79.4s	1641.8
含初始化启发信息的GA	79000.2	37.4s	1398.9

    从表2中可以看出，当初始种群时引入启发信息将提高遗传算法的寻优能力。同时缩短了遗传算法的寻优时间和问题的求解精度。

    1)循环贪心交叉算子的核心代码

for(i=1；i<m_Chrom；i++)

{

  flag=0；

  city=m_newpop[first].chrom[i-1]；         //确定当前城市

  j=0；

  while(flag==0&&j<4)

  {

      sign=adjcity[city][j]； //adjcity数组的数据为当前城市按顺序排列的邻接城市

      flag=judge(first，i，sign)；  //判断此邻接城市是否已经存在待形成的个体中

      j++；

  }

  if(flag= =0)       //如果所有邻接城市皆在待扩展的个体中

  {

      while(flag= =0)

      {

           sign=(int)rand()/(RAND_MAX/(m_ Chrom-1))；     //随机选择一城市

           flag=judge(first，i，sign)；

      }

  }

  if(flag==1)

      m_newpop[first].chrom[i]=sign；

  }

    2)问题描述与结果比较

    下面笔者用经典的测试遗传算法效率的Oliver TSP问题来测试循环贪心交叉算子的解的精度和解效率。Oliver TSP问题的30个城市位置坐标如表3所示^[2]。

表3  Oliver TSP问题的30个城市位置坐标

城市编号	坐标	城市编号	坐标	城市编号	坐标
1	(87，7)	11	(58，69)	21	(4，50)
2	(91，83)	12	(54，62)	22	(13，40)
3	(83，46)	13	(51，67)	23	(18，40)
4	(71，44)	14	(37，84)	24	(24，42)
5	(64，60)	15	(41，94)	25	(25，38)
6	(68，58)	16	(2，99)	26	(41，26)
7	(83，69)	17	(7，64)	27	(45，21)
8	(87，76)	18	(22，60)	28	(44，35)
9	(74，78)	19	(25，62)	29	(58，35)
10	(71，71)	20	(18，54)	30	(62，32)

 

表4  贪心交叉与部分匹配交叉的比较(Oliver TSP问题的30个城市)

交叉算子	交叉操作次数	平均时间	平均最优解
部分匹配交叉	59760	31.2s	517.0
贪心交叉	15774	28.6s	433.4