Tabu - local search mechanism for Mega Process genetic algorithm
Yoshiko Hanada, Tomoyuki Hiroyasu, Mitsunori Miki · 2005
In this study a new genetic algorithm (GA) using tabu: local search mechanism for large-scale computer systems is proposed. We call the GA that uses huge computing resources a mega process GA. The GA described in this paper is considered a mega process GA which has the effective mechanism to solve the problems quickly and to use massive processors, namely mega processors, comprised in large-scale computing systems such as super PC clusters and grid computation environments. Our proposed method has a GA-specific database that possesses information of space that has been already searched. At the same time, the proposed GA performs a local search for the space that is not searched. Such mechanisms enable us to comprehend the quantitative rate of a searched region during the search. Using this information, the searched space can be expanded linearly as the number of computing resources increase and the exhaustive search is guaranteed under infinite computations. Using and describing different experiments, the features of the introduced GA are discussed and examined. At first, this method was applied on one max problem and 3-deceptive problem; the former is one of primitive functions and the latter is one of trap functions. Through this experiment, it is shown that the method ensures an effective exhaustive search. This method was then applied to the test functions of continuous optimization problems under restricted computing costs. Using such an experiment, it is clear that this method has the same performance as a conventional GA.