Parallelization of probabilistic sequential search algorithms

We compare some strategies for the parallelization of probabilistic sequential search algorithms. We are concerned with those probabilistic sequential search algorithms which generate a sequence of candidate solutions where each solution is generated from the previous one by the application of a probabilistic local improvement operator. Two good examples of such algorithms are Lin's 2-opt strategy for the Traveling Salesman Problem and Simulated Annealing. We explore the concept of searching by a pool of candidate solutions.;In this work we compare some strategies of parallelization of Lin and Kernighan's 2-opt operator for the Traveling Salesman Problem. In particular, we study the tradeoffs between processors working independently and processors communicating at regular intervals. Communication in this case involves exchanging information about good tours. We show that a good strategy of parallelization is one that involves communication at fairly regular intervals. We explore some strategies for information exchange like redistributing the current best tour at regular intervals, redistributing k best tours at regular intervals and so on. We also explore the selection strategy, of Holland's Genetic Algorithms as a strategy for information exchange. We also explore the quick approximate evaluation of tour lengths to determine the fitness of each tour for information exchange.;This is a study of searching by a pool of candidate solutions on a parallel machine. This is an interesting technique in that good strategies are very robust and it is possible to introduce other operators like the structural exchange operator which is well suited for a parallel machine and can improve the performance.