Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
Seminar 1
| 7. for y =1 to height
8. select an individual k (located at position [x',y']) neighboring with i (located at position [x,y]); 9. generate offspring from i and k ; 10. apply the user-defined replacement policy to update i; 11. mutate i with probability pmut; 12. evaluate the individual i; end for end for end while Fig. 3. Pseudocode of the slice process. Each slice process uses the parameters read from a file to configure the genetic programming algorithm performed on each grid point. The parame- ters regard the population size, the max depth that the trees can have after the crossover, the parsimony factor, the number of iterations, the number of neighbors of each individual, and replacement policy. CAGE implementes three replacement policies: direct (the best of the offspring is always re- placed to the current individual), greedy (the replacement occurs only if offspring is fitter), probabilistically (the replacement happens according to fitness difference between parent and offspring (simulated annealing )). The size of the subpopulation of each slice process is calculated divid- ing the population for the number of the processors on which CAGE is exe- cuted. Each slice process updates sequentially the individuals belonging to its subgrid. At the start, in each process, is generated a random subpopula- tion and the fitness is evaluated. After, for numGeneration iterations the loop for generating the new subpopulation is performed. The variables 203 length and height define the boundaries of the 2D subgrid that is contained in a process. It should be noted that two copies of the data are maintained for calculating the new population. In fact, as each element of the current population is used many times the current population cannot be rewritten. CAGE uses the standard tool for genetic programming sgpc [25] to ap- ply the GP algorithm to each grid point. However, in order to meet the re- quirements of the cellular GP algorithm, a number of modifications have been introduced. The same data structure of sgpc is used to store a tree in each cell. The structure that stored the population has been transformed from a one- dimensional array to a two-dimensional array and we duplicated this struc- ture in order to store the current and the new generated tree. The selection procedure has been replaced with one that uses only the neighborhood cells and three replacement policies arc added. The crossover operator accepts in input the current tree and the best tree in the neighborhood. Two procedures to pack and unpack the trees that must be sent to the other processes have been added. The pack procedure is used to send in a linearized form the trees of the boundary data to the neighbor processes. Data are transmitted as a single message in order to minimize the message startup and transmission time. The unpack procedure rebuilds the data and stores it in the new proc- essor's private address space. The execution of a parallel program is composed of two phases: compu- tation and communication. During the computation phase each process of the concurrent program that implements the run-time support executes computations which only manipulate data local to this process. These data can be local variables or boundary data received from neighbor processes. The effective data transmission between processes is done at the end of each local computation. This means that, during computation phase, no data are exchanged. The parallel implementation has been realized on a multicomputer Meiko CS-2. In [15] we present the convergence results obtained with CAGE and compare them with the sequential canonical GP and the island model implementation realized by [22] and [24]. sgpcl.1 is used as the ca- nonical sequential implementation of genetic programming. Preliminary experimental results shows better performances of tins approach. We are planning an experimental study on a wide number of benchmark problems to substantiate the validity of the cellular implementation. |