Human-based genetic algorithm
Encyclopedia
In evolutionary computation
, a human-based genetic algorithm (HBGA) is a genetic algorithm
that allows humans to contribute solution suggestions to the evolutionary process. For this purpose, a HBGA has human interfaces for initialization, mutation, and recombinant crossover. As well, it may have interfaces for selective evaluation. In short, a HBGA outsources the operations of a typical genetic algorithm to humans.
This table compares systems on lines of human agency:
One obvious pattern in the table is the division between organic (top) and computer systems (bottom).
Another is the vertical symmetry between autonomous systems (top and bottom) and human-interactive systems (middle).
Looking to the right, the selector is the agent that decides fitness in the system.
It determines which variations will reproduce and contribute to the next generation.
In natural populations, and in genetic algorithms, these decisions are automatic; whereas in typical HBGA systems, they are made by people.
The innovator is the agent of genetic change.
The innovator mutates and recombines the genetic material, to produce the variations on which the selector operates.
In most organic and computer-based systems (top and bottom), innovation is automatic, operating without human intervention.
In HBGA, the innovators are people.
HBGA is roughly similar to genetic engineering.
In both systems, the innovators and selectors are people.
The main difference lies in the genetic material they work with: electronic data vs. polynucleotide sequences.
The HBGA methodology was derived in 1999-2000 from analysis of the Free Knowledge Exchange project that was launched in the summer of 1998, in Russia (Kosorukoff, 1999). Human innovation and evaluation were used in support of collaborative problem solving. Users were also free to choose the next genetic operation to perform. Currently, several other projects implement the same model, the most popular being Yahoo! Answers
, launched in December 2005.
Recent research suggests that human-based innovation operators are advantageous not only where it is hard to design an efficient computational mutation and/or crossover (e.g. when evolving solutions in natural language), but also in the case where good computational innovation operators are readily available, e.g. when evolving an abstract picture or colors (Cheng and Kosorukoff, 2004). In the latter case, human and computational innovation can complement each other, producing cooperative results and improving general user experience by ensuring that spontaneous creativity of users will not be lost.
Evolutionary computation
In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
, a human-based genetic algorithm (HBGA) is a 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...
that allows humans to contribute solution suggestions to the evolutionary process. For this purpose, a HBGA has human interfaces for initialization, mutation, and recombinant crossover. As well, it may have interfaces for selective evaluation. In short, a HBGA outsources the operations of a typical genetic algorithm to humans.
Evolutionary genetic systems and human agency
Among evolutionary genetic systems, HBGA is the computer-based analogue of genetic engineering (Allan, 2005).This table compares systems on lines of human agency:
| system | sequences | innovator | selector |
|---|---|---|---|
| natural selection Natural selection Natural selection is the nonrandom process by which biologic traits become either more or less common in a population as a function of differential reproduction of their bearers. It is a key mechanism of evolution.... | nucleotide Nucleotide Nucleotides are molecules that, when joined together, make up the structural units of RNA and DNA. In addition, nucleotides participate in cellular signaling , and are incorporated into important cofactors of enzymatic reactions... | nature Nature Nature, in the broadest sense, is equivalent to the natural world, physical world, or material world. "Nature" refers to the phenomena of the physical world, and also to life in general... | nature |
| artificial selection Artificial selection Artificial selection describes intentional breeding for certain traits, or combination of traits. The term was utilized by Charles Darwin in contrast to natural selection, in which the differential reproduction of organisms with certain traits is attributed to improved survival or reproductive... | nucleotide | nature | human Human Humans are the only living species in the Homo genus... |
| genetic engineering Genetic engineering Genetic engineering, also called genetic modification, is the direct human manipulation of an organism's genome using modern DNA technology. It involves the introduction of foreign DNA or synthetic genes into the organism of interest... | nucleotide | human | human |
| human-based genetic algorithm | data | human | human |
| interactive genetic algorithm | data | computer | human |
| 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... | data | computer | computer |
One obvious pattern in the table is the division between organic (top) and computer systems (bottom).
Another is the vertical symmetry between autonomous systems (top and bottom) and human-interactive systems (middle).
Looking to the right, the selector is the agent that decides fitness in the system.
It determines which variations will reproduce and contribute to the next generation.
In natural populations, and in genetic algorithms, these decisions are automatic; whereas in typical HBGA systems, they are made by people.
The innovator is the agent of genetic change.
The innovator mutates and recombines the genetic material, to produce the variations on which the selector operates.
In most organic and computer-based systems (top and bottom), innovation is automatic, operating without human intervention.
In HBGA, the innovators are people.
HBGA is roughly similar to genetic engineering.
In both systems, the innovators and selectors are people.
The main difference lies in the genetic material they work with: electronic data vs. polynucleotide sequences.
Differences from a plain genetic algorithm
- All four genetic operators (initialization, mutation, crossover, and selection) can be delegated to humans using appropriate interfaces (Kosorukoff, 2001).
- Initialization is treated as an operator, rather than a phase of the algorithm. This allows a HBGA to start with an empty population. Initialization, mutation, and crossover operators form the group of innovation operators.
- Choice of genetic operator may be delegated to humans as well, so they are not forced to perform a particular operation at any given moment.
Functional features
- HBGA is a method of collaboration and knowledge exchange. It merges competence of its human users creating a kind of symbiotic human-machine intelligence (see also distributed artificial intelligenceDistributed artificial intelligenceDistributed artificial intelligence is a subfield of artificial intelligence research dedicated to the development of distributed solutions for complex problems regarded as requiring intelligence...
).
- Human innovation is facilitated by sampling solutions from population, associating and presenting them in different combinations to a user (see creativity techniquesCreativity techniquesCreativity techniques are methods that encourage creative actions, whether in the arts or sciences. They focus on a variety of aspects of creativity, including techniques for idea generation and divergent thinking, methods of re-framing problems, changes in the affective environment and so on. They...
).
- HBGA facilitates consensus and decision making by integrating individual preferences of its users.
- HBGA makes use of a cumulative learningMulti-task learningMulti-task learning is an approach to machine learning that learns a problem together with other related problems at the same time, using a shared representation. This often leads to a better model for the main task, because it allows the learner to use the commonality among the tasks...
idea while solving a set of problems concurrently. This allows to achieve synergy because solutions can be generalized and reused among several problems. This also facilitates identification of new problems of interest and fair-share resource allocation among problems of different importance.
- The choice of genetic representation, a common problem of genetic algorithms, is greatly simplified in HBGA, since the algorithm need not be aware of the structure of each solution. In particular, HBGA allows natural language to be a valid representation.
- Storing and sampling population usually remains an algorithmic function.
- A HBGA is usually a multi-agent systemMulti-agent systemA multi-agent system is a system composed of multiple interacting intelligent agents. Multi-agent systems can be used to solve problems that are difficult or impossible for an individual agent or a monolithic system to solve...
, delegating genetic operations to multiple agents (humans).
Applications
- Evolutionary knowledge managementKnowledge managementKnowledge management comprises a range of strategies and practices used in an organization to identify, create, represent, distribute, and enable adoption of insights and experiences...
, integration of knowledge from different sources.
- Social organization, collective decision-making, and e-governanceE-GovernanceSeveral dimension and related factors influence the definition of eGovernance. The word “electronic” in the term e-Governance implies technology driven governance...
.
- Traditional areas of application of interactive genetic algorithms: computer artComputer artComputer art is any art in which computers play a role in production or display of the artwork. Such art can be an image, sound, animation, video, CD-ROM, DVD-ROM, videogame, web site, algorithm, performance or gallery installation...
, user-centered designUser-centered designIn broad terms, user-centered design or pervasive usability is a design philosophy and a process in which the needs, wants, and limitations of end users of a product are given extensive attention at each stage of the design process...
, etc.
- Collaborative problem solving using natural language as a representation.
The HBGA methodology was derived in 1999-2000 from analysis of the Free Knowledge Exchange project that was launched in the summer of 1998, in Russia (Kosorukoff, 1999). Human innovation and evaluation were used in support of collaborative problem solving. Users were also free to choose the next genetic operation to perform. Currently, several other projects implement the same model, the most popular being Yahoo! Answers
Yahoo! Answers
Yahoo! Answers is a community-driven question-and-answer site or a knowledge market launched by Yahoo! on June 28, 2005 that allows users to both submit questions to be answered and answer questions asked by other users...
, launched in December 2005.
Recent research suggests that human-based innovation operators are advantageous not only where it is hard to design an efficient computational mutation and/or crossover (e.g. when evolving solutions in natural language), but also in the case where good computational innovation operators are readily available, e.g. when evolving an abstract picture or colors (Cheng and Kosorukoff, 2004). In the latter case, human and computational innovation can complement each other, producing cooperative results and improving general user experience by ensuring that spontaneous creativity of users will not be lost.
See also
- Human-based computationHuman-based computationHuman-based computation is a computer science technique in which a computational process performs its function by outsourcing certain steps to humans...
- Human-based evolutionary computationHuman-based evolutionary computationHuman-based evolutionary computation is a set of evolutionary computation techniques that rely on human innovation. Human-based evolutionary computation techniques can be classified into three more specific classes analogous to ones in evolutionary computation. There are three basic types of...
- Human-computer interaction
- Interactive genetic algorithm
- 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...
- Social computingSocial computingSocial computing is a general term for an area of computer science that is concerned with the intersection of social behavior and computational systems. It has become an important concept for use in business. It is used in two ways as detailed below....
External links
- Free Knowledge Exchange, a project using HBGA for collaborative solving of problems expressed in natural language.