利用DNA遗传算法求解制造资源的模糊优化问题

摘要:为了求解制造资源的模糊优化问题,提出基于DNA计算的混合遗传算法的求解方法。在该求解方法中,建立模糊优化问题的数学模型,以最大满意度为优化目标;采用四进制编码方式,将DNA序列分成中性和有害两部分,交叉操作只在中性部分进行;变异概率是动态变化的,由变异概率决定是否执行变异操作。通过对编码、选择、交叉和变异等遗传操作进行研究,给出了实例仿真的实验结果及结论。

关键词:DNA计算;改进遗传算法;模糊优化

中图分类号:TP312文献标识码:A文章编号:1009-3044(2010)17-4746-02

Solving Fuzzy Optimization Problems of Manufacturing Resources with DNA Genetic Algorithm

NIE Shu-zhi, YANG Fan, LI Jian-xiong

(Depart. of Computer Science and Eng., Guangzhou Vocational & Technical Institute of Industry & Commerce, Guangzhou 510850, China)

Abstract: In order to resolve manufacturing resources fuzzy optimization problems, put forward a method-hybrid genetic algorithm based on DNA computing. In this method, mathematical models for fuzzy optimization problems were built up, with the greatest satisfaction as the optimization goal; quaternary encoding was adopted, DNA sequence was divided into two parts-neutral and harmful, and the crossover operation can be carried out only in the neutral part; mutation rate changed dynamically, the performance of mutation operation depended on the mutation rate. According to the researches of genetic operations: encoding, selection, crossover and mutation etc,experimental results and conclusions from simulation examples are given.

Key words: DNA computing; improved genetic algorithm; fuzzy optimization

由于单一算法求解模糊问题存在一定的局限性,而采用混合方法既利用特定知识,又保持通用性,这是改善基本遗传算法性能的一个有效途径[1]。本文采用基于DNA计算与遗传算法相结合的策略,有效地解决模糊优化问题,并通过实例仿真验证了算法的可行性和有效性。

1 问题描述

以制造资源中的Job Shop调度为例,由于生产过程中由于作业过程受诸多随机因素的影响,只能得到工件i某道工序j 加工时间的一个大概数据以及数据的可能变化范围。同时,工件的交货期与客户的满意度最为密切,不同的客户对工件的交货期要求不同,并非都要求为一固定时刻,而是一个与客户满意度关联的时间窗口,即交货期也是模糊的[2-3]。

为此本文用三角模糊数ij(p1ij,p2ij,p3ij)来表示加工时间,μij(x)表示在机器j上加工的工件i在加工时间x内属于完工集合的隶属度。用梯形模糊数i来表示交货期,如图2所示,μi(c)表示工件i的满意隶属度函数,梯形模糊数(d1i,d2i,d3i,d4i)对应实际生产中提前/拖期完工情况。如果工件在[d2i,d3i]内完成,则该工件的满意度为1。

同时考虑模糊加工时间和模糊交货期,由于加工时间和交货期均为模糊量,采用以平均满意度作为优化指标[3]。客户满意度为产品模糊完工时间隶属函数和模糊交货期隶属函数的交集所围成的图形面积(即图3阴影部分图形面积)与模糊完工时间隶属函数形成的图形面积之比,其中i,i、分别表示模糊加工时间和模糊交货期的隶属函数形成的图形面积。

令Π表示工件的可行调度集合,对于一个给定的调度σ∈Π,令f(σ)表示相应的目标函数值,则平均满意度的最大调度模型可描述如公式4所示,其中,i为工件号,σ*为使得平均满意度最大的最优调度。

(1)

2 算法设计

遗传算法是一种通用而有效的解最优化问题的方法,但单用简单的遗传算法在许多情况下不是十分有效[7]。而遗传算法与DNA计算的观念有着天然的相似之处,DNA是重要的基因物质,携带着丰富的遗传信息,能促进遗传算法进一步模拟生物的遗传机理和基因调控机理,改善遗传算法的性能,而遗传算法可以成为突破DNA计算局限性的方法[4-5],因此二者的结合是一个值得深入研究的问题。

2.1 编码

DNA序列的解空间为E={A,C,G,T}L,本文采用0(00)、1(01)、2(10)、3(11)四个数字对应DNA的四种碱基进行四进制编码,则长度为L的DNA分子序列的类型空间为E={0,1,2,3}L。

2.2 初始化

随机产生N个位数为n×m,用[1,n]之间的自然数编码的染色体作为初始种群组成DNA汤,N为种群数,依次用随机数产生[1,n]之间的自然数,并记录产生的次数,每个随机数在染色体中只能出m次,这样可防止非法染色体的产生。

2.3 选择

为保护优良个体并保持种群多样性,在比例选择操作执行前,选择最好的N/2个序列和最差的N/2个序列作为选择操作的父辈。当前序列被复制的数目可根据下式计算:

(5)

式(5)中,,Fmax为保证Ji大于零的常数,fi为第i次的目标函数,通过选择操作将产生N个序列作为交叉和变异的父辈。

2.4 交叉

文献[6]将DNA分子序列分为中性和有害两大类,并指出在不同的分子序列中进行遗传操作可得到不同的进化结果。受此启发,可以定义最好的N/2个个体为中性个体,剩下的为有害个体。交叉算子均在中性个体中执行,其中置换操作的概率为1,转位操作的概率为0.5,若转位操作未执行,则执行换位操作。通过交叉操作,N/2个中性父辈将产生N个子后代。

2.5 变异

文献[6]指出,在同一个DNA序列的不同位置,存在hot spot和cold spot,且前者的碱基其变异概率远远大于后者。受此影响,对DNA遗传算法而言,在进化的不同阶段,DNA序列应拥有不同的hot spot和cold spot,且变异概率应是一个动态变化的过程。为保持种群的多样性并产生新的基因信息,变异操作在父辈的有害个体和交叉操作产生的子代中进行。

3 仿真试验与分析

3机器3工件的模糊加工任务分如表1所示。已知该3×3问题在规定加工顺序2-3-3-2-1-2-3-1-1下运用常规遗传算法求得的平均最大满意度为0.5[6-7]。现使用DNA遗传算法来求解,取最大进化代数为100,种群个数N为50,DNA序列长度L为40,经过多次运算均能获得平均最大满意度值为0.5,工件加工顺序为3-2-2-1-3-1-2-3-1。该调度结果与在规定加工顺序2-3-3-2-1-2-3-1-1下得到的最大满意度值0.5一致,从而验证了算法的有效性、可行性。

4 结论

采用DNA遗传算法和模糊的适应度函数求解模糊优化问题,通过改进遗传算子的编码、选择、交叉和变异等操作,可有效地解决模糊优化问题,仿真结果表明算法是可行的、有效的。

参考文献:

[1] 刘民,吴澄.制造过程智能优化调度算法及其应用[M].北京:国防工业出版社,2008:1-20.

[2] GARETTI M,TAISCH M. Neural networks in production planning and control[J]. Production Planning and Control,1999(10):324-339.

[3] 耿兆强,邹益仁.基于遗传算法的作业车间模糊调度问题的研究[J].计算机集成制造系统,2007,8(8):616-620

[4] 丁永生.DNA计算与软计算[M].北京:科学出版社,2002.61-73.

[5] 陶吉利.基于DNA计算的遗传算法及应用研究[D].浙江大学博士论文,2007:3-10.

[6] NEUHAUSER C, KRONES M. The Genealogy of Samples in Models with Selection[J].Genetics,1997,145(2):519-534.