应用遗传算法解决可靠性约束下的网络优化问题

Genetic-Algorithm-Based Topological Optimization of Network with a Reliability Constraint

利用遗传算法考虑一类可靠性约束下的网络结构优化问题。其目的是在系统可靠性不低于给定标准 ( p0 )条件下 ,寻找一种优化的网络结构 ,使其连接边的费用最低。过去 ,这类问题多采用分枝定界法处理。为了提高处理问题的速度 ,便于将这类问题向大规模网络优化问题扩展 ,采用遗传算法。这一方法的最大优点是可将其推广到求解一般带有约束的网络优化问题。而且结果表明无论是解的精度还是运算速度遗传算法都优于分枝定界法及其它启发式算法。

This paper considers network topological optimization with a reliability constraint. The objective is to find the topological layout of links, at a minimal cost, under the constraint that the network reliability is not less than a given level of system reliability. Decomposition method based on branch and bound has been used for solving the problem. In order to speed-up the procedure, this paper presents a new method, Genetic-Algorithm (GA), to optimize a specified objective functions. This technique is very powerful because the same approach can be extended to solve different types of optimization problems with constraint. Results show that GA can produce better solutions than branch and bound in accuracy and computation time.