Patent Publication Number: US-5839120-A

Title: Genetic algorithm control arrangement for massively parallel computer

Description:
This is a Continuation of application Ser. No. 08/159,336 filed on Nov. 30, 1993, now abandoned. 
    
    
     FIELD OF THE INVENTION 
     The invention relates generally to the field of parallel computer systems, and more particularly to genetic algorithm control arrangements for use with such systems. 
     BACKGROUND OF THE INVENTION 
     Developing computer programs and verifying them to be optimum has proven to be a difficult and arduous task for a number of classes of problems. Genetic algorithm methodologies have been developed to facilitate development of optimal solutions. In genetic algorithm methodologies, programs are represented by &#34;genomes,&#34; which, in a series of iterations, are evaluated (by execution of the respective programs represented thereby), selected (in accordance with some criteria related to execution, such as execution speed) and mated and mutated in a selected manner. The result at the end of each iteration represents a set of programs which, in turn, are evaluated during a subsequent iteration. In each iteration, characteristics of those genomes that are selected in the selection step survive to the next iteration, in a manner similar to survival of genetic traits from one generation to the next under Darwin&#39;s theory of natural selection. Genetic algorithm methodologies thus facilitate construction of what might be described as &#34;spaces&#34; of programs, which are searched for optimal programming solutions. 
     SUMMARY OF THE INVENTION 
     The invention provides a new and improved genetic algorithm control arrangement for a parallel computer system. 
     In brief summary, a genetic algorithm arrangement comprises a processor array controlled by a control arrangement. The processor array comprises a plurality of processing nodes interconnected by an interconnection network for transferring messages among the processing nodes. The control arrangement controls the processing nodes of the processor array through a series of iterations. Initially, a genome array establishment portion enables the processing nodes to establish a genome array comprising a plurality of entries, each processing node having a selected number of entries, each entry receiving a genome. An evaluation score generation control portion enables the processing nodes to perform an evaluation operation in connection with each genome to generate an evaluation score associated with each genome. A threshold score generation control portion enables the processing nodes to generate a threshold value in response to the evaluations for the respective genomes. A surviving genome control portion enables the processing nodes to identify as surviving genomes those genomes in respective portions of the genome array response to the threshold value. A surviving genome propagation control portion enables the processing nodes to propagate the surviving genomes through the entries of the genome array as a function of their respective evaluation scores. A genome mating control portion enables the processing nodes to 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. An iteration control portion enables the genome array establishment portion, the evaluation score generation control portion, the threshold score generation control portion, the surviving genome propagation control portion and the genome mating control portion, to control the processing nodes in a series of iterations. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     This invention is pointed out with particularity in the appended claims. The above and further advantages of this invention may be better understood by referring to the following description taken in conjunction with the accompanying drawings, in which: 
     FIG. 1 is a functional block diagram of a parallel computer system forming part of the invention; and 
     FIGS. 2A through 2F jointly comprise a flow diagram illustrating operations performed by the system depicted in FIG. 1 in connection with the invention. 
    
    
     DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT 
     Before describing the genetic algorithm arrangement, it would be helpful to describe the general structure of a parallel computer system forming part of the arrangement. FIG. 1 depicts a functional block diagram of a parallel computer system 10 forming part of the genetic algorithm arrangement. With reference to FIG. 1, the parallel computer system 10 includes a control processor 11 which transmits commands to a processor array 12, and specifically to a plurality of processing nodes 13(0) through 13(P)  generally identified by reference numeral 13(i)!, to control processing thereby. Each processing node 13(i) includes a processor 14(i) and a memory 15(i), with the memory 15(i) having a plurality of storage locations for storing data and instructions. The processor 14(i) of each processing node 13(i) performs processing operations as defined in the commands from the control processor 11 in connection with data stored in its respective memory 15(i). In performing the processing operations, the processor 14(i) may make use of the instructions stored in its associated memory 15(i). Depending on particular sequences of instructions used by the processors 14(i) for particular commands, the processing nodes 13(i) may be performing generally similar operations in response to a command, or they may perform diverse types of operations. 
     In connection with the processing operations enabled by the commands provided by the control processor 11, the processing nodes 13(i), and in particular the respective processors 14(i), may also generate messages for transmission over an interconnection network 16. Messages may contain data, thereby facilitating the transfer of data from one processing node, identified as a source processing node 13(s), to another processing node, identified as a destination processing node 13(d). The processing nodes 13(i) and the control processor 11 may also transmit messages to each other over the interconnection network 16 to thereby facilitate the transfer of data therebetween. Processing nodes 13(i) and control processor 11 may also transmit messages to facilitate synchronization of their various processing and message generation and transfer operations. 
     While the parallel computer system 10 depicted in FIG. 1 has been described as having a control processor 11 separate and apart from the processing nodes 13(i) of the processor array 12, it will be appreciated the system 10 will not necessarily require that the control processor 11 be physically a processor or element separate and apart from the processing nodes 13(i). One or more of the processing nodes 13(i) may, in addition to performing the operations of the processing nodes described above, in addition perform the functions of the control processor 11 described above. 
     The system 10 further includes a mass storage subsystem 17 which stores data for all of the processing nodes 13(i) and also for the control processor. Input/output commands from the control processor 11 enable the processing nodes 13(i) of processor array 12 and the mass storage subsystem 17 to cooperate to transfer data stored in the mass storage subsystem 17 through the interconnection network 16 to the processing nodes 13(i) for processing. Input/output commands also enable the processing nodes 13(i) and mass storage subsystem 17 to cooperate to transfer data from the processing nodes 13(i) to the mass storage subsystem for storage. 
     The genetic algorithm arrangement further includes a control arrangement for controlling the parallel computer system 10 to implement searching of program spaces using genetic algorithm methodologies. The operations performed by the system 10 in accordance with the genetic algorithm arrangement are depicted in flow charts contained in FIGS. 2A through 2F. The control arrangement enables the system 10 to perform a series of iterations to develop and search &#34;spaces&#34; of computer programs to obtain one or more programs which are deemed optimal. The control arrangement may enable the system to perform a number of iterations as specified by a user, or it may provide information to the user at the end of each selected number of iteration to enable the user to determine whether it should continue, or alternatively it may continue until it reaches some other selected termination criteria. 
     The genetic algorithm arrangement operates in connection with data in the form of &#34;genomes,&#34; which are data words of, for a particular computer program space, of a selected structure. The particular structure of a genome is determined by the particular application for which the computer programs are to be used. For a particular program space, each genome has a predetermined number of fields, in a predetermined order, with each field having a number of data bits. The detailed genome structures for program spaces are well known to those skilled in the art, and will not be described herein. 
     With this background, with reference to FIG. 2A, in accordance with the genetic algorithm arrangement an initial set of genomes are distributed to the processing nodes 13(i) (step 100). The initial set of genomes may be generated in a conventional manner. Generally, the genomes will be generated as random values. The processing nodes 13(i) collectively establish in their memories 15(i) a genome array that comprises a plurality of entries, with each entry in the genome array receiving and storing a genome. The entries of the genome array may be considered to be organized in a plurality of rows and a plurality of columns, with the number of columns corresponding to the number of processing nodes 13(i), and each column being associated with one processing node 13(i), that is, each processing node 13(i) having, in a series of successive storage locations in its memory 15(i), entries in the genome array. Preferably, the processing nodes 13(i) will all have generally the same number of genomes, and thus entries in the genome array, to provide for general balancing of the processing load among the processing nodes in the subsequent operations. The genome array has a particular predetermined &#34;shape&#34;, defined by the number of columns (corresponding to the number of processing nodes) and number of rows (corresponding to the number of genomes assigned to each processing node 13(i)). 
     After the processing nodes 13(i) receive the initial set of genomes, in accordance with the generic algorithm arrangement they, in parallel, perform an evaluation operation in connection with the genomes to generate an evaluation score for each genome in the genome array (step 101). In that operation, the parallel computer system 10 (FIG. 1) will process each of the programs represented by the respective genomes and develop a score in response to selected processing criteria in a conventional manner. For example, the processing criteria may relate to the time required to process the program represented by the genome. 
     After generating the evaluation scores for the genomes, the processing nodes 13(i) perform a series of steps 102 through 106 to generate a threshold evaluation score used to identify the genomes to survive to the next generation. Initially, the processing nodes 13(i) perform steps 102 through 104 to establish a sorted evaluation score array, having entries with the same structure and shape as the genome array, and to place the evaluation scores in order in the sorted evaluation score array according to their evaluation scores. In that operation, the entries in the column of the sorted evaluation score array maintained by processing node 13(x) will receive evaluation scores which are higher than the evaluation scores in the column maintained by processing node 13(y) if x&gt;y, and the evaluation scores in successive entries in each column are in numerical order. To place the evaluation scores in order, the processing nodes 13(i) initially determine a rank value for evaluation scores, which identifies for each evaluation score the evaluation score&#39;s ranking among the evaluation scores generated in step 101 (step 102). The processing nodes 13(i) then establish the sorted evaluation score array and generate messages which they transmit over the interconnection network 16 to place the evaluation scores in sorted order in the sorted evaluation score array (step 103). In generating each message, the processing nodes generate a destination address reflecting the rank value associated with the evaluation score to be transmitted in the message, and the shape designation. The resulting destination address will identify the processing node 13(i) to receive the message and the location of the entry in the receiving processing node&#39;s memory 15(i) to place the evaluation scores in sorted order. The processing nodes 13(i) then perform a send operation to transmit the messages over the interconnection network (step 104). 
     Following step 104, the evaluation scores are in sorted order. The control processor 11, or the processing nodes 13(i), in response to a reaper percentage identifying the percentage of genomes to survive to the next generation, generate a survival value that identifies the number of genomes to survive (step 105). Using the survival value and the shape designation of the sorted evaluation score array, an entry in the sorted evaluation score array is identified (step 106). That entry, plus the number of entries in the sorted evaluation score array having equal or higher evaluation scores, corresponds to the survival value, that is, the number of genomes to survive to the next generation, and thus the evaluation score in the identified entry is used as a threshold evaluation score value. 
     The threshold evaluation score value determined in step 106 is then broadcast to all of the processing nodes 13(i), and the processing nodes 13(i) perform a comparison operation to compare the threshold evaluation score with the evaluation scores of all of the genomes in their respective portion of the genome array. For each genome, the processing nodes 13(i) establish an &#34;alive&#34; flag and condition the flag in response to the result of the comparison operation (step 107). In response to a positive comparison in step 107, indicating that the genome&#39;s evaluation score had a selected relationship to the threshold evaluation score (such as if the evaluation score was greater than or equal to the threshold evaluation score), the processing node 13(i) will set the genome&#39;s alive flag, and otherwise it will clear the genome&#39;s alive flag. 
     Following step 107, the processing nodes 13(i) perform a series of steps 108 through 116 essentially to reproduce the surviving genomes in the genome array in weighted relation to their respective evaluation scores, in particular in weighted relation to the difference between their respective evaluation scores and the threshold score. In that operation, the processing nodes 13(i) initially reset to zero the evaluation score values that are associated with each of the genomes in the genome array which have a clear alive flag (step 108). The processing nodes 13(i) then decrement each respective genome&#39;s evaluation score by the threshold evaluation score (step 109). In that operation, the processing nodes 13(i) reset to zero those decremented threshold scores which are below zero, that is, the decremented evaluation scores associated with the genomes whose alive flags are clear. The processing nodes 13(i) then perform, in connection with the decremented evaluation scores, a &#34;reduce&#34; operation to generate a total score value, which is the sum of the decremented evaluation scores for all of the genomes (step 110) and a &#34;scan-with-add&#34; operation to generate a scan score value, which is a running sum of decremented evaluation scores for the genomes in the genome array up to, but not including, the particular genome (step 111). That is: 
     
         SSV(i+1)=SUM{DES gen(i)!}, where 
    
     &#34;SSV&#34; is the scan score value, &#34;DES&#34; is the decremented valuation score for the genome in entry gen(i), and &#34;SUM&#34; indicates the sum operator. (The &#34;reduce&#34; and &#34;scan-with-add&#34; operations are well known and will not be described herein.) The processing nodes 13(i) then establish a segment flag associated with each entry in the genome array, with all of the segment flags initially having a clear condition (step 112). 
     The processing nodes 13(i) then generate, for each genome which have set alive flags, that is, for each genome to survive to the next generation, an address value using the scan score value and the decremented evaluation score value associated with the genome, as well as the total score value and the number of genomes in the genome array (step 113). In that operation, for each genome, a processing node 13(i) determines the difference between the scan score value and the decremented score value for the genome, divides the difference by the total score value. Since the total number of genomes in the genome array in each generation will be the same, the processing node 13(i) multiplies the quotient by the number of genomes in the genome array, with the result being a function of the required address value. The address value is actually an offset value, which will be used to identify an entry in a second genome array, which has the same size and shape as the original genome array, but at different locations in the memories 15(i) of the processing nodes 13(i). Accordingly, each entry in the second genome array will have a corresponding entry in the original genome array, with the correspondence being defined by the respective offset values, from an array base, for the entry. 
     After generating the address values (step 113), the processing nodes 13(i) use the address values to identify entries in the original genome array whose segment flags are to be set (step 114). In addition, the processing nodes 13(i) generate, for each genome with a set alive flag, a message including the genome and a destination address, with the destination address being generated using the address value and the predetermined shape designation. The processing nodes 13(i) transmit the generated messages over the interconnection network 16 to transmit the surviving genomes to entries of the second genome array identified by the respective address values (step 115). 
     As noted above, each entry in the second genome array corresponds to an entry in the original genome array. As is evident, the entries in the second genome array which received genomes in step 115 correspond to the entries in the original genome array whose segment flags were set in step 114. Following step 115, the processing nodes 13(i) copy each genome from an entry in the second genome array into the corresponding entry of the original genome array, and also copies the genome into successive entries in the original genome array up to, but not including, the next higher entry whose segment flag is set. Since, for each genome in an entry gen(i), the starting entry gen(i+1) in the original genome array for the next genome in the array is based on the scan score value for the next genome gen(i+1), which scan score value in turn reflects the first genome&#39;s  that is, the genome in entry gen(i)! evaluation score value, the number of copies of the genome in the original genome array will be a function of its decremented evaluation score value. At the end of step 116, the genomes have been reproduced or propagated generally in proportion to their respective decremented evaluation scores. 
     Following step 116, the processing nodes 13(i) perform a series of steps 117 through 120 to use the genomes in the original genome array generate, for each such genome, a mating genome and to perform a mating operation, thereby to create a set of &#34;next-generation&#34; genomes for a subsequent iteration. It will be appreciated that, at this point, all of the genomes in the original genome array are either the original or a copy of the genomes selected to survive to the next generation. In those operations, the processing nodes 13(i) initially generates a random number for each genome in an entry in the original genome array (step 117) and generates a rank value for each of the random numbers to rank the numbers that were generated in step 117 (step 118). Each rank value is used to identify an entry in the second genome array to which a copy of the genome in the original genome array will be transmitted. Following step 118, for each entry in the original genome array, the processing nodes 13(i) generate an address using the rank values and the predetermined shape designation identifying an entry in the second genome array. Thereafter, the processing nodes 13(i) generate messages, which they transmit over the interconnection network 16, to send copies of the genomes into entries in the second genome array (step 119). Since the addresses are generated in response to rank values, which in turn are generated in response to random numbers, the genome copies are randomly distributed in the second genome array. 
     Thereafter, the processing nodes 13(i) perform a mating operation between the genome in each entry in the original genome array and the genome copy in the corresponding entry in the second genome array, except for the genomes in the entries of the original genome array whose segment flags are set (step 120). In the mating operation, for each genome and genome copy, the processing node 13(i) substitutes, for selected fields from the genome in the original genome array, corresponding fields from the genome copy. The selection is preferably made on a random basis, so that, for different genome/genome copy pairs from corresponding entries of the original genome array and the second genome array, diverse sets of fields from the genome copy will be substituted for corresponding fields of the respective genomes. Since no mating operation is performed in connection with the genomes in the entries of the original genome array whose segment flags are set, the genetic algorithm arrangement assures that at least one copy of each genome whose evaluation score exceeded the threshold evaluation score value will be preserved to the next generation. 
     Following step 120, the genomes constitute a subsequent generation, which may be used in a subsequent iteration. However, in one embodiment the genetic algorithm arrangement performs a series of steps 121 through 124 to randomize the locations of the various genomes in the original genome array, which can assist in randomizing processing loads among the processing nodes 13(i), when performing the evaluation step (step 101) in a subsequent iteration. In those operations, the processing nodes 13(i) generate a random number for each genome in the original genome array (step 121), generate a rank value in response to the random numbers (step 122), and generate messages for transmission over the interconnection network 16 using genomes and an address value generated in response to the rank value and the predetermined shape designations (step 123). The processing nodes 13(i) transmit the messages over the interconnection network 16 to reorder the genomes according to their respective random addresses. Thereafter, if a subsequent iteration is to be performed, the genetic algorithm arrangement returns to step 101 to perform a subsequent iteration. 
     The foregoing description has been limited to a specific embodiment of this invention. It will be apparent, however, that various variations and modifications may be made to the invention, with the attainment of some or all of the advantages of the invention. It is the object of the appended claims to cover these and such other variations and modifications as come within the true spirit and scope of the invention.