一种基于模拟退火的多目标Memetic算法.pdf_第1页
一种基于模拟退火的多目标Memetic算法.pdf_第2页
一种基于模拟退火的多目标Memetic算法.pdf_第3页
一种基于模拟退火的多目标Memetic算法.pdf_第4页
免费预览已结束,剩余1页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第 3 6卷第 1 期 2 0 0 7年 2月 信 息 与控制 I n f o r ma t i o n a n d C o n t r o l Vo 1 3 6 No 1 F e b 2 0 0 7 文章编号 1 0 0 2 0 4 1 1 2 0 0 7 0 1 0 0 2 9 05 一 种基于模拟退火的多 目标 Me me t i c算法 郭秀萍 杨根科 吴智铭 上海交通大学 自动化系 上海2 0 0 2 4 0 摘要 为了改善多目标进化算法的搜索效率 提出了基于模拟退火的多 目标 Me m e t i c 算法 此算法根 据 P a r e t o占优关系评价个体适应值 采用模拟退火进行局部搜索 并结合交叉算子和基于网格密度的选择机 制改善算法的收敛速度和解的均衡分布 fl o w s h o p调度问题算例的仿真结果表明 基于模拟退火的多 目标 Me m e t i c 算法能够产生更接近 P a r e t o前沿的近似集 关键词 多 目标优化 模拟退火 Me me t i c 算法 网格密度 fl o w s h o p 调度问题 中图分类号 T P 3 0 1 文献标识码 A A S i mu l a t e d An n e a l i n g B a s e d Mu l t i Ob j e c t i v e Me me t i c A l g o r i t h m GU0 Xi u p i n g YANG Ge n k e W U Zh i mi n g A u t o m a t i o n De p a r t m e n t S h a n g h a i J i a o t o n g U n i v e r s i t y S h a n g h a i 2 0 0 2 4 0 C h i n a A b s t r a c t I n o r d e r t o i m p r o v e t h e s e a r c h e ffic i e n c y o f m ult i o b j e c t i v e e v o l u t i o n a r y a l g o ri t h m s a m u l t i o b j e c t i v e Me me t i c a l g o ri t h m b a s e d o n s i mu l a t e d a n n e a l i n g i s p r o p o s e d T h e me t h o d e v a l u a t e s t h e i n d i v i d u a l fi t n e s s b a s e d o n P a r e t o d o mi n a n c e r e l a t i o n s h i p a p p l i e s s i mu l a t e d a n n e a l i n g t o l o c a l s e a r c h a n d u s e s t h e e r o s s o v e r o p e r a t o r a n d a d d e n s i t y b a s e d s e l e c t i o n s c h e me t o i mp r o v e t h e e o n v e r g e n e e o f t h e alg o ri t h m a n d t o e n h a n c e t h e u n i f o rm d i s t ri b u t i o n o f s o l u t i o n s S i m u l a t i o n s o n m u l t i o b j e c t i v e fl o w s h o p s c h e d u l i n g p r o b l e m s s h o w t h a t t h e p r o p o s e d a l g o ri t h m c a n g e n e r a t e a p p r o x i ma t i o n s e t s c l o s e r t o t h e P are t a f r o n t o f t h e p r o b l e m K e y w o r d s m u l t i o b j e c t i v e o p t i m i z a t i o n s i m u l a t e d a n n e a l i n g M e me t i c al g o ri t h m g ri d d e n s i t y fl o w s h o p s c h e d u l i n g p r o b l e m 1引言 I n t r o d u c ti o n 实际问题 常要求考虑多个相互 冲突的 目标 多 目标优化的困难不仅在于其组合 的复杂性 而且还 在于需要找到 P a r e t o 最优集 模拟退 火 S A 是解决 单 目标组合优化 问题 的有效 方法 利 用加权 函数 S A已被用于多 目标优化 文 1 3 分别提 出多 目 标模 拟 退 火算 法 MO S A Mu l t i O b j e c t i v e S i mu l a t e d A n n e a l i n g S M O S A S u p p a p i t n a r m s Mu l t i O b j e c t i v e S i m u l a t e d A n n e a l i n g 和 P S A P a r e t o S i m u l a t e d A n n e a l i n g 其共同点是解的适应值评价和接收概率都 基于多个 目标的加权和 并通过 在优化过程 中改变 权值来改变搜索方向以维护解的多样性 近年来 一 些基于 P a r e to占优概念的多 目标进化算法 M O E A M u l t i O b j e c t i v e E v o l u t i o n a r y A l g o r i t h m 曲 受到 了 许多研究者 的关注 S u m a n 提 出了基 于 P a r e t o占 收稿 日期 2 0 0 6 0 l l 2 基金项 目 国家 自然科 学基金 资助项 目 6 0 1 7 4 0 0 9 优的多 目标模拟退火算法 P D MO S A P a r e t o D o m i n a t i o n B a s e d Mu l t i O b j e c t i v e S i mu l a t e d A n n e a l i n g 采 用 P a r e to占优关系评价适应值并计算 S A的接收概 率 研究 表明 方法 3 7 3 均能鲁棒地找到 问题 的 近似集 然而 这些基于 s A的优化算法主要强调了 解的多样性 为了提高算法的收敛速度 本文提出一 种基于 S A的多 目标 Me me t i e算法 S A MO MA S i mu l a t e d A n n e a l i n g B a s e d Mu l t i O b j e c t i v e Me me t i c A l g o r i t h m 将 S A实现的局部搜索与进化算子以及一种 基于网格密度 的选择机制相结合 以增强算法的全局 搜索能力 并采用 P a r e t o占优关系评价适应值并计 算 S A的接收概率 多 目标 fl o w s h o p调度问题 F l o w S h o p S c h e d u l i n g P r o b l e m F S S P 是典型的 N P难问题 本文通过求解 一 组多目标 F S S P算例对 S A M O M A和基于S A的多 维普资讯 信息与控制 3 6卷 目 标算法 M O S A 1 及 P D M O S A 7 进行了比较 仿真 结果表明 S A MO MA在求解多 目标 F S S P时具有更快 的收敛速度并能产生分布更均匀的近似集 2 多 目标 问题 描 述 S t a t e me n t o f mu l t i o b j e c t i v e p r o b l e m 一 般 多 目标优化问题可描述如下 j mi n Y 厂 上 S t 戈 1 戈 2 X m X 其中 是具有 m个决策变量的向量 表示可行解 空间 点Y 是 在目 标空间的目标向量 P a r e t o占优定义为 j 对任意两个解 a b X a 占优 b 即a d o m i n a t e b 记为 a 当且仅当 V i 1 2 a b 且 j 1 2 n a b 当 a 则f a 厂 b 解 X是 P a r e t o最 优 当且仅当没有其它解 X占优 所有 P a r e t o 最优解组成 的集合 称为 P a r e t o最优集 P a r e t o最优 集在 目 标空间的像称为 P a r e t o 前沿 在基于 P a r e t o占优概念的多 目标优化方法 中 解的适应值由目 标向量表示 解的生存概率依赖于 P a r e t o占优关系 3 基于 S A 的多目标 Me me t i c 算法 S i mu l a t e d a n n e a l i n g b a s e d mult i o b j e c t i v e Me me t i c a l g o r i t h m S A MoMA S A M O M A的框架如图 1 所示 每代包括局部搜 索和进化重组两部分 这也是简单 M e m e t i c 算法 亦 称混合遗传算法 的基本结构 S A M O M A用两个档 案管理优化过程产生的非劣解 内部档案 I A用于存 放局部搜索得到的非劣解 外部档案 E A用于存放 进化过 程产生 的所 有非劣 解 S A MO MA 的实现 如 下 改 局部搜索 善 种 群 t 新 一 代 l进化 重 组 如 交 叉 变 异 1 种群 图 1 Me m e t i c 算法的基本框架 F i g 1 F r a me wo r k o f t h e Me me t i c a l g o r i t h m 1 初始化 随机生成规模为 p o p s iz e 的初始种群 P o p 计算 每个个体的目 标向量 将 P o p中的非劣解存人外部 档案 E A 设置 s A的冷却度 初始温度 和终止 温度 2 计算 设置代数 g 0 d o f o r 每个个体 P o p 局部搜索 执行局部搜索 S a x 并将得到的非劣解存人 内部档案 I A 用 I A更新 E A E A 一E A uI A 将改善的 返回P o p 设置中间种群 m P o p为空集 n 0 进化重组 d o r 0 d o 从种群 E A u P o p中随机选择两个个体对 其进行交叉形成新个体 C 用后代 C更新 E A r w h i l e r C T O S S 且 C被 E A中的任何解占优 i f C被 E A中的解 占优 放弃 C 并用基于网格密度的锦标赛方法 从 E A中选择新后代 C 将 C放人种群 m P o p n w h i l e n p 0 更新种群 P o pr a n d o m 0 1 维普资讯 1 期 郭秀萍等 一种基于模拟退火的多 目标 M e me t i c算法 3 1 接收x x 1 k w h i le k T e d 其中 A s S X 一 S X S X 和 S X 分别是 某温度下迭代数为 k 时 X 和X基于 P a r e t o占优关 系的适应值 S X 1 E A中占优 X的个体数 显然 s 越小 说明解越接近 P a r e t o 最优 因此 当 S X S X 时 则接收邻域解 X 否则以概率 e x p 一 A s T 接收 X 1 在进化重组阶段 S A M O M A执行交叉操作直到 后代被接收或超出最大交叉数 17 c r o s s 对于后者 情形 则通过基于网格密度的锦标赛方法选择新个 体形成新一代种群 网格密度的确定如图2所示 首先将外部档案 E A中种群所 占据的 凡维 目标空间划分成 G G 2 G 个网格区域 G 表示第 维 目标空间的网格 数 1 2 凡 如图2 G G 4 于是 第 维 目标空间的网格宽度 如图2 和 计算为 W i m ax n u n 1 2 n i 式中F 和 F 分别是第 维 目 标空间的上边界和 下边界 如图 2 F 和 F 体圈 网 格 图2 基于网格密度的选择 F i g 2 Gr i d d e n s i t y b a s e d s e l e c t i o n E A中每个个体 X都位于一个网格区域 X在第 维目标空间的位置 z 的计算如下 Z ro o d d f f 1 1 2 r t 式中d m 是 X在第 i 维目标空间的距离测 量 是X的第i 维目标函数 函数 m o d n b 是 a b 的模数 即a b 的整数部分 网格的密度定义为其 包含的个体数 如图 2 所示 个体 c D E的位置都 为 z 3和z 2 其网格密度为 3 基于网格密度的 锦标赛选择指选取所在网格密度较小的个体作为新 一 代个体 即如图 3所示 个体 A和 B比网格密度 较大的个体 c D和E被选择的几率大 以此增强算 法搜索的遍历性 本实验中锦标赛选择次数取5 4 算法测试 A l g o r i t h m t e s t 4 1 测试 问题 我们用多 目标 F S S P测试算法性 能 多 目标 F S S P可描述为 凡 个工件 按照相同的 加工路线在 m台机器 上加工 预确 定在工艺约束条件下 凡 个工件的加工顺序 使以下 目标函数达到最小 制造周期 Ma k e s p a n 最大拖后时间 Ma x i mu m t a r d i n e s s 如果考虑第 3个目标 则还要最小化以下目标 函数 总流程时间 T o t a l fl o w t i me 本文测试算例 8 包括机器数 m为2 0 工件数 凡 分别是2 0 4 0 6 0和 8 0 目标数 为 2和 3的 8个 F S S P 算法均由c b u i l d e r 编程实现 所有实验在 C P U为2 4 0 G H z 内存为5 1 2 M的个人电脑上进行 4 2 性能指标 多目 标优化的一个 目的是收敛到 P a r e t o 前沿 F i e l d s e n d等 提出用 c C o v e r a g e 比较两个集合的 收敛速度 假设 A B是两个近似集 c的定义如下 A B l D l 3 C 0 1 当B中任何点都被 A中某些点占优时 C A B 1 当B中所有点都不被 A中任何点占优 时 c A B 0 一般 c A B C B A 所以都要 考虑 本文采用的第 2个性能指标是用 T a n 等 叫提 出的均衡分布 U n i f o r m D i s t r i b u t i o n U D 来测量算 法所得折 中面 t r a d e o ff s u I a c e 上点 的分 布情况 U D越小 解分布越均匀 近似集 A的 U D定义为 1 U D A 4 l十 n c 式中s 是 A中所有点的小生境计数值的标准偏差 维普资讯 3 2 信息与控制 3 6 卷 5 其中 是近似集中的个体数 n e y 是点Y Y A 的小生境计数值 而 A 是所有 n c Y i 1 2 n 的平均值 分别确定如下 n c y i 且 har 6 0 其它 6 NA n c y 而 7 式中d i 表示个体 i 与 在 目标空间的距离 o r 是人为设定 的小生境半径 本文取 5 4 3 计算结果和比较 S A MO MA的参数设置如表 1所示 包括种群大 小 p o p s iz e 最大交叉数 m a x c r o s s 第 i 维 目标空 间的网格数 G 最后一列给 出了对 每个 问题的计算 终止条件 即最大适应值评价次数 f u n c t io n e v a l u a t i o n s n u m b e r F E N 其它两种方法设定相同的计算 停止条件 每种算法都采用双点交叉和随机选择两 个工件交换其加工排序 的变异算子求解算例 且对 每个算例均运行 2 0次进行测试 表 1 S A MOMA对每个 F S S P算例的参数设置 T a b 1 P a r a me t e r s e t s o f S AMO MA f o r e a c h F S S P i n s t a n c e 算例 p o p s l z e G1 F EN 1 0 m 2 0 N 2 n 2 0 2 0 1 0 3 0 2 0 2 2 5 N 2 n 4 0 2 0 1 O 3 0 2 0 2 2 5 N 2 n 6 0 2 0 1 0 4 0 3 0 4 5 0 N 2 n 8 0 2 0 l 0 4 0 3 0 4 5 0 N 3 r t 2 0 2 0 1 0 3 0 2 0 5 0 4 5 0 N 3 n 4 0 2 0 1 O 4 0 3 0 5 0 4 5 0 N 3 r t 6 0 2 0 1 0 5 0 4 0 7 0 4 5 0 N 3 r t 8 0 2 0 1 O 6 0 5 0 7 0 4 5 0 S A MO MA中局部搜索 s A的参数在求解每个算 例时均设置为 T o 0 1 T e 0 0 1 y 0 9 5 每温度 下迭代次数 m a x l te r 5 0 图 3给出了基于性能指标 c 的比较 我们用数 据统计图 b x p l o t s 对 值的分布进行可视化描 述 B o x的中间线表示一组采样的中间值 上下端分 别表示5 0 采样的上下界 垂直线的上下端分别表 示一组采样的最大和最小值 图3所示每个矩形图 中左面 4个 b o x p l o t s 对应两 目标 F S S P 从左到右工 件数为 2 0 4 0 6 0和 8 0 右面 4个 b o x p l o t s 对应三 目标 F S S P 从左到右工件数为 2 0 4 0 6 0和 8 0 图 3 说 明 基 于 C 值 在 相 同的算 法终 止条件下 s A M O M A明显优于 P D MO S A 因为对每个实例 前者 能产生更接近 P a r e t o前沿 的近似集 特别对于需要 考虑 3个 目标 的 F S S P算例 P D M O S A折中面的 7 5 以上被 S A MO M A得 到 的点 占优 而 P D MO S A 的近似集只占优 S A M O M A折中面非常小的一部分 即C P D M O S A S A M O M A 接近或等于0 由图3可 见 与 MO S A相 比 S A MO MA也具有更快 的收敛 速 度 特别对 于工件数 是 4 0和 6 0 考 虑 3个 目标 的 F S S P算例 c S A M O M A M O S A 都大于6 0 而c MO S A S A MO MA 小于 5 CT S A MO MA P D MO S A P D MO S A S A MO MA 图 3 基于 C的 b o x p l o t s F i g 3 C b a s e d b o x p l o t s 图4 a 和 b 以工件数为 6 0和 8 0的两 目标 F S S P为例 描述了不 同算法得到近似集 的比较 显 然 与 P D M O S A和 M O S A比较 S A M O M A能得到更 接近 P a r e t o 前沿的近似 表 2比较 了不同算法运行 2 0次所得近似集均 衡分布 U D 的平均值 由表 2 可知 对于所有算例 S A MO MA比 MO S A得 到 的近似集 分布更 均匀 与 P D M O S A比较 S A M O MA在求解 三 目标 F S S P时能 维普资讯 郭秀萍等 一种基于模拟退火的多 目标 Me me t i c 算法 3 3 得到分布更均匀的近似集 2 5 0 0 2 0 00 1 5 0 0 1 0 00 5 0 0 0 25 0 0 2 0 0 0 1 5 0 0 1 0 0 0 5 0 0 0 4 6 0 0 4 8 00 5 0 00 5 2 00 制造周期 a 5 6 0 0 58 0 0 制造周期 b 图4 不同算法得到近似集的比较 F i g 4 Ap p r o x i ma t i o n s c o mp a ris o n o f d i f f e r e n t a l g o ri t h ms 表2 S AMOMA和 P DMOS A MOS A的比较 U D T a b 2 C o mp a ris o n o f S AMOMA P D MOS A a n d MOS A U D 实例 m 2 0 S A MO MA P D MO S A MO S A N 2 n 2 0 4 8 9 E一0 1 4 8 4E一0 1 4 9 8E一01 N 2 n 4 0 5 0 5 E一0 1 4 7 5 E一01 5 42 E一01 N 2 n 6 0 4 81 E一0 1 4 4 7E一01 7 2 4E 一01 N 2 n 8 0 4 8 0 E一0 1 4 4 1 E一01 7 1 7E 一01 N 3 n 2 0 4 6 7 E一0 1 5 1 9E 一01 5 3 8 E一01 N 3 4 0 4 6 9 E O1 5 1 8E O1 5 7 4E O1 N 3 n 6 0 4 8 7 E一0 1 4 9 9E一01 5 41 E 一01 N 3 n 8 0 5 4 3 E一01 5 5 6E 一01 7 0 0E一01 5 结语 C o n c l u s i o n 本文提出了基于 S A的多 目标 M e m e t i c算法 S A M O M A 该方法采用 P a r e t o 法评价适应值 由 S A 实现局部搜索 并与交叉算子 和一种基于 网格密度 的选择机制相结合以改善算法的 e x p l o r a t i o n能力和 收敛速度 求解了多目标 F S S P算例 并与其它基于 S A的多 目标方法进行 比较 结果表 明 S A MO MA能 更快地产生接近 P a r e t o前沿且分布更均匀的近似集 参考文献 R e f e r e n c e s 1 U l u n g u E L T e g h e m J F o r t e mp s P H e t a 1 MO S A me t h o d A t o o l f o r s o l v i n g m u l t i o b j e c t i v e c o m b i n a t o ri a l o p ti m i z a t i o n p r o b l e m s J J o u rna l o f Mu h i c ri t e ri a D e c i s i o n An aly s i s 1 9 9 9 8 4 2 2 1 2 3 6 2 S u p p a p i t n a r m A S e f f e n K A P a r k s G T e t a 1 S i m u l a t e d a n n e a l i n g A n a h e ma t i v e a p p roa c h t o t r u e m u h i o b j e c t i v e o p t i m i z a ti o n J E n g i n e e r i n g O p t i mi z a t i o n 2 0 0 0 3 3 1 3 3 5 9 3 C z y z a k P J asz k i e w i c z A P are t o s i mu l a t e d a n n e a l i n g A me t a h e u ri s t i c t e c h n i q u e f o r mu l t i p l e o b j e c t i v e c o m b i n a t o ri al o p t i m i z a t i o n J J o u rna l o f M u h i c ri t e ri a D e c i s i o n A n al y s i s 1 9 9 8 7 1 3 4 4 7 4 Z i t z l e r E T h i e l e L Mu l t i o b j e c t i v e e v o l u ti o n a r y a l g o ri t h m s A c o mp ar a ti v e c a s e s t u d y a n d t h e s t r e n g t h P a r e t o a p p r o a c h J I E E E T r a n s a c t i o n s o n E v o l u t i o n a r y C o mp u t a t i o n 1 9 9 9 3 4 2 5 7 2 71 5 K n o w l e s J C o me D M P A E S A M e m e t i c al g o ri t h m fo r m u l ti o b j ec t i v e o p t i m i z a t i o n A P r o c e e d i n g s o f t h e 2 0 0 0 C o n g r e s s o n E v o l u t i o n a r y C o m p u t a ti o n C P i s c a t a w a y N J U S A I E E E 2 0 0 0 3 2 5 3 3 2 6 D e b K P r a t a p A A g a r w a l S e t a 1 A f ast a n d e l i ti s t m u l t i o b j e c fi v e g e n e t i c al g o ri t h m N S G A I I J I E E E T r a n s a c t i o n s o n E v o l u t i o n a r y C o mp u t a t i o n 2 0 0 2 6 2 1 8 2 1 9 7 7 S u m a n B S t u d y o f s i m u l a t e d a n n e al i n g b ase d al g o ri t h m s fo r m u h i o b j e c t i v e o p t i m i z a t i o n o f a c o n s t r a i n e d p r o b l e m J C o m p u t e r s a n d C h e mi c al E n gin e e ri n g 2 0 0 4 2 8 9 1 8 4 9 1 8 7 1 8 I s h i b u c h i H Yo s h i d a T Mu r a t a T B alanc e b e t w e e n g e n e t i c s e a r c h a n d l o c al s e a r c h i n me me t i c al g o ri thm s for

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论