贪心算法遗传算法流程图遗传算法实质是通过种群搜索技术课件.ppt

《贪心算法遗传算法流程图遗传算法实质是通过种群搜索技术课件.ppt》由会员分享，可在线阅读，更多相关《贪心算法遗传算法流程图遗传算法实质是通过种群搜索技术课件.ppt（48页珍藏版）》请在三一办公上搜索。

1、打孔机生产效能的提高,1 问题提出 2 问题分析3 模型假设4 模型的建立与求解5 模型评价及改进,目录,问题关键,印刷线路板过孔加工费用占制版费用30%到40%，打孔机主要用于线路板打孔作业，提高打孔机生产效能可以降低制版费用，时间。,钻头上安有八种刀具，有些过孔需要多个工序且有次序要求。,分别给出单钻头和双钻头最优加工作业线路，时间，成本，研究双钻头合作间距对加工路线和效率影响,问题重述,某些孔需多把刀具加工；某些孔加工时刀具有次序限制；钻头上有八把刀具，可顺逆旋转；共十种孔型，但孔数量大；不仅要研究单钻头打孔，还要研究双钻头打孔；综上分析可知：这道题与TSP问题类似，但不同之处是某些孔需

2、多把刀具加工且加工有次序限制。因此我们要想办法把本题转化为TSP问题求解。,问题分析,问题特点,本文框架,流程图：,成本矩阵,蚁群算法,方案一,不考虑单个过孔钻孔作业成本。不考虑单个过孔钻孔作业时间。钻头无损耗，不损坏。钻头移动速度恒定。钻头视为质点。,模型假设,已知线路板上各类孔型如表所示：,我们对题目中所给的原始数据进行处理，对需要多种刀具的孔型进行拆分，把需多孔型的一点拆分成只需一刀具的多个孔，拆分成的多个孔的坐标相同，但所需刀具不一样，这样一旦确定了一种加工次序，就把换刀方案确定了。,模型建立与求解,过孔转换,上述10种孔型可转化为：,处理后孔的数量由2124个变为2814个单孔，分别

3、对2814个孔坐标进行编号，即每一个孔都对应一个确切编号，坐标和所需刀具，这样的话，我们转换成TSP问题进行求解。,模型建立与求解,转换后的孔型,对刀具进行编号，18,每个空为三维坐标，前两维是位置，第三维是刀具编号。,模型建立与求解,孔型三维坐标,总加工花费,从i孔到j孔换刀次数,总加工时间,模型建立与求解,符号约定、公式,刀具编号：1，2，38,目标函数,模型建立与求解,问题一：,其中：（f:总成本，H：换刀成本，L：行进成本，Xt：行进时间，Ht:换刀时间。）,目标函数,模型建立与求解,问题二：,其中：（f1：钻头一成本，f2：钻头二成本，T1：钻头一时间，T2:钻头二时间。）,模型建立

4、与求解,问题一：,1.蚁群算法：,随着时间的推进，路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时的便是待优化问题的最佳解。,模型建立与求解,问题一：,1.蚁群算法,(一)、将三维坐标形成成本矩阵，即孔孔之间的刀具转换成本和行进成本之和。(二)、采用蚁群算法进行计算。,模型建立与求解,问题一：,1.蚁群算法,初始化,随机放置蚂蚁,以每一只蚂蚁所在孔，作为起始城市,选择选下一个城市,返回到初始城市,还有可选城市？,更新信息素矩阵，即更新每路径上的信息素的量,满足停止条件？,输出最好的路径,Yes,No,No,模型建立与求解,

5、问题一：,1.蚁群算法,成本：1197.2元时间：1382.2秒,模型建立与求解,问题一：,2.贪心算法,(一)、换刀方案：d,e,f,g,h,a,b,c,f(二)、换刀时间：180秒(三)、权值：距离,模型建立与求解,问题一：,2.贪心算法,算法流程图,模型建立与求解,问题一：,2.贪心算法,作业时间：267.68秒成本：932.19元,d刀具加工图(单位：mil),模型建立与求解,问题一：,2.贪心算法,537(465)-522-525-518-514-510-506-503-507-511-515-516-512-508-504-523-528-531-533-536-524-517-5

6、13-509-505-520-521-527-530-532-535-534-529-526-519-498-492-497-485-486-487-493-500-499-488-489-494-502-501-490-484-491-496-495-483-换h刀具,g刀具走刀路线：,模型建立与求解,问题一：,2.贪心算法,最终选择cst=0.6,csf=0.4计算出总费用为965.12元，加工时间为214秒,模型建立与求解,问题一：,2.贪心算法,遗传算法流程图,遗传算法实质是通过种群搜索技术，根据适者生存原则逐代进化，最终得到最优解或准最优解。,输出结果,结束,1,模型建立与求解,问题

7、一：,3.遗传结合贪心算法,改良圈算法：（以m=233）为例,改良圈算法是一种经典的近似算法，用于优化遗传算法的初始种群，令i=1，第一步：随机生成初始圈（初始解）：,第二步：交换u，v之间的顺序，则得到新路径：,模型建立与求解,问题一：,3.遗传结合贪心算法,改良圈算法：,评判标准为两次相邻路径的差值：,若f0,则以新路径替换旧路径，直到不能修改为止。,第三步：令i=i+1，若i=POP（种群规模）,算法结束，否则转向第一步,模型建立与求解,问题一：,3.遗传结合贪心算法,遗传算法的实现：,编码策略采用十进制编码，用随机数列,作为染色体(个体)，其中为避免在交叉后产生的染色体出现重复的基因（

8、孔编号），限定,模型建立与求解,问题一：,3.遗传结合贪心算法,遗传算法的实现：,（2）种群初始化：本文利用改良圈算法得到一个规模为50的种群。（3）交叉根据孔数的规模，本文采用单点交叉方案，取交叉概率pc=1。先从种群中随机选取两个父代（两个初始解）1和2：,用Logistic 混沌序列产生一个2到232之间的正整数，例如得到随机数21，则对相应基因进行交叉得到新染色体。,模型建立与求解,问题一：,3.遗传结合贪心算法,遗传算法的实现：,(4)变异是实现群体多样性的一种手段，是跳出局部最优，全局寻优的重要保证。本模型中具体变异算子设计如下，首先根据给定的变异率(本模型选为 0.02)，随机地

9、取两个在2 到232之间的整数，对这两个数对应位置的基因进行变异，具体变异以当前的基因值为初值利用Logistic混沌序列进行适当次数的迭代，得到变异后新的基因值，从而得到新的染色体。,模型建立与求解,问题一：,3.遗传结合贪心算法,遗传算法的实现：,（5）选择本文选取目标函数作为适应度函数，选择上述所有个体中适应度函数最小的50个个体作为下一代个体。,采用圆盘赌法：计算适应度函数值Fitness,模型建立与求解,问题一：,3.遗传结合贪心算法,模型建立与求解,问题一：,3.遗传结合贪心算法,(一)、换刀方案：d.c.b.a.b.g.f.e.d.c(二)、换刀时间：162秒(三)、权值：距离,

10、（1）用遗传算法进行计算。（2）采用贪心算法进行搜索。,模型建立与求解,问题一：,3.遗传结合贪心算法,成本：892.97元；时间：242.9s,换刀路径图,打孔路径图,模型建立与求解,问题一：,3.遗传结合贪心算法,成本：892.97元；时间：242.9s,成本：1197.2元，时间为1382.2秒,蚁群算法：,贪心算法：,成本：932.19元；成本：267.6754秒,遗传结合贪心算法：,模型建立与求解,问题一：,结论：,模型建立与求解,问题二：,钻头一：642.3 秒成本：450.83 元钻头二：1021.5 秒成本：738.32 元,1.蚁群算法,总成本：1189.2 元时间：1021

11、.5 秒,模型建立与求解,问题二：,2.贪心算法,钻头一钻头二，d刀具的加工图,模型建立与求解,问题二：,钻头一：总时间：213.909秒，总花费：360.66元(其中换刀时间为：180秒,行进时间：33.91秒)钻头二：总时间：234.28秒，总花费：577.26元(其中换刀时间为：180秒，行进时间：54.28秒)则双钻头：总时间：234.28秒总花费：937.92元,2.贪心算法,模型建立与求解,问题二：,2.贪心算法,可能冲突的点形成的距离矩阵（以x=-50000mil划分）,模型建立与求解,问题二：,2.贪心算法,双钻头和钻间距与加工费用和时间的关系,模型建立与求解,问题二：,2.贪

12、心算法,x:是合作间距,y:是加工费用,合作间距函数：,x:是合作间距 y:是加工时间,费用函数：,钻头同时工作时的生产效能，提出以下两种分配方案：首先采用K-means聚类分析方法，以合作间距为依据将所有孔分为两大类，采用遗传结合贪心算法对两大类分别计算得到最优路径。第一类初始类中心为：（-325400,554800）第二类初始类中心为：（88800,919800）,模型建立与求解,问题二：,聚类分析,3.遗传结合贪心算法,模型建立与求解,问题二：,3.遗传结合贪心算法,聚类结果：,双钻头打孔算法流程图,开始,聚类为两类,输出下一起点,结束,按方案三，对两类分别计算,模型建立与求解,问题二：

13、,3.遗传结合贪心算法,其中第一个钻头路径图,模型建立与求解,问题二：,3.遗传结合贪心算法,钻头一：,钻头二：,总时间：207.5s作业成本：942.392元,模型建立与求解,问题二：,3.遗传结合贪心算法,单钻头：总加工时间：242.9s总加工费用：892.97元,双钻头：总时间：207.5s作业成本：942.392元,结论：与单钻头相比，双钻头加工可以明显缩短加工时间，提高效率14.5%，但费用有增加5.5%。,模型建立与求解,模型评价及改进,本文亮点：1.结合作业孔的作业要求，以目标权重（时间，成本或时间成本的加权和）为“距离”构造一个非对称的图，进一步建立了一个理论上相对完备的数学模型（TSP模型），理论上该模型的最优解就是全局最优解。2.本文采用了改进的贪心算法以减少换刀次数为原则分别对问题一和问题二进行了有效求解获得的较好结果。3.通过引入遗传算法并结合贪心算法进一步改进了上述结果，且在双钻头模型中引入聚类分析方法进行了作业孔自动分区。4.详细计算讨论了在第二种方法下，合作间距对作业时间和成本的影响并得出相应结论；,1.遗传算法容易出现早熟收敛。2.程序计算速度慢。3.问题二处理较为简单，若能采用其他分区方法进行处理效果可能更好。,模型评价及改进,不足：,恳请老师、同学批评指正！,谢谢！,