TJPNSEC : Vol. 1 (2010) , No. 1 pp.89-101

Towards the Maintenance of Population Diversity: A Hybrid Probabilistic Model Building Genetic Network Programming

Xianneng Li¹⁾, Shingo Mabu¹⁾, Kotaro Hirasawa¹⁾

1) Graduate School of Information, Production and Systems, Waseda University

Summary: Some researchers have investigated that the diversity loss will significantly decrease the performance of Probabilistic Model Building Genetic Algorithm (PMBGA), especially under large search space, leading to the premature convergence and local optimum. However, few work has been done on the diversity maintenance in the Probabilistic Model Building Evolutionary Algorithms (PMBEAs) with more complex chromosome structures, such as tree structure based Probabilistic Model Building Genetic Programming (PMBGP) and graph structure based Probabilistic Model Building Genetic Network Programming (PMBGNP). For the PMBEAs with more complex chromosome structures, the required sample size is usually much larger than that of binary structure based PMBGA. Therefore, these algorithms usually become much more sensitive to the population diversity. In order to obtain enough population diversity, the large population size is needed, which is not the best way. In this paper, the maintenance of the population diversity is studied in PMBGNP, which is a kind of PMBEA, but has its unique characteristics because of its directed graph structure. This paper proposed a hybrid PMBGNP algorithm to maintain the population diversity to avoid the premature convergence and local optimum, and presented a theoretical analysis of the diversity loss in PMBGA, PMBGP and PMBGNP. Two techniques have been proposed for the diversity maintenance when the population size is set at not large values, which are multiple probability vectors and genetic operators. The proposed algorithm is applied and evaluated in a kind of autonomous robot, Khepera robot. The simulation study demonstrates that the proposed hybrid PMBGNP is often able to achieve a better performance than the conventional algorithms.

Keywords:

probabilistic model building evolutionary algorithm (PMBEA), estimation of distribution algorithm (EDA), genetic network programming (GNP), probabilistic model building genetic network programming (PMBGNP), diversity maintenance

進化計算学会論文誌

Transaction of the Japanese Society for Evolutionary Computation