遗传算法概述

顾　玮

（徐州高等师范学校　徐州　221116）



遗传算法概述

顾玮

（徐州高等师范学校徐州221116）

摘要基于遗传算法，介绍了算法的相关概念，列出了算法的操作步骤，分析了算法实现的关键技术，为以后遗传算法的应用提供了理论支持。

关键词遗传算法关键技术操作步骤

一、遗传算法简介

遗传算法［1］（Genetic Algorithms，简称GA）是生命科学与工程科学互相交叉、互相渗透的产物，其本质是一种求解问题的高度并行的全局随机化搜索算法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。

经过中外学者近20年的研究，遗传算法不论是在应用上、算法设计上，还是在基础理论上，都取得了很大的发展，已成为信息科学、计算机科学、运筹学和应用数学等诸多学科所共同关注的热点研究领域。

二、遗传算法的有关概念

下面列出了遗传算法相关的基本概念。

编码：染色体中遗传信息在一个长链上按一定的模式排列，即进行了遗传编码。在优化问题中染色体编码表现为具体参数到染色体基因表现形式的映射。

选择：指决定以一定的概率从种群中选择若干个体的操作。选择过程是一种基于适应度的优胜劣汰的过程。

交叉：父代个体繁殖下一代个体时，两个父个体的染色体之间通过交叉重组，即在两个染色体的某一位置处被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称为基因重组。

变异：染色体复制时可能以很小的概率产生某些复制差错，从而使染色体基因发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。

三、遗传算法的基本操作

1、遗传算法的基本操作步骤

遗传算法所涉及的五大要素为：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。遗传算法的运行过程为一个典型的迭代过程，其必须完成的工作内容和基本步骤如下：

（6）按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；

（7）判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则返回步骤6。

2、实现遗传算法的关键技术

（1）染色体编码［2］

遗传算法不能直接处理实际问题的参数，而只能处理以基因串的形式表达的染色体。因此要使用遗传算法就必须把优化问题解的参数转换成染色体形式，这一转换操作就叫编码。

（2）个体适应度评价

遗传算法在搜索过程中仅以适应度函数［3］作为寻优的依据。遗传算法的适应度函数不受连续可微的约束且定义域可以为任意集合，对适应度函数的唯一要求就是函数值不能为负数。

（3）遗传算子

在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境的适应程度施加一定的操作，从而实现优胜劣汰的进化过程。遗传算法的遗传操作包括选择、交叉和变异三个基本算子［4］。

①选择算子

从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。常用的选择策略主要有：适应度比例法、最佳个体保留法、期望值方法、排序选择法和联赛选择法。

②交叉算子

遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉把两个父个体的部分基因相互交换而生成新个体的操作。常用的交叉算子为：单点交叉、两点交叉和均匀交叉。

③变异算子

变异算子就是对群体中个体的染色体某些位置的基因发生变动。变异能保证后代群体中个体的多样性。常见的变异算子主要有：基本变异算子、均匀变异算子和自适应变异。

（4）遗传算法的运行参数

在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。这组参数在初始化阶段或群体进化过程中需要合理的选择和控制，以使遗传算法以最佳的搜索轨迹达到最优解。主要的参数有：

交叉概率一般应取较大值。但若取值过大的话，它又会破坏群体中的优良模式，对进化运算反而产生不利影响；若取值过小的话，产生新个体的速度又较慢。

若变异概率取值较大的话，虽然能产生出较多的新个体，但也有可能破坏掉很多较好的模式；若变异概率取值太小的话，则变异操作产生新个体的能力和抑制早熟现象的能力就会较差。

终止代数是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。

⑤遗传算法的终止条件

遗传算法迭代过程的终止，一般采用设定最大代数的方法。该方法简单易行但不准确。其次，可以根据群体的收敛程度来判断。最后，在采用精英保留选择策略的情况下，按每代最佳个体的适应值的变化情况确定。

四、结束语

本文主要从遗传算法的相关概念、基本操作、操作步骤和关键实现技术等方面研究了遗传算法，为遗传算法的深入研究和应用奠定了理论基础。

参考文献

［1］陈国良，王煦法，庄镇泉，王东生.遗传算法及其应用［M］.北京：人民邮电出版社，2012：51-53.

［2］董敏，霍剑青，王晓蒲.基于自适应遗传算法的智能组卷研究［J］.小型微型计算机系统，2004，25（1）：82-85.

［3］梁艳春，周春光，李寿范.基于遗传算法的函数优化问题的研究［J］.软件学报，2005，8（9）：701-708.

［4］戴亚非，李晓明.计算机自动组卷算法分析［J］.小型微型计算机系统，2005，16（9）：51-55.

［5］魏平，熊伟洁.用遗传算法解组卷问题的设计与实现［J］.微电子学与计算机，2002（4）：48-50.

［6］丁建立，陈增强，袁著社.遗传算法与蚁群算法的融合［J］.计算机研究与发展，2003，40（9）：1351-1356.

Overview of Genetic Algorithms

Gu Wei
（Xuzhou Higher Normal School Xuzhou 221116）

AbstractBased on genetic algorithm，introduces the related concepts of the algorithm，lists the steps of the algorithm，and analyzed the key technologies to implement the algorithm，for the application of genetic algorithms to provide theoretical support.

KeywordsGenetic algorithm Key technology Operation steps

中图分类号TP301.6

文献标识码A

文章编号160223-7211

作者简介

顾玮，女，1981年生，汉族，徐州高等师范学校教师，硕士研究生，研究数据库，数据挖掘，系统开发。