广西科技大学2014届本科毕业设计（论文）说明书
散函数、凹函数和凸函数、高维函数和低维函数、单峰函数和多峰函数等。针对于一些非线性、多目标、多模型的函数优化课题，使用其它的优化方法可能较难求得最优解，而应用遗传算法可以方便的得到相对较好的结果。
（2）组合优化 组合优化问题的搜索空间随着实际求解问题规模不断增大而急剧扩展，目前的实际应用中在运算上利用枚举法求得最优解显得甚是艰难。针对这一类复杂的问题，研究人员将主要研究方向集中于寻求问题满意解上，而遗传算法已经验证是寻求问题满意解的最佳工具之一。实践表明，遗传算法应用优化组合优化中的NP问题取得显著效果[12]。遗传算法已经成功应用于求解旅行商问题、装箱问题、背包问题、图形划分问题等。
（3）生产调度 在许多情况下生产调度问题难以精确地建立起数学模型，往往经过一系列简化之后也可以求解．但会因为简化的原因从而使得求解结果与实际问题相差较大。目前在现实生产中主要是依靠于从事生产人员的实践经验来进行具体调度。复杂调度问题的解决过程中遗传算法已经发展成为高效的工具[13]。遗传算法有效地应用于部件生产调度、车间流水线生产调度、企业生产规划、生产任务人员分配等多方面。 （4）自动控制 在自动控制领域中亟需求解很多优化类的问题。而遗传算法在这方面已经得到了一定的应用，结果也显示出理想的效果。例如使用遗传算法来优化高速铁路控制系统、将遗传算法应用到模糊模型的控制器的优化设计中[14]、将遗传算法应用于参数辨识过程中、利用遗传算法来优化设计神经网络控制系统的结构等都表明了遗传算法可以应用于自动控制领域中。
（5）机器人学 机器人作为一类实际应用中难以建立起精确模型的复杂的人工智能系统，而从遗传算法的起源中可以看出其来自对人工自整定系统的研究。因此，遗传算法可以成功地应用于机器人学领域。比如，遗传算法已经研究应用于机器人的移动路径规划[15]、关节机器人运动轨迹的规划、机器人逆运动学中的问题求解等方面。 （6）图像处理 图像处理是计算机视觉中的主要研究领域。在图像处理过程中，如扫描数字化输入、边缘检测、图像分割等无法避免地会存在一定的误差，因而影响到图像最终的处理效果。衡量计算机视觉能否达到实用效果的重要要求就是如何使得处理过程中的误差达到最小化。在图像处理过程中的优化计算方面完全可以使用遗传算法进行处理。目前遗传算法已经在模式识别（包括汉字识别）[16]、图像恢复、图像特征提取等领域得到了实际应用。
（7）人工生命 人工生命是基于计算机软件工程、人工智能技术等模拟或构造出的具有自然生物系统所特有行为的人工模拟生命系统。人工生命与遗传算法有着密不可分的关系。研究人工生命现象过程中将基于遗传算法的进化模型作为其重要的基础理论
[17]
。遗传算法已经在人工生命的繁殖模型、自组织模型、进化模型等多方面其实际应用
能力已经得到初步的显示，并且其研究应用及发展还将会不断地深入。人工生命与遗传算法互促发展，人工生命研究中遗传算法可以被当作有效的工具之一，同时人工生命的研究也推动了遗传算法的不断向前发展。
- 12 -
广西科技大学2014届本科毕业设计（论文）说明书
（8）遗传编程 美国Stanford大学的Koza教授发展了遗传程序设计的概念，其基本思想是：采用常用的树型结构来表示计算机程序，运用遗传算法的思想来自动生成计算机程序来解决实际问题。虽然遗传程序设计尚未具备完全成熟的理论，实际应用也有一系列的限制，但在人工生命、机器学习等领域已经得到成功的应用。目前可用的遗传编程实验系统有Koza教授开发的ADF系统等.
（9）机器学习 高级自适应系统所具备的能力中学习能力必不可少，将遗传算法应用于机器学习在很多领域中都得到了应用[18]。例如，学习模糊控制规则过程中应用遗传算法来进行，利用遗传算法来学习隶属度函数，可以使得模糊控制系统的性能得到更好地改进；利用遗传算法的机器学习可以用来优化人工神经网络的结构设计。 （10）数据挖据 数据挖掘是近些年才出现的新的数据库技术，其能够从大型数据库中提取客户所需要的隐藏的、未知的、具备潜在价值的知识或规则。许多数据挖掘问题都是搜索问题的体现，将数据看作成搜索空间，将挖掘算法看作成搜索策略。因此，应用遗传算法作为挖掘算法在数据库中进行搜索，对随机产生的一组知识或规则进行不断地进化，直到数据库能被该组知识或规则覆盖，这样就可挖掘出隐藏在数据库中的知识或规则[19]。
4.1.3 遗传学基本概念
(1) 串（string）：串作为个体的形式，在算法中一般为二进制形式，与遗传学中的染色体相对应。
(2) 群体（population）：将个体集合形成的即称作群体，群体的基本构成元素是串。 (3) 群体大小（population size）：在群体中包含的所有个体的数量被称作群体的大小。 (4) 基因（gene）：串中的元素即为基因，可以实现个体特征的表示。例如存在串s=0111，则其中的0，1，1，1这四个元素分别被称作基因。其对应的值被称为等位基因。
(5) 非线性：与遗传学中的异位显性相对应。
(6) 基因位置（gene position）：一个基因位于串中所处的位置就被称作基因位置，或者称作基因位。在串中基因位置都是自左至右来计算，如串s=0111中，0所处基因位置为1。基因位置与遗传学中的地点相对应。
(7) 基因特征值（gene feature）：当使用串表示某个整数时，基因的特征值应该与二进制的权值相同。比如在串s=0111中，基因位置4中的1，它对应基因特征值是1。基因位置2中的1，它对应基因特征值是4。
(8) 串结构空间ss：在串中，基因通过随机组合从而形成了的串的集合。在结构空间内执行基因操作。串所构成的结构空间与遗传学中基因型的集合相对应。
(9) 参数空间sp：将串空间映射到实际系统中形成，与遗传学中表现型集合相对应。 (10) 适应度（fitness）：表示具体某个体对于其所处环境的适应程度。
- 13 -
广西科技大学2014届本科毕业设计（论文）说明书
4.2 遗传算法的应用步骤
针对实际中一个需要进行优化的问题，通常依据下述步骤构造出遗传算法： 第一步：确定好决策变量和各项约束条件，即确定好具体个体的表现型X和解决对象的解空间；
第二步：建立出优化模型，即确定出目标函数的类型及数学描述形式或量化方法； 第三步：确定表示方法可行解的染色体编码方法，即确定出个体基因型X及遗传算法的搜索空间；
第四步：确定解码方法，即确定出由个体基因型X到个体表现型X的对应关系或者转换方法；
第五步：确定个体适应度的量化评价方法，即确定出由目标函数值J(x)到个体适应度f(x)的转换规则；
第六步：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方法；
第七步：确定遗传算法的有关运行参数，即M,G,Pc,Pm等参数。[1]
现在对其中的参数编码和解码、适应函数的选择、遗传算法这三个重要步骤进行具体说明：
（1）参数的编码和解码
在遗传算法中如何来描述一个问题的可行解，即把一个需要求解的问题的可行解从其现有的解空间转换到遗传算法可以处理的搜索空间中来，这样的转换方法就被称为编码。一般把求解问题的各种参数先用编码的方法让其构成子串，然后再把子串连接构造成染色体串。遗传算法中最常用的一种编码方法是二进制编码方法。本论文中采用二进制编码的编码方式。
PID 中三个参数Kp，Ki和Kd作为编码对象，采用如下公式进行转换：
n?Umax?Umi??l u?Umax n （4.1）2?1其中， u是编码对象，Umax和Umin是U的取值范围，l是二进制编码的长度。n是
l位的二进制数。
（2）适应度函数的选择
适应度函数表明了种群中的个体适应环境能力的强弱，其相关于所选取的目标函数。本论文采用了绝对误差积分模型：
- 14 -
广西科技大学2014届本科毕业设计（论文）说明书
J论文定义了适应度函数f为:
??te(t)dt （4.2）
ox f?（3）遗传算法的组成 ① 选择(selection operator)
1?J1?te(t)dt0x （4.3）
在遗传算法中使用选择算子来对种群中的所有个体进行优胜劣汰操作。在选择过程中，以是否满足适应度作为选择或放弃的原则。适应度选择准则体现了生物进化过程中“优胜劣汰，适者生存”自然法则。适应度较高的个体被执行遗传操作保留到下一代新生种群的概率相对较大，适应度较低的个体被执行遗传操作保留到下一代新生群体中的概率相对较小。研究工作中比例选择算子是最常用及的选择算子，本文中运用比例选择算子来执行选择操作。其基本思想为：选中种群中各个独立个体的概率正比于此个体满足适应度的程度。假设群体的大小为M，个体i的适应度为Fi，则选中个体i的概率Pi如公式4.4.
Pi?Fi?Fii?1M （4.4）
上式表明：
个体满足适应度较高，繁殖出的下一代中数目相对比较多。
个体满足适应度较低，繁殖出的下一代中数目相对比较少，甚至发生逐渐被淘汰的现象。
这样，群体中就产生了能够适应环境的后代个体。如果从解决问题的角度来看，这样就可以选择出比较接近最优解的中间解。
② 交叉(crossover operator)
对于因为满足适应度而被选中用来繁殖产生下一代的个体当中，任意选择其中的两个个体上相同位置，以交叉概率P位于选择的位置进行相互交换。这个过程反映了遗传过程中信息随机的交换；这项操作的目的在于产生全新的基因组合，即是在种群中产生出新的个体。进行交叉操作时，可以选择进行单点交叉或者多点交叉。交叉算子是指对两个已经相互配对好的染色体以某种方式来相互交换其中的部分基因，这样形成了两个新的个体。本论文运用中间重组双点交叉法来执行交叉操作，即在种群中任意选取两个个体，并在个体的编码串中任意设置好两个交叉点，然后在该点上以一定的概率Pc对两个已经配对好的个体的部分染色体进行相互交换。研究中一般Pc的经验设定值范围是0.50～0.99。
- 15 -
