Behavior dominated search in evolutionary search systems

A computer-implemented system for discovering optimal solutions to a problem defined based on a provided fitness function and provided training data, comprising:

• a memory storing a candidate pool database identifying a pool of candidate individuals, each candidate individual identifying a potential solution to the problem, each candidate individual further having associated therewith an indication of a respective fitness estimate;
• a processing unit which:
• i. tests individuals from the pool of candidate individuals against a portion of the training data;
• ii. updates the fitness estimates for selected ones of individuals tested, in dependence upon the results of such testing, 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 measurei 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;
• iii. determines 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 the behavior difference between individuals x and y, and w is a scaling parameter;
• iv. selects individuals for discarding from the pool of candidate individuals, in dependence upon their domination estimate, wherein the non-discarded candidate individuals are stepping stone candidate individuals;
• v. procreates additional candidate individuals using at least the stepping stone candidate 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
• vi. repeats steps i. to v. until an elitist pool of candidate individuals representing the optimal solutions is achieved.

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:

• i. provide a candidate pool database identifying a pool of candidate individuals, each candidate individual identifying a potential solution to a provided problem which is defined based on a provided fitness function and provided training data, each candidate individual further having associated therewith an indication of a respective fitness estimate;
• ii. test individuals from the pool of candidate individuals against a portion of the training data;
• iii. update the fitness estimates for selected ones of individuals tested, in dependence upon the results of such testing, 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 measurei 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;
• iv. 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 fitness estimate difference between individuals x and y, d(b(x),b(y) is the behavior difference between individuals x and y, and w is a scaling parameter;
• and
• v. select individuals for discarding from the pool of candidate individuals, in dependence upon their domination estimate, wherein the non-discarded candidate individuals are stepping stone candidate individuals;
• vi. procreate additional candidate individuals using at least the stepping stone candidate 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
• vii. repeat steps ii. to vi. until an elitist pool containing an optimal set of individuals is achieved.

A computer-implemented data mining system, for use with a data mining training database containing training data and for further use in selecting a diverse and optimal set of individuals, comprising:

• a memory storing a candidate pool database identifying a pool of candidate individuals, each candidate individual identifying a plurality of conditions and at least one corresponding proposed output in dependence upon the conditions, each candidate individual further having associated therewith an indication of a respective fitness estimate;
• means for testing individuals from the pool of candidate individuals against a portion of the training data;
• means for updating the fitness estimates for selected ones of individuals tested, in dependence upon the results of such testing, 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 measurei 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;
• means for 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 the behavior difference between individuals x and y, and w is a scaling parameter;
• means for selecting individuals for discarding from the pool of candidate individuals, in dependence upon their domination estimate;
• means for procreating additional candidate individuals using at least the stepping stone candidate 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;
• repeating steps of testing, updating, determining, selecting and procreating until an elitist pool containing an optimal set of individuals is achieved.