多阶段自适应差分进化算法及应用分析

1、.东 华 人学 管 J里学 博 卜学 位 论 文基 于 改 进 差 分 的 聚 类 算 法 ， 用 于 提 高 数 据 聚类 的 准 确 性 和 质 量 。最 后 ，对 全 文 研 究 内容 进 行 了 总 结 ， J一旨出研 究 工 作 中 存 在 的 不 足 ， 明 确 了下 一 步 的 研 究 方 向 。关 键 词 : 差分进化算法; 阶段交叉; 两段式; 自适应 ; 流水车间; 二次规划;聚 类.;A b str a e tA b s tr a c tD iffe ren tial ev o lu tion (D E ) alg o rith mh as d em o n strate

2、d a reliab le，aecu rate，ro b u st a n d f ast e v o lu tio n a ry a lg o rith m a n d su e e e s sf u l a P P lie d in m a n y re a l一w o rlda re a s . H o w e v e r，D E h a s sh o w n s o m e w e a k n e s s e s ，e sP e e ia lly D E in s o lv illg c o m P le x functio n s w ith h igh d im en sion s

3、 h as sh o w n so m e w eak n esses， su ch as lo w e o n v e r g e n e e sP e e d ， P r e m a tu r e e o n v e r g e n e e a n d lo w P re e is io n ， W ith a n e y e toim P ro v e th e P e rf or m a n c e o f D E ， it 15 n e e es sary to d e P e n d u P o n a P P ro P ria te ly e h o o sin g e o n

4、tro l P a ra m e te rs . In v ie w o f th is P ro b le m d e P e n d e n e y ， a n o v e l s e lf -a d a p tin g d if fe re n tia l e v o lu tio n a lg o rith m w it h P ie e e w is e o P e ra to rs 15 P ro P o s e d .O P e ra to rs a re re sP e e tiv e ly s e lf -a d a P te d b a s e d o n C a u e

5、h y o r xlo n n a l d is tr ib u tio nra n d o m n u m b e r ，a n d d y n a m ie a lly g e n e ra te th e se e o n tro l P a ra m e te rs in th is a lg o rith m .T h e e v o lu tio n P ro e e ss 15 d iv id e d in to tw o s ta g e s ，d if fe r e n t e o n f ig u r a tio n P a ra m e te rsa re u se d

6、to g e n e ra te a m P lif ic a tio n f ac to rs a n d e ro s so v e r P ro b a b ility b y re sP e e tiv eo P erato rs (o r to eh o o se su itab le ero sso v er P ro b ab ility ) at eaeh stag e . A t th e sam e tim e，to e n h a n c e th e e o n v e r g e n t sP e e d ，a n e w m u ta tio n s tra te

7、g y 15 izltro d u e e d to g u id eseareh in g d irectio n . B en ellln ark P rob lem s are u sed to v erify th is alg o rith m an d th ere su lt o f sim u la tio n in d ie a te d th a t h a s im P ro v e d sig n if ic a n tly b o th in e o n v e rg e n e esP e e d a n d P re e isio n o f o P tim iz

8、 a tio n .In th is s tu d y ，d if fe re n tia l e v o lu tio n a ry e o m P u tin g a n d its a P P lie a tio n a re f o c u s e do n . S o m e n o v e l se lf -a d a P tiv e a lg o rith m s a re P ro P o s e d b a s e d o n m u lti一sta g e a n d tra d itio n a l d if fe re n tia l e v o lu tio n .

9、T o re P a ir d e f ic ie n e ie s ，su e h a s P ro b le m d e P e n d e n e y ， low P recisio n in so lv in g eo m P lex fun etio n s w ith h igh d im en sio n s an d easily traP P ed in t o a lo e a l o P tim u m ， se g llle n ta l w a v e a n d P ie e e w ise e ro sso v e r a lg o rith m s a reP

10、ro P o s e d . In o rd e r to im P ro v e th e P ra e tie a lity o f th e a lg o r ith m ，a so lu tio n to d e a l w it h th e e o n stra in e d o P tim iz a tio n P ro b le m s 15 a lso P ro v id e d .T h e P ro P o s e d a lg o r ith m sf in ally a p p ly in th e f ie ld s su e h a s tra n sp o r

11、ta tio n p ro b le m s， q u a d ra tic p ro g ra m s ，b lo ek in g f lo w sh o P sc h e d u lin g a n d e lu ste rin g P ro b le m s . M o re d e ta ils a re g iv e n a s follow : (1) In so lv in g a sP eeifie P ro b lem erucially d eP en d s o n aP P ro P riately eh o o sin g eo ntr o l P aram eter

12、s，a n o v el tw o 一stag e d iffe ren tial ev o lu tio n strateg y 15 P ro P o sed .(2 )In solv in g eo m P lex fun etio n s w ith h igh d im en sio n s h as sh o w n low Precision ，a n ew川为; 华 人 学 管 理 学 博 卜学 位 论 文s e lf -a d a P tin g d if fe re n tia l e v o lu tio n a lg o rith zn w ith se g 一n e

13、n ta l e ro sso v e r 15 P ro P o se d . 5 0 e ro s so v e r P ro b a b llity 15 se llsitiv e to th e o P tim iz a tio ll P ro b le m ， s e lf -a d a P tiv ee o n tro l f ae to rs a re o b ta in e d to iln P ro v e th e a lg o rith ln in h ig h d iln e n s io lla l a e e u ra e y o f th e o P tim iz

14、 atio n P ro b lem .(3 ) A t th e sam e tizn e，to ellh an ee th e lo eal eo n v erg en t sP e e d ， th e o P tim a l f o n e tio n f itn e ss v a lu e o f ra l记 o m ly se le e te d v e e to rs P ro v id e sin f o r m a tio n o f P ro g r e s s d ire e tio n a s th e b a se r nu ta tio n stra te g y

15、in th e se n e walg o rith m s.(4 ) T h ere are th e m ajo rity eo n strain ed P ro b lem s in sP eeifie aP P lieatio n sf ie ld s，a c o n stra in t h a n d lin g m e e h a n ism 15 P ro v id e d to b e e o m P a tib le w ith th e n e walgo rith m s.(5 ) T h is P aP er P resen ts a n o v el tw o 一st

16、ag es d iserete d iffe rential ev o lu tio n aP P lied to so lv e th e b lo ek in g flo w sh oP seh ed u lin g P ro b lem s. (6 ) T h e n ew D E ean b e u se d to f in d th e o P tim iz a tio n e f fe e tiv e ly ，50 a n o v e l e lu ste rin g a lg o r ith m b y u s in g o fm u lti一s ta g e d if fe r

17、e n tia l e v o lu tio n a lg o rith m 15 e m P lo y e d to im P ro v e th e a e e u ra e y a n d q u a lity o f e lu s te r in g .F in a lly ，a su m m a ry o f th e th e sis 15 m a d e ，a n d th e d e f ie ie n e y o f th e stu d y a n d th ef ur th e r d e v e lo P m e n t a re n a r ra te d re sP

18、 e e tiv e ly .K e y w o r d s : D if fe re n tia l E v o lu tio n A lg o r ith m ; S e g llen ta l c ro sso v e r; T w o 一sta g e ;S elf-ad aP tiv e ; F lo w S h o P ; Q u adratie P ro gram s;C lu sterin g1V目录摘 要 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

19、- - - - - - - - - - - 一工A b s tr a e t 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一工工工目 录 - - -一-一-一-一-一-一-一-一-一-一-一-一-一-一一- -一一- -一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一-一一- 一- -一-一-一一一-一-一-一-一-一-一-一-一-一-一-一一一 V图 目录 - - - - - - - - - - - - - - - - -

20、- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一- - - - - - - - - - - 一 工X表 目录 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一X 工第 l 章 绪论 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

21、 - - - - - - - - - - - - - -一l1. 1 研 究 背 景 及 意 义 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -一 11.2 标 准 差 分 进 化 算 法 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -一 21.2 . 1 差 分 算 法 介 绍 - - - - - - - - - - - - - - - - - - - - - - - -

22、 - - - - - - - - - - - - - - - - - 一 21.2 .2 算 法 处 理 基 本 步 骤 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 31.2 .3 控 制 参 数 对 算 法 性 能 影 响 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 61. 3 差 分 进 化 算 法 研 究 进 展 - - - - - - - - - - - - - - - - - -

23、 - - - - - - - - - - - - - - - - - - - - -一 61.3 . 1 D E 算 法 的 数 学 模 型 及 理 论 研 究 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 71.3 .2 D E 算 法 的 改进 研 究 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 71.3 .3 离 散 差 分 进 化 算 法 - - - - - - - - -

24、- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 151. 3 .4 差 分 进 化 算 法 应 用 领 域 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -一 161.4 主 要 研 究 内容 及 创 新 点 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一181. 5 论 文 的 组 织 结 构 - - - - - - - -

25、- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一19第 2 章 阶 段 波 动 差 分 进 化 算 法 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一212 . 1 差 分 进 化 算 法 研 究 背 景 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一212 .2 经 典 白适 应 差 分 进 化 算 法 - - -

26、 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一222 . 3 阶 段 波 动 D E 算 法 (SWD E) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一2 32 .3 . 1 变 异 策 略 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -一 232 . 3 .2 参 数 自适

27、应 控 制 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 242 .3 . 3SW D E 算 法 及 时 间 复 杂 度 讨 论 - - - - - - - - - - - - - - - - - - - - - - - - - - - -一 242 . 3 .4 算 法 收 敛 性 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 262 .4 实 验 与 分 析

28、- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一262 .4 . 1 B en c h m a r k 和 D ix o n 一S z e g 6 函 数 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 2 72 .4 .2 变 异 策 略 比较 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

29、 - - - - - 一 292 .4 .3 种 群 敏 感 性 试 验 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 302 .4 .4 种 群 多 样 性 及 速 度 试 验 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 3 12 .4 .5 30 维 B enc hm a rk 问题 实 验 及 分 析 - - - - - - - - - - - - - - - - -

30、- - - - - - - - - - - 一 312 .4 .6 低 维 D ixon 一S z eg 6 函 数 实 验 及 分 析 - - - - - - - - - - - - - - - - - - - - - - - - -一 342 .4 . 7 S W D E 参 数 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 352 .5 本 章 小 结 - - - - - - - - - - - - - - - - - - - - - - - - - - - -

31、- - - - - - - - - - - - - - - - - 一37第 3 章 两 段 交 叉 差 分 进 化 算 法 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一393 . 1 引 言 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -一一- - - - - - - - - -一 393 .2 两 段 交 义 D E 算 法 (T CD E)- - - - - - - - - -

32、 - - - - - - - - - - - - - - - - - - - - - - - - - - - -一 393 .2 . 1 变 异 策 略 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 403 .2 . 2 参 数 自适 应 控 制 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 403 .2 . 3 T C DE 算 法 及 时 间 复 杂 度 讨 论 - -

33、 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 403 . 3 实 验 与 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -一一- - - - - - - - - - -一 413 . 3 . 1 B e n c h m a r k a n d D i x o n 一 S z e g 6 - 一- 一- - - - - - - - - 一- - - 一- - - - - - 一一- - - - - - - - 一- - - 一 4 23 .

34、3 .2 种 群 多 样 性 及 速 度 试 验 - - - - 一4件咨9 43 .3 . 3 30 维 B en ehm ar k 问题 实 验 及 分 析东 华 人 学 管 理 学 博 卜学 位 论 文3 . 3 . 4 10 0 维 函 数 实 验 及 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 453 .3 . 5 全 局 收 敛 实 验 比 较 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - -

35、- - - - 一 4 73 . 3 . 6 低 维 D IX o n 一S z eg 6 函 数 实 验 及 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 铭3 .3 . 7 T C D E 参 数 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 503 .4 算 法 在 运 输 问 题 中 应 用 - - - - - - - - - - - - - - - - - - - - - - - -

36、 - - - - - - - - - - - - - - -一 513 .4 . 1 平 衡 运 输 问 题 模 型 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 513 .4 . 2 种 群 初 始 方 案 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -一 523 .4 . 3 案 例 仿 真 试 验 - - - - - - - - - - - - - - -

37、- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 5 33 .5 结 论 - - - - - - - - - -一- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 56第 4 章 多 阶 段 差 分 进 化 算 法 求 解 约 束 优 化 问 题 - - - - - - - - - - - - - - - - - - - - - - - - - - - 一574 . 1 引 言 -

38、 - - - 一- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 574 .2 约 束 优 化 问 题 定 义 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -一 574 .3 约 束 处 理 和 目标 函 数 偏 好 策 略 - - - - - - - - - - - - - - - - - - - - - -

39、- - - - - - - - - - - - - - 一584 .4 多 阶 段 差 分 约 束 优 化 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一594 .5 实 验 与 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一614 .5 . 1 测 试 函 数 与 性 能 衡 量 -一- - - - - - - - - - -

40、- - - - - - - - - - - - - - - - - - - - - - - - 一 614 .5 . 2 不 同 的 约 束 处 理 机 制 比 较 分 析 - - - 一- - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 624 .5 . 3 人 种 群 对 多 阶 段 算 法 的 性 能 影 响 及 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - -一 654 .5 .4 不 同 约 束 优 化 进 化 算 法 性 能 比 较 - - - - -

41、- - - - - - - - - - - - - - - - - - - - - - - - - 一 674 .6 在 二 次 规 划 问 题 中 的 应 用 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一684 . 7本 章 小 结 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一70第 5 章 多 阶 段 差 分 算 法

42、在 Bl oc k in g 流 水 车 间 调 度 问题 中 的 应 用 - - - - - - - - - - - - - - - - 一715 . 1 引 言 - - - - 一- - - - - - - - - - - - - - 一- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 715 .2 B lo c k in g 水 车 间 调度 问 题 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

43、 - - 一725 .2 . 1 B lo c k in g 水 车 间 问 题 定 义 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 725 .2 . 2 可 阻 塞 流 水 车 间 调 度 图 形 描 述 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 745 .3 离 散 阶 段 自适 应 差 分 进 化 - - - - - - - - - - - - - - - - - - - - - - - - - - -

44、- - - - - - - - - - - - - 一 745 .3 . 1 编 码 选 择 - - - - - - - - - 一- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 745 . 3 . 2 基 于 _卜件 排 序 的 变 异 策 略 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 745 .3 . 3 基 于 _1二件 排 序 的 交 叉 操 作 - - - - - - - -

45、- - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 765 .3 .4 种 群 初 始 策 略 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 765 .3 . 5 插 入 编 码 评 价 策 略 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 775 .3 . 6 离 散 多 阶 段

46、差 分 进 化 算 法 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 775 .4 仿 真 实 验 及 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 785 .4 . 1 实 验 设 置 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

47、- - - - - - 一 785 .4 . 2 实 验 与 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 785 .5 本 章 小 结 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 80第 6 章 多 阶 段 差 分 聚 类 及 D e ep W eb 中 的 应 用 - - - -

48、- - - - - - - - - - - - - - - - - - - - - - - - - - 一816 . 1 引 言 - - - - - - - - -一- - - - - 一- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 816 . 1. 1 文 档 聚 类 的 相 关 背 景 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 816 . 1. 2 文 档 聚 类 方

49、法 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 826 .2 改 进 差 分 聚 类 - - - - - - - - - - -一- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 836 .2 . 1问 题 定 义 - - - - - - - - 一- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

50、- - - - - 一 836 .2 . 2 差 分 染 色 体 编 码 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 846 .2 . 3 适 应 度 函 数 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 846 .2 . 4 算 法 实 现 - - - - - - - - - - - - - - - - - - - - - - -

51、 - - - - - - - - - - - - - - - - - - - - - - - - - 一 866 .3 数 值 试 验 及 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 866 .3 . 1 数 据 集 选 择 及 实 验 设 置 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 86目录6 .3 .2 实 验 及 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一 876 .4 D eep W eb 中 聚 类 应 用 及 分 析 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 一8S6 .4 . 1 问 题 提 出 - - - - - - - - - - -