北京邮电大学学报

  • EI核心期刊

北京邮电大学学报 ›› 2001, Vol. 24 ›› Issue (1): 22-27.

• • 上一篇    下一篇

七号信令网的A/B平面划分问题及其启发式解法

忻展红, 吴启程, 莫文冬   

  1. 北京邮电大学经济管理学院, 北京 100876
  • 收稿日期:2000-09-01 出版日期:2001-01-10
  • 作者简介:忻展红(1949—),男,浙江宁波市人,教授.

A/B Plane Partition Problem in CCS7 Network and Its Heuristic Solutions

XIN Zhan-hong, WU Qi-cheng, MO Wen-dong   

  1. Business School, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • Received:2000-09-01 Online:2001-01-10

摘要: 七号信令网拓扑优化中存在高级信令转接点(HSTP)的A/B平面划分问题,其可归纳为一类新的图的划分问题.该问题被证明难度是NP完备的,神经网络、遗传算法和模拟退火等启发式算法被应用于该问题的求解.为了算法的可比性,精心设计了试验方案,计算结果显示遗传算法和模拟退火可以很高的概率和效率搜索到该问题的最优解.

关键词: 信令网, A/B平面划分, NP完备, 启发式算法

Abstract: There is an issue of A/B plane partition of HSTPs in the topology optimization of CCS7 network. It can be formulated into a new kind of graph partition problem. The problem is proved to be NP-complete, so the neural network, the genetic algorithm and the simulated annealing are applied to solve it. In order to make the algorithms comparable, the testing schemes are carefully designed. The computing results for the three algorithms show that the genetic algorithm and the simulated annealing are quite robust for the problem, they can search out the optimum with a larger probability and a higher efficiency.

Key words: signaling networks, A/B plane partition, NP-completeness, heuristic algorithms

中图分类号: