The surprising little effectiveness of cooperative algorithms in parallel problem solving.
REIA, Sandro Martinelli; AQUINO, Larissa Fernandes de; FONTANARI, José Fernando.
REIA, Sandro Martinelli; AQUINO, Larissa Fernandes de; FONTANARI, José Fernando.
Abstract: Biological and cultural inspired optimization algorithms are nowadays part of the basic toolkit of a great many research domains. By mimicking processes in nature and animal societies, these generalpurpose search algorithms promise to deliver optimal or near-optimal solutions using hardly any information on the optimization problems they are set to tackle. Here we study the performances of a cultural-inspired algorithm { the imitative learning search { as well as of asexual and sexual variants of evolutionary algorithms in nding the global maxima of NK- tness landscapes. The main performance measure is the total number of agent updates required by the algorithms to nd those global maxima and the baseline performance, which establishes the e ectiveness of the cooperative algorithms, is set by the blind search in which the agents explore the problem space (binary strings) by ipping bits at random. We nd that even for smooth landscapes that exhibit a single maximum, the evolutionary algorithms do not perform much better than the blind search due to the stochastic e ects of the genetic roulette. The imitative learning is immune to this e ect thanks to the deterministic choice of the ttest string in the population, which is used as a model for imitation. The tradeo is that for rugged landscapes the imitative learning search is more prone to be trapped in local maxima than the evolutionary algorithms. In fact, in the case of rugged landscapes with a mild density of local maxima, the blind search either beats or matches the cooperative algorithms regardless of whether the task is to nd the global maximum or to nd the ttest state within a given runtime.
@article={003000693,author = {REIA, Sandro Martinelli; AQUINO, Larissa Fernandes de; FONTANARI, José Fernando.},title={The surprising little effectiveness of cooperative algorithms in parallel problem solving},journal={European Physical Journal B},note={v. 93, n. 7, p. 140-1-140-11},year={2020}}