简述遗传算法的基本原理范例(3篇)

简述遗传算法的基本原理范文

关键词：遗传算法；最优路径；旅行商问题；C++指针

1概述

“旅行商问题”常被称为“旅行推销员问题”，指的是需要有一个推销员拜访多个地点，如何找到时间来访问每个地点，然后返回到最短路径的起点。规则是简单的，但增加了位置的数量后，解决极为复杂。以42个地点举例，以确定是否要列出所有最好的旅游路线，然后计算总路径大，几乎难以计数。多年来全球数学家竭尽全力，试图找到一个高效的算法。在文章中，基于遗传算法寻求TSP问题的更优解决。

2遗传算法介绍

2.1遗传算法的机理

在遗传算法中，优化问题的解决方案被称为个体，它可表示为染色体或基因串。染色体通常可以表示为一个简单的字符串或数字串，这个过程称为编码处理。算法随机生成一定数量的个体。在每一代均可以被评估，并通过计算获得适应度值。之后个体和群体组成的下一代。这个过程是通过（crossover）和突变（mutation）来实现。根据一项新的个体适应选择，这个过程被重复：每个个体进行评价，计算两个个体的适合度进行，然后突变，形成第三代。周而复始，直到终止条件出现。

2.2遗传算法的实施步骤

（1）选择一个编码；给出一个有N个染色体的出事群体pop，t：=1。

（2）对群体pop（t）中每一个染色体计算它的适应函数fi=fitness（popi（t））。

（3）若停止的规则满足，则算法会停止；否则，计算概率

，i=1，2，…，N，

并以概率的分布（9）从pop（t）随机选染色体来构成一个新种群

NewPOP（t+1）={popi（t）1j=1，2，…，N}

（4）通过得到一个拥有N个染色体的CrossPOP（t+1）。

（5）用一个较小概率p，将一个染色体一个基因发生突变，形成MutePOP（t+1）；t：=t+1，一个新的群体POP（t）=MutePOP（t）产生；返回2步。

3遗传算法求解旅行商问题

3.1编码

由于遗传算法不能直接处理空间数据的问题，所以我们要质疑的空间数据被映射到数据串型空间的遗传结构，而基因型字符串变换算法程序结构可以处理基因数据的空间。例如，计算现在北京，广东，天津，新疆四个城市，但算法不直接处理与北京，广东，天津，新疆，这些数据，所以我们给他们编号，北京（0），广东（1），天津（2），新疆（3），路径（广东新疆北京天津）可以将其表示为一个字符串结构型数据（1302）。

（1）二进制编码化，基因代码用0、1表示。例如：基因A：01100100011（代表一个个体的染色体）

（2）编码的互换（用于解决排序）。例如旅行商问题中，一串新的基因编码用来表示遍历的城市顺序，如：6783401295，表示这九个城市中，要先经过城市6，再经过城市7，依此类推。

（3）值的编码。在值的编码中，每以个基因就是一串新值。这些新值可以是与问题相关的任何值。

3.2适应度函数和选择

遗传算法是好还是坏的适应度函数值来评估一个个体的，适应度函数值越大，质量越好。在本实施例中，采用的适应度比例法是遗传算法是最常见基本的选择方法，即选择每个单独的概率成正比其适应值。

3.3交叉的过程

生物的进化是生物基因重组的中心作用，遗传算法是核心操作系统交叉，即所谓的交指结构的两个或更多亲本部分由个体重组操作代替生成一个新的个体。

文章采用匹配交叉（PMX）法：先随机产生两个新的交叉点，再定义这两点间区域为匹配区域，并交换两个父代匹配区域。

父代A项：132|468|7638

父代B项：983|567|3694

变换为：

TEMPA项：132|567|7638

TEMPB项：983|468|3694

对于TEMPA、TEMPB中匹配区域以外出现数码的重复，要依据匹配区域内的位置进行逐一替换。匹配关系：153670

子代A项：532|567|0668

子代B项：986|468|6394

3.4变异

变异性是指特定基因编码的字符串被替换为另一种基因突变的概率值的基础上，对各个值，以形成一个新的个体。GA的变异操作是产生新个体辅助方法，它决定了GA局部搜索的能力，同时还能保持种群的多样性。

基本位变异算指随机分配到一个单独的代码串或几个基因的某些突变操作。用于通过如果值为0的原始基因位点的突变，然后将它变成一个突变操作所需的二进制个体表示为1；即1到0，0到1。

变异前：

010001010010100010000

变异后：

001001010001010010001

3.5其他运行参数选择

GA运行参数应根据具体的问题进行选择处理，并固定，算法参数到目前为止，没有一个为所有的应用领域的GA理论能适用。下面是使用GA参数时，一般建议的方法：

（1）交叉率的选择。交叉率一般应该会比较大，推荐会使用85%-96%。（2）变异率的选择。变异率一般应该会比较小，一般使用0.4%-1%最好。（3）遗传运算终止进化代数。个人的想法是设置一个计数器，如果变异连续几代出现最佳个体n值相同（严格来说应该是，最好的个体适应连续的N-代后代种群

4试验及结果分析

实验：

采用的算法各参数设计为：种群规模70，交叉概率0.9，变异概率0.1，保留比例0.6，最大代数20。用上述算法对一个有15个真实城市和真实距离旅行商问题进行求解，要求合理安排行程路线，使总的旅行距离最短。

程序结果最优路径为：

613924314571081101126路径总长度为：15825

计算总耗时：54.735秒

5结束语

（1）随着迭代次数递增，优化结果会逐渐接近最优解，并在最佳值附近来回波动。

（2）交叉概率Pc值均对优化结果的影响较大，从0.8选择值的范围为1.0，可以得到更好的优化效果；突变起到支撑作用，变异概率值只要得到适当，不会对优化结果造成太大影响。

（3）初始种群的选取对优化结果有较大的影响。

参考文献

[1]郭靖扬.旅行商问题概述电子科技大学光电信息学院[J].大众科技，2006.

[2]王海龙，周辉仁，魏颖辉.基于遗传算法的一类旅行商问题研究[J].计算机应用，2009.

[3]王大志，汪定伟，闫杨.一类旅行商问题的计算及仿真分析[J].系统仿真学报，2009.

[4]周辉仁，唐万生，魏颖辉.基于GA的最小旅行时间的旅行商问题研究[J].计算机应用研究，2009.

简述遗传算法的基本原理范文

关键词:医药物流遗传算法路径规划旅行商问题

中图分类号:TP301文献标识码:A文章编号:1009-3044(2010)11-2717-02

医药物流是指医药器械从医药配送中心分发、配送到各个医院和医疗中心的过程,甚至包括通过医院到达消费者(患者)手中的过程,其中所产生的物流成本是医药器械成本的重要组成部分。降低医药运输成本是减少患者医疗负担的重要途径之一。而药物配送实际上就是旅行商问题[1]。遗传算法作为一种求解问题的高效并行全局搜索方法,成为目前解决NP完全问题的较为有效的方法之一。

1旅行商问题与遗传算法

1.1旅行商问题原理

旅行商问题(TravelingSalemanProblem,TSP)是VRP[2]的特例,已证明TSP问题是NP难题。旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题。TSP问题可描述为:给定一组n个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次而且总的旅行路径最短。TSP问题的描述很简单,简言之就是寻找一条最短的遍历n个城市的路径,或者说搜索整数子集X={1,2,…,n}(X中的元素表示对n个城市的编号)的一个排列π(X)={v1,v2,…,vn},使取最小值。式中的d(vi,vi+1)表示城市vi到城市vi+1的距离。

1.2遗传算法基本原理与描述

1.2.1算法原理

遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法,由美国J.Holland教授提出,其主要内容是种群搜索策略和种群中个体之间的信息交换,搜索不依赖于梯度信息。该算法是一种全局搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。

1.2.2算法描述

该算法包括以下6个基本要素:

1)编码:遗传算法不能直接处理解空间的数据,必须通过编码将它们表示成基因型串数据。常对参数采用二进制编码,编码当作一条染色体,编码前应先量化[3]。

2)生成初始种群:初始种群的个体通过随机方法产生,且对应研究问题的一个解。

3)评估适应度:遗传算法在搜索过程中用适应度来评估个体的优劣,并把它作为遗传操作的依据。适应度函数常取非负数,且适应度增大的方向与目标函数的优化方向一致。

4)选择:根据适者生存的选择原理,从当前种群中选择生命力强的个体(即适应度高的个体),产生新的种群。适应度越高的个体,被选择的机会就越大,但并不意味着适应度高的个体一定会被选择[4]。

5)交叉:将选择出的个体存入配对库,用随机的方法进行配对,以产生新一代的个体。

6)变异:在交叉过程中可能丢失一些重要的遗传信息(特定位置的0或1)1必须引入适度的变异,即按一定的概率改变染色体基因位。

2优化路径遗传算法的构造

针对优化物流配送路径的特点,本文构造了求解该问题的遗传算法。

2.1初始种群的生成与编码方法的选定

随机生成规模为N的初始种群。采用巡回旅行路线所经过的各个城市的顺序排,列来表示各个个体的编码串,这是TSP问题最自然的一种个体编码方式。例如对于一个10个城市的TSP:2-5-3-4-7-1-6-8-9(可简单表示为[253471698]),表示从城市2出发依次经过城市5,3,4,7,1,6,8,9,然后返回城市2的一条路径。这种编码方式满足TSP问题的约束条件,保证了每个城市经过且只经过一次,在任何一个城市子集中不形成回路[5]。

2.2适应度评估

对于某条染色体,设其对应的配送路径方案的不可行路径数为Ni(Ni=0表示该个体对应一个可行解),其目标函数7值为Td,则该个体的适应度可用下式表示:,式中α为对每条不可行路径的惩罚权重,可根据目标函数的取值范围取一个相对较大的正数(α值太小则会影响适应度的比较)。

2.3遗传操作

2.4.1选择操作

选择将使适应度较大个体有较大的存在机会,而适应度较小的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制,令Σfi表示群体的适应度值之总和,fi表示种群中第i个染色体的适应度值,它产生后代的能力正好为其适应度值所占份额fi/Σfi。作为其被选中的概率Psi。这方法既可保证最优个体生存至下一代,又能保证适应度较大的个体以较大的机会进入下一代。

2.4.2杂交操作

采用顺序编码法后,若用简单的一点杂交或多点杂交,必然会导致未能完全遍历所有城市的非法路径。如城市9的TSP问题的两个父路径为:1234|56789;9876|54321,若采取一点杂交,杂交点随机选为4,则杂交产生的两个后代为:9876|56789;1234|54321,显然,这两个子路径均未能遍历所有9个城市都违反了TSP问题的约束条件,为解决这一问题,既要进行杂交操作,又要满足约束条件,就必须对杂交操作进行修正[6]。关于路径表示的常用的几种修正的杂交操作方法为:

1)部分映射杂交(PMX,partially-mappedcross-over)。

在PMX操作中,先随机地在父体中选取两杂交点,并交换相应段。再根据段内的城市确定部分映射。在每父体中先填入无冲突的城市,而对有冲突的城市分别执行这些部分映射直到填入无冲突,则获得杂交后的两后代。例如,两父体A1、A2为('|'标记截断点)A1=(264|7358|91),A2=(452|1876|93)。则由交换段确定的部分映射为:7-1,3-8,5-7,8-6,先交换相应的段得B1=(###|1876|##),B2=(###|7358|##)。此处'#'表示城市待定。再从各自的父体中填入无冲突的城市得B1=(2#4|1876|9#),B2=(4#2|7358|9#)。个体B1第一个'#'处原处为6,映射到8后仍有冲突,再将8映到3填入。第二个'#'处原处为1,映射到7后仍有冲突,再将7映到5填入。类似地求得B2。于是两后代为B1=(234|1876|95),B2=(412|7358|96)。这样,子代仍是遍历的,但每个子代的次序部分地由其父代确定。

2)次序杂交(OX,ordercrossover)。

次序杂交的操作与部分映射杂交的操作非常类似。也是首先随机地在父体中选择两杂交点,再交换杂交段,其它位置根据保持父体中城市的相对次序来确定。例如,设两父体及杂交点仍为前述的A1和A2,A1=(264|7358|91),A2=(452|1876|93)。交换杂交段于是仍有B1=(###|1876|##),B2=(###|7358|##)。从B1的第二个杂交点开始,将路径依原次序排列,即:9-1-2-6-4-7-3-5-8去除杂交段中的城市,得子路径9-2-4-3-5。依次顺序从第二个杂点开始填入得B1=(435|1876|92),类似地有B2=(216|7358|94),虽然,PMX法与OX法非常类似,但它们处理相似特性的手段却不同。PMX法趋向于所期望的绝对城市位置。本算法采用此方法交杂交。

3)循环杂交(CX,cyclecrossover)

循环杂交将另一父体作为参照以对当前父体中的城市进行重组。先与另一父体实现一个循环链,并将对应的城市填入相应的位置。循环组成后,再将另一父体的城市填入相同的位置。例如,仍考虑前两个父体路径A1=(264735891),A2=(452187693)。先从A1中取第1个城市作为B1的起始点,于是B1=(2########),由于后代中第一个城市都必须从父体相同位置的城市中选取,于是根据循环原则,2对应于A2中的城市4,而在A1中位于第3位,所以应有B1=(2#4######),又A1中城市4对应于A2中的2,于是组成了一个环。再将A2中剩余的城市填入对应的相同位置得到B1=(254187693),类似地可得到B2=(462735891),由此可见,循环杂交保持其父体串中城市所处的绝对位置。

3算法实现和结果

下面对某市一医药公司的销售点的物流配送路径规划用遗传算法进行优化。该公司有56处销售点,通过路径规划希望找出最优路径以节省运输成本。

3.1运行参数设计

本实验采用n城市的遍历顺序编码法,适应度函数取总长度Td的倒数(无惩罚函数)。选择机制是保留M个较优个体,在每一代运算中,个体被选中的概率与其在群体中的相对适应度成正比。杂交操作采用OX(次序杂交)法。为使算法尽快地收敛,在经过杂交变异操作后,增加了局部优化过程,提高个体对环境的适应。群体规模取56,交叉概率和变异概率分别取0.9和0.01,最大迭代数2000。

3.2实验结果

运行环境:操作系统MicrosoftWindowsXP;仿真软件:MierosoftVisualC++6.0。

在实验计算中采用以上设定参数对该公司配送路径问题求解,所得到的优配送化路径最优长度为862,用时126秒,迭代次数1528。得到的路径线路如图1所示。

4结论

在此也可以看到,运用遗传算法解决实际问题,算法是使用参数的编码集,而不是参数本身,参数的选择十分方便;遗传算法与其他计算机算法不同,相比之下,它比较具有随机性而不是稳定性,遗传算法是在点群中,而不是在一个单点寻优。因此利用遗传算法解决实际问题需要选取大量数据,通过多次实验的数据分析不断改进算法和设置参数来求得更优的结果。用遗传算法求解组合优化问题具有巨大的优越性[7]。非常有助于物流企业根据自己的实际情况科学、有效地制定物流决策,降低风险,降低成本,提高经济效益和自身的竞争力。

参考文献:

[1]田贵超,黎明.旅行商问题(TSP)的几种求解方法[J].计算机仿真,2006,23(8):153-157.

[2]HollandJH.Adaptationinnaturalandartificialsystems[M].AnnArbor,Ml:TheUniversityMichiganPress,1975.

[3]余有明,刘玉树.遗传算法的编码理论与应用[J].计算机工程与应用,2006,42(3):86-89.

[4]陈国良,王煦法,庄镇泉,等.遗传算法及其应用[M].北京:人民邮电出版社,1996.

[5]唐坤.车辆路径问题中的遗传算法设计[J].东北大学学报:自然科学版,2002,28(1):66-70.

简述遗传算法的基本原理范文篇3

关键词：遗传算法；早熟；遗传算子；小种群并行

中图分类号：TP312文献标识码：A文章编号：16727800（2013）002003302

0引言

遗传算法最早是由Michigan大学的J・Holland教授于1975年提出的一种基于生物进化机制的自适应算法，适用于各类复杂系统的优化计算。遗传算法本身具有很多优点，如简单易行、通用性强、鲁棒性高、全局搜索能力强等，这些优点使其可以应用于大量复杂问题求解当中。然而遗传算法固有的一些缺陷如：过早收敛、容易陷入局部最优、算法运行后期搜索效率较低等，也不可避免地制约了遗传算法的使用与推广。

对于全局范围的搜索算法而言，早熟现象的产生是其失败的主要原因。种群的规模在很大程度上决定遗传算法应用的成功与否。种群数目过小会导致算法收敛速度过快，往往来不及找到全局最优解；种群数目过大会消耗过多的进化和处理时间，使得算法运行异常缓慢。

为了更好地使用遗传算法处理实际问题，长期以来人们在标准遗传算法（SGA）的基础上做了大量的研究和尝试，并且取得了巨大的成效。其改进方法包括对遗传算子的改进、增强算法的自适应性、与其它智能算法搭配使用等，然而很多改进方法却使得算法变得较为复杂，从而失去了遗传算法简单易用的特点。本文在此提出一种新的基于小种群并行的改进型遗传算法：一方面针对实际应用中的一些问题对标准遗传算法的遗传算子加以改进，另一方面提出在个体总量相同的条件下，采用多个小种群并行运算，并在各种群间产生交互的方法，确保在尽可能保持计算简单性的前提下，防止遗传算法中早熟现象的产生。

1遗传算子的改进

交叉算子是遗传算子中最为重要的组成部分，其不仅对遗传算子的收敛性起到了至关重要的作用，同时也对遗传算法的收敛速度有很大的影响。传统交叉算子的操作往往具有一定的盲目性，亲代染色体交叉互换后所形成的子代很可能将亲代个体中所具备的优良基因模式丢弃或者破坏了。本文提出一种改进的交叉算子方案，以便以较大的可能性保护亲代个体的优秀基因模式并使之得以传递至子代个体。

在此使用相似程度的概念，通过相似程度的高低来决定是否进行交叉操作。首先给出相似度的定义，假设有两个二进制编码的父代个体，分别记作个体X和个体Y，则此二者的相似程度定义如下：

定义1相似程度：

ε=a/n

（1）

其中ε表示个体X和个体Y的相似程度，a表示两个体之间最大相同位串的数目，n表示个体染色体编码的长度。举例来说，例如个体X的染色体编码为1010110010，个体Y的染色体编码为1000101001，则二者的最大相同位串数目a为5，而个体染色体编码长度n为10，则个体X与个体Y的相似程度ε为5/10，即0.5。显然，同一种群中任意两个个体的相似程度为一个处于两者之间的数。

为了判别是否进行交叉操作，需要用到一个临界值作为参照对象，在此本文给出另一个概念标准交叉点定义2：

K=（G+2g）/3G

（2）

其中K为标准交叉点的值，G表示此种群预先设定的总进化代数，g表示算法到目前为止已运行的代数。由上述公式显然可知，标准交叉点K的值是动态变化的，其值随着当前种群进化代数的增长而不断增大，而预先设定的总进化代数对标准交叉点K的变化也有较大影响。当被选中参与交叉运算的两个个体的相似程度ε小于或等于K值时，则进行染色体的交叉互换操作；而当相似程度ε大于K的值时，则不允许二者进行交叉互换操作，而是克隆本身，复制产生与二者完全相同的子代个体。在遗传算法运行的初期，随即生成的种群个体之间的相似程度较低，为了控制交叉率，以便在确保种群得到充分进化的前提下尽量不破坏个体中的优秀基因模式，标准交叉点的值K应当相对较小，反之在遗传算法运行的后期，种群进化了多代，此时个体间差异已经较小，相似程度较高，故而标准交叉点的值K也应当随之提高。根据上述公式，动态控制父代染色体标准交叉点的移动，有助于提高遗传算法的收敛性能和收敛速度。为了简便以及更好地评价本文提出的改进方法，当一组亲代个体的染色体通过标准交叉点的比较判断后，本文使用传统的单点交叉方法来对它们进行交叉互换操作。

2基于小种群并行的算法方案

种群的规模是决定遗传算法能否成功使用的一个重要原因，显然无论种群的规模过大或是过小，均不可能令算法最终得到一个令人满意的全局最优解。种群规模过小会导致所得到解的准确性和可信性难以得到保证，而种群规模过大则会使得遗传算法的收敛速度过低，且在运行代数不足的前提下仍然不能确保得到准确的全局最优解，这更加降低了遗传算法的运行效率，据此，本文提出一种基于小种群并行的改进型遗传算法。区别于传统的遗传算法，新方案将在初始化的过程中同时建立多个个体数量完全相同而染色体编码彼此之间完全不同的相对规模较小的种群，以此实现在不影响算法运行总体效率的前提下，提高算法的全局搜索能力。算法流程描述如下：

（1）依据实际问题的需要建立一个由n个种群组成的集合，每个种群中包含由染色体编码组成完全不同的m个个体。

（2）根据上文中已经给出的对于遗传算子的改进方案，在每个小规模的种群内部进行一次独立的遗传运算。即从种群1开始，每个种群均进行一次使用上文中改进遗传算子的遗传运算过程，得到下一代种群个体，直到n个种群均完成了上述运算。

（3）对种群中各个个体的相对适应度进行计算，并选择出每个种群中相对适应度最高的个体，得到的n个个体按照来源的种群编号为1至n，称为优秀个体。

（4）使用得到的每一个优秀个体与剩余的所有优秀个体分别进行杂交，即杂交（n-1）次。对n个优秀个体分别进行此项杂交操作，根据下文中的杂交规则，在杂交完成后即产生新一代的种群。

（5）判断算法此时的运行结果是否满足终止条件，如满足则终止算法，如不满足则转向步骤（2）。

关于上述算法，说明如下：

（1）步骤（1）中初始化的方式可以为先随机生成m*n个完全不同的个体，然后再随机将它们分配进入n个种群当中，每个种群分配m个个体即可。分配完成后，此n个种群随机编号为从1至n号，并记为种群1至种群n，此时种群内的个体即为第一代个体。

（2）步骤（4）中的杂交规则举例说明如下：编号1的优秀个体与编号2至n的优秀个体分别杂交，当其与优秀个体2进行杂交时，得到两个新的子代个体，此时计算两个新个体与优秀个体1和优秀个体2的相似程度。其中与优秀个体1相似程度高的子代个体记为个体1（2），与优秀个体2相似程度高的子代个体记为个体2（1）。如果两个子代个体均与某一优秀个体的相似程度高或与两个优秀个体的相似程度相同，则随机将子代个体中的某一个记作1（2），另一个记作2（1）。以上面方法依次进行杂交，则可分别得到新的子代个体1（2）至1（n）。同理，在经过相互间的杂交后，还可以得到新的子代个体2（1）、2（3）…2（n）直至n（1）…n（n-1）。计算个体1（2）至1（n）的相对适应程度，在得到的结果中选择相对适应度最大的一个子代，并将其作为新的优秀个体1，并根据上述方法逐步得到新的优秀个体2至优秀个体n。最后，将此时得到的新优秀个体1至n根据编号带入相应的下一代种群1至n，从而得到新的下一代种群。

（3）由于新算法中选取的每个小种群中的个体数量较少，故而算法的全局搜索能力由优秀个体之间的杂交来保证，而收敛速度和收敛性能则主要由算法中针对遗传算子的改进来保证。

3算法测试

为了验证新算法的性能，本文将选用两个常见的优化函数对其进行测试，并使用标准遗传算法与之同时测试以作参照。

测试函数1：

maxf1（x1，x2）=100（x21-x22）2+（1-x1）2，-2.048≤xi≤2.048（i=1，2）；f1有2个局部最大点，即f1（2.048，-2.048）=3897.7342，f1（-2.048，-2.048）=3905.926；其中后者为该函数的全局最大点；

测试函数2：

minf1（x1，x2）=（4-2.1x21+x41/3）x21+x1x2+（-4+4x22）x22≤3，-3≤x1≤3，-2≤x2≤2；f2有6个局部最小点，其中（-0.0898，0.7126）和（0.0898，0.7126）为该函数的全局最小点。

算法测试过程中，标准遗传算法记为SGA，本文提出的基于小种群并行的改进遗传算法记为IGA。算法运行过程中，SGA分别使用赌选择和单点交叉进行选择和交叉操作，其中交叉概率取0.7。IGA则根据本文提出的新算法进行运算。其中SGA设定初始种群数为100，IGA则初始化为5个小种群，每个小种群包含20个个体。算法运行的最大进化代数为200，变异概率为0.05，当搜索到的最优解与理想极值的误差小于e-3，则可认为算法已经成功收敛并停止进化。

根据对比结果可以看出，本文提出的基于小种群并行的改进遗传算法可以有效抑制早熟现象的发生，并可以减少收敛时间，以相对较少的遗传代数得到最优解，从而提高算法的执行效率。

4结论

本文针对标准遗传算法易早熟，算法运行后期搜索效率较低等问题，提出了一种基于小种群策略的并行遗传算法。通过对交叉算子的修正，以及多个小规模种群并行优化求解的方案，使得算法的执行效率得到了提高，并且在一定程度上解决了标准遗传算法运行过程中收敛速度与易得到局部最优解之间的矛盾。在对两种算法进行测试后，仿真结果显示本文提出的改进算法较于标准遗传算法性能更好。

参考文献：

＼[1＼]HOLLANDJH.Adaptationinnatureandartificialsystem＼[M＼].Masscchusetts：MasscchusettsInsitituteofTechnology，1992.

＼[2＼]MSRINIVAS，LPATNAIK.Adaptiveprobabilitiesofcrossoverandmutationingeneticalgorithm＼[J＼].IEEETrans.OnSystems，Man，andCybernetics，1994.