基本概念

遗传算法(Genetic Algorithms, GA)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。

它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

GA的组成:

（1）编码（产生初始种群）

（2）适应度函数

（3）遗传算子（选择、交叉、变异）

（4）运行参数

编码

基因在一定能够意义上包含了它所代表的问题的解。基因的编码方式有很多，这也取决于要解决的问题本身。常见的编码方式有：

（1）       二进制编码，基因用0或1表示（常用于解决01背包问题）

如：基因A：00100011010 (代表一个个体的染色体)

（2）       互换编码（用于解决排序问题，如旅行商问题和调度问题）

如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城市中，先经过城市2，再经过城市3，依此类推。

（3）       树形编码（用于遗传规划中的演化编程或者表示）

如,问题：给定了很多组输入和输出。请你为这些输入输出选择一个函数，使得这个函数把每个输入尽可能近地映射为输出。

编码方法：基因就是树形结构中的一些函数。

（4）       值编码 （二进制编码不好用时，解决复杂的数值问题）

在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他一些更复杂的东西。

适应度函数

遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。

如TSP问题，遍历各城市路径之和越小越好，这样可以用可能的最大路径长度减去实际经过的路径长度，作为该问题的适应度函数。

遗传算子——选择

遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。

SGA（基本遗传算法）中采用轮盘赌选择方法。

轮盘赌选择又称比例选择算子，基本思想：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：

遗传算子——交叉

所谓交叉运算，是指对两个相互配对的染色体依据交叉概率按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算在GA中起关键作用，是产生新个体的主要方法。

1.    单交叉点法（用于二进制编码）

选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。

如：交叉前：

00000|01110000000010000

11100|00000111111000101

交叉后：

00000|00000111111000101

11100|01110000000010000

2. 双交叉点法（用于二进制编码）

选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因.

如：交叉前：

01 |0010| 11

11 |0111| 01

交叉后：

11 |0010| 01

01 |0111| 11

3. 基于“ 与/或 ”交叉法（用于二进制编码） 

对父代按位"与”逻辑运算产生一子代A;按位”或”逻辑运算产生另一子代B。该交叉策略在解背包问题中效果较好 .

如：交叉前：

       01001011

       11011101

交叉后：

       01001001

       11011111

4. 单交叉点法（用于互换编码）

选择一个交叉点，子代的从初始位置出发的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代中没有，就把它添加进去。

如：交叉前：

    87213 | 09546

    98356 | 71420

交叉后：

    87213 | 95640

    98356 | 72104

5. 部分匹配交叉（PMX）法（用于互换编码）

先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。

父代A：872 | 130 | 9546

父代B：983 | 567 | 1420    变为：

TEMP A: 872 | 567 | 9546

TEMP B: 983 | 130 | 1420

对于 TEMP A、TEMP Ｂ中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1<——>５　３<——>６　７<——>０

子代Ａ：802 | 567 | 9143

子代Ｂ：986 | 130 | 5427

6. 顺序交叉法(OX) （用于互换编码）

从父代Ａ随机选一个编码子串，放到子代Ａ的对应位置；子代Ａ空余的位置从父代Ｂ中按Ｂ的顺序选取（与己有编码不重复）。同理可得子代Ｂ。

父代A: 872 | 139 | 0546

父代B: 983 | 567 | 1420

交叉后：

子代A: 856 | 139 | 7420

子代B: 821 | 567 | 3904

7. 循环交叉（CX）法（用于互换编码）

CX同OX交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：OX中来自第一个亲代的编码子串是随机产生的，而CX却不是，它是根据两个双亲相应位置的编码而确定的。

父代Ａ：1 2 3 4 5 6 7 8 9

           |  |   |  |        |

父代Ａ：5 4 6 9 2 3 7 8 1

可得循环基因：1->5->2->4->9->1

用循环的基因构成子代Ａ，顺序与父代Ａ一样

1 2   4 5          9

用父代Ｂ剩余的基因填满子代Ａ：

1 2 6 4 5 3 7 8 9

子代Ｂ的编码同理。（循环基因 5->1->9->4->2->5）

遗传算子——变异

变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。GA中的变异运算是产生新个体的辅助方法，它决定了GA的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。

注：变异概率Pm不能太小，这样降低全局搜索能力；也不能太大，Pm > 0.5，这时GA退化为随机搜索。

1. 基本位变异算子（用于二进制编码）

基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。

如：变异前：

000001110000000010000

变异后：

000001110001000010000

2. 逆转变异算子（用于互换编码）

在个体中随机挑选两个逆转点，再将两个逆转点间的基因交换。

如：变异前：

1346798205

变异后：

1246798305

 运行参数

GA运行时选择的参数应该视解决的具体问题而定，到目前为止，还没有一个适用于GA所有应用领域的关于算法参数的理论。下面是一般情况下使用GA时推荐的参数：

1) 交叉率

交叉率一般来说应该比较大，推荐使用80％-95％。

2) 变异率

变异率一般来说应该比较小，一般使用0.5％-1％最好。

3) 种群的规模

种群规模指的是群体中个体的个数。实验发现，比较大的种群的规模并不能优化遗传算法的结果。种群的大小推荐使用20-30，一些研究表明，种群规模 的大小取决于编码的方法，具体的说就是编码串（Encoded String）的大小。也就是说，如果说采用32位为基因编码的时候种群的规模大小最好为32的话，那么当采用16位为基因编码时种群的规模相应应变为原 来的两倍。

4) 遗传运算的终止进化代数

个人的想法是，设定一个计数器，如果连续N代出现的最优个体的适应度都一样时，（严格的说应该是，连续N代子代种群的最优个体适应度都<=父代最优个性的适应度）可以终止运算。

也可以简单的根据经验固定进化的代数。

II 运算流程

 图中的“是否满足停止准则”便可参照上节中“遗传运算的终止进化代数”

III 灾变与精英主义

灾变

遗传算法的局部搜索能力较强，但是很容易陷入局部极值。引用网上的一段原话:

“那么如何解决遗传算法容易陷入局部极值的问题呢？让我们来看看大自然提供的方案。六千五百万年以前，恐龙和灵长类动物并存，恐龙在地球上占绝对统 治地位，如果恐龙没有灭绝灵长类动物是绝没有可能统治地球的。正是恐龙的灭绝才使灵长类动物有了充分进化的余地，事实上地球至少经历了5次物种大灭绝，每 次物种灭绝都给更加高级的生物提供了充分进化的余地。所以要跳出局部极值就必须杀死当前所有的优秀个体，从而让远离当前极值的点有充分的进化余地。这就是灾变的思想。”

灾变就是杀掉最优秀的个体，这样才可能产生更优秀的物种。那何时进行灾变，灾变次数又如何设定？

何时进行灾变，可以采用灾变倒计数的方式。如果n代还没有出现比之前更优秀的个体时，可以发生灾变。灾变次数可以这样来确定，如果若干次灾变后产生的个体的适应度与没灾变前的一样，可停止灾变。

精英主义

当利用交叉和变异产生新的一代时，我们有很大的可能把在某个中间步骤中得到的最优解丢失。

精英主义的思想是,在每一次产生新的一代时，首先把当前最优解原封不动的复制到新的一代中。然后按照前面所说的那样做就行。精英主义方法可以大幅提高运算速度，因为它可以防止丢失掉找到的最好的解。

矛盾

由上面看来,灾变与精英主义之间似乎存在着矛盾.前者是将产生的最优个体杀掉,而后者是将最优秀个体基因直接保存到下一代.

应该辩证地看待它们之间的矛盾,两者其实是可以共存的.我们在每一代进行交叉运算时,均直接把最优秀的个体复制到下一代;但当连续N代,都没有更优 秀的个体出现时,便可以猜想可能陷入局部最优解了,这样可以采用灾变的手段.可以说,精英主义是伴随的每一代的,但灾变却不需要经常发生,否则算法可能下 降为随机搜索了.

当然,每个算法中不一定要用精英主义和灾变的手段,应该根据具体的问题而定.

IV GA的特点

遗传算法的优点:

（1）群体搜索，易于并行化处理；

（2）不是盲目穷举，而是启发式搜索；

（3）适应度函数不受连续、可微等条件的约束，适用范围很广。

（4）容易实现。一旦有了一个遗传算法的程序，如果想解决一个新的问题，只需针对新的问题重新进行基因编码就行；如果编码方法也相同，那只需要改变一下适应度函数就可以了。

遗传算法的缺点:

（1）全局搜索能力不强,很容易陷入局部最优解跳不出来；(可结合SA进行改进,因为SA在理率上是100%得到全局最优的,但搜索代价高)

 

第二篇：遗传算法程序

遗传算法程序（一）:

说明: fga.m 为遗传算法的主程序; 采用二进制Gray编码,采用基于轮盘赌法的非线性排名选择, 均匀交叉,变异操作,而且还引入了倒位操作!

function [BestPop,Trace]=fga(FUN,LB,UB,eranum,popsize,pCross,pMutation,pInversion,options) % [BestPop,Trace]=fmaxga(FUN,LB,UB,eranum,popsize,pcross,pmutation) % Finds a maximum of a function of several variables.

% fmaxga solves problems of the form:

% max F(X) subject to: LB <= X <= UB

% BestPop - 最优的群体即为最优的染色体群

% Trace - 最佳染色体所对应的目标函数值

% FUN - 目标函数

% LB - 自变量下限

% UB - 自变量上限

% eranum - 种群的代数,取100--1000(默认200)

% popsize - 每一代种群的规模；此可取50--200(默认100)

% pcross - 交叉概率,一般取0.5--0.85之间较好(默认0.8)

% pmutation - 初始变异概率,一般取0.05-0.2之间较好(默认0.1)

% pInversion - 倒位概率,一般取0.05－0.3之间较好(默认0.2)

% options - 1*2矩阵,options(1)=0二进制编码(默认0),option(1)~=0十进制编

%码,option(2)设定求解精度(默认1e-4)

%

% ------------------------------------------------------------------------

T1=clock;

if nargin<3, error('FMAXGA requires at least three input arguments'); end

if nargin==3, eranum=200;popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end

if nargin==4, popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end if nargin==5, pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end

if nargin==6, pMutation=0.1;pInversion=0.15;options=[0 1e-4];end

if nargin==7, pInversion=0.15;options=[0 1e-4];end

if find((LB-UB)>0)

error('数据输入错误,请重新输入(LB<UB):');

end

s=sprintf('程序运行需要约%.4f 秒钟时间,请稍等......',(eranum*popsize/1000));

disp(s);

global m n NewPop children1 children2 VarNum

bounds=[LB;UB]';bits=[];VarNum=size(bounds,1);

precision=options(2);%由求解精度确定二进制编码长度

bits=ceil(log2((bounds(:,2)-bounds(:,1))' ./ precision));%由设定精度划分区间

[Pop]=InitPopGray(popsize,bits);%初始化种群

[m,n]=size(Pop);

NewPop=zeros(m,n);

children1=zeros(1,n);

children2=zeros(1,n);

pm0=pMutation;

BestPop=zeros(eranum,n);%分配初始解空间BestPop,Trace

Trace=zeros(eranum,length(bits)+1);

i=1;

while i<=eranum

for j=1:m

value(j)=feval(FUN(1,:),(b2f(Pop(j,:),bounds,bits)));%计算适应度

end

[MaxValue,Index]=max(value);

BestPop(i,:)=Pop(Index,:);

Trace(i,1)=MaxValue;

Trace(i,(2:length(bits)+1))=b2f(BestPop(i,:),bounds,bits);

[selectpop]=NonlinearRankSelect(FUN,Pop,bounds,bits);%非线性排名选择

[CrossOverPop]=CrossOver(selectpop,pCross,round(unidrnd(eranum-i)/eranum));

%采用多点交叉和均匀交叉，且逐步增大均匀交叉的概率

%round(unidrnd(eranum-i)/eranum)

[MutationPop]=Mutation(CrossOverPop,pMutation,VarNum);%变异

[InversionPop]=Inversion(MutationPop,pInversion);%倒位

Pop=InversionPop;%更新

pMutation=pm0+(i^4)*(pCross/3-pm0)/(eranum^4);

%随着种群向前进化，逐步增大变异率至1/2交叉率

p(i)=pMutation;

i=i+1;

end

t=1:eranum;

plot(t,Trace(:,1)');

title('函数优化的遗传算法');xlabel('进化世代数(eranum)');ylabel('每一代最优适应度(maxfitness)');

[MaxFval,I]=max(Trace(:,1));

X=Trace(I,(2:length(bits)+1));

hold on; plot(I,MaxFval,'*');

text(I+5,MaxFval,['FMAX=' num2str(MaxFval)]);

str1=sprintf ('进化到 %d 代 ,自变量为 %s 时,得本次求解的最优值 %f\n对应染色体是：%s',I,num2str(X),MaxFval,num2str(BestPop(I,:))); disp(str1);

%figure(2);plot(t,p);%绘制变异值增大过程

T2=clock;

elapsed_time=T2-T1;

if elapsed_time(6)<0

elapsed_time(6)=elapsed_time(6)+60; elapsed_time(5)=elapsed_time(5)-1;

end

if elapsed_time(5)<0

elapsed_time(5)=elapsed_time(5)+60;elapsed_time(4)=elapsed_time(4)-1; end %像这种程序当然不考虑运行上小时啦

str2=sprintf('程序运行耗时 %d 小时 %d 分钟 %.4f 秒

',elapsed_time(4),elapsed_time(5),elapsed_time(6));

disp(str2);

%初始化种群

%采用二进制Gray编码,其目的是为了克服二进制编码的Hamming悬崖缺点 function [initpop]=InitPopGray(popsize,bits)

len=sum(bits);

initpop=zeros(popsize,len);%The whole zero encoding individual

for i=2:popsize-1

pop=round(rand(1,len));

pop=mod(([0 pop]+[pop 0]),2);

%i=1时,b(1)=a(1);i>1时,b(i)=mod(a(i-1)+a(i),2)

%其中原二进制串:a(1)a(2)...a(n),Gray串:b(1)b(2)...b(n)

initpop(i,:)=pop(1:end-1);

end

initpop(popsize,:)=ones(1,len);%The whole one encoding individual

%解码

function [fval] = b2f(bval,bounds,bits)

% fval - 表征各变量的十进制数

% bval - 表征各变量的二进制编码串

% bounds - 各变量的取值范围

% bits - 各变量的二进制编码长度

scale=(bounds(:,2)-bounds(:,1))'./(2.^bits-1); %The range of the variables numV=size(bounds,1);

cs=[0 cumsum(bits)];

for i=1:numV

a=bval((cs(i)+1):cs(i+1));

fval(i)=sum(2.^(size(a,2)-1:-1:0).*a)*scale(i)+bounds(i,1);

end

%选择操作

%采用基于轮盘赌法的非线性排名选择

%各个体成员按适应值从大到小分配选择概率：

%P(i)=(q/1-(1-q)^n)*(1-q)^i, 其中 P(0)>P(1)>...>P(n), sum(P(i))=1

function [selectpop]=NonlinearRankSelect(FUN,pop,bounds,bits)

global m n

selectpop=zeros(m,n);

fit=zeros(m,1);

for i=1:m

fit(i)=feval(FUN(1,:),(b2f(pop(i,:),bounds,bits)));%以函数值为适应值做排名依据 end

selectprob=fit/sum(fit);%计算各个体相对适应度(0,1)

q=max(selectprob);%选择最优的概率

x=zeros(m,2);

x(:,1)=[m:-1:1]';

[y x(:,2)]=sort(selectprob);

r=q/(1-(1-q)^m);%标准分布基值

newfit(x(:,2))=r*(1-q).^(x(:,1)-1);%生成选择概率

newfit=cumsum(newfit);%计算各选择概率之和

rNums=sort(rand(m,1));

fitIn=1;newIn=1;

while newIn<=m

if rNums(newIn)<newfit(fitIn)

selectpop(newIn,:)=pop(fitIn,:);

newIn=newIn+1;

else

fitIn=fitIn+1;

end

end

%交叉操作

function [NewPop]=CrossOver(OldPop,pCross,opts)

%OldPop为父代种群，pcross为交叉概率

global m n NewPop

r=rand(1,m);

y1=find(r<pCross);

y2=find(r>=pCross);

len=length(y1);

if len>2&mod(len,2)==1%如果用来进行交叉的染色体的条数为奇数，将其调整为偶数

y2(length(y2)+1)=y1(len);

y1(len)=[];

end

if length(y1)>=2

for i=0:2:length(y1)-2

if opts==0

[NewPop(y1(i+1),:),NewPop(y1(i+2),:)]=EqualCrossOver(OldPop(y1(i+1),:),OldPop(y1(i+2),:));

else

[NewPop(y1(i+1),:),NewPop(y1(i+2),:)]=MultiPointCross(OldPop(y1(i+1),:),OldPop(y1(i+2),:));

end

end

end

NewPop(y2,:)=OldPop(y2,:);

%采用均匀交叉

function [children1,children2]=EqualCrossOver(parent1,parent2)

global n children1 children2

hidecode=round(rand(1,n));%随机生成掩码

crossposition=find(hidecode==1);

holdposition=find(hidecode==0);

children1(crossposition)=parent1(crossposition);%掩码为1，父1为子1提供基因 children1(holdposition)=parent2(holdposition);%掩码为0，父2为子1提供基因 children2(crossposition)=parent2(crossposition);%掩码为1，父2为子2提供基因 children2(holdposition)=parent1(holdposition);%掩码为0，父1为子2提供基因

%采用多点交叉，交叉点数由变量数决定

function [Children1,Children2]=MultiPointCross(Parent1,Parent2)

global n Children1 Children2 VarNum

Children1=Parent1;

Children2=Parent2;

Points=sort(unidrnd(n,1,2*VarNum));

for i=1:VarNum

Children1(Points(2*i-1):Points(2*i))=Parent2(Points(2*i-1):Points(2*i));

Children2(Points(2*i-1):Points(2*i))=Parent1(Points(2*i-1):Points(2*i));

end

%变异操作

function [NewPop]=Mutation(OldPop,pMutation,VarNum)

global m n NewPop

r=rand(1,m);

position=find(r<=pMutation);

len=length(position);

if len>=1

for i=1:len

k=unidrnd(n,1,VarNum); %设置变异点数，一般设置1点 for j=1:length(k)

if OldPop(position(i),k(j))==1

OldPop(position(i),k(j))=0;

else

OldPop(position(i),k(j))=1;

End

end

end

end

NewPop=OldPop;

%倒位操作

function [NewPop]=Inversion(OldPop,pInversion)

global m n NewPop

NewPop=OldPop;

r=rand(1,m);

PopIn=find(r<=pInversion);

len=length(PopIn);

if len>=1

for i=1:len

d=sort(unidrnd(n,1,2));

if d(1)~=1&d(2)~=n

NewPop(PopIn(i),1:d(1)-1)=OldPop(PopIn(i),1:d(1)-1);

NewPop(PopIn(i),d(1):d(2))=OldPop(PopIn(i),d(2):-1:d(1)); NewPop(PopIn(i),d(2)+1:n)=OldPop(PopIn(i),d(2)+1:n); End

end

end

遗传算法程序（二）:

function youhuafun

D=code;

N=50; % Tunable

maxgen=50; % Tunable

crossrate=0.5; %Tunable

muterate=0.08; %Tunable

generation=1;

num = length(D);

fatherrand=randint(num,N,3);

score = zeros(maxgen,N);

while generation<=maxgen

ind=randperm(N-2)+2; % 随机配对交叉

A=fatherrand(:,ind(1:(N-2)/2));

B=fatherrand(:,ind((N-2)/2+1:end));

% 多点交叉

rnd=rand(num,(N-2)/2);

ind=rnd tmp=A(ind);

A(ind)=B(ind);

B(ind)=tmp;

% % 两点交叉

% for kk=1:(N-2)/2

% rndtmp=randint(1,1,num)+1;

% tmp=A(1:rndtmp,kk);

% A(1:rndtmp,kk)=B(1:rndtmp,kk);

% B(1:rndtmp,kk)=tmp;

% end

fatherrand=[fatherrand(:,1:2),A,B];

% 变异

rnd=rand(num,N);

ind=rnd [m,n]=size(ind);

tmp=randint(m,n,2)+1;

tmp(:,1:2)=0;

fatherrand=tmp+fatherrand;

fatherrand=mod(fatherrand,3);

% fatherrand(ind)=tmp;

%评价、选择

scoreN=scorefun(fatherrand,D);% 求得N个个体的评价函数 score(generation,:)=scoreN;

[scoreSort,scoreind]=sort(scoreN);

sumscore=cumsum(scoreSort);

sumscore=sumscore./sumscore(end);

childind(1:2)=scoreind(end-1:end);

for k=3:N

tmprnd=rand;

tmpind=tmprnd difind=[0,diff(tmpind)];

if ~any(difind)

difind(1)=1;

end

childind(k)=scoreind(logical(difind));

end

fatherrand=fatherrand(:,childind);

generation=generation+1;

end

% score

maxV=max(score,[],2);

minV=11*300-maxV;

plot(minV,'*');title('各代的目标函数值');

F4=D(:,4);

FF4=F4-fatherrand(:,1);

FF4=max(FF4,1);

D(:,5)=FF4;

save DData D

function D=code

load youhua.mat

% properties F2 and F3

F1=A(:,1);

F2=A(:,2);

F3=A(:,3);

if (max(F2)>1450)||(min(F2)<=900)

error('DATA property F2 exceed it''s range (900,1450]') end

% get group property F1 of data, according to F2 value F4=zeros(size(F1));

for ite=11:-1:1

index=find(F2<=900+ite*50);

F4(index)=ite;

end

D=[F1,F2,F3,F4];

function ScoreN=scorefun(fatherrand,D)

F3=D(:,3);

F4=D(:,4);

N=size(fatherrand,2);

FF4=F4*ones(1,N);

FF4rnd=FF4-fatherrand;

FF4rnd=max(FF4rnd,1);

ScoreN=ones(1,N)*300*11;

% 这里有待优化

for k=1:N

FF4k=FF4rnd(:,k);

for ite=1:11

F0index=find(FF4k==ite);

if ~isempty(F0index)

tmpMat=F3(F0index);

tmpSco=sum(tmpMat);

ScoreBin(ite)=mod(tmpSco,300); end

end

Scorek(k)=sum(ScoreBin);

end

ScoreN=ScoreN-Scorek;

遗传算法程序（三）：

%IAGA

function best=ga

clear

MAX_gen=200; %最大迭代步数 best.max_f=0; %当前最大的适应度 STOP_f=14.5; %停止循环的适应度 RANGE=[0 255]; %初始取值范围[0 255] SPEEDUP_INTER=5; %进入加速迭代的间隔 advance_k=0; %优化的次数

popus=init; %初始化

for gen=1:MAX_gen

fitness=fit(popus,RANGE); %求适应度 f=fitness.f;

picked=choose(popus,fitness); %选择 popus=intercross(popus,picked); %杂交 popus=aberrance(popus,picked); %变异 if max(f)>best.max_f

advance_k=advance_k+1;

x_better(advance_k)=fitness.x;

best.max_f=max(f);

best.popus=popus;

best.x=fitness.x;

end

if mod(advance_k,SPEEDUP_INTER)==0 RANGE=minmax(x_better);

RANGE

advance=0;

end

end

return;

function popus=init%初始化

M=50;%种群个体数目

N=30;%编码长度

popus=round(rand(M,N));

return;

function fitness=fit(popus,RANGE)%求适应度

[M,N]=size(popus);

fitness=zeros(M,1);%适应度

f=zeros(M,1);%函数值

A=RANGE(1);B=RANGE(2);%初始取值范围[0 255] for m=1:M

x=0;

for n=1:N

x=x+popus(m,n)*(2^(n-1));

end

x=x*((B-A)/(2^N))+A;

for k=1:5

f(m,1)=f(m,1)-(k*sin((k+1)*x+k));

end

end

f_std=(f-min(f))./(max(f)-min(f));%函数值标准化 fitness.f=f;fitness.f_std=f_std;fitness.x=x; return;

function picked=choose(popus,fitness)%选择 f=fitness.f;f_std=fitness.f_std;

[M,N]=size(popus);

choose_N=3; %选择choose_N对双亲 picked=zeros(choose_N,2); %记录选择好的双亲 p=zeros(M,1); %选择概率

d_order=zeros(M,1);

%把父代个体按适应度从大到小排序

f_t=sort(f,'descend');%将适应度按降序排列 for k=1:M

x=find(f==f_t(k));%降序排列的个体序号 d_order(k)=x(1);

end

for m=1:M

popus_t(m,:)=popus(d_order(m),:);

end

popus=popus_t;

f=f_t;

p=f_std./sum(f_std); %选择概率

c_p=cumsum(p)'; %累积概率

for cn=1:choose_N

picked(cn,1)=roulette(c_p); %轮盘赌

picked(cn,2)=roulette(c_p); %轮盘赌

popus=intercross(popus,picked(cn,:));%杂交

end

popus=aberrance(popus,picked);%变异

return;

function popus=intercross(popus,picked) %杂交

[M_p,N_p]=size(picked);

[M,N]=size(popus);

for cn=1:M_p

p(1)=ceil(rand*N);%生成杂交位置

p(2)=ceil(rand*N);

p=sort(p);

t=popus(picked(cn,1),p(1):p(2));

popus(picked(cn,1),p(1):p(2))=popus(picked(cn,2),p(1):p(2)); popus(picked(cn,2),p(1):p(2))=t;

end

return;

function popus=aberrance(popus,picked) %变异

P_a=0.05;%变异概率

[M,N]=size(popus);

[M_p,N_p]=size(picked)

U=rand(1,2);

for kp=1:M_p

if U(2)>=P_a %如果大于变异概率，就不变异 continue;

end

if U(1)>=0.5

a=picked(kp,1);

else

a=picked(kp,2);

end

p(1)=ceil(rand*N);%生成变异位置

p(2)=ceil(rand*N);

if popus(a,p(1))==1%0 1变换

popus(a,p(1))=0;

else

popus(a,p(1))=1;

end

if popus(a,p(2))==1

popus(a,p(2))=0;

else

popus(a,p(2))=1;

end

end

return;

function picked=roulette(c_p) %轮盘赌

[M,N]=size(c_p);

M=max([M N]);

U=rand; if U<c_p(1)

picked=1;

return;

end

for m=1:(M-1)

if U>c_p(m) & U<c_p(m+1)

picked=m+1;

break;

end

end

全方位的两点杂交、两点变异的改进的加速遗传算法（IAGA） 遗传算法优化pid参数matlab程序

chap5_4m

%GA(Generic Algorithm) program to optimize Parameters of PID clear all;

clear all;

global rin yout timef

G=100;

Size=30;

CodeL=10;

MinX(1)=zeros(1);

MaxX(1)=20*ones(1);

MinX(2)=zeros(1);

MaxX(2)=1.0*ones(1);

MinX(3)=zeros(1);

MaxX(3)=1.0*ones(1);

E=round(rand(Size,3*CodeL));%Initian Code!

BsJ=0;

for kg=1:1:G

time(kg)=kg;

for s=1:1:Size

m=E(s,:);

y1=0;y2=0;y3=0;

m1=m(1:1:CodeL);

for i=1:1:CodeL

y1=y1+m1(i)*2^(i-1);

end

Kpid(s,1)=(MaxX(1)-MinX(1))*y1/1023+MinX(1);

m2=m(CodeL+1:1:2*CodeL);

for i=1:1:CodeL

y2=y2+m2(i)*2^(i-1);

end

Kpid(s,2)=(MaxX(2)-MinX(2))*y2/1023+MinX(2);

m3=m(2*CodeL+1:1:3*CodeL);

for i=1:1:CodeL

y3=y3+m3(i)*2^(i-1);

end

Kpid(s,3)=(MaxX(3)-MinX(3))*y3/1023+MinX(3);

%*******Step 1:Evaluate Best J*******

Kpidi=Kpid(s,:);

[Kpidi,BsJ]=chap5_3f(Kpidi,BsJ);

BsJi(s)=BsJ;

end

[OderJi,IndexJi]=sort(BsJi);

BestJ(kg)=OderJi(1);

BJ=BestJ(kg);

Ji=BsJi+1e-10;

fi=1./Ji;

%Cm=max(Ji);

%fi=Cm-Ji; %Avoiding deviding zero

[Oderfi,Indexfi]=sort(fi);%Arranging fi small to bigger

%Bestfi=Oderfi(Size); %Let Bestfi=max(fi)

%BestS=Kpid(Indexfi(Size),:); %Let BestS=E(m),m is the Indexfi belong to %max(fi)

Bestfi=Oderfi(Size);%Let Bestfi=max(fi)

BestS=E(Indexfi(Size),:);%Let BestS=E(m),m is the Indexfi belong to max(fi)

kg

BJ

BestS;

%****Step 2:Select and Reproduct Operation***

fi_sum=sum(fi);

fi_Size=(Oderfi/fi_sum)*Size;

fi_S=floor(fi_Size); %Selecting Bigger fi value

kk=1;

for i=1:1:Size

for j=1:1:fi_S(i) %Select and Reproduce

TempE(kk,:)=E(Indexfi(i),:);

kk=kk+1; %kk is used to reproduce

end

end

%**********Step 3:Crossover Operation******

pc=0.06;

n=ceil(20*rand);

for i=1:2:(Size-1)

temp=rand;

if pc>temp

for j=n:1:20

TempE(i,j)=E(i+1,j);

TempE(i+1,j)=E(i,j);

end

end

end

TempE(Size,:)=BestS;

E=TempE;

%***************Step 4: Mutation Operation************** %pm=0.001;

pm=0.001-[1:1:Size]*(0.001)/Size;%Bigger fi,smaller pm %pm=0.0; %No mutation

%pm=0.1; %Big mutation

for i=1:1:Size

for j=1:1:3*CodeL

temp=rand;

if pm>temp %Mutation Condition

if TempE(i,j)==0

TempE(i,j)=1;

else

TempE(i,j)=0;

End

end

end

end

%Guarantee TempE(Size,:)belong to the best individual TempE(Size,:)=BestS;

E=TempE;

%*************************************************** end

Bestfi

BestS

Kpidi

Best_J=BestJ(G)

figure(1);

plot(time,BestJ);

xlabel('Time');ylabel('Best J');

figure(2);

plot(timef,rin,'r',timef,yout,'b'); xlabel('Time(s)');ylabel('ran,yout');

chap5_3f.m

function [Kpidi,BsJ]=pid_gaf(Kpidi,BsJ)

global rin yout timef

ts=0.001;

sys=tf(400,[1,50,0]);

dsys=c2d(sys,ts,'z');

[num,den]=tfdata(dsys,'v');

rin=1.0;

u_1=0.0;u_2=0.0;

y_1=0.0;y_2=0.0;

x=[0,0,0]'; B=0;

error_1=0;

tu=1;

s=0;

P=100;

for k=1:1:P

timef(k)=k*ts;

r(k)=rin;

u(k)=Kpidi(1)*x(1)+Kpidi(2)*x(2)+Kpidi(3)*x(3);

if u(k)>=10

u(k)=10;

end

if u(k)<=-10

u(k)=-10;

end

yout(k)=-den(2)*y_1-den(3)*y_2+num(2)*u_1+num(3)*u_2; error(k)=r(k)-yout(k);

%-------------------Return of PID parameters---------------- u_2=u_1;u_1=u(k);

y_2=y_1;y_1=yout(k);

x(1)=error(k); % Calculating P

x(2)=(error(k)-error_1)/ts; % D

x(3)=x(3)+error(k)*ts; % I

error_2=error_1;

error_1=error(k);

if s==0

if yout(k)>0.95&yout(k)<1.05

tu=timef(k);

s=1;

end

end

end

for i=1:1:P

Ji(i)=0.999*abs(error(i))+0.01*u(i)^2*0.1; B=B+Ji(i);

f i>1

erry(i)=yout(i)-yout(i-1);

if erry(i)<0

B=B+100*abs(erry(i));

End

End

end

Bsj=B+0.2*tu*10