遗传算法论文

1、数学建模论文基本遗传算法的MATLAB实现一、问题的提出遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方 法，它借鉴了达尔文的进化论和孟德尔的进化学说。其本质是一种高效、并行、 全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自 适应的控制过程以求的最优解。遗传算法操作使用适者生存的原则，在潜在的解 决方案中逐次产生一个近似最优方案。在遗传算法的每一代中，根据个体在问题 域中的适应度值和从自然遗传中借鉴来的再造方法进行个体选择，产生一个新的 近似解。这个过程导致种群中个体的进化，得到新个体比原来个体更适应环境， 就像自然界中的改造一样。基本遗传算法，最重要的是

2、产生随机数的过程，已知目标函数 max f(x1,x2)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2)其中约束条件为：-3.0=x1=12.14.1=x2=5.8编程用matlab实现基本遗传算法。二、问题的分析与模型的建立：遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿真算法，它模 拟基因重组与进化的自然过程，把待解决问题的参数编成二进制码或十进制码即 基因，若干基因组成一个染色体个体许多染色体进行类似于自然选择配对交叉和 变异的运算，经过多次重复迭代直到得到最后的优化结果。习惯上，适应度值越 大，表示解的质量越好。对于求解最小值问题，可通过变换转为求解

3、最大值问题。 遗传算法以群体为基础，不以单点搜索为基础，能同时从不同点获得多具极值， 因此不易陷入局部最优；遗传算法是对问题变量的编码集进行操作，而不是变量 本身，有效地避免了对变量的微分操作运算；遗传算法只是利用目标函数来区别 群体中的个体好坏而不必对其进行过多的附加操作。基本遗传算法定义：基本遗传算法是一种群体型操作，该操作以群体中的所有个体为对象只使 用基本遗传算子：选择算子，交叉算子，变异算子其遗传操作过程简单，容易理 解，是其他一些遗传算法的基础。数学模型：基本遗传算法可表示为：SGA=(C,E,P0,M, 0 , r , ,T) 其中：C一个体的编码方法E一个体适应度评价函数P0初

4、始种群M 种群大小0一选择算子r 一交叉算子w 一变异算子T遗传运算终止条件步骤：1.染色体的编码和解码。基本遗传算法使用固定长度的二进制符号来表示群体中的个体其等位基 因由二值0,1所组成。初始群体中各个个体的基因可用均匀分布的随机 数来生成。个体适应度的检测评估基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个 体遗传到下一代群体中机会多少。为了正确估计这个概率，要求所有个 体的适应度必须为非负数。遗传算子选择算子选择过程是以旋转赌轮次为基础的，赌轮上的刻度是每 个染色体的适应度来划分的。因此，这些刻度并不是平均分的。染色 体的适应度越大，该染色体在赌轮上所占的面积也就越大，该染

5、色体 被选中的概率也就越大。每次旋转都为新的种群选择一个新的染色 体。若设种群数为M，个体i的适应度为fi，则个体i被选取的概率为：Pi=fi/丈 fkk=1交叉运算使用单点交叉算子，只有一个交叉点位置，任意挑选经过选 择操作后的种群中两个个体作为交叉对象，随机产生一个交叉点位置 互换部分基因码，形成两个子个体。变异运算使用基本位变异算子算法函数目标函数 max f(x1,x2)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2) 其中约束条件为：-3.0=x1=12.14.1=x2=5.8决策变量为 x1,x2(x1,x2)表现型编码染色体，当(x1,x2)代入算法函

6、数，算法函数 max f(x1,x2)越大，则个体适应度越强，即选择概率越大。编码方法要进行编码工作，即将变量转化为二进制串。在此，变量x1的区间是-3.0,12.1,它要求的精度是小数点后四位，也就意味着每个变 量应该被分成至少(3.0+12.1)*104个部分。用下面的式子计算变量的二进制串位数：217(12.1+3.0)218-1解码方法设要求的精度为小数点后四位，则变量x1,x2可以转化为下面的串：(12.1+3.0)*10000=1510021715100=218所以m1=18(5.8-4.1)*10000=1700021417000=0上述染色体的适应度值为：eval(u1)=f(

7、-2.687969,5.361653) 二eval(u2)eval(u3)eval(u4)eval(u5)eval(u6)eval(u7)eval(u8)eval(u9)eval(u10)遗传操作选择（轮盘赌）计算适应度总和：F=如 eval （uk）k=1每个染色体的选择概率Pk:、eval （uk）Pk=F计算每个染色体的累计概率Qk：Qk= Epjj=i交叉（单点交叉）随机选择一个染色体串的节点，然后交换两个父辈节点右端部分来产生父辈。在这里假设交叉概率为25%,即在平均水平上游25%的染色体进行了交叉，变异（变异算子）如果被选定的染色体的被选定基因选作变异，即如果该位基因是1，则变异后

8、 就为0。将变异概率设为Pm=0.01，本题共有33*10=330个基因，希望每一代中有3.3 个变异的基因，每个基因变异的概率是相等的。因此，我们要生成一个位于0,1 之间的随机系列。问题的假设、符号说明:F表示计算适应度总和；Pk表示每个染色体的选择概率；Qk表示计算每个染色体的累计概率 x1,x2表示决策变量。五、模型的求解：六、模型的评价和推广：1 .评价：.优点：对可行解表示的广泛性；群体搜索特性；不需要辅助信息；内在启发式随机搜索特性；遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数 是不连续的，非规则的或有噪音的情况下，也能以很大的概率找到全局最优 解；遗传算法具有固有的并行性和并行计算能力；遗传算法具有可扩展性，易于同别的技术混合。.缺点：编码不规则或编码存在表示的不规则性；单一的遗传算法编码不能全面的将优化问题的约束表示出来；遗传算法通常的效率比比其他传统的优化