遗传算法.docx
《遗传算法.docx》由会员分享，可在线阅读，更多相关《遗传算法.docx（17页珍藏版）》请在冰点文库上搜索。
遗传算法
2011-2012
（1）专业课程实践论文
遗传算法
伊政，0718180126，数学与应用数学+软件工程07-1
一、算法理论
遗传算法就是将问题的求解表示为“染色体”的适者生存的过程，通过染色体群的一代代不断进化：
包括复制、交叉和变异过程，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。
遗传算法具有简单、易操作、需求低和全局性的特点。
（1）编码一次换算法首先要用字符串表达所研究问题的解，这称为编码。
表达问题解的字符串称为个体（染色体）。
一种简单的表示解的编码为二进制编码，即用0,1字符串。
（2）形成初始群体由于生物的进化是以集团为主体，即由一代遗传进化为下一代。
因此遗传算法的运算对象是由
个可行解组成的群。
群体中个体的数目称为群体的规模。
初始群体通常用随机方法产生。
（3）计算适应值适应值是衡量个体好坏的指标，也是今后“优胜劣汰”的主要依据，适应值函数依据目标函数而定，但要求取值非负，且与原优化问题的目标函数有相同的极值点。
适应值函数简记为
。
对于问题：
，一般可取
其中
为预先选定的一个较小的数，或取进化到当前一代位置的最小目标函数值。
（4）选择把当前群体中适应值较大的个体按某种规则或模型选择至另一个群体（交配池），交配池是当前代和下一代间的中间群体，它的规模也为
，以体现优胜劣汰原则。
选择一种常用技术即用赌盘实现。
（5）交叉通过选择产生的新群体，其总体性能得到改善，然而却不能产生新的个体。
为了产生新个体，遗传算法依照生物学中杂交的方法，从交配池中随机选取两个个体进行交叉换位。
交叉后产生两个不同的子代个体，它们一般与父代个体不同，却又包含父代个体的遗传基因。
（6）变异变异是遗传算法产生新个体的另一种方法。
它是以很小概率
（
一般取0.0001-0.1）随机地对个体中某个字符进行补运算（即若原来字符为0，则改为1；若原来为1则改为0）。
具体的，针对每个个体的每个自负产生一个[0,1]区间上的均匀分布的随机数
，若
，则将该字符进行变异，否则不进行变异。
变异运算具有增加群体多样性的效果。
（7）终止反复进行（3）—（6）项工作，直至得到满意解。
终止的条件也可用事先规定进化的代数，一般取100—500。
二、算法框图
图1
三、算法程序
function[x,fval,exitFlag,output,population,scores]=ga（fun,nvars,Aineq,bineq,Aeq,beq,lb,ub,nonlcon,options）
%GAConstrainedoptimizationusinggeneticalgorithm.
%GAattemptstosolveproblemsoftheform:
%minF（X）subjectto:
A*X<=B,Aeq*X=Beq（linearconstraints）
%XC（X）<=0,Ceq（X）=0（nonlinearconstraints）
%LB<=X<=ub
%
%X=GA（FITNESSFCN,NVARS）findsalocalunconstrainedminimumXtothe
%FITNESSFCNusingGA.NVARSisthedimension（numberofdesign
%variables）oftheFITNESSFCN.FITNESSFCNacceptsavectorXofsize
%1-by-NVARS,andreturnsascalarevaluatedatX.
%
%X=GA（FITNESSFCN,NVARS,A,b）findsalocalminimumXtothefunction
%FITNESSFCN,subjecttothelinearinequalitiesA*X<=B.Linear
%constraintsarenotsatisfiedwhenthePopulationTypeoptionissetto
%'bitString'or'custom'.Seethedocumentationfordetails.
%
%X=GA（FITNESSFCN,NVARS,A,b,Aeq,beq）findsalocalminimumXtothe
%functionFITNESSFCN,subjecttothelinearequalitiesAeq*X=beqas
%wellasA*X<=B.（SetA=[]andB=[]ifnoinequalitiesexist.）Linear
%constraintsarenotsatisfiedwhenthePopulationTypeoptionissetto
%'bitString'or'custom'.Seethedocumentationfordetails.
%
%X=GA（FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub）definesasetoflowerand
%upperboundsonthedesignvariables,X,sothatasolutionisfoundin
%therangelb<=X<=ub.Useemptymatricesforlbandubifnobounds
%exist.Setlb（i）=-InfifX（i）isunboundedbelow;setub（i）=Infif
%X（i）isunboundedabove.Linearconstraintsarenotsatisfiedwhenthe
%PopulationTypeoptionissetto'bitString'or'custom'.Seethe
%documentationfordetails.
%
%X=GA（FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub,NONLCON）subjectsthe
%minimizationtotheconstraintsdefinedinNONLCON.Thefunction
%NONLCONacceptsXandreturnsthevectorsCandCeq,representingthe
%nonlinearinequalitiesandequalitiesrespectively.GAminimizes
%FITNESSFCNsuchthatC（X）<=0andCeq（X）=0.（Setlb=[]and/orub=[]if
%noboundsexist.）Nonlinearconstraintsarenotsatisfiedwhenthe
%PopulationTypeoptionissetto'bitString'or'custom'.Seethe
%documentationfordetails.
%
%X=GA（FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub,NONLCON,options）minimizes
%withthedefaultoptimizationparametersreplacedbyvaluesinthe
%structureOPTIONS.OPTIONScanbecreatedwiththeGAOPTIMSETfunction.
%SeeGAOPTIMSETfordetails.
%
%X=GA（PROBLEM）findstheminimumforPROBLEM.PROBLEMisastructure
%thathasthefollowingfields:
%fitnessfcn:
%nvars:
%Aineq:
%bineq:
%Aeq:
%beq:
%lb:
%ub:
%nonlcon:
%options:
%rngstate:
%
%[X,FVAL]=GA（FITNESSFCN,...）returnsFVAL,thevalueofthefitness
%functionFITNESSFCNatthesolutionX.
%
%[X,FVAL,EXITFLAG]=GA（FITNESSFCN,...）returnsEXITFLAGwhich
%describestheexitconditionofGA.PossiblevaluesofEXITFLAGandthe
%correspondingexitconditionsare
%
%1Averagechangeinvalueofthefitnessfunctionover
%options.StallGenLimitgenerationslessthanoptions.TolFunand
%constraintviolationlessthanoptions.TolCon.
%3Thevalueofthefitnessfunctiondidnotchangein
%options.StallGenLimitgenerationsandconstraintviolationless
%thanoptions.TolCon.
%4Magnitudeofstepsmallerthanmachineprecisionandconstraint
%violationlessthanoptions.TolCon.Thisexitconditionapplies
%onlytononlinearconstraints.
%5Fitnesslimitreachedandconstraintviolationlessthan
%options.TolCon.
%0Maximumnumberofgenerationsexceeded.
%-1Optimizationterminatedbytheoutputorplotfunction.
%-2Nofeasiblepointfound.
%-4Stalltimelimitexceeded.
%-5Timelimitexceeded.
%
%[X,FVAL,EXITFLAG,OUTPUT]=GA（FITNESSFCN,...）returnsa
%structureOUTPUTwiththefollowinginformation:
%rngstate:
%generations:
%funccount:
%maxconstraint:
,ifany
%message:
%
%[X,FVAL,EXITFLAG,OUTPUT,POPULATION]=GA（FITNESSFCN,...）returnsthe
%finalPOPULATIONattermination.
%
%[X,FVAL,EXITFLAG,OUTPUT,POPULATION,SCORES]=GA（FITNESSFCN,...）returns
%theSCORESofthefinalPOPULATION.
%
%
%Example:
%Unconstrainedminimizationof'rastriginsfcn'fitnessfunctionof
%numberOfVariables=2
%x=ga（@rastriginsfcn,2）
%
%DisplayplottingfunctionswhileGAminimizes
%options=gaoptimset（'PlotFcns',...
%{@gaplotbestf,@gaplotbestindiv,@gaplotexpectation,@gaplotstopping}）;
%[x,fval,exitflag,output]=ga（@rastriginsfcn,2,[],[],[],[],[],[],[],options）
%
%Anexamplewithinequalityconstraintsandlowerbounds
%A=[11;-12;21];b=[2;2;3];lb=zeros（2,1）;
%%Usemutationfunctionwhichcanhandleconstraints
%options=gaoptimset（'MutationFcn',@mutationadaptfeasible）;
%[x,fval,exitflag]=ga（@lincontest6,2,A,b,[],[],lb,[],[],options）;
%
%FITNESSFCNcanalsobeananonymousfunction:
%x=ga（@（x）3*sin（x
（1））+exp（x
（2））,2）
%
%IfFITNESSFCNorNONLCONareparameterized,youcanuseanonymous
%functionstocapturetheproblem-dependentparameters.Supposeyouwant
%tominimizethefitnessgiveninthefunctionmyfit,subjecttothe
%nonlinearconstraintmyconstr,wherethesetwofunctionsare
%parameterizedbytheirsecondargumenta1anda2,respectively.Here
%myfitandmyconstrareMATLABfilefunctionssuchas
%
%functionf=myfit（x,a1）
%f=exp（x
（1））*（4*x
（1）^2+2*x
（2）^2+4*x
（1）*x
（2）+2*x
（2）+a1）;
%
%and
%
%function[c,ceq]=myconstr（x,a2）
%c=[1.5+x
（1）*x
（2）-x
（1）-x
（2）;
%-x
（1）*x
（2）-a2];
%%Nononlinearequalityconstraints:
%ceq=[];
%
%Tooptimizeforspecificvaluesofa1anda2,firstassignthevalues
%tothesetwoparameters.Thencreatetwoone-argumentanonymous
%functionsthatcapturethevaluesofa1anda2,andcallmyfitand
%myconstrwithtwoarguments.Finally,passtheseanonymousfunctionsto
%GA:
%
%a1=1;a2=10;%defineparametersfirst
%%Mutationfunctionforconstrainedminimization
%options=gaoptimset（'MutationFcn',@mutationadaptfeasible）;
%x=ga（@（x）myfit（x,a1）,2,[],[],[],[],[],[],@（x）myconstr（x,a2）,options）
%
%SeealsoGAOPTIMSET,FITNESSFUNCTION,GAOUTPUTFCNTEMPLATE,PATTERNSEARCH,@.
%Copyright2003-2010TheMathWorks,Inc.
%$Revision:
1.1.6.3$$Date:
2010/02/0822:
34:
19$
%Ifthefirstargisnotagaoptimset,thenit'safitnessfunctionfollowedbyagenome
%length.Herewemakeagaoptimsetfromtheargs.
defaultopt=struct（'PopulationType','doubleVector',...
'PopInitRange',[0;1],...
'PopulationSize',20,...
'EliteCount',2,...
'CrossoverFraction',0.8,...
'MigrationDirection','forward',...
'MigrationInterval',20,...
'MigrationFraction',0.2,...
'Generations',100,...
'TimeLimit',inf,...
'FitnessLimit',-inf,...
'StallGenLimit',50,...
'StallTimeLimit',inf,...
'TolFun',1e-6,...
'TolCon',1e-6,...
'InitialPopulation',[],...
'InitialScores',[],...
'InitialPenalty',10,...
'PenaltyFactor',100,...
'PlotInterval',1,...
'CreationFcn',@gacreationuniform,...
'FitnessScalingFcn',@fitscalingrank,...
'SelectionFcn',@selectionstochunif,...
'CrossoverFcn',@crossoverscattered,...
'MutationFcn',{{@mutationgaussian11}},...
'HybridFcn',[],...
'Display','final',...
'PlotFcns',[],...
'OutputFcns',[],...
'Vectorized','off',...
'UseParallel','never'）;
%Checknumberofinputarguments
errmsg=nargchk（1,10,nargin）;
if~isempty（errmsg）
error（'globaloptim:
ga:
numberOfInputs',[errmsg,'GArequiresatleast1inputargument.']）;
end
%Ifjust'defaults'passedin,returnthedefaultoptionsinX
ifnargin==1&&nargout<=1&&isequal（fun,'defaults'）
x=defaultopt;
return
end
ifnargin<10,options=[];
ifnargin<9,nonlcon=[];
ifnargin<8,ub=[];
ifnargin<7,lb=[];
ifnargin<6,beq=[];
ifnargin<5,Aeq=[];
ifnargin<4,bineq=[];
ifnargin<3,Aineq=[];
end
end
end
end
end
end
end
end
%Isthirdargumentastructure
ifnargin==3&&isstruct（Aineq）%Oldsyntax
options=Aineq;Aineq=[];
end
%Oneinputargumentisforproblemstructure
ifnargin==1
ifisa（fun,'struct'）
[fun,nvars,Aineq,bineq,Aeq,beq,lb,ub,nonlcon,rngstate,options]=separateOptimStruct（fun）;
%Resettherandomnumbergenerators
resetDfltRng（rngstate）;
else%Singlei
升级会员 