遗传算法和蚁群算法的比较

全局优化报告——遗传算法和蚁群算法的比较姓名：郑玄玄学号：3112054023班级：硕20411遗传算法1.1遗传算法的发展历史遗传算法是一种模拟自然选择和遗传机制的寻优方法。20世纪60年代初期，Holland教授开始认识到生物的自然遗传现象与人工自适应系统行为的相似性。他认为不仅要研究自适应系统自身，也要研究与之相关的环境。因此，他提出在研究和设计人工自适应系统时，可以借鉴生物自然遗传的基本原理，模仿生物自然遗传的基本方法。1967年，他的学生Bagley在博士论文中首次提出了“遗传算法”一词。到70年代初，Holland教授提出了“模式定理”，一般认为是遗传算法的基本定理，从而奠定了遗传算法的基本理论。1975年，Holland出版了著名的《自然系统和人工系统的自适应性》，这是第一本系统论述遗传算法的专著。因此，也有人把1975年作为遗传算法的诞生年。1985年，在美国召开了第一届两年一次的遗传算法国际会议，并且成立了国际遗传算法协会。1989年，Holland的学生Goldberg出版了《搜索、优化和机器学习中的遗传算法》，总结了遗传算法研究的主要成果，对遗传算法作了全面而系统的论述。一般认为，这个时期的遗传算法从古典时期发展了现代阶段，这本书则奠定了现代遗传算法的基础。遗传算法是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。在进化论中，每一个物种在不断发展的过程中都是越来越适应环境，物种每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来；否则，就将被淘汰。在遗传学中认为，遗传是作为一种指令遗传码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有特殊的位置并控制某个特殊的性质。每个基因产生的个体对环境有一定的适应性。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。在求解过程中，遗传算法从一个初始变量群体开始，一代一代地寻找问题的最优解，直到满足收敛判据或预先假定的迭代次数为止。遗传算法的应用研究比理论研究更为丰富，已渗透到许多学科，并且几乎在所有的科学和工程问题中都具有应用前景。一些典型的应用领域如下：（1）复杂的非线性最优化问题。对具体多个局部极值的非线性最优化问题，传统的优化方法一般难于找到全局最优解；而遗传算法可以克服这一缺点，找到全局最优解。（2）复杂的组合优化或整数规划问题。大多数组合优化或整数规划问题属于NP难问题，很难找到有效的求解方法；而遗传算法即特别适合解决这一类问题，能够在可以接受的计算时间内求得满意的近似最优解，如著名的旅行商问题、装箱问题等都可以用遗传算法得到满意的解。（3）工程应用方面。工程方法的应用是遗传算法的一个主要应用领域，如管道优化设计、通风网络的优化设计、飞机外型设计、超大规模集成电路的布线等。（4）计算机科学。遗传算法广泛应用于计算机科学的研究，如用于图像处理和自动识别、文档自动处理、VLSI设计等。（5）生物学。遗传算法起源于对生物和自然现象的模拟，现在又反过来用于生物领域的研究，如利用遗传算法进行生物信息学的研究等。（6）社会科学。遗传算法在社会科学的许多领域也有广泛应用，如人类行为规范进化过程的模拟、人口迁移模型的建立等（7）经济领域。经济学领域也用到遗传算法。例如，国民经济预测模型、市场预测模型和期货贸易模型等。遗传算法与神经网络相结合正成功地被应用于从时间序列分析来进行财政预算等。1.2遗传算法的基本原理遗传算法是一种基于自然选择和群体遗传机制的搜索算法，它模拟了自然选择和自然遗传过程中的繁殖、杂交和突变现象。在利用遗传算法求解问题时，问题的每个可能的解都被编码成一个“染色体”，即个体，若干个个体构成了群体（所有可能解）。在遗传算法开始时，总是随机地产生一些个体（即初始解）。根据预定的目标函数对每个个体进行评估，给出了一个适应度值。基于此适应度值，选择个体用来复制下一代。选择操作体现了“适者生存”的原理，“好”的个体被选择用来复制，而“坏”的个体则被淘汰。然后选择出来的个体经过交叉和变异算子进行再结合生成新的一代。这一群新个体由于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优解的方向进化。因此，遗传算法可以看成是一个由可行解组成的群体逐步进化的过程。图给出了简单遗传算法的基本过程。下面介绍遗传算法的编码及基本遗传操作过程。1.2.1编码利用遗传算法求解问题时，首先要确定问题的目标函数和变量，然后对变量进行编码。这样做主要是因为在遗传算法中，问题的解是用数字串来表示的，而且遗传算子也是直接对串进行操作的。编码方式可以分为二进制编码和实数编码。若用二进制数表示个体，则将二进制数转化为十进制数的解码公式可以为ljjijliiiiliibRTRbbbF1121212),...,,(其中，),...,,(iliibbb21为某个个体的第i段，每段段长都为l，每个ikb都是0或者1，iT和iR是第i段分量iX的定义域的两个端点。1.2.2遗传操作遗传操作是模拟生物基因的操作，它的任务就是根据个体的适应度对其施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度看，遗传操作可以使问题的解逐代的优化，逼近最优解。遗传操作包括以下三个基本遗传算子：选择、交叉、变异。选择和交叉基本上完成了遗传算法的大部分搜索功能，变异增加了遗传算法找到最接近最优解的能力。1.选择选择是指从群体中选择优良的个体并淘汰劣质个体的操作。它建立在适应度评估的基础上。适应度越大的个体，被选择的可能性就越大，它的“子孙”在下一代的个数就越多。选择出来的个体被放入配对库中。目前常用的选择方法有轮赌盘方法（也称适应度比例法）、最佳个体保留法、期望值法、排序选择法、竞争法、线性标准化方法等。2.交叉交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作，交叉的目的是为了能够在下一代产生新的个体。通过交叉操作，遗传算法的搜索能力得以飞跃性的提高。交叉是遗传算法获得新优良个体的最重要的手段。交叉操作是按照一定的交叉概率cP在配对库中随机地选取两个个体进行的。交叉的位置也是随机确定的。交叉概率cP的值一般取得很大，为0.6~0.9。3.变异变异就是以很小的变异概率mP随机地改变群体中个体的某些基因的值。变异操作的基本过程是：产生一个],[10之间的随机数rand，如果mPrand，则进行变异操作。变异操作本身是一种局部随机搜索，与选择、交叉算子结合在一起，能够避免由于选择和交叉算子而引起的某些信息的永久性丢失，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力，同时使得遗传算法能够保持群体的多样性，以防止出现未成熟收敛。变异操作是一种防止算法早熟的措施。在变异操作中，变异概率不能取值太大，如果50.mP，遗传算法就退化为随机搜索，而遗传算法的一些重要的数学特性和搜索能力也就不复存在了。1.3基本步骤遗传算法的基本步骤如下：1）在一定编码方案下，随机产生一个初始种群；2）用相应的解码方法，将编码后的个体转换成问题空间的决策变量，并求得个体的适应值；3）按照个体适应值的大小，从种群中选出适应值较大的一些个体构成交配池；4）由交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一代的种群；5）反复执行步骤2~4，直至满足收敛判据为止。使用遗传算法需要决定的运行参数有：编码串长度、种群大小、交叉和变异概率。编码串长度优优化问题所要求的求解精度决定。种群大小表示种群中所含个体的数量，种群较小时，可提高遗传算法的运算速度，但却降低了群体的多样性，可能找不到最优解；种群较大时，又会增加计算量，使遗传算法的运行效率降低。一般取种群数目为20~100.交叉概率控制着交叉操作的频率，由于交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率通常应取较大值；但若过大的话，又可能破坏群体的优良模式。一般取0.4～0.99.变异概率也是影响新个体产生的一个因素，变异概率小，产生新个体少；变异概率太大，又会使遗传算法变成随机搜索。一般取变异概率为0.0001～0.1.遗传算法常采用的收敛判据有：规定遗传代数：连续几次得到的最优个体的适应值没有变化或变化很小等。1.4用MATLAB实现遗传算法MATLAB是Matwork公司的产品，是一个功能强大的数学软件，其优秀的数值计算能力使其在工业界和学术界的使用率都非常高。MATLAB还十分便于使用，它以直观、简洁并符合人们思维习惯的代码给用户提供了一个非常友好的开发环境。利用MATLAB处理矩阵运算的强大功能来编写遗传算法程序有着巨大的优势。1.4.1编码遗传算法不对优化问题的实际决策变量进行操作，所以应用遗传算法首要的问题是通过编码将决策变量表示成串结构数据。本文中我们采用最常用的二进制编码方案，即用二进制数构成的符号串来表示一个个体，用下面的encoding函数来实现编码并产生初始种群。function[bin_gen,bits]=encoding(min_var,max_var,scale_var,popsize)bits=ceil(log2((max_var-min_var)./scale_var));bin_gen=round(rand(popsize,sum(bits)));end在上面的代码中，首先根据各决策变量的下界（min_var）、上界（max_var）及其搜索精度scale_var来确定表示各决策变量的二进制串的长度bits，然后随机产生一个种群大小为popsize的初始种群bit_gen。编码后的实际搜索精度为scale_dec=(max_var-min_var)/(2^bits-1)，该精度会在解码时用到。1.4.2解码解码后的个体构成的种群bin_gen必须经过解码，以转换成原问题空间的决策变量构成的种群var_gen，方能计算相应的适应值。我们用下面的代码实现。function[var_gen,fitness]=decoding(funname,bin_gen,bits,min_var,max_var)num_var=length(bits);popsize=size(bin_gen,1);scale_dec=(max_var-min_var)./(2.^bits-1);bits=cumsum(bits);bits=[0bits];fori=1:num_varbin_var{i}=bin_gen(:,bits(i)+1:bits(i+1));var{i}=sum(ones(popsize,1)*2.^(size(bin_var{i},2)-1:-1:0).*bin_var{i},2).*scale_dec(i)+min_var(i);endvar_gen=[var{1,:}];fori=1:popsizefitness(i)=eval([funname,'(var_gen(i,:))']);endend解码函数的关键在于先由二进制数求得对应的十进制数D，并根据下式求得实际决策变量值X：varmin_scale_decDX1.4.3选择选择过程是利用解码后求得的各个适应值大小，淘汰一些较差个体而选出一些比较优良的个体，以进行下一步的交叉和变异操作。选择算子的程序如下：function[evo_gen,best_indiv,best_var,max_fitness]=selection(old_gen,fitness,var_gen)popsize=length(fitness);[max_fitness,index1]=max(fitness);[min_fitness,index2]=min(fitness);best_indiv=old_gen(index1,:);best_var=var_gen(index1);index=1:popsize;index(index1)=0;index(index2)=0;in