第14章布局设计的现代算法

1、第十四章第十四章 布局设计的现代算法布局设计的现代算法14.1布局设计的数学建模求解算法 目前计算机布置算法可分为两类。一类是对布局设计问题简化并建立数学模型，再采用计算机现代算法求解的方法，称为数学建模求解算法。这类方法不能得出布局设计图，需要设计人员根据算出的数据，构思布局设计，然后再在图形绘制工具中绘制布局图。另一类是用计算机算法直接对布局图进行优化求解，最后得出优化的布局设计图， 14.1.1设施布局问题数学模型设施布局问题数学模型1单行布置的模型 首先要做如下假设，假设机器的形状是方形，机器排成一列，机器的方位是预先确定的。如图14-1所示。设有n台机器排成一列，要确定各机器的位置坐

2、标，使机器间运送物料的成本最低。 图14-1 单行布置示意图2多行布置的模型图14-2 多行布置示意图3二次分派问题模型 给定n个地点，现要把n个设施分配到这n个地点，这实际上是组合问题，共有n！种方案，在这n！种方案里找最佳方案使总的物料搬运费用最短。如果n等于4，则共有24种方案，显然可以用穷举发来求最优方案，如果n等于10，则有3628800种方案，如果n大于10，方案会更多，显然没有办法穷举，往往通过一些启发式算法寻找次优方案。 11niikx11nkikx11njjhx11nhjhxjhikninknjnhkhxxdxf1111ijijfc21)(min14.1.2遗传算法在布局设计

3、中的应用遗传算法在布局设计中的应用1遗传算法的结构遗传算法的结构 遗传算法开始时先随机地产生一些染色体（欲求解问题的侯选解），计算其适应度，根据适应度对诸染色体进行选择、交换、变异等遗传操作，剔除适应度低的染色体，从而得到新的群体。由于新群体的成员是上一代群体的优秀者，继承了上一代的优良性态，因而在总体上优于上一代。就这样反复迭代，向着更优解的方向进化，直至满足某种预定的优化指标。(1)编码与译码 许多应用问题结构很复杂，但可以化为简单的位串形式编码表示，我们将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫译码。我们把位串形式编码表示叫染色体，有时

4、也叫个体。 (2)适应度函数 为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。通过适应度函数来决定染色体的优、劣程度，它体现了自然进化中的优利劣汰原则。对优化问题，适应度函数就是目标函数。(3)遗传操作 简单遗传算法的遗传操作主要有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。 选择操作也叫复制操作，根据个体的适应度函数值所度量的优、劣程度决定它在下一代是被淘汰还是被遗传。一般地说，选择将使适应度较大(优良)个体有较大的存在机会，而适应度较小（低劣）的个体继续存

5、在的机会也较小。 交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。图 14-3 交叉前示意图 图 14-4 交叉后示意图 变异操作的简单方式是改变数码串的某个位置上的数码。我们先以最简单的二进制编码表示方式来说明. 图14-5 变异示意图(4)控制参数 并不是所有被选择了的染色体都要进行交叉操作和变异操作，而是以一定的概率进行，交叉概率 种群的染色体总数叫种群规模， 另一个控制参数是个体的长度2. 遗传算法应用举例(1) 问题的描述 假设有九台设备M1M9，在某个生产阶段设备之间的物流矩阵(实际上就是从至表)如图所示。现需要将这九台进行布置，使其运输工

6、具的总行程最小。假设由于场地的限制，设备需要分成三行来排列，且各生产设备之间距离相等为单位1 图14-6 设备之间的物流矩阵(2)遗传算法的设计 编码方法：这里使用浮点数编码方法，用设备的位置向量表示染色体 适应度函数： maxmaxmax)(0)()()(CxfCxfxfCxF 初始群体的产生：以随机的方式将这九台设备进行排列，共得到M种设备布局形式。 选择算子：这里使用比例选择算子，即个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。 交叉算子：将群体中M个个体以随机的方式两两配对，组成M/2对配对个体组。每对配对个体组随机选择其中之一为Parent1，则另外一个个体为Par

7、ent2。 变异算子：随机地选取个体中两个基因座，交换它们的基因，产生新个体。图14-7 交叉算子示意图(3)运算结果 在该算法中，采用保留最佳个体策略，加快了收敛速度，并且取得较优的解。计算出最优布局为(2，4，1，6，3，5，8，7，9)。在此布局下，目标函数值为2530，而最劣布局的目标函数值为3653。14.1.3 模拟退火算法在布局设计中的应用模拟退火算法在布局设计中的应用 1模拟退火算法流程(1) 随机产生一个初始解，计算目标函数值;(2) 设置初始温度 (3) 当 时，对应某个具体的温度T，重复执行步骤（4）K次。 minTT (4) 对当前最优解按照某一邻域函数，产生一新的解。

8、计算 新的目标函数值，并计算目标函数值的增量，根据增量的正负，确定最优解。(5) 步骤（4）完成k次重复后，令 ，若 执行步骤（6），若 ，回到步骤3。(6) 输出当前最优解，计算结束。newTT minTT minTT 2模拟退火算法的简单应用 考虑遗传算法部分的例题，用模拟退火算法求解，要点如下： 解空间S是所有布局方案的集合，S中的成员记为： ，其中为第k台机器所在的地点。初始解可选为(1，n)。 此时的目标函数即为运输工具的总行程 ),(21nkwwwwninjjiijdqwf11)(若km，则将 变为：),(121nmkkwwwwww),(1121nkkmmwwwwwww),(112

9、1nkkmmwwwwwww),(11111knnkmmmwwwwwwww3模拟退火算法的参数控制问题 (1) 温度T的初始值设置问题。 温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。 (2) 退火速度问题。 模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。 (3)

10、 冷却进度表T(t)。 冷却进度表是指从某一高温状态To向低温状态冷却时的降温管理表。假设时刻t的温度用T(t)来表示，则经典模拟退火算法的降温方式为： 而快速模拟退火算法的降温方式为： )1lg()(0tTtTtTtT1)(014.2 布置图的设计算法14.2.1 布置图设计算法的分类与原理布置图设计算法的分类与原理1算法的输人数据类型 布置算法可以按照它们所需的输人数据类型分类。有些算法只接受像相关图之类定性的“物流”数据，而有些接受由从至表表示的定量物流数据；还有一些算法同时接受相关图和从至表两种数据（如BLOCPLAN），但是在评价布置方案时只能选择这两种数据中的一种。现在的算法更趋向

11、于采用从至表数据， 2基于“量距积的和最小”为目标的算法 首先考虑基于距离的目标，设m为部门数， 为从部门i到部门j的物流量； 为将一个单元的物料从部门i移动到部门j单位距离的成本。于是目标函数是要使单位时间内部门间物料的移动总成本最小化 ijfijcijijmimjijdcfZ11min3基于相近程度目标函数的算法 考虑基于相近程度的目标函数，其中相近程度的分值是按布置中所有相邻两个部门物流量值的总和来计算的。如果部门i和j相邻就令 1，否则； 0，目标是求相邻值最大 ijxijxijmimjijxfZ11max 但如果要评价一个特定布置在某个上下边界的相对效率（相对优劣）时，设施规划人员可

12、采用以下“归一化”的相邻值。mimjijmimjijijfxfZ1111 如果采用 “负流量”值。归一化的相邻值计算公式修改如下FjiFjiijijFjiFjiijijijijffxfxfZ),(),(),(),()1 (14.2.2 CRAFT算法算法1.CRAFT算法的初始条件 CRAFT 是一种改进型布置算法，所以先要给它一定的基础，如从一个已有设施的实际布置或由另一种算法给出的初始布置开始，先确定初始布置中各部门的矩心，然后计算两两部门距心之间直角距离，并存储在距离矩阵之中。 2.CRAFT算法的迭代过程 在程序考虑部门i和j的位置交换时，不是实际交换它们的位置再来计算新的矩心和布置成

13、本，而是临时互换当前布置中部门i和部门j的矩心数据来估算布置成本。在按估算的布置成本找到最佳交换后，CRAFT程序再交换两者的位置并计算它们新的矩心后才开始下一步迭代。3.迭代结果依赖于路径 在搜索更好结果时，CRAFT只是从每次迭代中选择最好的交换方式，这是一种最速下降法。在上述的搜索过程中，它既不瞻前也不顾后。因此，CRAFT搜索时会在第一次碰到二相或三相最佳方案时就予以终结，这样的结果很可能只是局部最优解。 4.CRAFT用于非矩形厂房的策略 CRAFT一般仅限用于矩形厂房，但通过引人“虚”部门它也可以用于非矩形厂房。虚部门与其他部门没有任何物流或相互作用，但要由布置规划人员指定它的面积

14、。 一般来说，虚部门主要用于：填补建筑物的不规则之处；代表一设施内的障碍或不能用的区域（如楼梯、电梯、厂房维护区等）；代表厂房的额外空间；在最终布置中用于帮助通道位置的确定。5.CRAFT布置的修改 CRAFT的优点之一是能以合理的精确度找到初始布置。 这主要是因为CRAFT能在非矩形建筑物内的任何地方容纳矩形的部门或障碍。但是除了高度依赖路径外，CRAFT的缺点是产生的最终布置很少有部门形状是规则的，也少有直线形的且不中断的通道。 14.2.3 CRAFT算法案例算法案例1从至表2计算它们矩心间的直角距离 CRAFT首先计算图14-8所示各部门的矩心。然后对每一个部门单位对计算它们矩心间的直

15、角距离，并乘上从至表中相应的数据。例如部门A和B距心间直角距离为6格，CRAFT就以6乘以45，并将结果加到目标函数值中。对所有非零流的部门单位对，重复上述过程，得到初始布置的成本为2974单位（这里CRAFT按方格数来计算，如果按英尺计算，实际布置成本为29742059480单位）。图14-8初始CRAFT布置及各部门的矩心3迭代与交换 随后，CRAFT进行第一次迭代，交换部门E和F的位置所得布置如图14-9所示。部门E和F面积并不相等，但位置相邻，因此想像用一个框架将E和F框起来，不包括其他部门（如果E和F不相邻就找不到这样的框子）。CRAFT就在这个框架里交换E和F的位置。 图14-9交

16、换部门E和F的位置所得布置 下一次迭代时，估算的布置成本降低值是95单位，CRAET交换部门B和C的位置后的结果如图14-10所示。该布置成本为2833.50单位，实际降低119.50单位。这清楚地说明估算的误差在每一个方向都有。 图14-10交换B、C位置所得布置图14-11修改打磨后所得的布置4. 布置的修改 在打磨布置时，分析人员一般不采用网格，而采用连续式表现方式，这样就可以平滑部门边界并在必要时稍微修改部门的面积和取向。对图14.10所示的布置打磨后，所得的布置如图14.11所示。 5相邻不是交换的充分条件 前面的短评中提到对两个面积不等的部门，相邻是不影响其他部门进行位置交换的必要

17、而非充分条件。显然，相邻是必要的，否则就不可能这样交换，但相邻并不是充分条件，可以由下例说明。 图14-12部门2和4不能交换 6三相交换 三相交换所需的条件比较复杂。假设部门i，j和k要进行三相交换，如部门i换j，部门j换k，部门k换i。如果能用一个框架将部门i，j和k框起来，而不含其他部门，那么（除了上述部门2和4的情况），可以进行三相交换而不影响其他部门。注意要找到这样的框架，三个部门中的每个部门井不一定都要和其他两个共边。例如部门i和j相邻（但不与k相邻），或者部门k与j相邻（但不与i相邻）时都可以找到这样的框架。14.2.4 MCRAFT算法案例算法案例 MICRO-CRAFT（或简称MCRAFT ）类似于CRAFT，只是上述约束放松了（即MCRAFT可以不管两个部门是否相邻就进行换位）。 考虑