Towards solving practical problems of large solution space using a novel pattern searching hybrid evolutionary algorithm - An elastic optical network optimization case study

The fast social and economic development observed in the recent years brings up new challenging optimization problems. These problems are often very hard not only because of their computational complexity, but also due to their enormous solution space size. Therefore, this paper proposes an effective optimization method, based on the novel Multi Population Pattern Searching (MuPPetS) Algorithm, to solve optimization problems characterized with very large solution space. As a case study problem, we focus on the problem of routing and spectrum allocation with joint anycast and unicast traffic demands that arises in the field of optical networks optimization. The proposed method is adjusted to the problem with proper solution encoding, hybridization using a local search algorithm, and dedicated mechanisms necessary to improve method convergence. The above adjustments are required to make the method effective against test cases with solution space size of up to 103700 points (sets of values of the choice variables). The paper compares the performance of the proposed method with other reference methods known from the literature. Another key contribution of this paper is presentation of the complicated dependency between fitness function evaluation number (FFE) and real computation load, which are used to evaluate effectiveness of the proposed technique. The analysis is supported with proper empirical tests and their analysis.