Systems and Methods for Multi-Objective Evolutionary Algorithms with Soft Constraints

Patent metadata

Field	Value
Publication number	US-2017169353-A1
Application number	US-201514963870-A
Country	US
Kind code	A1
Filing date	Dec 9, 2015
Priority date	Dec 9, 2015
Publication date	Jun 15, 2017
Grant date	—

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

1 . A method, comprising:
identifying, by one or more processors, a chromosome, wherein the 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; determining, by the one or more processors, that the first constraint is a hard-constraint and that the second constraint is a soft constraint; applying, by the one or more processors, the first constraint model to the chromosome to derive a first constraint value; applying, by the one or more processors, the second constraint model to the 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 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 chromosome does violate the second constraint; indicating, by the one or more processors, that the chromosome is soft infeasible, wherein a tag of soft infeasible indicates that only soft constraints have been violated; and indicating, by the one or more processors, the second constraint value of the chromosome.

2 . The method of claim 1 , wherein the chromosome is a first chromosome and further comprising:
identifying, by the one or more processors, a second chromosome; determining, by the one or more processors, that the second chromosome is soft infeasible; identifying, by the one or more processors, a third constraint value corresponding to the second constraint and the second 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 second chromosome.

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

4 . 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 second chromosome, wherein determining that the first chromosome dominates the second chromosome further comprises comparing the first set of objective values to the second set of objective values.

5 . The method of claim 1 , wherein the chromosome is a first chromosome and further comprising:
identifying, by the one or more processors, a second chromosome; applying, by the one or more processors, the first constraint model to the second 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 chromosome violates the first constraint; and indicating, by the one or more processors, that the second 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 second chromosome based at least in part on the soft infeasible tag of the first chromosome and the hard infeasible tag of the second chromosome.

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

8 . The method of claim 7 , further comprising determining that the first chromosome dominates the second 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 second 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 third chromosome is feasible; determining, by the one or more processors, a second set of objective values corresponding to the third chromosome based at least in part on applying the one or more objective models to the third chromosome; and determining, by the one or more processors, that the third chromosome dominates the second chromosome, based at least in part on the first set of objective values and the second 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 chromosome, wherein the 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;
determine that the first constraint is a hard-constraint and that the second constraint is a soft constraint;
apply the first constraint model to the chromosome to derive a first constraint value;
apply the second constraint model to the chromosome to derive a second constraint value;
compare the first constraint value to a corresponding first threshold value to determine that the chromosome does not violate the first constraint;
compare the second constraint value to a corresponding second threshold value to determine that the chromosome does violate the second constraint;
indicate that the chromosome is soft infeasible, wherein a tag of soft infeasible indicates that only soft constraints have been violated; and
indicate the second constraint value of the chromosome.

12 . The system of claim 11 , wherein the chromosome is a first chromosome and wherein the at least one processor is further configured to execute the computer-executable instructions to:
identify a second chromosome; determine that the second chromosome is soft infeasible; identify a third constraint value corresponding to the second constraint and the second chromosome; and compare the third constraint value to the second constraint value to determine that the first chromosome is not dominated by the second chromosome.

13 . The system of claim 12 , wherein the first chromosome is stored in an archive checkpoint.

14 . The system of claim 12 , wherein the at least one processor is fu

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

• G06N99/005 Primary

  Physics · mapped topic