Systems and methods for multi-objective evolutionary algorithms with soft constraints

Patent metadata

Field	Value
Publication number	US-10387779-B2
Application number	US-201514963870-A
Country	US
Kind code	B2
Filing date	Dec 9, 2015
Priority date	Dec 9, 2015
Publication date	Aug 20, 2019
Grant date	Aug 20, 2019

Abstract

Systems and methods are provided to engage in multi-objective optimization where there may be one or more constraints. At least one of the constraints may be soft constraints, such that if a potential solution to the multi-objective optimization problem violates only soft constraint(s), then that potential solution may be allowed to persist in a population of potential solutions that may be used to propagate child potential solutions. Potential solutions that violate soft constraints may be tested for non-domination sorting against other potential solutions that violate soft constraints and based at least in part on values associated with the soft constraint violations.

First claim

That which is claimed:

1. A method, comprising:
identifying, by one or more processors, a first chromosome, wherein the first chromosome includes a plurality of decision variables to be optimized in a multi-objective optimization;
identifying, by the one or more processors, a first constraint model corresponding to a first constraint and a second constraint model corresponding to a second constraint;
identifying, by the one or more processors, the first constraint as a hard-constraint and the second constraint as a soft constraint;
applying, by the one or more processors, the first constraint model to the first chromosome to derive a first constraint value;
applying, by the one or more processors, the second constraint model to the first chromosome to derive a second constraint value;
comparing, by the one or more processors, the first constraint value to a corresponding first threshold value to determine that the first chromosome does not violate the first constraint;
comparing, by the one or more processors, the second constraint value to a corresponding second threshold value to determine that the first chromosome does violate the second constraint;
indicating, by the one or more processors, that the first chromosome is soft infeasible, wherein a tag of soft infeasible indicates that only soft constraints have been violated;
determining, based at least in part on the second constraint value, that the first chromosome is to be crossed-over with a second chromosome;
generating a third chromosome by crossing over the first chromosome with the second chromosome;
determining, based at least in part on the first constraint model and the second constraint model, that the third chromosome is feasible; and
providing the third chromosome as an optimized solution to the multi-objective optimization.

2. The method of claim 1 , further comprising:
identifying, by the one or more processors, a fourth chromosome;
determining, by the one or more processors, that the fourth chromosome is soft infeasible;
identifying, by the one or more processors, a third constraint value corresponding to the second constraint and the fourth chromosome; and
comparing, by the one or more processors, the third constraint value to the second constraint value,
determining, by the one or more processors and based at least in part on the comparison of the third constraint value to the second constraint value, that the first chromosome dominates the fourth chromosome.

3. The method of claim 2 , further comprising:
determining, by the one or more processors, a first set of objective values by applying one or more objective models to the first chromosome;
determining, by the one or more processors, a second set of objective values by applying the one or more objective models to the fourth chromosome,
wherein determining that the first chromosome dominates the fourth chromosome further comprises comparing the first set of objective values to the second set of objective values.

4. The method of claim 1 , wherein the first chromosome is stored in an archive checkpoint.

5. The method of claim 1 , further comprising:
identifying, by the one or more processors, a fourth chromosome;
applying, by the one or more processors, the first constraint model to the fourth chromosome to derive a third constraint value;
comparing, by the one or more processors, the third constraint value to the corresponding first threshold value to determine that the fourth chromosome violates the first constraint; and
indicating, by the one or more processors, that the fourth chromosome is hard infeasible, wherein a tag of hard infeasible indicates that at least one hard constraint has been violated.

6. The method of claim 5 , further comprising determining that the first chromosome dominates the fourth chromosome based at least in part on the soft infeasible tag of the first chromosome and the hard infeasible tag of the fourth chromosome.

7. The method of claim 1 , further comprising:
identifying, by the one or more processors, a fourth chromosome;
applying, by the one or more processors, the first constraint model to the fourth chromosome to derive a third constraint value;
applying, by the one or more processors, the second constraint model to the fourth chromosome to derive a fourth constraint value;
comparing, by the one or more processors, the third constraint value to the corresponding first threshold value to determine that the fourth chromosome does not violate the first constraint and comparing the fourth constraint value to the corresponding second threshold value to determine that the fourth chromosome does not violate the second constraint; and
indicating, by the one or more processors, that the fourth chromosome is feasible, wherein a tag of feasible indicates that the fourth chromosome does not violate any constraints.

8. The method of claim 7 , further comprising determining that the fourth chromosome dominates the first chromosome based at least in part on the soft infeasible tag of the first chromosome and the feasible tag of the second chromosome.

9. The method of claim 7 , further comprising:
determining, by the one or more processors, a set of objective values by applying one or more objective models to the fourth chromosome.

10. The method of claim 9 , wherein the set of objective values is a first set of objective values and further comprising:
identifying, by the one or more processors, that a fifth chromosome is feasible;
determining, by the one or more processors, a second set of objective values corresponding to the fifth chromosome based at least in part on applying the one or more objective models to the fifth chromosome; and
determining, by the one or more processors, that the fifth chromosome dominates the second chromosome, based at least in part on the first set of objective values and the fourth set of objective values.

11. A system, comprising:
a memory that stores computer-executable instructions;
at least one processor configured to access the memory, wherein the at least one processor is further configured to execute the computer-executable instructions to:
identify a first chromosome, wherein the first chromosome includes a plurality of decision variables to be optimized in a multi-objective optimization;
identify a first constraint model corresponding to a first constraint and a second constraint model corresponding to a second constraint;
identify the first constraint as a hard-constraint and the second constraint as a soft constraint;
apply the first constraint model to the first chromosome to derive a first constraint value;
apply the second constraint model to the first chromosome to derive a second constraint value;
compare the first constraint value to a corresponding first threshold value to determine that the first chromosome does not violate the first constraint;
compare the second constraint value to a corresponding second threshold value to determine that the first chromosome does violate the second constraint;
indicate that the first chromosome is soft infeasible, wherein a tag of soft infeasible indicates that only soft constraints have been violated;
determine, based at least in part on the second constraint value, that the first chromosome is to be crossed-over with a second chromosome;
generate a third chromosome by crossing over the first chromosome with the second chromosome;
determine, based at least in part on the first constraint model and the second constraint model, that the third chromosome is feasible; and
provide the third chromosome as an optimized solution to the multi-objective optimization.

12. The system of cla

Assignees

• Aerospace Corp

Inventors

• Thompson Timothy Guy
• Ferringer Matthew Phillip

Classifications

• G06N3/126 Primary

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

• G06N3/086

  using evolutionary algorithms, e.g. genetic algorithms or genetic programming · CPC title