Distributed collective adaptation applied to a hard combinatorial optimization problem
Thomas D. Haynes · 1999
We utilize collective memory to integrate weak and strong search heuristics to find cliques in FC, a family of graphs. We construct FC such that pruning of partial solutions will be ineffective. Each weak heuristic maintains a local cache of the collective memory. We examine the impact on the distributed search from the various characteristics of the distribution of the collective memory, the search algorithms, and our family of graphs. We find the distributed search performs better than the individuals, even though the space of partial solutions is combinatorially explosive. Introduction To solve hard combinatorial optimization problems we can use parallel and distributed versions of serial search heuristics, which can either reduce the time taken to find the optimal solution or allow for the scaling up of problem complexity. We can add a collective memory (either centralized or distributed) in the form of a blackboard system (Fennell & Lesser 1977) and restrict all communication bet...