P1=(12|3456|789) P2=(98|7654|321)
将P2的交配区域加到P1的前面或后面,P1的交配区域加到P2的前面或后面,得 M1=(7654|123456789) M2=(3456|987654321)
在M1中自交配区域后依次删除与交配区域相同的城市码,得到最终的两个子串: S1=(765412389) S2=(345698721)
同时为了能更好地增强算子的全局搜索能力,对该算子作了如下的改进。子代个体的新边来自:随机生成和群体中其他个体,其选择比例由随机数p和阈值P来决定。如果随机数p小于阈值P,则子代个体的新边来自随机生成,否则就来自群体中的其他个体。
这种改进后的交叉算子在父串相同的情况下仍能产生一定程度的变异效果,这对维持群体的多样化特性有一定的作用。实验结果也证实了这种改进算子对于种群的全局搜索能力有一定的提高,避免搜索陷入局部解。 2.2 局部启发式算子
为了增强遗传算法的局部搜索性能,在算法中引入2-Opt局部搜索算子[12]。该算子通过比较两条边并交换路径以提升算法的局部搜索性能,示例见图2。
比较子路径ab+cd和ac+bd,如果ab+cd>ac+bd则交换,否则就不交换。考虑到程序的运行效率,不可能对每对边都做检查,所以选取染色体中的一定数量的边进行比较。2-Opt搜索算子实际上进行的相当于变异操作,同时又不仅仅是简单的变异,而是提高算法的局部搜索性能的变异操作。
2.3 选择机制和收敛准则
为了限制种群的规模[13],该文采用了联赛选择法的淘汰规则。联赛选择法就是以各染色体的适应度作为评定标准,从群体中任意选择一定数目的个体,称为联赛规模,其中适应度最
高的个体保存到下一代。这个过程反复执行,直到保存到下一代的个体数达到预先设定的数目为止。这样做可能导致种群过早收敛,因此在收敛准则上要采取苛刻的要求来保证搜索的全局性。
遗传算法求TSP问题如果不设定终止条件,其演化过程将会无限制地进行下去。终止条件也称收敛准则,因为多数最优化问题事先并不了解最优的目标函数值,故无法判断寻优的精度。该文采用如下两条收敛准则:在连续K1代不再出现更优的染色体;优化解的染色体占种群的个数达K2的比例以上。当两准则均满足时,则终止运算,输出优化结果和对应的目标函数值。由数值实验表明,添加第2条准则之后,全局最优解的出现频率将大为提高。 2.4 基于多重搜索策略的群体演化算法
由于基因库的引入,可能降低初始种群的多样性,为避免算法陷入局部最优解,因此在群体演化中采取多重搜索策略。由Cheng-Fa Tsai提出的多重搜索策略[6],就是把染色体集中的染色体分成保守型和探索型两种不同类型的集合,然后针对不同类型的染色体集合根据不同的交叉、变异概率分别进行交叉变异操作,对保守型染色体集合就采用比较低的交叉变异概率,而对探索型染色体集合就采用比较高的交叉变异概率。这种策略对保守型染色体集合的操作最大限度地保留了父代的优秀基因片段,另一方面对探索型染色体集合的操作又尽可能地提高了算法的全局搜索能力。为了提高算法的收敛速度,初始染色体集合该文采用了前面单亲演化的结果中的染色体集合,交叉算子则利用的是前面介绍的改进后的算子,改进后的多重搜索策略见下。
3 实验结果与分析
该文的GB—MGA算法由C#编程实现,所有的结果都是在P42.0G微机上完成,并进行通用的TSP库实验,选用了具有一定代表性的TSP实例,并把该算法和其他算法做了一个对比。为了减少计算量,程序中的数据经过四舍五入整数化处理,与实数解有一定的偏差,下面给出图Kroa100的示例。
为了证明该文提出的GB—MGA算法的有效性,将该文算法与典型的遗传算法GA、单亲遗传算法PGA以及文[5]中杨辉提出的Ge—GA(gene pool genetic algorithm)算法和文[12]中提出的MMGA(modified multiple-searching genetic algorithm)算法都进行了一个对比。
实验结果证明,该文算法的求解质量要优于GA、PGA、MMGA算法,而求解速度方面则优于Ge—GA算法,特别是对于大规模城市的TSP问题求解效果尤其明显,具有快速收敛的特性。Ge—GA算法对于中等城市规模的TSP实例求解,其运算时间就大幅度增加,如果把该算法用于求解大规模和超大规模TSP问题,那么时间上的代价就让人无法忍受。而该文的GB—MGA算法在单亲遗传演化中就使用了基因库中的优质基因,使得单个个体的进化速度
大大提高,从而为进一步的演化提供了条件,群体演化过程的选择机制和收敛准则的恰当选取使得算法在注重了求解质量的同时兼顾了算法的效率。
结束语 该文在对TSP问题进行分析的基础上,通过对全局最优解和局部最优解中的边关系的分析发现,通过最小生成树的求解保存最有希望成为全局最优解的边,可以提高算法的效率,同时并不降低搜索的性能。在实验中发现,通过生成基因库快速提高种群质量,虽然可以快速收敛,但是TSP问题的求解质量并没有达到一个可以接受的程度,因此在群体演化阶段中又加入了2-Opt局部搜索算子和多重搜索策略,对不同类型的染色体以不同几率进行选择交叉操作。
用该算法测试TSP库中的典型实例,结果显示,对初始种群运用单亲遗传算法,并引入基因库方法是可行的,有效地提高了算法的效率和收敛速度,在群体演化过程中引入多重搜索策略的方法,提高了算法的并行性和全局寻优性能,即使在较少的寻优步数也能得到适应度不错的局部优化解。GB-MGA算法在提高算法求解质量的同时兼顾了算法的效率, 但是其中还有许多有待解决的问题,比如如何构建高质量的基因库,如何对现有基因库进行优化和扩充,以及算法中一些参数的选取问题等,这些方面,还需要进一步的研究。 参考文献
1 Bck T B,Hammel U,Schwefel H P.Evolutionary computation:Comments on the history and current state [J]. lEEE Transactions On Evolutionary Computation,1997,2(6):3~17 2王磊,潘进,焦李成.免疫算法[J].电子学报,2000,28(7):74~78
3 Dorigo M,Gambardella L M.Ant Colony System:A CooperativeLearning Approach to the Traveling Salesman Problem [J]. IEEETransactions on Evolutionary Computation,1997,2(8):53~66
4 Holland J H. Adaptation in Natural and Artificial Systems [M].Ann Arbor:The University of Michigan,1975.10~15
5杨辉,康立山,陈毓屏.一种基于构建基因库求解TSP问题的遗传算法[J].计算机学报,2003,26(12):1753~1758
6 Tsai Cheng-Fa, Tsai Chun-Wei, Yang Tzer. A Modified Multiple-Searching Method to Genetic Algorithms for Solving TravelingSalesman Problem [J].IEEE Transactions on Systems,Man andCybernetics,2002,3(10):6~12
7 Baraglia R,Hidalgo J I, Perego R. A Hybrid Heuristic for theTraveling Salesman Problem [J]. IEEE Transactions on Evolutionary Computation,2001,5(12):613~622
8 Tsai Cheng-Fa, Tsai Chun-Wei. A New Approach for SolvingLarge Traveling Salesman Problem Using Evolutionary Ant Rules[C].In:Proc.of the 2002 International Joint Conf.on Neural Networks,Hawaiian:honolulu,2002
9 Jung S,Moon B R.Toward Minimal Restriction of Genetic Encoding and Crossovers for the Two-Dimensional Euclidean TSP [J].IEEE Transactions on Evolutionary Computation,2002,6(12):557~565
10李茂军,童调生,罗隆诵.单亲遗传算法及其应用研究[J].湖南大学学报,1998,25(6):56~59
11陈国良,王煦法,庄镇泉,等.遗传算法及其应用[M].徐修存,王晓丹.北京:人民邮电出版社,1996.75~81
12 Watson J,Ross C,Eisele V,et al. The Traveling Salesrep Problem,Edge Assembly Crossover, and 2-opt [C].Parallel ProblemSolving from Nature V,Netherlands: Amsterdam,1998 13 Burkowski F J.Proximity and priority: applying a gene expressionalgorithm to the Traveling Salesperson Problem [J]. ParallelComputing,2004,30(5-6):803~816
GDDS的主要内容
国际货币基金组织（IMF）于1997年12月正式建立数据公布通用系统（GDDS），其总体框架主要包括数据特征、公布数据的质量、公布数据的完整性和公众获取4个部分。
一、数据特征：范围、频率和及时性
1、统计范围
GDDS将国民经济活动划分为五大经济部门：实际部门、财政部门、金融部门、对外部门和社会人口部门。对每一部门各选定一组能够反映其活动实绩和政策以及可以帮助理解经济发展和结构变化的最为重要的数据类别。系统提出了五大部门综合框架和相关的数据类别以及指标编制和公布的目标，鼓励以适当的、反映成员国需要和能力的频率和及时性来开发和公布指标。选定的数据类别和指标分为规定的和受鼓励的两类。
规定的数据类别包括：（1）来自综合框架中的核心部分，如实际部门的国民帐户总量、财政部门的中央政府预算总量、金融部门的广义货币和信贷总量、对外部门的国际收支总量；（2）追踪分析统计类目，如实际部门的各种生产指数、财政部门的中央政府财政收支和债务统计、金融部门的中央银行分析帐户、对外部门的国际储备和商品贸易统计；（3）与该部门相关的统计指标，如实际部门的劳动市场和价格指数统计；（4）社会人口数据，包括人口、保健、教育、卫生等方面统计。
除规定的数据类别以外，GDDS鼓励成员国发布更多的统计信息，以增强成员国经济实绩和政策的透明度。如实际部门列出储蓄、国民总收入指标，财政部门列出利息支付和偿债预计