A Memetic Algorithm for the Generalized Minimum Vertex-Biconnected Network Problem

摘要：

The generalized minimum vertex-biconnected network problem plays an important role in the design of survivable backbone networks that should be fault tolerant to single component outage. When given a graph where the nodes are partitioned into clusters, the goal is to .nd a subgraph of minimum costs that connects exactly one node from each cluster in a vertex-biconnected way. We present a memetic algorithm that uses fast local improvement methods to produce high quality solutions and an intelligent crossover operator which controls the balance between diversity and intensity in the population. Tests on Euclidean TSPlib instances with up to 442 nodes show that this approach is highly efficient.

关键词： Network Design Biconnectivity Memetic Algorithm

作者: Bin Hu Güunther R. Raidl

作者单位: Vienna University of Technology Favoritenstraβe 9-11/1861 1040 Vienna, Austria

会议类型: 国际会议

会议名称: 2009 Ninth International Conference on Hybrid Intelligent Systems(第九届混合智能系统国际会议 HIS 2009)

会议地点: 沈阳

会议语种:英文

页码: 1-6

在线出版日期: 2009-08-12（万方平台首次上网日期，不代表论文的发表时间）