遗传学条件概率范文

关键词：编码；交换；交叉算子；变异算子

中图分类号：TN929.5文献标识码：B文章编号：1009-9166（2009）02（c）-0056-02

遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。

一、遗传算法的基本流程

遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有的信息来指导搜索有希望改善优化质量的状态。标准遗传算法的流程图如图1所示。

主要步骤可描述入下：

(1)随机产生一组初始个体构成初始种群，并评价每一个体的适配值。(2)判断算法的收敛准则是否满足。若满足则输出搜索结果；否则执行以下步骤。(3)根据适配值大小以一定方式执行复制操作。(4)按交叉概率执行交叉操作。(5)按变异概率执行变异操作。(6)返回步骤，上述算法中，适配值是对染色体进行评价的一种指标，是GA进行优化所用的主要信息，它与个体的目标值存在一种对应关系；复制操作通常采用比例复制，即复制概率正比于个体的适配值，如此意味着适配值高的个体在下一代中复制自身的概率大，从而提高了总群的平均适配值；交叉操作通过交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，从而有助于产生优良的个体；变异操作通过随机改变个体中某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛。

二、移动通信中的遗传算法

（一）信道分配中的遗传算法。信道分配（CAP）属于组合优化中的NP完备问题，目的是提高系统对频率资源的有效利用率，它反映在两个方面：(1)在指定信道资源和服务质量的条件下，设法找到一种最佳的方法将这些信道分配给小区的呼叫；(2)在已知系统话务量分布和给定呼叫阻塞率条件下，确定满足服务要求所需信道数最少的方案。

目前常用的算法有：图形着色算法、神经网络算法、模拟退火算法、启发式算法、爬山法、找最大独立团法和遗传算法等。在遗传算法中提出了用一种改进的组合遗传算法进行信道分配，主要是针对“热点”小区信道分配难的情况，在“热点”小区设置了信道分配的优先级，从而提高了最优分配方案的收敛性。组合遗传算法（CGA）是把排序分配法和遗传算法相结合，利用遗传算法强大的搜索能力寻找和确定最佳呼叫列表，然后采用排序分配法试探和寻找最佳信道分配方案。CGA算法与其它应用遗传算法解决CAP方法的关键差异在于CGA中遗传算法的主要作用是寻找和优化最佳列表，而不是直接去寻找最佳信道分配结果。CGA算法对于现实中话务量分布非均匀蜂窝小区的信道分配问题存在算法收敛性差和运算花费时间大的问题。因此提出了用改进的组合遗传算法（MCGA）进行信道分配，在信道分配时考虑采用基于分配难度的小区排序方法，给予这些“热点”小区一定的优先级，以便让这些小区首先获得信道，并在CGA对整个解空间进行随机搜索时，注入一定的导向性信息加快CGA算法的收敛时间，提高它的收敛率。信道分配的目标是得到一个用最少的信道数，满足话务需求和电磁兼容限制的信道分配方案，即上面提到的提高频率资源有效利用率的情况（2）。为此采用了最小间隔编码方案，利用了固定遗传算子（交叉和变异），在整个迭代过程中始终满足话务需求的要求。在信道分配过程中按照标准的遗传算法流程进行，为了满足同位置限制的条件（CSC），采用了最小间隔编码方案；适值函数也是按照约束条件选取的：首先，必须满足需求向量的要求；

其次是CSC，还有同频限制（CCC）和邻频限制（ACC）；初始化种群时，先分配需求信道最多的前两个小区，剩余小区随机分配；在单点交叉和双点交叉算子的基础上提出了两种新的交叉算法（X1和X2）；为了保持种群的多样性，采用了三种变异算子（M1、M2和M3）；采用的选择操作是基于扩大的采样空间，双亲和后代有同样的生存竞争机会，这样可以用增加交叉率和变异率的方法来改进遗传算法的性能。采用了基于概率的随机竞赛选择方法（赌）。最后证实，遗传算法能很好的解决信道分配问题，性能受遗传算子的影响比较大，当采用基于两点交叉的交叉算子X2和选择性变异算子M3时，其性能更好。而且证明算法是有效的。在分析过去信道分配方法的基础上，提出了用遗传算法动态优化分配TD-SCDMA系统的信道资源，利用载频、时隙和扩频码对染色体进行编码，把通信干扰、业务类型、设备性能等作为个体选择的约束条件，可以寻求出全局最优信道分配方案。在染色体编码时，巧妙地构造了载频窗、时隙窗和扩频窗；在初始种群选择时，运用这些窗缩小了搜索范围，采用最优个体保存法选择优化种群，即用适应值最大的部分染色体淘汰掉适应值最小的部分染色体；选择单点交叉方式，这样可以保证一些优秀的基因不被淘汰；利用遗传算法可以最大可能的实现无线网络管理器（RNC）在全局最优解，最大限度地提高业务容量和业务质量，解决了现代工程动态信道分配中的不足。文中基于信道分配与遗传算法各自的特点构造了遗传算法的信道分配实现方案，根据信道分配的优化原则给出一个定理。为了克服遗传算法爬山能力差的弱点，提出一种自适应遗传方法。该方案与现有的FCA和DCA方案相比，有较小的呼阻率和较高的频谱利用率，不论在业务量较大还是较小都能取得较好的性能指标。

（二）CDMA多用户检测中的遗传算法。多用户信号的最佳检测在数学上可归结为求似然函数最大值问题，其求解过程相当复杂，实时性差，可以转化为在遗传算法中求解具有最高适应度函数的问题。在多用户信号最佳检测中提出了一种基于并行遗传算法的CDMA多用户检测器，通过与最佳多用户检测和传统检测器进行比较，表明采用并行遗传算法不仅能接近最佳监测器性能，而且易于实时应用和硬件实现。并行遗传算法将并行计算机的高速并行性和遗传算法天然的并行性相结合，并将遗传算法中的交叉算子和变异算子分别设计为与/或和同或/异或，极大地提升了遗传算法的性能。CDMA多用户检测器中先给出了在异步瑞利衰落信道下解调扩频信号的分集接收混合遗传算法多用户检测器的原理框图，然后分析了用混合遗传算法（HGA）进行多用户检测的理论依据和实际性能，仿真结果表明无论是抗多址干扰还是抑制远近效应，分集接收混合遗传算法多用户检测器都明显优于传统接收机，其性能接近分集接收最佳多用户检测器。HGA融合了遗传算法的并行处理和模拟退火算法的全局收敛的长处，并根据信息熵来搜索全局最优点，能实现快速全局收敛。HGA主要过程有：（1）编码；（2）用相关信息熵指导产生初始解群，避免初始解群对算法收敛的影响；（3）确定二进制串的适应值和平均相关适应值；（4）利用平均相关适应值确定群体中每个二进制串的生存概率，保持群体多样性，根据Metropolis准则搜索最优二进制串并输出判决变量。在这中间，用平均相关适应值代替了遗传算法在计算生存概率时所使用的适应值，这样可以保持群体中二进制串的多样性，避免算法收敛于局部极小点。HGA在接受新解时，除了接受优化解外，还在一定范围内接受恶化解。这是HGA与遗传算法的本质区别所在。

（三）遗传算法在移动通信中的其它应用。遗传算法在无限资源分配领域也有应用，文中提出了一种基于遗传算法的功率控制方法，与现有的基于固定迭代的功率控制方法相比，有效地提高了CDMA蜂窝移动通信系统中功率控制的收敛速度，降低了计算的复杂度。在卫星移动通信系统Flower星座设计中，给出了遗传算法的优化模型。在卫星星座的优化设计中，大量的参数需要反复调整和计算，运用遗传算法可以优化设计，提高卫星通信覆盖率。遗传算法还在无线通信网基站优化选址中有应用，针对一个区域，提出了在k个备选的位置中选择合适组合的粗粒度并行遗传算法，能在不提高成本的同时优化网络的覆盖率。此外，遗传算法还可以用来优化网络的参数，如QoS。在GSM移动通信网络频率规划中也有应用。

作者单位：浙江师范大学

参考文献：

[1]雷英杰,张善文,李续武,周创明编著.MATLAB遗传算法工具箱及应用[M].西安电子科技大学出版社,2005

遗传学条件概率范文篇2

关键词：排课；遗传算法；全局寻优；自动排课

中图分类号：TP301.6文献标识码：A文章编号：1009-3044(2008)33-1463-03

AKindofBasedonGeneticAlgorithmtheApplicationinLayoutCourseTable

QIAOAn-hong

(JiaxingUniversity,Jiaxing314001,China)

Abstract:CoursetablerowlessonarrangementandmanagementareeveryschoolcampaignworkofeducationaladministrationwithfrequentlyimportantCentralAfrica,itreliesoncomputertocompletecomplexrowlessonpart,haveavoidedtheteacherthathandworkrowlessonproducestoattendclasstimeconflictandclassroomconflict.Itisstudiedthatthispaperutilizestheoverallsituationofgeneticalgorithmtoseekthegooddesignconceptionforthesystemofautomaticrowlessonandthecourseofrealizingandhasgoneon,andbegtountieusinggeneticalgorithmforproblem.Inevolutioncoursehaveacceleratedgroupwithakindofnewhereditarystrategyshowrestraintspeed.Andhavegottenagoodalgorithmofthecoursetablemodelthatsolvestosuitschoolrequirement.

Keywords:queueuplesson;geneticalgorithm;overallsituationseekgood;queueuplessonvoluntarily

1引言

学校课程表排课安排和管理是每个学校教务活动中非常重要的工作，它涉及面广、限制条件多，而计算机自动排课系统设计就是根据教学计划的内容以及一些限制条件自动生成课程表，从而减轻排课的工作量、提高排课的效率和科学性，其功能是可根据用户需求进行如下的排课生成：设置上午、下午、晚上的上课节数，全校每天不排课的限制、上课周数。专业配课、年级配课、班级配课。课程信息设置，包含任课老师，性质、课时等。教室信息设置，包括性质、隶属。教师的信息配置，包括教授的课程、特殊情况等自动排课生成各类课表手动编排。

目前最具科学性的方法：使用计算机软件技术配合手工排课。就是将人脑和电脑的优势结合在一起发挥作用――即具有“人工排课”的灵活、合理性，又具有“智能排课软件”的便捷性。（也就是“计算机辅助排课”）使用计算机辅助排课系统的自动教师资源、教室资源和时间资源组成的效率与质量完全取决于时间表算法的设计。遗传算法以其自适应寻优及良好的智能搜索技术，受到了广泛的运用。PottsJC等人基于变异和人工选择的遗传算法对最优群体规模进行了论述；HamiltonMA等结合遗传算法把其运用到神经网络中，并取得了良好的效果；也有众多的学者对保留最佳状态的遗传算法的收敛速度做了讨论。通过理论推导和事实运用，发现遗传算法在寻优和收敛性方面都是非常有效的、确实可行的一种解决方法。

2问题描述

传统的人工排课，最令人担心的问题就是――出现教室资源冲突或教师资源冲突的情况。而且工作繁琐，工作量巨大。况且我发现目前的排课软件普遍存在――排课条件设置复杂，难以做到课程的合理分布（例如：数学、英语等主课多数要安排在上午上课）、出错概率高、难以操作等缺点。计算机自动排课系统实际上是时间表的优化问题。如何根据班级的课程设置、课程的周内次数、现有教室资源、以及现有教师资源进行科学的合理安排，提供给学校的教务部门一个自动排课系统，在实际工作中具有一定的应用价值。

在进行计算机自动排课系统设计过程中，我考虑了三类资源：一类是教师资源，一类是教室资源，一类是时间资源。教师资源包括在编教师和每个教师历年所上过的课程、以及所上过课程的评价值。同一课程可能有多名教师能开课，在资源分配允许的情况下，自然选择评价值高的教师上这门课。多数情况下，在进行教学任务安排时，已经人为考虑了教师和课程之间的固定联系。教室资源是指现有可用教室。时间资源是指允许可用的时间段。此外，按每学期教学大纲，本学期每个班(专业)所上课程和每门课的周学时数(次数)是预定的。同时，我还需要考虑不同时间段的上课效果。排课问题是根据现有教师资源、教室资源和时间资源，如何使排课结果最佳。适当定义相应的一些评价系数后，排课问题变成了一个时间表的优化问题。

而排课数据结构模型的产生和实现是计算机排课系统自动化或半自动化操作的核心目标之一，而如何保证生成的课程表能最大程度的满足用户的不同需要,并具有随机性、科学性、合理性，这是实现中的一个难点。尤其在交互式环境下用户对于生成课表速度要求较高，而一个理论上较完美的算法可能会以牺牲时间作为代价，往往不能达到预期的效果。因此，选择一个高效、科学、合理的算法是自动排课的关键。

以往计算机排课系统算法的实现，大多采用随机选取法和回溯试探法。两种算法各有其优缺点，在限制条件状态空间的控制下，随机选取法有时能够获取一组令用户满意的课表。只不过由于它随机选取时间表的的范围太大，无法确定目前条件下哪些区域能够抽取合适的时间表，反而可能在那些已经证明是无法抽取在合适课表的区域内反复选取，进行大量的无效操作进入死循环，最终导致课表生成失败。回溯试探法用于课表生成的成功率较高，但它是以牺牲大量的搜索时间为代价的，已不适合应用要求。因此,必须结合以上两种方法寻找一种新的改进算法，这种算法要具有全局寻优和收敛速度快的特点。遗传算法以其具有自适应全局寻优和智能搜索技术，并且以收敛性好的特性很好的满足课表自动生成的需求算法。

3遗传算法描述

3.1遗传算法基本思想

遗传算法（GeneticAlgorithm，缩写为GA）是一种有效的解决最优化问题的方法。它是基于人类社会的进化过程，遗传算法首先利用随机方式产生一切始群体（祖先），群体中的每个个体称为染色体，它对应着优化问题的一个可能解，染色体的最小组成元素应称为基因，它对应可能解的某一特征，即设计变量。染色体的评价函数值反映可能解的优劣，按照优胜劣汰原则对染色体进行选择，相对“好”的个体繁殖，相对“差”的个体将死亡，因此群体整体的性能，通过选择、杂交、突变等过程将趋于改善，经过若干代繁衍进化就可使群体性能趋于最佳。其实质就是一种把自然界有机体的优胜劣汰的自然选择、适者生存的进化机制与同一群体中个体与个体间的随机信息交换机制相结合的搜索算法。

3.2遗传算法的基本步骤

1)定义一个目标函数;2)将可行解群体在一定的约束条件下初始化,每一个可行解用一个向量X来编码，称染色体，向里的分量代表基因，它对应可行解的某一决策变量；3)计算群体中每条染色体Xi（i=1,2,……,n）所对应的目标函数值，并以此计算机适应值Fi，按Fi的大小来评价该可行解的好坏；4)以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的好坏，按概率随机选择，进行繁殖，形成新的群体；5)通过杂交和变异的操作，产生子代。杂交是随机选择两条染色体（双亲），将某一点或多点的基因互换而产生两个新个体，普通异是基因中的某一点或多点发生突变；6)对子代群体重复步骤3）-5）的操作，进行新一轮遗传进化过程，直到迭代收敛（适应值趋稳定）即找到了最优解或准最优解。

4遗传算法进行求解并优化应用

当我们对遗传算法的基本原理有了一定的实践和认识，利用其各种遗传操作算子就可建立和产生课程表排课系统的结构模型，并进行求解和优化描述应用如下：

4.1解的表示

表单元：一个班级的课程表为一个表单元。每周按7天计、每天按6个时间段计。如果周末和某些时间段不能排课，可以在初始约束时用一个布尔变量关闭。

时间段填充：单元中的时间段上用2元组（课程号，教室号）进行填充，当课程有重复次数时，固定课程号做重复填充。

原子码：班级码+课程码+星期码+时段码+教室码。

其中，班级码和课程码之间的关系是固定的。

表单元码：相同班级码的原子码集合。

个体码：假设有n个班，n个表单元码构成的序形成一个个体码。

可行解：满足协调条件的个体码。

4.2选择初始群体

1)根据给定的班级、该班级本学期所要上的课程集合、以及每门课的重复次数。随机产生星期码、时段码、教室码。与班级码和课程码构成一个原子码。

2)由原子码生成表单元码。

3)由表单元码生成个体码。

4)根据初始群体大小，生成由个体组成的初始群体。

4.3确定评价函数

评价函数在遗传过程中起着环境的作用，根据评价函数产生每个个体的适应值。这里，我将时间段效率、时间间距约束、教室利用率等因素结合起来定义评价函数。时间段效率和时间间距约束涉及到上课的效果，教室利用率涉及到资源的利用问题。因此，应该优先考虑时间段效率和时间间距约束，在保证这两者的前提下，再考虑教室利用率。在评价函数中，前两者所占的比重相对较高。在每个个体中，每个三元组(星期码，时段码，教室码)对应着时间段效率和教室利用率。对于每个班的重复课程，对应着一个时间间距约束问题。将这三个因素按比例进行累加，就可以得到每个个体的适应值。

4.4遗传策略

通常，我在遗传过程中采用三种算子：复制、杂交、变异，三者概率分别为Pr，Pc，Pm。

1）复制算子(reproduction):复制算子从群体中按照某一概率选择个体，某个体si被选择的概率Pi与其适应值成正比。通常，我用赌(roulettewheel)方法进行实现。赌方法的实现如下：设群体S：s1,s2,……,sn,每个个体的适应值分别为f(s1),f(s2),……,f(sn),令sum＝f(s1)+f(s2)+……+f(sn),某个体所si被选择的概率Pi＝f(si)/sum(i=1,2,……,n),在0与sum之间产生一个随机数A，令B＝0，依概率p1,p2,……,pn在1到n之间随机产生一个个体编号m，将f(sm)累加进B中，直到B>A,将此sm作为被选个体。

2）杂交算子(Crossover):杂交算子将被选中的两个个体的基因链按概率Pc进行杂交，即在某一确定段上，对等交换代码，生成两个新的个体，杂交位置是随机的。

3）变异算子(Mutation):变异算子将新个体的基因链的各位按概率Pm进行变异，对二进制基因链来说就是对某些随机选取的位置取反。

这样，对每一代群体，我首先用协调条件进行一次筛选，剔除不满足协调条件的个体。然后才对个体进行演化计算产生下一代，从而加快了进化速度。

结合上述三种算子，采取了一种新的遗传策略。在得到群体中每个个体的适应值后，首先用赌方法将群体选择到池中，然后从池中每次取两个个体依概率进行杂交或变异产生临时新群体，此时，临时新群体数目与父代群体数目相同。接着，再将临时新群体中每个个体依概率选择或直接复制到下一代，或与上一代对应个体进行竞争(即若其适应值比上一代对应个体差，则将上一代个体保留下来，否则将其保留至下一代)。另外，将每一代中最优个体进行保存，每次产生新群体后，判断新群体中是否有比现有最优个体的适应值更好的，若有，则用其替换当前最优个体。通过父代和子代竞争，可以提高解的收敛速度。

4.5停机准则

我可以采用多种方法来结束算法的执行，这里，我采用两种方式相结合对停机加以控制：

1)设定最大遗传代数M，当遗传进行到第M代时，让其停机。

2)预先定义评价函数的一个指标数，当某一代最优个体的适应值达到或超过该指标数时，让其停机。

4.6输出结果

遗传算法结束后，可以得到适应值（即综合效率函数值）最好的个体。根据这个结果，我将对个体码进行如下分解：

1)分解个体码成为表单元码。

2)分解每一个表单元码成为：班级码、课程码、星期码、时段码、教室码。

由分解后的班级码、课程码、星期码、时段码、教室码分别生成如下表格：

1)班级课程表。

2)根据教师与课程的固定关系，生成教师工作表。

3)每个教室的时间占用表。

4)教学单位的课程总表。

5结束语

本文基于遗传算法建立和描述了排课的数学模型，实际上是对一个时间任务表的优化问题，研究了对问题的求解。利用遗传算法的全局寻优和收敛速度快的特点，结合随机选取法和回溯试探法的优点，设计了一种用于课表自动生成的好的算法，在排课的成功率和速度都得到了明显的提高。实验表明：本排课模型算法的构成结果能得到较满意的课程表安排方案。然而要使课表自动生成的误差精度和收敛速度进一步得到改进，还需要做出更深的研究。

参考文献：

[1]PeterBrucker.SchedulingAlgorithm.Berlinetc:Springer,1998.

[2]J．H．Holland，Adaptationinnaturalandartificialsystems[M]，Annarbor:UniversityofMichigenpress,1975.

[3]HamiltonMA.JavaandtheShifttoNet-centricComputing.IEEEComputer,29(8),1996.

[4]刘勇，康立山，陈毓屏.非数值并行算法（第二册）－遗传算法[M].北京：科学出版社，1998.

[5]余建桥，预测模型获取的遗传算法研究[J].计算机科学,1998,25(2):12-14.

[6]王小平，曹立明.遗传算法－理论、应用与软件实现[M].西安：西安交通大学出版社，2002.

遗传学条件概率范文

关键词：XMPP遗传算法分布式数据访问路径优化

中图分类号：TP301文献标识码：A文章编号：1007-9416（2015）09-0000-00

1简介

XMPP（ExtensibleMessagingandPresenceProtocol，可扩展消息与存在协议）是一种基于XML的即时消息协议[1]。它继承了XML灵活性和扩展性，已经应用到其它非IM领域[2]。有学者提议XMPP作为物联网领域的标准协议[3]。也有学者将其应用到分布式数据存储领域，将提供相同数据的服务器放在网络中的不同位置，以减少链路带宽的消耗、提供数据的安全性和多用户的QoS（QualityofService）[4]。

作者利用XMPP对物流领域的异构系统进行数据兼容性整合和分布式存储。在实践过程中，海量的数据与有限的服务器资源和链路带宽之间存在很大的矛盾。导致，在相同服务器资源和链路带宽下，不同的访问选择将导致服务器负载和链路带宽负载不平衡等问题。因此有必要对访问选择问题进行探讨。

现行的解决方案主要是通过提高服务器的硬件配置和增加链路带宽的方式进行解决。本文在现有的服务器资源和链路带宽的条件下，利用优化算法对问题进行分析、建模和求解。通过构建XMPP选择优化服务器，首先通过正交实验得出各实验参数最优值，然后通过实验验证得出在双目标双约束条件下的不同解[5，6]。

2问题说明

基于分布式的XMPP服务器访问QoS选择优化的目标是优化网络中数据流的传输路径，实现服务器资源和链路带宽负载平衡。因为各数据流占用的服务器资源和服务器端链路带宽不同，所以研究的重点就是将网络中数据流分别重定向到不同服务器的路径优化问题[7]。另外，为了网络数据流的优化，需建立XMPP选择优化服务器。它负责定时收集相关信息，进行分析处理后得出在不同约束条件下的最优路径。如图1所示，是实验模拟的基于XMPP的分布式服务器的访问网络的拓扑图。图中包含30条链路（E0～E29），30个用户节点（C0～C29），4个服务器节点（S0～S3）。

图1基于XMPP的数据分布式存储网络拓扑图

将访问的网络看成一个有向连通图G（V，E），V是节点集；E是链路集。节点集V包括：

（1）服务器节点S；（2）用户访问节点C。

假设G（V，E）中C，S和E的数量分别为m，n，l，且用户与各个服务器之间链路都采用TCP/IP协议获得访问路径[8]，那么每个用户有n条可选链路，整个网络就存在nm种可选状态。求解的问题就从这些可选状态中选取一种，使得网络在满足约束条件的情况下整体性能达到最优，下面给出了它的问题模型。

优化的目标是服务器负载均衡，链路集E链路带宽负载均衡，即服务器端网络负载均衡。XMPP选择优化服务器收集的信息存储到以下矩阵中：

（1）：用户占用服务器资源矩阵，表示i用户占用的服务器资源；（2）：用户占用链路带宽矩阵，表示i用户占用的服务器端链路带宽；（3）：服务器资源矩阵，表示j服务器所能提供的最大服务器资源；（4）：链路带宽矩阵，表示j服务器所能提供的最大链路带宽；（5）：链路分布矩阵，表示i用户到j服务器是否链接，如果链接，否则；（6）：决策变量，表示i用户选择的服务器。

将路径优化问题用矩阵描述为如下双目标优化问题：

（1）

（2）

其中，

公式（2）表示服务器利用率的最大值，表示链路链路带宽利用率的最大值。

要实现访问的QoS，所有用户请求所消耗的链路带宽之和必须小于各服务器端链路带宽，所消耗的服务器资源之和必须小于各个服务器的资源，那么约束条件表示为：

（3）

3问题求解

从上述数学模型可知，问题是一个多目标多约束优化问题，使用遗传算法求解该问题的过程如下：

（1）编码。染色体编码采用的形式，基因表示i用户所选择的服务器，那么一条染色体表示一种网络路径选择状态。基因的区间为服务器的数量，取值为0到n-1范围内的任意整数。

（2）适应度函数。利用权重系数法，可得到适应度的求解公式：

（4）

其中，分别表示服务器利用率权重和链路带宽利用率权重，每一组权重对应一个解，可以调节权重值得到Pareto最优解集[7]。实际应用中根据具体情况来选定一组权重值，从而获得对应的解作为路径优化的目标。

（3）群体设定。要使得群体能够覆盖基因的所有可能取值，种群的规模与服务器的数量有关：

（5）

其中，为种群规模系数，>1。

（4）选择。可以采用最优复制与比例选择相结合的方法进行选择操作，在每一代的进化过程中，保留个当前最优个体不参与交叉、变异等遗传操作，直接把它们复制到下一代群体中。

其余个体在下一代群体中生存的数目N标书如下：

（6）

其中，是最优个体保留数量；是个体的适应度值。

（5）交叉。可以采用随机取交叉点的方式，选取CP个交叉点进行交叉操作。每个随机交叉点的取值范围为0到m-1。

（6）变异。可以采用随机取数的方式获取变异点，取值的范围为0到m-1；在变异点处使用随机取值的方式完成基因的变异。变异的基因值取值范围为0到n-1。

（7）终止条件。在一定代数内如果没有更优解出现时则自动终止，公式（7）是解的终止条件函数。

（7）

其中，是第k代到第k+λ代的相对误差；为第k代各染色体的最大适应度；是设定的评判标准。因为选择过程中保留前h个最优个体，且相邻两代的最优个体经常相同，因此E取λ代间隔的相对误差。

4实验及结果分析

研究将从理论角度的就行实验分析。随机模拟产生如下实验环境：服务器资源值为10～100间的模拟随机取整数值；链路带宽值10～100间的模拟随机取整数值；各用户节点所消耗的服务器资源值为0～5间的模拟随机取整数值；各用户节点所消耗的链路带宽值为0～5间的模拟随机取整数值。

从图1的环境可知m=30，n=4，l=30。用户所需链路带宽和服务器资源如表1所示，最优个体保留数量h=1，交叉点数量CP=1。

表1用户所需链路带宽和服务器资源

C0C1C2C3C4C5C6C7C8C9C10C11C12C13C14

323341112121121

423321221242213

C15C16C17C18C19C20C21C22C23C24C25C26C27C28C29

212113121121212

321121432222132

4.1遗传算法参数取值实验

在服务器的资源矩阵SR=（25，20，65，100），服务器链路带宽矩阵SN=（10，20，30，40），服务器的权限矩阵SRWeight=（0.5，0.5，0.5，0.5），服务链路带宽权限矩阵SNWeight=（0.5，0.5，0.5，0.5）条件下，通过对种群规模系数、交叉概率、变异概率和遗传代数四个因素进行正交实验。

表2为交叉概率=0.5、变异概率=0.05和遗传代数=20时，改变种群规模系数得出的最优和最差适应度值及其基因编码。

表2最优种群规模实验

Best

fitnessBestCodeWorst

fitnessWorstCode

110.50.05200.62513133111131332212333333233313320.6213313311113133221233333323330332

220.50.05200.68452313312333233223313333323233220.6845231331233323322331333332323322

330.50.05200.67502233211232232332233333323331310.6699223221123223233223333332333131

440.50.05200.72833333332222233233323232323323330.6980233333022223223232323232322333

5100.50.05200.71433123233232333333332333322233320.6443311123223222233333232333221332

6200.50.05200.73823333322332323323322233323333330.6327133023233331232232221232333333

7300.50.05200.74913333333323233333323333333333330.6875332233332313323132323333323333

8400.50.05200.75013333323333333333323233323333330.6479333332133332332132320232023322

9600.50.05200.73373333233332333322332333223323330.6072333030322333330232230321313333

10800.50.05200.74643333323332333332333333323323330.6119303303333233233133321232232033

表3为种群规模系数=5、变异概率=0.05和遗传代数=20时，改变交叉概率得出的最优和最差适应度值及其基因编码。

表3最优交叉概率实验

Best

fitnessBestCodeWorst

fitnessWorstCode

150.10.05200.55862223331033220113332023330003030.2810311002000003200003333100132010

250.20.05200.61793333322031221032030233322203230.3365122011300303203111032030011010

350.30.05200.59003133332321203313231330233212010.3398200312003313000011130011211231

450.40.05200.66752333333032312323233323223212310.3336011203013213102033201031020011

550.50.05200.67222333332233333331233022302232230.3452101123102122002122011002301111

650.60.05200.62083232322222233002022132321232220.3329011103322300002332000002133013

750.70.05200.64253222221031312232212323323223230.3605110110331131131110203311110022

850.80.05200.65422302332333332313330332223322320.3630310002103100223111321122311311

950.90.05200.71592332323323323322232223323332230.4051111131033002310012022123012221

1051.00.05200.64302332333333333312330133302122310.3601101000331331200122211122212111

表4为种群规模系数=5、交叉概率=0.9和遗传代数=20时，改变变异概率得出的最优和最差适应度值及其基因编码。

Best

fitnessBestCodeWorst

fitnessWorstCode

150.90.002200.67773133333323323232222313132222330.4443310231031213212203202210303013

250.90.004200.66403332322123232232131032222323230.4453202222313232010013122331202210

350.90.016200.66602232322332332300221333333332320.3688011213230032101103000132211302

450.90.064200.67822333323113323333221312332313330.3678121211113030321112210000312012

550.90.256200.62572333122213233132300032322333220.3058010212003011331111120220001033

650.90.512200.61252122312230223313223023332211320.3098013001310330301110230011222210

750.91.000200.61472321321323202332121323033223330.2762022303211111200111130200300101

表4最优变异概率

表5为种群规模系数=5、交叉概率=0.9和变异概率=0.002时，改变遗传代数得出的最优和最差适应度值及其基因编码。

表5最优遗传代数实验

Best

fitnessBestCodeWorst

fitnessWorstCode

150.90.002200.69013133322322233322133333332133330.4362130300033203231133011033023331

250.90.002400.73003233333333332332331232333323230.5428303320322233331310113310211321

350.90.002800.72183323322232322333332333323231330.6047221222223232203033232332223121

450.90.0021600.75013332323333323333333333333333330.6422023022333032233323333333333333

550.90.0023200.75423333333322333333333333333333330.6562332332112230333232303233333303

650.90.0026400.75943333333333333333333333333333330.6515333013333332333323333033033333

图2遗传代数=160时正交实验适应度曲线

从正交实验的实验结果可以得出：在种群规模系数=5、交叉概率=0.9、变异概率=0.002和遗传代数=640时，易得出最优解。

4.2优化路径实验

以正交实验结果为基础，在服务器的资源矩阵SR=（25，20，65，100），服务器链路带宽矩阵SN=（10，20，30，40）条件下，改变各服务器，的值，得出表6的优化结果。

编号1的实验，目的优先使用链路带宽，最后实验结果是多数用户选择4号和3号服务器，与预期结果吻合。

编号2的实验，目的优先使用服务器资源，最后实验结果是多数用户选择1号和2号服务器，与预期结果吻合。

编号3的实验，目的是链路带宽和服务器资源均衡使用，最后的结果是多数用户选择2号和3号服务器，也与预期结果吻合。

因此，通过所构建算法模型和正交实验得出的遗传算法参数值，符合实际需要。研究成果很好的解决了在双目标双约束条件下的XMPP服务器选择问题。

表6在不同条件下的优化结果

fitnessCode

rw1rw2rw3rw4nw1nw2nw3nw4

1000011110.6792333333333233333333333333333333

2111100000.5792000001100001000001000000000100

30.50.50.50.50.50.50.50.50.4125112121112111120111113112122112

5结语

为了提高XMPP网络分布式数据访问效率必须进行路径优化。本文从双目标优化角度运用遗传算法处理这个问题，给出了满足QoS双约束前提下的路径优化的算法模型与实现过程。实验结果表明本算法在不同权重系数下可以收敛于各个指标的最优值，实现路径的多目标组合优化。

参考文献

[1]P.Saint-Andre，Ed.ExtensibleMessagingandPresenceProtocol（XMPP）：Core.http：///rfcs/rfc3920.txt.

[2]黄剑.基于XMPP的端到端连接建立机制的研究与实现[D].国防科学技术大学硕士学位论文.2009.

[3]张卫，张峻峰，罗长寿.XMPP应用于物联网通讯协议的研究[J].中国农学通报，2012，28（09）：289-292.

[4]张丽，曲攀.自组织覆盖网络QoS组播动态路径优化研究[J].计算机工程与应用，2013，3（24）：83-87.

[5]LiuJunli，ChenShuangxi，MaoJie.Geneticalgorithmstudyontheuniversitycoursetimetablingproblem.2012IEEEInternationalConferenceonCyberTechnologyin.Automation，Control，andIntelligentSystems（CYBER）.Bangkok，Thailand.2012，179-182.

[6]ChangWookAhn，R.S.Ramakrishna.AGeneticAlgorithmforShortestPathRoutingProblemandtheSizingofPopulations[J].IEEETRANSACTIONSONEVOLUTIONARYCOMPUTATIONJun，2002：566-579.

[7]惠雯，尹浩，林闯，杨扬.内容分发网络请求路径研究[J].计算机科学，2012，2（12）：1-7.

[8]陶英华，韩英伟，刘剑.TCP/IP协议解析（上）[J].中国有线电视，2005，16（24）：1574-1577.

[9]李领治，丁秋林.基于遗传算法的QoS选播流路由优化算法[J].计算机工程，2008，34（6）：42-47.

收稿日期：2015-07-27