Cooperative guided local search

Over the past few decades, meta-heuristic algorithms (MHs) have proven to be powerful tools for dealing with difficult combinational optimization problems (COPs). These techniques can obtain high quality solutions within reasonable computational time for many hard ,.' A' problems. Among these methods, guided local search (GLS) is p'femising one. The proximate optimality principle (POP), an underlying assumption in most meta-heuristics, assumes that good solutions have similar structures. Structures which are common to good solutions are more likely to be part of the best solution. In this thesis we discuss how the performance of the GLS can be further enhanced through designing a cooperative mechanism based on the proximate optimality principle (POP). The approach that we took was to search for solutions using multiple agents, each of which running a copy of GLS. These agents benefit from each other through the exchange of information based on POP. We suggest based on POP that common features that appear in many locally optimal solutions of GLS agents are more likely to be parts of the globally optimal solution. Thus, this property should be taken into consideration during the search. We call this framework Population-based GLS (P-GLS). P-GLS shows its efficiency and effectiveness to converge quickly to promising regions of the search space in an intelligent manner. Four P-GLS versions are proposed which enhance the performance of P-GLS. These algorithms are extensively studied and tested on Traveling salesman problem (TSP), Multidimensional Knapsack Problem (MKP) and Field Workforce Scheduling Problem (FWSP). Computational results confirm the effectiveness of P-GLS compared to original GLS and other well known MHs.