第14章布局设计的现代算法知识讲稿.pptVIP

第十四章 布局设计的现代算法;14.1布局设计的数学建模求解算法 目前计算机布置算法可分为两类。一类是对布局设计问题简化并建立数学模型，再采用计算机现代算法求解的方法，称为数学建模求解算法。这类方法不能得出布局设计图，需要设计人员根据算出的数据，构思布局设计，然后再在图形绘制工具中绘制布局图。另一类是用计算机算法直接对布局图进行优化求解，最后得出优化的布局设计图， ; 14.1.1设施布局问题数学模型 1．单行布置的模型 首先要做如下假设，假设机器的形状是方形，机器排成一列，机器的方位是预先确定的。如图14-1所示。设有n台机器排成一列，要确定各机器的位置坐标，使机器间运送物料的成本最低。; 图14-1 单行布置示意图;2．多行布置的模型;;3．二次分派问题模型 给定n个地点，现要把n个设施分配到这n个地点，这实际上是组合问题，共有n！种方案，在这n！种方案里找最佳方案使总的物料搬运费用最短。如果n等于4，则共有24种方案，显然可以用穷举发来求最优方案，如果n等于10，则有3628800种方案，如果n大于10，方案会更多，显然没有办法穷举，往往通过一些启发式算法寻找次优方案。 ;;(1)编码与译码 许多应用问题结构很复杂，但可以化为简单的位串形式编码表示，我们将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫译码。我们把位串形式编码表示叫染色体，有时也叫个体。 (2)适应度函数 为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。通过适应度函数来决定染色体的优、劣程度，它体现了自然进化中的优利劣汰原则。对优化问题，适应度函数就是目标函数。 ;(3)遗传操作 简单遗传算法的遗传操作主要有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。 选择操作也叫复制操作，根据个体的适应度函数值所度量的优、劣程度决定它在下一代是被淘汰还是被遗传。一般地说，选择将使适应度较大(优良)个体有较大的存在机会，而适应度较小（??劣）的个体继续存在的机会也较小。 ; 交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。; 变异操作的简单方式是改变数码串的某个位置上的数码。我们先以最简单的二进制编码表示方式来说明. ;(4)控制参数 并不是所有被选择了的染色体都要进行交叉操作和变异操作，而是以一定的概率进行，交叉概率 种群的染色体总数叫种群规模， 另一个控制参数是个体的长度;2. 遗传算法应用举例 问题的描述 假设有九台设备M1～M9，在某个生产阶段设备之间的物流矩阵(实际上就是从至表)如图所示。现需要将这九台进行布置，使其运输工具的总行程最小。假设由于场地的限制，设备需要分成三行来排列，且各生产设备之间距离相等为单位1 ;图14-6 设备之间的物流矩阵;(2)遗传算法的设计 编码方法：这里使用浮点数编码方法，用设备的位置向量表示染色体 适应度函数： ; 初始群体的产生：以随机的方式将这九台设备进行排列，共得到M种设备布局形式。 选择算子：这里使用比例选择算子，即个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。 交叉算子：将群体中M个个体以随机的方式两两配对，组成M/2对配对个体组。每对配对个体组随机选择其中之一为Parent1，则另外一个个体为Parent2。 变异算子：随机地选取个体中两个基因座，交换它们的基因，产生新个体。;图14-7 交叉算子示意图;(3)运算结果 在该算法中，采用保留最佳个体策略，加快了收敛速度，并且取得较优的解。计算出最优布局为(2，4，1，6，3，5，8，7，9)。在此布局下，目标函数值为2530，而最劣布局的目标函数值为3653。;14.1.3 模拟退火算法在布局设计中的应用 1．模拟退火算法流程 随机产生一个初始解，计算目标函数值; (2) 设置初始温度 (3) 当 时，对应某个具体的温度T，重复执行步骤（4）K次。 ;(4) 对当前最优解按照某一邻域函数，产生一新的解。计算 新的目标函数值，并计算目标函数值的增量，根据增量的正负，确定最优解。 (5) 步骤（4）完成k次重复后，令 ，若 执行步骤（6），若 ，回到步骤3。 (6) 输出当前最优解，计算结束。;2．