%Rosenbrock函数的极大值0-1编码的GA算法
%初始参数
Size=80;
G=100;
CodeL=10;
umax=2.048;
umin=-2.048;
E=round(rand(Size,2*CodeL)); %生成初始种群
%主程序
for k=1:1:G
time(k)=k;
for s=1:1:Size
m=E(s,:);
y1=0;y2=0;
%解码方法
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
%****** Step 1 : 选择最优个体 ******
BestJ(k)=max(F); %记录每一代中最大个体的函数值
fi=F; %适应度函数
[Oderfi,Indexfi]=sort(fi); %按照适应度大小排序
Bestfi=Oderfi(Size); %Oderfi中最后一个即是最大的适应度
BestS=E(Indexfi(Size),:); %记录每一代中最优个体的0-1编码
bfi(k)=Bestfi; %记录每一代中最优个体的适应度
%****** Step 2 : 选择与复制操作******
fi_sum=sum(fi);
fi_Size=(Oderfi/fi_sum)*Size; %计算个体相对适应度
fi_S=floor(fi_Size); %对80个个体依据相对适应度进行划分等级
kk=1;
for i=1:1:Size
for j=1:1:fi_S(i) %选择等级高的个体，等级越高被选次数越多
TempE(kk,:)=E(Indexfi(i),:);
kk=kk+1; %选择进入下一代个体的个数，显然不够80个个体end
end
%************ Step 3 : 交叉操作 ************
pc=0.60;
n=ceil(20*rand);
for i=1:2:(Size-1)
temp=rand;
if pc>temp %交叉条件
TempE(i,n:end)=E(i+1,n:end);
TempE(i+1,n:end)=E(i,n:end);
end
end
TempE(Size,:)=BestS; %最优个体保留
E=TempE; %种群替换
%************ Step 4: 变异操作 **************
%pm=0.001;
%pm=0.001-[1:1:Size]*(0.001)/Size; %自适应变异概率
%pm=0.0; %没有变异
pm=0.1; %较大的变异概率
for i=1:1:Size
for j=1:1:2*CodeL
temp=rand;
if pm>temp %变异条件
if TempE(i,j)==0
TempE(i,j)=1;
else
TempE(i,j)=0;
end
end
end
end
TempE(Size,:)=BestS; %保留当代最优个体
E=TempE; %种群替换
end
%*************** 结果输出 *****************
Max_Value=Bestfi
BestS
x1
x2
figure(1);
plot(time,BestJ);
xlabel('Times');ylabel('Best J');
figure(2);
plot(time,bfi);
xlabel('times');ylabel('Best F');
遗传算法编码及算子简介 遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施加结构重组处理，从而不断地搜索出群体中个体间的结构相似性，形成并优化积木块以逐渐逼近最优解。由此可见，必须把群体中的个体转化成按一定基因结构组成的染色体或个体，即编码。编码原则包括两条： 1.有积极积木块编码规则，即所定编码应当易于生成所求问题相关的短距和低阶的积木块。 2.最小字符集编码规则，即所定编码应用最小字符集以使问题得到自然的表示或描述。 规则一是基于模式定理和积木块假设；规则二提供了一种更为实用的编码规则。评估编码策略常采用的规范有： 1.完备性：问题空间中的所有点都能作为GA空间的点表现。 2.健全性：GA空间中的染色体能对应所有问题空间中的候选解。 3.非冗余性：染色体和候选解一一对应。 这些评估规范是独立于问题领域的普遍准则。对某个具体的应用领域而言，应该客观化地比较和评估该问题领域中所用的编码方法。应用遗传算法进行优化，首先将问题描述成串的形式，以模拟染色体。选择何种编码方式对算法的运行有很大的影响。现在，流行的观点认为二进制编码能在相同的范围内表示最多的模式，能充分地体现所谓的隐含并行性。但是，二进制编码方式的精度依赖于染色体的基因位数及设计变量的范围。因而对于高精度、多变量问题，n值需很大，降低遗传算法的收敛速度。另外，二进制编码不直接反映真实的设计空间。其它的编码方式还有：格雷码编码、浮点编码、树结构编码、参数动态编码和多维编码等。 遗传算法主要有选择、交叉和突变算子 选择算子 遗传算法使用选择算子或称复制算子来对种群中的个体进行优胜劣汰操作：选择算子使适应性高的个体在后代中生存的概率较大，而适应度低的个体生存的概率很小甚至被淘汰。遗传算法中的选择操作就是来确定如何从父代群体中按某种方法选取那些个体以传到下一代群体的一种遗传算法。选择操作是建立在群体中个体的适应度评价基础上的。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。在遗传算法中级很重要的作用。选择操作有多种方法，最常用的是轮盘赌法。在具体使用中，应根据问题求解的特点采用合适的方法或者混合使用。下面简单介绍各种选择算法： (1) 比例选择算法 基本思想是：各个个体被选中的概率与其适应度大小成正比，即适应度越高的个体被选中的概率也越大，反之则小。 (2) 最优选择算法 在遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而不断地产出新的个体。虽然随着群体的进化过程会产出越来越多的优良个体，但由于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适应度最好的个体。由于随机操作的原因，这种选择方法的误差比较大，有时甚至连适应度较高的个体也选择不上，由此会降低群体的平均适应度，对算法的运行效率、收敛性都有不利的影响。一般说来，适应度最好的个体要尽可能地保留到下一代群体中。为此可以使用最优保留策略进化模型，即当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等操
遗传算法用于函数优化求解 一、实验目的 本实验要求在掌握遗传算法的基本思想、原理和算法流程的基础上，能够针对指定的单变量优化目标函数，设计相应的遗传算法优化程序，并求得全局最优解。 二、实验要求 针对目标函数 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以上后，就基本处于波动平衡状态。
姓名学号 实验 成绩 华中师范大学计算机科学系 实验报告书 实验题目：用遗传算法求解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
第四章遗传算法与函数优化 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 。
人工智能 遗传算法函数优化
目录 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次变异。因为每一位都有均等的机会被变异，所以对群体中的每一位可以产生区间
实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）； 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题； 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别 代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。微带电极的结构参数如图所示，W 、t 分别是上电极的宽度和厚度，D 是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率1GHz ），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）： 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率，为电阻率。可见电极的结构参数影响着电极损
耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个：W 、D 、t ，它们组成决策向量[W, D ,t ] T ，待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述： ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2) 其中()T n x x x X ,...,,21=是决策向量，x 1，…，x n 为n 个设计变量。这是一个单目标的数学规划问题：在一组针对决策变量的约束条件()0,1,...,j g X j p ≤=下，使目标函数最小化（有时 也可能是最大化，此时在目标函数()X f 前添个负号即可）。满足约束条件的解X 称为可行解，所有满足条件的X 组成问题的可行解空间。 2. 遗传算法基本原理和基本操作 遗传算法(Genetic Algorithm, GA)是一种非常实用、高效、鲁棒性强的优化技术，广 泛应用于工程技术的各个领域(如函数优化、机器学习、图像处理、生产调度等)。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化算法。按照达尔文的进化论，生物在进化过程中“物竞天择”，对自然环境适应度高的物种被保留下来，适应度差的物种而被淘汰。物种通过遗传将这些好的性状复制给下一代，同时也通过种间的交配(交叉)和变异不断产生新的物种以适应环境的变化。从总体水平上看，生物在进化过程中子代总要比其父代优良，因此生物的进化过程其实就是一个不断产生优良物种的过程，这和优化设计问题具有惊人的相似性，从而使得生物的遗传和进化能够被用于实际的优化设计问题。 按照生物学知识，遗传信息基因(Gene)的载体是染色体(Chromosome)，染色体中 一定数量的基因按照一定的规律排列（即编码），遗传基因在染色体中的排列位置称为基因
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、设置遗传算法的运行参数。包括：种群规模、变量个数、区域描述器、交叉概率、变异概率以及遗传运算的终止进化代数等等。
例说求函数的最大值和最小值的方法 例1.设x 是正实数，求函数x x x y 32+ +=的最小值。 解：先估计y 的下界。 55)1(3)1(5)21(3)12(222≥+- +-=+-+ ++-=x x x x x x x y 又当x =1时，y =5，所以y 的最小值为5。 说明 本题是利用“配方法”先求出y 的下界，然后再“举例”说明这个下界是可以限到的。“举例”是必不可少的，否则就不一定对了。例如，本题我们也可以这样估计： 77)1(3)1(7)21(3)12(222-≥-+ +-=-++ ++-=x x x x x x x y 但y 是取不到-7的。即-7不能作为y 的最小值。 例2. 求函数1 223222++--=x x x x y 的最大值和最小值。 解 去分母、整理得：(2y -1)x 2+2(y +1)x +(y +3)=0. 当2 1≠y 时，这是一个关于x 的二次方程，因为x 、y 均为实数，所以 ?=[2(y +1)]2-4(2y -1)(y +3)≥0, y 2+3y --4≤0, 所以 -4≤y ≤1 又当3 1-=x 时，y =-4;x =-2时，y =1.所以y min =-4，y max =1.
说明 本题求是最值的方法叫做判别式法。 例3.求函数152++-=x x y ，x ∈[0,1]的最大值 解：设]2,1[1∈=+t t x ，则x =t 2-1 y = -2(t 2-1)+5t = -2t 2+5t +1 原函数当t =169,45=x 即时取最大值8 33 例4求函数22 3,5212≤≤+--=x x x x y 的最小值和最大值 解：令x -1=t ( 121≤≤t ) 则t t t t y 4142+=+= y min =5 1,172max =y 例5.已知实数x ,y 满足1≤x 2+y 2≤4,求f (x )=x 2+xy +y 2的最小值和最大值 解：∵)(2 122y x xy +≤ ∴6)(23 ),(2222≤+≤++=y x xy y x y x f 又当2==y x 时f (x ,y )=6，故f (x ,y )max =6 又因为)(2122y x xy +- ≥
遗传算法编码 读万卷书不如行万里路，今天下决心写一个SGA(Simple Genetic Alogrithms)程序，是求解非约束优化问题。 max f(x1,x2)=21.5+x1*sin(4*PI*x1)+x2*sin(20*PI*x2) -3.0<=x1<=12.1 4.1<=x2<= 5.8 这可是遗传算法中最容易的，可是结果却令人失望，在整个求解过程中都收敛在局部最优，只有通过加大变异率才能求得全局最优，但问题可想而知：全局最优解不稳定，就好像是昙花一现。 查了一下资料才发现是编码设计的问题。我用的是二进制编码。 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。编码方法影响到交叉算子、变异算子等遗传算子的运算方法，大很大程度上决定了遗传进化的效率。 迄今为止人们已经提出了许多种不同的编码方法。总的来说，这些编码方法可以分为三大类：二进制编码法、浮点编码法、符号编码法。下面我们从具体实现角度出发介绍其中的几种主要编码方法。 1.二进制编码方法： 它由二进制符号0和1所组成的二值符号集。它有以下一些优点： 1)编码、解码操作简单易行 2)交叉、变异等遗传操作便于实现 3)符合最小字符集编码原则 4)利用模式定理对算法进行理论分析。 二进制编码的缺点是：对于一些连续函数的优化问题，由于其随机性使得其局部搜索能力较差，如对于一些高精度的问题（如上题），当解迫近于最优解后，由于其变异后表现型变化很大，不连续，所以会远离最优解，达不到稳定。而格雷码能有效地防止这类现象 2.格雷码方法： 格雷码方法是这样的一种编码方法，其连续两个整数所对应的编码值之间仅仅只有一个码位是不同的。如下表 十进制二进制格雷码 000000000 100010001 200100011 300110010 401000110 501010111 601100101 701110100 810001100 910011101 1010101111 1110111110 1211001010 1311011011
遗传算法求复杂函数极值问题 中文摘要： 本文首先介绍遗传算法的历史背景，基本思想，对遗传算法的常见的编码解码方法进行了深入的阐述，并对算子选择方法进行深入分析和对比，在此基础上把遗传算法应用于求解复杂函数的极值计算。最后在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
函数的最大值和最小值教案 1.本节教材的地位与作用本节主要研究闭区间上的连续函数最大值和最小值的求法和实际应用,分两课时,这里是第一课时,它是在学生已经会求某些函数的最值,并且已 经掌握了性质:“如果f(x)是闭区间[a,b]上的连续函数,那么 f(x)在闭区间[a,b]上有最大值和最小值” ,以及会求可导函数的极值之后进行学习的,学好这一节,学生将会求更多的函数的 最值,运用本节知识可以解决科技、经济、社会中的一些如何使成本最低、产量最高、效益最大等实际问题.这节课集中体现了数形结合、理论联系实际等重要的数学思想方法,学好本节,对于进一步完善学生的知识结构,培养学生用数学的意识都具有极为重要的意义. 2.教学重点会求闭区间上连续开区间上可导的函数的最值. 3.教学难点高三年级学生虽然已经具有一定的知识基础,但由于对求函数极值还不熟练,特别是对优 化解题过程依据的理解会有较大的困难,所以这节课的难点是理解确定函数最值的方法. 4.教学关键本节课突破难点的关键是:理解方程f′(x)=0的解,包含有指定区间内全部可能的极值点. 【教学目标】根据本节教材在高中数学知识体系中的地位和作用,结合学生已有的认知水平,制定本节如下的 教学目标: 1.知识和技能目标 (1)理解函数的最值与极 值的区别和联系. (2)进一步明确闭区间[a,b]上的连续函数
f(x),在[a,b]上必有最大、最小值. (3)掌握用导数法求上述 函数的最大值与最小值的方法和步骤. 2.过程和方法目标(1)了解开区间内的连续函数或闭区间上的不连续函数不一定有 最大、最小值. (2)理解闭区间上的连续函数最值存在的可能 位置:极值点处或区间端点处. (3)会求闭区间上连续,开区 间内可导的函数的最大、最小值. 3.情感和价值目标 (1) 认识事物之间的的区别和联系. (2)培养学生观察事物的能力,能够自己发现问题,分析问题并最终解决问题. (3)提高 学生的数学能力,培养学生的创新精神、实践能力和理性精神. 【教法选择】根据皮亚杰的建构主义认识论,知识是个体在 与环境相互作用的过程中逐渐建构的结果,而认识则是起源于主 客体之间的相互作用. 本节课在帮助学生回顾肯定了闭区间 上的连续函数一定存在最大值和最小值之后,引导学生通过观察 闭区间内的连续函数的几个图象,自己归纳、总结出函数最大值、最小值存在的可能位置,进而探索出函数最大值、最小值求解的 方法与步骤,并优化解题过程,让学生主动地获得知识,老师只是 进行适当的引导,而不进行全部的灌输.为突出重点,突破难点, 这节课主要选择以合作探究式教学法组织教学. 【学法指导】对于求函数的最值,高三学生已经具备了良好的知识基础,剩下 的问题就是有没有一种更一般的方法,能运用于更多更复杂函数 的求最值问题?教学设计中注意激发起学生强烈的求知欲望,使 得他们能积极主动地观察、分析、归纳,以形成认识,参与到课堂
基于遗传算法的染色体编码的分析 第19卷第1期 2010年1月 重庆电子工程职业学院V o1.19NO.1 lan.2010oumalofChon￡咽in￡CoUe~eofElectronicEnl~ine 基于遗传算法的染色体编码的分析 吴焱岷 (重庆大学计算机学院,重庆400044;重庆电子工程职业学院,重庆401331) 摘要:遗传算法为解决复杂问题,特别是NP类问题提供了一种全新的思路,其编码方式也将在一定程 度上决定算法效率的高低和程序设计的复杂程度.需要针对想要解决问题类型的不同而采取不同的编码方式. 关键词:遗传算法;编码;值类型;事务类型 中图分类号:TP39文献标识码:A文章编号:1674—5787(2010)01一【)【】86一O2 遗传算法的概念最早是由BagleyJ.D在1967年提出 的.而开始遗传算法的理论和方法的系统性研究在1975 年开始.这一开创性工作是由Michigan大学的J.H. Holland所实行.遗传算法简称GA(GeneticAlgorithm),在 本质上是一种不依赖具体问题的直接搜索方法.其基本 思想是基于Darwin进化论和Mendel的遗传学说 Darwin进化论最重要的是适者生存原理它认为每 一 物种在发展中越来越适应环境.物种每个个体的基本 特征由后代所继承.但后代又会产生一些异于父代的新 变化. Mendel遗传学说最重要的是基因遗传原理它认为
遗传以密码方式存在细胞中.并以基因形式包含在染色 体内每个基因有特殊的位置并控制某种特殊性质,所 以.每个基因产生的个体对环境具有某种适应性.基因突变和基因杂交可产生更适应于环境的后代.经过存优去 劣的自然淘汰.适应性高的基因结构得以保存下来. 遗传算法最大的特点莫过于可以绕过复杂的数学推 导而采用最直接的方式在有限空间中搜索结果.例如求 函数f(x)=x*sin(10"n'x)+2在(一1,2)区间上的极大值,按照常规思路.需要对函数求导,找出函数的变化趋势和拐点.才能确定最大值的位置.对于相对简单的函数.采用 这些数学的方法还没有太高的难度.但是对于复杂的函数.则需要较为深厚的数学功底.同时也增加了程序设计的复杂程度 对于GA.采用一套全新的思路,首先任意给定一组 随机值x.由此开始进行演化.这些值就是代表一系列原 始生命.这些生命是否可以延续,取决于他们的适应程 度将这些随机值带入函数中进行运算,对得到的一系列 函数值进行排序.求最大值,可以认为值较大的函数值对应的x接近我们所需要的结论,这些结果可以保留;反之.对于另外一些函数值较小的x.则表明应该被淘汰. 第二步就是按照Mendel的基因理论.对这些将被淘 汰的X进行演化.演化分两步进行: (1)交叉.两个x值交换数据,类似生物界的交配,染 色体进行重新重组.交换基因以期得到新的品种,新品种可能更加适应环境而得到生存的机会.也可能向相反的 方向发展.从而失去生存的机会.因此通过某种方式得到新的X的值可以导致函数值增大.也可能导致减小,他们都将参加新一轮的竞争 (2)变异.单一的X值进行自身的调整,这类似于生
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]
遗传算法十进制编码求函数极大值程序%Generic Algorithm for function f(x1,x2) optimum clear all; close all; Size=500; CodeL=2; MinX(1)=-2.048; MaxX(1)=2.048; MinX(2)=-2.048; MaxX(2)=2.048; E(:,1)=MinX(1)+(MaxX(1)-MinX(1))*rand(Size,1); E(:,2)=MinX(2)+(MaxX(2)-MinX(2))*rand(Size,1); G=200; BsJ=0; %*************** Start Running *************** for kg=1:1:G time(kg)=kg; %****** Step 1 : Evaluate BestJ ****** for i=1:1:Size xi=E(i,:); x1=xi(1); x2=xi(2); F(i)=100*(x1^2-x2)^2+(1-x1)^2; Ji=1./F; BsJi(i)=min(Ji); end [OderJi,IndexJi]=sort(BsJi); BestJ(kg)=OderJi(1); BJ=BestJ(kg); Ji=BsJi+1e-10; %Avoiding deviding zero fi=F; [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(kg)=Bestfi; kg 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 r=Size-sum(fi_S); Rest=fi_Size-fi_S; [RestValue,Index]=sort(Rest); for i=Size:-1:Size-r+1 fi_S(Index(i))=fi_S(Index(i))+1; % Adding rest to equal Size end k=1; for i=Size:-1:1 % Select the Sizeth and Reproduce firstly for j=1:1:fi_S(i) TempE(k,:)=E(Indexfi(i),:); % Select and Reproduce k=k+1; % k is used to reproduce end end %************ Step 3 : Crossover Operation ************ Pc=0.90; for i=1:2:(Size-1) temp=rand; if Pc>temp %Crossover Condition alfa=rand; TempE(i,:)=alfa*E(i+1,:)+(1-alfa)*E(i,:); TempE(i+1,:)=alfa*E(i,:)+(1-alfa)*E(i+1,:); end end TempE(Size,:)=BestS; E=TempE; %************ Step 4: Mutation Operation ************** Pm=0.10-[1:1:Size]*(0.01)/Size; %Bigger fi,smaller Pm
第五章遗传算法工具箱函数 本章介绍英国设菲尔德大学开发的遗传算法工具箱函数。 由于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。
#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个个体 {