Knowledge and population swarms in cultural algorithms for dynamic environments
Robert G. Reynolds, Bin Peng · 2005
Various biologically inspired approaches like Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), and Cultural Algorithms have been employed to solve problems in optimization and design. Cultural Algorithms employ a basic set of knowledge sources, each related to knowledge observed in various social species. These knowledge sources are combined to direct the individual agents in solving problems. Here we develop a knowledge integration algorithm based upon an analogy to the Marginal Value Theorem (MVI) in foraging theory to guide the integration of the knowledge sources. A simulation environment was developed in Java to examine the computational behavior of Cultural Algorithms. In particular we were interested in what structures would emerge at the individual, population, and belief levels during the problem solving process. Two basic categories of environments were tested, a Cones World Environment that was inspired by the Sugar Scape and ACO approaches, and a coil design problem from engineering that was tested with PSO. We show that use of the Marginal Value approach to knowledge integration produced the following emergent structures and behaviors in both problem environments: (1) The emergence of certain problem solving phases in terms of the relative performance of different knowledge sources over time. We label these phases as coarse-grained, fine-grained, and backtracking phases. Each phase is characterized by the dominance of a suite or subset of the knowledge sources that are most successful in generating new solutions in that phase. It appears that one type of knowledge produces new solutions that are consequently exploited by another knowledge source. Transitions between phases occur when the solutions produced by one phase can be better exploited by knowledge sources associated with the next phase. (2) The emergence of swarms of individuals moving within the problem space as a result of the interaction of the cultural knowledge. We called these “Population Swarms”. (3) We then observed the “swarming of knowledge” at the metalevel. These were called “knowledge swarms”. Thus, the swarming of knowledge sources at the meta-level was produced by the interaction of knowledge sources via the marginal value theorem and this induces a swarming at the population level.