有约束的随机最短路问题模型及算法  

Model and Algorithm of Random Shortest Path Problem With Constraints

作　　者：何方国[1,2] 齐欢[1] 范琼[1] 

机构地区：[1]华中科技大学系统工程研究所,武汉430074 [2]黄冈师范学院数学与信息科学学院,黄冈438000

出　　处：《武汉理工大学学报（交通科学与工程版）》2008年第6期1125-1128,共4页Journal of Wuhan University of Technology（Transportation Science & Engineering）

基　　金：国家自然科学基金项目资助(批准号:60574088)

摘　　要：针对不确定网络,研究具有随机参数的最短路径问题,采用随机数表示路径权值的不确定性,建立有约束的期望最短路模型.基于随机模拟方法,设计了一种融合退火技术的遗传算法,引入退火机制处理有约束的优化问题.在进化过程中,动态调节对不可行解的惩罚力度,使不可行解逐步被淘汰出去,最后收敛到问题的全局最优解.给出的数值实例验证了该算法的有效性.Aiming at the uncertain networks, the shortest path problem with stochastic parameters is studied and the expected value model with constraints is constructed. Based on the method of stochastic simulation, a genetic algorithm integrating annealing method is presented to deal with the constrained optimization problem. The proposed algorithm introduces annealing mechanism to adjust dynamically the degree of the punishment to infeasible solutions, so that the infeasible solutions are eliminated gradually in the process of evolution and converges to a global optimal solution finally. The result of simulation test shows the algorithm is useful for solving practical problems.

关 键 词：期望值模型 最短路径 遗传算法 不确定网络 

分 类 号：O157.9[理学—数学] TP183[理学—基础数学]