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

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

2、刀具，有些过孔需要多个工序且有次序要求。bcdefgha问题重述问题重述某些孔需多把刀具加工；某些孔需多把刀具加工；某些孔加工时刀具有次序限制；某些孔加工时刀具有次序限制；钻头上有八把刀具，可顺逆旋转；钻头上有八把刀具，可顺逆旋转；共十种孔型，但孔数量大；共十种孔型，但孔数量大；不仅要研究单钻头打孔，还要研究双钻头打孔不仅要研究单钻头打孔，还要研究双钻头打孔；综上分析可知：这道题与综上分析可知：这道题与TSPTSP问题类似，但不同之处是某些孔问题类似，但不同之处是某些孔需多把刀具加工且加工有次序限制。因此我们要想办法把本需多把刀具加工且加工有次序限制。因此我们要想办法把本题转化为题转化为TSP

3、TSP问题求解。问题求解。问题分析问题分析问题特点问题特点本文框架本文框架双钻头双钻头单钻头单钻头最优路径最优路径最优路径、最优路径、换刀方案换刀方案换刀方案换刀方案单钻头最优路径单钻头最优路径开始开始双刀最优路径、双刀最优路径、换刀方案换刀方案双刀换刀方案双刀换刀方案双钻头最优路径双钻头最优路径方案二方案三遗传算法结合贪心算法分块方案二方案二贪心算法贪心算法最优路径最优路径遗传算法结合贪心算法聚类分块分析合作间距影响分析合作间距影响结束结束对比分析生产效能对比对比成本成本矩阵矩阵方案一蚁群算法流程图：流程图：成本成本矩阵矩阵蚁群算法方案一 不考虑单个过孔钻孔作业成本。不考虑单个过孔钻孔作业成

4、本。 不考虑单个过孔钻孔作业时间。不考虑单个过孔钻孔作业时间。 钻头无损耗，不损坏。钻头无损耗，不损坏。 钻头移动速度恒定。钻头移动速度恒定。 钻头视为质点钻头视为质点。模型假设模型假设孔型孔型ABCDEFGHIJ所需刀具所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, c已知线路板上各类孔型如表所示：已知线路板上各类孔型如表所示：我们对题目中所给的原始数据进行处理，对需要多种刀具的孔型我们对题目中所给的原始数据进行处理，对需要多种刀具的孔型进行拆分，把需多孔型的一点拆分成只需一刀具的多个孔，拆分成的进行拆分，把需多孔型的一点拆分成只需一刀具的多个孔，拆分成的多个孔

5、的坐标相同，但所需刀具不一样，这样一旦确定了一种加工次多个孔的坐标相同，但所需刀具不一样，这样一旦确定了一种加工次序，就把换刀方案确定了。序，就把换刀方案确定了。模型建立与求解模型建立与求解过孔转换过孔转换 上述上述1010种孔型可转化为种孔型可转化为：处理后孔的数量由处理后孔的数量由21242124个变为个变为28142814个单孔，分别对个单孔，分别对28142814个孔坐标个孔坐标进行编号，即每一个孔都对应一个确切编号，坐标和所需刀具，进行编号，即每一个孔都对应一个确切编号，坐标和所需刀具，这样的话，我们转换成这样的话，我们转换成TSPTSP问题进行求解。问题进行求解。模型建立与求解模型

6、建立与求解转换后的孔型转换后的孔型对刀具进行编号，对刀具进行编号，1818每个空为三维坐标，前两维是位置，第三维是刀具编号。每个空为三维坐标，前两维是位置，第三维是刀具编号。模型建立与求解模型建立与求解孔型三维坐标孔型三维坐标2()NjFf ij ,44j iijhzz 2()NjTt ij 总加工花费总加工花费从从i i孔到孔到j j孔换刀次数孔换刀次数总加工时间总加工时间模型建立与求解模型建立与求解符号约定、公式符号约定、公式Zi刀具编号：刀具编号：1 1，2 2，3838目标函数目标函数模型建立与求解模型建立与求解HLf问题一：问题一：HLTtt其中：（其中：（f:f:总成本，总成本，H

7、 H：换刀成本，：换刀成本，L L：行进成本，：行进成本，X Xt t：行进时：行进时间，间，H Ht t: :换刀时间。）换刀时间。）目标函数目标函数模型建立与求解模型建立与求解fff21问题二：问题二：)(21maxTTT，其中：（其中：（f f1 1：钻头一成本，：钻头一成本，f f2 2：钻头二成本，：钻头二成本，T T1 1 ：钻头一时：钻头一时间，间，T T2 2: : 钻头二时间。）钻头二时间。）模型建立与求解模型建立与求解问题一：问题一：1.1.蚁群算法：蚁群算法：随着时间的推进，路径上累积的信息素浓度逐渐增高，随着时间的推进，路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个

8、数也愈来愈多。最终，整个蚂蚁会在选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时的便是待优化正反馈的作用下集中到最佳的路径上，此时的便是待优化问题的最佳解。问题的最佳解。模型建立与求解模型建立与求解问题一：问题一：1.1.蚁群算法蚁群算法( (一一) )、将三维坐标形成成本矩阵，即孔孔之间的刀具转换、将三维坐标形成成本矩阵，即孔孔之间的刀具转换成本和行进成本之和。成本和行进成本之和。( (二二) )、采用蚁群算法进行计算、采用蚁群算法进行计算。模型建立与求解模型建立与求解问题一：问题一：1.1.蚁群算法蚁群算法初始化随机放置蚂蚁以每一只蚂蚁所在孔，作为起

9、始城市选择选下一个城市返回到初始城市还有可选城市？更新信息素矩阵，即更新每路径上的信息素的量满足停止条件？输出最好的路径YesNoNo模型建立与求解模型建立与求解问题一：问题一：1.1.蚁群算法蚁群算法成本成本：1197.21197.2元元时间时间：1382.21382.2秒秒模型建立与求解模型建立与求解问题一：问题一：2.2.贪心算法贪心算法( (一一) )、换刀方案、换刀方案：d,e,f,g,h,a,b,c,fd,e,f,g,h,a,b,c,f( (二二) )、换刀时间：、换刀时间：180180秒秒( (三三) )、权值：距离、权值：距离模型建立与求解模型建立与求解问题一：问题一：2.2.

10、贪心算法贪心算法算法流程图模型建立与求解模型建立与求解问题一：问题一：2.2.贪心算法贪心算法作业时间：作业时间：267.68267.68秒秒成本：成本：932.19932.19元元d d刀具加工图刀具加工图( (单位：单位：mil)mil)模型建立与求解模型建立与求解问题一：问题一：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-5

11、04-523-528-531-533 -536-524-517-513-509-505-520-521-527-530 -536-524-517-513-509-505-520-521-527-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-49

12、1-496-495-483-换换h h刀具刀具g g刀具走刀路线：刀具走刀路线：模型建立与求解模型建立与求解问题一：问题一：2.2.贪心算法贪心算法权重系数cst10.90.80.70.60.50.40.30.20.10csf00.10.20.30.40.50.60.70.80.91费用(元)965.12965.12965.12965.12965.12965.12965.12956.38960.48932.27944.27时间(秒)214 214 214 214 214 214 214 3203734951084最终选择最终选择cstcst=0.6,csf=0.4=0.6,csf=0.4计算出

13、总费用为计算出总费用为965.12965.12元，加工时间为元，加工时间为214214秒秒模型建立与求解模型建立与求解问题一：问题一：2.2.贪心算法贪心算法遗传算法流程图遗传算法流程图遗传算法实质是通过种群搜索技术，根据适者生存原则逐代遗传算法实质是通过种群搜索技术，根据适者生存原则逐代进化，最终得到最优解或准最优解进化，最终得到最优解或准最优解。采用采用“改良圈改良圈”算法得到优良父代算法得到优良父代开始开始对父代进行交叉，变异，形成新种群对父代进行交叉，变异，形成新种群计算种群中个体的适应度值，并选择优良子代计算种群中个体的适应度值，并选择优良子代1 1满足遗传代满足遗传代输出结果输出结

14、果结束结束1 1模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法改良圈算法改良圈算法：（以：（以m=233m=233）为例）为例改良圈算法是一种经典的近似算法，用于优化遗传算法的初始种群，改良圈算法是一种经典的近似算法，用于优化遗传算法的初始种群， 令令i=1i=1，第一步：随机生成初始圈（初始解）：，第一步：随机生成初始圈（初始解）：第二步：交换第二步：交换u u，v v之间的顺序，则得到新路径之间的顺序，则得到新路径：11111233.uuuvvvC 11111233.uvvuuvC C=C=C C= =u uv vv vu u? ?模型建立与求解模型建

15、立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法改良圈算法：改良圈算法：评判标准为两次相邻路径的差值：评判标准为两次相邻路径的差值：1111()()uvuvuuvvfdddd 若若f0 ,f0 ,则以新路径替换旧路径，直到不能修改为止。则以新路径替换旧路径，直到不能修改为止。第三步：令第三步：令i=i+1i=i+1，若，若i=POPi=POP（种群规模）（种群规模）, ,算法结束，否则转向第一步算法结束，否则转向第一步C=C=C C= =u uv vv vu u0f模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法遗传算法的实现：遗传算法的实现

16、：编码策略采用十进制编码，用随机数列编码策略采用十进制编码，用随机数列作为染色体作为染色体( (个体个体) )，其中为避免在交叉后产生的染色体出现重复的基因，其中为避免在交叉后产生的染色体出现重复的基因（孔编号），限定（孔编号），限定 01i12330,1122 3 3. 2332331 1模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法）（232,3 , 2i遗传算法的实现：遗传算法的实现：（2 2）种群初始化：）种群初始化：本文利用改良圈算法得到一个规模为本文利用改良圈算法得到一个规模为5050的种群。的种群。（3 3）交叉）交叉根据孔数的规模，本文采用

17、单点交叉方案，取交叉概率根据孔数的规模，本文采用单点交叉方案，取交叉概率pc=1pc=1。先从种群。先从种群中随机选取两个父代（两个初始解）中随机选取两个父代（两个初始解）11和和22：2222211111111222112342122232233212342122232233. ，用用Logistic Logistic 混沌序列产生一个混沌序列产生一个2 2到到232232之间的正整数，例如得到随机数之间的正整数，例如得到随机数2121，则对相应基因进行交叉得到新染色体。则对相应基因进行交叉得到新染色体。1112221122 3 32122 3 3.，2332331 112332331 12

18、模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法遗传算法的实现：遗传算法的实现：(4)(4)变异变异是实现群体多样性的一种手段，是跳出局部最优，全局寻优的重要保证。本模型是实现群体多样性的一种手段，是跳出局部最优，全局寻优的重要保证。本模型中具体变异算子设计如下，首先根据给定的变异率中具体变异算子设计如下，首先根据给定的变异率( (本模型选为本模型选为 0.02) 0.02)，随机地取两个在，随机地取两个在2 2 到到232232之间的整数，对这两个数对应位置的基因进行变异，具体变异以当前的基因值为之间的整数，对这两个数对应位置的基因进行变异，具体变异以当前

19、的基因值为初值利用初值利用LogisticLogistic混沌序列进行适当次数的迭代，得到变异后新的基因值，从而得到新混沌序列进行适当次数的迭代，得到变异后新的基因值，从而得到新的染色体的染色体。模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法遗传算法的实现：遗传算法的实现：（5 5）选择）选择本文选取目标函数作为适应度函数，选择上述所有个体中适应度函数本文选取目标函数作为适应度函数，选择上述所有个体中适应度函数最小的最小的5050个个体作为下一代个体。个个体作为下一代个体。采用圆盘赌法：采用圆盘赌法：计算适应度函数值计算适应度函数值FitnessFitne

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

21、7892.97元；元；时间：时间：242.9s242.9s换刀路径图换刀路径图打孔路径图打孔路径图模型建立与求解模型建立与求解问题一：问题一：3.3.遗传结合贪心算法遗传结合贪心算法成本：成本：892.97892.97元；元；时间：时间：242.9s242.9s成本：成本：1197.21197.2元，时间为元，时间为1382.21382.2秒秒蚁群算法：蚁群算法：贪心算法：贪心算法：成本成本：932.19932.19元；元；成本：成本：267.6754267.6754秒秒遗传结合贪心算法：遗传结合贪心算法：模型建立与求解模型建立与求解问题一：问题一：结论：结论：模型建立与求解模型建立与求解问题

22、二：问题二：钻头一：钻头一：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 秒秒模型建立与求解模型建立与求解问题二：问题二：2.2.贪心算法贪心算法 钻头一钻头二，钻头一钻头二，d d刀具的加工图刀具的加工图模型建立与求解模型建立与求解问题二：问题二：钻头一：钻头一：总时间：总时间：213.909213.909秒秒，总花费：总花费：360.66360.66元元( (其中换刀

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

24、c)2413(c)2414(c)2728(f)钻 头 一 坐标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.1667169198808

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

26、关系双钻头和钻间距与加工费用和时间的关系模型建立与求解模型建立与求解问题二：问题二：2.2.贪心算法贪心算法1 .1260407. 55515. 02xxy x:x:是合作间距是合作间距y:y:是加工费用是加工费用合作间距合作间距函数：函数：29.2565833. 00595. 02xxyx:x:是合作间距是合作间距 y:y:是加工时间是加工时间费用函数：费用函数：钻头同时工作时的生产效能，提出以下两种分配方案：钻头同时工作时的生产效能，提出以下两种分配方案：首先采用首先采用K-meansK-means聚类分析方法，以合作间距为依据将所有孔聚类分析方法，以合作间距为依据将所有孔分为两大类，采用

27、遗传结合贪心算法对两大类分别计算得到最分为两大类，采用遗传结合贪心算法对两大类分别计算得到最优路径。优路径。第一类初始类中心为：（第一类初始类中心为：（-325400,554800-325400,554800）第二类初始类中心为：（第二类初始类中心为：（88800,91980088800,919800）模型建立与求解模型建立与求解问题二：问题二：聚类分析聚类分析3.3.遗传结合贪心算法遗传结合贪心算法模型建立与求解模型建立与求解问题二：问题二：3.3.遗传结合贪心算法遗传结合贪心算法聚类结果：聚类结果：双钻头打孔算法流程图双钻头打孔算法流程图开始开始聚类为两类聚类为两类输出下一起点输出下一起点

28、结束结束按方案三，对两类分别计算按方案三，对两类分别计算模型建立与求解模型建立与求解问题二：问题二：3.3.遗传结合贪心算法遗传结合贪心算法其中第一个钻头路径图其中第一个钻头路径图模型建立与求解模型建立与求解问题二：问题二：3.3.遗传结合贪心算法遗传结合贪心算法钻头一：钻头一：钻头二：钻头二：总时间：总时间：207.5s207.5s作业成本：作业成本：942.392942.392元元模型建立与求解模型建立与求解问题二：问题二：3.3.遗传结合贪心算法遗传结合贪心算法单钻头：单钻头：总加工时间：总加工时间：242.9s242.9s总加工费用：总加工费用：892.97892.97元元双钻头：双钻

29、头：总时间：总时间：207.5s207.5s作业成本：作业成本：942.392942.392元元结论：结论：与单钻头相比，双钻头加工可以明显缩短加工时间，提高效与单钻头相比，双钻头加工可以明显缩短加工时间，提高效率率14.5%14.5%，但费用有增加，但费用有增加5.5%5.5%。模型建立与求解模型建立与求解模型评价及改进模型评价及改进本文亮点：本文亮点：1.1.结合作业孔的作业要求，以目标权重（时间，成本结合作业孔的作业要求，以目标权重（时间，成本或时间成本的加权和）为或时间成本的加权和）为“距离距离”构造一个非对称的图，进构造一个非对称的图，进一步建立了一个理论上相对完备的数学模型（一步建

30、立了一个理论上相对完备的数学模型（TSPTSP模型），理模型），理论上该模型的最优解就是全局最优解。论上该模型的最优解就是全局最优解。 2. 2.本文采用了改进的贪心算法以减少换刀次数为原则分本文采用了改进的贪心算法以减少换刀次数为原则分别对问题一和问题二进行了有效求解获得的较好结果。别对问题一和问题二进行了有效求解获得的较好结果。 3. 3.通过引入遗传算法并结合贪心算法进一步改进了上述通过引入遗传算法并结合贪心算法进一步改进了上述结果，且在双钻头模型中引入聚类分析方法进行了作业孔自结果，且在双钻头模型中引入聚类分析方法进行了作业孔自动分区。动分区。 4. 4.详细计算讨论了在第二种方法下，合作间距对作业时详细计算讨论了在第二种方法下，合作间距对作业时间和成本的影响并得出相应结论；间和成本的影响并得出相应结论； 1.1.遗传算法容易出现早熟收敛。遗传算法容易出现早熟收敛。2.2.程序计算速度慢。程序计算速度慢。3.3.问题二处理较为简单，若能采用其他分区方法进行处理效问题二处理较为简单，若能采用其他分区方法进行处理效果可能更好。果可能更好。模型评价及改进模型评价及改进不足不足：谢谢！谢谢！