2021采用遗传算法进行车间平面布置

采用遗传算法进行车间平面布置文章编号:100725429(2002)0420030204收稿日期:2001-11-22基金项目:清华大学985工程“数字化轿车”资助项目作者简介:王昕岩(1977-),男,北京人,清华大学工业工程系硕士生。采用遗传算法进行车间平面布置王昕岩,蔡临宁,姚健(清华大学工业工程系,北京100084) 摘要:利用遗传算法进行车间的平面布置。计算结果表明,应用遗传算法求解车间布置问题 不仅可以获得优化程度高的近似最优解,而且具有高的计算效率和很强的实际应用性。关键词:遗传算法;平面布置;车间中图分类号:TH162.1 文献标识码:AApplication of G enetic Algorithms in Plant LayoutW ANG X in 2yan ,C AI Lin 2ning ,Y AO Jian(Dept.of Industrial Engineering ,Tsinghua University ,Beijing 100084,China ) Abstract :G enetic alg orithm is a kind of global stochastic research method that simulates biological ev olu 2tion process to achieve optimal results.The result shows that genetic alg orithms can not only get excellent near optimal s olutions ,but als o have high com puting efficiency and practicability. K ey w ords :genetic alg orithm ;plant lay out ;w orkshop1引言车间平面布置是使车间内的人、设备和物料在空间上实现最合理的组合,使其总体物流费用最低。1957年K oopm ans 和Beckm ann 把布置问题模型化为二次分派问题(QAP ),引起了人们对布置问题的深入研究。解决平面布置的方法有很多,按照优化程度,主要可分为两大类:最优化算法(optimal alg orithms )和启发式算法(heuristic alg orithms )。前者能够获得问题精确的最优解;而后者只能获得满足一定精确程度的近似最优解。一般来说中小规模的问题(设施个数小于14个)可以通过最优化算法来求解。但是随着设施个数的不断增加,问题的计算量呈指数递增,最优化算法就不能非常有效地解决问题。而启发式算法却能够在小计算量的情况下获得近似最优解,从而有效地解决大规模的平面布置问题。启发式算法有很多种,如:模拟退火算法、T ABU 寻优算法、爬山算法、遗传算法等。由于遗传算法计算效率高,求解效果好,得到了广泛的应用。平面布置中的遗传算法由编码方法、选择、交叉算子、变异算子以及解码调整等步骤组成。不同的编码及算子组合会构成大量的遗传算法。通过研究,本文选择了赌盘选择、基于顺序的交叉和启发式变异算子组合的遗传算法进行了某制造车间的块状平面布置。2平面布置的数学模型平面布置问题数学模型是一种组合优化问题。组合优化问题有3个基本要素:变量、约束和目标函数。在求解过程中选定的基本参数称为变量,对变量取值的种种限制称为约束,表示可行方案衡量标准的函数称为目标函数。平面布置问题的变量是各个设施在空间中的位置组成的向量;约束就是各个设施在空间中的位置约束;目标可以是单个的,也可以是多个的,大多数的车间布置问题都是以设施间物料搬运费用最小为目标。车间平面布置问题可以抽象为以下的数学模型:目标函数:f (x )=min ki j c ij (k )d ij (k )e ij (k )+jf j (k )(1)式中c ij (k )表示第k 种布局方案中,第i 个位置与第j 个位置的物流量;d ij (k )表示第k 种布局方案中,第i 个位置与第j 个位置间的距离;e ij (k )表示第k 种布局方案中,第i 个位置与第j 个位置间,单位距离单位物流量的物流运送费用;f j (k )表示第k 种布局方案中,设施布置在第j个位置所需的固定费用。一般来说对应于目标函数的遗传算法的适值函数可由以下转换机制实现:适值函数:fitf unc =C max -f (x ),f (x )C max0, f (x )C max(2)式中C max 是预定的参数,保证大多数解的适值为正值。3遗传算法3.1遗传算法的基本流程与特点遗传算法13是一种随机性的全局搜索算法。它是模拟生物的进化过程中优胜劣汰的过程来求解优化问题。首先,它将问题的解转化成一串数字(由自然数组成),把它类比为生物体基因的染色体,用它代表问题的某个解,称作解的染色体(chrom os ome ,以下简称染色体)。这个将问题的解转化成染色体的过程叫做编码。其次,随机产生一定数量的染色体组成一个染色体集合,把它称为群落。群落中染色体的数目在计算过程当中始终是固定的,令它为P (即种群数量)。这个随机产生的群落叫做遗传算法的初始代。第三,制定评价解优劣的准则适应性函数值(fitness ,以下简称适值)。它的值越高,染色体所代表的解就越“优”。适值是对解的评价,当然也就代表了问题的目标,它与平面布置问题的目标函数有着密切的关系。最后,通过对初始代的选择(selection )、交叉(cross over )、变异(mutation )计算产生子代个体新的一个染色体群落。对这新的一代继续进行选择、交叉、变异计算,它又产生自己的子代个体。就这样循环操作,直到满足循环一定代数为止。最后一代中最优的染色体对应的解就是近似最优解。遗传算法就是这样实现随机寻优搜索的,其基本步骤如图1所示。图1遗传算法流程图与传统的优化算法相比,遗传算法具有以下特点:(1)直接对解编码的集合进行操作,而不是对解集本身;(2)它的寻优始于解的一个群落,而不是单个解;(3)它利用目标函数本身的信息建立寻优方向,而不是利用其导数信息建立寻优方向,不存在求导和函数连续性的限制,因此它对优化设计问题的限制较少,仅要求问题是可计算的;(4)它采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。遗传算法利用概率转移规则,可以在一个具有不确定性的空间上寻优。与一般的随机型优化方法相比,遗传算法不是从一点出发沿一条线寻优,而是在整个解空间同时开始寻优搜索,因此可以有效地避免陷入局部极小点,具备全局最优搜索性。3.2平面布置问题解的编码如何将问题的解转化成染色体是应用遗传算法解决平面布置问题的基础。编码方案的好坏也直接关系到遗传算子的设计,进而影响问题解决的优化程度。在一个二维平面布置中,本文采用图2所示的编码方式,即染色体为9|5|1|4|8|6|10|7|2|3|11|。图2编码方式图3.3遗传算法的算子遗传算子是实现遗传优化的最基本的计算,也是影响算法计算效果的最大因素,它包括选择算子、交叉算子和变异算子。目前在平面布置问题中应用较为广泛的选择算子有:赌盘选择等;交叉算子有:单点交叉、OX 交叉、基于位置的交叉、基于顺序的交叉等;变异算子有:反转变异、移位变异、插入变异、互换变异、启发式变异等。通过分析比较,发现赌盘选择、基于顺序的交叉和启发式变异算子组合而成的遗传算法在平面布置问题中具有较好的遗传规律。下面对赌盘选择、基于顺序的交叉和启发式变异算子三种算子进行简单的介绍。3.3.1赌盘选择算子赌盘选择算子3选择将适值大的个体选进准备进行交叉的个体队伍中,而适值小的尽量避免被选中。它是以个体的适值占群落中所有个体的适值总和的比例为标准进行选择的。这种算法可以直观地用赌盘选择图(图3)来阐释。图中扇形面积占圆面积的比例就是个体适值占适值总和的比例。每次选择转动一次圆盘,圆盘停下时指针指向的个体就是被选中的个体。因此个体所占扇形面积越大,被指针指中的可能性就越大。图3赌盘选择图3.3.2基于顺序的交叉算子基于顺序的交叉算子3的基本步骤如下:步骤1:从第一个父代个体中随机选若干个位置,存储这些位置上对应的元素;步骤2:删去第二个父代个体中这些元素,将第二个父代个体其他的元素复制到一个空字串的相应位置,产生一个原始子代个体;步骤3:将第一个父代个体中被存储的元素按在第一个父代个体中的顺序定位到子代个体的空缺位置上。步骤说明示例如下:父代个体1564321父代个体2241536子代个体642531 示例中,第一步,父代个体1中被存储的元素及其相应顺序为6,2,1;第二步,删除父代个体2中6,2,1三个元素(圆圈内的3个元素),并将元素4,5,3按原来位置填入子代个体中,再将6,2,1三个元素按序填入。 3.3.3启发式变异算子启发式变异算子3对一个染色体按它的邻域交换不多于n 个基因位,可获得一组染色体,选择其中适值最大的一个作为变异产生的子代个体。启发式变异过程如下:步骤1:随机地选出n 个基因;步骤2:按所有选出基因的可能的换位产生邻域;步骤3:评估所有邻域点,选出最好的作为变异产生的子代个体。步骤说明如下: 原始子代个体264135 子代个体邻域2643152341652346152143652146354算例及结果通过上述的编码及遗传算子组合,利用C +实现了计算机辅助布置设计软件TH 2C AFP 的核心计算模块。需要指出的是,计算机辅助布置方法分为构建型及改进型方法。采用遗传算法是一种对已有平面布置进行改进的改进型方法,其初始布置可以随机生成也可以由构造型方法生成。本文算例由某制造厂的平面布置问题抽象而得来。这里将车间分为11个工作区,用1至11来代表各工作区。其面积如表1所示,各工作区中心间的直线距离如表2所示。各区之间的物流量如表3所示。优化目标以设施间的物料搬运费用最小为目标。计算中采用的参数为:种群数量P =100,交叉概率Pc =0.9,变异概率P m =0.05,最大代数maxgen =4000。采用以上参数重复进行10次计算。表1工作区面积工作区面积(m 2)1400220032004260520063407500840094001026011320王昕岩等:采用遗传算法进行车间平面布置表2距离表12345678910111015253340424755353020215010182527324250453532510081517223252554543318807914244449535402515702717374252642271792051535405074732221475010303540855423224171510020253593550524437353020051510304555494240352550101120354553525040351510 表3物流量表12345678910111052211412912502512782383220744945654257087818515114803413366124730584757479845076328184118709489225834690531093653734505111851652835 计算结果如表4所示。其中获得的最小费用为12202,染色体为:1|10|5|4|3|9|7|6|8|11|2|。经过 解码调整后,与该解相应的布局图如图4所示。表4计算结果次数最小费用染色体11269011|5|6|4|9|8|7|3|2|1|10|2122021|10|5|4|3|9|7|6|8|11|2|3126286|11|8|2|7|9|3|4|5|1|10|4124965|1|10|4|3|6|7|9|8|11|2|5131185|2|11|8|6|9|7|10|3|1|4|6126101|10|3|4|9|7|8|6|2|11|5|71281211|6|3|5|4|7|9|8|2|1|10|8124482|1|10|5|4|7|3|9|6|8|11|91267211|8|6|3|9|7|4|5|1|2|10|10122021|10|5|4|3|9|7|6|8|11|2|图4块状布置图 通过遗传算法对实际算例的计算,可以很明显 地看出它不仅可以获得优化程度高的近似最优解,而且计算效率也比较高。如果在同样的情况下利用最优化算法,需要搜索整个可行解空间,仅仅计算目标函数值就需要约n !=39916800次,而遗传算法无需遍历整个解空间,计算目标函数值仅需P 3maxgen =400000次,数量级相差102,大大节省了计算时间。另外,遗传算法尽量使优化程度高的解参与计算,从而保证近似最优解的优化程度。本文采用遗传算法对某企业11个部门进行了布置设计。需要指出的是,该方法及程序完全可以应用到大规模的布置设计中,而且规模越大,越可以反映出该方法的效率。仅以目标函数计算次数为例,如果固定遗传算法参数不变,n !/(P 3maxgen )将随着n 的增长而快速增大。这证明设施个数越多,遗传算法的计算效率越高。尽管设施个数的增大导致解空间变大,可能减弱求解精度,但是通过调整交叉率与编译率能够有效地弥补这一缺陷。因此基于遗传算法的TH 2C AFP 具有很强的实际应用性。5结论采用遗传算法编制了计算机辅助布置设计软件TH 2C AFP 的核心模块,并通过算例计算,说明了这种方法的计算效率及精度。Industrial Engineering and Management N o.4,2002工业工程与管理2002年第4期参考文献:1T avakkoli2M oghaddain R,Shayan E.Facility Lay out Design by G eneticAlg orithmsJ.C om puters and Industrial Engineering,1998,35:527530.2G ero J S,K azav ov V A.Ev olving Design G enes in S pace Lay out Plan2ning ProblemsJ.Artificial Intelligence in Engineering,1998,(12): 163-176.3玄光男(日),程润伟.遗传算法与工程设计M.汪定伟,唐加福,黄敏译.北京:科学出版社,2000.符合WT O规则的保护对策 熟悉并灵活运用WT O规则,维护国家及企业利益,是我国政府和企业界在“入世”后的过渡期乃至更远的将来需要认真研究的问题。 1.发展中国家适用的条款WT O允许发展中国家为保护民族工业和本国经济利益而使用保护措施,概括起来为以下3条:(1)关于保护幼稚工业的条款。WT O允许发展中国家为了加速某一特定产业的建立,即保护幼稚产业,在与缔约国和其他利害相关的缔约国达成协议的基础上,可以修改和撤销关税减让表中的关税减让。也就是说,即使列入关税减让表的关税仍然可以提高(修改和撤销)。同时,若提高关税后仍然不能满足经济发展需要,该国还可采取数量限制等措施。根据“东京回合”的决定,若拖延采取措施时会对执行其经济发展计划和政策造成困难,该提出申请的进口缔约国可以在通知缔约国全体后立即临时修改或撤销有关关税减让。这一决定增加了发展中国家使用关税措施的弹性,无需缔约国全体事先同意,而在采取行动后进行谈判。(2)关于维护国际收支的条款。WT O允许发展中国家在面临国际收支困难时,采取限制进口商品数量或价值的办法来控制它的一般水平。在一定条件下可以在歧视性限制基础上实施。也就是说,发展中国家可以针对不同进口产品确定不同的限制方式,并可按其经济发展政策的需要优先进口急需的产品。这一规定使符合条件的国家在制订进口配额措施时,可以更有针对性,而不受世贸组织无歧视原则的约束。(3)关于进口保障的条款。WT O允许缔约国对特定进口产品采取紧急限制行动,前提是产品进口数量激增,给国内生产者造成严重损害和威胁。保障行动可以采取关税措施,也可以采取非关税措施。该条款同样规定,若拖延采取措施会造成难以弥补的损害,该国可以先行动后谈判。值得一提的是,该条款并未规定如何确定损害和如何进行确定损害的调查;也未就“国内生产者”下定义,进口国可以根据自己的标准来确定国内生产者的范围。因而,援引该条款具有更强的灵活性。以上3条保护条款是对发展中国家的一种优惠,我国应加以充分利用,它可以缓减“入世”过渡期外国企业给我国企业带来的强大冲击,并为我国经济体制改革、产业结构调整提供一个缓冲的机会。2.关于反倾销与反补贴反倾销与反补贴是WT O赋予组织成员保护自己市场的重要手段,其中反倾销是各国采用最多的手段。中国产品在国外遭到的第一例反倾销调查为1979年8月,中国出口欧洲的糖精钠遭到当时欧共体的反倾销调查,迄今为止,中国产品已遭到来自29个国家和地区的400多起、涉及4000多种商品的反倾销调查,位居全球之首。我国企业之所以在国际反倾销诉讼中长期处于被动地位,一方面因为我国很多出口产品属于劳动密集型产品,在与发达国家的同类产品的竞争中处于明显有利地位,导致欧美等发达国家的贸易逆差不断上升;另一方面因为我国以前一直被挡在世贸组织的大门外,被一些国家视为“非市场经济国家”,因此企业的生产成本往往不被考虑。“入世”后,由于关税与非关税壁垒的削弱,我国企业面对的反倾销诉讼会进一步增多。因此我国企业一定要在遭遇反倾销指控时积极应诉,捍卫自己的合法权益和正当市场。因为外国对我国某种产品倾销的指控一旦认定,则所有来自中国的同一产品将被征收同样的高额反倾销税,最终将导致我国企业自动放弃该国市场的严重后果。对于中国企业来说,应密切注意在国内市场销售的同类外国产品的商情,一旦发现有倾销或补贴嫌疑,应配合本行业和有关主管部门采取必要的反倾销或反补贴措施,以维护自己的合法权益。3.关于技术性贸易政策技术性贸易政策是指商品进口国在实施贸易进口管制时,通过颁布法律、法令、条例、规定、建立技术标准、认证制度、卫生检验检疫制度等,提高对进口产品的技术要求,增加进口难度,以保障国家安全、保护消费者利益,最终保持国际收支平衡。WT O承认技术性壁垒存在的合理性和必要性,只是要求技术壁垒不要妨碍正常的国际贸易,不得具有歧视性。20世纪90年代以来发达国家不断提高进口产品的环保标准。1992年5月欧共体正式实施所谓“生态标签”制度,1993年7月正式推出欧洲环境标志,1995年4月,由发达国家控制的国际标准化组织开始实施国际环境标准监察制度。这些“绿色壁垒”曾影响到我国产品出口。发达国家的技术壁垒,有的带有明显的歧视性,这是我们所不能接受的,也是违反WT O规则的。但是也应看到我国出口产品的品质、技术标准与国际市场要求之间的差距。因此,只有加强管理、提高质量,同时掌握国外市场的标准要求,加快我国产品的标准化建设才能不授人以柄;同时,我国政府和企业应密切配合,加强这方面的研究,做到既不违反WT O规定,又能有效地保护和促进我国的工业发展。在这方面,可以借鉴发达国家和其他发展中国家的经验。例如,为了限制英法联合研制的协和号超音速客机的进口,美国测定协和号客机进场噪音达到119.5分贝以上,超过了美国民航机噪音标准的规定而不允许该机在美国领土上降落,从而阻止了协和号客机进入美国航空市场。4.关于知识产权协议WT O与贸易有关的知识产权协议(简称TRIPS协议)规定,发展中国家和由计划经济向市场经济过渡的国家“入世”后,在执行该协议时允许有5年的过渡期。我国在1997年,为了促进加入世贸谈判的进展,已经宣布放弃过渡期的优惠。也就是说,中国在加入世贸组织的同时,就必须完全执行TRIPS协议。中国已经修定了专利法、商标法和著作权法。在立法方面,中国已经基本符合该协议的要求。但是,在知识产仅的实施方面,我国还面临许多问题,它不仅涉及到立法、行政和司法,还涉及全民族的知识产权意识。“入世”后,西方发达国家可能会以中国没有认真完全地执行TRIPS协议为由,发起世贸组织争端解决程序,甚至以诉诸贸易制裁相威协。对此,应予以高度重视。(江苏省盐城市外经贸委金宁)王昕岩等:采用遗传算法进行车间平面布置