论文部分内容阅读
【摘要】本文介绍了遗传算法的起源和基本原理。详细介绍了影响算法的主要因素及其相应改进的方法。也介绍遗传算法需要改进的地方，这也是以后发展的一种趋势，在实际的应用方向及其广泛通用，进行进一步深入研究也是必要的。
【关键词】编码 交叉 变异 遗传算法
1、遗传算法的起源
遗传算法是霍兰(J. H. Holland, 1975) 提出[1]，通过模拟生物的进化过程，运用启发搜索规则，把一组模型中优良个体生存和随机变异的信息交换结合在一起。从一组初始模型出发，根据给定的参数变化范围及变化步长，将每个模型的全部参数用许多串联在一起的二进制编码(或其他编码) 串表示，通过选择、交叉互换和变异不断保留优势特征，最后得到问题的最优解。其不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解，它利用某种编码技术，作用于染色体的字符串，模拟由这些串组成的群体的进化过程。具有以下特点：对可行解的表示广泛；具有群体并行搜索特性；具有很强的鲁棒性；然而它也有一些不足，它的编码不规则及编码存在的不准确性，其搜索的计算量大且搜索效率低，出现早熟收敛等等，严重影响了遗传算法的应用，也是需要解决和改进研究的地方。进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题，成为求解全局优化问题的有力工具之一。
在基本理论发展方面来说，模式定理和积木块假设是遗传算法有效的理论依据。模式定理保证了较优先的模式样本呈指数级增长，从而满足了寻找最优解得必要条件，即遗传算法存在着找到全局最优解得可能性。而积木块假设指出，遗传算法所具备寻找到全局最优解得能力，即具有低阶、短距、高平均适应度的模式在遗传算子的作用下，相互结合，能生成高阶、长距、低适应度模式，最终求得全局最优解。遗传算法全局收敛性分析取得了很大进展，文献[1]给出了基于二进制编码的收敛性经典结果及在群体无限大的假设下，讨论了分别单独使用交叉和变异算子实数编码遗传算法的收敛性。文献[2]在采用最优个体保留策略的前提下得到了保证收敛的一般条件，并以之检验了采用常用的交叉与变异算子时的实数编码遗传算法的收敛性。总体而言，遗传算法的基础理论研究至今还没有取得突破性进展，理论与应用之间还存在着很大差距。
在算法设计方面发展，遗传算法需要选择的运行参数主要有群体规模，交叉概率、变异概率、终止代数，然而编码方式也对遗传算法的性能有较大的影响。在编码方式的发展，从由二进制编码逐渐发展为十进制编码。参数的控制由静态的设置逐渐演变为动态自适应技术，而交叉、变异算子也不断进行改进，将算法分层[3]或其他算法进行融合，很好的改进了遗传算法。
2、遗传算法的基本原理及实现的主要因素
遗传算法模拟基因重组与进化的自然过程，把待解决的问题的参数进行编码为基因，若干基因组成一个染色体（个体），许多染色体类似于自然选择、配对交叉和变异的运算，经过多次重复迭代直至得到最后的优化结果。遗传算法的实现需要对其进行参数编码、遗传操作运算包括（交叉运算、变异运算、选择运算）、适应度函数设计、参数的控制与约束条件的处理来实现。对各个部分进行良好的处理才能使整个算法性能最佳，寻求出最优解[4～6]。
编码是遗传算法要解决的首要问题。编码就是把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法。为了克服二进制代码之间的汉明距离很大的问题提出格雷码，然而引入了另一层隐悬崖，采用大符号集编码及逐渐提出了十进制编码、动态编码等等编码方式。
交叉运算是按较大概率从种群中选择两个个体，按某种方式相互交换两个个体的某个或某些部分基因，从而形成两个新的个体，其继承了父代的基本特征。它是遗传算法区别于其他进化算法的重要特征，是产生新个体的主要方法，也对算法的收敛性起主要作用。交叉算子的设计和实现与具体的问题密切相关，前面的编码一同考虑，得到一种好的交叉算子是研究者们一直致力于的工作。
变异运算以较小的概率对个体编码串上的某个或某些值进行改变，进而形成新个体。变异本身是一种随机算法，与交叉和选择算子结合能够避免某些信息的丢失，维持种群的多样性防止出现早熟现象，变异的方向性可能引导遗传的方向性，加速最优解得收敛。交叉算子和变异算子相互配合，共同完成对空间的全局搜索和局部搜索，从而使遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。
选择运算对个体进行优胜劣汰，根据每个个体的适应度值大小选择，适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。可以使得到群体中个体的适应值不断接近最优解。选择算子在避免基因损失，提高搜索速度和全局收敛方面有着举足轻重的作用。选择不当会造成群体进化停止不前；或使适应度值偏大的个体误导群体的发展方向，使遗传失去多样性，产生早熟问题。另外，选择与编码方式无关。
适应度函数设计，适应度函数用于转换目标函数值，给每一个个体一个非负的价值数。适应度函数通常根据目标函数采用一定的转换关系来设置。选择运算是根据适应值函数得到结果来进行选择的，其分辨程度对选择及整个算法都有很大的影响。即适应度函数设计不当，有可能造成在遗传进化的初期，超常个体会因竞争力突出而控制选择过程，影响算法的全局优化性能；在遗传进化的后期，种群中个体适应度差异较小时，继续优化的潜能下降，可能获得某个局部最优解，这两种问题的出现。良好的适应度函数能够起到重要作用，是遗传算法设计的一个重要方面。
参数的控制与约束条件的处理，控制参数选择的是否合理直接影响算法的收敛速度和搜索效率，当前没有完善的理论指导它的选择，还主要是根据经验。参数的控制对遗传算法的性能有较大的影响。良好的参数设置可以很好的改进算法的性能，加速算法的收敛。对约束条件进行处理，目前尚无处理各种约束条件的方法，根据具体问题而定，常采用搜索空间限定法，可行解变换法和罚函数法等等。
3、遗传算法发展趋势
遗传算法作为一种优化算法，其目的在于针对目标函数来进行求解未知参量的最优解。对于其研究的方向也是根据其目标函数来如何进行求解得到最优解。即可以应用于能建立出目标函数的任何一领域。对算法本身的性能研究，使算法在其可靠性、计算效率提高；通过不同算法的优点有机结合，形成混合算法；可以根据实际问题建立目标函数选择合适的参数控制及应用范围调整。
基于遗传算法自身的研究，早熟问題使种群失去了进化能力，是目前最难解决的问题。通常的表现是群体中所有的个体进化一定的代数后就陷于同一极值而停止进化了，或者接近最优解的个体总是被淘汰，找不到最优解。然而它的编码不规则及编码存在的不准确性，其搜索的计算量大且搜索效率低等等，也严重影响了遗传算法的应用。需要设计出良好的编码、良好的选择方式及良好的交叉、变异算子来改进算法中的不中之处。
遗传算法与其他计算智能方法的相互渗透和结合[7]。如遗传算法与模糊推理以及混沌理论、与传统算法、神经网络算法、粒子群算法、蚁群算法等等其他智能计算方法相互渗透和结合，必能达到取长补短的作用。混合算法的实质是通过不同算法的优点有机结合，改善单纯算法的性能。
然而随着实际问题难度的增加，对遗传算法本身的不足逐渐显露，即需要进一步改进，如单目标函数不在是以前的单峰一维或多峰单维或单峰多维，而是多峰多维且维数的增高，对求解的问题难度将急剧增加。针对不同问题采用重新设计程序、设计算法，采用一切有效方法来完成工程任务，是研究的目的。对多峰高维单目标函数在有限时间或迭代次数稳定优化[8]将是以后发展的一个重要方向，对多目标函数优化也成为研究热点[9]。
4、小结
本文从遗传算法的起源入手，介绍了它的基本原理。详细介绍了影响算法的主要因素及其相应改进的方法。也介绍遗传算法的需要改进的地方，这也是以后发展的一种趋势。说明了在实际的应用方向及其广泛通用，遗传算法已经是一种基本成熟的算法，主要是对搜索空间的广度和对一个最优解持续优化这深度求解，然而应用的广泛性及自身还有一些的不足，进行进一步深入研究也是必要的。
参考文献
[1] 张文修.梁怡.遗传算法的数学基础[M].西安：西安交通大学出版社,2003.
[2] 李敏强,寇纪淞等.基于实数编码的遗传算法的收敛性研究[J].计算机研究与发展.2000,37(11):1321～1326.
[3] 金菊良,魏一鸣等.计算层次分析法中排序权值的加速遗传算法[J].系统工程理论与实践.2002,(11):39～43.
[4] 黄焱,蒋培,王嘉松等.基于可调变异算子求解遗传算法的欺骗问题[J].软件学报.1999.10(2):216～210.
[5] 陈小平,于盛林.实数遗传算法交叉策略的改进[J].电子学报.2003.31(1):71～74.
[6] 李航.遗传算法求解多模态优化问题的研究.天津大学博士论文.2007.
[7] 玄光男.程润伟.于歆杰等.遗传算法与工程优化[M].北京:清华大学出版社,2004.
[8] 肖赤心.高维优化进化算法及其应用研究.中南大学博士论文.2009.
[9] 崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社,2006.
【关键词】编码 交叉 变异 遗传算法
1、遗传算法的起源
遗传算法是霍兰(J. H. Holland, 1975) 提出[1]，通过模拟生物的进化过程，运用启发搜索规则，把一组模型中优良个体生存和随机变异的信息交换结合在一起。从一组初始模型出发，根据给定的参数变化范围及变化步长，将每个模型的全部参数用许多串联在一起的二进制编码(或其他编码) 串表示，通过选择、交叉互换和变异不断保留优势特征，最后得到问题的最优解。其不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解，它利用某种编码技术，作用于染色体的字符串，模拟由这些串组成的群体的进化过程。具有以下特点：对可行解的表示广泛；具有群体并行搜索特性；具有很强的鲁棒性；然而它也有一些不足，它的编码不规则及编码存在的不准确性，其搜索的计算量大且搜索效率低，出现早熟收敛等等，严重影响了遗传算法的应用，也是需要解决和改进研究的地方。进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题，成为求解全局优化问题的有力工具之一。
在基本理论发展方面来说，模式定理和积木块假设是遗传算法有效的理论依据。模式定理保证了较优先的模式样本呈指数级增长，从而满足了寻找最优解得必要条件，即遗传算法存在着找到全局最优解得可能性。而积木块假设指出，遗传算法所具备寻找到全局最优解得能力，即具有低阶、短距、高平均适应度的模式在遗传算子的作用下，相互结合，能生成高阶、长距、低适应度模式，最终求得全局最优解。遗传算法全局收敛性分析取得了很大进展，文献[1]给出了基于二进制编码的收敛性经典结果及在群体无限大的假设下，讨论了分别单独使用交叉和变异算子实数编码遗传算法的收敛性。文献[2]在采用最优个体保留策略的前提下得到了保证收敛的一般条件，并以之检验了采用常用的交叉与变异算子时的实数编码遗传算法的收敛性。总体而言，遗传算法的基础理论研究至今还没有取得突破性进展，理论与应用之间还存在着很大差距。
在算法设计方面发展，遗传算法需要选择的运行参数主要有群体规模，交叉概率、变异概率、终止代数，然而编码方式也对遗传算法的性能有较大的影响。在编码方式的发展，从由二进制编码逐渐发展为十进制编码。参数的控制由静态的设置逐渐演变为动态自适应技术，而交叉、变异算子也不断进行改进，将算法分层[3]或其他算法进行融合，很好的改进了遗传算法。
2、遗传算法的基本原理及实现的主要因素
遗传算法模拟基因重组与进化的自然过程，把待解决的问题的参数进行编码为基因，若干基因组成一个染色体（个体），许多染色体类似于自然选择、配对交叉和变异的运算，经过多次重复迭代直至得到最后的优化结果。遗传算法的实现需要对其进行参数编码、遗传操作运算包括（交叉运算、变异运算、选择运算）、适应度函数设计、参数的控制与约束条件的处理来实现。对各个部分进行良好的处理才能使整个算法性能最佳，寻求出最优解[4～6]。
编码是遗传算法要解决的首要问题。编码就是把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法。为了克服二进制代码之间的汉明距离很大的问题提出格雷码，然而引入了另一层隐悬崖，采用大符号集编码及逐渐提出了十进制编码、动态编码等等编码方式。
交叉运算是按较大概率从种群中选择两个个体，按某种方式相互交换两个个体的某个或某些部分基因，从而形成两个新的个体，其继承了父代的基本特征。它是遗传算法区别于其他进化算法的重要特征，是产生新个体的主要方法，也对算法的收敛性起主要作用。交叉算子的设计和实现与具体的问题密切相关，前面的编码一同考虑，得到一种好的交叉算子是研究者们一直致力于的工作。
变异运算以较小的概率对个体编码串上的某个或某些值进行改变，进而形成新个体。变异本身是一种随机算法，与交叉和选择算子结合能够避免某些信息的丢失，维持种群的多样性防止出现早熟现象，变异的方向性可能引导遗传的方向性，加速最优解得收敛。交叉算子和变异算子相互配合，共同完成对空间的全局搜索和局部搜索，从而使遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。
选择运算对个体进行优胜劣汰，根据每个个体的适应度值大小选择，适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。可以使得到群体中个体的适应值不断接近最优解。选择算子在避免基因损失，提高搜索速度和全局收敛方面有着举足轻重的作用。选择不当会造成群体进化停止不前；或使适应度值偏大的个体误导群体的发展方向，使遗传失去多样性，产生早熟问题。另外，选择与编码方式无关。
适应度函数设计，适应度函数用于转换目标函数值，给每一个个体一个非负的价值数。适应度函数通常根据目标函数采用一定的转换关系来设置。选择运算是根据适应值函数得到结果来进行选择的，其分辨程度对选择及整个算法都有很大的影响。即适应度函数设计不当，有可能造成在遗传进化的初期，超常个体会因竞争力突出而控制选择过程，影响算法的全局优化性能；在遗传进化的后期，种群中个体适应度差异较小时，继续优化的潜能下降，可能获得某个局部最优解，这两种问题的出现。良好的适应度函数能够起到重要作用，是遗传算法设计的一个重要方面。
参数的控制与约束条件的处理，控制参数选择的是否合理直接影响算法的收敛速度和搜索效率，当前没有完善的理论指导它的选择，还主要是根据经验。参数的控制对遗传算法的性能有较大的影响。良好的参数设置可以很好的改进算法的性能，加速算法的收敛。对约束条件进行处理，目前尚无处理各种约束条件的方法，根据具体问题而定，常采用搜索空间限定法，可行解变换法和罚函数法等等。
3、遗传算法发展趋势
遗传算法作为一种优化算法，其目的在于针对目标函数来进行求解未知参量的最优解。对于其研究的方向也是根据其目标函数来如何进行求解得到最优解。即可以应用于能建立出目标函数的任何一领域。对算法本身的性能研究，使算法在其可靠性、计算效率提高；通过不同算法的优点有机结合，形成混合算法；可以根据实际问题建立目标函数选择合适的参数控制及应用范围调整。
基于遗传算法自身的研究，早熟问題使种群失去了进化能力，是目前最难解决的问题。通常的表现是群体中所有的个体进化一定的代数后就陷于同一极值而停止进化了，或者接近最优解的个体总是被淘汰，找不到最优解。然而它的编码不规则及编码存在的不准确性，其搜索的计算量大且搜索效率低等等，也严重影响了遗传算法的应用。需要设计出良好的编码、良好的选择方式及良好的交叉、变异算子来改进算法中的不中之处。
遗传算法与其他计算智能方法的相互渗透和结合[7]。如遗传算法与模糊推理以及混沌理论、与传统算法、神经网络算法、粒子群算法、蚁群算法等等其他智能计算方法相互渗透和结合，必能达到取长补短的作用。混合算法的实质是通过不同算法的优点有机结合，改善单纯算法的性能。
然而随着实际问题难度的增加，对遗传算法本身的不足逐渐显露，即需要进一步改进，如单目标函数不在是以前的单峰一维或多峰单维或单峰多维，而是多峰多维且维数的增高，对求解的问题难度将急剧增加。针对不同问题采用重新设计程序、设计算法，采用一切有效方法来完成工程任务，是研究的目的。对多峰高维单目标函数在有限时间或迭代次数稳定优化[8]将是以后发展的一个重要方向，对多目标函数优化也成为研究热点[9]。
4、小结
本文从遗传算法的起源入手，介绍了它的基本原理。详细介绍了影响算法的主要因素及其相应改进的方法。也介绍遗传算法的需要改进的地方，这也是以后发展的一种趋势。说明了在实际的应用方向及其广泛通用，遗传算法已经是一种基本成熟的算法，主要是对搜索空间的广度和对一个最优解持续优化这深度求解，然而应用的广泛性及自身还有一些的不足，进行进一步深入研究也是必要的。
参考文献
[1] 张文修.梁怡.遗传算法的数学基础[M].西安：西安交通大学出版社,2003.
[2] 李敏强,寇纪淞等.基于实数编码的遗传算法的收敛性研究[J].计算机研究与发展.2000,37(11):1321～1326.
[3] 金菊良,魏一鸣等.计算层次分析法中排序权值的加速遗传算法[J].系统工程理论与实践.2002,(11):39～43.
[4] 黄焱,蒋培,王嘉松等.基于可调变异算子求解遗传算法的欺骗问题[J].软件学报.1999.10(2):216～210.
[5] 陈小平,于盛林.实数遗传算法交叉策略的改进[J].电子学报.2003.31(1):71～74.
[6] 李航.遗传算法求解多模态优化问题的研究.天津大学博士论文.2007.
[7] 玄光男.程润伟.于歆杰等.遗传算法与工程优化[M].北京:清华大学出版社,2004.
[8] 肖赤心.高维优化进化算法及其应用研究.中南大学博士论文.2009.
[9] 崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社,2006.