Cultural algorithm
Encyclopedia
Cultural algorithms are a branch of evolutionary computation
where there is a knowledge component that is called the belief space in addition to the population
component. In this sense, cultural algorithms can be seen as an extension to a conventional genetic algorithm
. Cultural algorithms were introduced by Reynolds (see references).
.
The belief space is updated after each iteration
by the best individuals of the population. The best individuals can be selected using a fitness function
that assesses the performance of each individual in population much like in genetic algorithms.
.
Evolutionary computation
In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
where there is a knowledge component that is called the belief space in addition to the population
Population
A population is all the organisms that both belong to the same group or species and live in the same geographical area. The area that is used to define a sexual population is such that inter-breeding is possible between any pair within the area and more probable than cross-breeding with individuals...
component. In this sense, cultural algorithms can be seen as an extension to a conventional genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
. Cultural algorithms were introduced by Reynolds (see references).
Belief space
The belief space of a cultural algorithm is divided into distinct categories. These categories represent different domains of knowledge that the population has of the search spaceSearch algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
.
The belief space is updated after each iteration
Iteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
by the best individuals of the population. The best individuals can be selected using a fitness function
Fitness function
A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims....
that assesses the performance of each individual in population much like in genetic algorithms.
List of belief space categories
- Normative knowledge A collection of desirable value ranges for the individuals in the population component e.g. acceptable behavior for the agents in population.
- Domain specific knowledge Information about the domain of the problem CA is applied to.
- Situational knowledge Specific examples of important events - e.g. successful/unsuccessful solutions
- Temporal knowledge History of the search space - e.g. the temporal patterns of the search process
- Spatial knowledge Information about the topography of the search space
Population
The population component of the cultural algorithm is approximately the same as that of the genetic algorithmGenetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
.
Communication protocol
Cultural algorithms require an interface between the population and belief space. The best individuals of the population can update the belief space via the update function. Also, the knowledge categories of the belief space can affect the population component via the influence function. The influence function can affect population by altering the genome or the actions of the individuals.Pseudo-code for cultural algorithms
- Initialize population space (choose initial populationPopulationA population is all the organisms that both belong to the same group or species and live in the same geographical area. The area that is used to define a sexual population is such that inter-breeding is possible between any pair within the area and more probable than cross-breeding with individuals...
) - Initialize belief space (e.g. set domain specific knowledge and normative value-ranges)
- Repeat until termination condition is met
- Perform actions of the individuals in population space
- Evaluate each individual by using the fitness function
- Select the parents to reproduce a new generation of offspring
- Let the belief space alter the genome of the offspring by using the influence function
- Update the belief space by using the accept function (this is done by letting the best individuals to affect the belief space)
See also
- Artificial intelligenceArtificial intelligenceArtificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
- Artificial lifeArtificial lifeArtificial life is a field of study and an associated art form which examine systems related to life, its processes, and its evolution through simulations using computer models, robotics, and biochemistry. The discipline was named by Christopher Langton, an American computer scientist, in 1986...
- Evolutionary computationEvolutionary computationIn computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
- Genetic algorithmGenetic algorithmA genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
- Harmony searchHarmony searchIn computer science and operations research, harmony search is a phenomenon-mimicking algorithm inspired by the improvisation process of musicians...
- Machine learningMachine learningMachine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
- Memetic algorithmMemetic algorithmMemetic algorithms represent one of the recent growing areas of research in evolutionary computation. The term MA is now widely used as a synergy of evolutionary or any population-based approach with separate individual learning or local improvement procedures for problem search...
- MemeticsMemeticsMemetics is a theory of mental content based on an analogy with Darwinian evolution, originating from Richard Dawkins' 1976 book The Selfish Gene. It purports to be an approach to evolutionary models of cultural information transfer. A meme, analogous to a gene, is essentially a "unit of...
- MetaheuristicMetaheuristicIn computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
- Social simulationSocial simulationSocial simulation is a research field that applies computational methods to study issues in the social sciences. The issues explored include problems in sociology, political science, economics, anthropology, geography, archaeology and linguistics ....
- Sociocultural evolutionSociocultural evolutionSociocultural evolution is an umbrella term for theories of cultural evolution and social evolution, describing how cultures and societies have changed over time...
- Stochastic optimizationStochastic optimizationStochastic optimization methods are optimization methods that generate and use random variables. For stochastic problems, the random variables appear in the formulation of the optimization problem itself, which involve random objective functions or random constraints, for example. Stochastic...
- Swarm intelligenceSwarm intelligenceSwarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...