多目标免疫优化组播路由路径选择方法

摘要

本发明公开一种多目标免疫优化组播路由路径选择方法，主要解决组播路由优化问题。其实现步骤为：(1)确定优化目标，生成网络模型，给定运行参数，生成初始种群；(2)消除个体路径环路；(3)计算个体目标值，生成当前非支配种群；(4)判断结束条件，满足则输出当前非支配种群；否则转(5)；(5)计算当前非支配种群个体拥挤度距离，生成活跃种群；(6)对活跃种群进行克隆和局部搜索操作；(7)对克隆后种群进行重组、变异和局部搜索操作；(8)将当前非支配种群与(6)、(7)所得种群合并，消除个体路径环路；(9)计算个体目标值，更新当前非支配种群，转(4)。本发明具有提供灵活质优的方案的优点，适用于组播路由路径选择。

主权项

1.一种多目标免疫优化组播路由路径选择方法，包括如下步骤：(1)确定优化多目标和约束条件，其中确定的优化多目标为：组播树T的链路代价、组播树T的时延和组播树T的带宽占用率；其中组播树T的链路代价为组播树中从源节点到每一个目的节点路径的代价之和；组播树T的时延为组播树中从源节点到每一个目的节点路径的时延之和；组播树T的带宽占用率为组播树中从源节点到每一个目的节点路径带宽占用率的最小值；确定约束条件为：组播树的最高时延上限5秒；生成网络模型，设定种群进化终止代数，给定运行参数，根据网络模型，先假设对于网络中的每一个节点t都有三个参量D[t]，pre[t]，sign[t]，该D[t]表示从源节点s到t的路径的耗费度量，该pre[t]表示路径中节点t的前一个节点序号值，该sign[t]表示节点t是否被访问过的标记位；再使用随机Dijkstra算法生成初始种群，生成种群中每一个个体的具体操作为：(1a)从优化多目标中随机选择一个优化目标，作为当前个体路径产生过程中所依据的耗费度量值；(1b)首先，设置源节点s的参量值，令D[s]的值为0，pre[s]的值为-1，sign[s]的值为1；其次，设置网络中所有与源节点s直接相连的节点t的参量值，令D[t]的值为从源节点s到该节点t的耗费度量值，pre[t]的值为源节点s的序号值，sign[t]的值为0；再次，设置网络中所有与源节点s不直接相连的节点n的参量值，令D[n]的值为∞，pre[n]的值为-1，sign[n]的值0；最后，设置当前节点k的参量值，将D[s]的值赋给D[k]，将pre[s]的值赋给pre[k]，将sign[s]的值赋给sign[k]；(1c)：对于从当前节点k到与当前节点k直接连接但标记位的值不为1的节点m，设置D[m]的值为min{D[m]，D[m]+w_km}，w_km是从当前节点k到标记位的值不为1的节点m的耗费度量值；(1d)从与标记位的值不为1的节点m有连接关系的节点集中随机选取一个节点i；(1e)令sign[i]的值为1，pre[i]的值为标记位的值不为1的节点m的序号值；(1f)如果所有节点的标记位的值都为1，则个体生成结束；否则，对于当前节点k的三个参量，将D[i]的值赋给D[k]，将pre[i]的值赋给pre[k]，将sign[i]的值赋给sign[k]，并执行(1c)；(2)对初始种群中的每个个体，消除从源节点到目的节点路径中的环路，具体操作为：(2a)令源节点s为当前选定节点，将路径中的其他节点序号分别减去第一个节点的序号，置当前路径为空路径，将当前选定节点添加到该当前路径；(2b)根据节点序号判断当前选定节点是不是目的节点，如果是，则消除从源节点到目的节点路径中环路的操作，输出当前路径；否则，执行步骤(2c)；(2c)从当前选定节点开始，依次寻找路径中的其他节点序号与当前选定节点的序号相减后为0的节点，如果存在序号为0节点，将序号为0节点之后的节点作为当前选定节点；如果不存在序号为0的节点，将当前选定节点之后的节点作为新的当前选定节点；将当前选定节点添加到当前路径，并将当前选定节点之后的节点序号分别减去当前选定节点序号，返回步骤(2b)；(3)计算每个消除环路后的初始种群个体的目标函数值，去除不满足约束条件的个体，保留种群剩余个体中的非支配个体，作为当前非支配个体种群，并置当前进化代数为第一代；(4)判断当前进化代数是否满足(1)中设定的种群进化终止代数，如果满足，输出当前的非支配个体种群；否则，执行第(5)步；(5)计算当前非支配个体种群中个体的拥挤度距离，将拥挤度距离从大到小的顺序排列，根据设定的运行参数，优先选择拥挤度距离大的个体组成当前活跃种群，其中拥挤度距离为：${\zeta }_b\stackrel{\Delta }{=}\underset{j=1}{\overset{q}{\Sigma }}\frac{{\zeta }_b^j}{f_j^{\max }-f_j^{\min }}$是第j个目标函数的最大值，是第j个目标函数的最小值，q为优化多目标个数，为个体b的第j个目标函数的拥挤度距离，该的计算方式为：如果个体b第j个目标函数的数值f_j(b)等于或者等于则的数值为无穷大；否则，在当前非支配个体种群中，找出第j个目标函数的数值大于f_j(b)的个体b′和第j个目标函数的数值小于f_j(b)的个体b″，则的数值为f_j(b′)-f_j(b″)，这里f_j(b′)为个体b′的第j个目标函数的数值，f_j(b″)为个体b″的第j个目标函数的数值；(6)对当前活跃种群中的个体进行比例克隆操作，并对比例克隆种群中个体进行局部搜索操作，保留局部搜索所得种群，其中局部搜索的具体操作为：(6a)在源节点与第一个目的节点之前的节点之间，随机选择一个节点，作为子路径起点，再随机选择一个优化目标作为当前考虑的耗费指标，应用随机Dijkstra算法产生从子路径起点到第一个目的节点的最小耗费路径，作为当前个体的第一个局部搜索解；(6b)根据节点序号判断是否完成对当前个体从源节点到所有目的节点的局部搜索，如果是，完成对当前个体的局部搜索，否则执行步骤(6c)；(6c)在源节点与下一个目的节点之前的节点之间，随机选择一个节点，作为子路径的起点，随机选择一个优化目标作为当前考虑的耗费指标，应用随机Dijkstra算法产生从子路径起点到当前目的节点的最小耗费路径，更新原来的个体，作为当前个体对应于当前目的节点的局部搜索解，返回步骤(6b)；(7)对比例克隆后的种群个体进行重组操作和变异操作，并对变异操作后的种群进行局部搜索操作，得到变异局部搜索种群，其中重组的具体操作为：(7a)从进行重组的两个个体中，随机选择一个目的节点，置当前的重组寻找次数为1；(7b)如果两个个体中从源节点到该目的节点的路径不完全相同，但有且只有一个公共的节点，则选择这个公共的节点作为交叉点，当有两个或两个以上的公共节点时，选择第一个公共点作为交叉点，再对两个个体交叉点之后的序列进行交换，此次重组操作结束；否则，判断当前的重组寻找次数，如果重组寻找次数已经超过五次，则退出重组操作，否则执行步骤(7c)；(7c)从活跃种群中重新选择一个个体，递增当前的重组寻找次数，执行步骤(7b)；其中变异的具体操作为：(7d)在源节点与第一个目的节点之前的节点之间，随机选择一个节点，作为子路径的起点，再随机选择一个优化目标作为当前考虑的耗费指标，应用随机Dijkstra算法产生从子路径起点到第一个目的节点的最小耗费路径，更新原来的个体的对应路径；(7e)根据节点序号判断是否对从源节点到所有目的节点的路径都进行了变异操作，如果是，则将当前的更新路径后的个体作为变异操作后的个体；否则，执行步骤(7f)；(7f)在源节点与下一个目的节点之前的节点之间，随机选择一个节点，作为子路径的起点，随机选择一个优化目标作为当前考虑的耗费指标，应用随机Dijkstra算法产生从子路径起点到目的节点的最小耗费路径，更新原来的个体的对应路径，返回步骤(7e)；(8)将保留的局部搜索种群和得到的变异局部搜索种群以及当前非支配个体种群组成合并种群，并对合并种群中的每个个体，消除从源节点到目的节点路径中的环路；(9)计算消除环路后的合并种群中个体的目标函数值，去除不满足约束条件的个体，将种群剩余个体中的非支配个体作为当前非支配个体种群，递增当前进化代数，返回(4)，重新判断结束条件。