The invention relates generally to the field of methods and systems for interactive computing. The invention relates more particularly to the fields of methods for optimization.
Genetic and evolutionary algorithms (GAs) may be employed to optimize a solution set in a variety of problem types. Generally, GAs include selection from among a plurality of possible solutions based on fitness and recombination of one or more selected solutions to generate additional possible solutions. These two actions may be repeated as necessary until there is a convergence to an optimal or suitable solution.
An important concept used in GAs to implement a survival-of-the-fittest mechanism and to distinguish between good and bad solutions is the notion of fitness. Unlike traditional search methods, a fitness measure can be relative, and it can be an objective measure including a mathematical equation, model, or a computation. It could also be a subjective measure involving human evaluation, or even be coevolved in a co-operative or competitive environment.
GAs may be classified generally based on whether selection (choosing) and recombination (innovation), respectively, are performed by a human or by a computational agent such as, but not limited to, a computer. For example, a standard GA relies on computational selection (e.g., via computing a fitness function, model, or computation) and recombination (e.g., crossover and/or mutation). Computer-aided design (CAD), on the other hand, relies on computational selection of solutions, but a human performs the recombination of the solutions. In a human-based GA, a human performs both steps, though these steps may be augmented, for example, by a network or other communication or collaborative medium.
GAs in which fitness measure or quality of candidate solutions (e.g., selection or choosing) is provided by human evaluation and/or judgment rather than a fitness function, but in which recombination (e.g., innovation) is at least in part based on a computational agent are referred to as interactive genetic algorithms (iGAs). iGAs, a method of interactive evolutionary computation, allow human interaction to provide subjective input regarding fitness, while still providing computational recombination.
More particularly, in conventional iGAs, qualitative fitness as determined by a human user replaces quantitative fitness. As one example of providing qualitative fitness, a subset of generated solutions may be sorted and presented to a user, who selects a preferred solution from among the presented ones. The preferred solution is used for computationally-provided recombination of new subsets, which are again presented to the user.
Dawkin's Blind Watchmaker program, described in Dawkins, R., The Blind Watchmaker, New York: W. W. Norton, 1986, and the Faceprints system developed at New Mexico State University, as described in Caldwell, C., and Johnston, V. S., “Tracking a criminal suspect through face-space with a genetic algorithm”, Proceedings of the Fourth International Conference on Genetic Algorithms, Morton Kaufmann, 1991, pp, 416-421, are two nonlimiting examples of iGAs. For example, in Faceprints, a system replaces the role of a human sketch artist in evolving the faces of criminal suspects from witness recollection. Faces are encoded as binary strings, where subcodes represent different facial features (nose type, mouth type, hair type, etc.). Each full chromosome maps to a face, and the population of chromosomes is presented to the human critic, who is asked to determine how closely the face resembles that of the criminal. This subjective ten-point scale is used to drive the evolution of subsequent generations of faces, and in a relatively short time, the iGA arrives at a reasonable facsimile of the correct face.
However, unlike in evolutionary algorithms with objective fitness measures, one of the daunting challenges of iGAs is providing effective methods of combating user fatigue. Because a human is in charge of the evaluation of a solution, user fatigue results from the large time scale between user evaluations and the evolutionary mechanisms used to generate new solutions until convergence. For example, even for moderately sized problems, iGAs may require, for example, a few hundred to a few thousand fitness evaluations, which is highly improbable—sometimes even impossible—for users to perform. User fatigue may occur at fairly short time periods, such as within 1-2 hours, or even earlier.
User fatigue can result in sub-optimal solutions, or the end of an iGA session before even a suitable solution is found. Similarly, repeated evaluation of similar solutions can result in user frustration relatively quickly, compounding user fatigue.
Additionally, an important element for the successful application of interactive genetic algorithms (iGAs) or any other interactive evolutionary computation method is the reliability of the evaluations, or decisions, provided by a user. The decisions that the user makes when using an iGA guide the search across the space of possible hypotheses. Any interactive procedure, regardless of how efficient it can be for reducing the number of evaluations required, will fail to provide high-quality solutions if the user is unable to provide consistent fitness evaluations.
Thus, it is desired to provide ways to improve efficiency enhancement for iGAs, while also providing the reliability needed to use iGAs successfully.