服务质量路由问题的一个新进化算法

针对服务质量路由问题,设计了一种新颖的进化算法QoS_EA.该算法具有以下特点:(1)通过采用一种前向自然教编码方法,使路径不包含圈,节省了进化算法在求解该问题时的圈检查过程;(2)设计了一种散接交叉算子,以防止出现不可行的路径,确保交又操作的有效性和种群的多样性;(3)与交叉算子相对应设计了一种基于局部链路选择性修改的选择性变异算子,以确保路径由任意初始状态进化到满足约束的路径.理论分析证明该算法具有明显的优越性,并以概率1收敛于所求路径.计算机仿真结果表明该算法性能优于其他同类算法.

Novel evolutionary algorithm for QoS routing

For the QoS routing problem,a novel evolutionary algorithm named QoS_EA is proposed.Firstly,a novel coding technology named PNNC is designed to omit the circle checking process,and so no circle exists on the path based on PNNC.Secondly,a novel crossover operator called DCC operator is proposed for the validity of the crossed paths and the diversity of the population,which can avoid reproducing the infeasible path.Thirdly,a novel mutation operator named selective mutation operator is proposed,by which the initial path can change to the satisfied one gradually.Finally,the theoretical analysis proves that the algorithm outperforms the other algorithms in performance for the problem,and converges to the satisfactory solution with probability 1.Extensive simulations show that the novel evolutionary algorithm is a promising algorithm for the problem with high performance.