遗传算法的一种改进实现

遗传算法的一种改进实现

向婷，潘大志，陈友军，杨爽

（西华师范大学数学与信息学院，四川南充 637009）

摘要:遗传算法是模拟生物界的遗传和进化过程而形成的一种自适应全局优化搜索算法.针对基本遗传算法的缺点，从选择、交叉和变异三个算子出发，采取替换部分最差个体、引入小生境思想和集中因子等方式进行处理，提出一种改进的遗传算法（IGA）.通过测试函数Rastrigin确定IGA中的相关参数，并与基本遗传算法比较，体现IGA 的优越性和可行性.

关键词:遗传算法；小生境；集中因子；自适应

中图分类号：TP18 文献标识码:A

1 引言

遗传算法最早由美国密执安大学的Holland教授提出[1]，后由De. Jong进行了大量的纯数值函数优化计算实验[2]，80年代由Goldberg归纳形成基本框架[3].目前，遗传算法由于其运算简单和解决问题的有效能力而被运用到了众多领域，主要体现在优化问题、自动控制、机器人智能控制等领域.

但是，基本遗传算法(GA)存在易早熟、收敛速度慢等缺点.人们也提出了许多改进措施，主要着眼于编码表示、适应度函数、选择策略、控制参数、遗传算子、算法融合等方面.如JaehunLee[4]等提出了染色体矩阵编码方法，实现了遗传算法与贝叶斯网络两种算法的集成和应用；文献[5]中提到的重复串的适应度处理通过选择策略的改变调控并维持种群多样性等.马坚[6]提出基于改进遗传算法的彻底进化神经网络算法，实现对电力变压器故障的快速且准确的判断.

目前，遗传算子的改进是遗传算法改进的焦点与突破口.如文献[7]中的交叉算子将种群逐步向极值点引导，并将惩罚策略与修复策略相结合提出修复算子，提高了算法搜索效率以及对非线性约束的处理能力；唐国新等[8]优化设计了交叉算子和变异算子，并引入了自定义的插入和删除两种操作提高算法的进化效率，已成功应用于机器人路径规划中；Fatemeh Vafaee等人[9]提出的利用差分进化实现遗传算子自适应选择的方法卓有成效，推动了自适应选择的方向发展.本文从遗传算法的三个基本算子出发，采取替换部分最差个体、引入小生境思想和集中因子等方式实现改进，改进算法的收敛速度和稳定性都大为提高，其优势在高维的优化问题中尤为明显.

2 基本遗传算法

遗传算法是建立在达尔文(Darwin)的生物进化论和孟德尔(Mendel)的遗传学说基础上的一种自适应全局优化搜索算法.遗传算法的运算对象是由多个个体组成的集合，称为群体.基本遗传算法中包含了选择、交叉和变异三种算子，其运算过程是运用三种算子的反复迭代过程，最终得到群体的优良个体，它所对应的表现型将达到或者接近于所求问题的最优解.

基本遗传算法的主要步骤如下：

step1. 根据待解问题的参数集进行编码；

step2. 初始化群体；

step3. 计算群体中每个个体的适应度值；

step4. 按照由个体的适应度值所决定的某个规则选择将进入下一代的个体；

收稿日期：2014-06-18

基金项目：四川省教育厅自然科学基金( 14ZA0127，14ZA0134); 西华师范大学博士启动基金（12B022）

作者简介：向婷（1991—），女，四川巴中人，西华师范大学数学与信息学院硕士研究生，主要从事智能计算、数值计算研究

通讯作者：潘大志（1974—），男，四川三台人，西华师范大学数学与信息学院教授，硕士生导师，主要从事智能计算，算法设计研究

step5. 按交叉概率而进行交叉操作； step6. 按变异概率而进行变异操作；

step7. 如果没有满足某种终止条件，则转到第step3，否则进入step8； step8. 输出种群中适应度值最优的染色体作为问题的满意解或最优解.

3 改进的遗传算法

虽然遗传算法被运用到众多领域，理论上也证明了算法能够从概率意义上以随机的方式寻求问题的最优解，但是在遗传算法的应用中仍存在着缺点：易早熟收敛，搜索性能不高，不易达到全局收敛；时间复杂度比较高，搜索的效率比较低.而局部最优和收敛速度往往相互矛盾.为了协调这一矛盾，提高遗传算法的搜索效率的同时保证得到全局最优解，本文从三个基本算子出发，提出了改进的遗传算法（IGA ）. 3.1 选择算子的改进

选择操作在实际的运算初期，对所有个体进行赌盘选择会让算法需要很长时间才能收敛到最优解，影响运算效率.针对这一缺点，将群体中适应度最差的部分个体用适应度较好的个体替换，提高种群的整体适应度.改进的选择算子如下:

Step1. 利用公式（1）计算出个体的赌盘概率，按概率大小对种群中的全部个体进行升序排列，得到最小概率

min p 和最大概率max p ；

∑==M

k k i i F F p 1/ (1)

Step2. 把概率在min p ~)(min max min p p p -+α范围内的N 个低概率个体丢掉，从概率在

)(min max min p p p -+α~max p 范围的个体中随机选择N 个个体加入种群，保证种群大小为M 不变.

Step3. 对种群进行赌盘选择.

其中i F 为第i 个个体的适应度值，α为替换因子.该方法可使每一代中的优良个体得到保护,不良个体被淘汰,以期通过交叉等操作产生更优的个体,让算法的寻优速度得以提高. 3.2 交叉算子的改进

基本遗传算法中关于交叉算子的操作是非常简陋的，且交叉概率为一个恒定不变的数，不会考虑到个体的相似度[10].这种交叉一方面会使部分相似度较高的个体进行交叉，产生的子代和父代差别很小，使得交叉过程作用不大；另一方面在运算后期，恒定的c p 很容易将优良基因模式破坏，使算法不能够收敛或者是收敛速度明显变慢.本文效仿自识别交叉算子[11]，利用小生境的思想，得到了改进的交叉算子，其步骤如下：

Step1. 计算交叉个体i X 和j X 的距离ij s ； Step2. 如果D L s ij

?≤，转step4，否则按公式（2）计算交叉概率：

T

t

P P P P c c c c ?--=)(min 00 (2) Step3. 根据c P 进行交叉操作；

Step4. 交叉操作结束.

其中L 为临界距离系数；D 为问题维数；0c p 为初始交叉概率；m in c p 为最小的交叉概率；t 代表当前迭代次数；T 为终止代数.

当j i s 较大时，父代个体的相似度较低，进入交叉操作.迭代初期，c p 较大，可增强群体的多样化程度，产生很多新的个体.随着迭代次数t 的增加，在进化后期，群体逐渐靠近最优解，此时较小的c p 可以一定程度上保护优良模式的个体，加快算法的收敛速度.

3.3 变异算子的改进

在进化后期，种群中的个体都趋近于最优解，种群的平均适应度和最优个体的适应度非常接近，部分个体也可能处于局部最优点.此时需要施加一个较大的变异概率来增强个体间的竞争力，帮助部分个体跳出局部最优，防止算法停滞不前或陷入局部最优[12]. 改进的变异算子中采用集中因子[13]来描述种群的集中程度，根据集中因子来控制变异概率.改进的变异算子如下：

Step1. 计算种群的集中因子m ：

max max /)(F F F m avg -= （3） Step2. 计算自适应变异概率： T

t

m k p p m m ??-=m a x （4） Step3. 根据

m p 进行变异.

其中max m p 为变异概率的最大值；k 为变异系数.

4 参数选择及算法性能测试

4.1 参数选择

IGA 中共涉及了三个参数，分别是：替换因子α、临界距离系数L 和变异系数k ，本文选用标准测试函数Rastrigin 来确定取值.Rastrigin 函数为：

]12.5,12.5[,)10)2cos(10()(12-∈+-=∑=i n

i i i x x x x f π

该函数是一个多峰函数，当),...,1(0D i x i ==时函数达到全局极小值点，全局极小值为0，在其可行解集},...,1],12.5,12.5[|),..,({1D i x x x X S i D =-∈==内大约存在D 10个局部极小值点.

在利用Rastrigin 函数对IGA 进行测试时设定：8.00=c P ，4.0m in =c P ，3.0m ax =m P ，种群大小40=M ，最大迭代次数2000max =T .通过前期数据处理分析，测试时，α取值为0.2、0.3和0.4， L 取值为0.01、0.05和0.1，k 取值为0.5、1.0、1.5、2.0和2.5，总共构成45种参数取值组合.在每种参数组合下，算法各运行20次，得到各组参数下Rastrigin 函数求解的最优值、最差值、平均值，对运行结果进行分析，确定出参数最佳取值组合.由于维数对算法的求解有一定的影响，为了考察IGA 在不同维数下的求解能力，这里分别考虑了Rastrigin 函数在维数D 分别为

15、20和25下的运行结果.

由于篇幅关系，这里没有给出IGA 算法在45组参数组合下求解Rastrigin 函数的优化结果，而是根据运行得到的基本数据给出分别按α、L 和k 进行均值计算的结果，结果见表1-表3.

表1 不同的替换因子α在L 和k 的15种组合下运行结果的均值

Tab.1 Average value of different alternative factor α under15 kinds of L and k .

α

D=15

Best Worst Avg

D=20 Best Worst Avg

D=25

Best Worst Avg

0.2 0.3 0.4 4.1E-04 1.9E-04 1.2E-04

7.0435 6.1284 5.5128 1.6800 1.5283 1.3888 1.0266 0.6750 0.3365 23.0945 18.2814 13.4251 9.4023 6.9597 5.8565 9.3232 5.6150 4.9570 47.8013 34.8830 26.7250 25.0435 16.7653 13.5910

表2 不同的临界距离系数L 在α和k 的15种参数组合下运行结果的均值 Tab.2 Average value of different distance coefficient L under15 kinds of αand K.

表 3 不同的变异系数k 在α和L 的9种参数组合下运行结果的均值

Tab.3 Average value of the different coefficient of variation k under 9 kinds of αand L .

由表1可知，在替换因子4.0=α时，IGA 算法求解Rastrigin 函数获得最好结果.在表2中，当临界距离系数01.0=L 时，IGA 算法在求解15维的Rastrigin 函数的最优值的均值最小，而在其他情况下IGA 算法均是在05.0=L 时求解Rastrigin 函数的均值最小.从表3可知，只是当变异系数

5.2=k 、25=D 时，IGA 算法求解Rastrigin 函数的最差值的均值最好，而在其他情况下，都是在0.2=k 时，算法获得最好值.

经过上面的分析可知，IGA 算法中的替换因子α、临界距离系数L 和变异系数k 三参数的取值组合可为：4.0=α、05.0=L 、0.2=k .

4.2 算法性能测试

表4 IGA 和GA 分别求解Rastrigin 函数的结果比较

Tab.4 The results comparison between IGA and GA respective solution to the Rastrigin function.

算法 D=15

Best Worst Avg

D=20

Best Worst Avg

D=25

Best Worst Avg

IGA GA

9.8E-05 2.0E-04 3.9871 45.4676 1.3705 13.3850 0.0050 18.7578 10.9631 94.4858 5.7904 54.6772 2.0019 60.7102 26.8801 135.4671 12.8357 102.6030

算法中的参数确定后，需要测试IGA 算法的性能，现将其与GA 算法同时用于求解Rastrigin 函数，求解结果对比见表4.从表4中可知，在求解Rastrigin 函数的最优解时，IGA 算得到的结果远

L

D=15

Best Worst Avg D=20

Best Worst Avg

D=25

Best Worst Avg

0.01 0.05 0.1

2.1E-04 2.3E-04 2.7E-04

6.3293 5.8118 6.5437 1.5712 1.5022 1.5236 0.6143 0.5497 0.8741 20.0990 16.4174 18.2846

7.2286 7.1604 7.8295 6.4919 6.3876 7.0156 36.0328 35.6566 37.7199 1

8.9283 18.0496 18.4219

k D=15

Best Worst Avg

D=20

Best Worst Avg

D=25

Best Worst Avg

2.5 2.0 1.5 1.0 0.5

2.5E-04 1.6E-04 2.5E-04

3.6E-04 1.8E-04 6.5586 5.5621 6.7810 5.6694 6.5701 1.7900 1.4863 1.5227 1.3024 1.5603 0.7918 0.4563 0.7967 0.9003 0.4517 16.1262 15.2865 19.5412 17.9083 22.4728 7.0187 6.8348 7.1783 7.5048 8.4942 5.5735 5.0642 7.1965 7.1464 8.1781 33.3256 3

4.1913 37.5103 3

5.7341 41.5875 1

6.9489 16.7880 18.5581 18.9659 21.0722

远好于GA 算法得到的结果，特别是在高维优化时，IGA 算法更加有效.分析表明IGA 算法相应的改进方法是有效可行的.

为了进一步了解GA 和IGA 算法在求解Rastrigin 函数最优值时的种群变化，在图1-图3中给出了两种算法的种群均值随迭代过程.

200

400

600

800

10001200

1400

1600

1800

2000

05101520253035404550t

R a s t r i g i n

GA IGA

图1. D=15时，种群均值迭代过程Fig.1 The iterative process of population

mean with D=15

200

400

600

800

10001200

1400

1600

1800

2000

020406080

100120

140160180200

t

R a s t r i g i n

GA IGA

图2. D=20时，种群均值迭代过程Fig.2 The iterative process of population

mean with D=20

0200400600800

100012001400160018002000

50

100

150

200

250

300

t

R a s t r i g i n

GA IGA

图3. D=25时，种群均值迭代过程Fig.3 The iterative process of population

mean with D=25

从图中可知，IGA 算法比GA 算法具有更好的稳定性，并且收敛速度更快，进一步表明IGA 算法的相关改进操作是有效可行的.

综上所述，IGA 算法是在基本算法基础上从三个基本算子出发的改进遗传算法，让选择算子和交叉算子缩短寻找最优解的时间，变异算子增强遗传算法跳出局部收敛的能力，从而达到调节遗传算法局部最优与收敛速度的矛盾的结果.通过测试函数Rastrigin 确定参数的取值和评价IGA 性能，由测试性能知：IGA 算法得到的结果远远好于GA 算法得到的结果，高维优化时IGA 算法更加有效，且IGA 算法比GA 算法具有更好的稳定性，收敛速度更快，表明IGA 算法的相关改进操作是有效可行的.

参考文献：

[1] HOLLAND J H .Adaptation in Nature and Artificial Systems[M].MIT Press ,1992.

[2] DE JONG K A.An Analysis of the Behavior of a Class of Genetic Adaptive Systems[M].Ph.D Dissertation, University of Michigan ,1975.

[3] GOLDBERG D E ,Genetic Algorithms in Search,Optimization and Machine Learning[M], Addition Wesley , 1989.

[4] JAEHUN LEE, WOO YONG CHUNG, EUNTAI KIM,SOOHAN KIM . A New Genetic Approach for Structure Learning of Bayesian Networks: Matrix Genetic Algorithm[J]. International Journal of Control Automation, and Systems ,2010, 8(2): 398-407.

[5] 刘学增,周 敏.改进的自适应遗传算法及其工程应用[J].同济大学学报(自然科学版),2009, 37(3): 303-307. [6] 马 坚.基于遗传算法及其改进的进化神经网络算法[J].硅谷,2012,04:166-180.

[7] 何大阔,王福利,贾明兴.改进的遗传算法在优化设计中的应用[J].东北大学学报(自然科学版), 2005, 26(12): 1123-1126.

[8] 唐国新,陈 雄,袁 杨.机器人路径规划中的改进型遗传算法[J].计算机工程与应用,2007, 43(22): 67-70. [9] FATEMEH VAFAEE,PETER C NELSON . Self-adaptation of Genetic Operator Probabilities Using Differential Evolution[C].Third IEEE International Conference on Self-adaptive and Self-organizing Systems, San Francisco ,2009:274-275.

[10] 吴少岩,许卓群.遗传算法中遗传因子的启发式构造策略[J 」.计算机学报, 1998,21(l1):1003-1008.

[11] 孟佳娜,王立宏.具有自识别能力的遗传算法求解旅行商问题[J].计算机工程与应用,2006,26(13):51-52.

[12] HOLLAND J H.Adaptation in Natural and Artificial Systems[M].MIT Press, Cambridge, Massachusetts. 1992.

[13] 郎敏峰.遗传算法的改进及其在组合优化中的应用[D].华东师范大学,2004.

Realization of Improved Genetic Algorithm

XIANG Ting,PAN Da-zhi,CHEN You-jun,YANG Shuang (college of Mathematics and Information, China West Normal University, Nanchong 637009, China) Abstract：Genetic Algorithm is an adaptive search algorithm for global optimization of genetic biological evolution and the formation of simulation. C ontrary to b asic genetic algorithm’s shortcomings, this article will put an improved genetic algorithm (IGA) from the three operators:selection,crossover and mutation, starting to use the ways of replacing the worst individual part, introducing niche ideas and Concentration factor for processing. Through testing Rastrigin to determine the relevant parameters in IGA and comparing with traditional genetic algorithms, IGA reflects the superiority and feasibility.

Key words: Genetic algorithm; Niche; Concentration factor; Adaptive

一种改进的遗传算法

第17卷第3期 辽阳石油化工高等专科学校学报Vol.17No.3 2001年9月 Journal of Liaoyang Petrochemical College September2001 一种改进的遗传算法 王亮申　王文友　吴克勤　江远鹏　谢　荣 (辽阳石油化工高等专科学校机械系,辽阳111003) 摘　要　给出的适应值标定公式能够解决对个体选择压力和标定后适应值非负问题. 对多极值函数的遗传算法所提出的改进措施可以增加群体的多样性,避免算法“早熟”,过早 陷入局部最优. 关键词　遗传算法;适应值标定;早熟 中图分类号　O224 由美国密执安(Michrgan)大学的Holland教授等人在1975年创立的遗传算法(G enetic Algo2 rithms简称G A),是建立在达尔文(Darwin)的生物进化论和孟德尔(Mendel)的遗传学说基础上的算法.经过后人的不断改进使得遗传算法更加完善.由于遗传算法求解复杂优化问题的巨大潜力及其在各个领域(如布局优化问题、交通问题、图像处理与识别、结构设计、电力系统设计、可靠性计算等)的成功应用,这种算法越来越被人们所接受. 遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法,它模拟基因重组与进化的自然过程,把待解决问题的参数编成二进制码或十进制码(也可编成其它进制码)即基因(gene),若干基因组成一个染色体(个体),许多染色体进行类似于自然选择、配对交叉和变异运算,经过多次重复迭代(即世代遗传)直至得到最后的优化结果.习惯上,适应度值越大,表示解的质量越好.对于求解最小值问题可通过变换转为求解最大值问题.遗传算法是一种高度并行、随机、自适应搜索算法. 尽管遗传算法有许多优点,也有许多专家学者对遗传算法进行不断研究,但目前存在的问题依然很多.如(1)适应值标定方式多种多样,没有一个简洁、通用方法,不利于对遗传算法的使用; (2)遗传算法的“早熟”现象即很快收敛到局部最 收稿日期:2001-06-27优解而不是全局最优解是迄今为止最难处理的关键问题;(3)快要接近最优解时在最优解附近左右摆动,收敛较慢. 1　改进方法 1.1　适应值标定 初始种群中可能存在特殊个体的适应值超常(如很大).为了防止其统治整个群体并误导群体的发展方向而使算法收敛于局部最优解需限制其繁殖;在计算临近结束,遗传算法逐渐收敛,由于群体中个体适应值比较接近,继续优化选择困难,造成在最优解附近左右摇摆,此时应将个体适应值适当加以放大,以提高选择能力,这就是适应值的标定.文献[1]提出的标定方法有两个计算公式,不利于使用;文献[2]的标定方式虽然限制了适应值范围但将最大最小值颠倒.此外象幂律标定、对数标定等亦有应用.本文针对适应值标定问题提出以下计算公式. f’= 1 f max-f min+δ (f+|f min|) f′—为标定后的适应值;f—为原适应值;δ—为在(0,1)内的一个正实数,目的是防止分母为零和增加遗传算法的随机性;|f min|—是为了保证定标后的适应值不出现负值。

遗传算法基本原理及改进

遗传算法基本原理及改进 编码方法： 1、二进制编码方法 2、格雷码编码方法 3、浮点数编码方法。个体长度等于决策变量长度 4、多参数级联编码。一般常见的优化问题中往往含有多个决策变量，对这种还有多个变量的个体进行编码的方法就成为多参数编码方法。多参数编码的一种最常用和最基本的方法是：将各个参数分别以某种方式进行编码，然后再将它们的编码按照一定顺序连接在一起就组成了标识全部参数的个体编码。 5、多参数交叉编码：思想是将各个参数中起主要作用的码位集中在一起，这样他们就不易于被遗传算子破坏掉。在进行多参数交叉编码时，可先对各个参数进行编码；然后去各个参数编码串的最高位连接在一起，以他们作为个体编码串前N位编码，同上依次排列之。

改进遗传算法的方法： （1）改进遗传算法的组成成分或实用技术，如选用优化控制参数、适合问题的编码技术等。 （2）采用动态自适应技术，在进化过程中调整算法控制参数和编码精度。 （3）采用混合遗传算法 （4）采用并行算法 （5）采用非标准的遗传操作算子 改进的遗传算法： （1）分层遗传算法 （2）CHC算法 （3）messy遗传算法； （4）自实用遗传算法（Adaptive Genetic Algorithm） （5）基于小生境技术的遗传算法（Niched Genetic Algorithm，简称NGA）。 （6）并行遗传算法（Parallel Genetic Algorithm） （7）混合遗传算法：遗传算法与最速下降法相结合的混合遗传算法；遗传算法与模拟退火算法相结合的混合遗传算法。 解决标准遗传算法早熟收敛和后期搜索迟钝的方案 （1）变异和交叉算子的改进和协调采用 将进化过程划分为渐进和突变两个不同阶段 采用动态变异 运用正交设计或均匀设计方法设计新的交叉和变异算子 （2）采用局部搜索算法解决局部搜索能力差的问题 （3）采用有条件的替代父代的方法，解决单一的群体更新方式难以兼顾多样性和收敛性的问题 （4）收敛速度慢的解决方法； 产生好的初始群体 利用小生境技术 使用移民技术 采用自适应算子 采用与局部搜索算法相结合的混合遗传算法 对算法的参数编码采用动态模糊控制 进行未成熟收敛判断

遗传算法改进思路

1.粒子群算法的基本原理 粒子群算法主要有三个部分组成,第一部分是一个权值乘以粒子前一次的飞行速度计算而来,这表示种群中每个粒子对其当前自身运动状态的一种信任,因此这个权值被称为“惯性权重”或者“速度权重”;第二部分是根据种群中每个粒子当前位置与其自身所经过的最优值位置之间的距离计算而来,也就是种群粒子对自身的一种“认知”;第三部分是根据种群每个粒子当前位置与种群所有粒子所经历过的最优值位置之间的距离计算而来,表示种群粒子间信息共享与相互合作的过程,它通过认知模仿了较好同伴的运动也就是种群粒子的“社会”认知部分。 每个粒子都享有以下几个信息： （1）粒子当前的位置; （2）到当前为止每个粒子发现的最好位置即个体历史最优值位置,这个信息被当作每个粒子本身的飞行经验; （3）到目前为止整个种群中所有粒子所发现的最好位置种群全局最优值位置,这个就是整个种群所有粒子之间所共同享有的飞行经验; 所以,每个粒子的运动速度受到自身个体历史最优值位置和整个种群的全局最优值位的影响。以此,以每个粒子自身的个体历史最优值位置和整个种群的最优位置来调整当前种群中每个粒子的运动方向和速度大小,能够很好地协调好每个粒子与整个种群之间的信息交换的关系。 2改进的思路： 粒子群算法在运行过程中，如果某粒子发现一个当前最优位置，其它粒子将迅速向其靠拢，如果该最优值为局部最优点，粒子群就无法在解空间内重新搜索，算法就陷入了局部最优，出现了早熟收敛现象。 2.1加入一个惯性权重到速度更新的公式中。 W（惯性因子），其大小决定了对粒子当前速度继承的多少，合适的选择可以使粒子具有均衡的探索和开发能力。也就是起到权衡全局搜索能力和局部搜索能力。W较大时，前一速度影响较大，全局抗震搜索能力较强;较小时，局部搜索能力较弱。所以它的大小决定了搜索的步伐大小，一般在开始的时候搜索的步伐大些可以加快速度，但随着迭代次数的增加应该适当地让步伐变小进行局部搜索，这样可以避免错过最优解，从而提高解的精度。 遗传算法改进思路： 1.初始种群的选择。 如果用随机方法产生一组初始解群体，这样可能会导致初始解群体在 解空间分布不均匀，从而影响算法的性能。 （1）将解空间划分为S个子空间 （2）量化每个子空间，运用均匀数组或正交数组选择M个解 （3）从M*S个解中，选择适应度函数最大的N个作为初始解群 体。 这样就可以保证初始解群体在解空间均匀分布，从而增加获取全局最 优解的可能。 2.增加一个步骤：判断适应值的相似度，去除相似 （1）个体按适应值大小排序 （2）求平均适应度值，以些为阈值，选择适应度值大于平均适

改进的混沌遗传算法

改进的混沌遗传算法 李辉 (计算机学院2004级研究生 04720746) 摘要：混沌遗传算法(chaos genetic algorithm, CGA)是基于混沌优化的遗传操作,将使子代个体均匀地分布于定义空间,从而可避免早熟,以较大的概率实现全局最优搜索.与传统的遗传算法相比较, CGA 的在线和离线性能都有较大的改进。而遗传算法作为一种智能算法，是解决非线性复杂优化问题的有利工具，但它在搜索过程中易陷入局部最优，收敛速度慢的缺陷又限制了它的寻优效能。混沌遗传算法具有两者的优点，大大提高了优化的效率。 关键词：遗传算法混沌混沌优化 Abstract：Chaos genetic algorithm (CGA)is a genetic operation,which based on chaos optimization,makes the individuals of subgeneration distribute uniformly in the defined space and avoids the premature of subgeneration.To compare the performances of the CGA with those of the traditional GA,The results demonstrated that the CGA’s on-line and off–line performance was all superior to that of the traditional GA.As an inteliengence algorithm,GA is a effectual toos to resolve the problem of the liner-optimization,but the slower convergence and the premature restrict its efficiency.And CGA which has the two strongpoint has promoted is efficiency in optimization. Key words: genetic algorithm chaos chaos optimization 1 引言： 遗传算法(GA)最早由美国Michigan大学的John Holland教授提出，通过模拟自然界中的生命进化过程，有指导地而不是盲目地进行随机搜索，适用于在人工系统中解决复杂特定目标的非线性反演问题。De Jong首先将遗传算法应用于函数优化问题的研究，他的工作表明在求解数学规划时，GA是一种有效的方法。但对于大型复杂系统，尤其是非线性系统优化问题的求解，GA仍有许多缺陷，如无法保证收敛到全局最优解，群体中最好的染色体的丢失，进化过程的过早收敛等。 混沌是自然界中一种较为普遍的现象，具有“随机性”、“遍历性”及“规律性”等特点，在一定范围内能按其自身的“规律”不重复地遍历所有状态的。在搜索空间小时混沌优化方法效果显著，但搜索空间大时几乎无能为力。 混沌遗传算法(CGA)的基本思想是将混沌状态引入到优化变量中，并把混沌运动的遍历范围“放大”到优化变量的取值范围，然后把得到的混沌变量进行编码，进行遗传算子操作。再给混沌变量附加—混沌小扰动，通过一代代地不断进化，最后收敛到一个最适合环境的个体上，求得问题的最优解。 2 传统遗传算法 传统遗传算法： population old_pop,new_pop;/*current and next population*/ int pop_size,generation; float p_cross,p_mutation; /*prob. Of crossover & mutation*/ 1 old_pop=initial random population={ind1,ind2,….indpopsize} 2 while(generation

遗传算法论文：浅谈遗传算法的研究与改进

遗传算法论文：浅谈遗传算法的研究与改进【摘要】遗传算法是模拟自然界生物进化机制的概率性搜索算法，可以处理传统搜索方法难以解决的非线性问题。但是经典遗传算法存在局部收敛、收敛速度慢等缺点，这使得经典遗传算法有时很难找到全局最优解。本文针对经典遗传算法中所存在的缺点，采用阶段式的适应度函数、基于竞争机制的交叉方式和仿粒子群变异操作，使遗传算法的收敛速率、全局收敛概率都得到了较大的提高。 【关键词】遗传算法适应度交叉操作仿粒子群变异 一遗传算法 遗传算法（genetic algorithm，简称ga）是holland 在研究自然遗传现象与人工系统的自适应行为时，模拟生物进化现象，并采用自然进化机制来表现复杂现象的一种全局群体搜索算法。遗传算法的基本思想起源于darwin进化论和mendel的遗传学说。作为一类智能计算工具和学习算法，由于其实现简单、对目标函数要求不高等特性，遗传算法已广泛应用于如人工智能、组合优化等研究领域。 1．遗传算法的优越性 遗传算法（genetic algorithm）利用某种编码技术作用在称为染色体的二进制串上，模拟由这些串组成的个体的进化过程。通过有组织的、随机的信息交换来重新结合那些

适应性好的串，在每一代中，利用上一代串结构中适应性好的位和段来形成一个新的串的群体，同时在串结构中尝试用新的位和段来代替原来的部分以形成新的个体，以增加种群的多样性。遗传算法的最大优点是能够通过群体间的相互作用，保存已经搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。但是，遗传算法也存在着计算速度较慢，并且容易陷入局部最优解的问题中。 遗传算法的优越性归功于它与传统搜索方法不同的特 定结构。 第一，遗传算法的操作对象是编码，对问题的限制极少，对函数的一些约束条件如连续性、可导性等不做要求，减少了要解决问题的复杂性。 第二，遗传算法同时搜索解空间内的许多点，因而可以有效地防止搜索过程中收敛到局部最优解，并获得全局最优解，与其他单点搜索的方法相比，在计算时间上也有较大的优势。 第三，遗传算法使用遗传操作时是按概率在解空间进行搜索，因而既不同于随机搜索，也不同于枚举法那样盲目地举例，而是一种有目标、有方向的启发式搜索。 2．遗传算法的基本步骤 遗传算法的实现中包括复制、交叉、变异三个算子，需