Behavior dominated search in evolutionary search systems

Patent metadata

Field	Value
Publication number	US-11247100-B2
Application number	US-202016934681-A
Country	US
Kind code	B2
Filing date	Jul 21, 2020
Priority date	Mar 3, 2017
Publication date	Feb 15, 2022
Grant date	Feb 15, 2022

Abstract

Roughly described, a computer system uses a behavior-driven algorithm that is better able to find optimum solutions to a problem by balancing the use of fitness and novelty measures in evolutionary optimization. In competition among candidate individuals, a domination estimate between a pair of individuals is determined by both their fitness estimate difference and their behavior difference relative to one another. An increase in the fitness estimate difference of one individual of the pair over the other increases the domination estimate of the first individual. An increase in the behavior distance between the pair of individuals decreases the domination estimate of both of the individuals. Individuals with a higher domination estimate are more likely to survive competitions among the candidate individuals.

First claim

The invention claimed is:

1. A computer-implemented method for discovering optimal solutions to a predetermined problem, comprising the steps of:
providing a computer system including a memory having a candidate pool database identifying a pool of candidate individuals, each candidate individual identifying a potential solution to the predetermined problem, each candidate individual further having associated therewith an indication of a respective fitness estimate, wherein the pool of candidate individuals includes multiple layers each layer including multiple candidate individuals in accordance with parameters for inclusion therein and each layer including a capacity Quota(L target ) for an allowable number of candidate individuals to be included therein;
a computer system testing individuals from the pool of candidate individuals against a portion of the training data;
a computer system updating the fitness estimates for selected ones of individuals tested, in dependence upon the results of such testing;
a computer system determining a domination estimate for (x) individuals from the pool of candidate individuals relative to other (y) individuals in the pool in accordance with the following function
( x,y )=( f ( x )− f ( y ))− w·d ( b ( x ), b ( y ))

wherein f(x)−f(y) is the fitness estimate difference between individuals (x) and (y), d(b(x),b(y)) is a behavior difference between individuals x and y, and w is a scaling parameter;
a computer system selecting individuals for inclusion in one of the multiple layers L 1 -L T in accordance with an experience parameter, wherein individuals in layer L T have the most experience and further wherein an individual can be reassigned to a different of the multiple layers L 1 -L T in accordance with a change in at least the individual's experience parameter;
a computer system selecting individuals for discarding from a layer L target of the candidate pool when the capacity Quota(L target ) for that layer is reached, wherein the discarding depends upon the domination estimate for the selected individuals; and
a computer system selecting one or more individuals from layer L T as optimal solutions to the predetermined problem.

2. The method of claim 1 , wherein testing individuals from the pool of candidate individuals against a portion of the training data includes identifying a behavioral value of the individual when tested against the portion of the training data, according to a predefined measure of behavior.

3. The method of claim 1 , wherein selecting individuals for discarding from layer L target in dependence upon their domination estimate comprises building a retention set of N>0 individuals to retain, wherein N is Quota(L target ) and discarding from the layer L target all individuals which are not in the retention set, wherein building the retention set comprises:
creating a plurality of subsets i of individuals from L target wherein each subset i has N i individuals;
adding to the retention set a number No of individuals that are not dominated by any other individuals in the subset, No being the lesser of N and the number of individuals in the subset that are not dominated by any other individuals in the subset; and
for i incrementing from 1 until the number of individuals in the retention set reaches N, adding to the retention set N i individuals that are dominated by individuals in the retention set but not by any other individuals in the subset.

4. The method of 3 , wherein in the last iteration of adding to the retention set Ni individuals, i is equal to a final value p, wherein after the (p−1)'th iteration, P>1 of the individuals in the subset are dominated by individuals in the retention set but not by any other individuals in the subset, the P individuals constituting a p'th subset, and wherein adding to the retention set Np individuals comprises selecting the Np individuals from among the individuals in the p'th subset in dependence upon both their relative fitness and the relative similarity of their behavior.

5. The method of 4 , wherein testing individuals from the pool of candidate individuals against a portion of the training data includes identifying a behavioral value of the individual when tested against the portion of the training data, according to a predefined measure of behavior, and wherein selecting the Np individuals from among the individuals in the p'th subset comprises iteratively, until the number of individuals in the p'th subset reaches Np, removing from the p'th subset the less fit of two individuals in the p'th subset which are most similar in their behavioral values.

6. The method of claim 1 , wherein the fitness estimate for each candidate individual in the pool is determined by the computer system based on a predetermined performance measure that is specific to the problem, the computer system calculating the fitness estimate in accordance with the following:

fitness
⁢

⁢
estimate

=

∑

i
=
1

n

⁢

⁢

performance
⁢

⁢

measure
i

n

wherein performance measure i is each candidate individual's performance measure when tested on a data sample i from the training data, and n is the number of data samples on which each candidate individual has been tested.

7. The method of claim 1 , further comprising procreating by the computer system additional candidate individuals using one or more non-discarded individuals in accordance with predetermined procreation rules, wherein the additional candidate individuals are subjected to testing against a portion of the training data, assigned estimate fitness estimates and subjected to domination estimate comparison.

8. A non-transitory computer readable medium having stored thereon a plurality of instructions which when executed by a processing unit cause the processing unit to:
provide a candidate pool database identifying a pool of candidate individuals, each candidate individual identifying a potential solution to the predetermined problem, each candidate individual further having associated therewith an indication of a respective fitness estimate, wherein the pool of candidate individuals includes multiple layers L 1 -L T , each layer including multiple candidate individuals in accordance with parameters for inclusion therein and each layer including a capacity Quota(L target ) for an allowable number of candidate individuals to be included therein;
test individuals from the pool of candidate individuals against a portion of the raining data;
update the fitness estimates for selected ones of individuals tested, in dependence upon the results of such testing;
determine a domination estimate for (x) individuals from the pool of candidate individuals relative to other (y) individuals in the pool in accordance with the following function
( x,y )=( f ( x )− f ( y ))− w·d ( b ( x ), b ( y ))

wherein f(x)−f(y) is the

Assignees

• Cognizant Tech Solutions U S Corporation

Inventors

• Meyerson Elliot
• Miikkulainen Risto

Classifications

• G16H20/30 Primary

  relating to physical therapies or activities, e.g. physiotherapy, acupressure or exercising · CPC title

• G06F16/23

  Updating · CPC title

• A63B24/0062 Primary

  Monitoring athletic performances, e.g. for determining the work of a user on an exercise apparatus, the completed jogging or cycling distance · CPC title

• A63B2024/0065

  Evaluating the fitness, e.g. fitness level or fitness index · CPC title

• A63B2024/0068

  Comparison to target or threshold, previous performance or not real time comparison to other individuals · CPC title