基于实数编码的遗传算法在饲料配方设计中的应用课件

基于实数编码的遗传算法基于实数编码的遗传算法在在饲料饲料配方设计中的应用配方设计中的应用基于实数编码的遗传算法在饲料配方设计中的应用1一、研究意义一、研究意义1、引入新的优化算法、引入新的优化算法遗传算法，解决现有饲料遗传算法，解决现有饲料配方设计中由纯数学思维算法本身局限性所产生配方设计中由纯数学思维算法本身局限性所产生的不足。的不足。如：线性规划模型中，当约束条件之间或约束条件如：线性规划模型中，当约束条件之间或约束条件与目标函数间存在矛盾时，系统无可行解；与目标函数间存在矛盾时，系统无可行解；数学上给出的满足约束条件和目标函数的优化配方，数学上给出的满足约束条件和目标函数的优化配方，从营养学的角度看有时又是不可行的。从营养学的角度看有时又是不可行的。一、研究意义1、引入新的优化算法遗传算法，解决现有饲料配2一、研究意义一、研究意义2、解决标准遗传算法在计算饲料配方时易产生早熟现象以及局、解决标准遗传算法在计算饲料配方时易产生早熟现象以及局部寻优能力差等问题部寻优能力差等问题 。如：用标准遗传算法在计算饲料配方时易产生早熟现象以及局部如：用标准遗传算法在计算饲料配方时易产生早熟现象以及局部寻优能力差等问题，特别是在原料多，约束条件多的情况下，这寻优能力差等问题，特别是在原料多，约束条件多的情况下，这种缺点表现的更为明显。种缺点表现的更为明显。一、研究意义2、解决标准遗传算法在计算饲料配方时易产生早熟现3二、遗传算法二、遗传算法（Genetic AlgorithmGenetic Algorithm，GAGA）遗传算法（遗传算法（Genetic Algorithm）是一类借鉴生物）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。演化而来的随机化搜索方法。1975年年遗传算法遗传算法美国美国J.Holland教授教授具有内在的隐并行性和更好的全局具有内在的隐并行性和更好的全局寻优能力；寻优能力；直接对结构对象进行操作，不存在求直接对结构对象进行操作，不存在求导和函数连续性的限定；导和函数连续性的限定；采用概率化的寻优方法，能自动获取采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。整搜索方向，不需要确定的规则。二、遗传算法（Genetic Algorithm，GA）遗传41、遗传算法的组成遗传算法可定义为一个遗传算法可定义为一个8员组：员组：SGA=(C,E,P0,M,T)C 个体的编码方法；个体的编码方法；E 个体适应度评价函数；个体适应度评价函数；P0 初始群体；初始群体；M 群体大小；群体大小；选择算子；选择算子；交叉算子；交叉算子；变异算子；变异算子；T 遗传运算终止条件。遗传运算终止条件。1、遗传算法的组成遗传算法可定义为一个8员组：52、遗传算法思想(1)(1)初始化群体；初始化群体；(2)(2)计算群体上每个个体的适应度值；计算群体上每个个体的适应度值；(3)(3)按由个体适应度值所决定的某个规则选择按由个体适应度值所决定的某个规则选择将进入下一代的个体；将进入下一代的个体；(4)(4)按概率按概率Pc进行交叉操作；进行交叉操作；(5)(5)按概率按概率Pm进行突变操作；进行突变操作；(6)(6)没有满足某种停止条件，则转第没有满足某种停止条件，则转第(2)步，否步，否则进入则进入(7)。(7)(7)输出种群中适应度值最优的染色体作为问输出种群中适应度值最优的染色体作为问题的满意解或最优解。题的满意解或最优解。2、遗传算法思想初始化群体；3、遗传算法的优点（1）遗传对所解的优化问题没有太多的数学要）遗传对所解的优化问题没有太多的数学要求，遗传算法可以处理任意形式的目标函数和约求，遗传算法可以处理任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连束，无论是线性的还是非线性的，离散的还是连续，甚至混合的搜索空间。续，甚至混合的搜索空间。（2）进化算子的各态历经性使得遗传算法能够）进化算子的各态历经性使得遗传算法能够非常有效的进行概率意义下的全局搜索，而传统非常有效的进行概率意义下的全局搜索，而传统的优化方法是通过邻近点比较而转移到较好的点，的优化方法是通过邻近点比较而转移到较好的点，从而达到收敛的局部搜索过程。从而达到收敛的局部搜索过程。（3）遗传算法对于各种特殊问题可以提供极大）遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式，从而保的灵活性来混合构造领域独立的启发式，从而保证算法的有效性。证算法的有效性。3、遗传算法的优点（1）遗传对所解的优化问题没有太多的数学要74、遗传算法性能分析指标（1）在线性性能评估）在线性性能评估在线性能表示为：在线性能表示为：其中：其中：T T 是进化代数；是进化代数；是第是第t t代的平均适应度函数；代的平均适应度函数；表示到表示到T T代为止所有适应度函数值的平均性能。代为止所有适应度函数值的平均性能。在线指标用于说明算法的在线性能。在线指标用于说明算法的在线性能。4、遗传算法性能分析指标（1）在线性性能评估其中：T 是进化84、遗传算法性能分析指标（2）离线性性能评估）离线性性能评估离线性能表示为：离线性能表示为：其中其中是第是第t代最好的个体的适应度函数值；代最好的个体的适应度函数值；表示至第表示至第T代每次最好的适应度函数值的平均。代每次最好的适应度函数值的平均。离线指标用于说明算法的收敛性。离线指标用于说明算法的收敛性。4、遗传算法性能分析指标（2）离线性性能评估其中是第t代最好三、遗传算法在饲料配方设计中的应用 算法设计流程图算法设计流程图饲料配方问题描述确定决策变量、约束条件建立线性规划模型确定适应度转换规则设计遗传因子个体表型X编码方法解码方法个体基因型X确定运行参数适应度函数F(x)遗传算法算法调试运行三、遗传算法在饲料配方设计中的应用 101、标准遗传算法在饲料配方设计中的应用1.1 编码策略编码策略 在遗传算法的运行过程中，它不对所求解问题的实际在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码决策变量直接进行操作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传算法，通过这种遗传操作施加选择、交叉、变异等遗传算法，通过这种遗传操作来达到优化的目的，这是遗传算法的特点之一。遗传算来达到优化的目的，这是遗传算法的特点之一。遗传算法通过这种对个体编码的操作，不断搜索出适应度较高法通过这种对个体编码的操作，不断搜索出适应度较高的个体，并在群体中逐渐增加其数量，最终寻求出问题的个体，并在群体中逐渐增加其数量，最终寻求出问题的最优解或近似最优解。的最优解或近似最优解。在遗传算法中如何描述问题的在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码算法所能处理的搜索空间的转换方法就称为编码。1、标准遗传算法在饲料配方设计中的应用1.1 编码策略 111.1 1.1 编码策略编码策略二进制编码二进制编码浮点数编码浮点数编码符号编码符号编码存在缺点：存在缺点：1、海明悬崖；、海明悬崖；2、求解的精度确定后算法缺乏微、求解的精度确定后算法缺乏微调能力；调能力；3、算法精度要求高或二进制编码、算法精度要求高或二进制编码字串长时，算法搜索效率较低。字串长时，算法搜索效率较低。也称实数编码，是指个体的每个也称实数编码，是指个体的每个基因值用某一范围内的一个浮点基因值用某一范围内的一个浮点数来表示，个体的编码长度等于数来表示，个体的编码长度等于其决策变量的个数。其决策变量的个数。根据饲料配方设计的要求及实数根据饲料配方设计的要求及实数编码的特点，在本次饲料配方中编码的特点，在本次饲料配方中的标准遗传算法采用实数编码。的标准遗传算法采用实数编码。1.1 编码策略二进制编码浮点数编码符号编码存在缺点：也称实121.2 初始种群的生成根据饲料原料及其营养成分表中各种原料的用量根据饲料原料及其营养成分表中各种原料的用量上限、用量下限、等量使用的要求，在最优解所上限、用量下限、等量使用的要求，在最优解所占问题空间中的分布范围内使用随机生成初始种占问题空间中的分布范围内使用随机生成初始种群。群。具体实现过程：具体实现过程：1.2 初始种群的生成根据饲料原料及其营养成分表中各种原料的131.2 初始种群的生成（1）生成随机种子；）生成随机种子；（2）设定初始种群的数量；）设定初始种群的数量；（3）利用约束条件对生成的每一个随机数的上下限进行控制，）利用约束条件对生成的每一个随机数的上下限进行控制，保证生成的随机数在约束条件围内；保证生成的随机数在约束条件围内；（4）测试生成的种群中各原料是否能满足营养需求，若不能满）测试生成的种群中各原料是否能满足营养需求，若不能满足则返回（足则返回（3）；）；（5）初始种群的数量是否达到，若达到则跳出，否则返回（）初始种群的数量是否达到，若达到则跳出，否则返回（3）。）。1.2 初始种群的生成（1）生成随机种子；141.3 适应度函数度量个体适应度的函数称为适应度函数度量个体适应度的函数称为适应度函数。饲料配方设计的要求是在保证满足饲养标准要求饲料配方设计的要求是在保证满足饲养标准要求的条件下降低饲料配方的成本。因此，本研究中的条件下降低饲料配方的成本。因此，本研究中遗传算法的个体适应度函数的设计采用饲料成本遗传算法的个体适应度函数的设计采用饲料成本极小化方法。适应度函数为：极小化方法。适应度函数为：ci代表第代表第i种的饲料原料的市场价格；种的饲料原料的市场价格；xi代表第代表第i种饲料原料在配方中的含量；种饲料原料在配方中的含量；Zmin为饲料配方的成本；为饲料配方的成本；n为饲料原料的种类数。为饲料原料的种类数。适应度较高的个体遗传到下一代的概率较大，适应度较适应度较高的个体遗传到下一代的概率较大，适应度较低的个体遗传到下一代的概率相对较小。低的个体遗传到下一代的概率相对较小。1.3 适应度函数度量个体适应度的函数称为适应度函数。ci代151.4 选择操作选择操作也叫复制操作，从群体中按个体的适应选择操作也叫复制操作，从群体中按个体的适应度函数值选择出较适应环境的个体。度函数值选择出较适应环境的个体。标准遗传标准遗传算法中采用轮盘赌模型。算法中采用轮盘赌模型。选择操作的主要目的是提高全局的收敛性和计算选择操作的主要目的是提高全局的收敛性和计算效率。效率。饲料配方设计中的标准遗传算法的选择操作的实现：饲料配方设计中的标准遗传算法的选择操作的实现：1.4 选择操作选择操作也叫复制操作，从群体中按个体的适应度161.4 选择操作 以单个个体适应度值倒数占种群中共以单个个体适应度值倒数占种群中共np个个体的适个个体的适应度值倒数之和的比率作为选择概率。即：应度值倒数之和的比率作为选择概率。即：单个个体适应度值倒数：单个个体适应度值倒数：适应度值倒数之和：适应度值倒数之和：选择概率：选择概率：(1=j=np)1.4 选择操作 以单个个体适应度值倒数占种群中共np1.5 交叉过程交叉运算是产生新个体的主要方法，是决定算法收敛性能的关键。交叉运算是产生新个体的主要方法，是决定算法收敛性能的关键。标准遗传算法中，进行交叉操作时，标准遗传算法中，进行交叉操作时，首先按照预先设定的交叉首先按照预先设定的交叉概率选出要进行交叉的个体，概率选出要进行交叉的个体，形成交叉配对池，形成交叉配对池，然后对配对池然后对配对池中的个体进行完全随机的等概率一一配对，最后对每一对父代个中的个体进行完全随机的等概率一一配对，最后对每一对父代个体随机确定交叉点，交换基因片段，生成新的子代个体。体随机确定交叉点，交换基因片段，生成新的子代个体。1.5 交叉过程交叉运算是产生新个体的主要方法，是决定算法收181.5 交叉过程根据实数编码的特点，交叉方式选择算术交叉。根据实数编码的特点，交叉方式选择算术交叉。算术交叉是指由两个个体的线性组合而产生出两个新的个算术交叉是指由两个个体的线性组合而产生出两个新的个体。体。当满足概率当满足概率Pc，则，则 ：rnd是是0,1上的随机数。上的随机数。1.5 交叉过程根据实数编码的特点，交叉方式选择算术交叉。r1.5 交叉过程否否种群中的每个个种群中的每个个体体Xi是否选择完是否选择完成？成？针对针对Xi生成随机数生成随机数R随机数随机数R小于小于交叉概率交叉概率Pc？种种群群中中的的个个体体Xi进进入入交交叉叉配配对池对池种群种群配配对对池池中中的的每每个个个个体体是是否否配配对完成？对完成？随机配对随机配对随机选择交叉随机选择交叉点点交换基因片段交换基因片段进入下一阶段操作进入下一阶段操作是是否否是是是是否否标准交叉操作具体流标准交叉操作具体流程图程图1.5 交叉过程否种群中的每个个体Xi是否选择完成？针对Xi201.6 变异过程变异运算是产生新个体的辅助方法。但也是必不变异运算是产生新个体的辅助方法。但也是必不可少的一步运算步骤。可少的一步运算步骤。主要目的：主要目的：（1）提高了遗传算法的局部搜索能力。提高了遗传算法的局部搜索能力。（2）维持群体的多样性，防止出现早熟现象。）维持群体的多样性，防止出现早熟现象。在本研究中，基本遗传算法变异过程的实现采用在本研究中，基本遗传算法变异过程的实现采用均匀变异均匀变异，即在变异过程中，个体中的一个随机，即在变异过程中，个体中的一个随机基因，在约束条件的上下范围内实现随机生成，基因，在约束条件的上下范围内实现随机生成，并替换原有基因值。并替换原有基因值。1.6 变异过程变异运算是产生新个体的辅助方法。但也是必不可211.7 算法操作的基本步骤（1）根据配方设计要求进行实数编码；）根据配方设计要求进行实数编码；（2）随机初始化群体）随机初始化群体P(0)=(p1,p2,pn)；（3）计算群体上每个个体的适应度值）计算群体上每个个体的适应度值(Fitness)；（4）评估适应度，对当前群体）评估适应度，对当前群体P(t)中每个个体中每个个体Pi计算其适计算其适应度应度F(Pi)；（5）按由个体适应度值所决定的某个规则应用选择算子产）按由个体适应度值所决定的某个规则应用选择算子产生中间代生中间代Pr(t)；（6）依照交叉概率）依照交叉概率Pc选择个体进行交叉操作；选择个体进行交叉操作；（7）根据变异概率）根据变异概率Pm对繁殖个体进行变异操作；对繁殖个体进行变异操作；（8）没有满足某种停止条件，则转第（）没有满足某种停止条件，则转第（3）步，否则进入）步，否则进入（9）步；）步；（9）输出种群中适应度值最优的个体。）输出种群中适应度值最优的个体。算法的停止条件：完成了预先给定的进化代数则停止。算法的停止条件：完成了预先给定的进化代数则停止。1.7 算法操作的基本步骤（1）根据配方设计要求进行实数编码22运行参数确定通过通过100次试验，分别确定：次试验，分别确定：终止代数终止代数G=300；群体大小群体大小M=128；交叉概率交叉概率Pc=0.7；变异概率变异概率Pm=0.1。运行参数确定通过100次试验，分别确定：23标准遗传算法的不足1、算法的运算时间长；、算法的运算时间长；2、计算后的结果不理想，与单纯型法的结果相比还有一定的差、计算后的结果不理想，与单纯型法的结果相比还有一定的差距。距。造成不足的原因：造成不足的原因：标准遗传算法在进化过程中易产生早熟现象和局部寻优能力差标准遗传算法在进化过程中易产生早熟现象和局部寻优能力差等问题。等问题。标准遗传算法的不足1、算法的运算时间长；242、改进的遗传算法2.1 编码策略编码策略同标准遗传算法。同标准遗传算法。2.2 初始种群生成初始种群生成同标准遗传算法。同标准遗传算法。2.3 适应度函数适应度函数同标准遗传算法。同标准遗传算法。2、改进的遗传算法2.1 编码策略252.4 选择策略标准遗传算法选择策略标准遗传算法选择策略轮盘赌模型存在以下轮盘赌模型存在以下缺陷：缺陷：（1）适应度函数中有较多指标需要计算，特别在）适应度函数中有较多指标需要计算，特别在多次的迭代过程中，一定程度上影响了程序运行多次的迭代过程中，一定程度上影响了程序运行效率；效率；（2）不能保证最优个体进入下一轮竞争。）不能保证最优个体进入下一轮竞争。2.4 选择策略标准遗传算法选择策略轮盘赌模型存在以下缺262.4 选择策略针对以上缺陷，对选择策略进行优化：针对以上缺陷，对选择策略进行优化：（1）采用随机联赛选择模型替代轮盘赌模型，降低计算机处理时间。）采用随机联赛选择模型替代轮盘赌模型，降低计算机处理时间。操作：每次从群体中随机选取操作：每次从群体中随机选取4个个体进行适应度大小比较，将其中适应度个个体进行适应度大小比较，将其中适应度最高的最高的2个个体遗传到下一代群体；重复上述过程直到下一代群体完全生成。个个体遗传到下一代群体；重复上述过程直到下一代群体完全生成。（2）构造新的种群时，采用精英主义方法。）构造新的种群时，采用精英主义方法。操作：在交叉和变异的过程中允许父代和子代进行竞争，让优良个体进入下操作：在交叉和变异的过程中允许父代和子代进行竞争，让优良个体进入下一轮的竞争环境，这样既保证了算法的迭代稳定性，又保证了算法具有实现一轮的竞争环境，这样既保证了算法的迭代稳定性，又保证了算法具有实现局部最优化的能力。局部最优化的能力。2.4 选择策略针对以上缺陷，对选择策略进行优化：272.5 交叉操作标准遗传算法交叉操作存在的缺陷：标准遗传算法交叉操作存在的缺陷：子代个体的搜索空间将不断收缩，从而导致早熟。子代个体的搜索空间将不断收缩，从而导致早熟。针对以上缺陷，对交叉操作进行改进。针对以上缺陷，对交叉操作进行改进。对父代矢量的各个分量进行交叉时，采用不同的随机数：对父代矢量的各个分量进行交叉时，采用不同的随机数：child1j=parent1j+rndj(parent2j-parent1j)child2j=parent2j+rndj(parent1j-parent2j)parent1j、parent2j分别为父代分别为父代parent1、parent2的分量；的分量；child1j、child2j分别为子代个体矢量分别为子代个体矢量child1、child2的分量；的分量；rndj为为-2,2区间的随机数。区间的随机数。2.5 交叉操作标准遗传算法交叉操作存在的缺陷：282.6 变异操作标准遗传算法变异操作存在的缺陷：标准遗传算法变异操作存在的缺陷：均匀变异特点适合应用于遗传算法的初期运行均匀变异特点适合应用于遗传算法的初期运行阶段，但在运行阶段后期对于局部的重点搜索，阶段，但在运行阶段后期对于局部的重点搜索，均匀变异的收敛难于达到一个很好的效果。均匀变异的收敛难于达到一个很好的效果。针对以上缺陷，对变异操作进行改进：针对以上缺陷，对变异操作进行改进：采用高斯变异来改进均匀变异，高斯变异时符采用高斯变异来改进均匀变异，高斯变异时符合正态分布的随机数合正态分布的随机数Q可由一些符合均匀分布的随可由一些符合均匀分布的随机数利用公式来近似产生。机数利用公式来近似产生。2.6 变异操作标准遗传算法变异操作存在的缺陷：292.7 交叉概率和变异概率标准遗传算法中存在问题：标准遗传算法中存在问题：交叉概率交叉概率Pc越大，新个体产生的速度越快，遗传模式被破越大，新个体产生的速度越快，遗传模式被破坏的可能性也越大；坏的可能性也越大；Pc太小，会使搜索过程缓慢，以至停太小，会使搜索过程缓慢，以至停滞不前。滞不前。变异概率变异概率Pm过小，不易产生新个体；变异率过小，不易产生新个体；变异率Pm过大，遗过大，遗传算法就变成了纯粹的随机搜索法。传算法就变成了纯粹的随机搜索法。改进方法：改进方法：针对针对Pc和和Pm采用自适应调整，对性能较差的个体采用较大采用自适应调整，对性能较差的个体采用较大的交叉率和变异率，对于性能优良的个体则根据适应度的的交叉率和变异率，对于性能优良的个体则根据适应度的大小采用适当的交叉率和变异率，随着繁衍代数的增大，大小采用适当的交叉率和变异率，随着繁衍代数的增大，交叉率和变异率将下降，以利于算法的收敛。交叉率和变异率将下降，以利于算法的收敛。2.7 交叉概率和变异概率标准遗传算法中存在问题：302.8 算法操作改进措施：改进措施：（1）在优化设计中不再使用固定代数作为进化的终止条件，采）在优化设计中不再使用固定代数作为进化的终止条件，采用连续用连续30代中每代的最优进化个体（配方）适应度值变化小于代中每代的最优进化个体（配方）适应度值变化小于0.001(吨成本吨成本)，即认为进化结束，如果计算达到，即认为进化结束，如果计算达到300代还未达成代还未达成前述要求，即认为进化结束。前述要求，即认为进化结束。（2）交叉和变异中，子个体与父代共同竞争，确保优良个体进）交叉和变异中，子个体与父代共同竞争，确保优良个体进入新种群。入新种群。2.8 算法操作改进措施：312.8 算法操作改进改进后遗后遗传算传算法的法的流程流程图图2.8 算法操作改进后遗传算法的流程图32四、总结目前本研究中设计的改进遗传算法在测试环境中组成一个配方平均需要的时目前本研究中设计的改进遗传算法在测试环境中组成一个配方平均需要的时间大约为间大约为27.67秒，速度优于标准遗传算法，最低成本配方优于标准遗传算秒，速度优于标准遗传算法，最低成本配方优于标准遗传算法和单纯型法设计的饲料配方，但还需结合营养学要求进一步完善算法，该法和单纯型法设计的饲料配方，但还需结合营养学要求进一步完善算法，该算法在饲料配方设计领域应具有很好的应用前景。算法在饲料配方设计领域应具有很好的应用前景。本研究目前还处于算法研究阶段，要达到实用还需做进一步的研究和完善工本研究目前还处于算法研究阶段，要达到实用还需做进一步的研究和完善工作。作。四、总结目前本研究中设计的改进遗传算法在测试环境中组成一个配33