Cultural Algorithms. Robert G. Reynolds
Читать онлайн книгу.
Space” and “Population Space – Networked.”"/>
Figure 1.1 Cultural Algorithm framework.
The results of agent interaction within the performance environment in which they are embedded can be accepted into the Belief Space. The Belief Space is a repository of the knowledge acquired by the system so far. It is viewed as a network of different knowledge sources. The accepted knowledge is then integrated into the network through the use of learning procedures that make focused adjustments to the cultural compendium of knowledge. The Information “cloud” can be viewed as the current manifestation of the Belief Space using current technology.
These knowledge sources in the Belief Space can be “active” and or “passive.” Active knowledge sources directly select individuals based on their location and history in the social fabric (network). Passive knowledge sources are selected by individual agents in the network. A knowledge source can be both active and passive. The influence function in a Cultural Algorithm has two stages. In the first stage, each individual is assigned a direct influence, either actively or passively. Next, comes the knowledge distribution stage. Each individual's direct knowledge source is compared with a subset of its neighbors in the network in the knowledge distribution stage. If the knowledge sources are the same, then nothing more needs to be done for an individual. On the other hand, if there is a disagreement, then there is a conflict that needs to be resolved. This conflict is mitigated by a knowledge distribution mechanism. Currently, the mechanisms used are taken from traditional approaches to conflict resolution including drawing straws, majority win, weighted majority, win, various auction mechanisms, and various game frameworks including the Prisoners Dilemma and Stackleberg games. The resultant distribution ranges from static, to moderate, to viral in nature. Individual agents then use their knowledge source(s) to direct their actions in the performance environment. The results of the actions are then sent to the Accept function to decide what will be used to update the Belief Space, and then the cycle continues.
The knowledge sources themselves can support exploitative, exploratory, or stem behaviors. Exploratory mechanisms produce new knowledge about the search space, while exploitative mechanisms focus the search within already discovered regions. A knowledge source that exhibits a “stem” behavior is one that can either produce exploitative or exploratory behavior dependent on the context. The term itself derives from the biologic notion of “stem cell.” It is a useful transitional device since in the solution of a complex multiphase optimization problem knowledge sources that are useful in one phase may become less useful at the onset of another. The stem knowledge source can help expedite the transition from one set of knowledge sources, say exploitative, that are dominant at the end of one phase to a set that are more useful in the start of the next phase, such as exploratory ones.
This ability to transition from the use of one set of knowledge sources to another as problem dynamics change is one of the key features of cultures in general. The goal of a Cultural System like that of an operating system for a computer is to continue to provide resources for its active agents. The features inherent in the Cultural Algorithm that support this notion of process sustainability are as follows:
1 Cultural Algorithms inherently support multiobjective approaches to problem solving. A multiobjective problem is when there is some conflict in an agent's goals, such that the achievement of one goal takes resources away from achieving the other. Since conflicting objectives can reside simultaneously in the Belief Space, agents working on one goal may need to resolve conflicts with agents working on complementary ones. So Cultural Algorithms do not need to be restructured to explicitly deal with multiobjective problems, whereas other machine learning algorithms may need to do so.
2 Cultural Algorithms inherently support population co‐evolution. Stress within the social fabric can naturally produce co‐evolving populations. New links can be created subsequently to allow the separate populations to interact again.
3 Cultural Algorithms also support alternative ways to use resources through the emergence of subcultures. A subculture is defined as a culture contained within a broader mainstream culture, with its own set of goals, values, practices, and beliefs. Just as co‐evolution concerns the disconnection of individuals in the agent network, subcultures represent a corresponding separation of knowledge sources in the Belief Space into subcomponents that are linked to groups of connected individuals within the Population Space.
4 Cultural Algorithms support the social context of an individual by providing mechanisms for that individual to resolve conflicts with other individuals in the population space through the use of knowledge distribution mechanisms. These mechanisms are designed to reduce conflicts between individuals through the sharing of knowledge sources that influence them. This practice can be used to modulate the flow of knowledge through the population. The use of certain distribution strategies can produce viral distributions of information on the one hand or slow down the flows of the other knowledge sources dependent on the context. This feature makes it a useful learning mechanism with regards to design of systems that involve teams of agents.
5 Cultural Algorithms support the idea of a networked performance space. That is, the performance environment can be viewed as a connected collection of performance functions or performance simulators. This allows agent performance to potentially modify performance assessment and expectations.
6 Cultural Algorithms can exhibit the flexibility needed to cope with the changing environments in which they are embedded. They were in fact developed to learn about how social systems evolved in complex environments [3].
7 Cultural Algorithms facilitate the development of distributed systems and their supporting algorithms. The knowledge‐intensive nature of cultural systems requires the support of both distributed and parallel algorithms in the coordination of agents and their use of knowledge.
All of these features have been observed to emerge in one or more of the various Cultural Algorithm systems that have been developed over the years. In subsequent chapters of this book, we will provide examples of these features as they have emerged and their context.
The Cultural Engine
While there is wide variety of ways in which Cultural Algorithms can be implemented, there is a general metaphor that describes the learning process in all of them. The metaphor is termed the “Cultural Engine.” The basic idea is that the new ideas generated in the Belief Space by the incorporation of new experiences into the existing knowledge sources produce the capacity for changes in behavior. This capacity can be viewed as entropy in a thermodynamic sense. The influence function in conjunction with the knowledge distribution function can then distribute this potential for variation through the network of agents in the Population Space. Their behaviors taken together provide a potential for new ideas that is then communicated to the Belief Space and the cycle continues.
We can express the Cultural Algorithm Engine in terms of the entropy‐based laws of thermodynamics. The basic laws of classical thermodynamic concerning systems in equilibrium are given below [4]:
Zeroth Law of Thermodynamics, About Thermal Equilibrium
If two thermodynamic systems are separately in thermal equilibrium with a third, they are also in thermal equilibrium with each other. If we assume that all systems are (trivially) in thermal equilibrium with themselves, the Zeroth law implies that thermal equilibrium is an equivalence relation on the set of thermodynamic systems. This law is tacitly assumed in every measurement of temperature.
First Law of Thermodynamics, About the Conservation of Energy
The change in the internal energy of a closed thermodynamic system is equal to the sum of the amount of heat energy supplied to or removed from the system and the work done on or by the system.
Second