Systems and methods for multi-objective heuristics with conditional genes

• US 10,402,728 B2
• Filed: 04/08/2016
• Issued: 09/03/2019
• Est. Priority Date: 04/08/2016
• Status: Active Grant

• Current Assignee: Aerospace Corporation
• Original Assignee: Aerospace Corporation
• Inventors: Thompson, Timothy Guy, Ferringer, Matthew Phillip, Clifton, Ronald Scott, Horan, Catherine F., Hanifen, Kyle D.
• Primary Examiner(s): Lu, Kuen S
• Application Number:
  US15/094,521
• Publication Number:
  US 20170293839A1
• Time in Patent Office: 1,243 Days
• Field of Search: 706 13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: Y04S 10/50 Systems or methods supporting the power network operation or management, involving a certain degree of interaction with the load-side end user applications

Abstract

Systems and methods are provided to engage in multi-objective optimization where there may be potential solutions for evaluation (e.g., chromosomes) that each have one or more conditional genes. The value of each of the conditional genes in each of the chromosomes may be equivalent to one of a plurality of hidden genes in each of the chromosomes. The value of each of the conditional genes may be evaluated prior to determining objective values of each of the chromosomes. The objective values of each of the chromosomes may be used to evaluate the potential solutions embodied in the chromosomes and further drive to more optimized solutions. The use of the conditional genes in the chromosomes may reduce the amount of constraint violation checks that may need to be performed.

Claims

1. A method, comprising:

generating, by a heuristic system comprising one or more processors and based at least in part on a first chromosome and a second chromosome, a third chromosome, wherein the third chromosome comprises a determinant gene and a conditional gene, wherein a value of the conditional gene is based at least in part on a value of the determinant gene;

identifying, by the heuristic system, a first hidden gene and a second hidden gene corresponding to the conditional gene;

determining, by the heuristic system and based at least in part on the value of the determinant gene, that the value of the conditional gene is equal to a value of the first hidden gene;

determining, by the heuristic system and based at least in part on the value of the conditional gene, an objective value corresponding to an objective model;

determining, by the heuristic system and based at least in part on the objective value, that the third chromosome is non-dominated by a fourth chromosome; and

providing the third chromosome as a solution to a multi-objective optimization problem.

2. The method of claim 1, further comprising:

determining, by the heuristic system and based at least in part on the value of the conditional gene, a constraint value corresponding to an objective model; and

determining, by the heuristic system and based at least in part on the constraint value, that the third chromosome is feasible.

3. The method of claim 1, the objective value is a first objective value, and further comprising:

determining, by the heuristic system, a second objective value corresponding to the fourth chromosome; and

comparing, by the heuristic system, the first objective value to the second objective value, wherein determining that the third chromosome is non-dominated by the fourth chromosome is based at least in part on the comparing.

4. The method of claim 1, wherein the conditional gene is a first conditional gene, and wherein generating the third chromosome comprises performing a cross-over function between the first chromosome and the second chromosome, wherein the first chromosome has a third hidden gene and a fourth hidden gene corresponding a second conditional gene, the second conditional gene of the first chromosome corresponding to the first conditional gene of the third chromosome.

5. The method of claim 1, wherein generating the third chromosome comprises performing a mutation function, wherein at least one of the first hidden gene and the second hidden gene is mutated.

6. The method of claim 1, wherein the first hidden gene corresponds to a first range of values of the determinant gene, and wherein the second hidden gene corresponds to a second range of values of the determinant gene.

7. The method of claim 1, wherein the first hidden gene has a first allowable range of values and the second hidden gene has a second allowable range of values, wherein the first allowable range and the second allowable range are at least partially non-overlapping.

8. The method of claim 1, wherein the determinant gene is a first determinant gene, and wherein the first determinant gene has a value equal to one of a value of a third hidden gene or a fourth hidden gene based at least in part on a second determinant gene.

9. The method of claim 1, wherein the conditional gene is a first conditional gene, and wherein the third chromosome has a second conditional gene, a third hidden gene corresponding to the second conditional gene, a fourth hidden gene corresponding to the second conditional gene, and a fifth hidden gene corresponding to the second conditional gene, wherein a value of the second conditional gene is based at least in part on a set of rules and a set of at least one determinant genes.

10. The method of claim 9, wherein the objective value is based at least in part on the second conditional gene.

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;

generate, based at least in part on a first chromosome and a second chromosome, a third chromosome, wherein the third chromosome comprises a determinant gene and a conditional gene, wherein a value of the conditional gene is based at least in part on a value of the determinant gene;

identify a first hidden gene and a second hidden gene corresponding to the conditional gene;

determine, based at least in part on the value of the determinant gene, that the value of the conditional gene is equal to a value of the first hidden gene;

determine, based at least in part on the value of the conditional gene an objective value corresponding to an objective model;

determine, based at least in part on the objective value, that the third chromosome is non-dominated by a fourth chromosome; and

provide the third chromosome as a solution to a multi-objective optimization problem.

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

determine, based at least in part on the value of the conditional gene, a constraint value corresponding to an objective model; and

determine, based at least in part on the constraint value, that the third chromosome is feasible.

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

determine a second objective value corresponding to the fourth chromosome; and

compare the first objective value to the second objective value, wherein determining that the third chromosome is non-dominated by the fourth chromosome is based at least in part on the comparing.

14. The system of claim 11, wherein the conditional gene is a first conditional gene, and wherein the at least one processor configured to generate the third chromosome comprises the at least one processor configured to perform a cross-over function between the first chromosome and the second chromosome, wherein the first chromosome has a third hidden gene and a fourth hidden gene corresponding a second conditional gene, the second conditional gene of the first chromosome corresponding to the first conditional gene of the third chromosome.

15. The system of claim 11, wherein the at least one processor configured to generate the third chromosome comprises performing a mutation function, wherein at least one of the first hidden gene and the second hidden gene is mutated.

16. The system of claim 11, wherein the first hidden gene corresponds to a first range of values of the determinant gene, and wherein the second hidden gene corresponds to a second range of values of the determinant gene.

17. The system of claim 11, wherein the first hidden gene has a first allowable range of values and the second hidden gene has a second allowable range of values, wherein the first allowable range and the second allowable range are at least partially non-overlapping.

18. The system of claim 11, wherein the determinant gene is a first determinant gene, and wherein the first determinant gene has a value equal to one of a value of a third hidden gene or a fourth hidden gene based at least in part on a second determinant gene.

19. The system of claim 11, wherein the conditional gene is a first conditional gene, and wherein the third chromosome has a second conditional gene, a third hidden gene corresponding to the second conditional gene, a fourth hidden gene corresponding to the second conditional gene, and a fifth hidden gene corresponding to the second conditional gene, wherein a value of the second conditional gene is based at least in part on a set of rules and a set of at least one determinant genes.

20. The system of claim 19, wherein the objective value is based at least in part on the second conditional gene.