遗传算法解决TSP问题.pptx

作业调度问题 第八小组 作业调度问题的概念问题发展现状涉及的基本概念问题常见分类相关优化方法建立数学模型 近年来 随着先进制造技术的发展 作业调度问题的含义有所拓展 增加了随机性 动态性 不确定性 约束性 多目标等 与实际生产情况更接近 许多学者作了大量研究 出了不少研究成果 发展现状 目前 人们对作业调度问题的研究已有几十年 但至今尚未形成一套系统方法和理论 理论研究与实际应用之间仍存在很大差距 作业调度问题的概念 作业调度问题 SchedulingProblem 是针对一项可分解的工作 探讨在尽可能满足约束条件 如交货期 工艺路线 资源情况 的前提下 通过下达生产指令 安排其组成部分 操作 使用哪些资源 其加工间及加工的先后顺序 以获得产品制造时间或成本的最优化 调度领域中的问题大多为NP完全问题 生产周期 Makespan 调度开始时间与终止时间之间的间隔 代表资源利用率 较短生产周期意味着较高资源利用率 常作为作业调度优化目标 关键路径 CriticalPath 就是最重要的路径 在这条路径上 所经过的时间是全部工程完工所需时间即生产周期 它是由美国杜邦公司提出 甘特图 GanttChart 第一次世界大战时由HenryLGantt首创使用 利用长条图显示所有任务 将任务画在表上 并显示开始 完成日期及持续时间 作业调度问题中涉及的基本概念 单机调度多台并行机调度流水车间调度 Flow Shop 单件车间调度 Job Shop 常见分类 加工系统复杂程度生产任务是否预知生产环境特点和问题参数是否确定 静态调度动态调度 确定性调度随机性调度 神经网络 NeuralNetworks 模拟退火法 SimulatedAnnealing 遗传算法 GeneticAlgorithms 禁忌搜索法 TabuSearch 贪心算法 GreedyAlgorithm 回溯算法 相关优化方法 问题的提出 n个作业 1 2 n 要在由2台机器M1和M2组成的流水线上完成加工 每个作业加工的顺序都是先在M1上加工 然后在M2上加工 M1和M2加工作业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垂直BCBC垂直CD 假设AB BC CD 10 假设从A出发 根据最近邻点法规则按照A B C D的顺序总长度约为52 如图总长度约等于48但其不是最近邻点法所以反例找到 最近插入法求解TSP问题 反例 从a开始 下面选ba b a b c1 2 3插入ca c b4 01所以选择a b c a b c d4插入da d b c10003a b d c20001所以最近插入法得到的最佳路径为a b c d长度为4 但是a c d b的长度 0 01 1 1 2 01 4于是找到了最近插入法的反例 PSO算法思想与框架 将优化问题的每一个解称为一个微粒 每个微粒在n维搜索空间中以一定的速度飞行 通过适应度函数来衡量微粒的优劣 微粒根据自己的飞行经验以及其它微粒的飞行经验 来动态调整飞行速度 以期向群体中最好微粒位置飞行 从而使所优化问题得到最优解 PSO算法基本思想 1 初始化粒子在搜索区域内根据随机产生的速度和位置初始化种群粒子 初始化粒子的个数应大于滤波器的阶数 初始搜索点的位置及其速度通常是在允许的范围中随机产生的 每个粒子的pbest坐标设置为其当前位置 且计算出其相应的个体极值 即个体极值点的适应度值 而全局极值 即全局极值点的适应度值 就是这些个体极值中最佳的 记录这个具有最佳值的粒子序号 并将gbest设置为该最佳粒子的当前位置 PSO算法框架 2 评价每一个粒子计算每一个粒子的目标适应度和约束适应度 首先比较粒子的约束适应度 约束适应度大的粒子靠前 如果约束适应度的值相等 再比较其目标函数适应度 适应度值大的粒子靠前 将粒子目标适应度值与其经历过的最好位置pbest作比较 如果好于该粒子当前的个体极值 则用该粒子的位置替代其pbest 且更新个体极值 如果所有粒子的个体极值中最好的好于当前的全局极值 则用该粒子的位置替代gbest 记录该粒子的序号 且更新全局极值 3 粒子的更新每一次迭代开始计算按照某种方式变化的惯性权重 用公式对每一个粒子的速度和位置进行更新 4 检验是否符合结束条件如果当前的迭代次数达到了预先设定的最大迭代次数 或者达到最小错误要求 则停止迭代 转到步骤6 否则转到步骤2 5 判断求得解是否为可行解是可行解 将其记录 否则不记录 重复以上的步骤 要求的全局迭代次数 6 得出最优解若求得可行优解 则从多次迭代得到的解中选择较好的解和最优解对应的目标函数输出 遗传算法解决TSP问题 算法流程 初始化 用矩阵表示出距离提供问题的研究背景for inti 0 i cityNumber i for intj 0 j cityNumber j if i j array i j 0 elsearray i j 1 rand 100 表示距离在 100之间 设定初始种群for inti 0 i groupsize i for intj 0 j cityNumber j people group i j cityNumber 初始化 voidpeople inta 100 inti intj intcitynumber a i j 1 rand citynumber if j 0 for intcount 0 count j count if a i j a i count people a i j citynumber 初始化种群调用的函数 评价适应值 intn groupsize 声明一个数组存储路径和 适应值 计算适应度函数直接用路径和表示for inti 0 i groupsize i for intj 0 j cityNumber 1 j n i array group i j 1 group i j 1 1 n i array group i cityNumber 1 1 group i 0 1 for inti 0 i best40 2 i intchange1 rand best40 intchange2 rand best40 for intj 0 j cityNumber j group best40 i 2 j group change1 group change2 j 1 group best40 i 2 1 j group change2 group change1 j 1 交叉 变异互换随机得到的个体的任意两个位置的城市序号for inti 0 i best40 2 i intrandom best40 2 intchange1 rand random 随机选出变异的个体for intj 0 j cityNumber j group 2 best40 i j group change1 j intchange2 rand cityNumber intchange3 rand cityNumber group 2 best40