Enhanced optimization with composite objectives and novelty pulsation

Patent metadata

Field	Value
Publication number	US-11481639-B2
Application number	US-202016800208-A
Country	US
Kind code	B2
Filing date	Feb 25, 2020
Priority date	Feb 26, 2019
Publication date	Oct 25, 2022
Grant date	Oct 25, 2022

Abstract

The computer system and method herein uses a multi-objective driven evolutionary algorithm that is better able to find optimum solutions to a problem because it balances the use of objectives as composite functions, and relative novelty and diversity in evolutionary optimization. In particular, the system and method herein described herein presents an improved process which introduces novelty pulsation, i.e., a systematic method to alternate between novelty selection and local optimization.

First claim

The invention claimed is:

1. A computer-implemented method for finding a solution to a provided problem which optimizes a plurality of objectives and operates a controlled system using the found solution, comprising the steps of:
providing a computer system having a memory storing a candidate pool database identifying a pool of candidate individuals, each identifying a respective candidate solution to the provided problem;
testing, by the computer system, individuals from the pool of candidate individuals against a portion of training data to develop a plurality of objective values for each of the tested individuals, each of the objective values estimating the individual's level of success with respect to a corresponding one of the objectives;
selecting, by a predefined dominance filter of the computer system, a first subset of individuals from the candidate pool database, the dominance filter being dependent upon a plurality of composite functions of the objectives, each of the composite functions being dependent on at least one of the objectives and at least one of the composite functions being dependent on more than one of the objectives;
procreating, by the computer system, new individuals from one or more of the individuals in the first subset of the individuals selected by the dominance filter;
inserting the new individuals into the candidate pool database and repeating the steps of testing, selecting and procreating, wherein each iteration of the testing, selecting and procreation is a generation G until a predetermined end point is achieved;
further wherein, every P generations, wherein P=G, after the step of selecting a first subset of the individuals, selecting a second subset of individuals from the first subset of individuals, and selecting from the second subset a predetermined number of individuals having greater average behavioral novelty among the individuals in the first subset of individuals, than the average behavioral novelty of all others of the individuals from the first subset, and inserting the predetermined number of individuals selected from the second subset into the candidate pool database and repeating the steps of testing, selecting and procreating, wherein each iteration of the testing, selecting and procreation is a generation G until a predetermined end point is achieved; and
operating a controlled system in dependence upon at least one of the individuals from the candidate pool database when the predetermined end point is achieved.

2. The computer-implemented method of claim 1 , wherein P≥2.

3. The computer-implemented method of claim 1 , wherein selecting a second subset of individuals from the first subset of individuals includes:
re-selecting the first subset of individuals to include an expanded number of individuals in accordance with a multiplier m, wherein m is greater than 1;
determining a novelty score for each of the individuals in the expanded first subset;
sorting the individuals in the expanded first subset in descending order of novelty score;
selecting a predetermined number of sorted individuals to establish a result set, wherein the individual from the expanded first subset with the highest novelty score is selected first;
adding each non-selected, sorted individual from the expanded first subset one at a time to the result set and selecting for removal from the result set an individual having a lowest minimum novelty; and
returning a final result set after each non-selected, sorted individual has been iteratively added and compared.

4. The computer-implemented method of claim 3 , wherein the novelty score is determined as follows:

NoveltyScore
⁡
(

x
i

)

=

∑

j
=
1

n

d
⁡
(

b
⁡
(

x
i

)

,

b
⁡
(

x
j

)

)

wherein b(x i ) is a function mapping any solution x i to its behavior b xi , and d(b(x i ), b(x j )) is a behavior distance wherein x j is the j th nearest neighbor of x i in a behavior space.

5. The computer-implemented method of claim 4 , wherein minimum novelty is determined as follows:

MinimumNovelty
⁡
(

x
i

)

=

min

1
≤
j
≤

n
;
j

≠
i

d
⁡
(

b
⁡
(

x
i

)

,

b
⁡
(

x
j

)

)

.

6. The method of claim 1 , wherein using a predefined dominance filter to select a first subset of individuals from the candidate pool database comprises selecting from the first subset of individuals, individuals from the pool of candidate individuals that, in accordance with the predefined dominance filter, are not dominated by any other individuals in the pool.

7. The method of claim 6 , wherein the predefined dominance filter is defined such that a first individual dominates over a second individual if and only if
(a) a composite value of the first individual is better than a composite value of the second individual for at least one of the composite functions and
(b) for all others of the composite functions, the composite value of the first individual is not worse than the composite value of the second individual.

8. The computer-implemented method of claim 1 , wherein the provided problem is in one of the following domains: gaming strategies, 3D printing, stock trading, and robotics systems.

9. The computer-implemented method of

Assignees

• Cognizant Tech Solutions U S Corp
• Cognizant Tech Solutions U S Corporation

Inventors

• Shahrzad Hormoz
• Hodjat Babak
• Miikkulainen Risto

Classifications

• G06N3/126 Primary

  Evolutionary algorithms, e.g. genetic algorithms or genetic programming · CPC title

• G06N5/04

  Inference or reasoning models · CPC title

• G06N20/00 Primary

  Machine learning · CPC title