遗传算法在求解复杂函数给定区间上最值中的应用

计算智能导论大作业---遗传算法在求解复杂函数给定区间上最值中的应用一、遗传算法简介遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解，对于各种通用问题都可以使用1.1术语说明由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是一些常用术语的说明：染色体染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。基因基因是串中的元素，基因用于表示个体的特征。例如有一个串S=1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alleles)。基因位点基因位点在算法中表示一个基因在串中的位置称为基因位置(GenePosition)，有时也简称基因位。基因位置由串的左向右计算，例如在串S=1101中，0的基因位置是3。特征值在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。适应度各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数是计算个体在群体中被使用的概率。1.2传算法的实现(1)编码遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码，也可以称作(问题的)表示(representation)。而二进制编码是目前遗传算法中最常用的编码方法。即是由二进制字符集{0,1}产生通常的0,1字符串来表示问题空间的候选解。它具有以下特点：a)简单易行b)符合最小字符集编码原则c)便于用模式定理进行分析，因为模式定理就是以基础的。(2)适应度函数进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值。由此可见，在不少场合，将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。适应度函数的设计主要满足以下条件：a）单值、连续、非负、最大化b)合理、一致性c）计算量小d）通用性强。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。(3)初始群体选取遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略:a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。1.3运算过程遗传算法的基本运算过程如图1，其中各步完成的工作如下a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。开始种群初始化计算个体适应度值选择操作交叉操作变异操作达到终止条件选择适应度最高的个体结束对问题进行编码YN图1.遗传算法流程图1.4特点及应用遗传算法还具有以下几方面的特点：(1)遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。(2)遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。(3)遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。(4)遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。(6)算法本身也可以采用动态自适应技术，在进化过程中自动调整算法控制参数和编码精度，比如使用模糊自适应法。由于遗传算法的整体搜索策略和优化搜索方法在计算时不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于函数优化和组合优化，车间调度等方面。二、用遗传算法求解复杂函数的在给定区间上的最值下面用遗传算法求函数f(x)的最大值f(x)=10*sin(5x)+7*cos(x²)x∈[0,10]，分辨率为0.012.1编码我们采用最常用的二进制编码形式进行编码，考虑到分辨率的要求，我们需要采用转换的方式进行浮点数的编码将x的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为(10-0)/(2^10-1)≈0.01。%将变量域[0,10]离散化为二值域[0,1023],x=0+10*b/1023,其中b是[0,1023]中的一个二值数。2.2适应度函数选取直接将目标函数取为适应度函数，同时考虑到f(x)存在小于零的情况，此时，需将适应度函数值取为0.即(),f(x)0()0,()0fxfitnessxfx2.3仿真结果最佳编码序列为：0000100000对应x的取值为:0.31281第8次迭代达到最大值求得最大值为16.96628833目标函数最优值随迭代次数变化如下图：05101520253011121314151617图2.函数最大值随迭代次数变化曲线可以看出，目标函数值随着迭代次数增加到8次即达到稳定状态，算法具有快速性和较强的全局寻优能力。2.4下面对求解结果的准确性进行检查在区间[0,10]上以0.01的步长进行搜索得到函数的最优值；可得：x=0.32时函数取得最大值为ymax=16.965539275225591随着x值的变化，对应的y值为：012345678910-20-15-10-505101520X:0.32Y:16.96图3.目标函数随x值的变化曲线显然，采用遗传算法得到的结果比定步长的结果更好，且运算次数更少，达到了大于0.01的目标。2.5方法的推广本方法通过映射关系使遗传算法可以解决函数在浮点数范围内的函数最值问题，扩展了遗传算法的应用范围。此外，如果把一个个体的编码划分为几节，分别对应不同自变量的编码，其余操作基本不变，则可以把遗传算法推广到多变量目标函数在给定区间上的最值的求取，并在结果精度和求解时间上均有较大提高。附1、原程序代码%参数的初始化,种群规模、染色体长度，交叉和变异概率；种群迭代次数；popsize=10;chromlength=10;pc=0.5;pm=0.04;circle=30;maxindividual=zeros(1,circle);bestcode=zeros(circle,chromlength);%对问题进行编码initpop=round(rand(popsize,chromlength));pop=initpop;times=0;whiletimescircle%对问题解码,即将2进制转化为10进制；decimal=zeros(1,popsize);forii=1:popsizeforjj=1:chromlengthdecimal(ii)=decimal(ii)+pop(ii,jj)*2.^(chromlength-jj);enddecimal(ii)=10*decimal(ii)/1023;end%计算个体的适应度值；fori=1:popsizeindividual(i)=10*sin(5*decimal(i))+7*cos(decimal(i).^2);if(individual(i)0)individual(i)=0;endend[maxindividual(times+1),maxindex]=max(individual);%每次迭代，种群中适应度的最大值；bestcode(times+1,:)=pop(maxindex,:);%适应度最高个体对应的编码；totalindividual=sum(individual);%进行选择操作；%转轮盘方法进行选择操作fori=1:popsizebdindividual(i)=sum(individual(1:i))/totalindividual;endfori=1:popsizej=1;rn=rand;whilernbdindividual(j)j=j+1;endnewpop(i,:)=pop(j,:);end%个体间进行交叉操作,pcps(交叉位置）；pop=newpop;fori=1:2:popsizern2=rand;if(rn2pc)pcps=round(chromlength*rn2);if(pcps==0)pcps=1;endnewpop(i,pcps:chromlength)=pop(i+1,pcps:chromlength);newpop(i+1,pcps:chromlength)=pop(i,pcps:chromlength);endend%对种群进行变异操作；fori=1:popsizeforj=1:chromlengthif(randpm)newpop(i,j)=1-newpop(i,j);endendendpop=newpop;times=times+1;end[maxall,index]=max(maxindividual);allindex=bestcode(index,:);value=0;