论文部分内容阅读
摘 要：本文首先介绍了遗传算法的基本概念、原理，然后根据算法在实际问题中所发挥的重要作用，将其用来解决实际问题；指出了遗传算法在啤酒配方领域应用中的几个关键问题，分析说明了遗传算法在该领域应用的具体方法步骤，通过实验结果表明遗传算法在解决该领域存在的实际问题中的所发挥的重要作用。
关键词：遗传算法；啤酒配方；适应度函数
1、 引言
遗传算法是一种源于生物进化论、物种选择学说和基因遗传理论的适合于复杂系统优化计算的自适应概率优化的最优解搜索算法；其基本思想是模拟生物进化、遗传等自然现象，在一定的搜索空间和群体范围中，通过种群的不断选择、交叉、变异等手段逐步寻找最优解的过程；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的品种，对这个新种群进行下一轮进化；鉴于遗传算法具有良好的全局寻优性能，其广泛应用于智能优化领域、模式识别工程设计等领域，本文主要将其同啤酒配方设计的实际问题相结合，展示了其在实际问题中所具有的良好性能。
2、 遗传算法与涉及行业的结合
在啤酒行业中，啤酒配料是啤酒口味的决定性因素，配料是由多种配方组合而成的，如
人为因素、自然条件因素等，都影响了配方的内在品质，即使同一产地，同一等级的配方由于各种因素的影响，配方的好坏直接影响啤酒口味的品质，而在如何选择合适的优化方法是一个难点，因为啤酒的配料是一个多变量的问题，而啤酒的优良与否一般由外观质量和内在质量两方面决定，而内在质量主要由啤酒的配方决定，然而随着我国啤酒行业的快速发展，为适应配料的变化，每一种配方的质量及其原料的稳定性对啤酒的质量起了重要的作用，只有提高每一种配方的质量才能使啤酒的品质得到有效的保证。但是每一种配方都是由多种原料组合而成，如何从多种配方中选择出一种最符合要求的、最优的配方是我们面临的问题。
遗传算法作为一种迅速发展的智能优化方法，其良好的全局寻优性能可以帮助我们自动寻找出我们所需的配方组合，进而得到最优的配料。这从另一个方面有效降低了生产成本，提高了生产效率，同时也有效的保证了啤酒的质量。目前啤酒配料都是依据以往经验和感性认识，对选出的配方进行配比组合做成一个配料，在对原料进行糖化、发酵、贮酒后熟设计得到样本，然后进行鉴定。
3、 算法的计算原理及应用
3、1算法步骤：
（1）选取合适的编码方式
本文采用二进制编码，二进制串的长度取决于所要求的精度。编码是遗传算法要解决的首要问题，我们需要对每一个个体进行编码，本文中我们采用二进制编码，它是遗传算法中最常用的编码方式，它具有以下一些优点：（1）编码、解码操作简单易行；（2）交叉、变异操作便于实现；（3）符合最小字符集编码原则；（4）便于利用模式定理对算法进行理论分析。把各种不同配方的问题变成组合问题， 1代表选中，0则反之；这样得到的0—1组合就代表配方方案。
（2） 产生初始群体
在给定变量范围内产生一批具有固定长度符号串的个体作为初始设计种群，每个个体的符号串中包含着各优化设计变量信息，选择一定的编码方案对初始群体进行编码，组成基因码串每一码串代表一个个体，表示优化问题的一个解。
（3） 预测模型的建立及其适应度的计算
适应度函数可以用来度量群体中各个个体在优化计算中可能达到最优解的优良程度。适应度值的大小决定个体遗传到下一代的概率大小。在该配方方案中，我们一般选定m种配方，每种配方含有n个原料属性。被选中的配方将组合成一个我们需要的配料。若有m种配方组合构成配料方案a，xak ， 表示配方k在方案a中是否被选中；当该位为编码1时表示该方案被选中，当该位编码为0时表示该方案未被选中，以 作为第b代个体，即将配方方案a表示为 ，这样所有的配方便组成一个二进制的编码，然后根据配方是否选定求出每一代中每个个体的适应度函数f（b）1…f（b）m ，然后找出每一代中最大适应度函数值f（b）1Max…f（b）mMax ，最后从中取出适应度最高的 f（z）Max。
（4） 结果的选取
在满足相应条件的情况下，我们首先求出每一代中单个个体的适应度函数，找出适应度值最高的那一个个体。然后根据每一代中适应度值最高的个体找到使误差函数 最小的解即为最优解。即求：
，其中za为实际优化计算得到的相应属性的值za， 为设定的目标预测值。
3.2 遗传操作
（1）选择操作
采用二元锦标赛选择。随机选择两个个体，如果非劣等级不同，则取等级（级数小）较高的，如果级数相同则取聚集密度较小的小生境内的个体，这样将保持个体的多样性，使进化朝着非劣解和均匀散步方向进行。
（2）交叉操作
本文采用单点交叉，把两个父代个体的部分结构进行替换重组得到新个体的操作。
交叉运算是遗传算法区别于其他进化算法的重要特征设。在交叉时该点前或后的两个个体的部分结构进行互换，同时生产两个新个体。由于交叉概率大小决定交叉操作的频率，频率越高，可以越快收敛到所希望的最优解，一般选择较大的概率值。
（3）变异操作
变异运算是产生新个体的辅助方法，但必不可少，因为它决定了遗传算法的局部搜索能力。变异过程中，如果概率过小，则算法产生新个体的能力会降低，概率太大会使算法变成纯粹的随机搜索算法，一般设定在0.01—0.2的范围内。在实际应用中， 不同的问题可以有不同的变异率， 在同一问题中针对不同的情况也可以有所变化，可根据需要适当人为调整。
4 实验结果
用遗传算法优化配料问题就是在给定原料和设定优化目标的情况下，搜索寻找出配方组合的最优方案。本文选择了配方的原料1、原料2、原料3、原料4、原料5几个数据和其他指数等作为实验标准，具体试验标准值情况参见表1。每次在选定的配方的情况下进行搭配优化并给出搭配方案，从中选出最优的配方搭配设计方案。在实验分析时，只参考了抽象数据的几个重要指标和其他指数，其他数据未纳入目标约束范围内； 图 1实验结果的截图：
表1 优化目标及设定值
我们首先确定该算法的运行参数为：群体大小为200，最大迭代次数为300，交叉概率为0.5，变异概率为0.03。实验结果列出了5个好的优化方案，为使分析结果更清晰直观进行了截图展示，请参见图1。图1列出了迭代次数、每一代最优个体编码、以及对应适应度值和误差函数，群体中最优个体的适应值和平均适应值不断变化，直至最优个体的适应值达到某一稳定值，或最优个体的适应值和群体的平均适应值不再变化，同时满足各项约束条件，输出结果，算法结束。通过程序的运行结果我们可以找出方案误差比例最小的那一个，方案误差比例越小，说明该配方方案越好，再通过该个体的二进制编码找出最优配料组合。用遗传算法优化配方，其优化配方方案设计效果是很理想的，达到了预计的要求；说明遗传算法在配方原料设计方面是十分有效的。
5 结束语
遗传算法作为一种非确定性的拟自然算法为复杂系统的优化提供了一种新的方法，并且经过实践证明效果显著。本文在经过研究各种原料配方和遗传算法的基础上，将遗传算法用于对各种配方误差的评定。尽管遗传算法在很多领域具有广泛的应用价值，但它仍存在一些问题，如遗传算法很多机制和现象还缺少理论的指导，这都需要对遗传算法做进一步的研究。
参考文献
[1] 陈建安等. 遗传算法理论研究综述 . 西安电子科技大学学报， 1998.
[2] 薛小兰. 遗传算法及其在平面度误差评定中的应用 .晋中学院学报，2009.
[3] 叶晋等. 遗传算法在轨道交通换乘路径求解问题上的应用 .电脑与信息技术，2009.
[4] 杨华芬. 遗传算法的分析及其改进 .云南民族大学学报，2009.
[5] 江季松，叶继红. 遗传算法在单层球壳质量优化中的应用.振动与冲击，2009.
[6] 丁香乾，韩运实.自适应遗传算法解决集装箱装载问题的方法探讨[J].中国海洋大学学报，2004.
[7] Hamidreza Eskandari， Luis Rabelo， Mansooreh Mollaghasemi. MUTIOBJECTIVE SIMULATION OPTIMIZATION USING AN ENHANCED GENETIC ALGORITHM. Proceedings of the 2005 Winter Simulation Conference.2005
关键词：遗传算法；啤酒配方；适应度函数
1、 引言
遗传算法是一种源于生物进化论、物种选择学说和基因遗传理论的适合于复杂系统优化计算的自适应概率优化的最优解搜索算法；其基本思想是模拟生物进化、遗传等自然现象，在一定的搜索空间和群体范围中，通过种群的不断选择、交叉、变异等手段逐步寻找最优解的过程；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的品种，对这个新种群进行下一轮进化；鉴于遗传算法具有良好的全局寻优性能，其广泛应用于智能优化领域、模式识别工程设计等领域，本文主要将其同啤酒配方设计的实际问题相结合，展示了其在实际问题中所具有的良好性能。
2、 遗传算法与涉及行业的结合
在啤酒行业中，啤酒配料是啤酒口味的决定性因素，配料是由多种配方组合而成的，如
人为因素、自然条件因素等，都影响了配方的内在品质，即使同一产地，同一等级的配方由于各种因素的影响，配方的好坏直接影响啤酒口味的品质，而在如何选择合适的优化方法是一个难点，因为啤酒的配料是一个多变量的问题，而啤酒的优良与否一般由外观质量和内在质量两方面决定，而内在质量主要由啤酒的配方决定，然而随着我国啤酒行业的快速发展，为适应配料的变化，每一种配方的质量及其原料的稳定性对啤酒的质量起了重要的作用，只有提高每一种配方的质量才能使啤酒的品质得到有效的保证。但是每一种配方都是由多种原料组合而成，如何从多种配方中选择出一种最符合要求的、最优的配方是我们面临的问题。
遗传算法作为一种迅速发展的智能优化方法，其良好的全局寻优性能可以帮助我们自动寻找出我们所需的配方组合，进而得到最优的配料。这从另一个方面有效降低了生产成本，提高了生产效率，同时也有效的保证了啤酒的质量。目前啤酒配料都是依据以往经验和感性认识，对选出的配方进行配比组合做成一个配料，在对原料进行糖化、发酵、贮酒后熟设计得到样本，然后进行鉴定。
3、 算法的计算原理及应用
3、1算法步骤：
（1）选取合适的编码方式
本文采用二进制编码，二进制串的长度取决于所要求的精度。编码是遗传算法要解决的首要问题，我们需要对每一个个体进行编码，本文中我们采用二进制编码，它是遗传算法中最常用的编码方式，它具有以下一些优点：（1）编码、解码操作简单易行；（2）交叉、变异操作便于实现；（3）符合最小字符集编码原则；（4）便于利用模式定理对算法进行理论分析。把各种不同配方的问题变成组合问题， 1代表选中，0则反之；这样得到的0—1组合就代表配方方案。
（2） 产生初始群体
在给定变量范围内产生一批具有固定长度符号串的个体作为初始设计种群，每个个体的符号串中包含着各优化设计变量信息，选择一定的编码方案对初始群体进行编码，组成基因码串每一码串代表一个个体，表示优化问题的一个解。
（3） 预测模型的建立及其适应度的计算
适应度函数可以用来度量群体中各个个体在优化计算中可能达到最优解的优良程度。适应度值的大小决定个体遗传到下一代的概率大小。在该配方方案中，我们一般选定m种配方，每种配方含有n个原料属性。被选中的配方将组合成一个我们需要的配料。若有m种配方组合构成配料方案a，xak ， 表示配方k在方案a中是否被选中；当该位为编码1时表示该方案被选中，当该位编码为0时表示该方案未被选中，以 作为第b代个体，即将配方方案a表示为 ，这样所有的配方便组成一个二进制的编码，然后根据配方是否选定求出每一代中每个个体的适应度函数f（b）1…f（b）m ，然后找出每一代中最大适应度函数值f（b）1Max…f（b）mMax ，最后从中取出适应度最高的 f（z）Max。
（4） 结果的选取
在满足相应条件的情况下，我们首先求出每一代中单个个体的适应度函数，找出适应度值最高的那一个个体。然后根据每一代中适应度值最高的个体找到使误差函数 最小的解即为最优解。即求：
，其中za为实际优化计算得到的相应属性的值za， 为设定的目标预测值。
3.2 遗传操作
（1）选择操作
采用二元锦标赛选择。随机选择两个个体，如果非劣等级不同，则取等级（级数小）较高的，如果级数相同则取聚集密度较小的小生境内的个体，这样将保持个体的多样性，使进化朝着非劣解和均匀散步方向进行。
（2）交叉操作
本文采用单点交叉，把两个父代个体的部分结构进行替换重组得到新个体的操作。
交叉运算是遗传算法区别于其他进化算法的重要特征设。在交叉时该点前或后的两个个体的部分结构进行互换，同时生产两个新个体。由于交叉概率大小决定交叉操作的频率，频率越高，可以越快收敛到所希望的最优解，一般选择较大的概率值。
（3）变异操作
变异运算是产生新个体的辅助方法，但必不可少，因为它决定了遗传算法的局部搜索能力。变异过程中，如果概率过小，则算法产生新个体的能力会降低，概率太大会使算法变成纯粹的随机搜索算法，一般设定在0.01—0.2的范围内。在实际应用中， 不同的问题可以有不同的变异率， 在同一问题中针对不同的情况也可以有所变化，可根据需要适当人为调整。
4 实验结果
用遗传算法优化配料问题就是在给定原料和设定优化目标的情况下，搜索寻找出配方组合的最优方案。本文选择了配方的原料1、原料2、原料3、原料4、原料5几个数据和其他指数等作为实验标准，具体试验标准值情况参见表1。每次在选定的配方的情况下进行搭配优化并给出搭配方案，从中选出最优的配方搭配设计方案。在实验分析时，只参考了抽象数据的几个重要指标和其他指数，其他数据未纳入目标约束范围内； 图 1实验结果的截图：
表1 优化目标及设定值
我们首先确定该算法的运行参数为：群体大小为200，最大迭代次数为300，交叉概率为0.5，变异概率为0.03。实验结果列出了5个好的优化方案，为使分析结果更清晰直观进行了截图展示，请参见图1。图1列出了迭代次数、每一代最优个体编码、以及对应适应度值和误差函数，群体中最优个体的适应值和平均适应值不断变化，直至最优个体的适应值达到某一稳定值，或最优个体的适应值和群体的平均适应值不再变化，同时满足各项约束条件，输出结果，算法结束。通过程序的运行结果我们可以找出方案误差比例最小的那一个，方案误差比例越小，说明该配方方案越好，再通过该个体的二进制编码找出最优配料组合。用遗传算法优化配方，其优化配方方案设计效果是很理想的，达到了预计的要求；说明遗传算法在配方原料设计方面是十分有效的。
5 结束语
遗传算法作为一种非确定性的拟自然算法为复杂系统的优化提供了一种新的方法，并且经过实践证明效果显著。本文在经过研究各种原料配方和遗传算法的基础上，将遗传算法用于对各种配方误差的评定。尽管遗传算法在很多领域具有广泛的应用价值，但它仍存在一些问题，如遗传算法很多机制和现象还缺少理论的指导，这都需要对遗传算法做进一步的研究。
参考文献
[1] 陈建安等. 遗传算法理论研究综述 . 西安电子科技大学学报， 1998.
[2] 薛小兰. 遗传算法及其在平面度误差评定中的应用 .晋中学院学报，2009.
[3] 叶晋等. 遗传算法在轨道交通换乘路径求解问题上的应用 .电脑与信息技术，2009.
[4] 杨华芬. 遗传算法的分析及其改进 .云南民族大学学报，2009.
[5] 江季松，叶继红. 遗传算法在单层球壳质量优化中的应用.振动与冲击，2009.
[6] 丁香乾，韩运实.自适应遗传算法解决集装箱装载问题的方法探讨[J].中国海洋大学学报，2004.
[7] Hamidreza Eskandari， Luis Rabelo， Mansooreh Mollaghasemi. MUTIOBJECTIVE SIMULATION OPTIMIZATION USING AN ENHANCED GENETIC ALGORITHM. Proceedings of the 2005 Winter Simulation Conference.2005