Using cultural algorithms to solve optimization problems with a social fabric approach.

摘要

Cultural Algorithms employ a basic set of knowledge sources, each related to knowledge observed in various animal species. These knowledge sources are then combined to direct the decisions of the individual agents in solving optimization problems using an influence function family based upon a Social Fabric metaphor. While many successful real-world applications of Cultural Algorithms have been produced, we are interested in studying the fundamental computational processes involved the use of Cultural Systems as problem solvers. In previous work the influence of the knowledge sources have been on individuals in the population only. Here we introduce the notion of a Social Fabric in which the expression of knowledge sources can be distributed through the population. We describe an implementation of this approach, the Cultural Algorithms Toolkit (CAT), as a simulation environment developed in the Repast agent-based simulation environment. Next we introduce the notion of "Social Fabric" which provides a framework in which the Knowledge Sources can access the social networks to which individuals can belong. A computational version of the Social Fabric idea is then implemented as an extension of the influence function in the CAT system. Next we apply the Social Fabric function to the solution of several benchmark problems. We show that different parameter combinations and configurations for the Social Fabric can affect the optimization process in terms of optimizing the mean and how deviated the generated values from the mean. We demonstrate also that the frequency with which the Knowledge Sources are able to access the network can affect the problem solving process, where using a suitable window-size will make enough time for the knowledge sources to affect the individuals and continue a normal exploration and exploitation process until the Fabric is weaved and the individuals are allowed to interact in a Social context.We show that use of the Social Fabric approach to knowledge integration produced the following emergent structures and behaviors generally in an optimization problem: (1) That population swarms emerged not as a result of interaction at the population level, but knowledge interaction or swarming at the knowledge level. In other words, the interaction of the knowledge sources can produce swarm-like behavior even when individuals are not interacting directly. (2) Certain knowledge sources were able to produce fine tuning changes to individuals whereas others were limited to coarse grain changes. (3) The several phases still emerged in the problem solving process due to the complementarily of the various knowledge sources. Since complex systems are often viewed in different hierarchal terms, different knowledge sources exploited detail at different levels. The Social Fabric Influence function was able focus the exploitation process while still allowing for exploration. Certain configuration of the Social Fabric did better at this than others. In general, too much or too little interaction between individuals slowed the process down. Here, the Square communication topology proved to be a good compromise.In future work, our interest will be in the emergence of Social Fabric configuration in response to the demands of the current problem landscape.