以基因演算法求解最大化路段不相交路徑問題與光路徑和光波長指派問題

Abstract

Optimization problems concerning edge-disjoint paths in a given graph have attracted considerable attention for decades. Lots of applications can be found in the areas of call admission control, real-time communication, VLSI (Very-large-scale integration) layout and reconfiguration, packing, etc. The optimization problem that seems to lie in the heart of these problems is the maximum edge-disjoint paths problem (MEDP), which is NP-hard. In this dissertation, we developed a novel genetic algorithm (GA) for handling the problem. The proposed method is compared with the purely random search method, the simple greedy algorithm, the multi-start greedy algorithm, and the ant colony optimization method. The computational results indicate that the proposed GA method performs better in most of the instances in terms of solution quality and time. Moreover, a real-world application of the routing and wavelength assignment problem (RWA), which generalizes MEDP in some aspects, has been performed; and the computational results further confirm the effectiveness of our work. Compared with the bin-packing based algorithms and particle swarm optimization, the proposed method can achieve the best solution on all testing instances. Although it is more time-consuming than the bin-packing based methods, the differences of computational time become small on large instances.

Optimization problems concerning edge-disjoint paths in a given graph have attracted considerable attention for decades. Lots of applications can be found in the areas of call admission control, real-time communication, VLSI (Very-large-scale integration) layout and reconfiguration, packing, etc. The optimization problem that seems to lie in the heart of these problems is the maximum edge-disjoint paths problem (MEDP), which is NP-hard. In this dissertation, we developed a novel genetic algorithm (GA) for handling the problem. The proposed method is compared with the purely random search method, the simple greedy algorithm, the multi-start greedy algorithm, and the ant colony optimization method. The computational results indicate that the proposed GA method performs better in most of the instances in terms of solution quality and time. Moreover, a real-world application of the routing and wavelength assignment problem (RWA), which generalizes MEDP in some aspects, has been performed; and the computational results further confirm the effectiveness of our work. Compared with the bin-packing based algorithms and particle swarm optimization, the proposed method can achieve the best solution on all testing instances. Although it is more time-consuming than the bin-packing based methods, the differences of computational time become small on large instances.