D-14-西南财经大学.ppt

,打孔机最优作业方案,队员： 廖蔚中 耿玉龙 叶倩倩 指导老师：戴岱,Copyright 2012 SWUFE. All rights reserved.,Page2,总体简介,本文以题中提供的某块印刷线路板过孔中心坐标的数据为基础，收集相关资料，研究打孔机作业的相关关系，通过对孔的技术性处理，最终建立了类似于TSP的模型，我们将孔按所需的刀具类型分群，并制定了钻头等待-规避策略与双钻头任务均衡的方法，结合蚁群算法很好的解决了单钻头与双钻头的最优作业问题。,Copyright 2012 SWUFE. All rights reserved.,Page3,基本假设,1.单个过孔的钻孔作业时间是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业时间都是相同的，过孔费用不计。 2. 钻头的行进速度是相同的，为180 mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min 3. 刀具在行进过程中可以同时进行刀具转换，但相应费用不减。 4. 一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。,Copyright 2012 SWUFE. All rights reserved.,Page4,基本假设,打孔机连续作业 （打孔机的连续作业即是把所有的孔按相应的刀具要求、顺序要求打一遍，最终回到出发点，形成生产线作业） 6. 把需要多种刀具加工的单个孔技术性地看作多个分别需要一种刀具加工的孔 （例如：孔型C需要刀具a和刀具c，且加工次序为a、c，于是我们将这一个孔看作两个孔，它们分别需要刀具a和c，并且打孔顺序按原来的要求） 7. 题目所给数据真实可靠,Copyright 2012 SWUFE. All rights reserved.,Page5,单钻头打孔机模型的建立,赋权联通图的构造 首先我们把需要多种刀具加工的孔分解成若干个只需要一种刀具加工的孔。这样我们便得到了2814个孔，它们作为图中的点，组成的集合记为点集V(G) 。点集 V(G)中任意两点之间的连线记为边 。点集中所有点两两之间的连线构成边集 V(E)。然后用点集 V(G)与边集V(E) 一起构成混合图G(E,V) 。最后我们对混合图 的每一条边进行相应的赋权就得到了赋权连通图 G(E,V)。其中，边权对应边的相应的费用（或时间）。,Copyright 2012 SWUFE. All rights reserved.,Page6,孔型分布图,Copyright 2012 SWUFE. All rights reserved.,Page7,权数的确定,Copyright 2012 SWUFE. All rights reserved.,Page8,在成本最优下，我们的目标是使印刷单个电路板的费用尽可能的小。即 每条边的权数为：,在时间最优的情况下，我们的目标是使印刷单个电路板的时间尽可能的小。即每条边的权数为：,权数的确定,Copyright 2012 SWUFE. All rights reserved.,Page9,单钻头打孔机的模型,Copyright 2012 SWUFE. All rights reserved.,Page10,模型求解算法选择分析,由于我们面对的问题的数据规模特别大（有多达2814个点）无法直接求出最优解，只能利用启发式算法。蚁群算法具有以下的特点： 1)采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解。 2)每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知 周围环境的实时变化，个体间通过环境进行间接的通讯。 3)搜索过程采用分布式计算方式，多个个体同时进行并行计算，大大提高了算法的运行效率。 4)启发式的概率搜索方式不容易陷入局部最优，易于寻找到全局最优解。 所以我们使用了人工蚁群算法来搜索一个逼近全局最优解的解。,模型求解算法选择分析,Copyright 2012 SWUFE. All rights reserved.,Page11,从实际运行效果来看，对于以 题目中数据所给的第一个孔为初始点，用三种算法求解，结果如下表所示，可以清晰的看到蚁群算法的优势。,Copyright 2012 SWUFE. All rights reserved.,Page12,模型求解蚁群算法描述,在使用蚁群算法求解现实问题时，先生成具有一定数量蚂蚁的蚁群，让每一只蚂蚁建立一个解或解的一部分，每只人工蚁从问题的初始状态出发，根据“激素”浓度来选择下一个要转移到的状态，直到建立起一个解，每只蚂蚁根据所找到的解的好坏程度在所经过的状态上释放与解的质量成正比例的“激素”。之后，每只蚂蚁又开始新的求解过程，直到寻找到满意解。为避免停滞现象，引入了激素更新机制。 算法步骤如下： 步骤一:初始化 ,各边的信息素浓度初始化。 步骤二:将 m个蚂蚁置于初始顶点上。 步骤三:按顺序选定一只蚂蚁；若已经选完所有的蚂蚁则转步骤七,Copyright 2012 SWUFE. All rights reserved.,Page13,模型求解蚁群算法描述,步骤四：筛选出这只蚂蚁从当前位置出发允许到达的点（去掉已经走过的点和刀 具加工顺序有冲突的点） 步骤五：蚂蚁根据连接当前点 与剩下点 之间的边 的信息素的浓度 计算出转移概率 。对于其他的点，令概率为零 。然后依据随机生成的概率来选择一个点作为下一个点。 步骤六：重复步骤四直到蚂蚁走过所有的点，否则转入下一只蚂蚁，进入步骤三 步骤七：让当前所有边上的信息素浓度进行衰减。 步骤八：每一只蚂蚁行走时分泌信息素，它会增加它所经过的每一条边的信息素浓度 步骤九: 进入下一阶段的迭代运算，若迭代次数达到最大迭代次数则算法结束。,Copyright 2012 SWUFE. All rights reserved.,Page14,模型求解蚁群算法流程图,Copyright 2012 SWUFE. All rights reserved.,Page15,两种目标下的求解结果分析,时间最优下刀具转换方案的优化,Copyright 2012 SWUFE. All rights reserved.,Page16,由上面分析，我们以总时间最优为目标，与此同时可以发现，钻头更换刀具的时间(252秒)已经大大超过了82秒的钻头行径的时间，所以，为了进一步的减少时间，我们必须减少刀具转换的次数。 由于不同孔型对刀具加工的次序要求，通过我们技术性处理之后的模型也仅仅是类似于TSP问题，次序的要求使得个别的点点之间的连接是有向的，于是模型并非TSP问题，而是类似。所以从不同的起始位置打孔，各自最终求解出来，对模型的结果是有影响的，所以需要进一步优化。 再者，从蚁群算法的角度，对于非线性问题，初始值的改变对最终的结果也将带来影响。,Copyright 2012 SWUFE. All rights reserved.,Page17,时间最优下刀具转换方案的优化,刀具转换方案的约束条件： 1）首先钻头上的刀具只能向邻近位转移 2）其次我们有8种刀具的加工需求，所以 每一种刀具类型都必须钻动过,Copyright 2012 SWUFE. All rights reserved.,Page18,刀具转换方案的约束条件,3）另外我们还需要保证加工次序。由于我们把孔按所需刀具类型分成了10种（包括a,b,d,e,f,g；c与f则分为优先打的c0 与f0和需要最后打的c1与f1）即我们必须保证如下次序： 打c1型前必须打a ,f0 ,e 打f1 型前必须打c0 g 打g型前必须打 d,Copyright 2012 SWUFE. All rights reserved.,Page19,分群示意图,Copyright 2012 SWUFE. All rights reserved.,Page20,分群示意图,Copyright 2012 SWUFE. All rights reserved.,Page21,分群示意图,Copyright 2012 SWUFE. All rights reserved.,Page22,分群示意图,Copyright 2012 SWUFE. All rights reserved.,Page23,分群示意图,Copyright 2012 SWUFE. All rights reserved.,Page24,算法描述,我们采用了遍历法来寻找合适的刀具转换方案 步骤一：初始化一条链 L 如 链 的长度 为8 步骤二：依次选取链 中的点 i作为起点， 步骤三：复位，给钻头1的转换方案末尾添加一个 j（ 为钻头2转换方案的起点），并也在钻头1的转换方案末尾添加一个 i。 步骤四：检验上述方案是否符合打孔次序的要求，并回到步骤二。如果将 中的点选完仍然找不到可行解，则转到步骤五。,Copyright 2012 SWUFE. All rights reserved.,Page25,算法描述,Copyright 2012 SWUFE. All rights reserved.,Page26,求解结果,我们最终得到了2个最优解： 方案一: 方案二： 进一步我们用上面求得的刀具转化方案得到了最优路线,Copyright 2012 SWUFE. All rights reserved.,Page27,最优路线的确定,首先我们根据每个孔所需要的刀具的类型和对加工次序的要求，我们把所有的孔分成了10种群： a b c0 c1 d e f0 f1 g h c0/f0为要求优先打的c型/f型孔 c1/f1为要求稍后打的c1型/f1型孔 其次我们根据刀具的转换方案，把加工这十种孔的任务分配到了钻头每一个阶段。 再其次我们用了蚁群算法求出了10种孔群的最佳打孔线路。（算法思路同第一问，在此就不再赘述） 最后我们用程序根据刀具的转换方案寻找到了一个最佳方案把这几个阶段连接起来。,Copyright 2012 SWUFE. All rights reserved.,Page28,算法描述,我们使用了等步长搜索法来解决这个问题： 步骤一：由蚁群算法求出最小Hamilton圈（通过图中的边能经过途中的顶点。 边可以重复走，但点只能经过一次。 步骤二：依次从c1群选择一个点作为起点，同时它在Hamilton圈上的邻点为终点。若选遍所有点，则算法结束。 步骤三：依次从c0群选择选择一个点作为起点，同时它在Hamilton圈上的邻点为终点。若选遍所有点，则转到步骤二。 步骤四：连接c1的终点与c0的起点，并以此连接这两个Hamilton圈。去掉连接c1的起点与终点的那条边与连接c0的起点与终点的那条边。 步骤五：且计算这条依次从c1起点连接到c0终点的边的长度，若这个长度短于当前最优解，则记录。转到步骤三。,Copyright 2012 SWUFE. All rights reserved.,Page29,算法描述,上一步中我们就得到的整个过程的起点与终点，我们用下面的算法把中间各个阶段的任务连接起来。 步骤一：由蚁群算法求出中间各个阶段的最小Hamilton圈，并删掉最长边，由此得一条弧。 步骤二：分别以每一条弧的两个端点中的任意一个作为起点，另一个作为终点。并且按加工顺序连接所有的弧。得到一个新的圈。 步骤三：计算这个圈的长度，若小于最优解就记录下来，找遍了步骤二中的所有情况则算法结束。,Copyright 2012 SWUFE. All rights reserved.,Page30,模型结果,最优刀具转换方案为： 方案二：,Copyright 2012 SWUFE. All rights reserved.,Page31,单钻头行进路线,Copyright 2012 SWUFE. All rights reserved.,Page32,双钻头打孔机模型的建立,赋权联通图的构造 首先我们把需要多种刀具加工的孔分解成若干个只需要一种刀具加工的孔。这样我们便得到了2814个孔，它们作为图中的点，组成的集合记为点集V(G) 。点集 V(G)中任意两点之间的连线记为边 。点集中所有点两两之间的连线构成边集 V(E)。然后用点集 V(G)与边集V(E) 一起构成混合图G(E,V) 。最后我们对混合图 的每一条边进行相应的赋权就得到了赋权连通图 G(E,V)。其中，边权对应边的相应的费用（或时间）。,Copyright 2012 SWUFE. All rights reserved.,Page33,权数的确定,Copyright 2012 SWUFE. All rights reserved.,Page34,双钻头打孔机模型,由于钻头数由一个增加到了两个，故问题从类似于TSP问题变成了一个类似于MTSP（多旅行商）的问题。首先我们需要把点集 V分成两个部分V1 与V2 分别交由两个钻头去打。对应点集然 与 我们分别构造出对应的边集 G1与G2 。后分别求出连接这两部分点集的最小哈密顿圈 与 。,其中 ， 为 中的顶点数 其中 ， 为 中的顶点数,Copyright 2012 SWUFE. All rights reserved.,Page35,双钻头打孔机模型,由于最终完成一个印刷电路板的总时间即为两个钻头中的用时较大的时间，我们的目标就是使两个钻头中的用时较大的时间尽可能地小。所以最后我们需要平衡两个钻头的工作量，要使得他们的工作量尽量平均化：,钻头一工作总时间 其中 钻头二工作总时间 其中,与此同时我们还需要满足双钻头的最小合作间距的要求。若两个钻头在任意时刻的位置为 与 ，那么有：,最终总时间为 我们的目标是 即,Copyright 2012 SWUFE. All rights reserved.,Page36,模型求解,双钻头情况下的最优刀具转换方案,第一，以时间最优为目标进行处理时，我们可以发现，转换一次刀具耗时18s，而18s钻头可以行进324cm ，已经远远超出印刷电路板上最远的两点之间的距离，所以只有当钻头完成一种孔型的任务后，才回去转换刀具。 第二，我们只有8种刀具，在孔数量庞大的情况下，大多数情况下所有的刀具都会被使用，以时间最优为目标的情况下，在以所需刀具为分类依据的孔群内钻头的行进时间是一定的，为了减少总时间，刀具更换应该是依序逐个转换的。示意如右图：,Copyright 2012 SWUFE. All rights reserved.,Page37,双钻头情况下的最优刀具转换方案,此外，我们要求两个钻头完成作业后，可以相互回到对方的初始位置与初始状态，以此保证连续作业与尽可少的刀具转换。示意图如下： 整个过程钻头1：由a转到e 整个过程钻头2：由e转到a,Copyright 2012 SWUFE. All rights reserved.,Page38,双钻头情况下的最优刀具转换方案,另外我们还需要保证加工次序。由于我们把孔按所需刀具类型分成了10种（包括a,b,d,e,f,g；c与f则分为优先打的c0 与f0和需要最后打的c1与f1）即我们必须保证如下次序： 1）打c1型前必须打a ,f0 ,e 2）打f1 型前必须打c0 g 3）打g型前必须打 d,Copyright 2012 SWUFE. All rights reserved.,Page39,算法描述,我们采用了遍历法来寻找合适的刀具转换方案 步骤一：初始化一条链 L 如 链的长度为8 步骤二：依次选取链中的点 i作为起点， 步骤三：复位，给钻头1的转换方案末尾添加一个 j（ 为钻头2转换方案的起点），并也在钻头1的转换方案末尾添加一个 i。 步骤四：检验上述方案是否符合打孔次序的要求，并回到步骤二。如果将链中的点选完仍然找不到可行解，则转到步骤五。 步骤五: 加边，依次在链 上按序取三点 I j k ，并在k 与j之间插入 I j 或k j 即i j I j k 或 I j k j k 作为新的链。转入步骤二，若 选遍了 中所有的点，算法结束,Copyright 2012 SWUFE. All rights reserved.,Page40,平衡任务量,最终完成一个印刷电路板的总时间即为两个钻头中的用时较大的时间，我们的目标就是使两个钻头中的用时较大的时间尽可能地小。所以我们要平衡两个钻头的任务量。 步骤一：我们首先使用了蚁群算法求出了10种孔群的最佳打孔线路，（算法思路同第一问，在此就不再赘述）并将每种孔群的作业时间作为任务量。 步骤二：从可行解里面依次选取一个方案，然后根据两钻头的刀具转换方案将这打10种孔群的任务分配到对应的钻头上。若选完了所有的方案则转步骤四 步骤三：计算出两个钻头的总作业时间，并且以作业时间长的那个钻头的时间作为这个方案的总作业时间。转步骤二 步骤四：选取总作业时间最少的那个方案作为最终的刀具转换方案。,Copyright 2012 SWUFE. All rights reserved.,Page41,求解结果,最优的刀具转换方案：,Copyright 2012 SWUFE. All rights reserved.,Page42,双钻头的合作作业的间距的调整策略,为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。上述不考虑合作间距的基础模型的结果已经将两个钻头的任务分配完毕，作业路线也已经确定，考虑间距后我们使一个钻头作为优先钻头，另一个钻头采取一定的策略来保证间距。 对于间距的处理采用等待与规避两种策略。以下以钻头1作为优先钻头为例进行说明。,Copyright 2012 SWUFE. All rights reserved.,Page43,等待策略,如果钻头1下一个的目标位置的以合作间距d为半径的圆内存在钻头2，那么钻头1将原地等待，直到目标的判断区域内没有钻头2，再行进到目标位置。,Copyright 2012 SWUFE. All rights reserved.,Page44,规避策略,如果判断到钻头2与钻头1距离为合作间距d时，钻头2就沿着两者连线相应的后退，直到判断距离大于d时，继续前往目标点。,Copyright 2012 SWUFE. All rights reserved.,Page45,算法描述,采用等时间步长法来计算总的作业时间，时间步长为0.001秒 步骤一：根据钻头1（优先钻头）的作业路线记录钻头1的每个时间所处的位置。 步骤二：初始化时间T，让钻头2开始按所给的任务进行作业，并将路线上第二个点作为目标点，转入步骤三 步骤三：若两钻头的距离d小于最小合作间距d0，则钻头二进行规避，向两钻头连线的反方向后退一步，并转入步骤六；反之则转入步骤四。 步骤四：若钻头2的目标点与当前钻头1的距离小于最小合作间距d0，则钻头2原地等待，转入步骤六；反之则转入步骤五。 步骤五：若钻头2与目标点的距离大于钻头二每步移动的距离，则钻头2向目标点移动一步。反之即认为钻头二到达目标点，并且将路线上的下一的点作为目标点；如取遍了所有的点，算法结束。 步骤六：时间走过一个步长，开始下一步转入步骤三。,Copyright 2012 SWUFE. All rights reserved.,Page46,算法描述,前面模型的复位点默认以标号最前的点作为复位点，而事实上最优的情况下复位点应该是所有满足约束条件的点中使总时间最短的点。我们用了等步长搜索法来求最佳的起点。 步骤一：得到当前阶段钻头1，钻头2结束刀具转换开始工作的时间。 步骤二：依次从当前钻头1所加工的孔群中选取一个点作为钻头1的起始点，转入步骤三；若取完所有的点，则转入步骤五。 步骤三：依次从当前钻头1所加工的孔群中选取一个点作为钻头2的起始点，转入步骤四；若取完所有的点，则转入步骤二。 步骤四：将两钻头开始工作的时间与开始作业的起始点带入程序（算法与上一问相同，故不再赘述）计算出最终的作业时间，转入步骤三。 步骤五：比较结果得到最优解，算法结束。,Copyright 2012 SWUFE. All rights reserved.,Page47,求解结果,Copyright 2012 SWUFE. All rights reserved.,Page48,双钻头任务均衡化的再优化,初始模型求出了使两个钻头任务尽可能接近的组合，事实上我们可以对他进一步优化，原来的方案为： 钻头一： 钻头二：,Copyright 2012 SWUFE. All rights reserved.,Page49,双钻头任务均衡化的再优化,由于之前我们将打a ,b两孔群的任务都分配给了钻头1，故而钻头2在后面其实是不用打a b两种孔的。但实际上在我们给出的最优打孔方案中钻头1打了132.3秒而钻头2则仅打了120秒，这也就是说钻头2有12秒的时间没有任务，如果我们把钻头1的任务分配给钻头2一部分就能进一步降低总的作业时间。,Copyright 2012 SWUFE. All rights reserved.,Page50,双钻头任务均衡化的再优化,我们分析发现，由于b型孔对于打孔的优先顺序是没有要求的，所以如果我们改变打b型孔的时间是不会影响到其他孔的加工的。故我们选择b型孔作为任务分配的对象。为此我们便用一条水平线L将b型孔分成了上下两个部分（分法见下图），把上面的那一部分分配给钻头2，下面的分配给钻头1。 任务分配完后我们再次计算钻头1，钻头2工作的总时间，并根据总时间的多少反馈调节水平线L的位置，直到两个钻头的总的工作时间最小。,Copyright 2012 SWUFE. All rights reserved.,Page51,双钻头任务均衡化的再优化,算法描述,我们利用了斐波那契那法对水平线L的位置进行调整 步骤一：选取初始数据，确定单峰区间 ,给出搜索精度 以及搜索次数 。 步骤二 ， ， 带入子程序计算最初的两个搜索点。然后计算： 为斐波那契那数列 步骤三 当迭代次数 时将 ， 分别代入子程序算出总的工作时间 ， 。 如果 则令：,Copyright 2012 SWUFE. All rights reserved.,Page52,双钻头任务均衡化的再优化,反之则,；,；,步骤四当迭代次数 时算法结束。 关于计算工作时间的子函数 步骤一根据直线 ： 把b型孔分成上下两个部分，并用蚁群算法计算出加工这两部分孔的最短环路。进一步去掉这两个环的最长边，确定起点，终点。 步骤二从第二阶段开始计算出两个钻头的作业时间，令阶段数为二，转入下一步 步骤三利用前面的程序不断调节每个阶段两个钻头开始作业的起始点来寻找最优的作业线路 步骤四重复步骤三，直到加工完毕，计算出总时间，并以两个钻头工作时间较长的那个作为程序的返回值 ，算法结束,Copyright 2012 SWUFE. All rights reserved.,Page53,模型结果,当直线 为 时，总的工作时间达到最小值,具体刀具转换方案如下：,Copyright 2012 SWUFE. All rights reserved.,Page54,模型结果,Copyright 2012 SWUFE. All rights reserved.,Page5