论文研究-一种DCT变换的三维网格物体盲水印方法.pdf

所需积分/C币:5 2019-09-07 16:53:17 1.12MB .PDF
收藏 收藏
举报

为了研究Job-shop调度问题,分析了调度结果和调度过程,认为传统Job-shop调度模型的调度过程,实质是减少并减小空闲时间的组合优化过程,而且不同空闲时间对调度结果的影响程度不同。据此提出了最小化空闲时间的两个处理过程和不同空闲时间的处理顺序规则;并设计了进化算法中最小化空闲时间的初始种群生成过程、重组算子和变异算子。经典的调度基准问题对比测试表明最小化空闲时间的分析结论是正确的;最小化空闲时间过程高效可靠;最小化空闲时间的进化算法缩小了算法的搜索空间,大大提高了搜索效率,有效避免了早熟收敛现象,稳定可靠。
802007,43(27) Computer Engineering and Applications计算机工程与应用 排序后不会产生空闲时间;反之,通过循环选择产生最小空闲 3)随机搜索与集合A中工序顺序不同的个体X",记录 时间的工序。算法采用以随机数作为可调度工序集合S遍历起其A中相应工序的顺序。依据此顺序填充X′m中表示集合A′ 点的方法,使得多次运行时,选择不同工件的符合最小空闲时中工序的基因座,生成新个体Xn 间规则的第一个可调度工序。 (4)判断新个体X是否表示可行解;若不可行,则调整同 3.3广义海眀距离(H)定义与选择算子设计 工件的工序顺序进行修正。 种群个体具有较多的模式,则多样性越高。个体多样性通 (5)新个体X加入当代种群 过反映个体相似程度的广义海明距离定义。对于本文的染色体 重组算子依据最小化空闲时间操作随机重组了个体的两 编码,扩展二进制格雷码中海明距离( Hamming distance)的个基因段的顺序。新个体一般与3个父代个体相关,增加了种 概念,定义个体间的广义海明距离如下 群个体的多样性。 H(x g),X ())=>lx()-x(g) (3)35最小化空闲时间的变异算子设计 根据调度过程分析,调度过程应尽量减少并减小空闲时 式(3)中:X(g)表示第g代进化种群的第i个个体;x(g)表示间。变异算子作为提高个体适应度的重要手段,应达到这一目 X(g)中的第k个基因。其中运算符“”连接个体的两个等位基标。据此设计变异算子的运算过程如下: 因;若两个操作数的工件编号、工序编号和机床编号3个属性 (1)根据变异概率Pn随机选择种群的某一个体X。 值完全相同,则运算结果为0,否则为1。因此H的变化范围是 (2)搜索X中所有空闲时间的瓶颈工序,构成集合Ln O,(l为编码长度)。个体间的广义海明距离越大,则个体间的 (3)依据空闲时间的处理顺序原则排序,并更新集合L。 相似程度越低,则种群多样性越高。 (4)依次选择集合m中一个瓶颈工序P0 选择算子的操作对象包括当代种群的所有个体和交叉变 (5)根据2.2节的空闲时间调整过程对X进行处理;处理 异得到的个体,它们具有同等的选择机会。选择算子的操作过中每次调整都要对表示不可行解的个体进行修正;遇到完工时 程是 间减少则退出,否则转(4)选择下一个瓶颈工序,直到处理完所 1)首先选择所有个体的不同适应值,并递减排序,构成集有的空闲时间。 合中。 变异算子采用多次变异,按照空闲时间影响程度依次减小 (2)依次从φ中选择一个适应值∫,搜索所有适应值为∫空闲时间的方法加速调度结果完工时间的减小,从而提高个体 的个体,构成集合d。 的适应度。这与完全随机交换基因顺序的变异算子相比,缩小 (3)从集合φ'的第2个元素开始,依次计算其与前面所有了搜索空间,提高了搜索效率。 个体的广义海明距离,保存最小值H-;如果H-<M4(l为编码 长度),则从d中排除;直到处理完集合的所有个体。 调度基准实例对比分析 (4)将集合d的所有个体加入下一代种群,转(2)选择d 最小化空闲时间的进化算法采用Jaa编程实现,运行徵 的下一个适应值,直到处理完d的所有元素。 机的主频为PⅣ24G,内存为256M,操作系统为 Windows (5)从其它个体中,采用轮盘赌选择方法选择不同个体进XP。算法的测试分为三个部分:首先与基于简单启发规则的初 入下一代,直到达到种群规模P。 始种群生成过程相比,检测本文初始种群生成过程;第二部分 选择算子保证了当代个体和交叉变异得到的个体具有同通过与随机交换同机床工序顺序的变异算子比较测试最小化 等的选择机会确保最优个体进入下一代;优先选择适应度和空闲时间变异算子的搜索效率;第三部分通过与几种遗传算法 广义海明距离大的个体进入下一代,保证了种群的多样性。 比较测试本文算法的综合性能。 34最小化空闲时间的重组算子设计 日前, Fisher和 Thompson提出的实例f10已经成为公认 根据进化计算(EC)框架,重组算子产生的个体依赖于 的检验调度算法优劣的基准实例,其最优解的完工时间为930閂。 个以上的父代个体。结合最小化空闲时间的处理过程设计重作为最简单启发式方法的优先规则常用来产生初始种群,常见 组算子的运算步骤如下: 的优先规则有SPT、LPT、MWR、LWR、MOR、LOR、EDD、FCFS (1)根据重组概率P随机选择个体X;搜索X的某个空和 RANDOM。本文的最小化空闲时间(ST初始种群生成过 闲时间(若没有得到,则认为得到最优解,整个算法退岀),其瓶程与基于启发式规则的初始种群生成过程作为比较,对实例 颈工序为P。搜索与其紧前工序为P同机床加工的,早于10进行了测试。限制算法运行时间不超过5s,产生不同个体 P1加工的工序,连同P1构成集合A={Pk=0,1,2,…,n;搜 的数量不超过2000,运行结果见表1。综合评价显示ST最 优,LWR和MOR次之。早期研究重视的SP规则没有取得 索与P同机床加工的,晚于P,加工的工序,连同P构成集理想效果。 合A'={Pk′=0,1,2,…,n。 为了测试最小化空闲时间变异算子的搜索效率,与随机交 (2)随机搜索与集合A中工序顺序不同的个体X〃,记录其换同机床基因顺序,直到完工时间减少的变异算子,采用f20 A中相应序的顺序。依据此顺序填允,中表示集合A中L实例进行了比较。算法的种群规模为500,变异概率为0.9,交 序的基因座,生成新个体X。操作过程实例如图4所示。 叉概率为0.7,10次运行的平均结果如图5所示。随机变异的 X, PoPo0o P1.1 Po.P2.0 X, P1.o Po,P2.0 P1.Po, 情况下收敛趋势非常缓慢,也可以收敛到最优解;最小化空闲 时间的变异在47代左右收敛于最优解。 选择与Gier- Thompson算法结合的遗传算法(GTGA) XnP0|PoP.|P2o‖P 与启发式规则结合的遗传算法(HGA)作为比较,对不同规模的 图4重组操作示意图 (下转174页)

...展开详情
试读 3P 论文研究-一种DCT变换的三维网格物体盲水印方法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743481 你的留言是对我莫大的支持
2019-09-07
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
最新推荐
论文研究-一种DCT变换的三维网格物体盲水印方法.pdf 5积分/C币 立即下载
1/3
论文研究-一种DCT变换的三维网格物体盲水印方法.pdf第1页

试读结束, 可继续阅读

5积分/C币 立即下载 >