（生物医学工程专业论文）调强放疗的逆向计划研究.pdf

东南大学硕士学位论文 a b s t r a c t a sa na d v a i l c e dt e c h i l i q u eo f 1 r e e d i m e n s i o n a lc 帆妇m a lr a d i o t h e m p y 3 d c r t i i l t e n s 时 m o d u l a i e dm d i 0 血e r a p y 哪 h a sb e c a p p l i e di n t oc l i n i c a lo c o l o g yw o d d 埘d e l yn ei n t e n s 时 o f 山er a d i a 石o nb e 锄i sm o d u l a t e da c r o s st h e 骶a n n e n t6 e l d c o r p a r a t i v e l ye v e nd o s a g ec a nb e a c h i e v e db yu s i n gm o d u l a t e di i r a d i a d o no m et i l m o rt a 曜e t a c l es 锄e 廿m e l e s sd o s ef a l l si n t 0 t l l en e a r 锄b i e n tn o 衄a la n ds e n s i t i v e 矗s s u e 叫r th a ss i 卿矗c a n tp o t e n t i a lf o ri m p r o v i n gt h e t 1 1 e r a p e u t i cr a t i oa n dr e d u c i n gt o x i c i 咄 n 口仃 a n n e tp l a n sa r eo f t e ng e n e r a t e du s i l l gi n v e r s ep 1 姐 i n g w h i c hi sd i 丘b r e n tf 如m t r a d m o n a lf 0 刑a r dp l a i l t l i i l g f 戤 d o c t o rd e t e m i n e st 1 1 ep r e s c 抽ed o s e t h e no p t i m i z a t i o n t e c h n j q u e sa r el l s e dt 0h e l pd e t e r m i n et h ed i s 喇b u t i o no fi n t e n s i d e sa c r o s st h et a r g e tv 0 1 u m e t h e o p t i l n i z 撕o no f 廿1 e 订e a n l l e n tp l 咖i n gi sm ec n l c i a lp a r to fl h ew h o l ei 1 1 v e r s ep l a i l i l i n gs t e m w h i c hd i r e c t l yi n n u e c em ep r e c i s i o n 鲫de m c i e c yo f m e 山e r a p 弘 1 1 1 i s p a p e r i s f o c u s e do n t h er e s e a r c ho f t l l eo p t i i n i z 撕o n f o r t h e i n v e r s ep l a n i l i n go f m r tf h t o p t i m i z a 石o nm e m o d sa r ei d 订 血l c e d w h i c hi n c l u d eg r a d i e n tm e 廿 o d sa 1 1 ds t o c h a s d cm e 血o d s s u c h a ss i m u j a 把da n n e a l i n g g e n e h ca l g 嘶血m e t c s e c o d l y t 1 1 ec o n c e p to f m u l t i o b j e c t i v eo p t i m i z a d o h a sb e 饥a n a l y z e di nd e 诅i l e s p e c i a l l y 血en s g a i i 9 0 珊l n l n i r d ly 血ed o s ec a l c u l 舐o nm o d e i s o f b o mr e g u l a rf i e l d sa n di n g u i a r 丘e l d sh a v eb e e np r e s e l l t e d w h e r em ed o s ec a l c u l 撕o b a s e d0 n m ep e n c i lb e 锄m o d e sm a i l l l yi n 仃0 d u c e d f i i l a l l y 佃oo p t i m i z a 石o nm e t h o d sh a v eb e e ns t i d i e df o r m 汀p l a n n i g o n ei sb a s e do ng m d i e n tm e t h o da n d 廿l eo t h e ri sb 船e do nm u l d o b j e c d v eg e n e n c a 1 9 0 r i 也1 1 1 t h e yh a wb e e na p p l i e dt os o m es i i n u l a t e dd a t aa t l dh a v eb e e nc o m p a r e dw i t he a c ho 也e l 弛e 石r s tm e t l l o di sb a s e do nl b f g sa 1 9 0 r i 血m w h e r eo b j e c t i v ef i l r l c d o n sa r e 仃a n s f o n e dt oa s i n g l eo b j e c 石v eo n e t h em e 山o dc o n v e r g e sq u i c l l y b u to f t e nf a l l si l l t 0l o c a lo p t i m a l a n do n l yo n e o p 劬a 1s 0 1 u t i o nc a i lb e0 b t a i n e da to n e 妇1 e i nc o m p 撕s o n n s g a i lm e 山o dc a np r o v i d ep a 阍 0 o p 廿m a ls e tf o rc j 缸c a lc h o i c e i t sm o r en e x i b l ea n dm e e t sm ec l i n i c a ir e q u i r e i n e n t sb e n e r k e yw o r d s i m r t i n v e r s e 廿e a 仰e n tp j 觚n i i l g g e n e t i ca l g 商m m m u l t i 0 b j e c t i v e 叩血n i z a d o n l b f g sa l g o r i 1 n 1 n s g a i ia l g 嘶t 1 1 m 第一章绪论 1 l 课题背景和研究意义 第一章绪论 随着计算机技术 影像学 放射物理学 放射生物学 分子生物学等学科的有力支持 以及多边缘学科的有机结合 放射治疗技术已经取得了革命性的进步 根据世界卫生组织估 计 在全部恶性肿瘤中 4 5 的病人可以被目前的治疗方法治愈 其中2 2 被手术治愈 1 8 被放射治疗治愈 余下5 靠化疗治愈 若以全部肿瘤病人计算 其中的三分之二在其病程 的某一阶段可接受根治性活姑息性的放疗 可见放疗已经被广泛应用于肿瘤的治疗 近 r 个世纪以来 人们不断尝试种种努力米提高对肿瘤杀伤效应的同时 减少对正常组 织的损害 从而提高肿瘤放疗的治疗比 山e r 印e u t i cg a i l lf k t o lt g f 肿瘤的立体形态是不规则 的 而且往往与周边正常组织相互交错 最理想的放疗是放射线只照射肿瘤 而完全不照射 肿瘤周围的正常组织 这种放疗目前还不存在 三维适形放射治疗 3 d i i i e n s i a lc o n f o r m a lr a d i a t i o n 血e m py 3 d c r t 通过三维空间上拉弧 或多野非共面集束照射 使照射剂量的分布在三维方向上与靶组织的形状适合 一般来说 为达到剂量分布的三维适形 必须满足两个条件 一是在照射方向上 射野形状与靶区一致 二是靶区内各点的输出剂量率能按临床要求的方式进行调整 满足第一条的3 d c r t 称为狭义 适形放射治疗 同时满足两个条件的3 d c r t 称为广义适形放射治疗 亦称调强放射治疗 i 1 1 t e n s i t ym o d u l a t e dm d i a t i o n 山锄p y i m r t 调强放疗是近年来发展起来的一项新技术 被誉为二十一世纪放射治疗发展的方向 它 能优化配置每一个射野内各线束的权重 使高剂量区剂量分布的形状在三维方向与靶区的实 际形状相一致 实现了儿何形态和强度分布的双重适形 i m r t 精确定位 精确计划 精确照 射使靶区接受的剂量最大 靶区周罔正常组织受量最小 增加肿瘤控制率 减少正常组织的 损伤 改善病人生存质量 r t 系统包括两个部分 一个能产生强度可调射线束的装置 多叶准直器 和一个治疗 计划制定系统 与传统的治疗计划不同 d 以r t 采用逆向计划 i i l v e r s e p l a n 血g 即由医生根据 肿瘤 关键组织的形态和性质给出处方剂量 包括靶区的照射剂量和靶区周嗣敏感组织的耐 受剂量 然后由计算机给出实现该结果的方法和参数 从而实现了治疗计划的自动最佳设计 逆向计划是调强放疗系统的重要组成部分 逆向计划的可靠性 适用性和计算效率直接 影响了d m 盯的临床应用结果 因此逆向计划的研究 对提高调强放疗的精度与效率有着重要 豹意义 第一章绪论 1 2 国内外研究现状 二十世纪七十年代 美国的b j a r n g a r dk 日e w s 等提出唧的概念 由于当时计算机技 术及剂量模型条件的限制 哪还不能实施 但它为以后的发展提供了理论基础 2 多叶准 直器及计算机控制系统的建立和发展 为哪铺平了道路 8 0 年代b m h m e 教授提出逆向计 划设计的概念 以及笔形束计算模型的建立 为i m r t 提供了先决条件 在世界上 n o m o s 公司最早在加速器上利用微型多叶光栅准直器 实现了啷 国外已有数家公司正在开发和研制各种 v i r t 系统 目前进入临床的由美国n o m o s 公 司的p e a c o c k 系统和s c a l l d i 昀n 投m m 5 0 回旋加速器 由于价格的昂贵以及硬件条件的瓶颈限 制 i m r t 技术还难以广泛进入我国的临床放射治疗 目前 研究和开发能够为广大医院接受 的新型啷系统成为国内研究的热点 其中第一军医大学 中国医学科学院协和医科大学等 专家正在对d 江r t 系统进行研究 但离临床全面应用尚有一定距离 d r t 逆向计划中 需要运用计算机技术制定治疗的优化方案 即根据医生给定的处方剂 量 搜索各射线柬的最优强度分布 这是一个最优化的过程 对哪优化方面研究有主要贡 献的人有b o r t f e l d b 脚 n e w 曲b m o h a n 等 逆向设计方法是由计算机通过各种优化方法 寻找满足衡量目标函数的最佳参数配置 目标函数用来衡量计划的好坏程度 常用的目标函数有两类 基于剂量约束的模型和基于放射生物学模型口 生物学模型认为 优化应该基于由剂量分布产生的生物效应 目标函数多为最大化肿瘤控制概率 t c p 同时使 正常组织损害概率叫t c p 在可接受的范围内 然而这种目标函数在文献中尚未得到严谨论证 目前尚未应用于临床 本文采用的仍然是最为常用的基丁剂量约束的模型 使得各个目标满 足剂量约束的要求 实际上生物学效应也隐含于处方剂量中 d i h 需要优化的参数很多 包括射野参数 分次优化参数 调强参数 其中射野参数 包括射野的数量 方向 能量的大小等 分次优化参数包括时间 剂量因子等 调强参数包 括射束强度分布 独立准直器或多叶准直器的运动控制 机架旋转速度等等 如此之多的参 数 即使借助于计算机来优化也是相当困难的 通常选取其中的部分参数进行优化 本文主 要对射野强度分布优化做了较为深入的研究 调强放疗的射束强度优化方法有基于梯度的方法 模拟动力学方法 1 线性规划方 法 1 2 模拟退火 1 1 5 遗传算法 7 1 等等 不同的方法都有各自不同的优点和缺点 基于 梯度的方法属于确定性的方法 该方法的收敛速度很快 但往往陷入局部极小点 难以得到 全局最优解 而模拟退火 遗传算法这类的随机搜索算法 理论上说可以摆脱局部最小点的 困扰 得到全局最优解 但这类的方法通常速度较慢 不能满足临床的要求 近年来 多目 标优化方法被引入到调强放疗的优化中 本文将对多目标遗传算法进行了深入的研究 提出 了基于多目标遗传算法的调强放射治疗优化 第一章绪论 1 3 论文组织结构 本论文分为五个章节 第一章绪论 介绍了课题背景 说明了研究意义 分析了本课题 在国内外的研究现状 并对论文的要点进行了阐述 第二章最优化方法 对最优化理论和方 法作了必要的介绍 包括确定性的优化方法和随机优化方法 其中着重介绍了遗传算法和多 目标方法 并深入研究了多目标遗传算法中的n s g a i i 算法 这一章是后述章节有关优化方 案的理论基础 第三章剂量计算模型 本章在介绍一些常规剂量计算方法的基础上 重点论 述了基于笔形束模型的精确剂量计算方法 第四章调强放射治疗优化方法 分别基于梯度算 法和基于多目标遗传算法对调强放射治疗逆向计划进行了优化 并进行了比较分析 第五章 总结和展望 对本论文的工作进行了总结 并对今后的工作提出了建议 第二章最优化方法 2 1 引言 第二章最优化方法 自2 0 世纪4 0 年代以来 由于生产和科学研究突飞猛进地发展 最优化理论和方法日益 受到人们的重视 特别是计算机的广泛应用 使最优化问题的研究成为一种迫切的需要 形 成了一门新的应用数学分支学科 渗透到生产 管理 商业 军事 决策等各领域 最优化问题是指在一定的约束条件下 决定某个或某些可控制的因素应有的合理取值 使所选定的目标达到最优的问题 许多科学和工程问题都可以归结为最优化问题 最优化 问题的一般表示形式为 m m x j fx s 2 1 其中x 是决策变量 x 是目标函数 s c r 为约束集或可行域 特别地 如果约束集s r 一 则优化问题 2 1 成为无约束优化问题 盥厂 x 2 2 约束最优化问题通常写为 m 拥 x s f c x 0 j e 2 3 c x o f i 这里e 和1 分别是等式约束指标集和不等式约束指标集 q x 是约束函数 当目标函数 和约束函数均为线性函数时 问题称为线性规划 当目标函数和约束函数至少有一个是变量x 的非线性函数时 问题称为非线性规划 此外 根据决策变量 目标函数和要求的不同 最 优化还分成了整数规划 动态规划 网格规划 非光滑规划 随机规划 儿何规划 多目标 规划等若干分支 最优化方法解决问题一般可以分为以下几个步骤 1 提出需要进行最优化的问题 开始收集有关资料和数据 2 建立求解最优化问题的有关数学模型 确定变量 列出目标函数和有关约束条件 3 分析模型 选择合适的最优化方法 4 求解方程 一般通过编制程序在电子计算机上求得最优解 5 最优解的验证和实施 最优化方法总体上可以分为两大类 确定性方法 d e t c i 邛 i i l e dm e t h o d 和随机性方法 s 0 c h a s d cm e t h o d s 确定性方法的特点是速度快 但容易陷入局部极小 得不到全局晟优解 相反 随机性方法不易陷入局部极小 从概率上可以收敛到全局最优 但是收敛速度比较慢 第二章最优化方法 在很多领域中实际遇到的问题大部分都无法使用确定性方法求解 例如旅行商问题 流 水车间调度问题 设备布局设计问题等 此外还会经常遇到在多准则或多设计目标下设计和 决策问题 这些目标往往是相互背离的 需要运用多目标优化方法来寻找权衡于这些目标之 间的最佳解决方案 包括模拟退火 遗传算法 神经网络算法等在内的各种智能优化算法的 发现和发展 使得更有效地求解这些难题成为可能 这些方法大都属于随机性方法 下面我们按照确定性和随机性优化方法的分类 介绍一些常用的优化方法 其中主要讨 论了遗传算法和多目标优化方法 并重点研究了n s g a i i 多目标遗传算法 2 2 确定性最优化方法 1 8 锄 确定性的方法很多 包括单纯形法 最速下降法 共轭梯度法 牛顿法 变尺度法 拟 牛顿法 等 这些方法的计算速度比较快 然而 应用的前提是假定仅有一个极限值存在 对于多极限值问题 这些方法往往会陷入局部极值 难以得到全局优化 但由于其速度的优 势 往往与后述的随机性的方法结合使用 1 单纯形法 单纯形方法 s i l n p l e xm e t h o d 是g b d a n t z i g 在1 9 4 7 年首次提出米的 该方法不仅理论 上完善 算法简单 而且适用于各种类型的线性规划问题 是一种求解线性规划问题的最常 用方法 单纯形方法是从一个可行解迭代到另一个可行解 每一次迭代都能使目标函数值得到改 善 而且经过有限次迭代之后 便可求出目标函数的最优值 从而得到该线性规划问题有最 优解或判别原问题无最优解 该方法首先计算出若干个点上的目标函数值 例如对于有n 个 变量的优化问题 算出n 1 个点 它们构成单纯形的各个顶点 上的函数值 然后进行比较 再通过单纯形法的迭代计算 舍去其中最坏的点 代之以新的点 构成一个新的单纯形 再 进行各点函数值比较 这样逐步逼近极小值点 从而完成单纯形法的最优化搜索 2 最速下降法 最速下降法以负梯度方向作为极小化算法的下降方向 又称为梯度法 是无约束最优化 中最简单的方法 考虑到函数 0 在点一 处沿着方向d 的方向导数删 w b 其意义 为 厂扛 在点z 处沿着方向d 的变化率 当 连续可微时 方向导数为负 说明函数值沿着 该方向下降 方向导数越小 表明下降速度越快 因此确定搜索方向d 的一个想法 就是以 0 在点一 方向导数最小的方向作为搜索方向 即令 d 一1 盯 x 最速下降法的具体步骤为 选定初始点z 和给定精度要求s 0 令t 1 2 4 第二章最优化方法 若 i 可y 舻 j 占 则停 z x 否则令d 一v x 在z 处沿方向d 作线性搜索得x x 口t d 女 t l 返回 一般说来 最速下降法在开始迭代时 效果较好 能较快地到达最优解附近 但当其继 续迭代时 往往发生扭摆现象 迭代点沿相互正交的方向扭摆 进展非常缓慢 不能直接达 到最优解 以至于常常由于舍入误差的影响造成 早停 在距离最优解较远的地方 机器就 接到停止信号而停机 3 共轭梯度法 共轭梯度法是针对二次函数 厂 去z 7 1 参 6 7 j c x 一 k 7 2 5 的无约束极小问题 考虑出一种搜索方向得合理选取方法 然后形式地推广到一般可微函数 其中q 为实对称正定矩阵 共轭方向法基本定理告诉我们 共轭性和精确线性搜索产生二次 终止性 共轭梯度法是最著名的共轭方向法 它就是使得最速f 降方向具有共轭性 从而提 高算法的有效性和可靠性 对于m i l l x 厂 c 的共轭梯度法的步骤为 任选工 1 尺 d 1 一1 e 厂 工 1 j l 若口可 z 口 占 则停 否则 x 1 工 2 d n 口t a 1 善m i l l 厂 石 口d d 竹 1 一v c x 忙 貉d 忡 2 6 七 1 返同 共轭梯度法的主要特点是存储量小 不需存储矩阵 而只需存储若干向量 这个特点使 得共轭梯度法在大规模问题中具有明显的优势 4 牛顿法 牛顿法的基本思想是利用二次函数近似目标函数 把这个二次函数的极小点作为新的迭 代点 对于二次可微的目标函数 可将目标函数按泰勒级数展开至二次项 x d x i 1 盯 x i 7 d t d h d t 2 7 其中 女 x 一x i 影丫x f j 7 为 在 处的j a c o b i 矩阵 为 在 处的h c s s e 矩阵 二阶导数 偏导数对称方阵 6 第二章最优化方法 h t v r x t j 兰f x k 血1 m 1 姜f f xk m 2 m l f x k 出 l 姜r f x k 出l m 2 善 f i x k 血2 c k 2 善 f xk 1 m 月 2 2 7 式的极小值应满足如下一阶必要条件 町r x tj h d t 0 7 r x j 融月积 2 8 方程 2 8 称为牛顿方程 满足牛顿方程的方向d i 称为牛顿方向 若h t 可逆 那么优 化问题的牛顿算法如下 确定下降方向 d 女 一r h f 厂1 i y r x i 寻找最佳步长 以j m 拥 x a d t 参数迭代 x x i 以d i 牛顿法收敛速度为二阶 是它的最大优点 牛顿法对正定二次函数一步迭代即达到最优 解 冈此具有二次终结性 但牛顿法又一些致命的缺点 常导致方法进行中产生困难 甚至失败 这些缺点有 i 牛顿法是局部收敛的 当初始点选择不当时 往往导致不收敛 i i 牛顿法不是下降算法 当二阶h e s s e 矩阵非正定时 不能保证产生的方向时下降方向 血 对函数要求苛刻 二阶连续可微 h e s s e 矩阵可逆 而且运算量大 为此 人们在克服上述缺点方面做了很多有益的工作 如下述的变尺度法就时对牛顿法 的一种改进方法 4 变尺度法 拟牛顿法 变尺度法的基本思想是用对称正定矩阵近似二阶h e s s e 矩阵 或h e s s e 矩阵的逆 这是某 种意义下的近似 要求满足拟牛顿方程 因此该类方法又称为拟牛顿法 选用正定矩阵可以 对搜索方向保证下降性 另一个重要的改进是变尺度法的矩阵 它是通过逐步迭代修正产生 的 因而避开逐点计算二阶偏导数的大量运算 由于满足条件的对称正定矩阵有无穷多个 所以拟牛顿法其实是一族算法 常用的有d f p 法和b f g s 法 其中b f g s 算法是求解无约束优化问题拟牛顿方法类的最有效方法之一 在 处理凸非线性优化问题上 以其完善的数学理论基础 采用不精确线性搜索时的超线性收敛 性和处理问题的有效性 受到人们的重视 b f g s 算法并不直接计算函数的h e s s e 矩阵 而是 采用一阶梯度信息g r 矿 缸i 可 缸2 可 知 j 7 来构造一系列的正定矩阵来逼近h e s s e 矩 阵 7 第二章最优化方法 b f g s 方法求解无约束优化问题的主要步骤如下 给变量赋初值x o 变量维数n 和b f g s 方法收敛精度s 令h o i 单位阵 桔o 计 算 x 在点x o 的梯度g o 取p f 一耳女g p 沿m 作一维搜索 确定最优步长 m 觑 f x i 口i p ij 口t 得到新的点x x t 铆p 女 计算x t l 点处的梯度g 若懈 忙 则令x x 厂 x 厂 x b f g s 搜索结束 否则执行 计算h k h 1 雩盟j 簪一丛旦雩些遒 5 y t8 y l8 y 其中s 女 x 一x t y l g t 十l g 格抖l 转 与d e p 方法相比较 b f g s 方法结合w i l f e p o w e l l 不精确一维搜索 可在理论上得到全 局收敛性结果 是目前认为 最好 的拟牛顿方法 近年来还有学者对其改进 如l b f g s 算法口 该算法的计算复杂度和所需的存储空间有明显的降低 适合于大规模优化问题 l o c 畦m i n 妇a 灿 图2 1 全局最优和局部最优 图a 为单极值的情况 图b 为多极值的情况 小结 以上各确定性方法各有其特点 相比较而言 相比较而言 单纯形法在最优点处 收敛速度很慢 共轭梯度法初值可以不必接近最优点 但是要求一维搜索精确 才有较快的 收敛速度 n e w t o n 法收敛速度相当快 但是初值要求非常接近最优点 否则很难收敛 而且 每次要求计算h e s s e 矩阵的逆 计算量很大 d f p 算法和b f g s 算法是比较好的变尺度方法 尤其b f g s 算法数值稳定性比较好 收敛速度相当快 而且对一维搜索精度要求也不严格 但 是这些方法都急于找到附近的解 由起始点出发 尽可能直接向下搜索 这就导致了一个局 部的而不必是全局的极小 图2 1 中a 是一个全局只有一个极小点的情况 这种情况可以用确 定性方法来优化 而对于b 多极值的全局优化问题 确定性方法往往陷于局部极小而不能找 到全局极小 冈此 随机性优化方法的研究越来越受到人们的重视和运用 8 一 第二章最优化方法 2 3 随机性最优化方法 很多工程问题的优化都是全局优化 往往不能通过确定性方法求得全局优化解 与确定 性优化方法不同 随机优化方法不容易陷入局部极小 2 0 世纪8 0 年代以来 一些新颖的随机 性优化算法2 如模拟退火 s i i n u l 咖dm e a h n 曲 遗传算法 g e n e t i ca 1 9 0 r i l m m o n t ec a r l o 方法等 这些方法通过模拟或揭示自然现象或过程而得到发展 其思想和内容涉及数学 物 理学 生物进化 统计力学等方面 为解决复杂问题提供了新的思路和手段 这些方法具有 很强的鲁棒性 广泛用于人工智能 组合优化 图像处理等各领域 2 3 1 蒙特卡罗 m o n t ec a r l o 方法 蒙特卡罗 m c 方法 又称随机抽样或统计试验方法 属于计算数学的一个分支 它是 在本世纪四十年代中期为了适应当时原子能事业的发展而发展起来的 传统的经验方法由于 不能逼近真实的物理过程 很难得到满意的结果 而蒙特卡罗方法由于能够真实地模拟实际 物理过程 故解决问题与实际非常符合 可以得到很圆满的结果 蒙特卡罗方法的基本原理及思想 当所要求解的问题是某种事件出现的概率 或者是某个随机变量的期望值时 它们可以 通过某种 试验 的方法 得到这种事件出现的频率 或者这个随机变数的平均值 并用它 们作为问题的解 这就是蒙特卡罗方法的基本思想 蒙特卡罗方法通过抓住事物运动的几何 数量和几何特征 利用数学方法来加以模拟 即进行一种数字模拟实验 它是以一个概率模 型为基础 按照这个模型所描绘的过程 通过模拟实验的结果 作为问题的近似解 可以把 蒙特卡罗解题归结为三个主要步骤 构造或描述概率过程 实现从已知概率分布抽样 建立 各种估计量 蒙特卡罗方法的解题步骤 i 构造或描述概率过程 对于本身就具有随机性质的问题 如粒子输运问题 主要是正确描述和模拟这个概率过 程 对于本来不是随机性质的确定性问题 比如计算定积分 就必须事先构造一个人为的概 率过程 它的某些参量正好是所要求问题的解 即要将不具有随机性质的问题转化为随机性 质的问题 i i 实现从已知概率分布抽样 构造了概率模型以后 由丁各种概率模型都可以看作是由各种各样的概率分布构成的 因此产生己知概率分布的随机变量 或随机向量 就成为实现蒙特卡罗方法模拟实验的基本 手段 这也是蒙特卡罗方法被称为随机抽样的原因 最简单 最基本 最重要的一个概率分 布是 0 1 上的均匀分布 或称矩形分布 随机数就是具有这种均匀分布的随机变量 随机数 序列就是具有这种分布的总体的一个简单子样 也就是一个具有这种分布的相互独立的随机 9 第二章最优化方法 变数序列 产生随机数的问题 就是从这个分布的抽样问题 在计算机上 可以用物理方法 产生随机数 但价格昂贵 不能重复 使用不便 另一种方法是用数学递推公式产生 这样 产生的序列 与真正的随机数序列不同 所以称为伪随机数 或伪随机数序列 不过 经过 多种统计检验表明 它与真正的随机数 或随机数序列具有相近的性质 因此可把它作为真 正的随机数来使用 由已知分布随机抽样有各种方法 与从 o 1 上均匀分布抽样不同 这些方 法都是借助于随机序列来实现的 也就是说 都是以产生随机数为前提的 由此可见 随机 数是我们实现蒙特卡罗模拟的基本工具 i i i 建立各种估计量 一般说来 构造了概率模型并能从中抽样后 即实现模拟实验后 我们就要确定一个随 机变量 作为所要求的问题的解 我们称它为无偏估计 建立各种估计量 相当于对模拟实 验的结果进行考察和登记 从中得到问题的解 蒙特卡罗方法的特点 蒙特 罗方法与一般计算方法有很大区别 一般计算方法对于解决多维或因素复杂的问 题非常困难 而蒙特卡罗方法对于解决这方面的问题却比较简单 其优点有 直接追踪粒子 物理思路清晰 易于理解 采用随机抽样的方法 较真切的模拟粒子输运的过程 反映了统计涨落的规律 不受系统多维 多因素等复杂性的限制 是解决复杂系统粒子输运问题的好方法 m c 程序结构清晰简单 应用灵活性强 m c 方法主要缺点是收敛速度较慢和误差的概率性质 如果单纯以增大抽样粒子个数n 来减小误差 就要增加很大的计算量 2 3 2 模拟退火算法 模拟退火算法 s i m u l a t e da n n e a l i l l g 简称s a 是基于m 0 n t ec a r l o 迭代求解策略的一种 随机优化算法 目前在生产调度 控制工程 机器学习 图像处理等领域得到了广泛的应用 模拟退火算法最早是由m e 昀p 0 1 i s 等于1 9 5 3 年提出的 而聒r k p a 仃i c k 等人最先于8 0 年 代将其用于组合优化 其特点在于 1 为具有n p 复杂性的问题提供有效的近似求解算法 2 克服优化过程陷入局部极小 3 克服初值依赖性 模拟退火的基本思想 模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性 物质在加热的 时候 粒子问的布朗运动增强 到达一定强度后 固体物质转化为液态 这个时候再进行退 火 粒子热运动减弱 并逐渐趋丁有序 最后达到稳定 模拟退火算法在某一初温下 伴随 温度参数的不断下降 结合概率突跳特性在解空问中随机寻找目标函数的全局最优解 即在 局部最优解能概率性地跳出并最终趋于全局最优 1 0 第二章最优化方法 模拟退火的解不再像局部搜索那样最后的结果依赖初始点 它引入了一个接受概率 如 果新的点的目标函数更好 则选取新点 否则 接受概率是当前点的目标函数 新点的目标 函数以及另一个控制参数 温度 t 的函数 也就是说 模拟退火没有像局部搜索那样每次都 贪婪地寻找比现在好的点 目标函数差一点的点也有可能接受进来 随着算法的执行 系统 温度t 逐渐降低 最后终止于某个低温 在该温度卜 系统不再接受变化 模拟退火的典型特征是除了接受目标函数的改进外 还接受一个衰减极限 当t 较大时 接受较大的衰减 当t 逐渐变小时 接受较小的衰减 当t 为0 时 就不再接受衰减 这一 特征意味着模拟退火与局部搜索相反 它能避开局部极小 并且还保持了局部搜索的通用性 和简单性 模拟退火算法的步骤 模拟退火算法的一般步骤可描述如下 1 初始化 初始温度t 充分大 初始解状态s 是算法迭代的起点 每个温度下 的迭代次数l 2 对k l l 重复第 3 至第 6 步 3 产生新解s7 4 计算增量 c c s7 一c s 其中c s 为评价函数 5 若 c7 o 然后转第 2 步 模拟退火算法关键参数和操作的设定 从算法流程上看 模拟退火算法包括三函数两准则 即状态产生函数 状态接受函数 温度更新函数 抽样稳定准则 算法终止准则 这些环节的设计将决定s a 算法的优化性能 此外 初温的选择对s a 算法性能也有很大影响 1 状态产生函数 候选解由当前解的邻域函数决定 可以取互换 插入 逆序等操作产生 然后根据概率 分布方式选取新的解 概率可以取均匀分布 正态分布 高斯分布 柯西分布等 2 状态接受函数 这个环节最关键 但是 实验表明 何种接受函数对于最后结果影响不大 所以 一般 选取m i l l 1 e x p 0 作为状态接受函数 3 温度更新函数 即温度的下降方式 常用的为指数退温函数 即 旯瑶 其中o 且其大小可 以不断变化 4 抽样稳定准则 一1 1 第二章最优化方法 一般常用的有 检验目标函数的均值是否稳定 连续若干步的目标值变化较小 5 算法终止法则 通常的做法有 设置终止温度的阂值 设置迭代次数 搜索到的最优值连续多次保持不 变 检验系统熵是否稳定 2 3 3 遗传算法口z 2 3 遗传算法 g e n e t i c a l g o 棚n 缩写为g a 是一种有效地解决最优化问题的方法 它最先 是由j o h nh 0 1 1 a i d 于1 9 7 5 年提山的 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进 化过程的计算模型 它的思想源于生物遗传学和适者生存的自然规律 是具有 生存 检测 的迭代过程的搜索算法 2 0 世纪8 0 年代由g o i d b e 曙进行总结归纳 形成了遗传算法的基本 框架 遗传算法以一种群体中的所有个体为对象 并利用随机化技术指导对一个被编码的参 数空间进行高效搜索 2 3 3 1 遗传算法的基本步骤 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法 与传统搜索算法不同 遗传算法从一组随机产生的成为 种群 p o p u l a t i o n 的初始解开始搜索过程 种群中的每个 个体是问题的一个解 称为 染色体 c h m m o s o m e 染色体是一串符号 比如一个二进制 字符串 这些染色体在后续迭代中不断进化 称为遗传 在每一代中用 适应度 f i t n e s s 来测量染色体的好坏 生成的下一代染色体称为 后代 o 舔p r i n g 后代是由前一代染色体 通过交叉 c r o s s o v e r 或者变异 m u t a t i o n 运算形成的 在新一代形成过程中 根据适应度 的大小选择部分后代 淘汰部分后代 适应度高的染色体被选中的概率较高 这样经过若干 代之后 算法收敛于晟好的染色体 它很可能就是问题的最优解或次优解 图2 2g a 的计算过程流程图 1 2 第二章最优化方法 遗传算法的主要步骤如下所示 1 编码 g a 在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数 据 这些串结构数据的不同组合便构成了不同的点 编码可以是二进制编码 也可以是实数 编码 或是其它的编码方式 2 初始群体的生成 随机产生 个初始串结构数据 每个串结构数据称为一个个体 个个体构成了一个群体 g a 以这 个串结构数据作为初始点开始迭代 3 适应度评估检测 适应性函数表明个体或解的优劣性 对于不同的问题 适应性函 数的定义方式也不同 4 选择 选择的目的是为了从当前群体中选出优良的个体 使它们有机会作为父代为 下一代繁殖子孙 遗传算法通过选择过程体现了这一思想 进行选择的原则使适应性强的个 体为下一代贡献一个或多个后代的概率大 选择实现了达尔文的适者生存原则 5 交叉 交叉操作是遗传算法中最主要的遗传操作 通过交叉操作可以得到新一代个 体 新个体组合了其父辈个体的特性 交叉体现了信息交换的思想 6 变异 变异首先在群体中随机选择一个个体 对于选中的个体以一定的概率随机地 改变串结构数据中某个串的值 同生物界一样 g a 中变异发生的概率很低 通常取值在 0 0 0 l 0 0 l 之问 变异为新个体的产生提供了机会 2 3 3 2 遗传算法的特点 遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法 与其他一些优化算法相比 主要有一下几个特点 1 遗传算法以决策变量的编码作为运算对象 传统的优化算法往往直接利用决策变量 的实际值本身进行优化 但遗传算法不是商接以决策变量的值 而是以决策变量的某种形式 的编码为运算对象 从而可以很方便地引入和应用遗传操作算子 2 遗传算法直接以目标函数值作为搜索信息 传统的优化算法往往不只需要目标函数 值 还需要目标函数的导数等其他信息 这样 对于许多目标函数无法求导或很难求导的函 数 遗传算法就显得方便的多 3 遗传算法同时进行解空间的多点搜索 传统的优化算法往往从解空间的一个初始点 开始搜索 这样容易陷入局部极值点 遗传算法进行群体搜索 而且在搜索的过程中引入遗 传运算 使群体又可以不断进化 这些使遗传算法所特有的一种隐含并行性 4 遗传算法使用概率搜索技术 遗传算法属于一种自适应概率搜索技术 其选择 交 叉 变异等运算都是以一种概率的方式来进行的 从而增加了其搜索过程的灵活性 实践和 理论都已经证明 在一定条件下遗传算法总是以概率l 收敛于问题的最优解 2 3 3 3 标准遗传算法 标准遗传算法的描述如下 初始化 随机初始化群体规模为 的群体 群体内每个个体必须以某种编码形式进 第二章最优化方法 行表示 编码可以是二进制编码 也可以是实数编码 或是其它的编码方式 从而 产生一系列的个体 z p x z 2 a j b i 1 2 n 这里n 为最优问题的变量个数 k 为第k 个个体 适应度计算 计算种群中每个个体的适应度值 适应度值代表了进化的好坏程度 为下一步选择操作提供了数据和方向 选择 根据个体的适应度函数值从父代中选择两个个体 适应度函数值越大 被选 中的概率越大 交叉 将选择出的两个个体以一定的杂交概率只进行杂交 产生两个新的个体 变异 对新个体按变异概率p j 进行变异 再生 接受新个体并判断是否完成新群体的生成 如果没有 则返回到 检验停止演化的条件 若满足收敛条件或固定迭代次数则停止演化 若不满足条件则 转 2 重新进行演化 每一次进化过程就产生新一代的群体 群体内个体所表示的解 到停止演化时 就是所求的最优解 2 3 3 4 遗传算法的运行参数 遗传算法中需要选择的运行参数主要有编码方式 编码串长度z 群体大小m 交叉概率 p 变异概率m 终止代数t 等 这些参数对遗传算法的运行性能影响较大 需认真选取 编码方式 如何将问题的解编码称为然色体是遗传算法使用中的关键问题 在过去的1 0 年中 已经 针对特定的问题提山了各种编码方法 根据采用何种符号作为基因的等位基冈 编码方式可 以分类如下 二进制编码 b i n a r ye n c o d i n g 实数编码 r e a l n u m b e re n c o d i l l g 整数或字母排列编码 1 i t e r a lp e h n u t a t i o ne t l c o d i n g 一般数据结构编码 二进制编码方法是遗传算法中最常用的一种编码方法 它使用的编码符号集是有二进制 符号o 和l 所组成的二值符号集 o 1 它所构成的个体基因型是一个二进制编码符号串 它 具有编码解码操作简单易行 遗传操作便于实现 便于利用模式定理对算法进行理论分析等 特点 但它的缺点也有很多 比如存在连续函数离散化的映射误差 不便于反映索求问题的 特定知识等等 对于工业工程领域里的许多问题而言 人们往往采用实数编码方法 实数编码又称为浮 点数编码 是指个体的每个基因值用某一范围内的一个浮点数来表示 个磊甭磊丽嘉疆霎 于 其决策变量丽不蠹 面两蠢秆孺稿芳疆覆甬雨趸磊磊戛三丽i 萎石 丙i 五五再赢码方 法 实数编码有下面几个优点q 一 一一 一1 4 第二章最优化方法 适合于在遗传算法中表示范围较大的数 适台于精度要求较高的遗传算法 便于较大空间的遗传搜索 改善了遗传算法的计算复杂性 提高了运算效率 便于遗传算法与经典优化方法的混合使用 便于处理复杂的决策变量约束条件 编码串艮度 使用二进制编码来表示个体时 编码串长度 的选取与问题所要求的求解精度有关 使用 实数编码来表示个体时 编码串长度 与决策变量的个数相等 群体大小m 群体大小m 表示群体中所含个体的数量 当m 取值较小时 可提高遗传算法的运算速度 但却降低了群体的多样性 有可能会引起遗传算法的早熟现象 相反当m 取值较大时 又会 使得遗传算法的运行效率降低 交叉概率仇 交义操作是遗传算法中产生新个体的主要方法 所以交叉概率一般都取较大的值 但若 取值过大的化 它又会破坏群体中的优良模式 对进化运算反而产生不利影响 若取值过小 的话 产生的新个体的速度又较慢 一般建议的取值范围是o 4 o 9 9 另外也可使用白适应 的思想来确定交叉概率肼 如d a v i s 提山的 随着遗传算法在线性能的提高 可以增大交叉 概率的取值 变异概率p m 若变异概率p 取值较火的话 虽然能够产生较多的新个体 但也又可能破坏掉很多较好 的模式 速度很慢 若变异概率p 取值太小的话 则变异操作产生新个体的能力就会较差 容易出现早熟现象 一般建议的取值范围是o 0 0 l o 1 另外也可使用白适应的思想来确定 如d a v i s 提出 随着遗传算法在线性能的下降 可以减小变异概率的取值 而在w h j t l e y 提 出 变异概率与上一代群体间的海明距离成反比 其结果显示出这种方法能够有效地维持群 体的多样性 终 r 代数t 终止代数t 是表示遗传算法运行结束条件的一个参数 它表示遗传算法运行到指定的进 化代数之后就停止运行 并将当前群体中的最佳个体作为所求问题的最优解输出 一般建议 的取值范围是1 0 0 1 0 0 0 至于遗传算法的终止条件 还可以利用某种判定准则 当判定出群体已经进化成熟且不 再x 进化趋势时就可终止算法的运行过程 常用的判定准则又下面两种 连续几代平均适应度的差异小于某一个极小的阈值 群体中所有个体适应度的方差小于某一个极小的闽值 第二章屉优化方法 2 4 多目标优化算法 最优化处理是在一堆可能地选择种搜索对丁 某些目标来说是最优解地问题 如果仅考虑 一个目标 就成为单目标优化问题 这种问题在过去5 0 年种已经得到了深入地研究 如果存 在的目标超过一个并需要同时处理 就成为多目标优化问题 多目标优化问题起源于许多实 际复杂系统地设计 建模和规划问题 这些系统所在地领域包括工业制造 城市运输 资本 预算 森林管理 水库管理 新城市的布局和美化 能量分配等等 几乎每个重要的现实生 活种的决策问题都要在考虑不同约束的同时处理若干个相互冲突的目标 这些问题大大增加 了问题的复杂程度 自2 0 世纪6 0 年代早期以来 多目标优化问题吸引了越来越多不同背景 研究人员的注意力 许多学者对多目标优化问题作出了重要的贡献 其中p a r e t o 是本领域公 认的开创者