US 2012/0084314 A1Published application

Systems and methods for supporting restricted search in high-dimensional spaces

AssigneeThe Aerospace Corporation

InventorsMatthew Phillip Ferringer, Timothy Guy Thompson, Ronald Scott Clifton, Marc David DiPrinzio

Life of this patent

Estimating the term…

Loading patent…

Abstract

Embodiments of the invention may provide systems and methods for supporting restricted search capabilities in high-dimensional spaces. These example restricted search capabilities may allow for an unbiased search that is simply restricted to those regions of interest to a decision maker. It will be appreciated that a restricted search does not mean that additional constraints, such as preference or biasing information, are utilized to reduce the search space into some feasible sub-space of the original optimization problem. Instead, the example restricted search may limit the search to a certain sub-space of the full multi-dimensional tradeoff space.

Claims20

Dependent claims

A method comprising:

determining a plurality of sub-dimensional subsets, wherein the plurality of sub-dimensional subsets collectively define a restricted search space for an unbiased optimization of a plurality of variables in accordance with a plurality of objectives, wherein the restricted search space is only a portion of a total search space defined from the plurality of objectives;
receiving a pair of chromosome data structures, wherein each parent chromosome data structure provides a plurality of genes representative of the plurality of variables, wherein each of the plurality of variables are permitted to evolve in value;
for each subset of the plurality of sub-dimensional subsets, the method further includes:
selecting the respective subset for competition;
determining a subset-winning chromosome data structure from the pair of chromosome data structures by considering at least one of (i) respective domination characteristics for respective ones of the pair of chromosome data structures based upon a competition between the pair of chromosome data structures, or (ii) respective diversity characteristics associated with respective ones of the pair of chromosome data structures;
accumulating a unit of measure for the subset-winning chromosome data structure, wherein an amount accumulated for the unit of measure varies depending upon a respective subset ranking previously assigned to the subset-winning chromosome data structure, the respective subset ranking determined by performing domination sorting, restricted to the selected subset, for an entire population of chromosome data structures that included the subset-winning chromosome data structure;
and
determining an overall winning chromosome data structure of the pair of chromosome data structures by at least comparing the respective accumulated unit of measure for each of the pair of chromosome data structures,
wherein the prior steps are performed by one or more computers.

6 more elements

A system, comprising:

at least one 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 plurality of sub-dimensional subsets, wherein the plurality of sub-dimensional subsets collectively define a restricted search space for an unbiased optimization of a plurality of variables in accordance with a plurality of objectives, wherein the restricted search space is only a portion of a total search space defined from the plurality of objectives;
receive a pair of chromosome data structures, wherein each parent chromosome data structure provides a plurality of genes representative of the plurality of variables, wherein each of the plurality of variables are permitted to evolve in value;
for each subset of the plurality of sub-dimensional subsets:
select the respective subset for competition;
determine a subset-winning chromosome data structure from the pair of chromosome data structures by considering at least one of (i) respective domination characteristics for respective ones of the pair of chromosome data structures based upon a competition between the pair of chromosome data structures, or (ii) respective diversity characteristics associated with respective ones of the pair of chromosome data structures;
accumulate a unit of measure for the subset-winning chromosome data structure, wherein an amount accumulated for the unit of measure varies depending upon a respective subset ranking previously assigned to the subset-winning chromosome data structure, the respective subset ranking determined by performing domination sorting, restricted to the selected subset, for an entire population of chromosome data structures that included the subset-winning chromosome data structure;
and
determine an overall winning chromosome data structure of the pair of chromosome data structures by at least comparing the respective accumulated unit of measure for each of the pair of chromosome data structures.

7 more elements

Dependencies are inferred from the claim text.