科研之友
微信
新浪微博
Facebook
分享链接
摘要
Network design is a broad class of essential engineering and science problems. The target of network design is to construct a graph that satisfies some restrictions. Many network design problems (NDPs) are known as NP-hard and become more challenging as networks grow fast in size. In this paper, we propose a novel genetic algorithm based on partitioning, termed PGA, which divides large-scale NDPs into low dimensional subproblems and achieves global optimal solution by coordination of sub-problems. Experiments with PGA applied to the degreeconstrained minimum spanning tree problem have shown the effectiveness of PGA for large-scale NDPs.
