论文部分内容阅读
摘要：遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法，它与传统的算法不同。大多数古典的优化算法是基于一个单一的度量函数(评估函数)的梯度或较高次统计，以产生一个确定性的试验解序列；遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解。该文针对传统遗传算法的缺陷，提出了一些新的改进思路，即从搜索技术和遗传算子等的角度来改进遗传算法。
关键词：遗传算法；自然遗传机制；搜索；遗传算子；改进
中图分类号：TP301.6文献标识码：A 文章编号：1009-3044(2008)33-1461-02
Genetic Algorithm and Application
MA Si-hong
(Radio and TV University in Wuxi ,Wuxi 214011,China)
Abstract: The genetic algorithm is a kind of natural selection from biological and natural genetic mechanisms of random search algorithm, it is different from the traditional method. Most of the classical algorithm is based on a single measurement function (evaluation function) or the gradient times higher statistics, in order to produce a definitive solution test sequence; genetic algorithm does not rely on gradient information, but through the simulation of natural evolution To search for optimal solutions. In this paper, the shortcomings of traditional genetic algorithm, put forward some new ideas to improve, that is, from the search technology and genetic operators such as the point of view to improve the genetic algorithm.
Key words: genetic algorithms; natural genetic mechanisms; search; genetic operator; improve
遗传算法(Genetic Algorithms，GA)是二十世纪七十年代开始兴起的以自然选择和遗传理论为基础，将是模拟生物进化过程中，“适者生存，优胜劣汰”规律而无需函数梯度信息的自适应全局搜索算法，在模式识别、神经网络，控制系统优化等方面得到了广泛应用。遗传算法倍受各行设计者青睐之原因在于：这类随机算法能够同时处理N个设计变量，有利于实现并行操作，提高多变量优化问题的计算效率。但是很多研究表明如果优化参数配置不当，遗传算法可能会出现不收敛的情况。为使遗传算法运用于工程结构优化领域，诸多学者对遗传算法做出不少改进 。
1 遗传算法的原理与一般流程
1.1 遗传算法的原理
遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法，它与传统的算法不同。大多数
古典的优化算法是基于一个单一的度量函数(评估函数)的梯度或较高次统计，以产生一个确定性的试验解序列；遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解。遗传算法一般包含三个基本操作，即选择、交叉和变异，选择体现了适者生存的自然法则，是通过把适应值高的个体复制到下一代来改善群体的平均适应值，它的目的是从群体中选出繁殖后代的双亲，避免基因缺失，提高全局收敛性和计算效率。交叉操作对于保证遗传算法的寻优过程能收敛到全局最优点，以及提高对优化过程的收敛速度起着重要的作用，常见的交叉操作主要有：单点交叉、多点交又 、均匀交叉等。变异操作是将个体染色体编码串中的某些基因座上的基因值用该基因的其它等位基因来替换，形成一个新的个体，从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了GA 的全局搜索能力，而变异运算是产生新个体的辅助方法，但它也是必不可少的一个运算步骤，决定了GA 的局部搜索能力，交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使得CA 能够以良好的搜索性能完或最优化问题的寻优过程。
1.2 遗传算法的一般流程
对于基本的遗传算法GA，可以定义成为一个8元组：
GA=(C，F，Po，M，Ps，Pc，Pm，T )
式中，C-个体的编码方法，
F-个体的适应度函数，
Po-初始种群，
M-群体大小，
Ps-选择算子，
Pc-交叉算子，
Pm- 变异算子，
T-算法终止条件，一般终止进化代数为100—500。
其中影响遗传算法精度以及收敛速度的有选择算子，交叉算子以及变异算子。由于遗传算法的搜索基本不利用外部信息，仅以适应度函数为依据，因此，适应度函数的选择对算法的实现至关重要。
遗传算法的具体可以分为以下几个步骤：1)随机产生初始种群，个体数目一定，每个个体表示为染色体的基因编码；2)计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及其代表的最优解，并结束计算；否则转向第三步；3)依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；4)按照一定的交叉概率和交叉方法，生成新的个体；5)按照一定的变异概率和变异方法，生成新的个体；6)有交叉和变异产生的新一代的种群，返回到第二步。
2 遗传算法的改进
目前对遗传算法主要应从以下三个方面着手改进：① 控制参数的调整；② 遗传算子的改进；③ 与其它启发式搜索技术结合构成的基本遗传算法的混合搜索算法。对控制参数调整的研究，笔者在以前论文中已经述及，本文主要从后两个角度的改进这个角度来探讨如何改进遗传算法。
2.1 搜索技术的改进
众所周知，遗传算法是基于自然选择和基因遗传学原理的一种群体寻优的搜索算法，它只要求被优化的函数是可计算的，因而具有很强的全局搜索能力，可有效地防止搜索过程收敛于局部最优解。但是GA的不足在于它的局部搜索能力弱，如果解空间很小的话，GA很难搜索到精确的最优值。为了提高算法的搜索效率，有必要引入新的算法思想，其中复合形法就是一种很好的改进措施。复合形法的基本思想与遗传算法类似，也是同时从参数空间中随机地取几个点构成复合形，并从这个复合形出发进行搜索。具体地说，就是对空间中这些点计算出各自性能指标值，去掉最坏的个体，并通过计算其它个体的中心点，以此对最坏点做一个映射，得到一个新的较好的个体。如此反复迭代，使复合形逐步向最优点收缩，复合形法也存在收敛速度慢的问题，且若初始随机数取得不好，使复合形的形状不好时，还可能导致复合形不收敛。但是在一般情况下，复合形有相对确定的搜索方向，而这正是遗传算法所欠缺的。基于以上想法，可以在遗传算法中增加一个操作收缩，即把种群中各个体作为一个复合形的顶点，并根据各点的指标函数值，产生新的较好点以取代最坏点，把整个种群向最优解的方向收缩一次。有研究表明，改进后的算法保持了原有的遗传算法的优点，同时引入了复合形法的搜索方向，使进一步提高遗传算法的收敛速度成为可能。
2.2 遗传算子的改进
在GA中引入一种成长算子，它不要求目标函数连续、可导，能有效防止算法陷入伪极值点，加速GA的收敛，简称这种改进的GA为GGA。其特点是：描述该点的部分或全部参数的二进制编码的最后几位全是1或0，比如**1000000或**011111。以**100000为例，这时如最优点为**011110，且待寻优函数值关于最优点对称，那么，只有区间(**011111，**011101)中的个体优于**100000，这些个体与**100000的欧几里德距离最大为3，而它们与**100000的距离最小也为5，而变异概率为1/4，仅依靠基本的交叉，变异操作，要花很长时间寻到更优个体。若将成长算子引入二进制编码GA中，能避免算法陷入伪极值点，同时能加强算法的方向性，加快算法的收敛。成长算子加在适应度值计算之后及复制算子之前，该算子对每一代中适应度值最大的前m个个体进行成长操作。若每一代种群中有N个个体Bi(i=1，2，… ，N )，它们的适应度值为fi(i=1，2，… ，N)，个体Bj由n个待寻优参数的二进制编码6j(j=1，2，…，N)组成，成长操作的具体步骤如下：
1) i=1；
2) 取出种群中的适应度值第i大的个体Bi；
3) j=1；
4) B=Bi(B为中间变量，其中相应的几个参数编码为6
5) Bj=Bj 1，未溢出则判断B的适应度值f比fi大否，大则8)，否则6)；
6) B=Bi；
7) Bj=Bj-1，未溢出则判断B的适应度值f比fi大否，大则8)，否则9)；
8) Bi=B；
9) j=j 1，若j≤ n则4)，j> n则10)；
10) 将B放回种群中，i= i 1，若i≤ m则2)，i> m则11)；
11) 成长操作结束。
从上面步骤可看出，该成长算子可以实现欧几里德距离较小而海明距离较大的两点之间的跨越，使当
前最优个体向其所在单极值区域的极值点收敛一步，弥补了二进制编码GA的不足。
2.3 其他
上面所列出的各种改进措施均是在标准GA的各步骤中进行的。更进一步地人们在遗传算法中又添加了附加的算法和一些辅助功能，GA的理论得到了更进一步的发展。同时还有更多的研究在进行进一步的探讨。其中有研究在普通GA中加入了漂移算子，即以当前最优个体为研究对象，将染色体基因片段的后二分之一的基因分别按一定的概率做±1的随机漂移，排位靠后的基因的漂移概率较大，排位靠前的基因漂移概率较小，由此产生一定数量的新个体，这种改变染色体申的低位基因的取值的方法可以起到扩大局部搜索能力的作用。有研究针对机组启停问题的特点，设计了“可行性检查”、“冗余检查”、“边界搜索”等附加功能，减少了GA求解过程中的无效操作，有效地提高了GA 的效率。还有人提出了多层遗传算法的概念，即除了群体内部各个体之间进行遗传操作外，在各个群体阔也进行类似的遗传操作(即群体的复制、交叉、变异)，以加强群体间的信息交换，改善寻优能力。此外，遗传算法本身是以激励机制-适应度函数为基础，故对适应度函数的改进应该是最基本的、最有效的改进方式。
总之，通过计算机模拟来再现生命现象是正在兴起的一个新的课题，人工生命研究的重要内容之一就是进化现象，而遗传算法则是研究进化现象的重要方法。各种算法对遗传算法的改进能够有效地避免一般遗传算法在计算过程中存在的问题，同时相对于一般遗传算法，其收敛速度和效率都有了很大的提高。
参考文献：
[1] 周明，孙树栋．遗传算法原理与应用[M]．北京：国防工业出版社，1999：33-65．
[2] 刘利民，柴跃廷．分布式库存系统优化控制的一种改进遗传算法[J]．计算机集成制造系统-CIMS，2002，8(5)：399-403
[3] 李海民，吴成柯．基于BP网络的遗传算法[J]．模式识别与人工智能，1999，12(2)：223-228．
[4] 唐文艳，顾元宪．遗传算法在结构优化中的研究进展[J]．力学进展，2002，32(1)：26-40．
[5] 张延年，刘斌，董锦坤，等．改进遗传算法在建筑结构优化设计中的应用[J]．东北大学学报(自然科学版)，2004，25(7)：692-694．
[6] 谢楠．遗传算法的改进策略及其在桥梁抗震优化设计中的应用效果[J]．工程力学，2000，(3)：98-100.
[7] 高山．遗传算法在机组启停中的应用及改进[J]．东南大学学报，2000，(3)：21-22.
[8] 吴超仲．一种多层遗传算法的提出及实现[J]．武汉交通科技大学学报，2000，(4)：354.
关键词：遗传算法；自然遗传机制；搜索；遗传算子；改进
中图分类号：TP301.6文献标识码：A 文章编号：1009-3044(2008)33-1461-02
Genetic Algorithm and Application
MA Si-hong
(Radio and TV University in Wuxi ,Wuxi 214011,China)
Abstract: The genetic algorithm is a kind of natural selection from biological and natural genetic mechanisms of random search algorithm, it is different from the traditional method. Most of the classical algorithm is based on a single measurement function (evaluation function) or the gradient times higher statistics, in order to produce a definitive solution test sequence; genetic algorithm does not rely on gradient information, but through the simulation of natural evolution To search for optimal solutions. In this paper, the shortcomings of traditional genetic algorithm, put forward some new ideas to improve, that is, from the search technology and genetic operators such as the point of view to improve the genetic algorithm.
Key words: genetic algorithms; natural genetic mechanisms; search; genetic operator; improve
遗传算法(Genetic Algorithms，GA)是二十世纪七十年代开始兴起的以自然选择和遗传理论为基础，将是模拟生物进化过程中，“适者生存，优胜劣汰”规律而无需函数梯度信息的自适应全局搜索算法，在模式识别、神经网络，控制系统优化等方面得到了广泛应用。遗传算法倍受各行设计者青睐之原因在于：这类随机算法能够同时处理N个设计变量，有利于实现并行操作，提高多变量优化问题的计算效率。但是很多研究表明如果优化参数配置不当，遗传算法可能会出现不收敛的情况。为使遗传算法运用于工程结构优化领域，诸多学者对遗传算法做出不少改进 。
1 遗传算法的原理与一般流程
1.1 遗传算法的原理
遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法，它与传统的算法不同。大多数
古典的优化算法是基于一个单一的度量函数(评估函数)的梯度或较高次统计，以产生一个确定性的试验解序列；遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解。遗传算法一般包含三个基本操作，即选择、交叉和变异，选择体现了适者生存的自然法则，是通过把适应值高的个体复制到下一代来改善群体的平均适应值，它的目的是从群体中选出繁殖后代的双亲，避免基因缺失，提高全局收敛性和计算效率。交叉操作对于保证遗传算法的寻优过程能收敛到全局最优点，以及提高对优化过程的收敛速度起着重要的作用，常见的交叉操作主要有：单点交叉、多点交又 、均匀交叉等。变异操作是将个体染色体编码串中的某些基因座上的基因值用该基因的其它等位基因来替换，形成一个新的个体，从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了GA 的全局搜索能力，而变异运算是产生新个体的辅助方法，但它也是必不可少的一个运算步骤，决定了GA 的局部搜索能力，交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使得CA 能够以良好的搜索性能完或最优化问题的寻优过程。
1.2 遗传算法的一般流程
对于基本的遗传算法GA，可以定义成为一个8元组：
GA=(C，F，Po，M，Ps，Pc，Pm，T )
式中，C-个体的编码方法，
F-个体的适应度函数，
Po-初始种群，
M-群体大小，
Ps-选择算子，
Pc-交叉算子，
Pm- 变异算子，
T-算法终止条件，一般终止进化代数为100—500。
其中影响遗传算法精度以及收敛速度的有选择算子，交叉算子以及变异算子。由于遗传算法的搜索基本不利用外部信息，仅以适应度函数为依据，因此，适应度函数的选择对算法的实现至关重要。
遗传算法的具体可以分为以下几个步骤：1)随机产生初始种群，个体数目一定，每个个体表示为染色体的基因编码；2)计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及其代表的最优解，并结束计算；否则转向第三步；3)依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；4)按照一定的交叉概率和交叉方法，生成新的个体；5)按照一定的变异概率和变异方法，生成新的个体；6)有交叉和变异产生的新一代的种群，返回到第二步。
2 遗传算法的改进
目前对遗传算法主要应从以下三个方面着手改进：① 控制参数的调整；② 遗传算子的改进；③ 与其它启发式搜索技术结合构成的基本遗传算法的混合搜索算法。对控制参数调整的研究，笔者在以前论文中已经述及，本文主要从后两个角度的改进这个角度来探讨如何改进遗传算法。
2.1 搜索技术的改进
众所周知，遗传算法是基于自然选择和基因遗传学原理的一种群体寻优的搜索算法，它只要求被优化的函数是可计算的，因而具有很强的全局搜索能力，可有效地防止搜索过程收敛于局部最优解。但是GA的不足在于它的局部搜索能力弱，如果解空间很小的话，GA很难搜索到精确的最优值。为了提高算法的搜索效率，有必要引入新的算法思想，其中复合形法就是一种很好的改进措施。复合形法的基本思想与遗传算法类似，也是同时从参数空间中随机地取几个点构成复合形，并从这个复合形出发进行搜索。具体地说，就是对空间中这些点计算出各自性能指标值，去掉最坏的个体，并通过计算其它个体的中心点，以此对最坏点做一个映射，得到一个新的较好的个体。如此反复迭代，使复合形逐步向最优点收缩，复合形法也存在收敛速度慢的问题，且若初始随机数取得不好，使复合形的形状不好时，还可能导致复合形不收敛。但是在一般情况下，复合形有相对确定的搜索方向，而这正是遗传算法所欠缺的。基于以上想法，可以在遗传算法中增加一个操作收缩，即把种群中各个体作为一个复合形的顶点，并根据各点的指标函数值，产生新的较好点以取代最坏点，把整个种群向最优解的方向收缩一次。有研究表明，改进后的算法保持了原有的遗传算法的优点，同时引入了复合形法的搜索方向，使进一步提高遗传算法的收敛速度成为可能。
2.2 遗传算子的改进
在GA中引入一种成长算子，它不要求目标函数连续、可导，能有效防止算法陷入伪极值点，加速GA的收敛，简称这种改进的GA为GGA。其特点是：描述该点的部分或全部参数的二进制编码的最后几位全是1或0，比如**1000000或**011111。以**100000为例，这时如最优点为**011110，且待寻优函数值关于最优点对称，那么，只有区间(**011111，**011101)中的个体优于**100000，这些个体与**100000的欧几里德距离最大为3，而它们与**100000的距离最小也为5，而变异概率为1/4，仅依靠基本的交叉，变异操作，要花很长时间寻到更优个体。若将成长算子引入二进制编码GA中，能避免算法陷入伪极值点，同时能加强算法的方向性，加快算法的收敛。成长算子加在适应度值计算之后及复制算子之前，该算子对每一代中适应度值最大的前m个个体进行成长操作。若每一代种群中有N个个体Bi(i=1，2，… ，N )，它们的适应度值为fi(i=1，2，… ，N)，个体Bj由n个待寻优参数的二进制编码6j(j=1，2，…，N)组成，成长操作的具体步骤如下：
1) i=1；
2) 取出种群中的适应度值第i大的个体Bi；
3) j=1；
4) B=Bi(B为中间变量，其中相应的几个参数编码为6
5) Bj=Bj 1，未溢出则判断B的适应度值f比fi大否，大则8)，否则6)；
6) B=Bi；
7) Bj=Bj-1，未溢出则判断B的适应度值f比fi大否，大则8)，否则9)；
8) Bi=B；
9) j=j 1，若j≤ n则4)，j> n则10)；
10) 将B放回种群中，i= i 1，若i≤ m则2)，i> m则11)；
11) 成长操作结束。
从上面步骤可看出，该成长算子可以实现欧几里德距离较小而海明距离较大的两点之间的跨越，使当
前最优个体向其所在单极值区域的极值点收敛一步，弥补了二进制编码GA的不足。
2.3 其他
上面所列出的各种改进措施均是在标准GA的各步骤中进行的。更进一步地人们在遗传算法中又添加了附加的算法和一些辅助功能，GA的理论得到了更进一步的发展。同时还有更多的研究在进行进一步的探讨。其中有研究在普通GA中加入了漂移算子，即以当前最优个体为研究对象，将染色体基因片段的后二分之一的基因分别按一定的概率做±1的随机漂移，排位靠后的基因的漂移概率较大，排位靠前的基因漂移概率较小，由此产生一定数量的新个体，这种改变染色体申的低位基因的取值的方法可以起到扩大局部搜索能力的作用。有研究针对机组启停问题的特点，设计了“可行性检查”、“冗余检查”、“边界搜索”等附加功能，减少了GA求解过程中的无效操作，有效地提高了GA 的效率。还有人提出了多层遗传算法的概念，即除了群体内部各个体之间进行遗传操作外，在各个群体阔也进行类似的遗传操作(即群体的复制、交叉、变异)，以加强群体间的信息交换，改善寻优能力。此外，遗传算法本身是以激励机制-适应度函数为基础，故对适应度函数的改进应该是最基本的、最有效的改进方式。
总之，通过计算机模拟来再现生命现象是正在兴起的一个新的课题，人工生命研究的重要内容之一就是进化现象，而遗传算法则是研究进化现象的重要方法。各种算法对遗传算法的改进能够有效地避免一般遗传算法在计算过程中存在的问题，同时相对于一般遗传算法，其收敛速度和效率都有了很大的提高。
参考文献：
[1] 周明，孙树栋．遗传算法原理与应用[M]．北京：国防工业出版社，1999：33-65．
[2] 刘利民，柴跃廷．分布式库存系统优化控制的一种改进遗传算法[J]．计算机集成制造系统-CIMS，2002，8(5)：399-403
[3] 李海民，吴成柯．基于BP网络的遗传算法[J]．模式识别与人工智能，1999，12(2)：223-228．
[4] 唐文艳，顾元宪．遗传算法在结构优化中的研究进展[J]．力学进展，2002，32(1)：26-40．
[5] 张延年，刘斌，董锦坤，等．改进遗传算法在建筑结构优化设计中的应用[J]．东北大学学报(自然科学版)，2004，25(7)：692-694．
[6] 谢楠．遗传算法的改进策略及其在桥梁抗震优化设计中的应用效果[J]．工程力学，2000，(3)：98-100.
[7] 高山．遗传算法在机组启停中的应用及改进[J]．东南大学学报，2000，(3)：21-22.
[8] 吴超仲．一种多层遗传算法的提出及实现[J]．武汉交通科技大学学报，2000，(4)：354.