Genetic algorithm control arrangement for massively parallel computer
First Claim
Patent Images
1. A genetic algorithm system comprising:
- A. a processor array comprising a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes;
B. a control subsystem comprising;
i. a genome generation portion for enabling the processing nodes to a plurality of genomes distributed among the processing nodes;
ii. an evaluation score generation control portion for enabling said processing nodes to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome, said evaluation score generation control portion including;
(a) an evaluation score array generation control portion for enabling said processing nodes to establish an evaluation score array having a plurality of evaluation score entries each associated with a genome,(b) an evaluation score control portion for enabling the processing nodes to, in parallel, perform evaluation operations in connection with each of their respective genomes to generate an evaluation score and for storing the evaluation score in the evaluation score array entry associated therewith;
iii. a threshold score generation control portion for enabling said processing nodes to generate a threshold value in response to the evaluation scores for the respective genomes, said threshold score generation control portion comprising;
(a) a sort control portion for enabling the processing nodes to generate a sorted evaluation score array comprising a plurality of sorted evaluation score entries in which the evaluation scores from the evaluation score array are in stored order;
(b) a threshold identifier for enabling the processing nodes to identify a sorted evaluation score entry in response to a reaper percentage value, the evaluation score in the identified sorted evaluation score entry comprising the threshold value;
iv. a surviving genome control portion for enabling said processing nodes to identify from the genomes, surviving genomes in response to each genome'"'"'s evaluation score and the threshold value;
v. a surviving genome propagation control portion for enabling said processing nodes to, in messages transmitted over the interconnection network, duplicate the surviving genomes as a function of their respective evaluation scores and, in messages transmitted over the interconnection network;
vi. a genome mating control portion for enabling said processing nodes to perform a random mating operation in connection with surviving genomes and the original genomes to generate a plurality of mated genomes for use along with the surviving genomes as genomes in a subsequent iteration; and
vii. an iteration control portion for enabling said genome array establishment portion, said evaluation score generation control portion, said threshold score generation control portion, said surviving genome propagation control portion and said genome mating control portion, to control said processing nodes in a series of iterations, the mated genomes and surviving genomes generated during each iteration being used as genomes for the subsequent iteration.
2 Assignments
0 Petitions
Accused Products
Abstract
A genetic algorithm arrangement comprising a processor array controlled by a control arrangement through a number of iterations. The processor array comprises a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes. In accordance with the control arrangement, the processing nodes are first enabled to establish a genome array comprising a plurality of entries, each processing node having a selected number of entries, each entry receiving a genome. The processing nodes are then enabled to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome. The processing nodes are enabled to generate a threshold value in response to the evaluations for the respective genomes. Surviving genomes are then identified by the processing nodes as those genomes in respective portions of the genome array response to the threshold value. The processing nodes then are enabled to propagate the surviving genomes through the entries of the genome array as a function of their respective evaluation scores. The control portion then enables the processing nodes perform a mating operation in connection with a genome in each entry of the genome array and a genome in a respective randomly-selected entry of the genome array. The control portion enables the processing nodes to perform these operations through a series of iterations.
24 Citations
53 Claims
-
1. A genetic algorithm system comprising:
-
A. a processor array comprising a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes; B. a control subsystem comprising; i. a genome generation portion for enabling the processing nodes to a plurality of genomes distributed among the processing nodes; ii. an evaluation score generation control portion for enabling said processing nodes to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome, said evaluation score generation control portion including; (a) an evaluation score array generation control portion for enabling said processing nodes to establish an evaluation score array having a plurality of evaluation score entries each associated with a genome, (b) an evaluation score control portion for enabling the processing nodes to, in parallel, perform evaluation operations in connection with each of their respective genomes to generate an evaluation score and for storing the evaluation score in the evaluation score array entry associated therewith; iii. a threshold score generation control portion for enabling said processing nodes to generate a threshold value in response to the evaluation scores for the respective genomes, said threshold score generation control portion comprising; (a) a sort control portion for enabling the processing nodes to generate a sorted evaluation score array comprising a plurality of sorted evaluation score entries in which the evaluation scores from the evaluation score array are in stored order; (b) a threshold identifier for enabling the processing nodes to identify a sorted evaluation score entry in response to a reaper percentage value, the evaluation score in the identified sorted evaluation score entry comprising the threshold value; iv. a surviving genome control portion for enabling said processing nodes to identify from the genomes, surviving genomes in response to each genome'"'"'s evaluation score and the threshold value; v. a surviving genome propagation control portion for enabling said processing nodes to, in messages transmitted over the interconnection network, duplicate the surviving genomes as a function of their respective evaluation scores and, in messages transmitted over the interconnection network; vi. a genome mating control portion for enabling said processing nodes to perform a random mating operation in connection with surviving genomes and the original genomes to generate a plurality of mated genomes for use along with the surviving genomes as genomes in a subsequent iteration; and vii. an iteration control portion for enabling said genome array establishment portion, said evaluation score generation control portion, said threshold score generation control portion, said surviving genome propagation control portion and said genome mating control portion, to control said processing nodes in a series of iterations, the mated genomes and surviving genomes generated during each iteration being used as genomes for the subsequent iteration. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A genetic algorithm method for controlling a processor array comprising a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes, the method comprising the steps of
i. enabling the processing nodes to a plurality of genomes distributed among the processing nodes; -
ii. enabling said processing nodes to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome; iii. enabling said processing nodes to generate a threshold value in response to the evaluation scores for the respective genomes; iv. enabling said processing nodes to identify from the genomes, surviving genomes in response to each genome'"'"'s evaluation score and the threshold value, the surviving genome control step including the steps of; A. enabling said processing nodes to generate an alive flag array comprising a plurality of flags each associated with a genome; B. enabling said processing nodes to compare the evaluation scores associated with the genomes maintained by the respective processing nodes to the threshold value to identify surviving genomes; and C. enabling the processing nodes to condition the alive flags in response to the comparison; v. enabling said processing nodes to, in messages transmitted over the interconnection network, duplicate the surviving genomes as a function of their respective evaluation scores and, in messages transmitted over the interconnection network; vi. enabling said processing nodes to perform a random mating operation in connection with surviving genomes and the original genomes to generate a plurality of mated genomes for use along with the surviving genomes as genomes in a subsequent iteration; vii. enabling said genome array establishment portion, said evaluation score generation control portion, said threshold score generation control portion, said surviving genome propagation control portion and said genome mating control portion, to control said processing nodes in a series of iterations, the mated genomes and surviving genomes generated during each iteration being used as genomes for the subsequent iteration. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
-
-
32. A genetic algorithm system comprising:
-
A. a processor array comprising a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes; B. a control subsystem comprising; i. a genome generation portion for enabling the processing nodes to a plurality of genomes distributed among the processing nodes; ii. an evaluation score generation control portion for enabling said processing nodes to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome; iii. a threshold score generation control portion for enabling said processing nodes to generate a threshold value in response to the evaluation scores for the respective genomes; iv. a surviving genome control portion for enabling said processing nodes to identify from the genomes, surviving genomes in response to each genome'"'"'s evaluation score and the threshold value; v. a surviving genome propagation control portion for enabling said processing nodes to, in messages transmitted over the interconnection network, duplicate the surviving genomes in relation to a comparison between their respective evaluation scores and said threshold value, in messages transmitted over the interconnection network;
the surviving genome control portion including(a) an alive flag array generator for enabling said processing nodes to generate an alive flag array comprising a plurality of flags each associated with a genome; (b) a comparator for enabling said processing nodes to compare the evaluation scores associated with the genomes maintained by the respective processing nodes to the threshold value to identify surviving genomes; and (c) an alive flag conditioner for enabling the processing nodes to condition the alive flags in response to the comparison; vi. a genome mating control portion for enabling said processing nodes to perform a random mating operation in connection with surviving genomes and the original genomes to generate a plurality of mated genomes for use along with the surviving genomes as genomes in a subsequent iteration; and vii. an iteration control portion for enabling said genome array establishment portion, said evaluation score generation control portion, said threshold score generation control portion, said surviving genome propagation control portion and said genome mating control portion, to control said processing nodes in a series of iterations, the mated genomes and surviving genomes generated during each iteration being used as genomes for the subsequent iteration. - View Dependent Claims (33, 34, 35, 36, 37, 38, 39, 40)
-
-
41. A genetic algorithm system comprising:
-
A. a processor array comprising a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes; B. a control subsystem comprising; i. a genome generation portion for enabling the processing nodes to a plurality of genomes distributed among the processing nodes; ii. an evaluation score generation control portion for enabling said processing nodes to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome; iii. a threshold score generation control portion for enabling said processing nodes to generate a threshold value in response to the evaluation scores for the respective genomes; iv. a surviving genome control portion for enabling said processing nodes to identify from the genomes, surviving genomes in response to each genome'"'"'s evaluation score and the threshold value; v. a surviving genome propagation control portion for enabling said processing nodes to, in messages transmitted over the interconnection network, duplicate the surviving genomes as a function of their respective evaluation scores and, in messages transmitted over the interconnection network, the surviving genome propagation control portion enabling said processing nodes to (a) generate a surviving genome array including a number of entries each containing a copy of a surviving genome, and (b) a number of copies of each surviving genome in relation to its evaluation score and a value corresponding to the sum of normalized evaluation scores for the surviving genomes, for each surviving genome the normalized evaluation score corresponds to the difference between the surviving genome'"'"'s evaluation score and the threshold value, the surviving genome copies being distributed among the processing nodes; vi. a genome mating control portion for enabling said processing nodes to perform a random mating operation in connection with surviving genomes and the original genomes to generate a plurality of mated genomes for use along with the surviving genomes as genomes in a subsequent iteration;
the genome mating control portion includingA. a genome distribution element for enabling the processing nodes to randomly distribute said genomes thereamong said processing nodes in messages transmitted over the interconnection network; B. a mating operation control element for enabling the processing nodes to perform a mating operation between genomes and the surviving genome copies to generate mated genomes, the genome mating control portion enabling the processing nodes to maintain at least some surviving genome copies in an unmated condition; and vii. an iteration control portion for enabling said genome array establishment portion, said evaluation score generation control portion, said threshold score generation control portion, said surviving genome propagation control portion and said genome mating control portion, to control said processing nodes in a series of iterations, the mated genomes and surviving genomes generated during each iteration being used as genomes for the subsequent iteration. - View Dependent Claims (42, 43)
-
-
44. A genetic algorithm system comprising:
-
A. a processor array comprising a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes; B. a control subsystem comprising; i. a genome generation portion for enabling the processing nodes to a plurality of genomes distributed among the processing nodes; ii. an evaluation score generation control portion for enabling said processing nodes to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome; iii. a threshold score generation control portion for enabling said processing nodes to generate a threshold value in response to the evaluation scores for the respective genomes; iv. a surviving genome control portion for enabling said processing nodes to identify from the genomes, surviving genomes in response to each genome'"'"'s evaluation score and the threshold value; v. a surviving genome propagation control portion for enabling said processing nodes to, in messages transmitted over the interconnection network, duplicate the surviving genomes as a function of their respective evaluation scores and, in messages transmitted over the interconnection network, the surviving genome propagation control portion enabling said processing nodes to (a) generate a surviving genome array including a number of entries each containing a copy of a surviving genome, and (b) a number of copies of each surviving genome in relation to its evaluation score and a value corresponding to the sum of normalized evaluation scores for the surviving genomes, for each surviving genome the normalized evaluation score corresponds to the difference between the surviving genome'"'"'s evaluation score and the threshold value, the surviving genome copies are distributed among the processing nodes; vi. a genome mating control portion for enabling said processing nodes to perform a random mating operation in connection with surviving genomes and the original genomes to generate a plurality of mated genomes for use along with the surviving genomes as genomes in a subsequent iteration;
the genome mating control portion includingA. a genome distribution element for enabling the processing nodes to randomly distribute said genomes thereamong said processing nodes in messages transmitted over the interconnection network; B. a mating operation control element for enabling the processing nodes to perform a mating operation between genomes and the surviving genome copies to generate mated genomes, C. a mated genome distribution control element for enabling the processing nodes to randomly distribute the mated genomes among the processing nodes for use as genomes during a subsequent iteration; and vii. an iteration control portion for enabling said genome array establishment portion, said evaluation score generation control portion, said threshold score generation control portion, said surviving genome propagation control portion and said genome mating control portion, to control said processing nodes in a series of iterations, the mated genomes and surviving genomes generated during each iteration being used as genomes for the subsequent iteration. - View Dependent Claims (45, 46)
-
-
47. A genetic algorithm method for controlling a processor array comprising a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes, the method comprising the steps of
i. enabling the processing nodes to a plurality of genomes distributed among the processing nodes; -
ii. enabling said processing nodes to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome, said evaluation score generation step including the steps of; A. enabling said processing nodes to establish an evaluation score array having a plurality of evaluation score entries each associated with a genome, B. enabling the processing nodes to, in parallel, perform evaluation operations in connection with each of their respective genomes to generate an evaluation score and for storing the evaluation score in the evaluation score array entry associated therewith; iii. enabling said processing nodes to generate a threshold value in response to the evaluation scores for the respective genomes, said threshold score generation control step including the steps of; A. enabling the processing nodes to generate a sorted evaluation score array comprising a plurality of sorted evaluation score entries in which the evaluation scores from the evaluation score array are in stored order; B. enabling the processing nodes to identify a sorted evaluation score entry in response to a reaper percentage value, the evaluation score in the identified sorted evaluation score entry comprising the threshold value; iv. enabling said processing nodes to identify from the genomes, surviving genomes in response to each genome'"'"'s evaluation score and the threshold value; v. enabling said processing nodes to, in messages transmitted over the interconnection network, duplicate the surviving genomes as a function of their respective evaluation scores and, in messages transmitted over the interconnection network; vi. enabling said processing nodes to perform a random mating operation in connection with surviving genomes and the original genomes to generate a plurality of mated genomes for use along with the surviving genomes as genomes in a subsequent iteration; vii. enabling said genome array establishment portion, said evaluation score generation control portion, said threshold score generation control portion, said surviving genome propagation control portion and said genome mating control portion, to control said processing nodes in a series of iterations, the mated genomes and surviving genomes generated during each iteration being used as genomes for the subsequent iteration.
-
-
48. A genetic algorithm method for controlling a processor array comprising a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes, the method comprising the steps of
i. enabling the processing nodes to a plurality of genomes distributed among the processing nodes; -
ii. enabling said processing nodes to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome; iii. enabling said processing nodes to generate a threshold value in response to the evaluation scores for the respective genomes; iv. enabling said processing nodes to identify from the genomes, surviving genomes in response to each genome'"'"'s evaluation score and the threshold value; v. enabling said processing nodes to, in messages transmitted over the interconnection network, duplicate the surviving genomes as a function of their respective evaluation scores and, in messages transmitted over the interconnection network, the surviving genome propagation control step including the steps of; (a) enabling said processing nodes to generate a surviving genome array including a number of entries each containing a copy of a surviving genome, (b) enabling the processing nodes to generate a number of copies of each surviving genome in relation to its evaluation score and a value corresponding to the sum of normalized evaluation scores for the surviving genomes, the normalized evaluation score corresponding to the difference between the surviving genome'"'"'s evaluation score and the threshold value, the surviving genome copies being distributed among the processing nodes; vi. enabling said processing nodes to perform a random mating operation in connection with surviving genomes and the original genomes to generate a plurality of mated genomes for use along with the surviving genomes as genomes in a subsequent iteration, the genome mating control step including the steps of; (a) enabling the processing nodes to randomly distribute said genomes thereamong said processing nodes in messages transmitted over the interconnection network; (b) enabling the processing nodes to perform a mating operation between genomes and the surviving genome copies to generate mated genomes; (c) enabling the processing nodes to maintain at least some surviving genome copies in an unmated condition; vii. enabling said genome array establishment portion, said evaluation score generation control portion, said threshold score generation control portion, said surviving genome propagation control portion and said genome mating control portion, to control said processing nodes in a series of iterations, the mated genomes and surviving genomes generated during each iteration being used as genomes for the subsequent iteration. - View Dependent Claims (49, 50)
-
-
51. A genetic algorithm method for controlling a processor array comprising a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes, the method comprising the steps of
i. enabling the processing nodes to a plurality of genomes distributed among the processing nodes; -
ii. enabling said processing nodes to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome; iii. enabling said processing nodes to generate a threshold value in response to the evaluation scores for the respective genomes; iv. enabling said processing nodes to identify from the genomes, surviving genomes in response to each genome'"'"'s evaluation score and the threshold value; v. enabling said processing nodes to, in messages transmitted over the interconnection network, duplicate the surviving genomes as a function of their respective evaluation scores and, in messages transmitted over the interconnection network, the surviving genome propagation control step including the steps of; (a) enabling said processing nodes to generate a surviving genome array including a number of entries each containing a copy of a surviving genome, (b) enabling the processing nodes to generate a number of copies of each surviving genome in relation to its evaluation score and a value corresponding to the sum of normalized evaluation scores for the surviving genomes, the normalized evaluation score corresponding to the difference between the surviving genome'"'"'s evaluation score and the threshold value, the surviving genome copies being distributed among the processing nodes; vi. enabling said processing nodes to perform a random mating operation in connection with surviving genomes and the original genomes to generate a plurality of mated genomes for use along with the surviving genomes as genomes in a subsequent iteration, the genome mating control step including the steps of; (a) enabling the processing nodes to randomly distribute said genomes thereamong said processing nodes in messages transmitted over the interconnection network; (b) enabling the processing nodes to perform a mating operation between genomes and the surviving genome copies to generate mated genomes; and (c) enabling the processing nodes to randomly distribute the mated genomes among the processing nodes for use as genomes during a subsequent iteration; vii. enabling said genome array establishment portion, said evaluation score generation control portion, said threshold score generation control portion, said surviving genome propagation control portion and said genome mating control portion, to control said processing nodes in a series of iterations, the mated genomes and surviving genomes generated during each iteration being used as genomes for the subsequent iteration. - View Dependent Claims (52, 53)
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeOracle International Corporation (Oracle Corporation)
-
Original AssigneeThearling, Kurt
-
InventorsThearling, Kurt
-
Primary Examiner(s)Hafiz, Tariq R.
-
Application NumberUS08/856,401Time in Patent Office552 DaysField of Search703/12, 703/13, 703/77, 703/11US Class Current706/13CPC Class CodesG06N 3/126 Evolutionary algorithms, e....
