Abstract: This paper presents a hybrid approach of genetic algorithm and heuristic algorithm for the backbone network design of communication networks. The backbone network design problem is defined as finding the network topology minimizing the the design cost of a network under R-edge-connectivity and hops-constraint considerations. The crossover and mutateon operators will produce infeasible soluteion, and infeasible soluteion becomes feasible by adding links. The offspring has higher cost than parents when adding links, and there will have redundant links. In the hybrid approach, heuristic strategy is added in genetic algorithm, it can delete redundant links to reduce the cost of the offspring that accelerates the course of algorithm. Simulation results show the effectiveness of the method.

Key words: Network design; Genetic algorithm; Heuristic algorithm; Hops; Edge-connectivity

摘要： 提出了一种由启发式算法和遗传算法混合使用的混合遗传算法用于通信网络中的骨干网拓扑设计。文中骨干网拓扑设计问题是在满足R 边连通和跳数约束的情况下使得网络费用最小。在遗传算法中，交叉和变异操作会产生不可行解，可通过增加链路来使不可行解变为可行解。增加链路后，其费用一般要比父代个体大，并且有多余的链路。该文的混合遗传算法是在遗传算法中加入启发式策略，来消除多余的链路，降低子代的费用，加快算法的收敛速度。仿真结果验证了算法的有效性。

关键词: 网络设计；遗传算法；启发式算法；跳数；边连通