Systems and methods for multi-objective heuristics with conditional genes

Patent metadata

Field	Value
Publication number	US-10402728-B2
Application number	US-201615094521-A
Country	US
Kind code	B2
Filing date	Apr 8, 2016
Priority date	Apr 8, 2016
Publication date	Sep 3, 2019
Grant date	Sep 3, 2019

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.

First claim

That which is claimed:

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 hidde

Assignees

• Aerospace Corp

Inventors

• Thompson Timothy Guy
• Ferringer Matthew Phillip
• Clifton Ronald Scott
• Horan Catherine F
• Hanifen Kyle D

Classifications

• G06N3/126 Primary

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

• Y04S10/54

  Cross-Sectional Technologies · mapped topic

• Y04S10/50

  Systems or methods supporting the power network operation or management, involving a certain degree of interaction with the load-side end user applications · CPC title