一种优化多目标的交互式路由算法

An Interactive Routing Algorithm for Multi-object Optimization

QoS路由的基本任务是寻找一条满足多个约束条件同时优化多个网络参数的路径。研究多约束条件下的多个线性目标优化的QoS路由问题。选取带宽作为约束条件,线性函数(时延和耗费)作为优化目标,建立了QoS路由选择的多目标线性整数规划模型。通过将多目标优化问题转化为线性单目标优化问题,证明了新问题的最优解是原问题的有效解,给出一种求解模型的交互式算法。该算法引入目标函数参考点概念,逐步调整目标函数参考点,压缩目标函数搜索空间来满足决策者和实时网络资源要求,并最终得到满意解。仿真实例表明了算法的可行性和可操作性。

The basic task of QoS routing is to find a route in the network which has sufficient resources to optimize some network parameters and satisfy multiple constraints. The problem to optimize multiple linear objective functions in QoS routing is studied. A multi-objective linear integer-programming model is put forward, which optimizes linear functions such as delay and cost constrained of bandwidth. The multi-objective programming is transformed to a linear single objective programming and the optimal solution to the new programming is proved to be an efficient solution to the original programming. A reference point of the objective value is introduced and an interactive algorithm is provided. The idea of the algorithm is to modify the reference point in each iteration step to reduce the solution space, which adapts to decision-maker抯 information and network resource currently, and to obtain a satisfactory solution. Finally the performance of the algorithm is demonstrated by simulation experiments.