学海网

多目标优化问题的研究概述

  收稿日期: 20100921; 修回日期: 20101108  基金项目: 国家  863 计划资助项目 ( 2009AA04Z161)

  作者简介: 肖晓伟 ( 1984), 女, 陕西宝鸡人,硕士研究生, 主要研究方向为多 目标优化算法及 其在工程中 的应用 ( w ei_bb_zz@ 163. com ); 肖迪

( 1975), 女, 副教授, 主要研究方向为机器学习、图像处理、模式识别; 林锦国 ( 1957), 男, 教授, 主 要研究方向为系 统科学与工程、自动化、模式识

别与图像处理; 肖玉峰 ( 1979), 男, 学士, 主要研究方向为化工工艺设计、过程控制及化工装置安装.

多目标优化问题的研究概述*

肖晓伟 1, 肖  迪 1, 林锦国 1, 肖玉峰 2

( 1. 南京工业大学 自动化与电气工程学院, 南京 210009; 2. 中石油东北炼化工程有限公司 吉林设计院, 吉林

132002)

摘  要: 详细介绍了实际生活中存在的多目标优化问题以及解决多目标优化问题的几种典型算法, 讨论了各个

算法存在的优缺点, 并且列举了近年来在各个领域中出现的多目标优化问题; 最后对多目标优化算法的未来发

展方向进行展望。

关键词: 多目标优化; 进化算法; 粒子群算法; 蚁群算法; 模拟退火

中图分类号: TP3016   文献标志码: A    文章编号: 10013695( 2011) 03080504

do:i 10. 3969 /.j issn. 10013695. 2011. 03. 002

Overview on multiobjective optim ization problem research

XIAO X iaowei1, XIAO D i1, LIN Jin guo1, X IAO Yu feng2

( 1. C ollege of Automation& E lectricalE ngineering, Nanjing University of Technology, Nanjing 210009, China; 2. J ilinD esign Institute, P et

roChinaN ortheastR efining & Chem ical Engineering Co. Ltd, Jilin 132002, China)

Abstract: Th is paper described themu ltiobjective optmi ization problem and several typ ical algorithm s that solvem ultiob jec

tive op tmi ization problem, discussed the advantages and d isadvantages of various algorithm s, and listed themu ltiobjective op

tmi ization problem appeared in the various fields in recent years. Finally, it looked ahead them ultiobjective optmi ization algo

rithm developm ent in the future.

Key words: mu ltiobjective optmi ization; evolutionary algorithm; particle swarm optmi ization; an t colony algorithm; smi u la

ted annealing

0 引言

生活中, 许多问题都是由相互冲突和影响的多个目标组

成。人们会经常遇到使多个目标在给定区域同时尽可能最佳

的优化问题, 也就是多目标优化问题。优化问题存在的优化目

标超过一个并需要同时处理, 就成为多目标优化问题 ( m ultiob

jective optim ization problem, MOP) 。

多目标优化问题在工程应用等现实生活中非常普遍并且

处于非常重要的地位, 这些实际问题通常非常复杂、困难, 是主

要研究领域之一。自 20世纪 60年代早期以来, 多目标优化问

题吸引了越来越多不同背景研究人员的注意力。因此, 解决多

目标优化问题具有非常重要的科研价值和实际意义。

实际中优化问题大多数是多目标优化问题, 一般情况下,

多目标优化问题的各个子目标之间是矛盾的, 一个子目标的改

善有可能会引起另一个或者另几个子目标的性能降低, 也就

是要同时使多个子目标一起达到最优值是不可能的, 而只能

在它们中间进行协调和折中处理, 使各个子目标都尽可能地

达到最优化。其与单目标优化问题的本质区别在于, 它的解并

非唯一, 而是存在一组由众多 Pareto最优解组成的最优解集

合, 集合中的各个元素称为 Pareto最优解或非劣最优解。

1 多目标优化问题的描述

多目标优化问题用文字描述为 D 个决策变量参数、N 个

目标函数、m + n个约束条件组成一个优化问题, 决策变量与目

标函数、约束条件是函数关系。在非劣解集中决策者只能根据

具体问题要求选择令其满意的一个非劣解作为最终解。多目

标优化问题的数学形式可以如下描述 [ 1] :

m in y = f(x ) = [f 1 ( x ), f2 (x ), !, fn ( x ) ]

n= 1, 2, !, N ( 1)

s. t.  g i ( x ) ? 0 i= 1, 2, !, m ( 2)

h j (x ) = 0 j = 1, 2, !, k ( 3)

x = [ x1, x2, !, xd, !, xD ] ( 4)

xd_m in? xd ? xd_m ax d= 1, 2, !, D ( 5)

其中: x 为 D 维决策向量, y 为目标向量, N 为优化目标总数; gi

(x ) ? 0为第 i个不等式约束, hj (x ) = 0 为第 j 个等式约束, fn

(x )为第 n 个目标函数; X 是决策向量形成的决定空间, Y 是目

标向量形成的目标空间。gi (x ) ? 0和 hj (x ) = 0 确定了解的

可行域, xd_m ax和 xd_m in为每维向量搜索的上下限。

对于多目标优化问题中最优解或非劣最优解可进行如下

定义 [ 2] :

第 28卷第 3期

2011年 3月 

计 算 机 应 用 研 究

ApplicationR esearch ofComputers

V o.l 28 N o. 3

M ar. 2011

定义 1 对任意的 d# [ 1, D ]满足 x*

d ? xd 且存在 d0# [ 1,

D ] 有 x*

d 0 < xd 0, 则向量 x* = [ x*

1 , x*

2 , !, x*

D ] 支配向量 x =

[ x1, x2, !, xD ]。

f( x* ) 支配 f (x )必须满足以下两个条件:

n, f n ( x* )? f n ( x )  n= 1, 2, !,N ( 6)

! n0

, fn0

(x* ) < f n0

( x )  1? n0? N ( 7)

f(x )的支配关系与 x 的支配关系是一致的。

定义 2 Pareto最优解是不被可行解集中的任何解支配的

解, 若 x* 是搜索空间中一点, 说 x* 为非劣最优解, 当且仅当不

存在 x (在搜索空间可行性域中 )使得 fn (x ) ? fn ( x* )成立,

n= 1, 2, !, N。

定义 3 给定一个多目标优化问题 f (x ), f (x* )是全局最优

解当且仅当对任意 x (在搜索空间中 ), 都有 f( x* ) ? f( x )。

定义 4 由所有非劣最优解组成的集合称为多目标优化

问题的最优解集 ( Pareto optim al set), 也称为可接受解集或有

效解集。

2 不同算法在多目标优化中的应用

多目标优化问题不存在唯一的全局最优解, 过多的非劣解

是无法直接应用的, 所以在求解时就是要寻找一个最终解。求

最终解主要有三类方法: a) 生成法, 即先求出大量的非劣解,

构成非劣解的一个子集, 然后按照决策者的意图找出最终解;

b)为交互法, 不先求出很多的非劣解, 而是通过分析者与决策

者对话的方式逐步求出最终解; c) 是事先要求决策者提供目

标之间的相对重要程度, 算法以此为依据, 将多目标问题转换

为单目标问题进行求解。而这些主要是通过算法来实现的, 一

直以来很多专家学者采用不同算法解决多目标优化问题, 如多

目标进化算法、多目标粒子群算法和蚁群算法、模拟退火算法

及人工免疫系统等。

2 1 多目标进化算法

多目标进化算法 (MOEA )是一类模拟生物进化机制而形

成的全局性概率优化搜索方法, 在 20世纪 90年代中期开始迅

速发展, 其发展可以分为两个阶段。第一阶段主要有两种方法

即不基于 Pareto优化的方法和基于 Pareto优化的方法; 第二个

阶段就是在此基础上提出了外部集这个概念, 外部集存放的是

当前代的所有非支配个体, 从而使解集保持较好的分布度。这

个时期提出的多目标进化算法更多地强调算法的效率和有效

性。在这两个阶段中, 比较典型的多 目标进化算法有 NS

GA2[ 3] 、PESA2和 SPEA2。对于这三种算法而言, 其优点较多

但是其缺点也比较明显的。如 NSGA2的优点在于运行效率

高、解集有良好的分布性, 特别对于低维优化问题具有较好的

表现; 其缺点在于在高维问题中解集过程具有缺陷, 解集的多

样性不理想。 PESA2的优点在于其解的收敛性很好, 比较容易

接近最优面, 特别是在高维问题情况下; 但其不足之处在于选

择操作一次只能选取一个个体, 时间消耗很大, 而且阶级的多

样性不佳。 SPEA2的优点在于可以取得一个分布度很好的解

集, 特别是在高维问题的求解上, 但是其聚类过程保持多样性

耗时较长, 运行效率不高。

多目标进化算法的基本原理描述如下: 多目标进化算法

从一组随机生成的种群出发, 通过对种群执行选择、交叉和变

异等进化操作, 经过多代进化, 种群中个体的适应度不断提高,

从而逐步逼近多目标优化问题的 Pareto最优解集。与单目标

进化算法不同, 多目标进化算法具有特殊的适应度评价机制。

为了充分发挥进化算法的群体搜索优势, 大多数 MOEA 均采

用基于 Pareto排序的适应度评价方法。在实际应用中, 为使算

法更好地收敛到多目标优化问题的 Pareto最优解, 现有的

MOEA 通常还采用了精英策略、小生境和设置外部集等关键

技术。

MOEA一般框架所描述的算法思想如下: MOEA 通过对种

群 X ( t)执行选择、交叉和变异等操作产生下一代种群 X ( t+ 1)。

在每一代进化过程中, 首先将种群 X ( t)中的所有非劣解个体都

复制到外部集 A ( t)中, 然后运用小生境截断算子剔除A ( t)中的

劣解和一些距离较近的非劣解个体, 以得到个体分布更为均匀

的下一代外部集 A( t+ 1), 并且按照概率 pe 从 A ( t+ 1)中选择

一定数量的优秀个体进入下代种群。在进化结束时, 将外部集

中的非劣解个体作为最优解输出, 如图 1所示 [4] 。

目前, MOEA 研究取得了大量成果, 已被应用于许多领

域, 如工程领域、工业领域和科学领域。其中, 工程领域的应用

最多, 如电子工程、水利工程、风电工程和控制等。

2 2 多目标模拟退火算法

模拟退火 ( SA) 是基于 Monte Carlo迭代求解策略的随机

寻优算法, 是局部搜索算法的扩展。其出发点是固体物质的退

火过程与一般组合优化问题的相似性, 通过模拟固体退火过

程, 从某一初温开始, 随着温度的降低, 结合概率突跳特性在解

空间中搜索最优解, 即在局部解时能概率性地跳出并最终趋于

全局最优。它采用了 M etropolisH astings接受准则, 并用一组

称为冷却进度表的参数控制算法进程 [ 5] 。

模拟退火算法的数学描述为: 在给定邻域结构后, 模拟退

火过程是从一个状态到另一个状态不断随机 游动 , 这个过

程可用马尔可夫链来描述。当温度 t为一定时, 两个状态的移

动概率定义如下:

pij =

G ij ( t)A ij ( t)  j? i且 j# |D |

0 j? |D |

( 8)

A ij不总是等于 1, 即状态也有不被接受的可能, 算法停留在状

态 i的概率为:

pi = 1- %

|D |

i= 1, k? 1

G ik ( t)A ik ( t) ( 9)

式中, pij是下一步转移概率; |D |表示状态集合 (解集合 )中状

态的个数; ij是从 i到 j的产生概率, 表示在状态 i时 j状态被

选取的概率, 可以理解 j是 i的邻域; A ij ( t)是接受概率, 表示在

状态 i产生 j后接受 j的概率, 模拟退火过程中其接受概率为

A ij =

1     f( i) & f( j)

exp( - f ij

t ) f( i) < f( j)

i, j= 1, 2, !, |D | ( 10)

其中, f ( i)为第 j个状态下的目标函数值, fij = f ( j) - f( i)。

模拟退火算法在迭代搜索过程以 M etropolis接受准则接

受目标, 所以具有跳出局部最优的能力, 通用、灵活性高。但是

模拟退火算法对初始温度和退温系数这两个参数的依赖性较

?806? 计 算 机 应 用 研 究  第 28卷

强, 这两个参数选择恰当与否将直接关系到算法性能。

模拟退火算法是一个有效的全局优化算法, 这类算法的最

大优点是对搜索空间 ( 目标函数的性质 ) 不加任何限制, 可以

是不连续的、不可微的, 并且也能求得 Pareto边界上多个不同

方向的 Pareto最优解; 但是其需要大量的迭代次数, 因而收敛

速度慢、优化效率较低。在解决多目标问题时仍将其转换为单

目标问题, 采用单目标技术求解。由于单目标问题与多目标问

题的不同, 在求解时, 往往得不到分布更广的 Pareto最优解集,

即将丢失一部分 Pareto解。

2 3 多目标蚁群优化算法

蚁群算法 ( ant colony algorithm, ACA)是通过模拟自然界蚂

蚁搜索食物的行为提出的仿生优化算法。仿生学家经过大量

细致观察研究发现, 蚂蚁个体之间是通过一种称之为信息素的

物质进行信息传递的。蚂蚁在运动过程中, 能够在它所经过的

路径上留下该种物质, 而且蚂蚁在运动过程中能够感知这种物

质, 并以此指导自己的运动方向。因此, 由大量蚂蚁组成的蚁

群集体行为便表现出一种信息正反馈现象: 某一路径上走过的

蚂蚁越多, 则后来的蚂蚁选择该路径的概率就越大。

蚁群算法的基本原理描述如下: 基于对自然界真实蚁群的

集体觅食行为的研究, 模拟真实的蚁群协作过程。算法由若干

个蚂蚁共同构造解路径, 通过在解路径上遗留并交换信息素的

方法反馈信息提高解的质量, 进而找到最短路径, 达到优化的

目的。

蚁群算法 [ 6] 是一种本质上并行的算法, 可以看做是一个

分布式的多 agent系统, 它在问题空间的多点同时开始进行独

立的解搜索, 不仅增加了算法的可靠性, 也使得算法具有较强

的全局搜索能力。其正反馈的过程不仅能够使得初始值不断

地扩大, 同时又可以引导整个系统向最优解的方向进化。同

时, 蚁群算法的求解结果不依赖于初始路线的选择, 而且在搜

索过程中不需要进行人工的调整。但是蚁群算法需要较长的

搜索时间, 易于出现早熟停滞现象。

2 4 多目标粒子群算法

粒子群优化算法 ( PSO )是一种源于对鸟群捕食行为的研

究而发明的进化计算技术, 最先由 Barnhart博士和 Kennedy博

士于 1995年提出 [ 7] 。它是一种基于迭代的优化工具, 系统初

始化一组随机解, 通过迭代搜寻最优值, 不但具有全局寻优能

力, 而且具有较强的局部寻优能力。在基本粒子群算法 [ 8, 9]

中, 粒子群由 n 个粒子组成, 每个粒子的位置 x i 代表优化问题

在 D 维搜索空间中潜在的解。粒子在搜索空间中以一定的速

度飞行, 这个速度根据它本身的飞行经验和同伴的飞行经验

来动态调整下一步飞行方向和距离。所有的粒子都有一个被

目标函数决定的适应值, 并且知道自己到目前为止发现的最

好位置 (个体极值 p i )和当前的位置 (x i )。除此之外, 每个粒

子还知道到目前为止整个群体中所有粒子发现的最好位置

(全局极值 pg ), 是所有最好位置中的最优值。

粒子群算法的数学描述如下 [ 10] : 每个粒子 i包含为一个 D

维的位置向量 x i = ( xi1, xi2, !, x iD )和速度向量 v i = ( vi1, vi2,

!, viD ), 粒子 i搜索解空间时, 保存其搜索到的最优经历位置

p i = (p i1, pi2, !, piD )。在每次迭代开始时, 粒子根据自身惯性

和经验及群体最优经历位置 pg = (pg1, pg2, !, pgD )来调整自己

的速度向量以调整自身位置。 c1、c2 是正常数, 称之为加速因

子; r1、r2 为 [ 0, 1] 中均匀分布的随机数, d 为 D 维中的维数;

是惯性权重因子。其中, 每个粒子的位置和速度更新按下式

进行 [ 11] :

xt+ 1

id = x t

id + vt+ 1

id ( 11)

v t+ 1

id = vt

id + c1 r1 ( pt

id - xt

id ) + c2r2 ( pt

gd - xt

id ) ( 12)

式 (12)由三部分组成, 第一部分是粒子原来的速度, 其值

越大, 越利于全局搜索, 其值小则利于局部搜索能力, 具有平衡

全局和局部搜索的能力; 第二部分是粒子本身的思考, 表明粒

子自身经验对当前搜索倾向的吸引程度, 受到 c1 r1 的随机调

整, 是对粒子所积累经验的利用, 使粒子有了足够强的全局搜

索能力, 避免局部极小; 第三部分是粒子学习其他粒子经验的

过程, 表明粒子间信息的共享和社会协作, 受到 c2 r2 的随机调

整, 并与 pg 的位置和种群的领域拓扑结构直接相关。在这三

部分的共同作用下, 粒子根据自己的经验并利用信息共享机制

不断调整自己的速度与位置, 从而有效地到达最好位置 [ 12] 。

粒子位置在每一代的上述更新方式可用图 2来描述。

由于粒子群算法具有高效的搜索能力, 有利于得到多目

标意义下的最优解; 通过代表整个解集种群, 按并行方式同时

搜索多个非劣解, 也即搜索到多个 Pareto最优解; 同时, 粒子群

算法的通用性比较好, 适合处理多种类型的目标函数和约束,

并且容易与传统的优化方法结合, 从而改进自身的局限性, 更

高效地解决问题。因此, 将粒子群算法应用于解决多目标优化

问题上具有很大的优势。

粒子群算法思想描述如下: 初始化种群后, 种群的大小记

为 N。基于适应度支配的思想, 将种群划分成两个子群, 一个

称为非支配子集 A, 另一个称为支配子集 B, 两个子集的基数

分别为 n1、n2, 满足两个子群基数之和为 N [ 13] 。外部精英集用

来存放每代产生的非劣解子集 A, 每次迭代过程只对 B 中的粒

子进行速度和位置的更新, 并对更新后的 B 中的粒子基于适

应度支配思想与 A 中的粒子进行比较, 若 x i# B, ! x j # A, 使得

x i 支配 x j, 则删除 x j, 使 x i 加入 A 更新外部精英集; 且精英集

的规模要利用一些技术维持在一个上限范围内, 如密度评估技

术、分散度技术等。最后, 算法终止的准则可以是最大迭代次

数 Tm ax、计算精度 !或最优解的最大凝滞步数 t等。其具体

步骤如图 3[ 14]所示。

图 3中, t是迭代的代数, x i 是第 i个粒子的位置坐标, vi

是第 i个粒子的速度, p i 是粒子的个体极值, pg 是粒子群的全

局极值。

粒子群算法是一种新兴起的优化算法, 其每个粒子根据自

身的最优位置和群体全局的最优位置更新自己的速度和位置,

各粒子由于群体全局的最优位置的影响, 很快收敛到全局最优

位置附近, 这已显示出它的快速性、有效性和鲁棒性等多种优

?807?第 3期 肖晓伟, 等: 多目标优化问题的研究概述   

点。目前, 多目标粒子群优化算法也已成功用于函数优化、神

经网络训练、模式分类、模糊系统控制以及其他的应用领域。

3 实际中的多目标优化问题

在工程应用、生产管理以及国防建设等实际问题中很多优

化问题都是多目标优化问题, 它的应用很广泛。

1)物资调运车辆路径问题

某部门要将几个仓库里的物资调拨到其他若干个销售点

去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程

中所要走的公里数最少和总的运输费用最低, 这是含有两个目

标的优化问题。利用首次适配递减算法和标准蚁群算法对救

灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得

结果进行了比较 [ 15] 。

2)设计

如工厂在设计某种新产品的生产工艺过程时, 通常都要求

产量高、质量好、成本低、消耗少及利润高等, 这就是一个含有

五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹

的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,

这就是一个含有四个目标的最优化问题。 Jo等人 [ 16] 将遗传算

法与有限元模拟软件结合应用于汽车零件多工序冷挤压工艺

的优化。 Chung等人 [17]也成功应用遗传算法对锻件工艺进行

了优化。

3)投资

假设某决策部门有一笔资金要分配给若干个建设项目, 在

确定投资方案时, 决策者总希望做到投资少收益大。 Branke等

人采用基于信封的多目标进化算法成功地解决了计划投资地

选择问题 [ 18] 。

4)模拟移动床过程优化与控制

一个工业化模拟移动床正常运行时, 一般有七股物料进、

出吸附塔, 其中起关键作用的物料口将作为决策量引起目标值

的变化。根据实际生产要求通常包括生产率、产品纯度、吸附

剂消耗量等多个目标。模拟移动床分离过程由于其过程操作

变量的强耦合性、工艺机理的复杂性及分离性能的影响因素繁

多性, 需要众多学者对其操作优化和过程控制进行深入的研

究。Huang等人利用 TPS 算法解决了模拟移动床多个冲突目

标的最大 最小的问 题, 并与 NSGA2 算法 的结果进 行了比

较 [ 19] 。吴献东等人运用粒子群算法开发出一种非线性模拟移

动床 ( SMB )色谱分离过程的优化策略 [20]。

5)生产调度

在离散制造生产系统中, 一个工件一般经过一系列的工序

加工完成, 每道工序需要特定机器和其他资源共同完成, 各工

件在各机器上的加工顺序 (称为技术约束条件 )通常是事先给

定的。车间调度的作用就是根据现有的资源状况合理地安排

作业加工顺序, 以满足特定生产目标的要求, 一般包括作业排

序和资源分配两个目标。进化算法已在此问题中得到有效应

用 [ 21, 22]。 Liu等人基于 PSO算法提出一种有效的混合算法求

解了无等待的流水车间调度问题以最小化制造跨度 [23]。 Jer

ald等人利用 PSO算法求解了柔性调度系统中, 目标为同时最

小化机器闲置时间和总惩罚成本的调度问题 [ 24] 。

由此可以看出, 在实际中存在很多关于多目标优化问题,

如何解决这些多目标优化问题就显得十分重要。而多目标进

化算法和多目标粒子群算法是用得比较多的解决多目标优化

问题的算法, 尤其是粒子群算法在解决多目标优化问题中具有

很多优势。

4 结束语

多目标优化问题是近年来人们越来越需要面对和解决的

问题, 而很多学者已经利用不同算法解决了实际中的一些多目

标优化问题, 但是各种算法都有其自身的缺陷。因此如何利用

更有效的手段解决多目标优化问题具有非常重要的意义。为

此, 总结未来的工作可以从以下几方面进行:

a)MOP算法的理论研究。继续加强各种多目标优化算法

的基础理论研究, 发展新的数学分析工具, 并建立更有效的性

能评价准则及算法的终止条件标准。

b)MOP的算法研究。对于复杂的高维多目标优化问题,

研究新的群体排序方法, 进一步加强搜索能力。注重各种多目

标优化算法或策略的结合, 取其各方面的优点进行综合。

c)MOP算法的应用研究。实际工程工业知识与多目标算

法的结合, 有针对性地根据多目标优化问题的特点, 结合相关

领域知识, 发展各种新的专门的多目标优化算法, 取得更优的

效果。

随着各种多目标优化算法的不断发展, 更多领域的多目标

优化问题必将被成功解决。

参考文献:

[ 1] 钱伟懿, 李阿军, 杨宁宁. 基于混沌的多目标粒子群优化算法 [ J].

计算机工程与设计, 2008, 29( 18): 47944800.

[ 2] TSA I S J, SUN T Y, LIU Chancheng, et al. An im provedm ultiob

jective particle sw arm optim izer form ultiobjective problem s[ J]. Ex

pertSystem sw ith Applica tions, 2010, 37( 8): 58725886.

[ 3] KUNDU P K, ZHANG yan, RAY A K. Multiobjective optim ization

of sim ulated countercurrent m oving bed chrom atographic reactor for

ox idative coupling of m ethane [ J]. Chem ical Eng ineering Sci

ence, 2009, 64( 19): 41374149.

[ 4] 马清亮, 胡昌华. 多目标进化算法及 其在控制 领域中的 应用综述

[ J]. 控制与决策, 2006, 21( 5): 481486.

[ 5] 王斌, 尚新春, 李 海峰. 解 决车辆 路径问 题的混 合模 拟退 火算法

[ J]. 计算机工程与设计, 2009, 30( 3): 651653.

[ 6] 兰世海. 改进蚁群算法研究及其在车辆调度中的 应用 [ D]. 上海:

东华大学, 2007.

[ 7] KENNEDY J, EBERHART R C. Particle sw arm optim ization[ C ] / /

P roc of IEEE International C onference on N eural Netw orks. 1995:

19421948.

[ 8] COELLO C A, PULIDO G T, LECHUGA M S. H andlingm ultiple ob

jectivesw ith particle sw arm optim ization[ J]. IEEE T rans on Evolu

tionary Computation, 2004, 8( 3): 256279.

[ 9] COELLO C A, LECHUGA M S. MOPSO: a proposal for multiple ob

jective particle sw arm optim ization[ C ] / /Proc of IEEE C ongress on

E volutionary Computation. Piscataw ay: IEEE Press, 2002: 1051

1056.

[ 10] 薛洪波, 伦淑娴. 粒子群算法在多目标优化中的应用综述 [ J]. 渤

海大学学报, 2009, 30( 3): 265269.

[ 11] SH I Yuhu,i EBERHART R C. A m odified particle sw arm optim izer

[ C ] / /Proc of IEEE International Conference on E volutionary Compu

tation. P iscataw ay: IEEE Press, 1998: 6973.

[ 12] EBERHART R, KENNEDY J. A new optim izer using particle sw arm

theory[ C ] / /Proc of the 6th International Sym posium on M icro M a

chine and H um an Science. 1995: 3943. (下转第 827页 )

?808? 计 算 机 应 用 研 究  第 28卷

ference on ShapeM odeling and Applications. 2003: 207215.

[ 31] DESCHAMPS T, COHEN L D. Fast extraction of m inim al paths in

3D im ages and applications to v irtua l endoscopy[ J]. Mecical Image

Analysis, 2001, 5( 4): 281299.

[ 32] HASSOUNA M S, FARAG A A. Robust centerline extraction fram e

w ork using level sets[ C ] / /Proc of IEEE Computer V ision and Pattern

Recognition. Washington DC: IEEE C om puter Society, 2005: 458

465.

[ 33] U ITERT vanR L, SUMMERSR M. Autom atic correction of level set

based subvoxelprecise centerlines for virtual colonoscopy using the co

lon outer w all[ J]. IEEE T rans on M edical Imag ing, 2007, 26

( 8): 10691078.

[ 34] HASSOUNA M S, FARAG A A, HUSHEK S G. 3D path planning

for virtual endoscopy[ C ] / /Proc of the International C ongress Series

1281. 2005: 115120.

[ 35] K IM D Y, CHUNG SM, PARK JW. Autom atic navigation path gen

eration based on tw ophase adaptive reg iongrow ing algorithm for virtu

al ang ioscopy [ J]. M edical Engineering & Physics, 2006, 28

( 4): 339347.

[ 36] 吕新荣, 高新波, 邹华. 基于医学影像的血管快速提取与可视化

[ J]. 中国生物医学工程学报, 2009, 28( 4): 527535.

[ 37] K IRALY A P, HELFERTY J P. Threedim ensional path planning for

virtual bronchoscopy[ J]. IEEE T rans on Med ical Imag ing, 2004,

23( 9): 13651379.

[ 38] JANDT U, SCH FER D, GRASSM, et al. Autom atic generation of

3D coronary artery centerlines using rotationalXray angiography[ J].

Med ica l Imaging Ana lysis, 2009, 13( 6): 846858.

[ 39] L IH ua, YEZZI A. Vessels as 4D curves: globalm inim al 4D paths

to extract 3D tubular surfaces and centerlines[ J]. IEEE T rans on

Med ica l Imaging, 2007, 26( 9): 12131223.

[ 40] HAYASH I Y, MORI K, HASEGAWA J, et al. A m ethod for detec

ting undisplayed regions in virtual colonoscopy and its application to

quantitative eva luation of flythroughm ethods[ J]. Academ ic Radi

ology, 2003, 10( 12): 13801391.

[ 41] HASSOUNA M S, FARAG A A. PDEbased three dim ensional path

planning for virtual endoscopy [ C ] / /Proc of the 19th International

C onference on Inform ation Processing M edica l Im ag ing. Berlin:

Springer, 2005: 529540.

[ 42] LEE J, KIM G, LEE H, et al. Fast path planning in virtual colonos

copy[ J]. Com puters in Biology and M edicine, 2008, 38 ( 9):

10121023.

[ 43] H E Taosong, HONG L ichan, CHEN Dongqing, et al. Reliable

path for v irtual endoscopy: ensuring com plete exam ination of hum an

organs[ J]. IEEE T rans on Visualization and Com puter Graphi

cs, 2001, 7( 4): 333342.

[ 44] JIANG R, BERLINER L, MENG J. C om puter graphics enhance

m ents in CT co lonography for im proved diagnosis and navigation

[ C ] / /P roc of the International C ongress Series 1281. 2005: 109

114.

[ 45] HUANG A, SUMMERS R M, ROY D. Synchronous navigation for

CT colonography [ C ] / /Proc of SPIE M edical Im aging C onference.

2006: 18.

[ 46] KWON K J, SH IN B S. An efficient cam era path com putation using

im age space inform ation in virtual endoscopy[ C ] / /Proc of the 19th

International Sym posium on Com puter Sciences. Berlin: Springer,

2004: 118125.

[ 47] KANG D G, RA J B. A new path planning algorithm for m ax im izing

visibility in com puted tomography colonography[ J]. IEEE T rans on

Med ica l Im aging, 2005, 24( 8) : 957968.

[ 48] X IE X iaom ian, TAO Duchun, CHEN Siping, et al. 3D navigation

of CTVE and correction ofM inIP m ethods in noninvasive diagnostic

detection[ J]. Computerized Medica l Imaging and Graph ics,

2006, 30( 6): 383389.

[ 49] BLEZEK D, ROBB R. Centerline algorithm for virtual endoscopy

based on Cham fer distance transform and D ijkstra( s single source

shortest path[ C] / /P roc of SPIE. 1999: 225233.

(上接第 808页 )

[ 13] 金欣磊. 基于 PSO的多目标优化算法研究及应用 [D ]. 杭州:浙江

大学, 2006.

[ 14] 郑友莲, 樊俊青. 多目标粒子群优化算法研究 [ J]. 湖北大学学报,

2008, 30( 4): 351355.

[ 15] 刘晨帆, 陈换新, 徐振. 一种利用网络分析实现高效救灾物资运输

的方法 [ J]. 测绘与空间地理信息, 2009, 32( 5): 121126.

[ 16] JO H H, LEE SK, KO D C, et al. A study on the optim al tool shape

design in a hot form ing process[ J]. Journal of Materia ls Proces

sing Techno logy, 2001, 111( 13): 127131.

[ 17] CHUNG J S, HWANG SM. Process optim al design in forging by ge

netic algorithm s[ J]. Journa l ofManufacturing Science and Engi

neering, 2002, 124( 2): 397408.

[ 18] BRANKE J, SCHECKENBACH B, STE INM, et al. Portfolio optim i

zation w ith an envelopebase m ultiobjective evolutionary algorithm

[ J]. European Journal of Operational Research, 2009, 199

( 3): 684693.

[ 19] HUANG L iang, SUN Le,i WANG N ing, et al. M ultiobjective opti

m ization of simulated m oving bed by tissue PSystem [ J]. Ch inese

Journa l of Chem ical Eng ineering, 15( 5): 683690.

[ 20] 吴献东, 金晓明, 徐志成, 等. 微粒群 算法在模 拟移动床 色谱分离

过程优化中的应用 [ J]. 化工自动化及仪表, 2006, 33( 4): 58.

[ 21] TSU JIMURA Y, GEN M. Genetic algorithm s for solving and m ulti

processor scheduling problem s[ C ] / /Proc of the 1stA siaPacificC on

ference on Simulated E volution and Learning. London: SpringerVer

lag, 1996: 106115.

[ 22] MORIKAWA K, FURUHASH I T, UCH IKAWAY. C ooperation and

evolution of scheduling system w ith genetic algorithm s[ C ] / /Proc of

IEEE International Conference on Evo lutionary Com putation. 1996:

491497.

[ 23] L IU Bo, WANG Ling, JIN Y ihu.i An effective hybrid particle sw arm

optim ization for now ait flow shop scheduling [ J]. Interna tional

Journa l of Advanced Manufacturing Techno logy, 2007, 31 ( 9

10): 10011011.

[ 24] JERALD J, ASOKAN P, PRABAHARAN G, et al. Scheduling op

tim isation of flexible system s using particle sw arm optim isation algo

rithm [ J]. Internationa l Journa l o f Advanced M anufacturing

Techno logy, 2005, 25( 910): 964971.

?827?第 3期 高向军, 等: 虚拟内窥镜的路径规划算法研究   


多目标优化问题的研究概述.pdf