title: Social interaction as a heuristic for combinatorial optimization problems.
abstract: We investigate the performance of a variant of Axelrod's model for dissemination of culture--the Adaptive Culture Heuristic (ACH)--on solving an NP-Complete optimization problem, namely, the classification of binary input patterns of size F by a Boolean Binary Perceptron. In this heuristic, N agents, characterized by binary strings of length F which represent possible solutions to the optimization problem, are fixed at the sites of a square lattice and interact with their nearest neighbors only. The interactions are such that the agents' strings (or cultures) become more similar to the low-cost strings of their neighbors resulting in the dissemination of these strings across the lattice. Eventually the dynamics freezes into a homogeneous absorbing configuration in which all agents exhibit identical solutions to the optimization problem. We find through extensive simulations that the probability of finding the optimal solution is a function of the reduced variable F/N(¼) so that the number of agents must increase with the fourth power of the problem size, N∝F⁴, to guarantee a fixed probability of success. In this case, we find that the relaxation time to reach an absorbing configuration scales with F⁶ which can be interpreted as the overall computational cost of the ACH to find an optimal set of weights for a Boolean binary perceptron, given a fixed probability of success.
authors.affiliation: Instituto de Física de São Carlos, Universidade de São Paulo, Caixa Postal 369, 13560-970 São Carlos, SP, Brazil.
authors.forename: José F
authors.initials: JF
authors.lastname: Fontanari
mesh_terms: D000465:Algorithms; D003469:Culture; D007398:Interpersonal Relations; D008962:Models, Theoretical; D015203:Reproducibility of Results