《表1 各对比算法所得解：基因池操作遗传算法的应用层组播路由优化》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《基因池操作遗传算法的应用层组播路由优化》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

根据本文采取的约束松弛策略，应从得到的Pareto前沿上截取符合度约束的解。图8（a）、（b）、（c）、（d）分别给出了本文算法对4个组播会话进行求解所得到的Pareto前沿，截取解均取自前沿上度约束超出量为0的非劣解。将截取解的拓扑结构列于表1。可以看出，本文算法求得的组播树全部满足Cod=2的度约束。当然仅满足度约束是不够的，传输时延也是评价组播树性能的核心指标。为了得到对本文算法构造的组播树在时延性能方面的评价基准，将几种已在IP组播中取得成功应用的智能算法迁移至应用层并在前述4个组播会话上进行同样的仿真测试。这些算法包括鱼群算法（Artificial Fish School Algorithm，AFSA）[18，27]和粒子群算法（Particle Swarm Optimization，PSO)[29]。需要说明的是：为了区别于本文采用的约束转目标的松弛策略，在测试AFSA[18]和PSO[29]的过程中，非可行解的评价采用具有代表性的惩罚函数法，其中惩罚因子分别取p=5和p=10；而AFSA[27]基于分治策略解决了有时延约束的IP组播路由问题，仅将时延约束替换为本文关注的度约束，并仍沿用其原有分治策略。为了便于和文献[18]中的AFSA进行区别，本文将文献[27]中采用分治策略的AFSA记作DC-AFSA（Divide-and-Conquer AFSA）。以上算法所得结果也在表1中列出。可以看出，AFSA和PSO在相同的惩罚因子p下总能得到一致的结果。当惩罚因子p=5时，AFSA和PSO对4个组播会话均得到了不满足度约束Cod=2的解；当惩罚因子p=10时，AFSA和PSO仍对第2、第4个组播会话求得非可行解。以组播会话(1）为例分析其原因：AFSA和PSO在惩罚因子p=5时得到的非可行解较之本文算法得到的组播树，丢弃了链路7?11而保留了链路11?18。根据图7，链路7?11的传输时延为33，而链路11?18的传输时延为25，因而AFSA和PSO在优化过程中通过保留链路11?18并丢弃链路7?11可获得传输时延减少8的收益（33-25=8），尽管链路11?18导致了18号节点的出度超过了Cod=2的限制，但惩罚因子p=5并不足以抵消传输时延的收益（8-p>0）。显然，得到非可行解并不是AFSA和PSO寻优能力的问题，而是惩罚函数法本身引入的求解风险。当惩罚因子p=10时，AFSA与PSO则得到了与本文算法相同的结果。显然，增加惩罚因子p能够降低求得非可行解的风险，但这种风险并不能完全消除。例如，对于组播会话（2）、（4），即使惩罚因子p从5增加到10，基于惩罚函数法的AFSA和PSO仍无法求得可行解。实际上，对组播会话（2）惩罚因子应至少取到p>37（注：191-154），对组播会话（4）则应取到p>11（注：414-403）。从这个角度讲，尽管在惩罚因子p=10时AFSA和PSO对组播会话（3）进行了成功求解，但仍有收敛至非可行解的风险。实际上，在求解之前确定惩罚因子的取值下界是不可能的。即便一再增大惩罚因子p也无法保证算法对所有网络、所有组播会话均有效。另一方面，惩罚因子p也不宜过大[30]。过大的惩罚因子会使算法的搜索很快被推至可行域内，从而难以接近约束边界并导致搜索效率的显著降低。相比于基于惩罚函数法的AFSA和PSO，基于分治策略的DC-AFSA对4个组播会话均求得了满足度约束Cod=2的组播树，表现出了与本文算法同等的可靠性。不过在时延性能方面，DC-AFSA对组播会话（4）得到的组播树较之本文算法求得的结果具有更大的时延。不难看出，尽管分治策略的确有助于提高算法对可行解的命中率，但对种群实行分治同时也弱化了算法的优化性能。表1结果表明，本文算法不仅具有较好的求解可靠性，同时在构造组播树的时延性能方面也优于对比算法。