结合SCE法的粒子群优化QoS路由算法(1)(2)
2015-04-10 01:12
导读：中选定一系列点（或者称为个体），这里，n是问题空间的维数。这些个体分别构成p个复形，每个复形由m个点构成。P和m是用户定义的参数，他们决定了群
中选定一系列点（或者称为个体），这里，n是问题空间的维数。这些个体分别构成p个复形，每个复形由m个点构成。P和m是用户定义的参数，他们决定了群体的大小s，即s=mp。每个复形独立地采用下山单纯形法（Nelder and Mead，1965）进行迭代进化。为了实现信息的共享，这些复形会定期进行洗牌（shuffled）处理，然后形成新的复形。如此，进化和洗牌重复进行直到满足预先指定的收敛准则。SCE算法的主要特征是通过竞争进化和定期洗牌来确保每个复形获得的信息能在整个问题空间获得共享。2.3基本PSO的停滞现象与改进 研究发现[14]，基本PSO粒子的位置是在本粒子前一最优位置和全局最优位置之间以减幅正弦波方式振荡的，如果在这一过程中，粒子经过的位置比前一最优位置要好，那么粒子将继续移动，通常收敛到目前找到的全局最优位置，所有的粒子跟随这一相同行为，很快聚集到一个本地最优解。然而，如果全局最优解不是刚好存在于初始粒子与这个本地最优解之间的位置的话，那么大部分粒子均被相同的本地最优解所限制，算法将出现暂时的停滞现象，需要经过很长的一段时间才能突破这个本地最优解的限制。那么，大多数粒子将浪费大量的计算时间在寻找和移动到局部最优的方向上。为了克服这种现象，我们采用结合了SCE 的PSO算法。 我们在每个复形中不是采用下山法，而是采用PSO算法。从而利用洗牌的处理，保证每个复形的多样性，利于算法跳出停滞阶段。 为了能使我们提出的结合SCE的PSO算法应用到求解QoS路由的离散性问题上，我们做如下改进： 首先我们定义如下几个概念：插入算子，删除算子，算子序列和基本算子序列。 ■插入算子对于一条QoS单播路由，用其经过的节点序列表示为 R=(Ni) i=1,…,n; 因此定义的插入算子INS(i1,k)如下： 定义1: 如果用插入算子INS(i1，k)作用于路由R，那么其结果为：在网络中搜寻一条从路由的第i1-1个节点N(i1-1)到节点k的不包含源节点的最短费用路径，插入到路由的第i1个节点Ni1前，然后,再在网络中寻找一条从节点k到节点Ni1的不包含源节点的最短费用路径，插入到Ni1前，并删除节点Ni1。 如果网络中节点N(i1-1)到节点k不存在连通的路径，则扩大为节点N(i1-2)到节点k，以此类推，直到找到或到达路由源节点为止。同理，如果网络中节点k到节点Ni1, 不存在连通的路径，则扩大为节点k到节点N(i1 1)，以此类推，直到找到或到达路由终节点为止。
图1. 随机生成的15 节点网络拓扑结构例1：如图1中：单播路由R=(3，7，11，8),那么R’=R INS(3，4)的结果是，寻找一条从R的第3个节点11到节点4的最短费用路径(11,9,4)，然后再寻找节点4到节点8的的最短路径（4，8），插入并删除节点8，最后得到的路径为（3，7，11，9，4，8）。 ■删除算子 定义2: 如果用删除算子DEL(i1)作用于路由R，那么其结果为：在网络中搜寻一条从节点N(i1-1)到节点N(i1 1)的不包含节点Ni1的最短费用路径，然后用它替代路由中N(i1-1)，Ni1和N(i1 1)三个节点。如果节点N(i1-1)到节点N(i1 1)不存在连通的路径,扩大为N(i1-2,i1 1)，如果仍找不到再扩大为N(i1-1,i1 2)，以此类推直到找到一条可替代的路径为止。 例2：如图1中：单播路由R=(3，7，11，9，8),那么R’= R DEL (4)的结果是，寻找一条节点11到8的最短费用路径(11,8)，替代11，9，8，最后得到的路径为（3，7，11，8）。 ■算子序列 定义3：如果有多个算子作用于一条路由，那么由这些算子组成的序列称为算子序列。如算子序列OS={INS1, INS2, DEL1}。这里，对各算子的先后顺序是敏感的。 ■基本算子序列 定义4：不同的算子序列作用于同一条路由，有可能得到相同的结果，把有最少操作的算子序列称为基本算子序列。 根据上面的定义我们设定基本算子序列的构造的准则：假设有两条路由R1,R2。这里的目标是如何构造基本算子序列，使之作用于R2从而得到R1。定义SS=R1-R2,从而，R2=R1 OS。 构造的基本规则是：首先对齐节点数，如果节点数少，则选择插入算子，如果节点数多，则选择删除算子，如果相等且有不同的节点，则随机选择插入或删除算子。 如图1中： 路由B={3,1,4,8},路由A={3,7,11,9,8}，求OS=A-B。首先是对齐节点数，路由A中 的第2个节点7在路由B中不存在，因此可考虑插入算子INS(2,7)，有B1=B INS(2,7) ,此时路由在3和7之间寻找到最短费用路径（3,7），7和4之间不经过源节点的最短费用路径为(7,11,8,4)，替换后得到B1=(3,7,11,8,4,8)。删除相同节点间的路径得B1=(3,7,11,,8)。此时，B1的节点数仍小于A，路由A中 的第4个节点9在路由A中仍不存在因此考虑INS(4,9)，根据插入算子的定义，最后得到B2=B1 INC(4,9)=(3,7,11,9,8)=A。因此得到基本算子：OS=A-B={INS(2,7),INS(4,9)}。 ■更新位置和速度 由于不再采用实数编码方式，因此公式(1)不再满足要求。根据上面的讨论，作如下修改：
