一种改进的非支配排序遗传算法

D0I:10.13374/i.issm1001053x.2002.06.025 第24卷第6期 北京科技大学学报 Vol.24 No.6 2002年12月 Journal of University of Science and Technology Beijing Dec.2002 一种改进的非支配排序遗传算法 吴中元2关志华)李光泉” 1)天津大学系统工程研究所，天津3000722)天津工业大学管理学院，天津300065 摘要为克服非支配排序遗传算法计算复杂度高，未采用精英策略，需要特别指定共享半径 的缺点，提出了一种改进的非支配排序遗传算法.通过实验验证，该算法在几个给定的函数优 化时都能取得比较好的结果. 关键词NSGA;NSGA;计算复杂性；精英策略；共享 分类号TP18 近年来，多目标进化算法领域出现了许多 1改进的非支配排序遗传算法 新的算法，由于可以在一个进化代中得到多 个不同的Pareto优化解，多目标进化算法在多 NSGA在许多问题上得到了应用uo.,算法 目标优化领域已成为一个新的研究热点.文献 流程见图1.主要思想是对所有个体按照非支 [5]提出的非支配排序遗传算法NSGA (Non- 配顺序进行排序，然后用指定的顺序适应度代 dominated Sorting Genetic Algorithm),把非支配 替原适应度计算，直到种群中的所有个体都分 排序的概念引入了多目标优化领域，取得了较 级为止 好的效果.但NSGA本身存在许多不足之处，使 得它在处理高维、多模态等问题时，难以得到满 进化代数gen-0 初始化种群 意的结果.NSGA存在的主要问题是：(1)计算复 杂性较高，为O(mW),其中m表示目标函数个数， front 1 N表示种群规模.当处理大种群问题时，计算代 进化代数 种群全 No 、部分级 识别非支配个体 价十分大，尤其是当种群在每代都需要进行排 gen=gen 1 Yes 序时，这种消耗则更明显.(2)缺乏精英策略.最 根据虚拟 指定虚拟适应度值 适应度进 近的研究刀表明，精英策略可以明显改善遗传 行复制 应用适应度共享（小生境法） 算法的收敛特性，同时可以避免丢失进化过程 交叉 重新指定共享后的虚拟适应度值 中取得的最优解，(3)需要特别指定共享半径 oe·共享可以确保种群的多样性，但对于共享 变异 从种群中忽路己分级非支配解 半径的取值仍是一个很难确定的问题.文献[8] 虽然尝试采用动态参数调整，但仍没有摆脱共 Yes 华 front=front+1 享半径参数的选择过程. No 本文在对NSGA存在的上述三方面问题进 终止 行研究的基础上，提出了一种改进的非支配排 图1NSGA算法流程图 序遗传算法NSGA(Improved Non--dominated Fig.1 NSGA flow chart Sorting Genetic Algorithm).通过和NSGA算法进 行比较可以看出：改进后的算法所得到的Pareto 1.1方法的改进 改进的非支配排序方法和原NSGA的主要 曲线分布更加均匀，所得到的解也更好 区别在于需要计算两个参数，即：①，群体中 收稿日期200106-21吴中元男，37岁，博士研究生 支配个体i的解个体的数量，②S,被个体i所 *国家自然科学基金项目资助项目(N0.69974026) 支配的解个体的集合，首先，找到群体中所有的

第 2 4 卷 第 6 期 2 00 2 年 1 2 月 北 京 科 技 大 学 学 报 J o u r n a l o f U n iv e r s ity o f S c i e n e e a n d eT e h n o l o gy B e ij in g V b l . 2 4 N 0 . 6 D e e . 2 0 0 2 一种改进的非支配排序遗传算法 吴 中元 ’ ,2) 关志 华 ” 李光泉 ” l) 天津大学系统工程研究所 , 天津 3 0 00 72 2) 天津工业大学管理学院 , 天津 3 00 0 65 摘 要 为克服非 支配排 序遗传算法计算 复杂度 高 , 未采用 精英策 略 , 需要特 别指定 共享半 径 的缺点 , 提 出 了一 种改进 的非支配排序遗 传算法 . 通过 实验验证 , 该算法在几 个给定 的 函数优 化 时都能取 得 比较好 的结果 . 关键词 N SG A ; NI SG A ; 计算复杂性 ; 精英策略 ; 共享 分类号 T P 18 近 年来 , 多 目标进化算法领域出 现了 许多 新 的算法 〔卜 4] , 由于可 以在一个进化代 中得到多 个不 同的 Par et o 优化解 , 多 目标进化算法在多 目标优化领域 已成为一个 新的研 究热 点 . 文献 5[] 提 出的非支配排 序遗传算 法 N s G A 困on - d o m 认at e d s ort i飞 o e n et i c A l g o ir t h m ) , 把非支配 排序 的概念引人 了多 目标优化领域 , 取得 了较 好的效果 . 但N S G A 本身存在许多不足之处 , 使 得它在处理高维 、 多模态等问题时 , 难 以得到满 意的结果 . N S G A 存在 的主要 问题是 : ( l) 计算 复 杂性较高 , 为 O伽 N 3 ) , 其 中。 表示 目标 函数个数 , 万表示 种群规模 . 当处 理大种群 问题时 , 计算 代 价十分大 , 尤其是 当种群在每代都需要进行排 序时 , 这种 消耗则更 明显 . (2) 缺乏精英策略 . 最 近 的研究 伪 ,7] 表 明 , 精英策略可 以 明显改善遗传 算法 的收敛特性 , 同时可 以避免丢失进化过程 中取得 的最优解 . (3) 需 要特别指定共享半径 氏ha . 共享可 以确保种群的多样 性 , 但对于 共享 半径的取值仍是一个很难确定 的问题 . 文献 8[ ] 虽 然尝试采用 动态参数调 整 , 但仍没有摆脱共 享半径参数 的选择过程 . 本文在对 N S G A 存在的上述三方面问题进 行研究 的基础上 , 提 出 了一种改进 的非支配排 序 遗 传 算 法 NI S G A 以m p or ve d No n 一 do m ian t ed s ort in g G en iet c A lgo r it h m ) . 通过和 N S G A 算法进 行 比较可 以看出: 改进后的算法所得到的 Par et o 曲线分布更加均匀 , 所得到 的解也更好 . 1 改进的非支配排序遗传算法 N S G A 在许多 问题上得到 了应用 ’ l0, , , , , 算法 流程见 图 1 . 主要 思 想是对所有个 体按照 非支 配顺 序进 行排 序 , 然后用指定 的顺序适应度代 替原适应度计 算 , 直到种群 中的所有个体都分 级为止 . 进化代数 ge 二O 初始化种群 丘O in 二 1 进化代数 g e n = g e n + l 根据虚拟 适应度进 行复制 变异 识别非支配个体 指定虚拟适应度值 应用适应度共享 (小生境法 ) 重新指定共享后的虚拟适应度值 从种群中忽略 己分级非支配解 斤。 nt = 斤。 nt + 1 图 1 N SG A 算法流 程 图 F ig . 1 N S G A n ow e h a rt 收稿 日期 2 0 01 一6一 1 吴 中元 男 , 37 岁 , 博士研究 生 * 国家 自然科学 基金项 目资助项 目困 0 . 6 9 9 7 4 0 2 6) L l 方法 的改进 改进 的非 支配排序方法 和原 N S G A 的主 要 区 别在于 需要 计算 两个参 数 , 即 : ① 拼 , 群体 中 支配个体 i 的解个体 的数量 , ② 民 , 被个体 i 所 支配的解个体的集合 . 首先 , 找到群体 中所有的 DOI: 10. 13374 /j . issn1001 -053x. 2002. 06. 025

·680· 北京科技大学学报 2002年第6期 n:=0的个体，将其存人当前集F;然后，对于当 这里，L[m表示集合L中的第个个体对于第m个 前集F,中的每个个体了，考察它所支配的个体集 目标函数的值.sort(L,m)指对个体进行非支配排 S,将集S,中的每个个体j的支配它的个体数量 序，算法的复杂性取决于排序的复杂性，最极端 n一1（因为支配个体j的个体已经存人了当前集 情况下为O(mNlogN). F),如果个体j的支配它的个体数量2=0，则将 1.3拥挤度比较 个体存入另一个集H.最后，将得到的当前集F 拥挤度比较是确保算法能收敛到一个均匀 作为第一级非支配个体集.继续对集H进行分 分布的Pareto曲面.经过排序和拥挤度计算，群 级操作，直到所有个体均被分级为止算法的总 体中的每个个体都得到两个属性：①非支配序 体复杂度为O(mW),在最极端的情况下存储开 i,;②密度iu.则定义偏序关系≥为：2j,如果 销为ON).上述的非支配排序的伪代码如下(P j,或者，=，且>j:.上式的意义为：如果两个 为种群，F为非支配个体集) 个体的非支配排序不同，取序号低的个体（分级 函数sort(P)定义为： 排序时，先被分离出来的个体)；如果两个个体 对每一个peP,q∈P, 在同一级，取周围较不拥挤的个体. 若p<q,则S,=SU{q}; 1.4NSGA算法流程 否则，若q<p,则n,=n+1. 随机初始化一个父代种群P。,将种群中的 若n,=0,则F=FU{p以. 所有个体按菲支配排序，根据非支配排序的级 i=1, 别给每个个体指定一个适应度值，比如可以指 当F卡⑦，H=O, 定这个适应度值等于非支配排序的级别，则1 对每一个p∈F,q∈S,n=n,一1. 是最佳适应度值.采用选择、交叉、变异等遗传 若n,=0,则H=HU{g}. 算子产生一个子代种群Q.从第一代开始主流 i=i计1， 程如下： F=H. R,=P,UO,F=sort(R,). 1.2确定拥挤度 若P+kW, 定义拥挤度为在种群中给定点周围个体的 计算集合F:的拥挤度， 密度，用表示，它指出了在个体周围包含个体 P=PUF 本身但是不包含其他个体的最小的长方形，如 sort(P+,≥)，PH=P[0: 图2所示. 通过遗传算子作用产生新种群2， t=t+1. 首先产生一个组合的种群R,=PUQ,种群R, 的个体数为2N.然后种群R根据非支配关系排 序，新的父代种群由当前的第一级非支配个体 填充，直到个体数量达到W就形成了新的父代 +1 0 种群P,然后在此基础上进行遗传操作，形成 子代种群2.算法的整体复杂性为OmW).非 图2个体i的拥挤度 支配解的多样性由拥挤度比较过程保证，通过 Fig.2 Crowing of i 计算得出个体所在区域的密度，算法不需要额 外的共享参数.通过对当前解和种群中所有个 用L表示个体密度集合，1=L.拥挤度计算 体的分级存放，算法维持着两个集合F,H,正是 的伪代码如下： 由于这两个集合才确保最佳个体不会丢失. 对每一个个体i,令L[la=0. 对每一个目标函数m, 2实验测试 L=sort(L,m), L[1]4=L[04=oo. 采用NSGA对三个测试函数进行了计算， 从i=2到1-1循环， 并与由NSGA计算得到的结果进行了对照（三 Llil=L[il(L[i+1).-L[i-1]). 个测试函数均为最小化问题)

. 6 8 0 - 北 京 科 技 大 学 学 报 2 0 0 2 年 第 6 期 n ` 二 0 的个 体 , 将其 存人 当前集名 ; 然后 , 对 于当 前集凡 中的 每个个体 j , 考察它所支配的个体集 及 , 将集及中的每个个体 j 的支配 它的个 体数量 nj 一 l( 因为支配个 体j 的个体 已 经存人 了 当前集 月 ) , 如果个体 j 的 支配它的个 体数 量nj = o , 则将 个钩存人 另一个集.H 最后 , 将得到的 当前集名 作 为第一级非支 配个体集 . 继续对集州左行分 级操作 , 直到所有个体均被分级为止 . 算法的总 体复杂度 为 O( m N 2 ) , 在最极 端的情况下存储 开 销 为口(矿) . 上述 的非支 配排 序的伪代码如下伊 为种群 , F 为非支配个体集 ) . 函数 so rt 卿定义为 : 对每一个 p 任 p , q 任尸 , 若尸K q , 则凡一 又u {好 ; 否则 , 若 q印 , 则伟 = 伟+1 . 若伟 二 o , 则月 = 凡 u 切} . i 二 l , 当只 羊 O , H 二 ② , 对每一 个尸任只 , q 任及 , n , = n 。一 1 . 若 n 。 = 0 , 则H “ H U {砂 . i = +1 1 , 月 二 .H L Z 确定拥挤度 定义拥挤度 为在种群 中给定点周 围个体的 密度 , 用耘表示 , 它指 出了在个体周 围包 含个体 i本身但是不包含其他个体的最小 的长方形 , 如 图 2 所 示 . 0 0 0 _ 。 O 图 2 个体 i 的拥挤 度 F i g · 2 C r o , v i n g o f i 用L 表示个体 密度集 合 , =l 囚 . 拥挤 度计算 的伪代码如下 : 对每一个个体 i , 令双i] J = .0 对每一个 目标 函数 m, L = s o rt (L , m ) , L t l d = L「月 己二 二 . 从 卜 2 到l一 1循环 , L [ i ] 己 = L [ i ]+d (L [’+l l ] 。 一 L [ i 一 l ] , ) . 这里 , lL ilm 表示集合L 中的第i个个体对于 第m 个 目标 函数 的值 . s o rt (L , m) 指对个体进行非支配排 序 , 算法 的复杂性取决于排序 的复杂性 , 最极端 情况下为 口(阴刃 lo g N) · 1.3 拥挤度 比较 拥挤度 比较是确保算法能收敛到一个均匀 分布 的 P ar e ot 曲面 . 经过排序和 拥挤度计算 , 群 体 中的每个个体 i都得 到两个属 性 : ①非支配序 ;ir ② 密度耘 . 则定义偏序关 系全 。为 : 泛 。 j , 如果 吞>jr 或者 ir 移且耘>’ja . 上式 的意义为 : 如果两个 个体的非支配排序不 同 , 取序号低 的个体 (分级 排序时 , 先被分离 出来 的个体 ) ; 如果 两个个体 在同一级 , 取周 围较不拥挤 的个体 . 1.4 I N S G A 算法流程 随机初 始化一个父代种群0P , 将种群 中的 所有个体按非支配排序 , 根据非支配排 序的级 别给每个 个体指定一个适应度 值 , 比如 可以 指 定这个适 应度值等于 非支 配排 序的级别 , 则 1 是最佳适应 度值 . 采用选择 、 交 叉 、 变异等遗传 算子 产生一个 子代种群 OQ . 从第一代开始 主流 程如 下 : R , = P, u g , F 二 so rt (R .t) 若 I凡 1 1N< , 计算集合双 的拥挤度 , 只 , = +tP I U只 , s o rt (pH 1 , 全 。 ) , 凡 , = 凡 : [ 0 :叼 . 通过遗传算子作用 产生新种群必 1 . t = +t 1 . 首先产生一个组合 的种群 R , = P, u Q , 种群tR 的 个体数为 Z.N 然后 种群R, 根据非 支配关系 排 序 , 新 的父代种 群 由当前 的第一级非 支配个体 填充 , 直到个体数量达到刃就形成 了新 的父 代 种群+tP , , 然后在此基 础上进行遗传操作 , 形成 子代 种群+tQ 1 . 算 法的整体复杂性为 o( m N 2 ) . 非 支 配解 的多样性 由拥挤度 比较 过程保证 , 通 过 计算得 出个体 所在 区域 的密度 , 算法不需要额 外 的共享参数 . 通过对 当前解 和 种群 中所有个 体的分级存放 , 算法 维持 着两个集合 F, H , 正是 由于这两个集 合才确保最佳个体 不会 丢失 . 2 实验测试 采用 创 S G A 对三个测 试函 数进行 了计算 , 并与 由 N S G A 计算得 到的 结果进行 了对照 (三 个测试 函数均为最小 化问题 )

Vol.24 吴中元等：一种改进的非支配排序遗传算法 681 闭=1-em-部-h 其中，-5≤xx2x≤5 F: 对于所有的测试问题，NSGA采用的参数 5闭=1-e-+方 为：实数编码方式，种群规模为100，联赛选择， 其中，-4≤xxx3≤4. 联赛规模为2，均匀交叉2，交叉概率为0.8，变 F f(x)=[1+(A-B,+(A2-B)] 异算子为非均匀变异，变异概率为7为变量 5(x)=[(x+3}2+(y+1)] 个数)，进化代数为250代.对于对照算法采用 这里， NSGA:实数编码方式，种群规模为100，联赛选 A,=0.5sin1-2cos1+sin2-1.5cos2, 择，联赛规模为2，均匀交叉，交叉概率为0.8，变 A:=1.5sin1-cos1+2sin2-0.5cos2, 异算子为非均匀变异，变异概率为01，进化代 B=0.5sinx-2cosx+siny-1.5cosy, 数为250代，目标函数空间共享.计算所得到的 B2=1.5sinx-cosx+2siny-0.5cosy. Pareto曲线见图3.从图3可以看出，采用NSGA =-10exp(-0.2V+a1 得到的Pareto曲线分布更均匀，且解的精确度 F3: 也较高. 56x)=Ik+5 ssin(x)】 1.2 1.2 (a) (b) 10 NSGA 1.0 INSGA 0.8 0.8 三0.6 三0.6 0.4 0.4 0.2 0.2 0 0.5 1.0 1.5 0 0.5 1.0 1.5 25 (c) (d) 20 NSGA INSGA 20 15 10 10 0 10 15 20 0 10 15 20 (e) () NSGA INSGA -12 -12 -20 -18 -16 -14 -20 -18 -16 -14 图3函数F,F,F的Pareto曲线，(a),(b)为函数F;(c,(d)为函数F;(e,(⑨为函数R Fig.3 Pareto front of F,Fi,Fs

V bl 一 2 4 吴 中元等 : 一种 改进 的非 支配排序 遗传算 法 妇 | I 们J ù ; 、少. 、产卫J es . 了尹.1 . J 了产1」 一誊卜 - 一 睿卜 + 其中 , 这里 , 。 : 长思 = 「l + (A : 一 B , ) 2+ 扭 2 一及 ) , 〕 = 【+x( 3 ) , + +y( l ) , ] A , = 0 . s s i n l 一 Zc o s l + s lnZ 一 1 . s e o s Z , A Z = 1 . s s in l 一 c o s l + 2 s ln2 一 0 . s e o s Z , B l 二 0 . s s lnx 一 Z e o sx + s iny 一 l . s e o sy , B Z = 1 . s s ixn 一 e o s x + Zs iyn 一 0 . s e o sy . x() 一 戳 一 e10 xP (一 .02 丫不霖乃〕 x() = 乏仁阮1 0 · ` + s s in x(t) , 〕 其 中 , 一 5 三 xl 丙丙` .5 对 于所有 的测试 问题 , m SG A 采用 的参数 为 : 实数 编码方式 , 种群规模为 10 , 联赛选择 , 联赛规模为 2 , 均匀交叉12[ ,13] , 交叉概率为 .0 8 , 变 异算 子为非均匀变异 , 变异概率 为告(n 为变量 个数 ) , 进化代数 为 2 50 代 . 对于 对照 算法采用 N S G A : 实数编码方式 , 种群规模为 1 0 , 联赛选 择 , 联赛规模为 2 , 均匀交叉 , 交叉概率为 .0 8 , 变 异算 子为非均匀变异 , 变异概率为 0 . 1 , 进化代 数 为 2 50 代 , 目标 函数空 间共享 . 计算所得到 的 P a r e t o 曲线见图 3 . 从 图 3 可 以看 出 , 采用 m S G A 得 到的 P ar et 。 曲线分 布更均匀 , 且解 的精确度 也较 高 . 仁防l比尸r L :sF 一 、 、 、 性 ’ \ (a) N SG A 山) IN SG A 0 . 8 产自、 钱 .0 6 呀气`通 0 : 0 只成U 0 4 nlj八曰 ( ō x)f . 0 1 . 5 ( e ) N SG A ’ “ 2 0匡卜 (d ) IN S G A 3 、 、 气娜 ~ 、 , . , 一今 `nlJ 11 é 0 `CUJ `,妇, ù且, l 毅 0 5 10 15 2 0 不 、曰一 l0龙 ( e ) N SG A (幻 IN S G A 3 、 翻 3、 、 、 。 一 6 \ 今 今 令 一 12 L 一2 0 一 1 8 一 1 6 一 1 2 L es 一 2 0 X 苦 X 万 图 3 函 数lF 入 几 的 P a r e t o 曲线 , ( a ) , ( b )为 函数 lF ; ( c ) , ( d )为 函数凡: ( e ) , (乃为函 数凡 F ig . 3 P a r e t o fr o n t o f 凡 , zF , 凡

·682 北京科技大学学报 2002年第6期 3结论 Computation,1999,7(3):205 6 Rudolph G.Evolutionary search under partially ordered 经过对多目标进化算法的改进，INSGA的 sets [R].Technical Report No.CI-67/99,Dortmund:De- 算法复杂性有所降低，由于采用了精英策略，减 partment of Computer Science/LS11,University of Dor- 少了共享参数的指定.在三个难度较大的多目 tmund,1999 7 Zitzler E,Deb K,Thiele L.Comparison of multiobjective 标优化测试函数上进行了试算，通过对照结果 evolutionary algorithms:Empirical results[J].Evolutio- 可以看出NSGA要优于NSGA nary Computation.1999,8(2):173 8 Knowles J,Corne D.The Pareto archived evolution strat- 参考文献 egy:A new baseline algorithm for multiobjective optimi- 1 Srinivas N,Deb K.Multiobjective function optimization zation [A].In:Proceedings ofthe 1999 Congress on Evol- using nondominated sorting genetic algorithms [J].Evol- utionary Computation [C].Piscatway:IEEE Service Cen- utionary Computation,1995,2(3):221 ter,1999.98 2 Fonseca C M,Fleming P J.Genetic algorithms for multi- 9 Zitzler E.Evolutionary algorithms for multiobjective op- objective optimization:Formulation,discussion and gen- timization:Methods and applications [D].Zurich:Swiss eralization [A].In:Forrest S.Proceedings of the Fifth In- Federal Institute of Technology (ETH).Aachen:Shaker ternational Conference on Genetic Algorithms [C].San Verlag,1999 Mateo:Morgan Kauffman,1993.416 10 Coello C A C,Christansen A D.A simple genetic algor- 3 Horn J,Nafploitis N,Goldberg D E.A niched Pareto gen- ithm for the design of reinforced concrete beams [J].En- etic algorithm for multiobjective optimization [A].In: gineering with Computers,1997,13(4):185 MichalewiczZeditor,Proceedings of the First IEEE Con- 11 Mitra K,Deb K,Gupta S K.Multiobjective dynamic opti- ference on Evolutionary Computation [C].Piscataway: mization of an industrial Nylon 6 semibatch reactor using IEEE Service Center,1994.82 genetic algorithms [J].Journal of Applied Polymer Sci- 4 Zitzler E,Thiele L.Multiobjective optimization using evol- ence,1998,691):69 utionary algorithms-A comparative case study [A].Par- 12 Deb K,Agrawal R B.Simulated binary crossover for con- allel Problem Solving from Nature V [C].Berlin,1998 tinuous search space [J].Complex Systems,1995,9:115 292-301. 13 Michalewicz Z.Genetic Algorithms Data Structures 5 Deb K.Multiobjective genetic algorithms:Problem diffic- Evolution Programs [MJ.2nd Edition.Spinger-Verlag. ulties and construction of test Functions [J].Evolutionary 1992 An Improved Evolutionary Algorithm for Multi-objective Optimization WU Zhongyuan2,GUAN Zhihua,LI Guangquan" 1)Institute of Systems Engineering,Tianjin University,Tianjin 300072,China 2)Management school,Tianjin Polytechnic University,Tianjin 300065,China ABSTRACT Multi-objective evolutionary algorithms which use non-dominated sorting and sharing have been mainly criticized for the problems,(1)O(mN)computational complexity (where m is the number of ob- jectives and n is the population size),(2)non-elitism approach,and (3)the need for specifying a sharing par- ameter.This paper suggests a non-dominated sorting based the multi-objective evolutionary algorithm INSGA which alleviates all the above three difficulties.Simulation results on five difficult test problems show that the proposed INSGA is able to find much better spread of solutions in all problems compared to NSGA. KEY WORDS NSGA:INSGA:computational complexity;elitism approach:sharing

. 6 8 2 - 北 京 科 技 大 学 学 报 2 0 0 2 年 第 6期 3 结论 经 过对 多 目标进化算法 的改进 , NI S G A 的 算法复杂性有所降低 , 由于采用 了精英策略 , 减 少 了共 享参数的 指定 . 在三个难度较大 的 多 目 标优化测试 函数上进行 了试算 , 通过对 照结果 可 以看 出 NI S G A 要优 于 N S G .A 参 考 文 献 1 S r i n iv a s N , D e b K . M u it i o bj e e t iV e fu n e t i o n o Pt 1m i z at i o n u s i n g n o n do m i n a t e d s o rt i n g ge ne t i e a lg o r i th m s [J」 . E v o l - ut i o n a yr C o m P u t a t i o n , 1 9 9 5 , 2 ( 3 ) : 2 2 1 2 Fo n s e c a C M , F 1 e m ing P J . G e n e ti e a lg o r i t h n 1 s fo r m u l t i - o bj e c t i v e o tP im i z at i o n : F o mr u lat i o n , d i s e u s s i o n an d g e n - e r a li z at i o n [A ] . I n : F o er s t 5 . P r o e e e di n g s o f ht e F ihft I n - t e m at i o n a l C o n fe er n e e o n G e n e ti e A l g o r i t l l m s [ C ] . S an M aet o : M o r g a l l K au l节m an , 1 9 9 3 . 4 16 3 H o nr J , N a印l o i ti s N , G o ld b e gr D E . A n i c h e d P aer t o g e n - e ti e a lg o ir th n l fo r m u l t i o bj e e t iV e o tP i m i z at i o n A[ ] . I n : M i e h a l e w i c z 2 e diot r, Por e e e di n g s o f ht e Fi r s t I E E E C o n - fe er n e e o n E v o lut i o n a yr C o l n Put at i o n [C ] . Pi s c at aw ay : I E E E S e vr i c e C e n t e r, 19 9 4 . 8 2 4 Z itz l e r E , T h i e l e L . M u lit o bj e c ti v e o Pt im i z iat o n us in g ve o l - ut i o n a yr a lg o r i t h m s一 - A e o m Par at i v e c a s e s ut 勿 [A ] . P -ar a ll e l P or b l e m S o l v i n g fr o m N aut r e V [C」 . B e r l i n , 1 9 9 8 。 2 9 2一 3 0 1 . 5 D e b K . M u 1tiObj e c t i v e g e n e t i e al g o r iht m s : P r ob l e m d iif e - u l ti e s an d c o n s trU e ti o n o f t e s t F u n c ti o n s [J ] . E v o l u t i o n a r ) C o m P u t a t l o n , 1 9 9 9 , 7 ( 3 ) : 2 0 5 6 uR d o lPh G . E v o l u ti o n ayr s e ar e h u nd e r Part i a l ly o dr e er d s e t s 汇R ] . eT e h n l e a l eR P o rt N o . C l 一 6 7 9/ 9 , D o r tm un d : D e - P art m e n t o f C o m P u t e r S e i e n e e / L S l l , U n i v e r s iyt o f D or - 加 un d , 1 9 9 9 7 Z i tZ l e r E , D e b K , hT i e l e L . C o n 1 P ar i s o n o f m u It i o bj e c t i v e e v o l ut i o n a r y al g or i t hm s : E m P ir i e a l er s u l t s [J l . vE o lut i o - n a yr C o m Put at i o n . 1 9 9 9 , 8 ( 2 ) : 17 3 8 K n o w le s J , C o net D . T I 、 e P ar e t o ar e h i v e d e v o l u t ion 盘-at e gy : A n e w b a s e l ine a l g o r l t」1 1l l fo r m u l t i o bj e c t iV e OP t im i - z at i o n [ A 】 . I n : Por e e e d i n g s o f ht e 1 9 9 9 C o n g er s s o n E v o l - u ti o n a卿 C o l n P u t at i o n [ C ] . P i s c a wt a y : I E E E S e vr i e e C e n - et r, 19 9 9 . 9 8 9 Z i tz l e r E , E v o l u t ion a ry a lg o r l t 】l m s fo r m u l t i o bj e e ti v e o P · t加i z at i o n : M e t h o d s an d ap Pl i c at i o n s [ D ] . Z u ir e h : Sw i s s F e d e r a l I n s ti tu e o f eT c hn o l o gy ( E T H ) . A ac h e n : S h a k e r Ve r lag , 1 9 9 9 1 0 C o e ll o C A C , C hr i s t an s e n A D . A s i m Pl e g e n e ti e a l go r - i tl l n l for th e d e s i gn o f er i n fo r e e d e o n e r e t e b e a m s [J] . E n - g i n e e r i n g w i th C o m P u t e r s , 1 9 9 7 , 1 3 ( 4 ) : 1 8 5 1 1 M i tar K , D e b K , G u P t a 5 K . M u l ti o bj e e ti v e d y n am i e o P ti - m i z a ti o n o f an in d u s t r i a l N y l o n 6 s e m ibat e h r e a e t o r u s i n g g e n e t i e a l g o r i t l l m s [J ] . J o unr a l o f A p l i e d p o ly m e r S e i - e nc e , 19 98 , 6 9 ( 1) : 6 9 12 D e b K , A g r a w a l R B . S i m u l at e d b i n a ry e or s s o v e r of r e o n - t i n u o u s s e are h s P a e e [J ] . C o m Pl e x S y s t e m s , 1 9 9 5 , 9 : 1 1 5 13 M i e h a l e w i e z 2 . G e n e t i c A lg o r i t h n l s + D at a S t ur e ut r e s = vE o lut i o n Por gr am s M[ ] . Z n d E di ti o n . S Pi n g e r 一 Ve lr ag , 1 9 9 2 A n I m P r o v e d E v o l讯i o n a yr A lg o r iht m fo r M u lt i 一 o bj e c ti v e O P t im i z at i o n 环万 hZ o 儿 g y u a n , , 2), G UA N hZ ih u a l) , LI G u a n g呀u a n l) l ) nI st i t u t e o f sy s t e m s E l l g lne e r ign , T i anj in U n iv e rs ity , T i anj in 3 0 0 0 72 , C l l i 们 a 2 ) M an ag em e nt s e h o o l , iT anj in P o 」yt e c hn i c U n i v e rs ity, Ti anj in 30 00 6 5 , Ch丽 A B S T R A C T M u lt i 一 o bj e e t ive e v o lut i o n a r y a l g o ir t h m s w h i e h u s e n o n 一 d o m in at e d s o rt i n g an d s h iar n g h a v e b e e n m a i n l y e ir t i e i z e d of r ht e p r o b l e m s , ( l ) O ( 子刀 脚 , ) e o呷ut at i o n a l e o m p l e x iyt ( w h e r e m 1 5 ht e num b e r o f o b - j e e t i v e s an d n 1 5 ht e Pop u l at i o n s i z e ) , ( 2 ) n o n 一 e lit i s m ap P r o a e h , a n d ( 3 ) ht e n e e d fo r sP e e i fy in g a s h ar ign P ar - am e t e .r Th i s p ap e r s u g g e st s a n o n 一 d o m i n at e d s o rt in g b a s e d ht e mu lt i 一 obj e e it v e e v o lut i o n娜 a l g o r it hi n NI SG A w hi e h a llve i at e s al l ht e ab vo e htr e e id m cu lt i e s . S i l l l u l at ion r e s u lt s o n ivf e d iif c ul t t e s t rP ob l e m s s h o w ht at ht e Pr o Po s e d m S G A 1 5 ab l e t o if n d m u e h b e et r s P r e a d o f s o lut i o n s in a ll rP o b l e m s e o m Par e d t o N S G A . K E Y W O R D S N S G A ; NI S G A ; e o m P ut at i o n a l e o m Pl e x i yt ; e lit i s m ap Por a e h ; s h ar ign