Systems and methods for multi-objective optimizations with decision variable perturbations

• US 10,474,953 B2
• Filed: 09/19/2016
• Issued: 11/12/2019
• Est. Priority Date: 09/19/2016
• Status: Active Grant

• Current Assignee: Aerospace Corporation
• Original Assignee: Aerospace Corporation
• Inventors: Thompson, Timothy Guy, Ferringer, Matthew Phillip
• Primary Examiner(s): Afshar, Kamran
• Assistant Examiner(s): Yousefi, Bahram
• Application Number:
  US15/268,840
• Publication Number:
  US 20180082198A1
• Time in Patent Office: 1,149 Days
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

Systems and methods are provided for providing an optimized solution to a multi-objective problem. Potential solutions may be generated from parent solutions to be evaluated according to multiple objectives of the multi-objective problem. If the potential solutions are infeasible, the potential solutions may be perturbed according to a perturbation model to bring the potential solution to feasibility, or at least a reduced level of constraints. The perturbation models may include a weight vector that indicates the amount of perturbation, such as in a forward and/or reverse direction, of decision variables of the potential solutions. In some cases, the perturbation models may be predetermined. In other cases, the perturbation models may be learned, such as based on training constraint data. Additionally, potential solutions may be generated in a secondary optimization where a constraint based optimization may be performed to drive to generating a feasible solution for further evaluation according to objective values.

Claims

1. A method, comprising:

determining, by one or more processors of a multi-objective heuristic system, a first chromosome and a second chromosome associated with a multi-objective optimization;

generating, by the one or more processors, a third chromosome by performing a genetic operation on the first chromosome and the second chromosome;

determining, by the one or more processors and based at least in part on one or more constraint models, that the third chromosome is infeasible, wherein the one or more constraint models provide an indication of a first gene of a constraint, a second gene that is a source of the constraints, and a magnitude of the constraint;

perturbing, by the one or more processors and based at least in part on a decision variable perturbation model, at least one of the first gene or the second gene;

perturbing, by the one or more processors and based at least in part on the perturbation of the one of the first gene and the second gene, the other of the first gene or the second gene to generate a perturbed third chromosome;

determining, by the one or more processors, that the perturbed third chromosome is feasible; and

providing, by the one or more processors, the perturbed third chromosome as a solution to the multi-objective optimization.

2. The method of claim 1, further comprising:

ranking, by the one or more processors and according to one or more constraint metrics, the third chromosome against a set of chromosomes; and

determining, by the one or more processors and based at least in part on the ranking, that the third chromosome is non-dominated.

3. The method of claim 1, wherein determining the first chromosome and the second chromosome associated with the multi-objective optimization further comprises performing a tournament selection process according to one or more objective values of the multi-objective optimization.

4. The method of claim 1, wherein generating the third chromosome by performing the genetic operation on the first chromosome and the second chromosome further comprises generating a prenatal chromosome and modifying the prenatal chromosome according to a weight vector to generate the third chromosome.

5. The method of claim 1, further comprising indicating, by at least one of the one or more processors to another of the one or more processor, that the third chromosome is feasible.

6. The method of claim 1, wherein providing the perturbed third chromosome as a solution to the multi-objective optimization comprises non-domination ranking of the perturbed third chromosome relative to a plurality of chromosomes according to a plurality of objectives.

7. The method of claim 1, wherein the perturbed third chromosome comprises a perturbed third gene, wherein a constraint depends on the value of the perturbed third gene and at least one of the first gene and the second gene.

8. The method of claim 1, further comprising revising the decision variable perturbation model based at least in part on the indication of the first gene, the second gene, and the magnitude of the constraint.

9. The method of claim 8, wherein the decision variable perturbation model comprises a weight vector having one or more weights corresponding to constraints resulting from one or more interdependencies between the first gene and the second gene.

10. The method of claim 8, wherein the decision variable perturbation model is further based at least in part on a plurality of weight vectors.

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;

determine a first chromosome and a second chromosome associated with a multi-objective optimization;

generate a third chromosome by performing a genetic operation on the first chromosome and the second chromosome;

determine, based at least in part on one or more constraint models, that the third chromosome is infeasible, wherein the one or more constraint models provide an indication of a first gene of a constraint, a second gene that is a source of the constraints, and a magnitude of the constraint;

perturb, based at least in part on a decision variable perturbation model, at least one of the first gene or the second gene;

perturb, by the one or more processors and based at least in part on the perturbation of the one of the first gene and the second gene, the other of the first gene or the second gene to generate a perturbed third chromosome;

determine that the perturbed third chromosome is feasible; and

provide the perturbed third chromosome as a 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:

rank, according to one or more constraint metrics, the third chromosome against a set of chromosomes; and

determine, based at least in part on the ranking, that the third chromosome is non-dominated.

13. The system of claim 11, wherein the at least one processor is configured to determine the first chromosome and the second chromosome associated with the multi-objective optimization further comprises the at least one processor is configured to execute the computer-executable instructions to perform a tournament selection process according to one or more objective values of the multi-objective optimization.

14. The system of claim 13, wherein the at least one processor is configured to generate the third chromosome by performing the genetic operation of the first chromosome and the second chromosome further comprises the at least one processor is configured to execute the computer-executable instructions to generate a prenatal chromosomes and modifying the prenatal chromosome according to a weight vector to generate the third chromosome.

15. The system of claim 11, wherein the at least one processor is further configured to execute the computer-executable instructions to indicate that the third chromosome is feasible.

16. The system of claim 11, wherein the at least one processor is configured to provide the perturbed third chromosome as a solution to the multi-objective optimization further comprises the at least one processor is configured to non-domination rank the perturbed third chromosome relative to a plurality of chromosomes according to a plurality of objectives.

17. The system of claim 11, wherein the first chromosome is at least one of:

(i) at or about a local minima in an objective space of the optimization problem;

(ii) at or about a local maxima in the objective space of the optimization problem;

or (i) at or about a saddle point in the objective space of the optimization problem.

18. The system of claim 11, wherein the at least one processor is configured to further execute the computer-executable instructions to revise the decision variable perturbation model based at least in part on the indication of the first gene, the second gene, and the magnitude of the constraint.

19. The system of claim 18, wherein the decision variable perturbation model comprises a weight vector having one or more weights corresponding to constraints resulting from one or more interdependencies between the first gene and the second gene.

20. The system of claim 18, wherein the decision variable perturbation model is further based at least in part on a plurality of weight vectors.