Human-based genetic algorithm

Last updated January 31, 2022

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.

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	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 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 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.
A 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.
Education and Academic benefits from Real Time Simulation with Synthetic Curriculum Modeling using Dynamic Point Cloud environments.

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.

Furthermore, human-based genetic algorithms prove to be a successful measure to counteract fatigue effects introduced by interactive genetic algorithms.^[1]

Related Research Articles

In artificial intelligence, genetic programming (GP) is a technique of evolving programs, starting from a population of unfit programs, fit for a particular task by applying operations analogous to natural genetic processes to the population of programs.

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection. Some examples of GA applications include optimizing decision trees for better performance, automatically solve sudoku puzzles, hyperparameter optimization, etc.

In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions. Evolution of the population then takes place after the repeated application of the above operators.

In computer science, evolutionary computation is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms, they are a family of population-based trial and error problem solvers with a metaheuristic or stochastic optimization character.

NeuroEvolution of Augmenting Topologies (NEAT) is a genetic algorithm (GA) for the generation of evolving artificial neural networks developed by Ken Stanley in 2002 while at The University of Texas at Austin. It alters both the weighting parameters and structures of networks, attempting to find a balance between the fitness of evolved solutions and their diversity. It is based on applying three key techniques: tracking genes with history markers to allow crossover among topologies, applying speciation to preserve innovations, and developing topologies incrementally from simple initial structures ("complexifying").

In genetic algorithms and evolutionary computation, crossover, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring. It is one way to stochastically generate new solutions from an existing population, and is analogous to the crossover that happens during sexual reproduction in biology. Solutions can also be generated by cloning an existing solution, which is analogous to asexual reproduction. Newly generated solutions are typically mutated before being added to the population.

Collaborative intelligence characterizes multi-agent, distributed systems where each agent, human or machine, is autonomously contributing to a problem solving network. Collaborative autonomy of organisms in their ecosystems makes evolution possible. Natural ecosystems, where each organism's unique signature is derived from its genetics, circumstances, behavior and position in its ecosystem, offer principles for design of next generation social networks to support collaborative intelligence, crowdsourcing individual expertise, preferences, and unique contributions in a problem solving process.

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 or the result of optimization should fit a particular user preference.

In computer programming, 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 evolvable is a hard problem in evolutionary computation. Difference in genetic representations is one of the major criteria drawing a line between known classes of evolutionary computation.

Human-based computation (HBC), human-assisted computation, ubiquitous human computing or distributed thinking is a computer science technique in which a machine performs its function by outsourcing certain steps to humans, usually as microwork. This approach uses differences in abilities and alternative costs between humans and computer agents to achieve symbiotic human–computer interaction. For computationally difficult tasks such as image recognition, human-based computation plays a central role in training Deep Learning-based Artificial Intelligence systems. In this case, human-based computation has been referred to as human-aided artificial intelligence.

Human-based evolutionary computation (HBEC) is a set of evolutionary computation techniques that rely on human innovation.

3form Free Knowledge Exchange is one of the earliest examples of human-based computation and human-based genetic algorithm. It uses both human-based selection and three types of human-based innovation, in order to implement collaborative problem-solving between humans.

A hyper-heuristic is a heuristic search method that seeks to automate, often by the incorporation of machine learning techniques, the process of selecting, combining, generating or adapting several simpler heuristics to efficiently solve computational search problems. One of the motivations for studying hyper-heuristics is to build systems which can handle classes of problems rather than solving just one problem.

Lateral computing is a lateral thinking approach to solving computing problems. Lateral thinking has been made popular by Edward de Bono. This thinking technique is applied to generate creative ideas and solve problems. Similarly, by applying lateral-computing techniques to a problem, it can become much easier to arrive at a computationally inexpensive, easy to implement, efficient, innovative or unconventional solution.

Design Automation usually refers to electronic design automation, or Design Automation which is a Product Configurator. Extending Computer-Aided Design (CAD), automated design and Computer-Automated Design (CAutoD) are more concerned with a broader range of applications, such as automotive engineering, civil engineering, composite material design, control engineering, dynamic system identification and optimization, financial systems, industrial equipment, mechatronic systems, steel construction, structural optimisation, and the invention of novel systems.

In applied mathematics, multimodal optimization deals with optimization tasks that involve finding all or most of the multiple solutions of a problem, as opposed to a single best solution. Evolutionary multimodal optimization is a branch of evolutionary computation, which is closely related to machine learning. Wong provides a short survey, wherein the chapter of Shir and the book of Preuss cover the topic in more detail.

Natural computing, also called natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of novel problem-solving techniques; 2) those that are based on the use of computers to synthesize natural phenomena; and 3) those that employ natural materials to compute. The main fields of research that compose these three branches are artificial neural networks, evolutionary algorithms, swarm intelligence, artificial immune systems, fractal geometry, artificial life, DNA computing, and quantum computing, among others.

This glossary of artificial intelligence is a list of definitions of terms and concepts relevant to the study of artificial intelligence, its sub-disciplines, and related fields. Related glossaries include Glossary of computer science, Glossary of robotics, and Glossary of machine vision.

Multi-task optimization is a paradigm in the optimization literature that focuses on solving multiple self-contained tasks simultaneously. The paradigm has been inspired by the well-established concepts of transfer learning and multi-task learning in predictive analytics.

References

↑ Kruse, J.; Connor, A. (2015). "Multi-agent evolutionary systems for the generation of complex virtual worlds". EAI Endorsed Transactions on Creative Technologies. 2 (5): 150099. arXiv: 1604.05792 . doi:10.4108/eai.20-10-2015.150099. S2CID 12670076.

Kosorukoff, Alex (1999). Free knowledge exchange. internet archive
Kosorukoff, Alex (2000). Human-based genetic algorithm. online
Kosorukoff, Alex (2001). Human-based genetic algorithm. In IEEE International Conference 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
Milani, Alfredo (2004). Online Genetic Algorithms. International Journal of Information Theories and Applications pp. 20–28
Milani, Alfredo and Silvia Suriani (2004), ADAN: Adaptive Newspapers based on Evolutionary Programming In IEEE/WIC/ACM International Conference on Web Intelligence,(WI'04), pp. 779–780, IEEE Press, 2004
Allan, Michael (2005). Simple recombinant design. SourceForge.net, project textbender, release 2005.0, file _/description.html. release archives, later version online
Kruse, Jan (2015). Interactive evolutionary computation in design applications for virtual worlds. full text
Kruse, Jan and Connor, Andy (2015). Multi-agent evolutionary systems for the generation of complex virtual worlds. full text

External links

Free Knowledge Exchange, a project using HBGA for collaborative solving of problems expressed in natural language.
ParEvo, ParEvo is a method of developing alternative future scenarios, using a participatory evolutionary process

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Kruse, J.; Connor, A. (2015). "Multi-agent evolutionary systems for the generation of complex virtual worlds". EAI Endorsed Transactions on Creative Technologies. 2 (5): 150099. arXiv: 1604.05792 . doi:10.4108/eai.20-10-2015.150099. S2CID 12670076.

[1]