当前位置:文档之家› 遗传算法在求解复杂函数给定区间上最值中的应用

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

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

计算智能导论大作业

---遗传算法在求解复杂函数给定区

间上最值中的应用

一、遗传算法简介

遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解,对于各种通用问题都可以使用

1.1术语说明

由于遗传算法是由进化论和遗传学机理而产生的搜索算法,所以在这个算法中会用到很多生物遗传学知识,下面是一些常用术语的说明:

染色体

染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。

基因

基因是串中的元素,基因用于表示个体的特征。例如有一个串S=1011,则其中的1,0,1,1这4个元素分别称为基因。它们的值称为等位基因(Alleles)。

基因位点

基因位点在算法中表示一个基因在串中的位置称为基因位置(Gene Position),有时也简称基因位。基因位置由串的左向右计算,例如在串 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,则以进化过程中所得到的具有最大适应度个体作

为最优解输出,终止计算。

图1.遗传算法流程图

1.4特点及应用

遗传算法还具有以下几方面的特点:

(1)遗传算法从问题解的串集开始搜索,而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的;容易误入局部最优解。遗传算法从串集开始搜索,覆盖面大,利于全局择优。

(2)遗传算法同时处理群体中的多个个体,即对搜索空间中的多个解进行评估,减少了陷入局部最优解的风险,同时算法本身易于实现并行化。

(3)遗传算法基本上不用搜索空间的知识或其它辅助信息,而仅用适应度函数值来评估个体,在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束,而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。

(4)遗传算法不是采用确定性规则,而是采用概率的变迁规则来指导他的搜索方向。

(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时,适应度大的个体具有较高的生存概率,并获得更适应环境的基因结构。

(6)算法本身也可以采用动态自适应技术,在进化过程中自动调整算法控制参数和编码精度,比如使用模糊自适应法。

由于遗传算法的整体搜索策略和优化搜索方法在计算时不依赖于梯度信息或其它辅助知识,而只需要影响搜索方向的目标函数和相应的适应度函数,所以

遗传算法提供了一种求解复杂系统问题的通用框架,它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于函数优化和组合优化,车间调度等方面。

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

下面用遗传算法求函数f(x)的最大值

f(x)=10*sin(5x)+7*cos(x 2) x ∈[0,10],分辨率为0.01

2.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,()0

f x fitness x f x >=?=?

2.3仿真结果

最佳编码序列为:0 0 0 0 1 0 0 0 0 0 对应x 的取值为: 0.31281 第 8 次迭代达到最大值 求得最大值为 16.96628833

目标函数最优值随迭代次数变化如下图:

图2.函数最大值随迭代次数变化曲线

可以看出,目标函数值随着迭代次数增加到8次即达到稳定状态,算法具有快速性和较强的全局寻优能力。

2.4下面对求解结果的准确性进行检查

在区间[0,10]上以0.01的步长进行搜索得到函数的最优值;

可得:x=0.32时函数取得最大值为

ymax =16.965539275225591

随着x值的变化,对应的y值为:

图3.目标函数随x值的变化曲线

显然,采用遗传算法得到的结果比定步长的结果更好,且运算次数更少,达到了大于0.01的目标。

2.5方法的推广

本方法通过映射关系使遗传算法可以解决函数在浮点数范围内的函数最值问题,扩展了遗传算法的应用范围。

此外,如果把一个个体的编码划分为几节,分别对应不同自变量的编码,其余操作基本不变,则可以把遗传算法推广到多变量目标函数在给定区间上的最值的求取,并在结果精度和求解时间上均有较大提高。

附1、原程序代码

%参数的初始化,种群规模、染色体长度,交叉和变异概率;种群迭代次数;

popsize=10;

chromlength=10;

pc=0.5;

circle=30;

maxindividual=zeros(1,circle);

bestcode=zeros(circle,chromlength);

%对问题进行编码

initpop=round(rand(popsize,chromlength));

pop=initpop;

times=0;

while times

%对问题解码,即将2进制转化为10进制;

decimal=zeros(1,popsize);

for ii=1:popsize

for jj=1:chromlength

decimal(ii)=decimal(ii)+pop(ii,jj)*2.^(chromlength-jj);

end

decimal(ii)=10*decimal(ii)/1023;

end

%计算个体的适应度值;

for i=1:popsize

individual(i)=10*sin(5*decimal(i))+7*cos(decimal(i).^2);

if(individual(i)<0)

individual(i)=0;

end

end

[maxindividual(times+1),maxindex]=max(individual);%每次迭代,种群中适应度的最大值;

bestcode(times+1,:)=pop(maxindex,:);%适应度最高个体对应的编码;

totalindividual=sum(individual);

%进行选择操作;

%转轮盘方法进行选择操作

for i=1:popsize

bdindividual(i)=sum(individual(1:i))/totalindividual;

end

for i=1:popsize

j=1;

rn=rand;

while rn>bdindividual(j)

j=j+1;

end

newpop(i,:)=pop(j,:);

end

%个体间进行交叉操作,pcps(交叉位置);

pop=newpop;

for i=1:2:popsize

rn2=rand;

if(rn2

pcps=round(chromlength*rn2);

if(pcps==0)

pcps=1;

end

newpop(i,pcps:chromlength)=pop(i+1,pcps:chromlength);

newpop(i+1,pcps:chromlength)=pop(i,pcps:chromlength);

end

end

%对种群进行变异操作;

for i=1:popsize

for j=1:chromlength

if(rand

newpop(i,j)=1-newpop(i,j);

end

end

end

pop=newpop;

times=times+1;

end

[maxall,index]=max(maxindividual);

allindex=bestcode(index,:);

value=0;

for jj=1:chromlength

value=value+allindex(jj)*2.^(chromlength-jj);

end

value=10*value/1023;

fprintf('最佳编码序列为:');disp(allindex);disp('\n');

fprintf('对应x的取值为:%8.5f\n',value);

fprintf('第%d 次迭代达到最大值\n',index);

fprintf('求得最大值为%f \n',maxall);

timeserie=zeros(1,times);

for i=1:times

timeserie(i)=max(maxindividual(1,1:i));

end

figure;

plot(1:times,timeserie); figure;

sn = @(x) 10*sin(5*x)+7*cos(x.^2); fplot(sn,[0,10])

% xx=0:0.01:10;

% yy=10*sin(5*xx)+7*cos(xx.^2); % [ymax,xmax]=max(yy)

用遗传算法求解Rosenbrock函数最优解实验报告

姓名学号 实验 成绩 华中师范大学计算机科学系 实验报告书 实验题目:用遗传算法求解Rosenbrock函数的最大值问题课程名称:智能计算 主讲教师:沈显君 辅导教师: 课程编号: 班级:2011级 实验时间:2011.11

用遗传算法求解Rosenbrock函数最大值问题 摘要: 本文利用遗传算法研究了求解Rosenbrock函数的最大值问题.在较多的计算机模拟实验结果中表明,用遗传算法可以有效地解决这一问题.文中分析了一种基于遗传算法对Rosenbrock函数最大值问题的求解,得到了适于解决此问题的合理的遗传操作,从而为有效地解决最速下降法所不能实现的某一类函数代化问题提供了一种新的途径.通过对基于遗传算法对Rosenbrock函数最大值问题的求解,进一步理解遗传算法对解决此类问题的思想。 关键词:遗传算法,Rosenbrock函数,函数优化,最速下降法。 Abstract: This paper deals with the maximum of Rosenbrock s function based ongenetic algorithms. The simulated results show that the problem can be solved effectivelyusing genetic algorithms. The influence of some rnodified genetic algorithms on searchspeed is also examined. Some genetic operations suitable to the optimization technique areobtained, therefore, a novel way of solving a class of optimizations of functions that cannot be realized using the method of steepest descent is proposed.Through dealing with the maximum of Rosenbrock s function based ongenetic algorithms,a better understanding of the genetic algorithm to solve such problems thinking. Keyword:ongenetic algorithms,Rosenbrock function,function optimization,Steepest descent method

MATLAB实验报告-遗传算法解最短路径以及函数最小值问题

硕士生考查课程考试试卷 考试科目:MATLAB教程 考生姓名:考生学号: 学院:专业: 考生成绩: 任课老师(签名) 考试日期:20 年月日午时至时

《MATLAB教程》试题: A、利用MATLAB设计遗传算法程序,寻找下图11个端点的最短路径,其中没有连接的端点表示没有路径。要求设计遗传算法对该问题求解。 a c d e f h i k 1 2 1 6 8 3 1 7 9 4 6 7 2 9 4 2 1 1 B、设计遗传算法求解f(x)极小值,具体表达式如下: 要求必须使用m函数方式设计程序。 C、利用MATLAB编程实现:三名商人各带一个随从乘船渡河,一只小船只能容纳二人,由他们自己划行,随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货,但是如何乘船渡河的大权掌握在商人手中,商人们怎样才能安全渡河? D、结合自己的研究方向选择合适的问题,利用MATLAB进行实验。 以上四题任选一题进行实验,并写出实验报告。

选择题目: A 一、问题分析(10分) 1 2 3 4 5 6 8 9 10 11 1 2 1 6 8 3 1 7 9 4 6 7 2 9 4 2 1 1 如图如示,将节点编号,依次为 1.2.3.4.5.6.7.8.9.10.11,由图论知识,则可写出其带权邻接矩阵为: 0 2 8 1 500 500 500 500 500 500 500 2 0 6 500 1 500 500 500 500 500 500 8 6 0 7 500 1 500 500 500 500 500 1 500 7 0 500 500 9 500 500 500 500 500 1 500 500 0 3 500 2 500 500 500 500 500 1 500 3 0 4 500 6 500 500 500 500 500 9 500 4 0 500 500 1 500 500 500 500 500 2 500 500 0 7 500 9 500 500 500 500 500 6 500 7 0 1 2 500 500 500 500 500 500 1 500 1 0 4 500 500 500 500 500 500 500 9 2 4 0 注:为避免计算时无穷大数吃掉小数,此处为令inf=500。 问题要求求出任意两点间的最短路径,Floyd算法采用的是在两点间尝试插入顶点,比较距离长短的方法。我思考后认为,用遗传算法很难找到一个可以统一表示最短路径的函数,但是可以对每一对点分别计算,然后加入for循环,可将相互之间的所有情况解出。观察本题可发现,所有节点都是可双向行走,则可只计算i到j的路径与距离,然后将矩阵按主对角线翻折即可得到全部数据。二、实验原理与数学模型(20分) 实现原理为遗传算法原理: 按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选,使得适应度高的个体被保留下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。这样周而复始,群体中个体适应度不断提高,直到满足一定的条件。 数学模型如下: 设图由非空点集合和边集合组成,其中 又设的值为,故可表示为一个三元组 则求最短路径的数学模型可以描述为:

遗传算法用于函数优化

遗传算法用于函数优化求解 一、实验目的 本实验要求在掌握遗传算法的基本思想、原理和算法流程的基础上,能够针对指定的单变量优化目标函数,设计相应的遗传算法优化程序,并求得全局最优解。 二、实验要求 针对目标函数 2 1(1),[0,2]y x x =--∈,设计利用遗传算法进行优化求解的程序,绘制迭代过程中最优解的变化情况,并分别改变算法中的编码位数、种群规模、交叉和变异概率,分析这些变量对算法精度及收敛性的影响。 三、实验步骤 1、初始化种群,确定种群规模M=20,编码位数n=5 和编码机制(二进制编码); 初始化种群:E = round(rand(M,n)); 每个编码对应的二进制数值: (1) 2i i i y y -=?∑ i y 为第i 位二进制代码; 二进制数y 转换为十进制数x : max min min *21n x x x y x -= +-; 2、根据给定的目标函数,计算各个种群的适应度值; 3、采用轮盘选择法对种群进行选择复制; 4、设定交叉概率为0.9,进行遗传操作(交叉); 5、设定变异概率0.05,进行遗传操作(变异); 6、产生下一代种群,与终止条件比较,不满足返回到步骤2直到满足条件退出。 算法的流程如图7.1所示。

N Y 结束 输出结果 迭代次数达上限? 开始 初始化种群(编码) 计算适应度函数 交叉、变异 选择、复制 达到系统指标? 图7.1 算法流程图 四、实验结果及分析 我们采用遗传算法来寻求目标函数的最大值。初始化样本个数为20个,编码位数为5位,采用二进制编码,交叉概率为0.9,变异概率为0.05,最大迭代次数为1000次,初始样本随机选择,当父代与子代间适应度变化小于0.001时,达到系统指标。MATLAB 模拟运行输出迭代种群的平均适应度变化、种群的最优解与最差解,绘出图像(见图1),计算运行时间的平均值(见表1),由表可知,平均运行时间约为0.65秒左右,速度较快。由图可知,前期平均适应度是不断上升的,到达一定程度后即平均适应度在0.9以上后,就基本处于波动平衡状态。

遗传算法求解函数最大值

人工智能 遗传算法函数优化

目录 1引言 (3) 1.1 摘要 (3) 1.2 背景 (3) 2 实验过程 (4) 2.1 程序目标 (4) 2.2 实验原理及步骤 (4) 2.3程序 (5) 2.3.1程序理解: (5) 2.3.3调试程序: (5) 2.4 实验总结 (18)

1引言 1.1 摘要 函数优化是遗传算法的经典应用领域,也是对遗传算法进行性能评价的常用算例。本文将用一个详细的例子来说明用遗传算法解一个简单参数优化问题的过程。这里求解的是一个函数的最大值的问题。 1.2 背景 遗传算法采纳自然进化模型。通过保持一个潜在解的群体执行了多方向的搜索并支持这些方向上的信息构成和交换。群体经过一个模拟进化的过程:在每一代,相对“好”的解产生,相对“差”的解死亡。为区别不同解,我们使用了一个目标(评价)函数,它起着一个环境的作用。 选择是用来确定管理费用或交叉个体,以及被选个体将产生多少个代个体。 杂交组合了两个亲代染色体的特征,并通过交换父代相应的片断形成了两个相似的后代。杂交算子的意图是在不同潜在解之间进行信息交换。 变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因。变异算子的意图是向群体引入一些额外的变化性。 运用遗传算法解题必经的五个步骤: 1.对问题潜在解的遗传表达。 2.产生潜在解初始群体的方法。 3.起环境作用的用“适应值”评价解的适应程度的评价函数。 4.改变后代组成的各种遗传算子。 5.遗传算法所使用的各种参数:群体规模、应用遗传算子的概率等。

2 实验过程 2.1 程序目标 在实验过程中,我们应用遗传算法来模拟一个函数优化的问题。程序所要解决的问题是求f(x1,x2)=21.5+x1*sin(4pi*x1)+x2*sin(20pi*x2)的最大值,其中-3.0≤x1≤12.1及4.1≤x2≤5.8。 2.2 实验原理及步骤 1 )首先确立变量x1的定义域长度为15.1;所要求的小数点以后第四位精度意味着区间[-3.0, 12.1]应该至少被分成15.1*10000个等距区间,即染色体的第一部分需要18位;自变量x2域长度为 1.7,精度要求区间[4.1, 5.8]应该至少被分成1.7*10000个等距区间,即染色体的第二部分需要15位。所以染色体总长度为33位。用遗传算法的优化函数f,产生了一个有pop_size = 20个染色体的群体。所有染色体的33位都是随机初始化。对每个染色体进行解码并计算解码后的(x1,x2)的适应函数值,eval(vi) (i=1,..,pop_size) = f(x1,x2)。 2)为选择过程建立一个轮盘。计算群体的总适应值F,并计算每个染色体vi (i=1,..,pop_size)的选择概率pi:pi = eval(vi) / F 和累积概率qi: qi = p1 + .. + pi. 3)转动轮盘20次,每次为新群体选择一单个染色体。生成一个区间[0,1]里的20个数的一个随机序列。如果一个随机数位于qi于q(i+1)之间,则q(i+1)被选择。4)对新群体中的个体应用杂交算子。杂交概率pc = 0.25,所以预计染色体中平均有25%将经历杂交。杂交按照下面的方法进行:对新群体中的每个染色体,产生在区间[0,1]里的随机数r,并从随机序列中选出r<0.25的染色体进行杂交。 5)对被选择的染色体随机进行配对。并从区间[1,32]里产生一个随机整数pos。数字pos表示杂交点的位置。 6)算子变异。在一位一位基础上执行。变异概率pm = 0.01,所以我们预计平均将有1%的位经历变异。整个群体共有m*pop_size = 660位,可以预计平均每代有6.6次变异。因为每一位都有均等的机会被变异,所以对群体中的每一位可以产生区间

4遗传算法与函数优化

第四章遗传算法与函数优化 4.1 研究函数优化的必要性: 首先,对很多实际问题进行数学建模后,可将其抽象为一个数值函数的优化问题。由于问题种类的繁多,影响因素的复杂,这些数学函数会呈现出不同的数学特征。除了在函数是连续、可求导、低阶的简单情况下可解析地求出其最优解外,大部分情况下需要通过数值计算的方法来进行近似优化计算。 其次,如何评价一个遗传算法的性能优劣程度一直是一个比较难的问题。这主要是因为现实问题种类繁多,影响因素复杂,若对各种情况都加以考虑进行试算,其计算工作量势必太大。由于纯数值函数优化问题不包含有某一具体应用领域中的专门知识,它们便于不同应用领域中的研究人员能够进行相互理解和相互交流,并且能够较好地反映算法本身所具有的本质特征和实际应用能力。所以人们专门设计了一些具有复杂数学特征的纯数学函数,通过遗传算法对这些函数的优化计算情况来测试各种遗传算法的性能。 4.2 评价遗传算法性能的常用测试函数 在设计用于评价遗传算法性能的测试函数时,必须考虑实际应用问题的数学模型中所可能呈现出的各种数学特性,以及可能遇到的各种情况和影响因素。这里所说的数学特性主要包括: ●连续函数或离散函数; ●凹函数或凸函数; ●二次函数或非二次函数; ●低维函数或高维函数; ●确定性函数或随机性函数; ●单峰值函数或多峰值函数,等等。 下面是一些在评价遗传算法性能时经常用到的测试函数: (1)De Jong函数F1: 这是一个简单的平方和函数,只有一个极小点f1(0, 0, 0)=0。

(2)De Jong 函数F2: 这是一个二维函数,它具有一个全局极小点f 2(1,1) = 0。该函数虽然是单峰值的函数,但它却是病态的,难以进行全局极小化。 (3)De Jong 函数F3: 这是一个不连续函数,对于]0.5,12.5[--∈i x 区域内的每一个点,它都取全局极小值 30),,,,(543213-=x x x x x f 。

二次函数在闭区间上的最值 (经典)

二次函数在闭区间上的最值 一、 知识要点: 一元二次函数的区间最值问题,核心是函数对称轴与给定区间的相对位置关系的讨论。一般分为:对称轴在区间的左边,中间,右边三种情况. 设f x ax bx c a ()()=++≠2 0,求f x ()在x m n ∈[],上的最大值与最小值。 分析:将f x ()配方,得顶点为- -?? ???b a ac b a 2442 ,、对称轴为x b a =-2 当a >0时,它的图象是开口向上的抛物线,数形结合可得在[m ,n]上f x ()的最值: (1)当[] -∈b a m n 2,时,f x ()的最小值是 f b a ac b a f x -?? ???=-2442 ,()的最大值是f m f n ()()、中的较大者。 (2)当[] - ?b a m n 2,时 若-< b a m 2,由f x ()在[] m n ,上是增函数则f x ()的最小值是f m (),最大值是f n () 若n b a <-2,由f x ()在[] m n ,上是减函数则f x ()的最大值是f m (),最小值是f n () 当a <0时,可类比得结论。 二、例题分析归类: (一)、正向型 是指已知二次函数和定义域区间,求其最值。对称轴与定义域区间的相互位置关系的讨论往往成为解决这类问题的关键。此类问题包括以下四种情形:(1)轴定,区间定;(2)轴定,区间变;(3)轴变,区间定;(4)轴变,区间变。 1. 轴定区间定 二次函数是给定的,给出的定义域区间也是固定的,我们称这种情况是“定二次函数在定区间上的最值”。 例1. 函数y x x =-+-2 42在区间[0,3]上的最大值是_________,最小值是_______。 练习. 已知232 x x ≤,求函数f x x x ()=++2 1的最值。 2、轴定区间变 二次函数是确定的,但它的定义域区间是随参数而变化的,我们称这种情况是“定函数在动区间上的 最值”。 例2. 如果函数f x x ()()=-+112 定义在区间[] t t ,+1上,求f x ()的最值。 例3. 已知2 ()43f x x x =--+,当[1]()x t t t ∈+∈R ,时,求()f x 的最值. 对二次函数的区间最值结合函数图象总结如下: 当a >0时??? ???? +<-+≥-=) )((212)())((2 12)()(21max 如图如图,,n m a b n f n m a b m f x f ?? ? ? ? ? ??? <-≤-≤->-=)(2)()(2)2()(2)()(543min 如图如图如图,,,m a b m f n a b m a b f n a b n f x f

遗 传 算 法 详 解 ( 含 M A T L A B 代 码 )

GATBX遗传算法工具箱函数及实例讲解 基本原理: 遗传算法是一种典型的启发式算法,属于非数值算法范畴。它是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。它是采用简单的编码技术来表示各种复杂的结构,并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法的操作对象是一群二进制串(称为染色体、个体),即种群,每一个染色体都对应问题的一个解。从初始种群出发,采用基于适应度函数的选择策略在当前种群中选择个体,使用杂交和变异来产生下一代种群。如此模仿生命的进化进行不断演化,直到满足期望的终止条件。 运算流程: Step 1:对遗传算法的运行参数进行赋值。参数包括种群规模、变量个数、交叉概率、变异概 率以及遗传运算的终止进化代数。 Step 2:建立区域描述器。根据轨道交通与常规公交运营协调模型的求解变量的约束条件,设置变量的取值范围。 Step 3:在Step 2的变量取值范围内,随机产生初始群体,代入适应度函数计算其适应度值。 Step 4:执行比例选择算子进行选择操作。 Step 5:按交叉概率对交叉算子执行交叉操作。

Step 6:按变异概率执行离散变异操作。 Step 7:计算Step 6得到局部最优解中每个个体的适应值,并执行最优个体保存策略。 Step 8:判断是否满足遗传运算的终止进化代数,不满足则返回Step 4,满足则输出运算结果。 运用遗传算法工具箱: 运用基于Matlab的遗传算法工具箱非常方便,遗传算法工具箱里包括了我们需要的各种函数库。目前,基于Matlab的遗传算法工具箱也很多,比较流行的有英国设菲尔德大学开发的遗传算法工具箱GATBX、GAOT以及Math Works公司推出的GADS。实际上,GADS就是大家所看到的Matlab中自带的工具箱。我在网上看到有问为什么遗传算法函数不能调用的问题,其实,主要就是因为用的工具箱不同。因为,有些人用的是GATBX带有的函数,但MATLAB自带的遗传算法工具箱是GADS,GADS当然没有GATBX里的函数,因此运行程序时会报错,当你用MATLAB来编写遗传算法代码时,要根据你所安装的工具箱来编写代码。 以GATBX为例,运用GATBX时,要将GATBX解压到Matlab下的toolbox文件夹里,同时,set path将GATBX文件夹加入到路径当中。 这块内容主要包括两方面工作:1、将模型用程序写出来(.M文件),即目标函数,若目标函数非负,即可直接将目标函数作为适应度函数。2、设置遗传算法的运行参数。包括:种群规模、变量个数、区域描述器、交叉概率、变异概率以及遗传运算的终止进化代数等等。

二次函数在给定区间上的最值问题

二次函数在给定区间上的最值问题 【学前思考】 二次函数在闭区间上取得最值时的X ,只能是其图像的顶点的横坐标或给定区间的端点?因此,影响二次函数在闭区间上的最值主要有三个因素:抛物线的开口方向、对称轴以及给定区间的位置.在这三大因素中,最容易确定的是抛物线的开口方向(与二次项系数的正负有关),而关于对称轴与给定区间的位置关系的讨论是解决二次函数在给定区间上的最值问题的关键.本节,我 们将以若干实例说明解决此类问题的具体方法. 【知识要点&例题精讲】 二次函数在给定区间上的最值问题,常见的有以下三种类型,分别是: CaSe l、给定区间确定,对称轴位置也确定 说明:此种类型是较为简单的一种,只要找到二次函数的对称轴,画出其函数 图像,再将给定区间标出,那么二次函数的最值一目了然. 解法:若二次函数的给定区间是确定的,其对称轴的位置也确定,则要求二次函数在给定区间上的最值,只需先考察其对称轴的横坐标是否在给定区间内 (i) 当其对称轴的横坐标在给定区间内时,二次函数在给定区间上不具有单调性,此时其一个最值在顶点处取得,另一个最值在离对称轴的横坐标较远的端点处取得;(ii )当其对称轴的横坐标不在给定区间内时,二次函数在给定区间上具有单调性,此时可利用二次函数的单调性确定其最值. 例1、二次函数y = χ2-2χ+3在闭区间[-1,2】上的最大值是_________ . 例2、函数f(X)= -X2 +4x-2在区间【0,3】上的最大值是_________ 最小值是

例3、已知2χ2≤3x,则函数f(χ)=χ2+χ+1的最大值是 ____________ ,最小值是 CaSe n、给定区间确定,对称轴位置变化 说明:此种类型是非常重要的,是考试必考点,主要是讨论二次函数的对称轴与给定区间的位置关系,一般需要分对称轴在给定区间的左侧、内部以及右侧三种情况进行分类讨论,然后根据不同情况求出相应的最值. 解法:若二次函数的给定区间是确定的,而其对称轴的位置是变化的,则要求 二次函数y=aχ2?bx ?c ( a =O)在给定区间[p,q 1上的最值,需对其对称轴与 给定区间的位置关系进行分类讨论.这里我们以a 0的情形进行分析: (i)若一A P ,即对称轴在给定区间∣p,q 1的左侧,贝U函数f(χ)在给定区间 2a l-P,q ]上单调递增,此时[f (X)]max = f(q),[f (X)]min = f ( P); (ii) 若^-―

遗传算法求解函数极值C语言代码

#include "stdio.h" #include "stdlib.h" #include "conio.h" #include "math.h" #include "time.h" #define num_C 12 //个体的个数,前6位表示x1,后6位表示x2 #define N 100 //群体规模为100 #define pc 0.9 //交叉概率为0.9 #define pm 0.1 //变异概率为10% #define ps 0.6 //进行选择时保留的比例 #define genmax 2000 //最大代数200 int RandomInteger(int low,int high); void Initial_gen(struct unit group[N]); void Sort(struct unit group[N]); void Copy_unit(struct unit *p1,struct unit *p2); void Cross(struct unit *p3,struct unit *p4); void Varation(struct unit group[N],int i); void Evolution(struct unit group[N]); float Calculate_cost(struct unit *p); void Print_optimum(struct unit group[N],int k); /* 定义个体信息*/ typedef struct unit { int path[num_C]; //每个个体的信息 double cost; //个体代价值 }; struct unit group[N]; //种群变量group int num_gen=0; //记录当前达到第几代 int main() { int i,j; srand((int)time(NULL)); //初始化随机数发生器 Initial_gen(group); //初始化种群 Evolution(group); //进化:选择、交叉、变异 getch(); return 0; } /* 初始化种群*/ void Initial_gen(struct unit group[N]) { int i,j; struct unit *p; for(i=0;i<=N-1;i++) //初始化种群里的100个个体 {

遗传算法求复杂函数极值问题【精品毕业设计】(完整版)

遗传算法求复杂函数极值问题 中文摘要: 本文首先介绍遗传算法的历史背景,基本思想,对遗传算法的常见的编码解码方法进行了深入的阐述,并对算子选择方法进行深入分析和对比,在此基础上把遗传算法应用于求解复杂函数的极值计算。最后在MATLAB语言环境下编写程序,对求解函数的最大值进行了仿真,并对调试的结果进行了分析,得出了部分结论。 关键词:遗传算法最优解算子选择复杂函数 作者:xx xx 指导老师:xxxx xx

Using Genetic Algorithm to Solve Extreme Problem of Complex Function Abstract Firstly,the historical background and basic idea of genetic algorithm are introduced in this paper. The common coding and decoding method of genetic algorithm are discussed too. Secondly, the selection method of genetic operator is analyzed and compared deeply, based on which genetic algorithm is used to solve extreme problem of complex function. Finally, with MA TLAB software, the program is compiled and the maximum is sought out. At the end of the paper, the debugging result is analyzed and the conclusion is given. Keywords: Genetic Algorithm Optimal Solution Operator Selection Complex Function Written by : xx xx Supervised by: xxxx xx

(实例)matlab遗传算法工具箱函数及实例讲解

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,xOverO ps,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(x1,x2)=100*(x1^2-x2)^2+(1-x1)^2; 的最大值(MATLAB) %Generic Algorithm for function f(x1,x2) optimum (最大值) clear all; close all; %Parameters Size=80; G=100; CodeL=10; 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 m=E(s,:); y1=0;y2=0; %Uncoding m1=m(1:1:CodeL); for i=1:1:CodeL y1=y1+m1(i)*2^(i-1); end x1=(umax-umin)*y1/1023+umin; m2=m(CodeL+1:1:2*CodeL); for i=1:1:CodeL y2=y2+m2(i)*2^(i-1); end x2=(umax-umin)*y2/1023+umin; F(s)=100*(x1^2-x2)^2+(1-x1)^2; end Ji=1./(F+1);

%****** Step 1 : Evaluate BestJ ****** BestJ(k)=min(Ji); fi=F; %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) bfi(k)=Bestfi; %****** 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.60; n=ceil(20*rand); for i=1:2:(Size-1) temp=rand; if pc>temp %Crossover Condition 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

遗传算法代码

%求下列函数的最大值% %f(x)=10*sin(5x)+7*cos(4x)x∈[0,10]% %将x的值用一个10位的二值形式表示为二值问题,一个10位的二值数提供的分辨率是每为(10-0)/(2^10-1)≈0.01。% %将变量域[0,10]离散化为二值域[0,1023],x=0+10*b/1023,其中b是[0,1023]中的一个二值数。 %2.1初始化(编码) %initpop.m函数的功能是实现群体的初始化,popsize表示群体的大小,chromlength表示染色体的长度(二值数的长度), %长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name:initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength));%rand随机产生每个单元为{0,1}行数为popsize,列数为chromlength的矩阵, %roud对矩阵的每个单元进行圆整。这样产生的初始种群。 %2.2计算目标函数值 %2.2.1将二进制数转化为十进制数(1) %遗传算法子程序 %Name:decodebinary.m %产生[2^n2^(n-1)...1]的行向量,然后求和,将二进制转化为十进制function pop2=decodebinary(pop) [px,py]=size(pop);%求pop行和列数 for i=1:py pop1(:,i)=2.^(py-i).*pop(:,i); end pop2=sum(pop1,2);%求pop1的每行之和 %2.2.2将二进制编码转化为十进制数(2) %decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制,参数spoint表示待解码的二进制串的起始位置 %(对于多个变量而言,如有两个变量,采用20为表示,每个变量10为,则第一个变量从1开始,另一个变量从11开始。本例为1), %参数1ength表示所截取的长度(本例为10)。 %遗传算法子程序 %Name:decodechrom.m

第五章-遗传算法工具箱函数

第五章遗传算法工具箱函数 本章介绍英国设菲尔德大学开发的遗传算法工具箱函数。 由于MATLAB高级语言的通用性,对问题用M文件编码,与此配对的是MA TLAB先进的数据分析、可视化工具、特殊目的的应用领域工具箱和展现给使用者具有研究遗传算法可能性的一致环境。MATLAB遗传算法工具箱为遗传算法从业者和第一次实验遗传算法的人提供了广泛多样的有用函数。 遗传算法工具箱使用MA TLAB矩阵函数为实现广泛领域的遗传算法建立一套通用工具,这个遗传算法工具是用M文件写成的,是命令行形式的函数,能完成遗传算法大部分重要功能的程序的集合。用户可通过这些命令行函数,根据实际分析的需要,编写出功能强大的MATLAB程序。 5.1 工具箱结构 本节给出GA工具箱的主要程序。表5.1为遗传算法工具箱中的各种函数分类表。 表5.1 遗传算法工具箱中函数分类表

5.1.1 种群表示和初始化 种群表示和初始化函数有:crtbase,crtbp,crtrp。 GA工具箱支持二进制、整数和浮点数的基因表示。二进制和整数种群可以使用工具箱中的crtbp建立二进制种群。crtbase是附加的功能,它提供向量描述整数表示。种群的实值可用crtrp进行初始化。在二进制代码和实值之间的变换可使用函数bs2rv,它支持格雷码和对数编码。 5.1.2 适应度计算 适应度函数有:ranking,scaling。 适应度函数用于转换目标函数值,给每一个个体一个非负的价值数。这个工具箱支持Goldberg的偏移法(offsetting)和比率法以及贝克的线性评估算法。另外,ranking函数支持非线性评估。 5.1.3 选择函数 选择函数有:reins,rws,select,sus。 这些函数根据个体的适应度大小在已知种群中选择一定数量的个体,对它的索引返回一个列向量。现在最合适的是轮盘赌选择(即rws函数)和随机遍历抽样(即sus函数)。高级入口函数select为选择程序,特别为多种群的使用提供了一个方便的接口界面。在这种情况下,代沟是必须的,这就是整个种群在每一代中没有被完全复制,reins能使用均匀的随机数或基于适应度的重新插入。 5.1.4 交叉算子 交叉算子函数有:recdis,recint,reclin,recmut,recombin,xovdp,xovdprs,xovmp,xovsh,xovshrs,xovsp,xovsprs。 交叉是通过给定的概率重组一对个体产生后代。单点交叉、两点交叉和洗牌交叉是由xovsp、xovdp、xovsh函数分别完成的。缩小代理交叉函数分别是:xovdprs、xovshrs和xovsprs。通用的多点交叉函数是xovmp,它提供均匀交换的支持。为支持染色体实值表示,离散的、中间的和线性重组分别由函数recdis、recint、reclin完成。函数recmut提供具有突变特征的线性重组。函数recombin是一高级入口函数,对所有交叉操作提供多子群支持入口。 5.1.5 变异算子 变异算子函数有:mut,mutate,mutbga。

二次函数的区间最值问题知识讲解

二次函数最值问题 二次函数y =ax 2 bx C a = 0)是初中函数的主要内容,也是高中学习的重要基 础?在初中阶段大家已经知道:二次函数在自变量 x 取任意实数时的最值情况(当a ■0时, 本节我们将在这个基础上继续学习当自变量 x 在某个范围内取值时,函数的最值问 题?在高中阶段,求二次函数的最值问题只需要记住“三点一轴”,即题目给出的 x 的取值范 围区间的两个端点, 二次函数的顶点,以及二次函数的对称轴, 注意结合图像学会用数形结 合解题。高中阶段的二次函数最值问题可以分为一下三个方面: 1.定轴定区间。2.动轴定区 间。3.定轴动区间。下面我们来看例题。 【例1】当-2空x 空2时,求函数y =x 2 -2x-3的最大值和最小值. 分析:这个问题十分简单,属于定轴定区间这一类题目, 只需要画出函数图像即可以解 决。 1 5 【例2】当t 兰x 兰t +1时,求函数y = -x 2 -X -一的最小值(其中t 为常数)? 2 2 函数在x 二 b 2a 处取得最小值 4ac -b 2 4a 无最大值;当时 a . 0,函数在x —处取得 2a 最大值 4ac -b 2 4a 无最小值.

分析:这类问题属于定轴动区间的问题,由于 X 所给的范围随着t 的变化而变化,所以 需要比较对称轴与其范围的相对位置. 1 5 解:函数y =-x2—x _-的对称轴是x=1。画出其草图。 2 2 (1) 灯=}12 j_| = —3 ; 1 i 5 1 i A min =尹+1) -(t +1)石=|t -3. 1 2 -t 2 -3,t<0 2 综上所述:y min = -3,0_t_1 】t 2 —t —5,t A 1 I 2 2 【例3】设二次函数f x =-x 2 ? 2ax ? 1-a 在区间0,1 ]上的最大值为2,求实数a 的 值。分析:这类问题属于动轴定区间的问题,由于函数的对称轴随 a 的变化而变化,所 ⑵当对称轴在所给范围左侧.即 1 2 5 t 1时当X"时,畑; (4)当对称轴在所给范围之间?即 t _1 _t 1= 0_t _1 时;当 x = 1 时, ⑹当对称轴在所给范围右侧?即 t 1 :::1= t :: 0时,当 x =t ? 1 时,

遗传算法求函数极大值(matlab实现)

遗传算法求函数最大值(matlab实现) 一、题目: 寻找f(x)=x2,,当x在0~31区间的最大值。 二、源程序: %遗传算法求解函数最大值 %本程序用到了英国谢菲尔德大学(Sheffield)开发的工具箱GATBX,该工具箱比matlab自带的GATOOL使用更加灵活,但在编写程序方面稍微复杂一些 Close all; Clear all; figure(1); fplot('variable*variable',[0,31]); %画出函数曲线 %以下定义遗传算法参数 GTSM=40; %定义个体数目 ZDYCDS=20; %定义最大遗传代数 EJZWS=5; %定义变量的二进制位数 DG=0.9; %定义代沟 trace=zeros(2, ZDYCDS); %最优结果的初始值

FieldD=[5;-1;2;1;0;1;1]; %定义区域描述器的各个参数%以下为遗传算法基本操作部分,包括创建初始种群、复制、交叉和变异 Chrom=crtbp(GTSM, EJZWS); %创建初始种群,即生成给定 规模的二进制种群和结构gen=0; %定义代数计数器初始值variable=bs2rv(Chrom, FieldD); %对生成的初始种群进行十进制转换 ObjV=variable*variable; %计算目标函数值f(x)=x2 while gen

相关主题
相关文档 最新文档