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