今西進化論に基づく遺伝アルゴリズムによるモジュール配置問題の多様な最適解の探索
田川 聖治, 水谷 浩二, 井上 克已, 羽根田 博正
pp. 467-474
DOI:
10.5687/iscie.14.467抄録
In order to find the plural number of optimal solutions for the module placement problem, which is of particular significance in the design of VLSI, a new Genetic Algorithm (GA) based on Imanishi's evolutionary theory is proposed. First of all, a phenotypic distance between two solutions, or individuals, is defined as the shortest Hamming distance between sets of isomorphic genotypes. If the phenotypic distance between two individuals is shorter than a threshold value, they are regarded as the same species. Then, a new generation alternation model that is analogous to the habitat segregation is presented. Since each individual in the population represents an isolating species, the diversity of the population is maintained spontaneously. Even though the selection of individuals based on their fitness is not employed, excellent individuals are created effectively by using the harmonic crossover operation combined with a local optimization method.