基于corba的分布式遗传算法在csp问题中的应用

基于corba的分布式遗传算法在csp问题中的应用

1tsp分布式计算tsp（交通便利的商业手段）是一个通过证明非营利时间复杂性来优化的问题。它的简单描述是：平面上有N(N>0）个城市，一推销员欲遍历所有城市，且每个城市仅能访问一次，并最后回到起始点，问按照怎样的城市遍历顺序，路径长度最短。即搜索子集X={1,2，…，n}（X的元素表示n个城市的编号）的一个排列π（X={v1,v2，…，vn}），使得取最小值。d(vi,vi+1）表示城市vi到城市vi+1的距离。根据排列组合理论，显然规模为N的TSP问题的有效解个数为N选。随着N线性增大，有效解搜索空间呈指数速度增长。由于该问题的典型性，使得快速、有效解决TSP有着重要的理论价值和应用价值。求解TSP问题比较成熟的算法有遗传算法、Hopfiled人工神经网络、模拟退火等，其中遗传算法是被认为是求解效率较高的一种算法。遗传算法依照自然界生物进化规律，通过对染色体的选择、杂交和变异操作来获取问题空间中的最优解或次优解。简单遗传算法是一种串行算法，适合于对小规模TSP问题求解。对大规模TSP问题，则在处理器速度和内存大小方面对机器有极高要求，而现阶段计算机硬件制造技术尚未达到该水平，所以利用并行计算代替串行计算便成了一种必然。孤岛模型是并行遗传算法，它的依据是：自然进化过程中总存在大量物种在彼此独立的空间向前进化，这种在不同空间独立进化的自然过程，可被抽象为并行演化。孤岛模型目前的软件实现方式有以下三种：一、在同一并行机上，多处理器并行计算；二、在单机上串行模拟；三、在网络环境中，通过TCP/IP协议，并行计算。由于经济原因，国内多数大学或研究部门很缺少并行机计算环境。且并行机上的软件因专用针对性太强，开发人员比较少。单机模拟对TSP问题规模有局限。用TCP/IP协议在网络上实现遗传算法的分布式计算需要约定与实现通信规程，设计开销大，且软件互通性差。从软件可重用性角度来看，使用通用的类和组件开发是今后分布式计算的发展潮流。基于以上的考虑，以下讨论用CORBA分布式求解TSP问题的方法。2采用分布式遗传统计法求解tsp问题的corba实现2.1客户机/服务器程序间通信采用CORBA技术实现分布式遗传算法有以下优点：（1）利用PC机组成的计算机局域网通信速度快，且易实现分布式并行计算。在局域网环境中，利用CORBA实现分布式计算的条件已经具备，不增加硬件投资；（2）通信协议透明性。利用Socket技术设计客户机/服务器程序时，需要自己定义和实现一套通信规程。而CORBA与Socket技术相比的优势是：CORBA在TCP层之上，实现了IIOP协议。它以ORB实现客户机与服务器程序间通信的中间件，ORB寻找适配完成请求工作的对象，并在服务器对象执行操作后返回结果。由于CORBA对待远程调用就像调用本地方法一样，大大简化了程序设计工作；（3）硬件无关性，平台透明性。CORBA的主要作用是用来屏蔽网络硬件的差异性和操作系统的异构性，使应用软件能够比较平滑地运行于不同平台上。同时在平衡负载、连接管理和调度方面起着协调作用。这种开放性充分利用了现有资源；（4)CORBA代表的软组件、软总线是未来程序设计的发展趋势，利用CORBA有利于程序在将来保持长期有效性。2.2应用服务器层图1示出了利用CORBA实现分布式遗传算法求解TSP问题的软件结构模型。该结构分成三层：第一层是浏览器层。用户通过因特网浏览可以访问该主页，通过页面中嵌入的JavaApplet程序，自定义TSP问题的规模、节点数据，最终能从该程序中得到计算结果。用户不必关心执行分布式计算的实际物理地址和实现算法；第二层是应用服务器层，应用服务器包括WWW服务器和TSP问题分布式计算应用服务器。WWW服务器通过HTTP协议与用户端的浏览器通信，而TSP问题分布式计算应用服务器在目录服务器注册后，提供CORBA对象接口被浏览器中的Applet程序远程调用，二者间通过IIOP协议进行通信。TSP问题分布式计算应用服务器的任务是发现现存孤岛，并将用户的计算任务和计算数据发送给各个孤岛，并以松耦合的形式控制多个孤岛计算，它自身并不做任何计算操作。由于Java语言的安全性限制，应用服务器中的两个程序必须运行在一台计算机中。目录服务器是第三方软件，它主要提供命名服务，目前在小系统中可以采用JDK中的命名服务，对大系统可以采用LDAP服务器；第三层是分布式遗传算法的实际计算进程。图1中的每个孤岛都代表运行在不同计算机中的遗传算法的计算进程。2.3并行遗传算法tsp采用CORBA实现分布式遗传算法与并行遗传算法相比较，有以下优点：（1）并行机中各孤岛采用的计算方法是一致的，易同时收敛于同一局部最优解。而基于网络的分布式计算模型中，各个孤岛可以采用不同的演化计算方法来对问题求解，各个孤岛只要求通信接口一致即可，内部的实现对个孤岛对象之间是透明的。不同孤岛采用不同的计算方法，甚至是采用神经网络或模拟退火算法进行计算，均可以在本软件结构中灵活实现。孤岛间的相异性，是对自然进化中各孤岛有自己不同特色的方式进化的成功模拟，从而从自然演化的多态性，可以映射本最优化求解问题中各孤岛求解结果分布的空间多态性。这对组合优化问题求解，避免求解区间过早收敛于某一局部最优区间是大有帮助的；（2）在并行遗传算法计算过程中，为了动态平衡各个孤岛间的计算负载，常采用征兵方式或招募方式。但是二者实现无论是采用紧耦合还是松耦合，进程间都需要一种N2次（如果同时有N个孤岛）查询，时间复杂度较高。而图1的三层结构中，繁忙孤岛进程可以直接去TSP问题分布式计算应用服务器获取空闲孤岛进程的ORB引用实例，然后完成计算负载的转移。比并行计算中的负载平衡要易于实现。3实验方法和计算3.1实验程序设计随着计算机网络应用水平的提高，软件跨平台计算能力成为衡量软件质量的一个重要指标。C语言是一种高效率的程序设计语言，目前在集中式遗传算法计算中采用C++比较多。但C++程序设计难度较高，且对分布式网络计算能力不及Java，所以本次实验使用Java作为程序设计语言。Java是目前最为流行的跨平台计算语言，且能方便地嵌入到HTML页面中，在网络上发布。因此实验中选择JDK1.3作为程序设计语言。该程序可以真正实现一次编译后，在各种装有Java虚拟机的操作系统上执行，无需修改。实验中计算的TSP问题是规模为34的中国旅行商问题CTSP(ChinaTravelingSalesmanProblem),34个城市分别为31个直辖市、省会和自治区首府，2个特别行政区（香港、澳门）以及台北。孤岛采用简单遗传算法进行计算，其具体实现过程见文献。杂交算子是部分映射杂交算子，个体适应度是环路长度。杂交父体的选择使用联赛机制，即每次从群体中随机选择num(num为联赛规模）条染色体，然后将这些个体按适应度大小排序，适应度最小的两个作为杂交父体，而最大的两个则被新生个体替代。实验中杂交发生概率置为1，变异发生概率置为0。本次实验中存在3个孤岛（在3台计算机上运行），每个孤岛每繁衍multiplyNumber/4代就向邻近岛迁移部分个体（multiplyNumber为最大繁衍代数）。在4次迁移中，迁移目的孤岛任意，以保持算法的随机性。迁入个体集取代被迁入子群体中适应度最差的个体集。3.2遗传算法比较当采用排序迁出式策略，孤岛子群体规模为1200，迁移率为20‰，繁衍代数为25000时，实验得到最短回路（路径长度为15676千米）。该路径是：合肥--南京--上海--杭州--台北--福州--南昌--武汉--长沙--广州--澳门--香港--海口--南宁--昆明--贵阳--重庆--成都--拉萨--乌鲁木齐--西宁--兰州--银川--呼和浩特--哈尔滨--长春--沈阳--北京--天津--济南--石家庄--太原--西安--郑州--合肥与该遗传算法的集中式计算结果（15704千米）相比较，环路长度缩短28千米。由于关于34点CTSP问题的计算结果不多，于是从该环路中除去香港、澳门、重庆三个城市，再将回路长度与31点CTSP问题的最短路径作比较。用遗传算法得到的最优解比用Hopfield神经网络求出的全局最优解15449千米长度少32千米；但比文献中的最优解15404千米略差。对比来看，该结果是很不错的。关于算法求解的最优性测试在论文第5部分有详细的验证。4试验中显示的三个规律4.1未算例sagct调查问卷的统计描述分布式遗传算法的个体迁移有多种策略。实验中比较了“最优迁移策略”和“随机迁移策略”对计算结果的影响程度。“最优迁移策略”BM(BestMigration）从孤岛的整个群体中选择最优个体集迁移给目标孤岛，迁移前需要对整个群体的个体适应度排序；在“随机迁移策略”RM(RandomMigration）中，随机选择个体集迁移。有资料表明随机选择所产生的效果至少不比其它任何方法差。为了验证该规律，于是对各群体规模做50次计算，然后从中挑选回路长度最小的30项作为有效统计项，求其算术平均值。使用这种统计方法的原因是遗传算法具有随机性，用均值比较，更利于反映普遍性规律。图2、图3示出了在子群体规模（subP）为1200、1500时，随迁移率MR(MigrationRate）的变化，BM策略和RM策略的解质量。从图中可以看出BM策略与RM策略解质量相当，总体走势与解分布比较一致，但BM策略在最优解上比RM策略稍胜一筹。BM在迁出前必须对整个子群体的适应度排序，排序算法最佳的平均时间为O(nlogn），开销是很大的；而采用RM无需排序，时间花费很小，且所得到的解并无太大悬殊，尚可以接受。所以在实际应用中应视具体情况采用不同的策略，当迁移频率较高时可选择RM，当迁移频率较低时可选择BM。论文中的以下实验均使用RM策略。4.2子群体规模司bp测试迁移率即一个孤岛向其它孤岛迁移的个体数占其整个子群体规模的比例。这个比例既不能太低，也不能太高。太低的迁移率对邻近孤岛的影响甚微，不足以改变现状；而太高的迁移率不仅使得通信开销增大，还可能使群体中的个体失去多样性，不利于最优解的产生。作者对迁移率为5‰、10‰、15‰、20‰、25‰，子群体规模（subP）为1200、1500、1800、2100的参数组合进行了测试，如图4、图5所示。结果表明迁移率在20‰附近易求得最优解。解分布并不严格遵守此规律，在相邻的迁移率有反复，这正体现了遗传算法求解的随机性。4.3衍代的生物量和时间在寻求最优解的过程中，实验中首先设置的繁衍代数是5000，但计算后发现结果不尽人意，于是以5000为步长，保持其它参数不变，将繁衍代数逐渐增大到35000。繁衍代数在达到一定的值以后，解趋于稳定。达到平衡后，就需要其它环境中的优秀个体突破地理限制，迁移进来以帮助其改善后代，跳出局部最优，达到全局最优。所以，繁衍代数并不是多多益善，繁衍代数越大、时间花费越多，它只要达到了求解要求即可。图6、图7示出了繁衍代数RG(ReproductionGeneration）在15000、20000、25000、30000、35000，子群体规模为1200和1500，迁移率为20‰时的解质量情况。5设置几何节点分布由于当前没有其它数据可以直接验证分布式遗传算法解TSP问题的有效性和评估求解质量，作者设计了三组标准几何分布数据，对上述的分布式遗传算法和参数设置规律加以验证。这三组数据分别是100×50的矩形边界上30等分点的坐标、100×100的正方形边界上40等分点的坐标和直径为100的圆边界上35等分点的坐标，节点分布如图8所示。选择这3组数据进行验证是基于两点考虑：（1）这些几何图形很容易证明沿其边界顺序连接各点得到的回路长度最短；（2）验证遗传算法求解与拓扑结构无关。实验结果如表1所示。以上数据表明实验规律对于N=35左右的TSP问题是适用的，而且遗传算法求解确实与拓扑结构无关。6实验结果及反思论文提出了基于CORBA的分布式遗传算法模型，它是求解大规模NP问题的一种有效途径。作者利用Java语言，在计算机局域网环境中实现了该软件模型，并通过该算法对CTSP问题求解，发现了其中关于孤岛计算参数设置与最优解影响的三组实验规律。由于从理论上分析该算法有一定困难，作者设计了多组数据来验证其有效性、求解