下载  >  开发技术  >  其它  > 论文研究-求解RCPSP的一种改进化学反应算法 .pdf

论文研究-求解RCPSP的一种改进化学反应算法 .pdf 评分

求解RCPSP的一种改进化学反应算法,郑环宇,王凌,针对资源约束项目调度问题(RCPSP)提出了一种改进的化学反应算法(CRO)。一方面对局部搜索、交叉和变异操作进行改进,另一方面通�
国武技论文在线 http:/www.paper.edu.cn 初始化 paphumber^分子 满足终止条件 是叫输出评价缁果 阬机选择一个 是<奔是单分 随机选择两个 分子 文应? 是是{满足分否 否<是百清尼合是 分解榮作 与筒壁轻微碰 分子间羟微碰 撞操作 撞架作 合成荣作 对新生成分子进行评价 更新最优解 图1CRO算法框架 改进化学反应算法 本节首先说明文献CRO- RCPSP算法2存在的问题,进而对算法进行收进。改进算法的 75框架同图1,其中斜体标出的5个模块体现对文献方法的改动部分 原 算法 原 CRO-RCPSP算法2的四种核心操作中,墙壁轻微碰撞操作和分子间轻微碰撞操作都 应用局部搜索算子,分解操作可认为使用两次变异算子,合成架作使用交叉算子,但只保留 其中一个解。局部搜索算子是在活动列表中交换任选两个位置活动以生成新的任务列表;变 80异算了是循环移位操作,即随机产生个整数∈[-,],如果>0则将整个活动列衣向右 移动位,如果<0则间左移动位,如果=0则不动;交叉算子是文[18]提出的距离保持 交叉( distance preserving crossover,DPX),即将与父母位置相同的活动拷贝到子女的活动 列表,其他位置的活动则随机分配且不同于父母。另外,原CRO- RCPSP算法用活动列表编 码,并用串行调度产牛规则解码。 85 最近,文[19]提出了扩展活动列表( extended activity list,EAL)编码,缩短了FBI前向 反向改进的搜索时间。EAL编码规则使用三个列表:活动列表∏、活动开始时间列表 活动结束时间列表。图2给出一个调度的EAL编码规则 3 国武技论文在线 http:/www.paper.edu.cn 2 5 12345678910111213141516 π2315467 ST00225912 FT225491214 图2一个调度和其对应的EAL 图3显示了利用EAL编码时FBI的每个步骤。为了缩短图2调度的工期,FBI将所有 活动按照结束时间F进行降序排列,并将所有活动尽量向右排列。例如,活动6和7都不 能再向右放,但活动1可向右移动到结束时间为12的位置。然后再将所有活动尽量向左排 95列。由图可见,调度期由原来的14缩短为13。因此,本文也使用EAL编码,并在SSGS 解码中加入FBI机制能够缩小工期 ST00225912 3 6 351467 sT00225912 2:45678910111213141516 FT224591214 2351467 T|13395912 FT|3551291214 12345678910111213141516 u2354167 2249121214 6 4 ST0024881⊥ ≯FT2248111113 L23456789l0111213141516 图3基于EAL的FB 100 局部搜索、交叉、变异算子 原算法中局部搜索、交叉、变异算子由于没有考虑 RCPSP问题的特质,很可能产生不 4 国武技论文在线 http:/www.paper.edu.cn 可行解,浪费计算量。例如,如果将3.2节问题的EAL的首行(即AL)从[2315467变成 [2317465],即将活动5和活动7的位置互换,则解码后的调度不变,局部搜索失效。类似 地,交叉和变异算子也会产牛失效的情况。文[20提出了几种交叉算子,其中两点交叉 105(two- point crossover)较其他算子更有效。文[21提出的局部搜索算子( permutation based local search,PBLS)也取得了较好结果。因此,木文采用这两和基于 RCPSP的算子,由于 这两种算子产生的解为可行解,于是可改善算法效率 两点交叉算子首先产满足1≤1≤2≤的两个随机整数1,2,AL中1≤≤1位置 的基因由母亲基因直接继承,即 ;1+1s≤2的基因由父亲继承,但要异于之 110前位置的基因,即 min,,≠{1,…,1};剩下2+1≤≤位置的基 因仍由母亲基因继承,但也要异于之前位置的基因,即 min .{1…,}。例如,图4中1=2,2=5,子女前两位基 因继承于母亲,中间三位继承于父亲,最后一位继承于母亲。可以证明,如果父母的AL都 满足活动优先约束,则子女的AL也满足活动优先约束。 Mother: 1 6 C1 Father:/3 461 Child:[123546 图4两点交叉算子 PBLS首先给定变异概率,对所有1≤ 1位置基因,和进行概率 的交换,并要求交换的两位基因满足活动优先约束。木文的变异算子采用PBLS 120 仿真测试和比较 实验设置 本文采用Ⅴ isual studio208C艹编程仿貞,计算机为 Lenovo ideapad z465,处理器为 aMd Phenom II n9302GHz四核,内存2GB。测试数据集来自于 PSPLIB,包括标准测试集 J30(480个问题,每个问题包含30个活动),J60(480个问题,每个问题包含60个活动), 125J120(600个问题,每个问题包含120个活动)。J30的工期下界是穷举后的最小工期,J60 和J120的工期下界是理论下界。现有的文献大多使用1000、5000、50000次评价作为停止 准则,本文也使用此准则。同时,使用如下平均偏差( Avcragc Deviation,ARV)进行比较: ∑ 其中, 是第个问题的工期, 是第个问题的工期卜界,是 130问题的个数。ARⅴ越小则说明算法的效果越好。 改进算法与原 的比较 首先测试原算法(CRO),然后加入FBI搜索机制(CRO+FBI),最后改变局部搜索、 国武技论文在线 http:/www.paper.edu.cn 交叉、变异算了(改进CRO),以探究各改进步骤对整体算法的影响。原算法的参数如表 12,其他算法采用相同的参数。另外,局部搜索和变异的 两两交换概凇分别设置为 135 0.4 =0.7。改进CRO各参数含义如衣2。 由于 PSPLIB中每10个问题的产生机制相同,此处选取J30的48个问题、J60的48个 问题、J20的60个问题进行仿真,结果如表3-5所示,数值均为×100。由表可见, 对于三种规模的问题,FBⅠ搜索的加入以及局部搜索、交叉、变异算子的改动都能逐步提升 算法的性能。改进CRO大幅度改善了原CRO算法求解 RCPSP的性能。 l40 表1CRO算法参数 10 0.5 .2 10000 200 l00 表2改进CRO算法参数含义 参数 含义 初始分子个数 与堵壁轻微碰撞操作动能损失限度 分子间反应操作占总操作百分比 各分子初始动能 发生分解操作阈值 发生合成操作阈值 局部搜索 两两交换概率 变异 两两交换概率 145 表3J30三个算法仿真结果 J30 1000 5000 50000 CRO 1.5683 1.0936 0.7749 CRO+ FBI 0.4773 0.3586 0.2151 进CRO 0.6774 0.2757 0.1082 表4J60三个算法仿真结果 60) 1000 5000 50000 CRO 15.1789 13.8953 CRO+ FBI 12. .3803 1.3875 改进CRO 117355 10.9062 10.4118 表5J20个算法仿真结果 J120 1000 5000 50000 CRO 50.5355 48.7908 45.8731 CRO+ FBI 38.7702 37.7099 36.5635 改进CRO 35.6299 34.1439 32.4003 150 基于 的参数分析 基于 Taguchi试验设计方法( design of experimen,DOE)2对改进CRO的参数进行分 析。使用J30的48个问题,J60的48个问题,J120的60个问题进行DOE实验。首先沿用 表1参数,仅对 和 两个参数进行4个因素水平的DOE试验,并选取5000次 155评价作为终止准则。这些参数的因素水平组合见表6。J30、J60、J120的统计结果如表7所 示。进而,绘制每个参数对于三种规模问题的趋势图,如图5-7所示。 国武技论文在线 http:/www.paper.edu.cn 160 表6改进CRO中 的因素水平 参数 亲水平 4 0.1 0.2 0.3 0.4 0.5 0.7 0.9 表7 和 的正交试验表和ARV值 实验编 因素 J30 J60 J120 1 0.006650 0.115928 0.348103 2 2 0.008100 0.120289 0.352441 3 0.005710 0.L19743 0.353919 4 4 0.006355 0.116807 0.352263 0.005480 0.113974 0.346625 6 0.005349 0.114810 0.344431 0.004927 0.116460 0.34 2 0.004233 0.113845 0.348488 0.006940 0.110466 0.342120 10 0.002702 0.10836 0.343126 11 0.001774 0.111131 0.341772 4 0.003496 0.112455 0.3866 0.002927 0.110528 0.339611 0.002180 0.110752 0.341300 4 0.002808 0.109465 0.339588 16 0.002680 0.110051 0.340632 PparB 0.007 0.006 0.00 0.004 0.003 0.1 165 图5J30的因素水平趋势图 国武技论文在线 http:/www.paper.edu.cn PperA 0.]19 0.11 0.115 0.114 0.113 C.9 图6J60的因素水平趋势图 Pper B 0,348- 0,346 0,344 0,310 C. L 0.2 0.3 C.4 0. 0 0.9 170 图7J120的因素水平趋势图 由此,得出求解J30、J60、J120最好的和参数配置,如表8所示。可见, 算法对不同问题的参数较为稳定,只有J30有所不同 175 表8最佳 和 参数组合 问题集 J30 0.4 0.7 J60 0.3 120 0.4 然后,对表2参数进行4个因素水平的DOE试验,参数的因素水平组合见表9,而 和 使用表8值。J30、J60、J20的统计的结果如表10所示,相应的趋势图如图8-10 180所小。进而,得出求解J30、J60、J120最好的参数配置如表11所小,这也是我们最终设置 改进CRO的参数。 8 国武技论文在线 http:/www.paper.edu.cn 表9改进CRO中其他参数的因素水平 公数 囚素水平 100 200 0.3 0.5 0.7 0.9 0.1 0.2 0.4 0.6 0.8 l00 1000 10000 l00000 1000000 200 500 1000 B 10 100 200 500 表10其他参数的正交试验表和ARV值 实验编 因素 J30 J60 J120 10.0015660.1099290.34044 0.00355 0.108923 0.339372 0.002432 0.339328 4 4 4 40.003861 0.1119860.335951 50.025300.1105260.341777 5 0.003828 0.108515 0.343008 1000 0.110487 8 20.0038540.112940.346860 4 0.003722 0.108656 0.337056 2 0.334972 0.003394 0.1172940.340872 500053100.1126803408 4 100028660.11278103651 14 4 3 5 2 0.004339 0.110796 0.337648 2 4 0.003662 0.120941 0.349320 2 0.110909 0.342090 40028310.108930.340290 4 2 50.0040790.1071930.337972 4 5 10002264 0.110123 0.338306 20 0.004255 0.1090900.340571 20.05760.1130560.344211 30.040610.1144 0.340852 40.003051 0.109472 0.341239 24 4 2 1 500026790.1094440.339616 5 10.039830.11781 0.358220 Ionize KELos sRate bilecoll C.0014 C.0014 C.0036 010001000C1CC000100000050100200 190 图8J30的因素水平趋势图 9 国武技论文在线 http:/www.paper.edu.cn PosIte KlLossRace Bilecoll 0.114 0.113 0.112 0.110 0.114 0.113 0.112 0.110 lCC100C1C00010CC001000000 1002005001000 10501 图960的因素水平趋势图 195 Pops KELossRace Molecoll 0.34 0.342 0.338 0.5D. 0.20.4C.638 0.34 0.341 0.340 100C1C00010CC001000000 图10J120的因素水半趋势图 表11改进CRO最佳参数组合 问题集 B J30 0.5 0.21000 50 0.40.7 J60 100 0.7 0.1 100 1000 500 0.4 0.3 J120 0.7 1000 200 0.4 0.3 200 算法比较 基于表11参数设置,分别以1000、5000、50000次评价为终止准则,对所有J30、J60、 10

...展开详情
所需积分/C币:10 上传时间:2019-08-17 资源大小:413KB
举报 举报 收藏 收藏
分享 分享
遗传算法求解RCPSP问题

自己根据串行编写的并行程序,已经测试过了可以运行,希望对大家有帮助

立即下载
论文研究-求解高维动态0-1背包问题的修补二进制差分进化算法.pdf

针对已有的动态优化算法求解高维动态背包问题(DKP)难以获得高质量的可行解,且跟踪环境速度慢,提出了一种修补二进制差分进化算法(BDE/R)用于求解高维DKP。在BDE/R设计中,一种随机压缩变异策略直接根据个体间的差异在离散域内对个体进行突变;提出了一种贪婪的修补策略,提高了所获可行解的质量和算法的收敛速度;设计了一种对偶变换算子,提高种群的多样性,加速了算法跟踪环境的能力。数值实验以平均环境跟踪精确度(Av-Acc)和平均环境跟踪适应度(Av-Ada)为性能评价指标,通过四种DKP测试BDE/R跟踪动态最优值的能力,并将BDE/R与其他五种著名的优化算法进行了比较。结果表明:BDE/R所获

立即下载
论文研究-基础R.pdf

粒子群优化算法是一类基于群体智能的启发式全局优化技术,群体中的每一个微粒代表待解决问题的一个候选解,算法通过粒子间信息素的交互作用发现复杂搜索空间中的最优区域。本文介绍了粒子群优化算法的基本原理,并通过建立记忆表,详尽描述了粒子群优化算法中个体极优和全局极优的搜寻求解过程。同时,文章给出了多种改进形式以及研究现状,并提出了未来可能的研究方向。

立即下载
论文研究-基于R-滤子的多帧图像重建算法.pdf

针对图像重建中低分辨率图像信息的利用和先验项(正则化项)的估计问题,提出一种新颖的算法——R-滤子方法,通过计算输入图像的高阶信息来构建先验项,同时采用广义交叉验证(Generalized Cross Validation,GCV)方法自适应求解先验项参数(正则化参数),加强算法的自适应性。实验结果表明:重建图像的峰值信噪比值(Peak Signal-to-Noise Ratio,PSNR)比目前主要先验项方法(BTV、Sparse、Huber)的重建图像的值更高,从重建图像的局部细节和纹理也看出该方法的重建图像具有更丰富的信息,同时,从构造方法上说明R-滤子方法在计算上要优于其他方法。

立即下载
论文研究-集合划分问题的分布估计求解.pdf

参考独立分量分析(ICA with Reference,ICA-R)充分利用先验知识或参考信号,取得了很好的分离效果,但其中的阈值参数很难选取,且计算量很大。理论分析和实验表明,若阈值选取不当,算法甚至不收敛。通过在FastICA算法的负熵对比度函数中引入ICA-R算法中的接近性度量函数作为正则化项,得到一个简单的改进算法。针对合成数据和实际的ECG数据的仿真实验表明,算法收敛快、提取效果好,同时正则化参数取值非常灵活。

立即下载
论文研究-未标定摄像机姿态估计的矢量求解算法.pdf

提出一种基于矢量运算未标定摄像机姿态估计的求解算法。重点研究了P5P问题,将五个控制点组成四个矢量,根据成像过程,由控制点矢量运算逐步构建摄像机姿态和相机矩阵的线性约束方程。依据线性理论及旋转阵R的正交性化简约束方程,通过矢量运算给出未标定P5P问题摄像机姿态和相机矩阵的解析解。给出有足够约束条件的PnP问题的求解过程。模拟和真实实验都验证了该方法的有效性。

立即下载
论文研究-平面并联机构工作空间的三维螺旋扫描CAD求解.pdf

针对平面并联机构无奇异位置工作空间求解困难、过程繁琐、计算量大等问题,提出了基于CAD求解平面并联机构工作空间的三维螺旋扫描方法。将[n]自由度平面并联机构分解成[n]条支链进行独立分析,得到每条支链下末端执行器的可达区域,再将所有支链可达区域取交集即为平面并联机构工作空间。应用SolidWorks软件建立平面并联机构模型,进行几何特征处理,通过自动求解器求解,将求解过程图形化,快速得到同轴布局5R机构和平面3-RPR并联机构的无奇异位置工作空间。通过同轴布局5R机构的运动学实验,验证了该求解方法的可行性。

立即下载
论文研究-应用于CRM的一类马氏链模型求解及其分析.pdf

给出了用于研究客户关系管理(Customer Relationship Management,CRM)模型中的一类马氏链数学模型(Pfeifer模型)的收益期望值的解析解(无限次交易条件下),以方便该类模型的研究和分析。借助于求逆公式,将V=(I-P)-1R方程中矩阵求逆部分进行分解和简化,解出矩阵逆的解析解,从而求解出该类模型收益期望值向量的解析解,并推广到n阶。基于该解析解,对该类模型收益总期望值的特性进行了简单分析和讨论,该收益期望值的解析解将给该类方程的解析分析提供帮助。

立即下载
论文研究-基于多消费群体的竞争选址模型与求解算法.pdf

针对传统的竞争选址过于简单地考虑消费群体这一要素问题, 建立了新的竞争选址问题模型。在新模型中, 应用层次分析法综合考虑了门店规模、零售店价格、商品质量、装修程度、交通状况对设施吸引力的影响, 且其影响程度对于不同的消费群体有所不同等问题。最后给出了求解该模型的遗传算法和具体算例, 并通过MATLAB进行了编程计算实验。结果表明, 该模型和算法可以用于竞争选址决策中, 且具有一定的可行性和有效性。

立即下载
论文研究-一种新的混合粒子群算法求解置换流水车间调度问题.pdf

针对粒子群算法易早熟的缺点, 提出了一种结合迭代贪婪(IG)算法的混合粒子群算法。算法通过连续几代粒子个体极值和全局极值的变化判断粒子的状态, 在发现粒子出现停滞或者粒子群出现早熟后, 及时利用IG算法的毁坏操作和构造操作对停滞粒子和全局最优粒子进行变异, 变异后利用模拟退火思想概率接收新值。全局最优粒子的改变会引导粒子跳出局部极值的约束, 增加粒子的多样性, 从而克服粒子群的早熟现象。同时, 为了使算法能更快找到或逼近最优解, 采用了循环迭代策略, 在阶段优化结果的基础上, 周而复始循环迭代进行求解。将提出的混合粒子群算法应用于置换流水车间调度问题, 并在问题求解时与几个具有代表性的算法进行

立即下载
论文研究-Jumarie’s修正的R-L分数阶系统的新解法.pdf

结合同伦摄动理论和Sumudu变换方法,提出了一种简单有效的摄动方法,并应用该方法求解了Jumarie’s修正的Riemann-Liouville(R-L)分数阶的方程,该方程带有分数阶的初值条件,而以前的文献中很少讨论分数阶的初值条件。结果表明该方法具有较高的精度和有效性。

立即下载
论文研究-个修理工.pdf

论文研究-个修理工.pdf,  文章研究了带有多个温贮备部件的机器维修问题,系统中有R个修理工,修理工进行N-策略休假. 同时还考虑了故障部件止步和中途退出的现象.文中利用Markov过程理论建立了系统状态概率满足的微分差分方程组, 利用矩阵理论和Laplace变换反演的方法求解出了系统故障状态概率的精确表达式,得到了系统可靠度及首次故障前的平均时间的精确表达式,并给出了数值结果.

立即下载
论文研究-多视角几何Rao-Blackwellised SLAM算法.pdf

低成本传感器、高精度定位是机器人同步定位与地图构建的热点研究问题。采用单视觉传感器来获取多个图像视觉信息,通过因式分解求解多幅图像的空间关系;利用多视角几何理论获得环境深度信息。机器人的同步定位与地图构建是通过对观测模型进行一阶泰勒近似,以及Rao-Blackwellised粒子滤波迭代进行的。在MT-R移动机器人研究平台进行实验,实验结果表明所提出的方法在定位精度指标优于经典的EKF-SLAM方法,并且只需要单个摄像头。

立即下载
论文研究-求解带时间窗取送货问题的遗传算法.pdf

论文研究-求解带时间窗取送货问题的遗传算法.pdf,  首先介绍基于时差的插入法,进而设计求解带时间窗取送货问题的遗传算法.与传统求解该问题的遗传算法相比, 本算法有 以下特点:一是设计了基于时差插入法的交叉算子、R1变异算子与R2变异算子;二是采用非代际搜索策略. 应用56个标准测试算 例测试显示,其求解质量比已有文献报道的同类算法高.

立即下载
论文研究-多目标飞机航线调配模型的模糊优化算法.pdf

论文研究-多目标飞机航线调配模型的模糊优化算法.pdf,  为了提高航空公司飞机的日使用率,研究了相同机型的各架飞机调配问题.在满足航班衔接、航班覆盖、机队规模的约束下,建立了多目标整数规划模型,针对模型设计了模糊隶属度函数,定义了多目标伸缩指标,利用L-R型模糊数的性质和max的定义,应用模糊数学理论求解模型.最后通过数值实验表明该飞机调配问题的模型可行,算法能在保证飞机起降次数均衡的条件

立即下载
论文研究-私家车位共享系统的车位动态预约与分配.pdf

论文研究-私家车位共享系统的车位动态预约与分配.pdf,  为解决城市"停车难"问题,在现有停车位资源下,设计私家车位共享系统,动态收集私家车位空闲时段和公共停车需求的预约,以停车场使用效率最大化为目标、使用停车位的时间不冲突为约束建立0-1整数规划模型并运用MATLAB R2016a中求解器intlinprog进行求解,为停车需求分配停车位.数值实验表明,需求充足能够保证停车场较高水平的使

立即下载
论文研究-一种基于协调知识水平的协调问题描述方法.pdf

论文研究-一种基于协调知识水平的协调问题描述方法.pdf,  从协调的本质出发,提出基于协调知识水平的协调理论研究框架,用活动、资源、相互依赖和协调机制等刻画协调知识水平.在此基础上,按照分析活动→判断资源→分清依赖的顺序对协调问题进行抽象,进而通过三元组(A,D,R)对其进行形式化的描述,将协调问题的求解过程简化为对三种基本相互依赖的处理过程,为利用计算机处理协调问题打下了基础.

立即下载
论文研究-考虑机器故障的串行生产系统控制策略优化.pdf

针对多级串行生产系统,考虑存在机器故障和随机需求,对生产及雇佣的控制策略进行研究。以最小平均总成本为目标,建立基于(Q,r)库存策略的优化模型;鉴于求解复杂性,提出一种改进的网格自适应直接搜索算法(MADS-GA),为避免陷入局部最优和提高收敛速度,算法中加入了停滞阻止策略;对研究实例进行求解,并与已有算法比较。结果表明,所提出的算法收敛速度和寻优能力更优,能有效优化串行生产系统的控制策略,降低平均总成本。

立即下载
论文研究-用小波变换和混沌映射实现图像置乱.pdf

基于前人提出的双环网络G(N;r,s)的分步直径求解法,提出了一个等价树直径求解方法,得到一个新的研究双环网络的拓扑结构-等价树;研究了双环网络等价树的性质并给出了等价树的构造算法;给出了双环网络直径d(N;r,s)的显示公式;利用C#编程语言对等价生成树的结构模型进行了仿真实现;对任意给定的N,1≤r≠s<N,可以计算出双环网络G(N;r,s)的紧优、几乎紧优、k紧优解。

立即下载
论文研究-时延网络化控制系统的量化输出反馈耗散控制.pdf

以带有时变时延的离散网络化控制系统为研究对象,研究了闭环系统的量化输出反馈耗散控制问题。引入两个对数量化器分别对系统中的测量输出信号和控制输入信号进行量化,利用扇形界方法,将量化反馈控制设计问题通过扇形界的不确定性转换为鲁棒控制问题进行求解。通过借助自由权矩阵方法,得到了非脆弱耗散控制器存在的充分条件。所设计的控制器能够保证闭环系统渐近稳定且严格(Q,R,S)-耗散。最后通过理论证明及数值仿真验证了所提控制策略的有效性。

立即下载