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

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

1、打孔机生产效能的提高队队 员：员：李伦李伦 王旭王旭 查姗查姗指导教师：指导教师：屠良平屠良平学学 校：校：辽宁科技大学辽宁科技大学打孔机生打孔机生产产效能的提高效能的提高队队 员员：李：李伦伦 王旭王旭 查姗查姗指指导导教教1 1 问题提出问题提出 2 2 问题分析问题分析3 3 模型假设模型假设4 4 模型的建立与求解模型的建立与求解5 5 模型评价及改进模型评价及改进目录目录目目录录问题关键问题关键印刷线路板过孔加工费用占制版费用印刷线路板过孔加工费用占制版费用30%30%到到40%40%，打孔机主要用于线路板打孔作业，提高打孔，打孔机主要用于线路板打孔作业，提高打孔机生产效能可以降低制

2、版费用，时间机生产效能可以降低制版费用，时间。钻头上安有八种刀具，有些过孔需要多个工序且有次序要求钻头上安有八种刀具，有些过孔需要多个工序且有次序要求。问题重述问题重述问题问题关关键键印刷印刷线线路板路板过过孔加工孔加工费费用占制版用占制版费费用用30%到到40%，打孔，打孔某些孔需多把刀具加工；某些孔需多把刀具加工；某些孔加工时刀具有次序限制；某些孔加工时刀具有次序限制；钻头上有八把刀具，可顺逆旋转；钻头上有八把刀具，可顺逆旋转；共十种孔型，但孔数量大；共十种孔型，但孔数量大；不仅要研究单钻头打孔，还要研究双钻头打孔不仅要研究单钻头打孔，还要研究双钻头打孔；综上分析可知：这道题与综上分析可知

3、：这道题与TSPTSP问题类似，但不同之处是某些孔问题类似，但不同之处是某些孔需多把刀具加工且加工有次序限制。因此我们要想办法把本需多把刀具加工且加工有次序限制。因此我们要想办法把本题转化为题转化为TSPTSP问题求解。问题求解。问题分析问题分析问题特点问题特点某些孔需多把刀具加工；某些孔需多把刀具加工；问题问题分析分析问题问题特点特点本文框架本文框架双钻头双钻头单钻头单钻头最优路径最优路径最优路径、最优路径、换刀方案换刀方案换刀方案换刀方案单钻头最优路径单钻头最优路径开始开始双刀最优路径、双刀最优路径、换刀方案换刀方案双刀换刀方案双刀换刀方案双钻头最优路径双钻头最优路径方案二方案三遗传算法结

4、合贪心算法分块方案二方案二贪心算法贪心算法最优路径最优路径遗传算法结合贪心算法聚类分块分析合作间距影响分析合作间距影响结束结束对比分析生产效能对比对比成本成本矩阵矩阵方案一蚁群算法流程图：流程图：成本成本矩阵矩阵蚁群算法方案一本文框架双本文框架双钻头单钻头钻头单钻头最最优优路径最路径最优优路径、路径、换换刀方案刀方案单钻头单钻头最最优优路径路径不考虑单个过孔钻孔作业成本。不考虑单个过孔钻孔作业成本。不考虑单个过孔钻孔作业时间。不考虑单个过孔钻孔作业时间。钻头无损耗，不损坏。钻头无损耗，不损坏。钻头移动速度恒定。钻头移动速度恒定。钻头视为质点钻头视为质点。模型假设模型假设不考不考虑单虑单个个过过

5、孔孔钻钻孔作孔作业业成本。模型假成本。模型假设设孔型孔型ABCDEFGHIJ所需刀具所需刀具aba,cd,e*c,fg,h*d,g,fhe,cf,c已知线路板上各类孔型如表所示：已知线路板上各类孔型如表所示：我们对题目中所给的原始数据进行处理，对需要多种刀具的孔型我们对题目中所给的原始数据进行处理，对需要多种刀具的孔型进行拆分，把需多孔型的一点拆分成只需一刀具的多个孔，拆分成的进行拆分，把需多孔型的一点拆分成只需一刀具的多个孔，拆分成的多个孔的坐标相同，但所需刀具不一样，这样一旦确定了一种加工次多个孔的坐标相同，但所需刀具不一样，这样一旦确定了一种加工次序，就把换刀方案确定了。序，就把换刀方案

6、确定了。模型建立与求解模型建立与求解过孔转换过孔转换 孔型孔型ABCDEFGHIJ所需刀具所需刀具aba,cd,e*c,上述上述1010种孔型可转化为种孔型可转化为：处理后孔的数量由处理后孔的数量由21242124个变为个变为28142814个单孔，分别对个单孔，分别对28142814个孔坐标个孔坐标进行编号，即每一个孔都对应一个确切编号，坐标和所需刀具，进行编号，即每一个孔都对应一个确切编号，坐标和所需刀具，这样的话，我们转换成这样的话，我们转换成TSPTSP问题进行求解。问题进行求解。模型建立与求解模型建立与求解转换后的孔型转换后的孔型上述上述10种孔型可种孔型可转转化化为为：处处理后孔的

7、数量由理后孔的数量由2124个个变为变为281对刀具进行编号，对刀具进行编号，1818每个空为三维坐标，前两维是位置，第三维是刀具编号。每个空为三维坐标，前两维是位置，第三维是刀具编号。模型建立与求解模型建立与求解孔型三维坐标孔型三维坐标对对刀具刀具进进行行编编号，号，18每个空每个空为为三三维维坐坐标标，前两，前两维维是位置，第三是位置，第三维维总加工花费总加工花费从从i i孔到孔到j j孔换刀次数孔换刀次数总加工时间总加工时间模型建立与求解模型建立与求解符号约定、公式符号约定、公式刀具编号：刀具编号：1 1，2 2，3838总总加工花加工花费费从从i孔到孔到j孔孔换换刀次数刀次数总总加工加

8、工时间时间模型建立与求解符号模型建立与求解符号约约目标函数目标函数模型建立与求解模型建立与求解问题一：问题一：其中：（其中：（f:f:总成本，总成本，H H：换刀成本，：换刀成本，L L：行进成本，：行进成本，X Xt t：行进时：行进时间，间，H Ht t:换刀时间。）换刀时间。）目目标标函数模型建立与求解函数模型建立与求解问题问题一：其中：（一：其中：（f:总总成本，成本，H：换换刀成刀成目标函数目标函数模型建立与求解模型建立与求解问题二：问题二：其中：（其中：（f f1 1：钻头一成本，：钻头一成本，f f2 2：钻头二成本，：钻头二成本，T T1 1 ：钻头一时：钻头一时间，间，T T

9、2 2:钻头二时间。）钻头二时间。）目目标标函数模型建立与求解函数模型建立与求解问题问题二：其中：（二：其中：（f1：钻头钻头一成本，一成本，f2模型建立与求解模型建立与求解问题一：问题一：1.1.蚁群算法：蚁群算法：随着时间的推进，路径上累积的信息素浓度逐渐增高，随着时间的推进，路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时的便是待优化正反馈的作用下集中到最佳的路径上，此时的便是待优化问题的最佳解。问题的最佳解。模型建立与求解模型建立与求解问题问题一：一：1.蚁蚁群算法

10、：随着群算法：随着时间时间的推的推进进，路径上累，路径上累模型建立与求解模型建立与求解问题一：问题一：1.1.蚁群算法蚁群算法(一一)、将三维坐标形成成本矩阵，即孔孔之间的刀具转换、将三维坐标形成成本矩阵，即孔孔之间的刀具转换成本和行进成本之和。成本和行进成本之和。(二二)、采用蚁群算法进行计算、采用蚁群算法进行计算。模型建立与求解模型建立与求解问题问题一：一：1.蚁蚁群算法群算法(一一)、将三、将三维维坐坐标标形成成本形成成本模型建立与求解模型建立与求解问题一：问题一：1.1.蚁群算法蚁群算法初始化随机放置蚂蚁以每一只蚂蚁所在孔，作为起始城市选择选下一个城市返回到初始城市还有可选城市？更新信

11、息素矩阵，即更新每路径上的信息素的量满足停止条件？输出最好的路径YesNoNo模型建立与求解模型建立与求解问题问题一：一：1.蚁蚁群算法初始化随机放置群算法初始化随机放置蚂蚁蚂蚁以每一只以每一只模型建立与求解模型建立与求解问题一：问题一：1.1.蚁群算法蚁群算法成本成本：1197.21197.2元元时间时间：1382.21382.2秒秒模型建立与求解模型建立与求解问题问题一：一：1.蚁蚁群算法成本：群算法成本：1197.2元元模型建立与求解模型建立与求解问题一：问题一：2.2.贪心算法贪心算法(一一)、换刀方案、换刀方案：d,e,f,g,h,a,b,c,fd,e,f,g,h,a,b,c,f(二

12、二)、换刀时间：、换刀时间：180180秒秒(三三)、权值：距离、权值：距离模型建立与求解模型建立与求解问题问题一：一：2.贪贪心算法心算法(一一)、换换刀方案：刀方案：d,e,模型建立与求解模型建立与求解问题一：问题一：2.2.贪心算法贪心算法算法流程图模型建立与求解模型建立与求解问题问题一：一：2.贪贪心算法算法流程心算法算法流程图图模型建立与求解模型建立与求解问题一：问题一：2.2.贪心算法贪心算法作业时间：作业时间：267.68267.68秒秒成本：成本：932.19932.19元元d d刀具加工图刀具加工图(单位：单位：mil)mil)模型建立与求解模型建立与求解问题问题一：一：2.

13、贪贪心算法作心算法作业时间业时间：267.68秒秒d模型建立与求解模型建立与求解问题一：问题一：2.2.贪心算法贪心算法537(465)-522-525-518-514-510-506-503-507 537(465)-522-525-518-514-510-506-503-507 -511-515-516-512-508-504-523-528-531-533 -511-515-516-512-508-504-523-528-531-533 -536-524-517-513-509-505-520-521-527-530 -536-524-517-513-509-505-520-521-52

14、7-530 -532-535-534-529-526-519-498-492-497-485 -532-535-534-529-526-519-498-492-497-485 -486-487-493-500-499-488-489-494-502-501 -486-487-493-500-499-488-489-494-502-501 -490-484-491-496-495-483-490-484-491-496-495-483-换换h h刀具刀具g g刀具走刀路线：刀具走刀路线：模型建立与求解模型建立与求解问题问题一：一：2.贪贪心算法心算法537(465)-522模型建立与求解模型建立

15、与求解问题一：问题一：2.2.贪心算法贪心算法权重系数cst 10.9 0.8 0.7 0.6 0.5 0.4 0.30.20.10csf 00.1 0.2 0.3 0.4 0.5 0.6 0.70.80.91费用(元)965.12965.12965.12965.12965.12965.12965.12956.38960.48932.27944.27时间(秒)214 214 214 214 214 214 214 3203734951084最终选择最终选择cst=0.6,csf=0.4cst=0.6,csf=0.4计算出总费用为计算出总费用为965.12965.12元，加工时间为元，加工时间为

16、214214秒秒模型建立与求解模型建立与求解问题问题一：一：2.贪贪心算法心算法权权重系数重系数cst10.90.模型建立与求解模型建立与求解问题一：问题一：2.2.贪心算法贪心算法模型建立与求解模型建立与求解问题问题一：一：2.贪贪心算法心算法遗传算法流程图遗传算法流程图遗传算法实质是通过种群搜索技术，根据适者生存原则逐代遗传算法实质是通过种群搜索技术，根据适者生存原则逐代进化，最终得到最优解或准最优解进化，最终得到最优解或准最优解。采用采用“改良圈改良圈”算法得到优良父代算法得到优良父代开始开始对父代进行交叉，变异，形成新种群对父代进行交叉，变异，形成新种群计算种群中个体的适应度值，并选择

17、优良子代计算种群中个体的适应度值，并选择优良子代1 1满足遗传代满足遗传代输出结果输出结果结束结束1 1模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法遗传遗传算法流程算法流程图遗传图遗传算法算法实质实质是通是通过过种群搜索技种群搜索技术术，根据适者生存原，根据适者生存原改良圈算法改良圈算法：（以：（以m=233m=233）为例）为例改良圈算法是一种经典的近似算法，用于优化遗传算法的初始种群，改良圈算法是一种经典的近似算法，用于优化遗传算法的初始种群，令令i=1i=1，第一步：随机生成初始圈（初始解）：，第一步：随机生成初始圈（初始解）：第二步：交换第二步：

18、交换u u，v v之间的顺序，则得到新路径之间的顺序，则得到新路径：C=C=C C=u uv vv vu u?模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法改良圈算法：（以改良圈算法：（以m=233）为为例改良圈算法是一种例改良圈算法是一种经经典的近似算典的近似算改良圈算法：改良圈算法：评判标准为两次相邻路径的差值：评判标准为两次相邻路径的差值：若若f0,f0,则以新路径替换旧路径，直到不能修改为止。则以新路径替换旧路径，直到不能修改为止。第三步：令第三步：令i=i+1i=i+1，若，若i=POPi=POP（种群规模）（种群规模）,算法结束，否则转向第一步

19、算法结束，否则转向第一步C=C=C C=u uv vv vu u模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法改良圈算法：改良圈算法：评评判判标标准准为为两次相两次相邻邻路径的差路径的差值值：若：若f0,则则以新以新遗传算法的实现：遗传算法的实现：编码策略采用十进制编码，用随机数列编码策略采用十进制编码，用随机数列作为染色体作为染色体(个体个体)，其中为避免在交叉后产生的染色体出现重复的基因，其中为避免在交叉后产生的染色体出现重复的基因（孔编号），限定（孔编号），限定 2332331 1模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗

20、传结合贪心算法遗传遗传算法的算法的实现实现：编码编码策略采用十策略采用十进进制制编码编码，用随机数列作，用随机数列作为为染色体染色体遗传算法的实现：遗传算法的实现：（2 2）种群初始化：）种群初始化：本文利用改良圈算法得到一个规模为本文利用改良圈算法得到一个规模为5050的种群。的种群。（3 3）交叉）交叉根据孔数的规模，本文采用单点交叉方案，取交叉概率根据孔数的规模，本文采用单点交叉方案，取交叉概率pc=1pc=1。先从种群。先从种群中随机选取两个父代（两个初始解）中随机选取两个父代（两个初始解）11和和22：用用Logistic Logistic 混沌序列产生一个混沌序列产生一个2 2到到

21、232232之间的正整数，例如得到随机数之间的正整数，例如得到随机数2121，则对相应基因进行交叉得到新染色体。则对相应基因进行交叉得到新染色体。2332331 12332331 1模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法遗传遗传算法的算法的实现实现：（：（2）种群初始化：用）种群初始化：用Logistic 混沌序混沌序遗传算法的实现：遗传算法的实现：(4)(4)变异变异是实现群体多样性的一种手段，是跳出局部最优，全局寻优的重要保证。本模型是实现群体多样性的一种手段，是跳出局部最优，全局寻优的重要保证。本模型中具体变异算子设计如下，首先根据给定的变异

22、率中具体变异算子设计如下，首先根据给定的变异率(本模型选为本模型选为 0.02)0.02)，随机地取两个在，随机地取两个在2 2 到到232232之间的整数，对这两个数对应位置的基因进行变异，具体变异以当前的基因值为之间的整数，对这两个数对应位置的基因进行变异，具体变异以当前的基因值为初值利用初值利用LogisticLogistic混沌序列进行适当次数的迭代，得到变异后新的基因值，从而得到新混沌序列进行适当次数的迭代，得到变异后新的基因值，从而得到新的染色体的染色体。模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法遗传遗传算法的算法的实现实现：(4)变变异模

23、型建立与求解异模型建立与求解问题问题一：一：3.遗传结遗传结合合遗传算法的实现：遗传算法的实现：（5 5）选择）选择本文选取目标函数作为适应度函数，选择上述所有个体中适应度函数本文选取目标函数作为适应度函数，选择上述所有个体中适应度函数最小的最小的5050个个体作为下一代个体。个个体作为下一代个体。采用圆盘赌法：采用圆盘赌法：计算适应度函数值计算适应度函数值FitnessFitness模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法遗传遗传算法的算法的实现实现：（：（5）选择选择采用采用圆盘赌圆盘赌法：模型建立与求解法：模型建立与求解问题问题一一 模型建立与

24、求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法(一一)、换刀方案：、换刀方案：d.c.b.a.b.g.f.e.d.cd.c.b.a.b.g.f.e.d.c(二二)、换刀时间：、换刀时间：162162秒秒(三三)、权值：距离、权值：距离 模型建立与求解模型建立与求解问题问题一：一：3.遗传结遗传结合合贪贪心算法心算法(一一)、换换刀方刀方（1 1）用遗传算法进行计算。）用遗传算法进行计算。（2 2）采用贪心算法进行搜索。）采用贪心算法进行搜索。模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法成本：成本：892.97892.97元；元

25、；时间：时间：242.9s242.9s（1）用）用遗传遗传算法算法进进行行计计算。模型建立与求解算。模型建立与求解问题问题一：一：3.遗传结遗传结合合换刀路径图换刀路径图打孔路径图打孔路径图模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法换换刀路径刀路径图图打孔路径打孔路径图图模型建立与求解模型建立与求解问题问题一：一：3.遗传结遗传结合合贪贪心算心算成本：成本：892.97892.97元；元；时间：时间：242.9s242.9s成本：成本：1197.21197.2元，时间为元，时间为1382.21382.2秒秒蚁群算法：蚁群算法：贪心算法：贪心算法：成本成

26、本：932.19932.19元；元；成本：成本：267.6754267.6754秒秒遗传结合贪心算法：遗传结合贪心算法：模型建立与求解模型建立与求解问题一：问题一：结论：结论：成本：成本：892.97元；元；时间时间：242.9s成本：成本：1197.2元元模型建立与求解模型建立与求解问题二：问题二：钻头一：钻头一：642.3 642.3 秒秒成本成本：450.83 450.83 元元钻头二：钻头二：1021.5 1021.5 秒秒成本成本：738.32 738.32 元元1.1.蚁群算法蚁群算法总成本：总成本：1189.2 1189.2 元元时间：时间：1021.5 1021.5 秒秒模型建

27、立与求解模型建立与求解问题问题二：二：钻头钻头一：一：642.3 秒秒成本：成本：45模型建立与求解模型建立与求解问题二：问题二：2.2.贪心算法贪心算法 钻头一钻头二，钻头一钻头二，d d刀具的加工图刀具的加工图模型建立与求解模型建立与求解问题问题二：二：2.贪贪心算法心算法 钻头钻头一一钻头钻头二，二，d刀具刀具模型建立与求解模型建立与求解问题二：问题二：钻头一：钻头一：总时间：总时间：213.909213.909秒秒，总花费：总花费：360.66360.66元元(其中换刀时间为：其中换刀时间为：180180秒秒,行进时间：行进时间：33.9133.91秒秒)钻头二：钻头二：总时间：总时间

28、：234.28234.28秒秒，总花费：总花费：577.26577.26元元(其中换刀时间为：其中换刀时间为：180180秒，行进时间：秒，行进时间：54.2854.28秒秒)则双钻头：则双钻头：总时间：总时间：234.28234.28秒秒总花费：总花费：937.92937.92元元2.2.贪心算法贪心算法模型建立与求解模型建立与求解问题问题二：二：钻头钻头一：一：2.贪贪心算法心算法模型建立与求解模型建立与求解问题二：问题二：2.2.贪心算法贪心算法钻 头 二 966(a)967(a)968(a)1974(b)2411(c)2412(c)2413(c)2414(c)2728(f)钻头一坐标

29、962(a)1751.16671691981158.111751.16671691988084.018084.01963(a)1701.16666691481108.121701.16666691488034.018034.01964(a)533.1445498798060.8276533.1445498798068666866965(a)1466.86349859802060.021466.86349859804866.014866.012409(c)1751.16671691981158.111751.16671691988084.018084.012410(c)1701.16666691

30、481108.121701.16666691488034.018034.01可能冲突的点形成的距离矩阵可能冲突的点形成的距离矩阵（以（以x=-50000milx=-50000mil划分）划分）模型建立与求解模型建立与求解问题问题二：二：2.贪贪心算法心算法钻头钻头二二 966(a)96模型建立与求解模型建立与求解问题二：问题二：2.2.贪心算法贪心算法合作间距1cm2cm3cm3.5cm4cm4.5cm5cm总 加 工费用(元)1257.51248.23 1248.23 1248.23 1248.22 1248.22 1248.22加 工 时间（秒）256255255255255255255

31、双钻头和钻间距与加工费用和时间的关系双钻头和钻间距与加工费用和时间的关系模型建立与求解模型建立与求解问题问题二：二：2.贪贪心算法合作心算法合作1cm2cm3cm3.模型建立与求解模型建立与求解问题二：问题二：2.2.贪心算法贪心算法 x:x:是合作间距是合作间距y:y:是加工费用是加工费用合作间距合作间距函数：函数：x:x:是合作间距是合作间距 y:y:是加工时间是加工时间费用函数：费用函数：模型建立与求解模型建立与求解问题问题二：二：2.贪贪心算法心算法 x:是合作是合作间间距距y:是加是加钻头同时工作时的生产效能，提出以下两种分配方案：钻头同时工作时的生产效能，提出以下两种分配方案：首先

32、采用首先采用K-meansK-means聚类分析方法，以合作间距为依据将所有孔聚类分析方法，以合作间距为依据将所有孔分为两大类，采用遗传结合贪心算法对两大类分别计算得到最分为两大类，采用遗传结合贪心算法对两大类分别计算得到最优路径。优路径。第一类初始类中心为：（第一类初始类中心为：（-325400,554800-325400,554800）第二类初始类中心为：（第二类初始类中心为：（88800,91980088800,919800）模型建立与求解模型建立与求解问题二：问题二：聚类分析聚类分析3.3.遗传结合贪心算法遗传结合贪心算法钻头钻头同同时时工作工作时时的生的生产产效能，提出以下两种分配方

33、案：模型建立与求效能，提出以下两种分配方案：模型建立与求模型建立与求解模型建立与求解问题二：问题二：3.3.遗传结合贪心算法遗传结合贪心算法聚类结果：聚类结果：模型建立与求解模型建立与求解问题问题二：二：3.遗传结遗传结合合贪贪心算法聚心算法聚类结类结果：果：双钻头打孔算法流程图双钻头打孔算法流程图开始开始聚类为两类聚类为两类输出下一起点输出下一起点结束结束按方案三，对两类分别计算按方案三，对两类分别计算模型建立与求解模型建立与求解问题二：问题二：3.3.遗传结合贪心算法遗传结合贪心算法双双钻头钻头打孔算法流程打孔算法流程图图开始聚开始聚类为类为两两类输类输出下一起点出下一起点结结束按方案三，

34、束按方案三，其中第一个钻头路径图其中第一个钻头路径图模型建立与求解模型建立与求解问题二：问题二：3.3.遗传结合贪心算法遗传结合贪心算法其中第一个其中第一个钻头钻头路径路径图图模型建立与求解模型建立与求解问题问题二：二：3.遗传结遗传结合合贪贪心算心算钻头一：钻头一：钻头二：钻头二：总时间：总时间：207.5s207.5s作业成本：作业成本：942.392942.392元元模型建立与求解模型建立与求解问题二：问题二：3.3.遗传结合贪心算法遗传结合贪心算法钻头钻头一：一：钻头钻头二：二：总时间总时间：207.5s模型建立与求解模型建立与求解问题问题二：二：3单钻头：单钻头：总加工时间：总加工时

35、间：242.9s242.9s总加工费用：总加工费用：892.97892.97元元双钻头：双钻头：总时间：总时间：207.5s207.5s作业成本：作业成本：942.392942.392元元结论：结论：与单钻头相比，双钻头加工可以明显缩短加工时间，提高效率与单钻头相比，双钻头加工可以明显缩短加工时间，提高效率14.5%14.5%，但费用有增加，但费用有增加5.5%5.5%。模型建立与求解模型建立与求解单钻头单钻头：双：双钻头钻头：结论结论：模型建立与求解：模型建立与求解模型评价及改进模型评价及改进本文亮点：本文亮点：1.1.结合作业孔的作业要求，以目标权重（时间，成本或结合作业孔的作业要求，以目

36、标权重（时间，成本或时间成本的加权和）为时间成本的加权和）为“距离距离”构造一个非对称的图，进一步构造一个非对称的图，进一步建立了一个理论上相对完备的数学模型（建立了一个理论上相对完备的数学模型（TSPTSP模型），理论上模型），理论上该模型的最优解就是全局最优解。该模型的最优解就是全局最优解。2.2.本文采用了改进的贪心算法以减少换刀次数为原则分本文采用了改进的贪心算法以减少换刀次数为原则分别对问题一和问题二进行了有效求解获得的较好结果。别对问题一和问题二进行了有效求解获得的较好结果。3.3.通过引入遗传算法并结合贪心算法进一步改进了上述通过引入遗传算法并结合贪心算法进一步改进了上述结果，且

37、在双钻头模型中引入聚类分析方法进行了作业孔自动结果，且在双钻头模型中引入聚类分析方法进行了作业孔自动分区。分区。4.4.详细计算讨论了在第二种方法下，合作间距对作业时详细计算讨论了在第二种方法下，合作间距对作业时间和成本的影响并得出相应结论；间和成本的影响并得出相应结论；模型模型评评价及改价及改进进本文亮点：本文亮点：1.1.遗传算法容易出现早熟收敛。遗传算法容易出现早熟收敛。2.2.程序计算速度慢。程序计算速度慢。3.3.问题二处理较为简单，若能采用其他分区方法进行处理效问题二处理较为简单，若能采用其他分区方法进行处理效果可能更好。果可能更好。模型评价及改进模型评价及改进不足：不足：1.遗传遗传算法容易出算法容易出现现早熟收早熟收敛敛。模型。模型评评价及改价及改进进不足：不足：恳请恳请老师、同学老师、同学批评指正！批评指正！谢谢！谢谢！恳请恳请老老师师、同学、同学谢谢谢谢！