The surprising little effectiveness of cooperative algorithms in parallel problem solving

Sandro M. Reia, Larissa F. Aquino and José F. Fontanari ()
Additional contact information
Sandro M. Reia: Instituto de Física de São Carlos, Universidade de São Paulo, Caixa Postal 369
Larissa F. Aquino: Instituto de Física de São Carlos, Universidade de São Paulo, Caixa Postal 369
José F. Fontanari: Instituto de Física de São Carlos, Universidade de São Paulo, Caixa Postal 369

The European Physical Journal B: Condensed Matter and Complex Systems, 2020, vol. 93, issue 7, 1-11

Abstract: 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 general-purpose 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 finding the global maxima of NK-fitness landscapes. The main performance measure is the total number of agent updates required by the algorithms to find those global maxima and the baseline performance, which establishes the effectiveness of the cooperative algorithms, is set by the blind search in which the agents explore the problem space (binary strings) by flipping bits at random. We find 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 effects of the genetic roulette. The imitative learning is immune to this effect thanks to the deterministic choice of the fittest string in the population, which is used as a model for imitation. The tradeoff 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 find the global maximum or to find the fittest state within a given runtime. Graphical abstract

Keywords: Statistical; and; Nonlinear; Physics (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1140/epjb/e2020-10199-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurphb:v:93:y:2020:i:7:d:10.1140_epjb_e2020-10199-9

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/10051

DOI: 10.1140/epjb/e2020-10199-9

Access Statistics for this article

The European Physical Journal B: Condensed Matter and Complex Systems is currently edited by P. Hänggi and Angel Rubio

More articles in The European Physical Journal B: Condensed Matter and Complex Systems from Springer, EDP Sciences
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().