06-GAlib在遗传算法实现中的应用1
需积分: 0 172 浏览量
2022-08-03
16:19:08
上传
评论
收藏 836KB PDF 举报
计 算 机 系 统 应 用 http://www.c-s-a.org.cn 2011 年 第 20 卷 第 10 期
184 应用技术 Applied Technique
GAlib 在遗传算法实现中的应用
①
张泰忠，徐 成
(湖南大学 信息科学与工程学院，长沙 410082)
摘 要：遗传算法（Genetic Algorithm）是一种模拟达尔文生物进化论的随机搜索方法，被人们广泛应用于组合
优化、机器学习、信号处理、自适应控制和人工生命等领域。然而，编程实现遗传算法的过程非常复杂且容易
引入人为的错误，进而影响相关研究的准确性。针对这一问题，讨论了基于 GAlib（Genetic Algorithm Library）
类库设计实现遗传算法的关键技术。最后，利用 GAlib 实现了遗传算法，并以解决旅行商人问题(TSP)对算法进
行评估，实际效果表明，基于 GAlib 开发的遗传算法编程简单，可读性强，结果准确。
关键词：GAlib；遗传算法；染色体；种群；适应度
Application of GAlib to the Implementation of Genetic Algorithm
ZHANG Tai-Zhong, XU Cheng
(College of Information Science and Engineering, Hunan University, Changsha 410082, China)
Abstract: Genetic Algorithm (Genetic Algorithm) is a random investigation method simulating Darwin’s biological
evolution, and it is applied to the fields like combinatorial optimization, machine learning, signal processing, adaptive
control and artificial life. However, the implementation process of genetic algorithm is very complicated and easily
introduce error artificially, and influence the accuracy of research. for this problem, the key technology of implementing
genetic algorithm based on GAlib（Genetic Algorithm Library）class library is discussed. Finally, genetic algorithm is
implemented using GAlib and evaluate the algorithm by solving the traveling salesman problem(TSP), the results shows
that the genetic algorithm implemented based on GAlib is easily programming, highly readable,and results are accurate.
Key words: GAlib; genetic algorithm; chromosome; population; fitness
1 引言
1975 年 J.Holland 教授提出了遗传算法
[1]
（Genetic
Algorithm）思想，该算法是一种借鉴达尔文生物进化
论“适者生存，优胜劣汰”遗传机制的随机搜索方法，
具有内在并行性良好，全局寻优能力强，搜索方式智
能等特点，广泛应用于函数优化、机器人学、图像处
理、数据挖掘和人工生命等领域，已逐渐成为现代人
工智能计算中的关键技术。然而，遗传算法在运用过
程中需要经历初始化种群、染色体编码、选择、交叉、
变异、适应度计算等一系列复杂操作，实现过程十分
繁琐，造成人为错误的可能性较大。
GAlib
[2]
（Genetic Algorithm Library）是美国麻省
理工学院的 Matthew Wall 用 C++开发的一套遗传算法
① 基金项目:国家自然科学基金(60973030)
收稿时间:2010-03-03;收到修改稿时间:2010-03-24
类库，设计合理，功能强大且易于扩展。本文针对利
用 GAlib 类库实现遗传算法需要解决的主要问题进行
讨论，组织结构如下：第 2 节介绍 GAlib 的相关概念；
第 3 节以解决旅行商人问题为实例，探讨基于 GAlib
实现遗传算法的关键技术；第 4 节统计旅行商人问题
的实验结果并分析利用 GAlib 实现的遗传算法的实际
效果，最后对本文的工作进行总结。
2 相关概念
一个完整的遗传算法包括染色体编码、初始化种
群，遗传操作以及适应度计算，针对遗传算法的主要
因素，GAlib 设计实现了遗传算法类、染色体类、种
群类、选择方案类及各自的派生体系。
评论0