Systems and methods for generating feasible solutions from two parents for an evolutionary process
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-015/18
G06N-003/00
G06N-003/12
G06N-003/08
출원번호
US-0550858
(2009-08-31)
등록번호
US-8494988
(2013-07-23)
발명자
/ 주소
Ferringer, Matthew Phillip
Thompson, Timothy Guy
출원인 / 주소
The Aerospace Corporation
대리인 / 주소
Sutherland Asbill & Brennan LLP
인용정보
피인용 횟수 :
4인용 특허 :
7
초록▼
Systems and methods may include receiving a pair of parent chromosome data structures, where each parent chromosome data structure provides a plurality of genes representative of variables that are permitted to evolve; combining genes of the two parent chromosome data structures to generate at least
Systems and methods may include receiving a pair of parent chromosome data structures, where each parent chromosome data structure provides a plurality of genes representative of variables that are permitted to evolve; combining genes of the two parent chromosome data structures to generate at least one first child chromosome data structure; evaluating the at least one first child chromosome data structures according to a plurality of constraint functions to generate a respective plurality of constraint function values for each of the at least one first child chromosome data structure, where the constraint functions define constraints on a feasible solution set; determining whether any of the at least one first child chromosome data structure is within the feasible solution set.
대표청구항▼
1. A method, comprising: receiving, by a slave processor from at least one master processor, a pair of parent chromosome data structures, wherein each parent chromosome data structure provides a plurality of genes representative of variables that are permitted to evolve;identifying, by the slave pro
1. A method, comprising: receiving, by a slave processor from at least one master processor, a pair of parent chromosome data structures, wherein each parent chromosome data structure provides a plurality of genes representative of variables that are permitted to evolve;identifying, by the slave processor, at least one evolutionary operator for generating at least one child chromosome data structure;identifying, by the slave processor, a plurality of constraint functions for evaluating the feasibility of the at least one child chromosome data structures;determining, by the slave processor, at least one feasible chromosome data structure within a feasible solution set based at least in part on the pair of parent chromosome data structures, the at least one evolutionary operator, and the plurality of constraint functions; andtransmitting, by the slave processor to the at least one master processor, the at least one feasible chromosome data structure. 2. The method of claim 1, wherein determining at least one feasible chromosome data structure further comprises: combining, by the slave processor, genes of the pair of parent chromosome data structures according to the at least one evolutionary operator to generate at least one child chromosome data structure;evaluating, by the slave processor, the at least one child chromosome data structures according to the plurality of constraint functions to generate a respective plurality of constraint function values for each of the at least one child chromosome data structure; anddetermining, by the slave processor, whether each of the at least one child chromosome data structures is within the feasible solution set based upon the respective plurality of constraint function values and identifying any of the child data structures within the feasible solution set as the at least one feasible chromosome data structure,wherein the prior combining, evaluating, and determining are repeated until one or more of the child chromosome data structures is determined to be within the feasible solution set. 3. The method of claim 1, wherein the at least one evolutionary operator includes one or both of a crossover evolutionary operator or a mutation evolutionary operator. 4. The method of claim 1, wherein the transmitted feasible chromosome data structure is responsive to a request from the at least one master processor to generate a feasible solution. 5. The method of claim 1, wherein the pair of parent chromosome data structures is received in a chromosome bundle by the slave processor from the at least one master processor. 6. The method of claim 1, further comprising performing an evolutionary algorithm, by the one or more master processors, based at least in part on the at least one feasible data structure. 7. The method of claim 1, wherein determining at least one feasible chromosome data structure further comprises: generating, by the slave processor, a random secondary population of parent chromosome data structures;combining, by the slave processors, the random secondary population of parent chromosome data structures with the previously received pair of parent chromosome data structures to provide an input secondary population of parent chromosome data structures;selecting, by the slave processors, pairs of parent chromosome data structures from the input secondary population of parent chromosome data structures;applying, by the slave processors, at least one second evolutionary operator to genes of the selected pairs of parent chromosome data structures to generate a plurality of second child chromosome data structures;evaluating, by the slave processor, the plurality of second child chromosome data structures according to the plurality of constraint functions to generate a respective plurality of constraint function values for each second child chromosome data structures; anddetermining, by the slave processor, whether any of the plurality of second child chromosome data structures are within the feasible solution set based upon the respective plurality of constraint function values and identifying any of the plurality of second child data structures within the feasible solution set as the at least one feasible chromosome data structure, wherein if no feasible solution is determined, then identifying a portion of the plurality of second child chromosome data structures as an elite set of chromosome data structures, wherein the elite set of chromosome data structures is received as the input secondary population of parent chromosome data structures,wherein the selecting, applying, evaluating, and determining are iteratively performed until a second child chromosome data structure is determined to be within the feasible solution set. 8. The method of claim 7, wherein the constraint functions are associated with relationship constraints associated with two or more parameters of a chromosome data structure. 9. The method of claim 8, wherein the portion of the plurality of second child chromosome data structures are identified as an elite set of chromosome data structures by applying constraint non-domination sorting to the plurality of second chromosome data structures. 10. The method of claim 9, wherein a difference between the plurality of second child chromosome data structures and the elite set of chromosome data structures defines a non-elite set of chromosome data structures, and wherein constraint non-domination sorting comprises determining that the elite set of chromosome data structures is no worse than the non-elite set of chromosome data structures according to all of the plurality of constraint functions, and strictly better than the non-elite set of chromosome data structures according to at least one of the plurality of constraint functions. 11. The method of claim 10, wherein the pair of parent chromosome data structures is received in a chromosome bundle by the slave processor from the one or more master processors. 12. A system, comprising: a memory that stores computer-executable instructions;a processor configured to access the memory, wherein the processor is further configured to execute the computer-executable instructions to: receive a pair of parent chromosome data structures, wherein each parent chromosome data structure provides a plurality of genes representative of variables that are permitted to evolve;identify at least one evolutionary operator for generating at least one child chromosome data structure;identify a plurality of constraint functions for evaluating the feasibility of the at least one child chromosome data structures;determine at least one feasible chromosome data structure within a feasible solution set based at least in part on the pair of parent chromosome data structures, the at least one evolutionary operator, and the plurality of constraint functions;transmit the at least one feasible chromosome data structure. 13. The system of claim 12, wherein the processor is further configured to: combine genes of the pair of parent chromosome data structures according to the at least one evolutionary operator to generate at least one child chromosome data structure;evaluate the at least one child chromosome data structures according to the plurality of constraint functions to generate a respective plurality of constraint function values for each of the at least one child chromosome data structure; anddetermine whether each of the at least one child chromosome data structures is within the feasible solution set based upon the respective plurality of constraint function values and identifying any of the child data structures within the feasible solution set as the at least one feasible chromosome data structure,wherein the prior combining, evaluating, and determining are repeated until one or more of the child chromosome data structures is determined to be within the feasible solution set. 14. The system of claim 12, wherein the at least one evolutionary operator includes one or both of a crossover evolutionary operator or a mutation evolutionary operator. 15. The system of claim 12, wherein the transmitted feasible chromosome data structure is responsive to a request from the at least one master processor to generate a feasible solution. 16. The system of claim 12, wherein the pair of parent chromosome data structures is received in a chromosome bundle by the slave processor from the at least one master processor. 17. The system of claim 12, wherein the processor is further configured to perform an evolutionary algorithm, by the one or more master processors, based at least in part on the at least one feasible data structure. 18. The system of claim 12, wherein the processor configured to determine at least one feasible chromosome data structure comprises the processor further configured to: generate a random secondary population of parent chromosome data structures;combine the random secondary population of parent chromosome data structures with the previously received pair of parent chromosome data structures to provide an input secondary population of parent chromosome data structures;select pairs of parent chromosome data structures from the input secondary population of parent chromosome data structures;apply at least one second evolutionary operator to genes of the selected pairs of parent chromosome data structures to generate a plurality of second child chromosome data structures;evaluate the plurality of second child chromosome data structures according to the plurality of constraint functions to generate a respective plurality of constraint function values for each second child chromosome data structures; anddetermine whether any of the plurality of second child chromosome data structures are within the feasible solution set based upon the respective plurality of constraint function values and identifying any of the plurality of second child data structures within the feasible solution set as the at least one feasible chromosome data structure, wherein if no feasible solution is determined, then identifying a portion of the plurality of second child chromosome data structures as an elite set of chromosome data structures, wherein the elite set of chromosome data structures is received as the input secondary population of parent chromosome data structures,wherein the selecting, applying, evaluating, and determining are iteratively performed until a second child chromosome data structure is determined to be within the feasible solution set. 19. The system of claim 18, wherein the constraint functions are associated with relationship constraints associated with two or more parameters of a chromosome data structure. 20. The method of claim 19, wherein the portion of the plurality of second child chromosome data structures are identified as an elite set of chromosome data structures by applying constraint non-domination sorting to the plurality of second chromosome data structures.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (7)
Tolson Michael (Mill Valley CA), Image processing using genetic mutation of neural network parameters.
Ferringer, Matthew Phillip; Clifton, Ronald Scott; Thompson, Timothy Guy, Systems and methods for a core management system for parallel processing of an evolutionary algorithm.
Ferringer, Matthew Phillip; Clifton, Ronald Scott; Thompson, Timothy Guy, Systems and methods for parallel processing optimization for an evolutionary algorithm.
Ghaddar, Chahid Kamel, Method, apparatus, and computer program product for optimizing parameterized models using functional paradigm of spreadsheet software.
Thompson, Timothy Guy; Ferringer, Matthew Phillip; DiPrinzio, Marc David; Clifton, Ronald Scott, Systems and methods for optimizing satellite constellation deployment.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.