一种基于模拟退火的多目标Memetic算法.pdf

第 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