遗传算法论文范文10篇

编者按：本文主要从单亲演化过程；群体演化过程；实验结果与分析；结束语四个方面进行论述。其中，主要包括：TSP的搜索空间是有限的、很可能不存在确定的算法能在多项式时间内求到问题的解、遗传算法是一种借鉴生物界自然选择和遗传机制的随机化搜索算法、用遗传算法求解TSP能得到令人满意的结果、个体质量的高低决定了算法的全局性能、TSP编码表示、构建TSP基因库、单亲演化算法、基因段错位操作是随机确定基因段、交叉算子、局部启发式算子、选择机制和收敛准则、基于多重搜索策略的群体演化算法、所有的结果都是在P42.0G微机上完成、该文算法的求解质量要优于GA、PGA、MMGA算法等，具体材料请详见。

论文摘要：TSP是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(GB—MGA),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际TSP库中多个实例的测试,结果表明:算法(GB—MGA)加快了遗传算法的收敛速度,也加强了算法的寻优能力。

论文关键词：旅行商问题遗传算法基因库多重搜索策略

TSP(travelingsalesmanproblem)可以简述为:有n个城市1,2,…,n,一旅行商从某一城市出发,环游所有城市后回到原出发地,且各城市只能经过一次,要求找出一条最短路线。TSP的搜索空间是有限的,如果时间不受限制的话,在理论上这种问题终会找到最优解,但对于稍大规模的TSP,时间上的代价往往是无法接受的。这是一个典型的组合最优化问题,已被证明是NP难问题,即很可能不存在确定的算法能在多项式时间内求到问题的解[1]。由于TSP在工程领域有着广泛的应用,如货物运输、加工调度、网络通讯、电气布线、管道铺设等,因而吸引了众多领域的学者对它进行研究。TSP的求解方法种类繁多,主要有贪婪法、穷举法、免疫算法[2]、蚂蚁算法[3]、模拟退火算法、遗传算法等。

遗传算法是一种借鉴生物界自然选择和遗传机制的随机化搜索算法,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息[4]。遗传算法主要包括选择、交叉和变异3个操作算子,它是一种全局化搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。遗传算法虽然不能保证在有限的时间内获得最优解,但随机地选择充分多个解验证后,错误的概率会降到可以接受的程度。

用遗传算法求解TSP能得到令人满意的结果,但是其收敛速度较慢,而且种群在交叉算子作用下,会陷入局部解。采用局部启发式搜索算法等,虽然能在很短的时间内计算出小规模城市的高质量解,一旦城市规模稍大就容易陷入局部最优解。因此,为了能够加快遗传算法的收敛速度,又能得到更好的近似最优解,该文采纳了文[5]中杨辉提出的基因库的想法,并结合文[6]中Cheng-FaTsai提出的多重搜索策略思想,使用单亲演化与群体演化相结合的方式来求解TSP问题。该文根据文[7]中最小生成树MST(minimumcostspanningtree)的应用,由MST建立TSP的基因库,保存有希望成为最优解的边,利用基因库提高初始群体的质量进行单亲演化,然后利用改进后的交叉算子和的多重搜索策略进行群体演化。

遗传算法的思想由来已久。早在20世纪50年代，一些生物学家就着手于计算机模拟生物的遗传系统。1967年，美国芝加哥大学的Holland,J.H.教授在研究适应系统时，进一步涉及进化演算的思考，并于1968年提出模式理论。1975年，Holland教授的专著《自然界和人工系统的适应性》问世，全面地介绍了遗传算法，为遗传算法奠定了基础[228]。此后，遗传算法无论在理论研究方面，还是实际应用方面都有了长足发展。

伴随遗传算法的发展，其独特的优越性逐渐被体现出来，且各种理论、方法都得到了进一步发展和完善。但是，遗传算法的实际应用仍然存在着缺陷，具体表现在：

遗传算法在寻优过程中易出现“早熟”、设计变量增多时效率较低以及结构分析时间长，在线功能差。为此，在实际运用中尚需改进，寻找更优秀的算子和编码方法等。目前，改进的方法也各有优劣，有对遗传算法遗传算子进行改进的，也有将遗传算法与其他方法结合起来的。编码方法有二进制编码、多值编码、实值编码、区间值编码、Delta编码等多种编码方法。在执行策略方面有如下几种方法值得注意：遗传算法与模拟退火算法的结合、遗传算法与局部优化方法的结合、并行遗传算法、共存演化遗传算法、混乱遗传算法。

遗传算法的噪声适应性问题。遗传算法主要是针对无噪声的确定性环境设计的，在应用过程中，知识的不确定性、训练样本的错误、人为因素等都可导致问题求解环境包含一个或多个噪声。事实上，噪声是不可避免的，在实际工程测量中，测量得到的静态应变常常会伴有一定的噪声。遗传算法的进化过程是通过适应度大小来进行选择、变异、交*等遗传算子操作，从而对个体进行优胜劣汰。然而在噪声环境下，目标函数或适应度带有噪声，不能反映个体真正的适应度。显然，用有噪声的适应度去进化，其结果可能会被误导。在这种情况下，遗传算法的性能如何，怎样改进，还有待深入研究。

摘要本文通过对基本遗传算法添加初始化启发信息、改进交叉算子和利用本身所固有的并行性构架粗粒度并行遗传算法等方法提高了遗传算法的收敛性及其寻优能力。

关键词遗传算法；TSP；交叉算子

1引言

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说来，遗传算法是按不依赖于问题本身的方式去求解问题。它的目标是搜索这个多维、高度非线性空间以找到具有最优适应值(即最小费用的)的点[1]。

基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子和变异算子作用于种群，最终可得到问题的最优解和近似最优解。

2遗传算法程序设计改进比较

1遗传算法设计

1．1基因编码设计

编码就是将遗传算法中处理不了的空间参数转换成遗传空间的由基因组成的染色体或个体的过程．其中基因在一定意义上包含了它所代表的问题的解．基因的编码方式有很多，这也取决于要解决的问题本身．常见的编码方式有：二进制编码，基因用0或1表示，通常用于解决01背包问题，如基因A：00100011010（代表一个个体的染色体）；互换编码，主要用于解决排序问题，如调度问题和旅行商问题，用一串基因编码来表示遍历城市顺序，如234517986，表示在9个城市中先经过城市2，再经过城市3，依此类推；树形编码，用于遗传规划的演化编程或表示，其编码的方法就是树形结构中的一些函数，本文采用的是树形编码．

1．2交叉算子设计

交叉运算的含义是参照某种方式和交叉概率，将两组相互配对的个体互换部分基因，生成新个体的过程．交叉运算在遗传算法中起关键作用，是产生新个体的主要方法．交叉操作流程如图1所示．交叉操作首先判定要交叉的基因是否相同，如果相同进行子基因组的交叉，然后再判定交叉是否完成，没完成就继续，完成就退出；如果交叉的基因不相同，就要选择是否依据概率进行基因交换，选择交换就交换其所有的次级基因结构，然后再判定交叉是否完成，选择不交换就直接判定交叉是否完成．

1．3变异算子设计

摘要：本文运用遗传算法的全局寻优对考试中的自动化组卷进行了研究，并得到了一个解决适合考方要求的试题模型的好的算法。

关键词：遗传算法全局寻优自动化组卷

1引言

计算机辅助考试系统的自动组卷的效率与质量完全取决于抽题算法的设计。如何设计一个算法从题库中既快又好的抽出一组最佳解或是抽出一组非常接近最佳解的实体，涉及到一个全局寻优和收敛速度快慢的的问题，很多学者对其进行了研究。遗传算法以其自适应寻优及良好的智能搜索技术，受到了广泛的运用。PottsJC等人基于变异和人工选择的遗传算法对最优群体规模进行了论述；HamiltonMA等结合遗传算法把其运用到神经网络中，并取得了良好的效果[4]；也有众多的学者对保留最佳状态的遗传算法的收敛速度做了讨论。通过理论推导和事实运用，发现遗传算法在寻优和收敛性方面都是非常有效的。

本文结合遗传算法的原理和思想，对考试自动出题组卷的问题进行了研究，找到了一种获得与考试试题控制指标符合的试题模型的解决方法。

2问题描述

摘要在浮点编码遗传算法中加入Powell方法，构成适于不可微函数全局优化的混合遗传算法。混合算法改善了遗传算法的局部搜索能力，显著提高了遗传算法求得全局解的概率。由于只利用函数值信息，混合算法是一种求解可微和不可微函数全局优化问题的通用方法。

关键词全局最优；混合算法；遗传算法；Powell方法

1引言

不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（minmax）问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视，常用的算法有模式搜索法、单纯形法、Powell方法等，但是这些方法都是局部优化方法，优化结果与初值有关。

近年来，由Holland研究自然现象与人工系统的自适应行为时，借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法，是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快，在各种问题的求解与应用中展现了其特点和魅力，但是其理论基础还不完善，在理论和应用上暴露出诸多不足和缺陷，如存在收敛速度慢且存在早熟收敛问题[1,2]。为克服这一问题，早在1989年Goldberg就提出混合方法的框架[2]，把GA与传统的、基于知识的启发式搜索技术相结合，来改善基本遗传算法的局部搜索能力，使遗传算法离开早熟收敛状态而继续接近全局最优解。近来，文献[3]和[4]在总结分析已有发展成果的基础上，均指出充分利用遗传算法的大范围搜索性能，与快速收敛的局部优化方法结合构成新的全局优化方法，是目前有待集中研究的问题之一，这种混合策略可以从根本上提高遗传算法计算性能。文献[5]采用牛顿－莱佛森法和遗传算法进行杂交求解旅行商问题，文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题，均取得良好的计算效果，但是不适于不可微函数优化问题。

本文提出把Powell方法融入浮点编码遗传算法，把Powell方法作为与选择、交叉、变异平行的一个算子，构成适于求解不可微函数优化问题的混合遗传算法，该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。

摘要在浮点编码遗传算法中加入Powell方法，构成适于不可微函数全局优化的混合遗传算法。混合算法改善了遗传算法的局部搜索能力，显著提高了遗传算法求得全局解的概率。由于只利用函数值信息，混合算法是一种求解可微和不可微函数全局优化问题的通用方法。

关键词全局最优；混合算法；遗传算法；Powell方法

1引言

不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（minmax）问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视，常用的算法有模式搜索法、单纯形法、Powell方法等，但是这些方法都是局部优化方法，优化结果与初值有关。

近年来，由Holland研究自然现象与人工系统的自适应行为时，借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法，是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快，在各种问题的求解与应用中展现了其特点和魅力，但是其理论基础还不完善，在理论和应用上暴露出诸多不足和缺陷，如存在收敛速度慢且存在早熟收敛问题[1,2]。为克服这一问题，早在1989年Goldberg就提出混合方法的框架[2]，把GA与传统的、基于知识的启发式搜索技术相结合，来改善基本遗传算法的局部搜索能力，使遗传算法离开早熟收敛状态而继续接近全局最优解。近来，文献[3]和[4]在总结分析已有发展成果的基础上，均指出充分利用遗传算法的大范围搜索性能，与快速收敛的局部优化方法结合构成新的全局优化方法，是目前有待集中研究的问题之一，这种混合策略可以从根本上提高遗传算法计算性能。文献[5]采用牛顿－莱佛森法和遗传算法进行杂交求解旅行商问题，文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题，均取得良好的计算效果，但是不适于不可微函数优化问题。

本文提出把Powell方法融入浮点编码遗传算法，把Powell方法作为与选择、交叉、变异平行的一个算子，构成适于求解不可微函数优化问题的混合遗传算法，该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。

摘要：遗传算法是根据生物学上的染色体基因因子构成机制而产生的一种启发式算法。该算法以群体中的所有个体为对象，通过选择、交叉、变异和重排序等类似生物遗传的操作算子，得到满足一定群体适应度的新种群。遗传算法为频率分配问题提供了解决途径。

关键字：频率分配遗传算法GECP组合优化

1.通信网频率分配问题的背景

无线通信设备之间通过相互发射电磁波达成信息沟通。相互通信的设备之间使用特定的频率（信道）构成无线通信链路。由于电磁波的自然特性，无线通信设备发射的电磁波可能对位于附近、满足一定功率和频率条件的其它设备形成干扰。频率分配（FAP）的目的就是给工作在一定地域内的无线通信设备指定使用的工作频率(或信道)，使所有设备都以尽量小的概率被干扰，从而使整个网络的可用性得到优化。FAP可以描述为：对N个给定的待分配工作频率的链路，设G={S1,S2,…Sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值，寻找最优解s*，使任意si∈G，C(s*)=minC（si）。因此FAP是一种组合优化问题。

具体设备频率分配方法虽然会随着设备的工作方式（单工、双工）、工作频段、天线类型、信号的调制解调方式的不同而有所区别，但是大部分频率分配算法都可以转换为等价的图的边着色问题。从图论算法理论上讲，图的广义边着色问题是NPC问题[7]，也就是说无法在多项式时间内求得问题的最优解。例如对于存在n条边的无向图，使用c种颜色对其着色，在没有其它约束条件下，其解空间是cn。即使在不考虑颜色重复使用（c>n）的情况下，其解空间也达到n!。这两者都是超越数，在c和n的值较大的情况下想利用穷举搜索的方法求得问题的最优解在时间上是不可行的。

在工程实践中许多NPC问题使用一些使用的近似算法得到问题的可行解。这些方法包括[]：只对问题的特殊实例求解；动态规划（DP）或者分支界限算法（BC）；概率算法；求近似解；启发式算法（HeufisticAlgorithms）等。这些方法的和核心是分割问题的解空间，按照特定规则搜索典型解作为次最优解。

论文摘要:将一种在在水质评价中得到广泛应用的评价方法——投影寻踪评价法引入生态城市评价领域中。采用基于实数遗传算法的投影寻踪评价法，以生态城市课题组建立的指标体系(指标涉及资源，经济，社会，环境，体制等各方面因素)为基础，利用M棚AB软件对石家庄市2000~~2007年的生态城市建设进行了评价。

论文关键词:投影寻踪法；生态城市评价；石家庄市

“生态城市”是20世纪80年代产生的一个全新概念，指将“生态系统”思想引入到城市建设和管理的过程中。它最早是由前苏联生态学家0．Yanitsky1971年在联合国教科文组织发起“人与生物圈计划(MAB)”时提出的。之后，很多学者都对其进行了研究，并给出了定义。如1984年城市生态学家0．Yanistky提出，生态城市是指自然、技术、人文充分融合，物质、能量、信息高效利用，人的创造力和生产力得到最大限度的发挥，居民的身心健康和环境质量得到维护，一种生态、高效、和谐的人类聚居新环境。美国生态学家R．Richard认为，生态城市即生态健康的城市，是低污、紧凑、节能、充满活力并与自然和谐共存的聚居地。虽然生态城市的概念尚处于不停的争论、探索、修改、完善之中，但在原则问题上，人们已经达成一些基本共识：“生态城市”的核心思想是它的区域整体观和可持续发展的生态观，且一般要求具有以下几种特性：和谐性、高效性、持续性、整体性、区域性、结构合理以及关系协调。

1生态城市测评方法概述

生态城市评价是生态城市建设的基础工作，一套科学客观的生态城市评价体系应具备以下功能：①帮助在操作层次理解什么是生态城市；②使城市建设转向生态城市建设；③衡量生态城市建设的趋势和速度，综合衡量生态城市各子系统的协调程度。

具体到测评方法而言，不同的测评方法从不同的角度描述指标体系的属性，由于各种方法的机理不同，方法的层次属性相异，在应用不同的测评方法时，测评的结果也存在差异。因此，要反映一个城市的全貌，体现上述生态城市的内涵要求，必须从多角度、全方位进行研究，这样得出的结论才能体现城市系统的本质和原貌。在数学分析方面，系统科学专家运用定量分析技术开发了几十种测评方法。目前，常用的主要有层次分析法(AnalyticHierarchyProcess，AHP)，因子分析法(FactorAnalysis，FA)以及网络层次分析法(ANP)等。但是，这些方法都有其局限性。层次分析法对应生态城市评价是不适用的，因为指标之间是不完备、不互斥的；因子分析法是较常用且简单的方法，能够反映生态城市建设的大概状况，但会丢失部分信息；网络分析法能够比因子分析法更全面地反映生态城市的概况，但其前提是各因子之间的关系比较清晰，这一过程需要作大量的研究工作。该文借鉴在水质评价中得到广泛应用，并被实践证明比较科学、合理的评价方法——投影寻踪评价法，将其应用到生态城市评价体系中。

摘要：复杂函数的全局最优化问题是在求解各种复杂工程与科学计算问题中提炼出来的亟待解决的计算问题，均匀设计具有让试验点在高维空间内均匀分散的特点，而Powell算法具有很好的求解局部最优解的能力，将两种方法进行有效改进后使之相结合，设计出并行全局最优化算法。通过经典的全局最优化函数对算法进行了比较测试，发现该算法具有比以前的算法更好的寻优能力，并对算法时间、空间复杂度以及并行性进行分析和测试。基于均匀设计与Powell算法的全局最优化并行算法具有寻优能力强，时间开销与问题因素个数的平方和布点数成线性复杂度，空间开销与因素个数和布点数成线性复杂度，并行效率好的特点。

关键词：并行计算；均匀设计；Powell算法；全局最优化

0引言

最优化理论方法是应用数学的一门分支，研究决策问题的最佳选择，构造寻找最佳解的计算方法，探讨这些计算方法的理论性质及计算表现。目前，求解线性规划、非线性规划、随机规划、非光滑规划、多目标规划、组合优化等各种最优化问题的新方法不断涌现。除了自然科学的各个领域之外，在建筑设计、金融设计、医药设计、生产管理、交通运输等诸多方面均涉及最优化的应用。随着高速计算机的普及和优化方法的不断进步，规模越来越大的优化问题得到解决。

面对最优化问题，目前的困难主要表现在两个方面：①目标函数常常多峰，随着优化问题规模的增大，局部最优解的数目将会迅速增加，往往得到的是局部最优解，而不能得到全局最优解。如何有效地跳出局部最优点而又不大幅度地增加计算代价，是目前的一个难题。②许多在串行计算环境下的最优化算法并不适合于并行环境，并行化难度大。

首先利用均匀设计具有使实验点高维空间均匀分散的特点，与Powell算法结合，并适当改进，经过经典的全局最优化函数测试发现它能够跳出局部最优陷阱，从而准确地找到全局最优点。最后，对算法的时间空间复杂度进行了测试，数据统计显示本文算法时间复杂度与计算问题需要考虑的因素个数的二次方和布点数成线性关系，空间复杂度与因素个数和布点数成线性关系。对算法进行了并行化，经测试得知并行效率很高。该算法具有很好的求解大型优化问题的潜力。