论文研究-造船监理员调度模型和混合遗传算法求解.pdf

所需积分/C币:9 2019-09-13 00:31:16 535KB .PDF
0
收藏 收藏
举报

有效快速地调度不同专业的造船监理员至不同厂区进行监理工作可以提高船舶建造效率,确保船只建造质量。针对我国造船监理公司监理员调度方面缺乏通用模型和调度手段落后的问题,建立起带有一系列硬性约束和软性约束的数学模型。随后针对该数学模型采用了基于模拟退火遗传算法的混合遗传算法进行求解。模拟仿真实验表明该模型与算法取得了理想效果。
2402014,50(21) Computer Engineering and Applications计算机工程与应用 调度情况越满足需求时值越大,即评价硬性约束满足状间默契程度的权重系数.其值由相应管理人员根据实际 况的奖励函数,得: 情况赋值。 (gn(X)=∑∑(c-∑Ox一n1D i=Ik=l 4基于模拟退火遗传算法的问题求解 冉把式(4)引入到H标数式(1)中,可得 4.1模拟退火遗传算法 minf=∑∑1x-4∑∑(-∑°x-nAD)(5) 遗传算法( Genetic∧ aIgorithms)是模拟达尔文生物进 =1= 化论的自然选择和遗传学机理的牛物进化过程的计算模 即要研究的只考虑硬性约束时的目标函数。由于型是一种通过模拟自然进化过程搜索最优解的方法"1。 付名监理工将作为特定单一专业工种的单位进行调度遗传算法广泛应用传统搜索方法难以解决的高度复 以满足实际需求所以在求解本目标函数过程中对于掌杂的线性领城,且在组合优化方面展示了良好的优越 握多种专业技能的监理员会自动淘汰其不大满足调度性。因此,将遗传算法应于本文研究的问题是可行的。 需求的专业,侏留其最佳专业进行调度。 虽然遗传算法是一种通用的全局优化算法,但是遗 为了使得调度人性化,下面将进一步考虑监理员之传算法局部搜索能力却较差。而遗传算法中每一代群 间默契程度和监理员对工作地点的偏好,建立一个造船体的优良度直接影响后代的优良度与整个算法的效率。 监理员调度问题扩展模型 大量的研究表明遗传算法性能可以通过结合局部搜索 在日常生活工作中,监理员之间的默契程度并非一步骤进行改善。这样的算法通常被称作“混合算法”。 致。有些监理员之间配合默契,T作效率高;相反,有些模拟退火算法( Simulated Annealing)是基于 Monte Carlo 监理员之间关系不佳,在起共事可能会造成不必要的迭代求解策略的一种随机寻优算法,其出发点是基于固 损失。监理员间配合默契程度是衠量不同监理员分配体物理退火过程与组合优化之间的相识性,模拟退火 在同一厂区L作时相互合作的效率和服务质量的指标,算法由某一较高温度开始,利用具有概率突跳特性的 相应管理人员可以针对实际情况(例如根据实际的利润 Metropolis抽样策略在解空间中进行随机搜索,伴随温 和损失等)对某些监理员之间的默契关系进行量化,对度不断下降重复抽样过程。固体内部粒子随温升变为 默契程度特别佳的给定个正值,对默契程度尤为不好无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个 的给定一个负值,而对其他默契程度不突出的设为0。温度都达到平衡态,最后在常温时达到基态,内能减为 在极端的情况监理员两两之间默契程度都不为0,这时最小,模拟退火算法是一种局部搜索能力很强的算法叫。 候监理员之间默契程度用一个nXn的矩阵R表示;对将模拟退火的思想引入遗传算法,对交叉和变异后的个 丁一般情况,表示造船监理员间默契程度的R是一个稀体实施 boltzmann按受策略,不但增强了遗传算法的全 疏矩阵。从而对于任意调度方案,都可以对每个厂区计局收敛性,并且使遗传算法在进化后期有较强的爬山性 算分配到该丿区监理员之间默契程度的总和,再汇总求能,加快了进化后期的收敛速度,形成模拟退火遗传算 和计算出该调度方案下默契总值p。 法,可以有效缓解遗传算法的压力“。针对本文研究 造船监理员对工作地点(即厂区)的偏好是指允许的问题,将遗传算法与模拟退火算法结合起来,使用模 监理员根据自己的身体状况、家庭状况、作息习惯和风拟退火遺传算法,以提升遗传算法局部搜索能力,从而 俗习惯等多方面因素,自行确定对工作地点(厂区)的偏对性能进行改善。 好,以供制作调度方案时参考。监理员对于厂区的偏好4.2基丁模拟退火遗传算法的问题求解流程 程度也分为正值、0和负值:表示监理员对厂区的偏好 本文采用实值编码方式,个体长度为待调度的造船 程度的是一个nxm的矩阵,用L来表示。 监理员人数,其中个体中每个元素的值表示该监理员被 监理员之间默契程度和他们对T作地点的偏好程度派往的1。这样的编码方式可以白动满是约束式(2)。 这两个约東属于钦性约東,考虑上述约東将有助于提高 本文研究的问题一个主要方面是差旅费开销。根 他们工作的积极性和质量。为了不降低获得叮行解的机据实际情况,在一次调度前可以知道上一个调度周期所 会,它们将被转化到目函数中:用目标函数式(6)替代待调度监理员所处的厂区和此次调度周期厂区对监 式(5)。于是得到一个扩展的造船监理员调度问题模型。理员相应需求情况。根据这些数据,用计算机可以快速 min f= C∑( 少-al)x 计算出哪些}区对哪些专业监理员需求人数超出已有 人数(即本次调度前已在此厂区的相关监理员人数),而 (6)这些厂区的相应监理员是无需调度到其他厂区的。这样 在不考虑软性约束时事先确定哪些造船监理员不必要调 其中表示第名监理员对第j个厂区的偏好程度;a度到其他厂区,从而能生成让这些监理员原地待命的初 和β分别为造船监理员对工作地点偏好和造船监理员始群体。同时为俫证初始群体的多样性,随机生成其他 符吴,葛洪伟,邵长鲁,等:造船监理员调度模型和混合遗传算法求解 20l4,50(21)241 监理员所派往的厂区编号。并且为更好地考虑到软性约 表示监理员之间默契程度的矩阵R为15×15的 束,随机选取任意“原地待命”的监理员随机生成他们所矩阵,令1=-1,其他元素都为0;表示15名监理员 派往的厂区。这样启发式生成初始种群的优势是能生成地点偏好的矩阵为15×5的矩阵,其中l=l1.= 性能较好的个体,提高算法的进化速率。虽然启发式生 1,其他元素值为0;表示监理员掌握专业的矩阵 成初始种群可能会增大运行开销,但是实验表明,这部分 开销在研究的问题整体规模中是极小的且可接受的。 O为: 般来说,遗传算法屮适应度计算最费时问,而且 10000 01000 需要不断产生新一代,每一代又有若干个体,提高遗传 10000 算法的运行速度显得尤为重要。出于遗传算法的内在 00100 并行机制.并行处理将有效地改善遗传算法的性能。迁 10000 移( migration)是并行遗传算法引入一个新的算子并在 01000 进化过程中使子群体互相交换个体的过程。本文将 00100 使用迁移策略将子群体中最好的个体发给其他的」群 O=00001 01000 体,通过迁移可以加快较好个体在群体屮的传播。算法 0001 流程如下 00010 步骤1输入监理员数量n、厂区个数m;输入差旅 00010 费矩阼T、专业矩阵O,人际关系矩阵R及地点偏好矩 00100 0001 阵L内元素的值 0000 步骤2启发式方法生成初始群体;输入遗传算法配 表示厂区对不同专业监理员需求人数的矩阵为 置参数;设定初始温度冮终止温度lm,温度下降率ν, 10020 1=1以及局部搜索参数v等运行参数。 0 步骤3采川遗传算法对种群进行交叉、变异、非线 1002 性排序和选择。 0 00300 步骤4对于种群中的每个个体调用模拟退火算法 步骤5更新温度i(t>t-n) then t=v;香则算法 本文使用的算法运行参数如表2和表3 结東,输出调度结果。 表2求解过程中堪本遗传算法使用的参数 步骤6转到步骤3 参数名 参数值 种样数量 0.7 5实验结果及分析 交叉率 变异率 0.01 仿真环境的运行平台为 Matlab,在 Core 152.3GHL 父代个体保留率 的CPU和4 GB RAM的PC上运行。为了方便说明和 验证,选用一组规模较小并且典型的数据进行测试。假 max(N) 设共有15名造船监理员,掌握5个不同的专业,其中 1000 位监理员同时掌握两个专业;共有5个厂区。设定在调 1000 度前15名监理员平均分配到5个厂区。根据现实中机 表3求解过程中有关子种群和迁移使用的参数 票价格,设定表示15名监理员的差旅费矩阵T为: 子种群数量子种群的插入率迁移率迁移间隔 0580170017502160 10 0.9 0.2 10代 0580170017502160 0580170017502160 从算法描述中可以看出,算法外循环执行次数与 130 09109901610 130 09109901610 fm和v有直接联系。股来说,tm要取得足 130 9109901610 够大,使得能够接受劣解的概率比铰大,在初始时能几 1280 0451055 乎100%的概率接受劣解。但由于本次实殓数据规模 T=17001280 0451055 较小,经过多次实验,最后采用的有关模拟退火参数如 17001280 451055 02260 表4。 300112045 02260 表4求解过程中有关 13001120 02260 l2501130117010800 模拟選火相关参数 1250113011701080 0 250113011701080 2422014,50(21) Computer Engineering and Applications计算机工程与应用 表5仿真实验调度结果 监理员编号123456789101112131415 4142513 厂区编号1235334341425 2353343 1235334341 333 从以上的参数和实验数据描述可以看岀,第14名验参数和变量因问题规模的增大而相应变大。实验取 监理员冋时掌握第4和第5号专业;而所有厂区对第5号得理想结果。 专业监理员的需求是2,对第3和第4号专业的需求为4, 对其他专业需求人数都为3;第1号表示不愿与第15号6结東语 监理员共事;第10号监理员和第11号监理员更偏好第4 本文是对我国造船监理公司监理人员调度问题的 号厂区,而第12号监理员不愿去第I号厂区。在接下来一个初步研究,旨在探讨一种系统解决针对实际造船监 的仿真实验中将着重考察这些要求是否满足 理公司监理人员调度问题的思路与方法。根据我国船 运行20次,平均耗时为357s。图1给出了随机某舶建造监理的实际情况,归纳出一系列硬性约束和软性 次实验过程中最优解的变化,可以看出在较少的迭代次约東,并建立了一个较通用的造船监理人员调度的数学 数内就可以获得较理想最优解。注意图中最优解的值模型。同时所建立模型有较好的可塑性和可扩展性,不 只是本模型和算法得出的用于量化的值,并非真实费用同的船舶建造监理公司可以依据实际情况将自身的独 开销。 特要求以软硬约束的形式融入模型中。 148 在数学模型的基础上,宏观采用遗传算法对该问题 求解,通过启发式生成种群和引入迁移策略改进算法效 -1.50 率,并引入模拟退火算法改进遗传算法的局部搜索能 函 力。仿真实验验证了模型有效且算法有较好的执行效 率和鲁棒性,具有一定的实用价值和经济效袷。在未来 工-1.56 的研究屮,将进步改善模型和算法。 血-1.58 15 参考文献: 迭代次数 []张莹浅谈船舶监造的管理方法[中国水运,2010,10(8) 图1实验过程中最优目标函数解的变化 10-11 随机选取5次运行结果,实验结果(即调度结果)如21李海平船舶建造工程的监理工作门中国水运:学术版 2010,6(2):42-44 表5所示。 3] Sabar M, Montreuil B, Frayrel J M.A multi-agent-based 从以上实验结果可以看出,对于硬性约東要求,调度 approach for personnel scheduling in assembly centers[J] 结果都很好满足了厂区对各专业监理员人数的需求且没 Engineering Applications of Artificial Intelligence, 2009 有出现¨应留守却被调离”等这样的无意义调度;同时总 22(7):1080-1088 差旅是最少的,例如对于第6号监理员,如若人工调度[4] Sabar m, Montreuil b, Fravel J M.An agent- based alyy- 可能凭感觉做出将第6号监理员继续留在第2号厂区的 rithm for personnel shift-scheduling and rescheduling in 决定,但仿真实验结果表明,第6号监理员调度至第3号 flexible assembly lines[J]Journal of Intelligent Manufac- 厂区并将第2号和第9号监理员分別调度至第2号和第4 turing,2012,23(6):2623-2634 号厂区更加节省调度开销。除表5中第一个调度结果对51 Kabak C, Ulengin F, Aktas H, et al.Efficient shift sched 第1号监理员与第15号监理员默契程度没有考虑周到 uling in the retail sector through two-stage optimization] European Journal of Operational Research, 2008, 184(1) 外,其余调度结果都较好满足了有关人性化的软性约束 76-90 要求,体现了调度人性化,如第10号至第12号监理员对 [6] Bai Ruibin, Burke E K. Kendall G, et al. a hybrid evolu 特定厂区的偏好等要求都被充分满足。最优实验解和最 tionary approach to the nurse rostering problem[JJIEEE 差实验结果相比偏差约为0.635%,算法有较好的稳定性。 Transactions on Evolutionary Computation, 2010, 14(4) 为验证系统的实用性,继续根据某监理公司实际情580-590 况进行仿真实验,每次调度的监理员人数达到百人。实 (下转263页)

...展开详情
试读 5P 论文研究-造船监理员调度模型和混合遗传算法求解.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743481 如果觉得有用,不妨留言支持一下
2019-09-13
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-造船监理员调度模型和混合遗传算法求解.pdf 9积分/C币 立即下载
    1/5
    论文研究-造船监理员调度模型和混合遗传算法求解.pdf第1页

    试读结束, 可继续读1页

    9积分/C币 立即下载 >