Computer Science – Data Structures and Algorithms
Scientific paper
2010-08-22
Phys. Rev. E 82, 056118 (2010)
Computer Science
Data Structures and Algorithms
Scientific paper
10.1103/PhysRevE.82.056118
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^{1/4}$ so that the number of agents must increase with the fourth power of the problem size, $N \propto F^ 4$, to guarantee a fixed probability of success. In this case, we find that the relaxation time to reach an absorbing configuration scales with $F^ 6$ 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.
No associations
LandOfFree
Social interaction as a heuristic for combinatorial optimization problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Social interaction as a heuristic for combinatorial optimization problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Social interaction as a heuristic for combinatorial optimization problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-165987