A fast discrete small-world optimization algorithm

The application of complex networks in optimization field has received increasing attention recently. This paper proposes a discrete small-world optimization algorithm (DSWOA) based on the small-world network theory and Six Degrees of Separation principle in sociology. The DSWOA model is composed of a lot of short-range contacts and few long-range contacts. In this algorithm, the short-range contactsachieve the fast searching and the long-range contacts can accelerate the convergence rate. Next, extensive computational experiments are conducted to compare the DSWOA with other algorithms for the permutation flowshop scheduling problems (PFSP) by using the Taillard instances(1). In the makespan tests, the results show that DSWOA has a stronger ability of quick searching, especially in the small-size problems. From the analysis results, the DSWOA has higher search efficiency than other algorithms.