著者
佐藤 浩 小野 功 小林 重信
出版者
社団法人人工知能学会
雑誌
人工知能学会誌 (ISSN:09128085)
巻号頁・発行日
vol.12, no.5, pp.734-744, 1997-09-01
被引用文献数
211

When Genetic Algorithms (GAs) are applied to optimization problems, characteristic preserving in designing coding/crossover and diversity maintaining in designing generation alternation are important. Generation alternation models are independent of problems, while coding/crossover depends on problems. We discuss generation alternation models in this paper. Simple GA is one of the well-known generation alternation models, however it has two problems. One is early convergence in the first stage of search and the other is evolutionary stagnation in the last stage of it. Many improvements and new models have been presented to overcome the above problems. In this paper, we propose a new generation alternation model called minimal generation gap (MGG) which has all advantages of conventional models. As generation alternation models use only information of fitness, alternation of generations can be regarded as a transformation of fitness distributions. We propose a new method of assessing generation alternation models. We measure the ability of avoiding the early convergence and suppressing the evolutionary stagnation by the dynamics of the best value and variance of fitness distributions. From the results of some experiments, we found that MGG is the most desirable model which can avoid the early convergence and suppress the evolutionary stagnation. We also show the efficiency of MGG by applying it to benchmarks in different two domains: function optimization and traveling salesman problems. In the both domains, MGG showed higher performance than the other conventional models especially under small population size.
著者
永田 裕一 小林 重信
出版者
社団法人人工知能学会
雑誌
人工知能学会誌 (ISSN:09128085)
巻号頁・発行日
vol.14, no.5, pp.848-859, 1999-09-01
被引用文献数
21

In this paper, we propose a new crossover named Edge Assembly Crossover(EAX) for the Traveling Salesman Problern. EAX constructs intermediate individuals by assembling only edges of parents under the assignment relaxation that is one of TSP relaxations, and then modifies them into complete ones to satisfy the original constraint of TSP. EAX has two features. One is that EAX is excellent in chartacteristic preservation in view of preserving edges from parents to children. The other is that EAX can generate a wide variety of children from a pair of parents. We show by experiments that EAX generates new soltution candidates under a suitable trade-off between characteristic preservation and a variety of children, which brings better performance than other crossovers do. Finally, we show that EAX realizes global neighborhood search by comparing EAX with the traditional local search operators for TSP.