Research And Application On Stochastic Local Search Algorithms

Stochastic Local Search (SLS) algorithm is a meta-heuristic for solving computa-tionally difficult problems in many areas of computer science and operations research. In recent years, SLS algorithms have been paid increasing attention due to their high ef-ficiency and easiness of implementation. In this research, we conduct a systematic and in-depth inspection of the key components of SLS algorithms, and then present ideas on how to design SLS algorithms combining specific problem features. More specifically, we select the set covering problem as our main studying objective. Our first contribu-tion is a Row Weighting Local Search (RWLS) algorithm for the set covering problem that has the following features.·a perturbative search framework that uses a pair of efficient operator to iterative reduce the size of the candidate solution;·a varity of tabu strategies to avoid possible osscilation of the search, including a timestamp method, a simple tabu list and a true or false checking mechanism;·a row weighting scheme to adaptive adjust the weights of uncovered rows during the search.Experimental studies have been carried out on80instances from OR-Library to test the effectiveness of RWLS. The systematic comparsion with state-of-the-art algorithms found in the literature shows that RWLS is very good at finding high quality solution results. It has improved14best known solutions in the literature, and performs robustly on instances with different characteristics, outperforming CPLEX on the last4very large-scale railway crew scheduling instances where CPLEX fails to produce solutions. The second contribution of our work is that we further abstract the idea of RWLS to an universal algorithmic framework that Balances Intensification and Diversification Perturbative Local Search (BIDPLS) for combinatorial optimization. The effectiveness of our framework is justified by applying it to the Multidimensional Multiple-choice Knapsack Problem.