当前位置: 东星资源网 > 中考资料 > 中考试题 > 正文

【遗传算法性能评价指标】 信息系统性能评价包含哪些指标

时间:2019-02-10 来源:东星资源网 本文已影响 手机版

   [提要] 实验研究过程中,我们发现:收敛时间、进化代数、全局搜索概率这三个性能评价指标在具体的评价过程中是不能同时达到最优的,因此本文提出了一种新的评价指标,即针对不同问题可赋予三个不同的权重,利用加权后的值作为评价指标来判断遗传算法的性能。
   关键词:遗传算法;进化代数;收敛时间;全局搜索能力;评价指标;权重
   中图分类号:TP3 文献标识码:A
   收录日期:2012年2月15日
   引言
   遗传算法(GA)由美国Michigan大学的Holland教授于1975年首先提出,后经De Jong、GoldBerg等人改进推广,广泛应用于各类问题。它是一种模拟自然界生物进化过程与机制的全局概率优化搜索方法。
   传统遗传算法中,人们常常利用进化代数、收敛时间和全局搜索能力等来评估算法的性能。而在进行算法的实验研究过程中,我们发现:收敛时间、进化代数、全局搜索概率这三个性能评价指标在具体的评价过程中是不能同时达到最优的。而且在研究种群规模对算法影响时发现:种群规模增大的过程中,三个指标变化方向是不同的、甚至是相反的,是相互矛盾的。因此,在用进化代数、收敛时间和全局搜索能力进行算法性能评价时,应该以哪一个指标作为评价标准是需要思考的问题,即我们需要一个参考标准。
   一、实际意义
   在实际问题中,我们评价算法的好坏要具有实际的意义,对三方面评价指标的要求也就有所不同。
   有些问题是时效性的,对算法的收敛时间要求很高,过了一定的时间限制所得到的结果是无意义的。如,铁路的调度问题中,最优调度方案需要及时给出,要求在最短的时间内得到各趟火车到站的停靠路线,那就对算法的收敛时间要求极高,而对算法的进化代数以及全局搜索能力要求不高,如果给出的算法收敛时间过长,在所需的时间之内不能给出最优解,则该结果失去了它的及时性,这样各火车之间就有可能会产生不可想象的后果。
   有些问题要求全局搜索能力要很强,在很多精密计算中,对算法的精度要求很高,也就是对全局搜索能力要求高,必须得到确切的最优解。如在炮弹的着陆点问题中,我们要求其最优解要非常精确,精确到一个很小的范围内,这样不论是在研究炮弹的精密性,还是在实战中,都有着举足轻重的作用,而此时对算法的收敛代数、收敛时间的要求相对就较低了。
   还有些问题要求有进化代数的限制,需要在有限的代数内得到最优解。在实际项目的完成过程中,每个结果的产生都需要付出一定的代价:人力、物力、财力,而为了降低成本,减少相关的支出,就需要限制进化代数,比如就要优化一次得到的结果,这样进化代数就为一,而对收敛时间和全局搜索能力的要求没有限制。
   因此,我们可以看出,在遗传算法中常用的三个评价指标:收敛时间、进化代数、全局搜索能力,我们可以根据实际需要调整他们在评价过程中的比重,进而使得进化性能得到更好地评价,能够在实际应用中发挥更重要的作用。为了比较评价不同的遗传算法,我们提出了一种新的评价指标来判断不同遗传算法的性能。
   二、评价指标
   在具体的遗传算法实验中,可以由使用者分别赋予收敛时间、进化代数、全局搜索能力以不同的权重,利用加权后的值作为评价指标。如:
   PGA=?棕1T+?棕2E+?棕3(1-P)
   其中,权值?棕1、?棕2、?棕3∈[0,1],且满足?棕1+?棕2+?棕3=1,T表示算法占用的CPU时间,E表示进化代数,P表示全局搜索能力。用PGA来衡量遗传算法的性能,PGA越小遗传算法的性能越好。
   在具体应用时,可以根据不同的要求调整权重?棕i的取值,体现在实际问题中其评价的重要性,从而满足不同的目的。
   对于时效性的问题,可以增大?棕1的取值,减小?棕2、?棕3的取值;对于全局搜索能力要求高的问题中,增大?棕3的取值,减小?棕1、?棕2的取值;而对进化代数有的限制的问题,增大?棕2的取值,减小?棕1、?棕3的取值。类似的,如果实际问题中要求的不仅仅是一个方面,就可以增大其中两个而减小另外一个,这样可以达到利用权值来控制各个性能所占用的比重,从而更好地得到最优解。
   三、结论
   本文提出了一种新的遗传算法性能评价指标,可以针对不同的情况,侧重不同的要求来调整进化代数、收敛时间、全局搜索概率的权重,进而评价改进后的遗传算法是不是有效地满足所需的指标。
  
  主要参考文献:
  [1]李敏强,寇纪淞,林丹等.遗传算法的基本理论与应用[M].北京:科学出版社,2004.
  [2]王力,侯燕玲.基于遗传算法通用试题库系统研究[J].微计算机信息,2008.
  [3]王小平,曹立明.遗传算法――理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
  [4]刘刚,曹勇,李华德.几种改进遗传算法的性能比较[J].微计算机信息,2007.23.
  [5]徐晓华,陈?,陈宏建.可变种群规模的遗传算法[J].系统仿真学报,2006.18.

标签:遗传 算法 评价指标 性能