Systems and Methods for Multi-Objective Optimizations with Objective Space Mapping

Patent metadata

Field	Value
Publication number	US-2018082209-A1
Application number	US-201615267528-A
Country	US
Kind code	A1
Filing date	Sep 16, 2016
Priority date	Sep 16, 2016
Publication date	Mar 22, 2018
Grant date	—

Abstract

Systems and methods are provided for operating to an initial optimized baseline solution to a multi-objective problem. As the initial optimized baseline solution is determined, some regions, such as local or global maxima, minima, and/or saddle points in the objective space may be mapped. The mapping may be performed by storing mesh chromosomes corresponding to some of the features (e.g., extrema, saddle points, etc.) in the objective space along with the location of those chromosomes within the objective space (e.g., objective values corresponding to each of the objectives). The mesh chromosome may be used in subsequent re-optimization problems, such as with reformulation. Although in a re-optimization the objectives, decision variables, and or objective/constraint models may change, the mesh chromosomes may still provide information and direction for more quickly and/or with reduced resources converge on a re-optimized solution.

First claim

That which is claimed:

1 . A method, comprising:
identifying, by one or more processors of a multi-objective heuristic system, a plurality of chromosomes, wherein the plurality of chromosomes are associated with an optimization problem; identifying, by the one or more processors, one or more mesh objectives; ranking, by the one or more processors and according to the one or more mesh objectives, the plurality of chromosomes; determining, by the one or more processors and based at least in part on the ranking, that a first chromosome among the plurality of chromosomes is mesh non-dominated according to the one or more mesh objectives; and providing, by the one or more processors, the first chromosome as a mesh chromosome.

2 . The method of claim 1 , further comprising:
identifying, by the one or more processors, a plurality of objectives; ranking, by the one or more processors and according to the plurality of objectives, the plurality of chromosomes; and determining, by the one or more processors and based at least in part on the ranking, that a second chromosome among the plurality of chromosomes is mesh non-dominated according to the plurality of objectives, wherein the first chromosome and the second chromosome are different chromosomes.

3 . The method of claim 1 , further comprising:
determining, by the one or more processors, a second chromosome based at least in part on the first chromosome, wherein the second chromosome comprises a potential mesh chromosome; determining, by the one or more processors, one or more mesh objective values for the second chromosome; identifying, by the one or more processors and based at least in part on a second ranking, that the second chromosome is mesh non-dominated; and providing, by the one or more processors, the second chromosome as a second mesh chromosome.

4 . The method of claim 1 , wherein the one or more mesh objective comprises a minimization of an absolute value of a slope of one of the objectives of the optimization problem.

5 . The method of claim 1 , wherein determining that the first chromosome among the plurality of chromosomes is mesh non-dominated according to the one or more mesh objectives comprises determining that the first chromosome outperforms the other of the plurality of chromosomes according to a value corresponding to the first chromosome and associated with the one or more mesh objectives.

6 . The method of claim 1 , wherein determining that the first chromosome among the plurality of chromosomes is mesh non-dominated according to the one or more mesh objectives comprises comparing a first value corresponding to the first chromosome and the one or more mesh objectives to a second value corresponding to a chromosome stored in a mesh archive.

7 . The method of claim 1 , 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 (iii) at or about a saddle point in the objective space of the optimization problem, wherein the first chromosome defines a boundary of a feature in an objective space of the optimization problem.

8 . The method of claim 1 , optimization problem is a first optimization problem, and wherein the method further comprises:
determining, by the one or more processors, that a second optimization problem is to be performed; and generating, by the one or more processors and based at least in part on the first chromosome, a second chromosome to be used in a starting population of chromosomes for the second optimization problem.

9 . The method of claim 8 , wherein the second chromosome comprises a different set of decision variables relative to the first chromosome.

10 . The method of claim 8 , further comprising generating a third chromosome to be evaluated in the second optimization problem based at least in part on one or more chromosomes stored in a mesh archive.

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 plurality of chromosomes, wherein the plurality of chromosomes are associated with an optimization problem; identify one or more mesh objectives; rank, according to the one or more mesh objectives, the plurality of chromosomes; determine, based at least in part on the ranking, that a first chromosome among the plurality of chromosomes is mesh non-dominated according to the one or more mesh objectives; and provide the first chromosome as a mesh chromosome.

12 . The system of claim 11 , wherein the at least one processor is further configured to execute the computer-executable instructions to:
identify a plurality of objectives; rank, according to the plurality of objectives, the plurality of chromosomes; and determine, based at least in part on the ranking, that a second chromosome among the plurality of chromosomes is mesh non-dominated according to the plurality of objectives, wherein the first chromosome and the second chromosome are different chromosomes.

13 . The system of claim 11 , wherein the at least one processor is configured to:
determine a second chromosome based at least in part on the first chromosome, wherein the second chromosome comprises a potential mesh chromosome; determine one or more mesh objective values for the second chromosome; identify, based at least in part on a second ranking, that the second chromosome is mesh non-dominated; and provide the second chromosome as a second mesh chromosome.

14 . The system of claim 11 , wherein the one or more mesh objective comprises a minimization of an absolute value of a slope of one of the objectives of the optimization problem.

15 . The system of claim 11 , wherein the at least one processor is configured to determine that the first chromosome among the plurality of chromosomes is mesh non-dominated according to the one or more mesh objectives further comprises the at least one processor is configured to execute the computer-executable instructions to determine that the first chromosome outperforms the other of the plurality of chromosomes according to a value corresponding to the first chromosome and associated with the one or more mesh objectives.

16 . The system of claim 11 , wherein the at least one processor is configured to determine that the first chromosome among the plurality of chromosomes is mesh non-dominated according to the one or more mesh objectives further comprises the at least one processor is configured to execute the computer-executable instructions to compare a first value corresponding to the first chromosome and the one or more mesh objectives to a second value corresponding to a chromosome stored in a mesh archive.

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 (iii) at or about a saddle point in the objective space of the optimization problem, wherein the first chromosome defines a boundary of a feature in an 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:
determine that a second optimization problem is to be perfo

Assignees

• Aerospace Corp

Inventors

• Thompson Timothy Guy

Classifications

• G06N99/005 Primary

  Physics · mapped topic

• G06N5/003

  Physics · mapped topic

• G06N3/126 Primary

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