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

• US 10,387,779 B2
• Filed: 12/09/2015
• Issued: 08/20/2019
• Est. Priority Date: 12/09/2015
• Status: Active Grant

• Current Assignee: Aerospace Corporation
• Original Assignee: Aerospace Corporation
• Inventors: Thompson, Timothy Guy, Ferringer, Matthew Phillip
• Primary Examiner(s): Waldron, Scott A.
• Assistant Examiner(s): Garner, Casey R.
• Application Number:
  US14/963,870
• Publication Number:
  US 20170169353A1
• Time in Patent Office: 1,350 Days
• CPC Class Codes: G06N 3/086 using evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

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.

Claims

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 claim 11, wherein the at least one processor is further configured to execute the computer-executable instructions to:

identify a fourth chromosome;

determine that the fourth chromosome is soft infeasible;

identify a third constraint value corresponding to the second constraint and the fourth chromosome; and

compare the third constraint value to the second constraint value to determine that the first chromosome is not dominated by the fourth chromosome.

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

14. The system of claim 11, wherein the at least one processor is further configured to execute the computer-executable instructions to:

identify that the first chromosome and the fourth chromosome are in the same epsilon box;

perform an analysis to determine that both the first chromosome and the fourth chromosome are to be stored in an archive checkpoint, wherein the analysis comprises at least one of;

(i) a non-domination sorting between the first chromosome and the fourth chromosome, (ii) a determination of a Euclidean distance for each of the first chromosome and the fourth chromosome, (iii) a non-domination sorting between the first chromosome and the fourth chromosome using reduced sets of objective metrics, (iv) a determination of a best performing chromosome for each objective metric, or (v) a determination of the genetic diversity of the first chromosome and the fourth chromosome;

store, based at least in part on the analysis, both the first chromosome and the fourth chromosome in the archive checkpoint.

15. The system of claim 14, wherein the at least one processor is further configured to execute the computer-executable instructions to:

identify a fourth chromosome;

apply the first constraint model to the fourth chromosome to derive a third constraint value;

compare the third constraint value to the corresponding first threshold value to determine that the fourth chromosome violates the first constraint; and

indicate that the fourth chromosome is hard infeasible, wherein a tag of hard infeasible indicates that at least one hard constraint has been violated.

16. The system of claim 15, wherein the at least one processor is further configured to execute the computer-executable instructions to determine 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.

17. The system of claim 11, wherein the at least one processor is further configured to execute the computer-executable instructions to:

identify a fourth chromosome;

apply the first constraint model to the fourth chromosome to derive a third constraint value;

apply the second constraint model to the fourth chromosome to derive a fourth constraint value;

compare the third constraint value to the corresponding first threshold value to determine that the fourth chromosome does not violate the first constraint and compare the fourth constraint value to the corresponding second threshold value to determine that the fourth chromosome does not violate the second constraint; and

indicate that the fourth chromosome is feasible, wherein a tag of feasible indicates that the fourth chromosome does not violate any constraints.

18. The system of claim 17, wherein the at least one processor is further configured to execute the computer-executable instructions to determine 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.

19. The system of claim 17, wherein the at least one processor is further configured to execute the computer-executable instructions to determine a set of objective values by applying one or more objective models to the fourth chromosome.

20. The system of claim 19, wherein the set of objective values is a first set of objective values and wherein the at least one processor is further configured to:

identify that a fifth chromosome is feasible;

determine 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

determine that the fifth chromosome dominates the fourth chromosome, based at least in part on the first set of objective values and the second set of objective values.