Active Interactive Genetic Algorithms for Reducing User Fatigue and Boosting Evaluation Consistency in Search-Based Domain

 

Interactive genetic algorithms (iGAs) depend on the evaluations or decisions provided by a user. The reliability of those evaluations is key for the successful application of iGAs. However, even moderately-sized problems my require thousands of evaluations that are sometimes between rather similar solutions which can lead to frustration and inconsistent evaluations.

This invention provides a scheme for actively combating user fatigue and inconsistency in iGAs. The efficiency gained from using an interactive procedure by requiring fewer evaluations is lost if the user is unable to provide consistent evaluations. This invention leads to the creation of active iGAs (aiGAs) which include steps of learning from human-computer interaction that actively guide the search-based interaction process.

The innovation includes an evaluation-relaxation scheme that actively combats user fatigue and inconsistency by addressing two important issues:

  • Lack of computable fitness
  • Lack of a systematic method for modeling user-decision process

Active iGAs optimize a synthetic fitness to obtain educated guesses of the user preferences and thereby reduce the number of user evaluations required. Three important components enable this invention to combat user fatigue and inconsistency.

  • Partial Ordering: Qualitative decisions made by the user about relative solution quality are used to generate partial ordering of solutions Induced
  • Complete Order: Concepts of non-domination and domination count from multi-objective evolutionary algorithms to induce a complete order of the solutions in the population based on their partial ordering
  • Surrogate Function: Induced order is used to assign ranks to the solutions and use them

Applications

This technology provides the ability to solve difficult problems such as data management, engineering design and optimization, and time and resource allocation in large-scale businesses and organizations, more quickly, reliably, and accurately.