中国物理B ›› 2016, Vol. 25 ›› Issue (12): 128904-128904.doi: 10.1088/1674-1056/25/12/128904

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇    

An improved genetic algorithm with dynamic topology

Kai-Quan Cai(蔡开泉), Yan-Wu Tang(唐焱武), Xue-Jun Zhang(张学军), Xiang-Min Guan(管祥民)   

  1. 1. School of Electronic and Information Engineering, Beihang University, Beijing 100191, China;
    2. Department of General Aviation, Civil Aviation Management Institute of China, Beijing 100102, China
  • 收稿日期:2016-07-10 修回日期:2016-09-10 出版日期:2016-12-05 发布日期:2016-12-05
  • 通讯作者: Xue-Jun Zhang E-mail:zhxjbh@163.com
  • 基金资助:

    Project supported by the National Natural Science Foundation for Young Scientists of China (Grant No. 61401011), the National Key Technologies R & D Program of China (Grant No. 2015BAG15B01), and the National Natural Science Foundation of China (Grant No. U1533119).

An improved genetic algorithm with dynamic topology

Kai-Quan Cai(蔡开泉)1, Yan-Wu Tang(唐焱武)1, Xue-Jun Zhang(张学军)1, Xiang-Min Guan(管祥民)2   

  1. 1. School of Electronic and Information Engineering, Beihang University, Beijing 100191, China;
    2. Department of General Aviation, Civil Aviation Management Institute of China, Beijing 100102, China
  • Received:2016-07-10 Revised:2016-09-10 Online:2016-12-05 Published:2016-12-05
  • Contact: Xue-Jun Zhang E-mail:zhxjbh@163.com
  • Supported by:

    Project supported by the National Natural Science Foundation for Young Scientists of China (Grant No. 61401011), the National Key Technologies R & D Program of China (Grant No. 2015BAG15B01), and the National Natural Science Foundation of China (Grant No. U1533119).

摘要:

The genetic algorithm (GA) is a nature-inspired evolutionary algorithm to find optima in search space via the interaction of individuals. Recently, researchers demonstrated that the interaction topology plays an important role in information exchange among individuals of evolutionary algorithm. In this paper, we investigate the effect of different network topologies adopted to represent the interaction structures. It is found that GA with a high-density topology ends up more likely with an unsatisfactory solution, contrarily, a low-density topology can impede convergence. Consequently, we propose an improved GA with dynamic topology, named DT-GA, in which the topology structure varies dynamically along with the fitness evolution. Several experiments executed with 15 well-known test functions have illustrated that DT-GA outperforms other test GAs for making a balance of convergence speed and optimum quality. Our work may have implications in the combination of complex networks and computational intelligence.

关键词: complex networks, genetic algorithm dynamic topology

Abstract:

The genetic algorithm (GA) is a nature-inspired evolutionary algorithm to find optima in search space via the interaction of individuals. Recently, researchers demonstrated that the interaction topology plays an important role in information exchange among individuals of evolutionary algorithm. In this paper, we investigate the effect of different network topologies adopted to represent the interaction structures. It is found that GA with a high-density topology ends up more likely with an unsatisfactory solution, contrarily, a low-density topology can impede convergence. Consequently, we propose an improved GA with dynamic topology, named DT-GA, in which the topology structure varies dynamically along with the fitness evolution. Several experiments executed with 15 well-known test functions have illustrated that DT-GA outperforms other test GAs for making a balance of convergence speed and optimum quality. Our work may have implications in the combination of complex networks and computational intelligence.

Key words: complex networks, genetic algorithm dynamic topology

中图分类号:  (Networks and genealogical trees)

  • 89.75.Hc
05.45.-a (Nonlinear dynamics and chaos)