Wikia

Psychology Wiki

Human-based genetic algorithm

Talk0
34,130pages on
this wiki
Revision as of 07:20, April 2, 2007 by Dr Joe Kiff (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Assessment | Biopsychology | Comparative | Cognitive | Developmental | Language | Individual differences | Personality | Philosophy | Social |
Methods | Statistics | Clinical | Educational | Industrial | Professional items | World psychology |

Cognitive Psychology: Attention · Decision making · Learning · Judgement · Memory · Motivation · Perception · Reasoning · Thinking  - Cognitive processes Cognition - Outline Index


In evolutionary computation, a human-based genetic algorithm (HBGA) is a genetic algorithm that allows humans to contribute innovative solutions to the evolutionary process. For this purpose, an HBGA has human interfaces for initialization, mutation, and recombinant crossover. As well, it may have interfaces for selective evaluation. In short, an HBGA outsources the operations of a typical genetic algorithm to humans.

Classes of evolutionary genetic systems

Comparing a range of evolutionary genetic systems with respect to their dependence on human agency, an HBGA is similar to population genetic engineering (Allan, 2005). The similarity is most pronounced in extreme forms of HBGA, those that offer the widest scope to human intervention.

system sequences innovator selectand selector
nature nucleotide nature individual nature
artificial selection nucleotide nature individual human
population genetic engineering nucleotide human gene human
human-based genetic algorithm data human gene human
interactive genetic algorithm data computer individual human
genetic algorithm data computer individual 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 far 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 selectand is the unit selected. In most organic and computer systems (top and bottom) the selectand is the whole individual. For example, in artificial selection, a breeding individual is selected from a cohort of domestic animals or plants. Similarly, in interactive genetic algorithms a whole artifact is selected from the population of artifacts. By contrast, in extreme forms of HBGA, the selectand is a variant gene, compound, or genetic fragment from the gene pool. For instance, in simplex recombinant text (Allan, 2001) the selectand is a single gene. It replicates and contributes to the next generation, taking the place of another gene, which does not. In this case, selection and differential reproduction are integral to recombination. In less extreme forms, such as the original Free Knowledge Exchange, two promising gene fragments are selected, and rejoined in a crossover (Kosorukoff, 2000). The recombinant product is usually a 'favoured' combination, and a less favoured one. However, in this case, both remain in the populatation; differential reproduction is deferred, and when it occurs, the actual selectand is a whole individual, not a gene.

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 systems (top and bottom), innovation is automatic, operating without human intervention. In HBGA, the innovators are people.

HBGA (Kosorukoff, 2001) is similar to population genetic engineering (Burt and Trivers, 2005). In both systems, the innovators and selectors are people; in both, they work directly on genes; and in both, the ultimate purpose is to modify a population. The main difference lies in the genetic basis of the population: 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.
  • Initialization is treated as an operator, rather than a phase of the algorithm. This allows an 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 intelligence).
  • Human innovation is facilitated by sampling solutions from population, associating and presenting them in different combinations to a user (see creativity techniques).
  • HBGA facilitates consensus and decision making by integrating individual preferences of its users.
  • HBGA makes use of a cumulative learning 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.
  • An HBGA is usually a multi-agent system, delegating genetic operations to multiple agents (humans).

Applications

  • 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, 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

References

  • Kosorukoff, Alex (1999). Free knowledge exchange. internet archive
  • Kosorukoff, Alex (2000). Human-based genetic algorithm. online
  • Allan, Michael (2001). Method and system for evolutionary phenogenetic engineering. Canadian patent application 2,340,792 (withdrawn). filing record
  • Kosorukoff, Alex (2001). Human-based genetic algorithm. In IEEE Transactions on Systems, Man, and Cybernetics, SMC-2001, 3464-3469. full text
  • Cheng, Chihyung Derrick and Alex Kosorukoff (2004). Interactive one-max problem allows to compare the performance of interactive and human-based genetic algorithms. In Genetic and Evolutionary Computational Conference, GECCO-2004. full text
  • Allan, Michael (2005). Simple recombinant design. SourceForge.net, project textbender, release 2005.0, file _/description.html. internet archive, later version online
  • Burt, Austin and Robert Trivers. (2005). Genes in Conflict: The Biology of Selfish Genetic Elements. Harvard University Press.

External links

  • Free Knowledge Exchange, a project using HBGA for collaborative solving of problems expressed in natural language.
  • Textbender, a system of collaborative writing based on recombinant text.
This page uses Creative Commons Licensed content from Wikipedia (view authors).

Around Wikia's network

Random Wiki