Human-based genetic algorithm

Human-based genetic algorithm

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.

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
nature nucleotide nature nature
artificial selection nucleotide nature human
genetic engineering nucleotide human human
human-based genetic algorithm data human human
interactive genetic algorithm data computer human
genetic algorithm 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 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

* Evolutionary knowledge management, integration of knowledge from different sources.

* Social organization, collective decision-making, and e-governance.

* Traditional areas of application of interactive genetic algorithms: computer art, user-centered design, 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, 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.

ee also

*Human-based computation
*Human-based evolutionary computation
*Human-computer interaction
*Interactive genetic algorithm
*Memetics
*Social computing

References

*Kosorukoff, Alex (1999). Free knowledge exchange. [http://web.archive.org/web/19990824183328/www.3form.com/formula/whatis.htm internet archive]
*Kosorukoff, Alex (2000). Human-based genetic algorithm. [http://www.geocities.com/alex+kosorukoff/hbga/hbga.html online]
*Kosorukoff, Alex (2001). Human-based genetic algorithm. In "IEEE Transactions on Systems, Man, and Cybernetics", SMC-2001, 3464-3469. [http://intl.ieeexplore.ieee.org/xpl/abs_free.jsp?arNumber=972056 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. [http://www.derrickcheng.com/Project/HBGA full text]
*Allan, Michael (2005). Simple recombinant design. SourceForge.net, project textbender, release 2005.0, file _/description.html. [http://sourceforge.net/project/showfiles.php?group_id=134813&package_id=148018 release archives] , [http://zelea.com/project/textbender/d/approach-simplex-wide.xht later version online]

External links

* [http://www.3form.com Free Knowledge Exchange] , a project using HBGA for collaborative solving of problems expressed in natural language.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Human-based evolutionary computation — (HBEC) 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… …   Wikipedia

  • Human-based computation — In computer science, human based computation is a technique when a computational process performs its function via outsourcing certain steps to humans (Kosorukoff, 2001). This approach leverages differences in abilities and alternative costs… …   Wikipedia

  • Genetic algorithm — A genetic algorithm (GA) 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. Genetic algorithms belong to the larger class of… …   Wikipedia

  • Genetic representation — is a way of representing solutions/individuals in evolutionary computation methods. Genetic representation can encode appearance, behavior, physical qualities of individuals. Designing a good genetic representation that is expressive and… …   Wikipedia

  • Genetic memory — describes a variety of processes in biology and psychology by which genetic material confers a memory of an individual s or species past history. It can refer to the genetic code of DNA, epigenetic changes to the genetic material, the inheritance …   Wikipedia

  • Genetic programming — In artificial intelligence, genetic programming (GP) is an evolutionary algorithm based methodology inspired by biological evolution to find computer programs that perform a user defined task. It is a specialization of genetic algorithms where… …   Wikipedia

  • Genetic linkage — is the tendency of certain loci or alleles to be inherited together. Genetic loci that are physically close to one another on the same chromosome tend to stay together during meiosis, and are thus genetically linked. Contents 1 Background 2… …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Case-based reasoning — (CBR), broadly construed, is the process of solving new problems based on the solutions of similar past problems. An auto mechanic who fixes an engine by recalling another car that exhibited similar symptoms is using case based reasoning. A… …   Wikipedia

  • Interactive evolutionary computation — (IEC) or Aesthetic Selection is a general term for methods of evolutionary computation that use human evaluation. Usually human evaluation is necessary when the form of fitness function is not known (for example, visual appeal or attractiveness;… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”