IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0895310
(2010-09-30)
|
등록번호 |
US-8560472
(2013-10-15)
|
발명자
/ 주소 |
- Ferringer, Matthew Phillip
- Thompson, Timothy Guy
- Clifton, Ronald Scott
- DiPrinzio, Marc David
|
출원인 / 주소 |
- The Aerospace Corporation
|
대리인 / 주소 |
Sutherland Asbill & Brennan LLP
|
인용정보 |
피인용 횟수 :
2 인용 특허 :
6 |
초록
▼
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
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.
대표청구항
▼
1. 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 sea
1. 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 of the pair of chromosome data structures 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;incrementing 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 respective subset, for an entire population of chromosome data structures that included the subset-winning chromosome data structure; anddetermining an overall winning chromosome data structure of the pair of chromosome data structures by at least comparing a 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. 2. The method of claim 1, wherein the competition determines whether one of the pair of the chromosome data structures is dominated by the other one of the pair of chromosome data structures, wherein the competition is limited to the selected subset. 3. The method of claim 2, wherein: if one of the chromosome data structures in the pair is dominated by the other one in the pair, then the subset-winning chromosome data structure is the non-dominated one of the chromosome data structures in the pair. 4. The method of claim 2, wherein if none of the chromosome data structures in the pair is dominating, then utilizing the respective diversity characteristics to determine whether one of the chromosome data structures is more diverse, and if so, the subset-winning chromosome data structure is the more diverse one of the chromosome data structures in the pair, and if not, the subset-winning chromosome data structure is a randomly selected one of the chromosome data structures in the pair. 5. The method of claim 4, wherein the diversity characteristics are associated with crowding distance or spread. 6. The method of claim 1, wherein the unit of measure comprises points, wherein a scoring system assigns a respective amount of points based upon the respective subset ranking previously assigned to the subset-winning chromosome data structure, the scoring system assigning points in a non-linear manner. 7. The method of claim 1, wherein the pair of chromosome data structures is received from a parent population of chromosome data structures, wherein each chromosome data structure in the parent population is either (i) randomly generated, or (ii) obtained from another population of chromosome data structures that are epsilon non-dominated for at least one subset in a restricted portion of the plurality of sub-dimensional subsets. 8. The method of claim 7, further comprising: processing, via one or more evolutionary operators, the overall winning chromosome data structure to generate one or more child chromosome data structures that is included as part of a merged population that further includes at least a portion of the parent population; andassigning, for each chromosome data structure in the merged population, a respective domination rank associated with each subset of the plurality of sub-dimensional subsets, each respective domination rank indicating an extent to which a particular chromosome data structure is non-dominated with respect to other chromosome data structures in the merged population with respect to the sub-dimensional subset associated with the respective domination rank. 9. The method of claim 8, further comprising: determining a set of non-dominated chromosome data structures from the merged population, wherein each chromosome data structure in the set is non-dominated with respect to any other chromosome data structure in the merged population for at least one subset in accordance with the respective domination rank; andapplying epsilon non-domination sorting to the set of non-dominated chromosome data structures, wherein epsilon non-domination sorting comprises, for each subset: determining one or more epsilon spacing values,assigning an epsilon address for each chromosome data structure in the set, wherein each epsilon address is based at least in part on the one or more epsilon spacing values; andwhere two or more chromosome data structures are assigned a same epsilon address for a respective subset, retaining only one chromosome data structure of the two or more chromosome data structures having the same epsilon address. 10. The method of claim 1, wherein the plurality of sub-dimensional subsets are determined as a portion of a total number of subsets defined from the plurality of objectives. 11. 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 of the pair of chromosome data structures 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; increment 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; anddetermine an overall winning chromosome data structure of the pair of chromosome data structures by at least comparing a respective accumulated unit of measure for each of the pair of chromosome data structures. 12. The system of claim 11, wherein the competition determines whether one of the pair of the chromosome data structures is dominated by the other one of the pair of chromosome data structures, wherein the competition is limited to the selected subset. 13. The system of claim 12, wherein: if one of the chromosome data structures in the pair is dominated by the other one in the pair, then the subset-winning chromosome data structure is the non-dominated one of the chromosome data structures in the pair. 14. The system of claim 12, wherein if none of the chromosome data structures in the pair is dominating, then utilizing the respective diversity characteristics to determine whether one of the chromosome data structures is more diverse, and if so, the winning chromosome data structure is the more diverse one of the chromosome data structures in the pair, and if not, the subset-winning chromosome data structure is a randomly selected one of the chromosome data structures in the pair. 15. The system of claim 14, wherein the diversity characteristics are associated with crowding distance or spread. 16. The system of claim 11, wherein the unit of measure comprises points, wherein a scoring system assigns a respective amount of points based upon the respective subset ranking previously assigned to the subset-winning chromosome data structure, the scoring system assigning points in a non-linear manner. 17. The system of claim 11, wherein the pair of chromosome data structures is received from a parent population of chromosome data structures, wherein each chromosome data structure in the parent population is either (i) randomly generated, or (ii) obtained from another population of chromosome data structures that are epsilon non-dominated for at least one subset in a restricted portion of the plurality of sub-dimensional subsets. 18. The system of claim 17, wherein the at least one processor is further configured to execute the computer-executable instructions to: process, via one or more evolutionary operators, the overall winning chromosome data structure to generate one or more child chromosome data structures that is included as part of a merged population that further includes at least a portion of the parent population; andassign, for each chromosome data structure in the merged population, a respective domination rank associated with each subset of the plurality of sub-dimensional subsets, each respective domination rank indicating an extent to which a particular chromosome data structure is non-dominated with respect to other chromosome data structures in the merged population with respect to the sub-dimensional subset associated with the respective domination rank. 19. The system of claim 18, wherein the at least one processor is further configured to execute the computer-executable instructions to: determine a set of non-dominated chromosome data structures from the merged population, wherein each chromosome data structure in the set is non-dominated with respect to any other chromosome data structure in the merged population for at least one subset in accordance with the respective domination rank; andapply epsilon non-domination sorting to the set of non-dominated chromosome data structures, wherein epsilon non-domination sorting comprises, for each subset:determining one or more epsilon spacing values,assigning an epsilon address for each chromosome data structure in the set, wherein each epsilon address is based at least in part on the one or more epsilon spacing values; andwhere two or more chromosome data structures are assigned a same epsilon address for a respective subset, retaining only one chromosome data structure of the two or more chromosome data structures having the same epsilon address. 20. The system of claim 19, wherein subsequent to the epsilon non-domination sorting, the determined set of non-dominated chromosome data structures is included within a current archive population of chromosome data structures, wherein the current archive population is compared to a prior archive population to determine, for each subset, a change in a number of unique epsilon addresses associated with the respective chromosome data structures in each archive population, the prior archive population generated from a prior iteration of a job, wherein the change in the number of unique epsilon addresses for each subset is a factor in determining whether to terminate the job.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.