来自集智百科
遗传算法（Genetic Algorithms）是一种很有趣的理论，由密歇根大学的约翰·霍兰德（John Holland）和他的同事于二十世纪六十年代在对元胞自动机（cellular automata）研究时提出。在八十年代前，对于遗传算法的研究还仅仅限于理论方面，直到在匹兹堡召开了第一届世界遗传算法大会。随着计算机计算能力的发展和实际应用需求的增多，遗传算法逐渐进入实际应用阶段。
遗传算法的基本思想，是让程序像生物那样在交配，变异中进化，产生出更适宜环境的（逼近目标函数的）程序。
遗传算法有很多不同的实现形式，一般都是用一个01串表达一个程序，但《集体智慧编程》（programming collective intelligence）里介绍了一种非常有意思的应用：用来寻找数据拟合的最优方程。
假如我们有如下数据：
许多人的第一直觉是使用多元回归来拟合方程f(x,y)，但我们这里要用遗传算法来做这件事。我们打算用一个程序代表一个方程，然后让方程之间交配、变异，最终进化出一个最符合数据的方程。
要用程序表达方程，显然不可能直接用01串实现，因为任意构造的01串及其交配变异是没有数学意义的。我们要用解析树（parse tree）的概念
树上的每个节点或者表达一种对它子节点进行的数学操作，或者表达一个参数或变量。运算时，树从下往上收缩。
上述树就可以表达如下程序：
def func(x,y)
return y + 5
return y - 2
因此，也就表达了一个方程。实际上，大多数程序语言在使用机器编译（compile）或解释（interpret）的时候，都是先变成这样一棵树。也许只有Lisp是例外，因为它相当于要求程序员直接写出这样的树结构。看起来树似乎只能表达比较简单的运算，但如果考虑到节点位置上的数学操作可以很复杂，例如欧式距离或者高斯函数，并且叶节点可以引用根节点，构成loop，树将可以表达非常复杂的运算。
变异对于01串表达程序的遗传算法模型来说就是随机地把一些0变成1或者相反。但在树结构里，我们定义两种变异：
一种是改变节点上的操作符号：
一种是替换树的一部分枝干
交配就是让两棵树相遇，互换一部分枝干，拼接出一棵新的树
我们先定义树的基本结构
from random import random,randint,choice
from copy import deepcopy
import numpy as np
class fwrapper:
def __init__(self,function,childcount,name):
self.function=function
self.childcount=childcount
self.name=name
class node:
def __init__(self,fw,children):
self.function=fw.function
self.name=fw.name
self.children=children
def evaluate(self,inp):
results=[n.evaluate(inp) for n in self.children]
return self.function(results)
def display(self,indent=0):
print (' '*indent)+self.name
for c in self.children:
c.display(indent+1)
class paramnode:
def __init__(self,idx):
self.idx=idx
def evaluate(self,inp):
return inp[self.idx]
def display(self,indent=0):
print '%sp%d' % (' '*indent,self.idx)
class constnode:
def __init__(self,v):
def evaluate(self,inp):
return self.v
def display(self,indent=0):
print '%s%d' % (' '*indent,self.v)
其中fwrapper代表着一种运算，它接受三个参数：函数的定义，函数里参数的个数，函数的名字。node就是一个节点，它的evaluate函数可以接受子节点的输入，并把fawapper定义的函数运用在子节点上，得到输出结果。它的display函数可以打印出节点以下的树的形式，方便我们分析程序内部表达的函数。paramnode是参数节点，总是返回输入的参数idx，constnode是常数节点，不管输入时什么，总是返回一个常数。
接下来我们定义一些基本的运算：
addw=fwrapper(lambda l:l[0]+l[1],2,'add')
subw=fwrapper(lambda l:l[0]-l[1],2,'subtract')
mulw=fwrapper(lambda l:l[0]*l[1],2,'multiply')
def iffunc(l):
if l[0]&0: return l[1]
else: return l[2]
ifw=fwrapper(iffunc,3,'if')
def isgreater(l):
if l[0]&l[1]: return 1
else: return 0
gtw=fwrapper(isgreater,2,'isgreater')
flist=[addw,mulw,ifw,gtw,subw]
其中加减乘都可以使用lambda一句话实现，但分段函数和比较函数要先定义一个函数，然后再用fwrapper。在flist里我们把这些函数都装起来，以便将来使用。
有了这些函数，其实我们已经可以定义一个示例树并观察其运算后果了
def exampletree( ):
return node(ifw,[
node(gtw,[paramnode(0),constnode(3)]),
node(addw,[paramnode(1),constnode(5)]),
node(subw,[paramnode(1),constnode(2)]),
exampletree=exampletree( )
exampletree.evaluate([2,3])
exampletree.evaluate([5,3])
exampletree.display( )
我们还可以制造随机树，用来作为演化的初始值
def makerandomtree(pc,maxdepth=4,fpr=0.5,ppr=0.6):
if random( )&fpr and maxdepth&0:
f=choice(flist)
children=[makerandomtree(pc,maxdepth-1,fpr,ppr)
for i in range(f.childcount)]
return node(f,children)
elif random( )&ppr:
return paramnode(randint(0,pc-1))
return constnode(randint(0,10))
random1=makerandomtree(2)
random1.evaluate([7,1])
random1.evaluate([2,4])
random2=makerandomtree(2)
random2.evaluate([5,3])
random2.evaluate([5,20])
random1.display( )
random2.display( )
接下来我们定义变异和交配函数来对树结构进行操作。
def mutate(t,pc,probchange=0.1):
if random( )&probchange:
return makerandomtree(pc)
result=deepcopy(t)
if isinstance(t,node):
result.children=[mutate(c,pc,probchange) for c in t.children]
return result
def crossover(t1,t2,probswap=0.7,top=1):
if random( )&probswap and not top:
return deepcopy(t2)
result=deepcopy(t1)
if isinstance(t1,node) and isinstance(t2,node):
result.children=[crossover(c,choice(t2.children),probswap,0) for c in t1.children]
return result
random2.display( )
muttree=mutate(random2,2)
muttree.display( )
cross=crossover(random1,random2)
cross.display( )
为了准备测试数据，我们使用事先给定的函数制造一个数据。其实上面那张表里面的数据就是这么制造出来的。为了便于评估数据，我们还需要准备相应的衡量一棵树拟合数据的结果的函数。
def hiddenfunction(x,y):
return x**2+2*y+3*x+5
def buildhiddenset( ):
rows=[]
for i in range(200):
x=randint(0,10)
y=randint(0,10)
rows.append([x,y,hiddenfunction(x,y)])
return rows
def scorefunction(tree,s):
for data in s:
v=tree.evaluate([data[0],data[1]])
dif+=abs(v-data[2])
return dif
def getrankfunction(dataset):
def rankfunction(population):
scores=[(scorefunction(t,dataset),t) for t in population]
scores.sort( )
return scores
return rankfunction
hiddenset=buildhiddenset( )
scorefunction(random2,hiddenset)
scorefunction(random1,hiddenset)
一切都准备好，就可以开始进行遗传算法的迭代了：
def evolve(pc,popsize,rankfunction,maxgen=500,
mutationrate=0.1,breedingrate=0.4,pexp=0.7,pnew=0.05):
# Returns a random number, tending towards lower numbers. The lower pexp
# is, more lower numbers you will get
def selectindex( ):
return int(np.log(random( ))/np.log(pexp))
# Create a random initial population
population=[makerandomtree(pc) for i in range(popsize)]
for i in range(maxgen):
scores=rankfunction(population)
print scores[0][0]
if scores[0][0]==0: break
# The two best always make it
newpop=[scores[0][1],scores[1][1]]
# Build the next generation
while len(newpop)&popsize:
if random( )&pnew:
newpop.append(mutate(
crossover(scores[selectindex( )][1],
scores[selectindex( )][1],
probswap=breedingrate),
pc,probchange=mutationrate))
# Add a random node to mix things up
newpop.append(makerandomtree(pc))
population=newpop
scores[0][1].display( )
return scores[0][1]
rf=getrankfunction(buildhiddenset( ))
final = evolve(2,500,rf,mutationrate=0.2,breedingrate=0.1,pexp=0.7,pnew=0.1)
有趣的是，许多时候我们会找到和原始公式一模一样，但比原始公式复杂的树。其实对树本身的变换，也就是符号计算背后的原理。这样，我们就更理解为什么说数学系统其实也是一个图灵机了。遗传算子简介&
1 选择算子&
把当前群体中的个体按与适应值成比例的概率
复制到新的群体中，遗传算法中最
常用的选择方式是轮盘赌选择方式。轮盘赌选择步骤如下：&
（1）求群体中所有个体的适应值总和S；&
（2）产生一个0到S之间的随机数M；&
（3）从群体中编号为1的个体开始，将其适应值与后续个体的适应值相加，直到累加和大于等于M，则停止。其中，那个最后加进去的个体即为新选择的个体。&
选择算子作用的效果是提高了群体的平均适应值及最差的适应值，低适应值的个体趋于被淘汰，高适应值的个体趋于被复制，但是是以损失群体的多样性为代价，选择算子并没有产生新的个体，当然群体中最好个体的适应值不会改进。
2 交叉算子&
交叉算子（又称杂交算子）每次作用在种群随机选取的两个个体上产生两个不同的子个体，它们一般与父个体不同，但又包含父个体的遗传物质，交叉运算是遗传算法区别于其它进化算法的重要特征。&
交叉规则内容包括两个方面：
（1）从种群中对个体随即配对，并按预定的交叉概率来决定是否进行交叉操作。
（2）设定个体的交叉点，并对这些点前后的配对个体的基因相互交换。&
例如：首先产生一个1到h（其中h为染色体分量的个数）的随机数i（称为交叉点），然后配对的两个个体相互交换从（i+1）到h的位子，如对以下两个数进行交叉且交叉点选择在2，即i=2，则 &
对种群要确定交叉概率。随机选择N&个个体进行交叉，其余不变。&
显然，利用选择、交叉算子可以产生具有更高平均适应值和更好个体的群体。但仅仅如此，容易导致局部最优解。
3 变异算子&
变异算子能使个体发生突然变异，导入新的遗传信息，使寻优有可能指向未探知区域，是提高全局最优搜索能力的有效步骤，也是保持群体差异，防止过早出现收敛现象的重要手段。以一个很小的变异概率，随机的改变染色体上的某个基因（）,具有增加群体多
样性的效果。例如：。
遗传算法求解步骤
遗传算法求解步骤
（1） 选择问题解的一个编码，给出一个有N个染色体的初始群体pop(1)，t=1。
（2） 对群体中的每一个染色体，计算它的适应函数值。
（3） &若停止规则满足，则算法停止，否则计算概率，并以此概率分布，从pop(t)中随机选取N个染色体构成一个新的种群newpop(t)。
(4) & 通过交叉（交叉概率为），得到N个染色体的crosspop(t+1)。
(5) & 以较小的变异概率使得某染色体的一个基因发生变异，形成新的群体mutpop(t+1)。 &令t=t+1，pop(t)=mutpop(t)，重复第（2）步。流程如图一所示。
& & & & & & & & & & & & & & & & & & & & & & &
遗传算法特点 & &
遗传算法的优越性：
（1）作为数值求解方法具有普适性，对目标函数几乎没有要求，总能以极大概率找到全局最优解。
（2）遗传算法在求解很多组合优化问题时，不需要很高的技巧和对问题有非常深入的了解，在给问题的决策变量编码后，其计算过程比较简单。
（3）与其他启发式算法有较好的兼容性，易于别的技术相结合，形成更优的问题解决方法。
&遗传算法的欺骗性问题：
（1）在遗传进化的初期，通常会产生一些超常个体，按比例选择，这些个体竞争力太强而控制了选择过程，影响算法的全局优化性能。（2）在遗传进化的后期，即算法接近收敛时，由于种群中个体适应度差异较小，继续优化的潜能降低，可能获
一个y对应一个x的案例代码
% Optimizing a function using Simple Genetic Algorithm with elitist preserved
%Max f(x1,x2)=100*(x1*x1-x2).^2+(1-x1).^2; -2.0480&=x1,x2&=2.0480
%函数的最大值为3905.9262，此时两个参数的值是-2.0480,2.0480
% Author: Wang Yonglin (wylin77@126.com)
format long;%设定数据显示格式
%初始化参数
T=20;%仿真代数
N=80;% 群体规模
pc=0.6;%交叉概率
pm=0.001;%变异概率
umax=10;umin=0;%参数取值范围
L=10;%单个参数字串长度，总编码长度2L
bval=round(rand(N,2*L));%初始种群
bestv=-%最优适应度初值
for ii=1:T
%解码，计算适应度：为了优化后的评价
% for i=1:N
% y1=0;y2=0;
% for j=1:1:L
% y1=y1+bval(i,L-j+1)*2^(j-1);
% x1=(umax-umin)*y1/(2^L-1)+
% for j=1:1:L
% y2=y2+bval(i,2*L-j+1)*2^(j-1);
% x2=(umax-umin)*y2/(2^L-1)+
%obj(i)=100*(x1*x1-x2).^2+(1-x1).^2; %目标函数
for j=1:1:L
y=y+bval(i,L-j+1)*2^(j-1);
x =(umax-umin)*y /(2^L-1)+
% obj(i)=x+10*sin(5*x)+7*cos(4*x);
obj(i)=x*x-1;
% xx(i,:)=[x1,x2];
xx(i,:)=[x];
func=%目标函数转换为适应度函数
p=func./sum(func);
q=cumsum(p);%累加
[fmax,indmax]=max(func);%求当代最佳个体
if fmax&=bestv
bestv=%到目前为止最优适应度值
bvalxx=bval(indmax,:);%到目前为止最佳位串
optxx=xx(indmax,:);%到目前为止最优参数
Bfit1(ii)= % 存储每代的最优适应度
%%%%遗传操作开始
%算法实现时采用随机数方法，先将每个染色体的适应度除以所有染色体适应度的和，
%再累加，使他们根据适应度的大小分布于0-1之间，适应度大的占的区域大，
%然后随机生成一个0-1之间的随机数，随机数落到哪个区域，对应的染色体就被选中。
%重复操作，选出群体规模规定数目的染色体。这个操作就是&优胜劣汰，适者生存&，但没有产生新个体。
%-----------------------------轮盘赌选择---------------------------------
for i=1:(N-1)
tmp=find(r&=q);
newbval(i,:)=bval(tmp(1),:);
newbval(N,:)=%最优保留
%-----------------------------单点交叉------------------------------------
%参与交叉的染色体是轮盘赌选出来的个体，并且还要根据选择概率来确定是否进行交叉
%（生成0-1之间随机数，看随机数是否小于规定的交叉概率），否则直接进入变异操作
for i=1:2:(N-1)
point=ceil(rand*(2*L-1));%取得一个1到2L-1的整数
ch=bval(i,:);
bval(i,point+1:2*L)=bval(i+1,point+1:2*L);
bval(i+1,point+1:2*L)=ch(1,point+1:2*L);
bval(N,:)=%最优保留
%----------------------------位点变异 -----------------------------------
%对于二进制位串，0变为1，1变为0就是变异。采用概率确定变异位，对每一位生成一个0-1之间的随机数，
%看是否小于规定的变异概率，小于的变异，否则保持原状。
%这个操作能够使个体不同于父辈而具有自己独立的特征基因，主要用于跳出局部极值
mm=rand(N,2*L)&%N行
mm(N,:)=zeros(1,2*L);%最后一行不变异，强制赋0
bval(mm)=1-bval(mm);
plot(Bfit1);% 绘制最优适应度进化曲线
bestv %输出最优适应度值
optxx %输出最优参数
二、有两个变量一个式子的代码
实例求函数-100*(x(1)^2-x(2))^2-(1-x(1))^2的最小值,两个变量的取值范围是from [-2.048;-2.048] to [2.048;2.048].1）使用ga工具箱X = ga(@(x) -100*(x(1)^2-x(2))^2-(1-x(1))^2,2,[],[],[],[],[-2.048;-2.048],[2.048;2.048])2）未使用ga工具箱
%//Generic Algorithm for function f(x1,x2) optimum
%//Parameters
umax=2.048;
umin=-2.048;
E=round(rand(Size,2*CodeL));
%//Initial Code 产生初始群体
%//Main Program
for k=1:1:G
time(k)=k;
%//选择 %//计算目标函数
for s=1:1:Size %//对每一行
y1=0;y2=0;
%//Uncoding
m1=m(1:1:CodeL);
for i=1:1:CodeL
y1=y1+m1(i)*2^(i-1);
x1=(umax-umin)*y1/1023+ %//计算参数1
m2=m(CodeL+1:1:2*CodeL);
for i=1:1:CodeL
y2=y2+m2(i)*2^(i-1);
x2=(umax-umin)*y2/1023+ %//计算参数2
F(s)=100*(x1^2-x2)^2+(1-x1)^2; %//计算目标函数 ，F是向量
%//****** Step 1 : Evaluate BestJ ******
BestJ(k)=min(Ji); %//找到F中最大的一项，保存到向量BestJ
%//Fitness Function
[Oderfi,Indexfi]=sort(fi);
%//Arranging fi small to bigger
Bestfi=Oderfi(Size);
%//Let Bestfi=max(fi)
BestS=E(Indexfi(Size),:);
%//Let BestS=E(m), m is the Indexfi belong to max(fi)
%//****** Step 2 : Select and Reproduct Operation******选择F较大的fi项
fi_sum=sum(fi);
fi_Size=(Oderfi/fi_sum)*S
fi_S=floor(fi_Size);
%//Selecting Bigger fi value ,fi_S为80项的向量,每一项为0或1,1表示该项被选择
for i=1:1:Size
for j=1:1:fi_S(i)
%//Select and Reproduce
TempE(kk,:)=E(Indexfi(i),:);
%//kk is used to reproduce
end %//选择完毕
fprintf('size TempE %//d\n',size(TempE))
%//************ Step 3 : Crossover Operation ************交换
n=ceil(20*rand);
for i=1:2:(Size-1)
if pc&temp
%//Crossover Condition
for j=n:1:20
TempE(i,j)=E(i+1,j);
TempE(i+1,j)=E(i,j);
TempE(Size,:)=BestS;
fprintf('size E %//d\n',size(E))
%//************ Step 4: Mutation Operation **************
%//pm=0.001;
%//pm=0.001-[1:1:Size]*(0.001)/S %//Bigger fi, smaller Pm
%//pm=0.0;
%//No mutation
%//Big mutation
for i=1:1:Size
for j=1:1:2*CodeL
if pm&temp
%//Mutation Condition
if TempE(i,j)==0
TempE(i,j)=1;
TempE(i,j)=0;
%//Guarantee TempPop(30,:) is the code belong to the best individual(max(fi))
TempE(Size,:)=BestS;
Max_Value=Bestfi
figure(1);
plot(time,BestJ);
xlabel('Times');ylabel('Best J');
figure(2);
plot(time,bfi);
xlabel('times');ylabel('Best F');
阅读(...) 评论() 上传我的文档
 下载
 收藏
粉丝量：127
工程师，工作经验5年以上，很多方案类资料自己整理
 下载此文档
遗传算法的实现及应用举例.
下载积分：3000
内容提示：遗传算法的实现及应用举例.
文档格式：PPT|
浏览次数：223|
上传日期： 03:07:25|
文档星级：
全文阅读已结束，如果下载本文需要使用
 3000 积分
下载此文档
该用户还上传了这些文档
遗传算法的实现及应用举例.
关注微信公众号没有更多推荐了，
不良信息举报
举报内容：
基本遗传算法(GA)的算法原理、步骤、及Matlab实现
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！