《遗传算法解决TSP问题.pptx》由会员分享，可在线阅读，更多相关《遗传算法解决TSP问题.pptx（32页珍藏版）》请在三一办公上搜索。
1、作业调度问题,第八小组,作业调度问题的概念问题发展现状涉及的基本概念问题常见分类相关优化方法建立数学模型,近年来，随着先进制造技术的发展，作业调度问题的含义有所拓展，增加了随机性、动态性、不确定性、约束性、多目标等，与实际生产情况更接近，许多学者作了大量研究，出了不少研究成果。,发展现状,目前，人们对作业调度问题的研究已有几十年，但至今尚未形成一套系统方法和理论，理论研究与实际应用之间仍存在很大差距。,作业调度问题的概念,作业调度问题（Scheduling Problem）是针对一项可分解的工作，探讨在尽可能满足约束条件（如交货期、工艺路线、资源情况）的前提下，通过下达生产指令，安排其组成部分
2、（操作）使用哪些资源、其加工间及加工的先后顺序，以获得产品制造时间或成本的最优化。调度领域中的问题大多为NP完全问题。,生产周期（Makespan）：调度开始时间与终止时间之间的间隔，代表资源利用率，较短生产周期意味着较高资源利用率，常作为作业调度优化目标。关键路径（Critical Path）：就是最重要的路径，在这条路径上，所经过的时间是全部工程完工所需时间即生产周期，它是由美国杜邦公司提出。甘特图（Gantt Chart）：第一次世界大战时由Henry L Gantt首创使用，利用长条图显示所有任务，将任务画在表上，并显示开始、完成日期及持续时间。,作业调度问题中涉及的基本概念,单机调度
3、 多台并行机调度 流水车间调度（Flow-Shop）单件车间调度（Job-Shop）,常见分类,加工系统复杂程度生产任务是否预知生产环境特点和问题参数是否确定,静态调度 动态调度,确定性调度随机性调度,神经网络（Neural Networks）模拟退火法（Simulated Annealing）遗传算法（Genetic Algorithms）禁忌搜索法（Tabu Search）贪心算法（Greedy Algorithm）回溯算法,相关优化方法,问题的提出：n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业
4、i所需的时间分别为ai和bi。作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。,建立数学模型,设全部作业的集合为N=1，2，n。S N是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。作业调度问题的最优值为T(N,0)。由作业调度问题的最优子结构性质可知：,最近邻点法求解TSP问题,反例,AB垂直BC BC垂直CD(假设AB=BC=CD=10)假设从A出发,根据最近邻点法规则 按照ABCD的顺序总长
5、度约为52,如图 总长度约等于48 但其不是最近邻点法 所以反例找到.,最近插入法求解TSP问题,反例,从a开始，下面选bab，abc 1+2=3插入c acb 4.01所以选择abc，abcd 4插入d adbc 10003 abdc 20001所以最近插入法得到的最佳路径为abcd 长度为4,但是acdb 的长度：0.01+1+1=2.014于是找到了最近插入法的反例。,PSO算法思想与框架,将优化问题的每一个解称为一个微粒，每个微粒在n维搜索空间中以一定的速度飞行，通过适应度函数来衡量微粒的优劣，微粒根据自己的飞行经验以及其它微粒的飞行经验，来动态调整飞行速度，以期向群体中最好微粒位置飞
6、行，从而使所优化问题得到最优解,PSO算法基本思想,1）初始化粒子在搜索区域内根据随机产生的速度和位置初始化种群粒子，初始化粒子的个数应大于滤波器的阶数。初始搜索点的位置 及其速度 通常是在允许的范围中随机产生的，每个粒子的pbest坐标设置为其当前位置，且计算出其相应的个体极值（即个体极值点的适应度值），而全局极值（即全局极值点的适应度值）就是这些个体极值中最佳的，记录这个具有最佳值的粒子序号，并将gbest设置为该最佳粒子的当前位置。,PSO算法框架,2）评价每一个粒子 计算每一个粒子的目标适应度和约束适应度，首先比较粒子的约束适应度，约束适应度大的粒子靠前；如果约束适应度的值相等，再比较
7、其目标函数适应度，适应度值大的粒子靠前。将粒子目标适应度值与其经历过的最好位置pbest作比较，如果好于该粒子当前的个体极值，则用该粒子的位置替代其pbest，且更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值，则用该粒子的位置替代gbest，记录该粒子的序号，且更新全局极值。,3）粒子的更新每一次迭代开始计算按照某种方式变化的惯性权重，用公式对每一个粒子的速度和位置进行更新。4）检验是否符合结束条件如果当前的迭代次数达到了预先设定的最大迭代次数（或者达到最小错误要求），则停止迭代，转到步骤6，否则转到步骤2。5）判断求得解是否为可行解是可行解，将其记录，否则不记录。重复以上的步
8、骤，要求的全局迭代次数。6）得出最优解若求得可行优解，则从多次迭代得到的解中选择较好的解和最优解对应的目标函数输出。,遗传算法解决TSP问题,算法流程,/用矩阵表示出距离 提供问题的研究背景for(int i=0;i cityNumber;i+)for(int j=0;j cityNumber;j+)if(i=j)arrayij=0;else arrayij=(1+rand()%100);/表示距离在-100之间/设定初始种群for(int i=0;i groupsize;i+)for(int j=0;j cityNumber;j+)people(group,i,j,cityNumber);,
9、初始化,void people(int a100,int i,int j,int citynumber)aij=1+rand()%citynumber;if(j!=0)for(int count=0;count j;count+)if(aij=aicount)people(a,i,j,citynumber);,（初始化种群调用的函数）,评价适应值,int ngroupsize=;/声明一个数组存储路径和(适应值)/计算适应度函数直接用路径和表示for(int i=0;igroupsize;i+)for(int j=0;jcityNumber-1;j+)ni+=arraygroupij-1gro
10、upij+1-1;ni+=arraygroupicityNumber-1-1groupi0-1;,for(int i=0;i best40/2;i+)int change1=rand()%best40;int change2=rand()%best40;for(int j=0;j cityNumber;j+)groupbest40+i*2j=groupchange1groupchange2j-1;groupbest40+i*2+1j=groupchange2groupchange1j-1;,交叉,/变异 互换随机得到的个体的任意两个位置的城市序号for(int i=0;i best40/2;i
11、+)int random=best40*2;int change1=rand()%random;/随机选出变异的个体for(int j=0;jcityNumber;j+)group2*best40+ij=groupchange1j;int change2=rand()%cityNumber;int change3=rand()%cityNumber;group2*best40+ichange2=groupchange1change3;group2*best40+ichange3=groupchange1change2;,变异,将最优解导入文件中,（头文件）,(导出每代最优解）,（导出最终的最优解并关闭文件）,（打开文件）,图表分析,（1）控制框截图,（2）导出数据截图,（3）Excel图表截图,Thank you,
