Global optimization properties of parallel cooperative search algorithms: A simulation study

Cooperative search is a parallelization strategy where parallelism is obtai ned by concurrently executing several search programs for the same optimiza tion problem instance, The programs cooperate by exchanging information on previously explored regions of the solution space. When the sharing of info rmation overlaps among several programs, changes in the search behavior of one program can propagate over time to several other programs; this is a pr ocess called diffusion in physical systems, The optimization properties of diffusion dynamics in cooperative algorithms have not been formally establi shed. However, it is generally believed that when the selection of shared i nformation is biased by the cost (objective) function, diffusion dynamics h elp to improve the search of cooperating programs. In this study, we simula te this aspect of cooperative algorithms using cellular automata (CAs) (the se are artificial dynamical systems often used to simulate the dynamics of complex systems). Our results show that the sharing of information based on the cost function does not affect the diffusion dynamics and therefore doe s not seem to help the optimization strategy of cooperating programs. Howev er, this study increases our understanding of the role played by diffusion processes in cooperative algorithms. We suggest new approaches that can hel p to subordinate diffusion dynamics to the optimization goals of the search programs. (C) 2000 Elsevier Science B.V. All rights reserved.