遗传算法适应值函数

A. 如何用遗传算法工具箱中的函数画出适应度函数曲线

matlab有遗传算法工具箱。

核心函数：
(1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始种群的生成函数
【输出参数】
pop--生成的初始种群
【输入参数】
num--种群中的个体数目
bounds--代表变量的上下界的矩阵
eevalFN--适应度函数
eevalOps--传递给适应度函数的参数
options--选择编码形式(浮点编码或是二进制编码)[precision F_or_B],如
precision--变量进行二进制编码时指定的精度
F_or_B--为1时选择浮点编码，否则为二进制编码,由precision指定精度)

(2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,
termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)--遗传算法函数
【输出参数】
x--求得的最优解
endPop--最终得到的种群
bPop--最优种群的一个搜索轨迹
【输入参数】
bounds--代表变量上下界的矩阵
evalFN--适应度函数
evalOps--传递给适应度函数的参数
startPop-初始种群
opts[epsilon prob_ops display]--opts(1:2)等同于initializega的options参数，第三个参数控制是否输出，一般为0。如[1e-6 1 0]
termFN--终止函数的名称,如['maxGenTerm']
termOps--传递个终止函数的参数,如[100]
selectFN--选择函数的名称,如['normGeomSelect']
selectOps--传递个选择函数的参数,如[0.08]
xOverFNs--交叉函数名称表，以空格分开，如['arithXover heuristicXover simpleXover']
xOverOps--传递给交叉函数的参数表，如[2 0;2 3;2 0]
mutFNs--变异函数表，如['boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation']
mutOps--传递给交叉函数的参数表,如[4 0 0;6 100 3;4 100 3;4 0 0]

注意】matlab工具箱函数必须放在工作目录下
【问题】求f(x)=x+10*sin(5x)+7*cos(4x)的最大值，其中0<=x<=9
【分析】选择二进制编码，种群中的个体数目为10，二进制编码长度为20，交叉概率为0.95,变异概率为0.08
【程序清单】
%编写目标函数
function[sol,eval]=fitness(sol,options)
x=sol(1);
eval=x+10*sin(5*x)+7*cos(4*x);
%把上述函数存储为fitness.m文件并放在工作目录下

initPop=initializega(10,[0 9],'fitness');%生成初始种群，大小为10
[x endPop,bPop,trace]=ga([0 9],'fitness',[],initPop,[1e-6 1 1],'maxGenTerm',25,'normGeomSelect',
[0.08],['arithXover'],[2],'nonUnifMutation',[2 25 3]) %25次遗传迭代

运算借过为：x =
7.8562 24.8553(当x为7.8562时，f（x）取最大值24.8553)

注：遗传算法一般用来取得近似最优解，而不是最优解。

遗传算法实例2

【问题】在－5<=Xi<=5,i=1,2区间内，求解
f(x1,x2)=-20*exp(-0.2*sqrt(0.5*(x1.^2+x2.^2)))-exp(0.5*(cos(2*pi*x1)+cos(2*pi*x2)))+22.71282的最小值。
【分析】种群大小10，最大代数1000，变异率0.1,交叉率0.3
【程序清单】
％源函数的matlab代码
function [eval]=f(sol)
numv=size(sol,2);
x=sol(1:numv);
eval=-20*exp(-0.2*sqrt(sum(x.^2)/numv)))-exp(sum(cos(2*pi*x))/numv)+22.71282;
%适应度函数的matlab代码
function [sol,eval]=fitness(sol,options)
numv=size(sol,2)-1;
x=sol(1:numv);
eval=f(x);
eval=-eval;
%遗传算法的matlab代码
bounds=ones(2,1)*[-5 5];
[p,endPop,bestSols,trace]=ga(bounds,'fitness')

注：前两个文件存储为m文件并放在工作目录下，运行结果为
p =
0.0000 -0.0000 0.0055

大家可以直接绘出f(x)的图形来大概看看f（x）的最值是多少，也可是使用优化函数来验证。matlab命令行执行命令：
fplot('x+10*sin(5*x)+7*cos(4*x)',[0,9])

evalops是传递给适应度函数的参数，opts是二进制编码的精度，termops是选择maxGenTerm结束函数时传递个maxGenTerm的参数，即遗传代数。xoverops是传递给交叉函数的参数。mutops是传递给变异函数的参数。

B. 遗传算法中常用的适应度函数是什么呢

1.物竞――适应度函数（fitness function）

自然界生物竞争过程往往包含两个方面：生物相互间的搏斗与及生物与客观环境的搏斗过程。但在我们这个实例里面，你可以想象到，袋鼠相互之间是非常友好的，它们并不需要互相搏斗以争取生存的权利。它们的生死存亡更多是取决于你的判断。因为你要衡量哪只袋鼠该杀，哪只袋鼠不该杀，所以你必须制定一个衡量的标准。而对于这个问题，这个衡量的标准比较容易制定：袋鼠所在的海拔高度。（因为你单纯地希望袋鼠爬得越高越好。）所以我们直接用袋鼠的海拔高度作为它们的适应性评分。即适应度函数直接返回函数值就行了。

引自：网页链接

C. 遗传算法的适度函数是什么意思举个例说明下最好通俗

适应度用于评价个体的优劣程度,适应度越大个体越好,反之适应度越小则个体越差；根据适应度的大小对个体进行选择,以保证适应性能好的个体有更多的机会繁殖后代,使优良特性得以遗传.因此,遗传算法要求适应度函数值必须是非负数,而在许多实际问题中,求解的目标通常是费用最小,而不是效益最大,因此需要将求最小的目标根据适应度函数非负原则转换为求最大目标的形式。
----------------
如何通俗易懂地解释遗传算法？有什么例子？
遗传算法，核心是达尔文优胜劣汰适者生存的进化理论的思想。

我们都知道一个种群，通过长时间的繁衍，种群的基因会向着更适应环境的趋势进化，牛B个体的基因被保留，后代越来越多，适应能力低个体的基因被淘汰，后代越来越少。经过几代的繁衍进化，留下来的少数个体，就是相对能力最强的个体了。

那么在解决一些问题的时候，我们能不能学习这样的思想，比如先随机创造很多很多的解，然后找一个靠谱的评价体系，去筛选比较好的解，再用这些好的解像生小宝宝一样生一堆可能更好的解，然后再筛再生，反复弄个几代，得到的说不定就是近似最优解哟

说干就干，有一个经典组合问题叫“背包问题”，我们拿这种思路来试试

“背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。”

这个问题的衍生简化问题“0-1背包问题” 增加了限制条件：每件物品只有一件，可以选择放或者不放，更适合我们来举例

这样的问题如果数量少，当然最好选择穷举法
比如一共3件商品，用0表示不取，1表示取，那么就一共有
000 001 010
011 100 101
110 111
这样8种方案，然后让计算机去累加和，与重量上限比较，留下来的解里取最大即可。

但如果商品数有300,3000,甚至3w种呢，计算量太大穷举法可能就不适用了，这时如果遗传算法使用得当，就能在较短的时间内帮我们找到近似的最优解，我们继续往下看：

新的问题是12件商品的0-1背包问题

我们先让计算机随机产生1000个12位的二级制数

把总重量超过背包上限的解筛掉

剩下的两两一对随机交换“基因片段”产生下一代
交换前：
0000 1100 1101
0011 0101 0101
交换后：
0000 0101 1101
0011 1100 0101

再筛选，再交配，如此反复几代，留下的解携带的“基因“差不多就是最好的了，怎么样跟生物进化是不是一模一样？
其实还差点，生物繁殖过程中，新产生的基因是有一定几率突变的，这是很多优良性状的重要来源，遗传算法中可也不能忽略它

比如：
变异前：
000101100101
变异后：
000101110101

那也有人得疑惑了，我怎么知道要让哪个地方产生突变呢？其实蜘蛛侠NB之前，他也不知道蜘蛛咬在那能让他变NB而不是SB，这就是一个概率问题。我们在设计算法的时候，会给每个基因设置一个突变概率（当然是非常非常小了）同样的在基因交换阶段交换哪些基因呢，也是一个算法设置问题。

总结一下，遗传算法应该有
一个基本函数：适度函数f(x)
三个基本操作：选择，交叉，变异

一.适度函数
适度函数很好理解，其实就是指解的筛选标准，比如我刚才说的把所有超过上限重量的解筛选掉，但是不是有更好的筛选标准或者这个现有的标准根本就是个渣呢？这将直接影响最后结果的接近程度以及求解所耗费的时间，所以设置一个好的适度函数很重要

二.选择
刚才为了大家理解方便，我直接让所有解都参与了后续的交叉以及变异，但真实世界可不是这样子的，因为也不是每个人都会结婚生子的对吧。
说直白点，所谓【屌丝注孤生】【工科男注孤生】什么的还不是因为loser的基因不适合往下传呗。不过实际情况是我们偶尔也能看到或听到屌丝逆袭、鲜花牛粪之类励志故事，只不过频率比较低咯

没错，概率！在遗传算法中选择也是个概率问题，在解的世界中（姑且这么称呼吧）适度更高的高富帅们是不是应该有更高的概率被选去传宗接代才合适呢？不过和现实世界一样，适度低的屌丝解是要给人家一点希望的对不对？所以

在选择一些解来产生下一代时，一种常用的选择策略是 “比例选择”，也就是个体被选中的概率与其适应度函数值成正比。假设群体的个体总数是M，那么那么一个体Xi被选中的概率为f(Xi)/( f(X1) + f(X2) + …….. + f(Xn) )

三.交叉
这是例子中详细说到的，交换两个解的部分”基因”，来构造两个子代的解。

四.变异
在繁殖子代的过程中，新产生的解中的“基因”会以一定的概率出错，称为变异。我们可以吧变异发生的概率设置为Pm

五.基本遗传算法优化
精英主义：这是基本遗传算法的一种优化。目的是防止进化过程中产生的最优解被变异和交叉所破坏。《遗传算法原理及应用》介绍的最优保存策略是：即当前种群中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。

后记：
其实不管是遗传算法，还是模拟退火算法或者其他算法，其本质都是借鉴自然界中的规则规律，人为的为问题设置了一个模拟模型，然后用大自然告诉我们的规律去找最优解，在理解这些算法的时候，可以照着这个思路去走，一般能让你快速拨云见日，了解算法的核心思想。
比如遗传算法，我们可以对比种群的进化，给问题设置的模型就是：
这样参照着我们熟悉的知识体系，去理解学习，原来听上去遥不可及的理论是不是一下就变得亲切易懂了吧？

可是我们再看一些教科书或者就拿网络来说（怕也是摘抄的某本书上的段落）
真的是通篇不说人话啊！对已经了解这个算法思想的人来说，还能勉强硬着头皮看下去，但对入门者来说，这TMD简直就是噩梦！而这完全是国内各种教材的通病！

我其实一直在想，教材面向的明明就是望门欲入的初学者，你不弄得生动活泼一点招徕门徒就算了，在一群幼儿园小朋友面前卖弄之乎者也还显本事了是么！我是还记得我们学校的高数书编的有多么生涩难懂，结果第一节课老教授上课时还说“我们不用同济的版本，那本书太浅，不适合我们学校的学生” 可是在我和大多数同学看来，同济版本的高数倒更像是为了要入门的同学编写的教材，自己学校编的那本却更像是给同行评阅炫耀作者深度的大部头。

知识明明可以讲的更有趣，让人愿意入其门来探个究竟。

作者：弹弹弹球

D. 遗传算法的基本原理

遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。