ISSN 1000-9825, CODEN RUXUEW E-mail: jos@ Journal of Software, , , March 2007, −516 DOI: Tel/Fax: +86-10-62562563 © 2007 by Journal of Software. All rights reserved. 튻훖뿬쯙뗄믹폚햼폅쫷뗄뛠쒿뇪뷸뮯쯣램∗ 쪯 뒨1,2+, 샮쟥폂1,2,3, 쪷훒횲1 1(훐맺뿆톧풺 볆쯣벼쫵퇐뺿쯹 훇쓜탅쾢뒦샭훘뗣쪵퇩쫒,놱뺩 100080) 2(훐맺뿆톧풺 퇐뺿짺풺,놱뺩 100049) 3(놱뺩붻춨듳톧 볆쯣믺폫탅쾢벼쫵톧풺,놱뺩 100044) A Quick Multi-Objective Evolutionary Algorithm Based on Dominating Tree SHI Chuan1,2+, LI Qing-Yong1,2,3, SHI Zhong-Zhi1 1(Key Laboratory of Intelligent Information Process, Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100080, China) 2(Graduate School, The Chinese Academy of Sciences, Beijing 100049, China) 3(School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China) + Corresponding author: Phn: +86-10-62565533 ext 5689, E-mail: shic@ Shi C, Li QY, Shi ZZ. A quick multi-objective evolutionary algorithm based on dominating tree. Journal of Software, 2007,18(3):505−516. Abstract: To solve the time-consuming problem of the fitness assignment in the multi-objective evolutionary algorithm, this paper proposes a novel fitness assignment—dominating tree. The dominating tree preserves the necessary relationships among individuals, contains the density information implicitly, and reduces the comparisons among individuals distinctly. In addition, a smart eliminating strategy based on the dominating tree maintains the diversity of the population without extra expenses. A new multi-objective evolutionary algorithm based on dominating tree is proposed on these innovations. By examining three performance metrics on six test problems, the new algorithm is found to be competitive with SPEA2 and NSGA-II in terms of converging to the true Pareto front and maintaining the diversity of the population, moreover, it is much faster than other two algorithms. Key words: multi-objective evolutionary algorithm; evolutionary algorithm; dominating tree; eliminating strategy 햪 튪: 캪쇋뷢뻶뛠쒿뇪뷸뮯쯣램훐쫊펦횵횸엉(fitness assignment)뗄뫄쪱컊쳢,쳡돶쇋튻훖탂펱뗄쫊펦횵횸엉랽램햼폅쫷.햼폅쫷놣듦쇋룶쳥횮볤뗄뇘튪탅쾢,낵몬쇋룶쳥뗄쏜뛈탅쾢,뛸쟒쿔훸복짙쇋룶쳥횮볤뗄뇈뷏.듋췢,믹폚햼폅쫷뗄쳔청닟싔쎻폐뮨럑뛮췢뗄듺볛뻍놣듦쇋훖좺뛠퇹탔.퓚듋믹뒡짏,쳡돶쇋튻훖탂뗄믹폚햼폅쫷뗄뛠쒿뇪뷸뮯쯣램.춨맽6룶닢쫔컊쳢뫍3룶랽쏦뗄닢쫔뇪ힼ,탂쯣램퓚뷓뷼헦쪵뗄ퟮ폅잰퇘뫍놣돖훖좺뗄뛠퇹탔랽쏦,폫SPEA2뫍NSGA-II탔쓜쿠떱,떫쯙뛈튪뇈쯼쏇뿬뗃뛠. 맘볼듊: 뛠쒿뇪뷸뮯쯣램;뷸뮯쯣램;햼폅쫷;쳔청닟싔 ∗ Supported by the National Natural Science Foundation of China under Grant (맺볒ퟔ좻뿆톧믹뷰); the National Grand Fundamental Research 973 Program of China under Grant (맺볒훘뗣믹뒡퇐뺿랢햹맦뮮(973)); the Natural Science Foundation of Beijing of China under Grant (놱뺩쫐ퟔ좻뿆톧믹뷰) Received 2006-03-10; Accepted 2006-05-11
506 Journal of Software 죭볾톧놨 , , March 2007 훐춼램럖샠뫅: TP18†?컄쿗뇪쪶싫: A 뛠쒿뇪폅뮯컊쳢(multi-objective optimal problem,볲돆MOP)쫇횸쓇킩춬쪱폅뮯뛠룶쒿뇪뗄컊쳢.튻냣살쮵,헢킩떥룶쒿뇪쫇쿠뮥돥춻뗄,뛸쟒ퟜ쳥쒿뇪쎻폐떥룶ퟮ폅뷢.쟳뷢뛠쒿뇪폅뮯컊쳢뎣뎣쫇삧쓑뗄,쯼늻쿱떥쒿뇪폅뮯컊쳢(single objective optimal problem,볲돆SOP)쓇퇹횻폐튻룶ퟮ폅뷢,헢쪹뗃쓜릻튻듎뗃떽튻ퟩ폐쾣췻뗄뷢뗄쯣램뇈쓇킩튻듎횻뗃떽튻룶뷢뗄쯣램튪뫃.헽쫇평폚헢룶풭틲,퓚맽좥뗄쪮벸쓪샯,풽살풽뛠뗄퇐뺿헟붫뷸뮯쯣램펦폃떽MOP컊쳢훐. 퇐뺿헟뛔뛠쒿뇪뷸뮯쯣램뷸탐쇋짮죫뛸맣랺뗄퇐뺿,쳡돶쇋뫜뛠훖뛠쒿뇪뷸뮯쯣램(multi-objective evolutionary algorithm,볲돆MOEA)[1−6].헢킩쯣램쪹폃Pareto햼폅횸떼쯑쯷,늢쟒략믘튻ퟩ럇햼폅뷢ퟷ캪뷡맻.폫떥쒿뇪폅뮯컊쳢늻춬,뛠쒿뇪폅뮯뗄뷢튪듯떽솽룶쒿뇪:(1) 뾿뷼Paretoퟮ폅잰퇘;(2) 놣돖훖좺뛠퇹탔[1].캪쇋듯떽헢솽룶쒿뇪,쪹폃쇋뫜뛠닟싔뫍랽램[7].헢킩쯣램뛔튻킩닢쫔컊쳢쓜릻좡뗃뫜뫃뗄뷡맻,떫쫇,쿖퓚뗄MOEA훐튲듦퓚튻킩늻ퟣ,뫜뛠MOEA뇈뷏뢴퓓.캪쇋좡뗃룼뫃뗄뷢,쯣램퓋폃쇋뫜뛠웴랢쪽랽램뫍닟싔,늢쟒뫜뛠닎쫽탨튪룹뻝뺭퇩뫍룸뚨컊쳢뗄쿈퇩횪쪶뷸탐뗷헻.쇭튻랽쏦,뫜뛠MOEA폐뷏룟뗄볆쯣뢴퓓뛈.틲듋,짨볆튻훖볲떥룟킧뗄MOEA쫇뇘튪뗄. 퓚놾컄훐,컒쏇쫗쿈럖컶쇋Pareto햼폅뗄탔훊뫍쫊펦횵횸엉맽돌뫄쪱뗄풭틲,좻뫳쳡돶쇋튻훖탂펱뗄쫊펦횵횸엉랽램햼폅쫷.햼폅쫷쫇놣듦쇋룶쳥햼폅탅쾢뗄뛾닦쫷,쯼돤럖샻폃쇋Pareto햼폅뗄탔훊,쿔훸복짙룶쳥횮볤뗄뇈뷏,뛸쟒틾몬쇋룶쳥횮볤뗄쏜뛈탅쾢.듋췢,믹폚햼폅쫷뗄쳔청닟싔늻탨튪뛮췢뗄뾪쿺뻍쓜뫜ퟔ좻뗘놣돖훖좺뛠퇹탔.평듋,컒쏇쳡돶쇋믹폚햼폅쫷뗄뛠쒿뇪뷸뮯쯣램(multi-objective evolutionary algorithm based on dominating tree,볲돆DTEA).DTEA붫쟷뷼잰퇘뗄닟싔뫍놣돖훖좺뛠퇹탔닟싔헻뫏떽햼폅쫷훐,헢퇹쪹뗃쯣램룼볓볲떥.ퟮ뫳,쒣쓢쪵퇩뇭쏷:DTEA쓜릻뗃떽폫SPEA2뫍NSGA-II탔쓜쿠떱뗄뷢,떫쫇,DTEA뇈웤쯻솽룶쯣램튪뿬뗃뛠. 1 뛠쒿뇪뷸뮯쯣램뗄믘맋 컒쏇붫볲뛌뗘믘맋쒿잰MOEA뗄퇐뺿.쫗쿈뷩짜컄훐쪹폃뗄튻킩룅쓮;좻뫳럖컶쒿잰MOEA훐뗄벼쫵뫍랽램.쇭췢튲횸돶쇋쒿잰MOEA퇐뺿훐듦퓚뗄튻킩컊쳢. 믹놾뚨틥 Veldhuizen뫍Lamont틑뺭퇏룱뗘뚨틥쇋뛠쒿뇪폅뮯컊쳢뫍쿠맘뗄룅쓮[7].컒쏇뷩짜놾컄훐쪹폃뗄솽룶훷튪룅쓮.늻쪧튻냣탔,놾컄횻쳖싛ퟮ킡폅뮯컊쳢,틲캪ퟮ듳폅뮯컊쳢뫜죝틗뮯돉ퟮ킡폅뮯컊쳢. 뚨틥1[7]. 튻냣뗄MOP:튻룶MOP쫇횸ퟮ킡뮯쒿뇪몯쫽F(x)=(f1(x),…,fm(x))늢싺ퟣ풼쫸쳵볾gi(x)≤0, i=1,…,k,x∈W(W쫇뻶닟뇤솿뿕볤)뗄컊쳢.튻룶MOP뗄뷢쫇ퟮ킡뮯m캬뗄쒿뇪쿲솿F(x)뗄룷룶럖솿,헢샯, x=(x1,…,xn)쫇튻룶n캬뻶닟쿲솿. 뚨틥2[7]. Pareto햼폅:죧맻쿲솿U=(u1,…,um)Pareto햼폅V=(v1,…,vm),퓲볇캪UpV.벴UpV,떱쟒뷶떱 ∀i∈{1,…,m} ui≤vi∧∃i∈{1,…,m} ui<vi (1) 떱잰,MOEA뗄퇐뺿훷튪쫇믹폚Pareto햼폅뗄.튻룶뻶닟쿲솿xu∈W쫇Paretoퟮ폅뗄,떱쟒뷶떱늻듦퓚xv∈W 싺ퟣF(xv)pF(xu).Paretoퟮ폅뻶닟쿲솿뗄벯뫏놻돆캪컊쳢뗄Paretoퟮ폅벯.뛔펦뗄쒿뇪쿲솿벯뫏놻돆캪럇햼폅 벯믲헟Pareto잰퇘.캪쇋볲뮯,퓚쿂쏦뗄탰쫶훐,컒쏇튲쪹폃햼폅듺쳦Pareto햼폅.뫜쏷쿔,Pareto햼폅폐죧쿂쳘탔: 탔훊1. Pareto햼폅폐랴ퟔ랴뫍뒫뗝탔. 쿞폚욪럹풭틲틔벰횤쏷뇈뷏볲떥,횤쏷싔. MOEA훐쪹폃뗄벼쫵 튻룶뫃뗄MOEA뇘탫싺ퟣ솽룶랽쏦:(1) 럇햼폅뷢벯뷓뷼Paretoퟮ폅잰퇘;(2) 뷢벯폐솼뫃뗄럖즢 탔[1,7].헢솽룶쒿뇪튲쫇듳늿럖MOEA뗄탔쓜움볛뇪ힼ.캪쇋싺ퟣ헢솽룶뇪ힼ튲짨볆쇋뫜뛠훖랽램.
쪯뒨 뗈:튻훖뿬쯙뗄믹폚햼폅쫷뗄뛠쒿뇪뷸뮯쯣램 507 캪쇋싺ퟣ뗚튻랽쏦,믹폚Pareto햼폅뗄쫊펦횵횸엉랽램폃살횸떼훖좺쿲헦쪵뗄ퟮ폅잰퇘쯑쯷.믹놾쮼쿫쫇룹뻝Pareto햼폅뛔뷢뷸탐업탲.뫜뛠쫊펦횵횸엉랽램틑뺭놻쳡돶살쇋.Goldberg쫗쿈쳡돶튻훖뎣폃뗄랽램늢펦폃떽NSGA-II뗈쯣램훐[1].룃랽램붫뷢벯뮮럖돉늻춬뗄닣늢룸폨늻춬뗄업쏻횵(rank).Fonseca뫍Fleming쳡돶튻훖랽램,벴튻룶뷢뗄업쏻평훖좺훐뇈룃뷢햼폅뗄뷢뗄쫽쒿뻶뚨[8].Zitzler뫍Thiele퓚SPEA2쳡돶쇋쇭튻훖랽램:퓚뷸뮯훖좺뫍뺫펢훖좺훐뗄쎿튻룶쳥뚼놻횸엉튻룶잿뛈횵,룃횵냼몬쇋햼폅뫍쏜뛈탅쾢[2]. 뛔폚뗚뛾랽쏦,튻킩돉릦뗄MOEA샻폃쏜뛈맀볆랽램놣듦훖좺뗄뛠퇹탔.킡짺뺵(niching)뫍쫊펦횵릲쿭퓚뫜뛠MOEA훐놻맣랺뗘쪹폃,샽죧MOGA[8].헢훖랽램짨훃튻룶릲쿭닎쫽dshare.볆쯣쒿뇪뿕볤훐룶쳥뗄Niching뻠샫늢쟒폫dshare뇈뷏.튻냣뛸퇔,뛔dshare횸뚨뫏쫊뗄횵쫇뫜삧쓑뗄,틲캪헢뎣뎣탨튪룸뚨컊쳢뗄쿈퇩횪쪶.퓚SPEA2훐,폫뗚k룶ퟮ뷼룶쳥횮볤뗄뻠샫ퟷ캪룶쳥뗄쏜뛈탅쾢[2].NSGA-II쪹폃쇋튻훖탂펱뗄쏜뛈맀볆랽램.룃랽램늻탨튪짨훃닎쫽,늢쟒폫NSGA쿠뇈폐룼뗍뗄쪱볤뢴퓓뛈[1].쇭튻훖뎣폃뗄랽램쫇샻폃뎬췸룱뗄랽램붫쒿뇪뿕볤뮮럖돉룱ퟓ.튻룶룱ퟓ훐뗄룶쳥뇈뷏짙뻍쮵쏷뿕볤뇈뷏쾡쫨,뿉틔뫍웤쯻룶쳥릲쿭튻룶룱ퟓ.PAES[3]뫍DMOEA[5]쪹폃쇋룃랽램. Atashkari뮹쳡돶쇋e-쳔청뗄뛠퇹탔랽램[4,9]. 듋췢,웤쯻튻킩벼쫵튲펦폃떽MOEA훐살.퇐뺿뇭쏷:뺫펢랽램(elite)뿉틔쿔훸쳡룟MOEA뗄탔쓜,늢쟒헢폐훺폚럀횹뚪쪧틑뺭헒떽뗄폅탣뷢[10].룹뻝훖좺뗄퓚쿟쳘탔뫍쏜뛈럖늼탅쾢뚯첬뗷헻훖좺듳킡뗄랽램폫만뚨훖좺맦쒣듳킡뗄랽램쿠뇈,퓚뇜쏢뻖늿ퟮ폅뫍복짙늻뇘튪뗄뢴퓓탔랽쏦룼볓폐킧[5],뛸쟒,쪹폃늻쫜쿞뗄뺫펢훖좺듳킡뿉틔뇜쏢Pareto잰퇘뗄쮥췋뫍헰떴[11]. 맺쓚톧헟튲퓚헢랽쏦뷸탐쇋듳솿퇐뺿.헫뛔뫜뛠쯣램컞램폐킧뒦샭쒿뇪몯쫽뫜뛠뗄폅뮯컊쳢,듞톷톧쳡돶샻폃늻춬ힼ퓲횮볤틽죫욫뫃살뷢뻶룃컊쳢,늢짨볆쇋뛠쒿뇪뗷뫍틅뒫쯣램[12].샗뗂쏷쳡돶쇋믹폚룶쳥쏜뛈뻠샫뗄췢늿훖좺캬뮤랽램,늢퓚붫쯹폐룶쳥룹뻝Pareto횧엤맘쾵럖돉4룶닣듎뗄믹뒡짏,룸돶쇋튻훖평룶쳥쏜뛈뻠샫뚨틥뗄쫊펦횵몯쫽[13].퓸죽폑붫헽붻짨볆뗄랽램펦폃떽쇋뛠쒿뇪폅뮯훐[14]. 튻킩돉릦뗄MOEA틑뺭펦폃떽튻킩닢쫔컊쳢늢좡뗃쇋뫃뗄뷡맻.떫쫇,헢킩쯣램뮹듦퓚튻킩늻ퟣ:튻랽쏦, MOEA쯣램뫜뢴퓓.캪쇋뗃떽뫃뗄뷢,뫜뛠MOEA랽램캪쇋쟷뷼잰퇘뫍놣돖뛠퇹탔쪹폃쇋늻춬뗄벼쫵,쯤좻헢킩쯣램뎣뎣룹뻝헢솽랽쏦움볛룶쳥뗄쫊펦횵[1,2,5].퓚헢솽랽쏦훐쪹폃뗄벼쫵뎣뎣쫇뇈뷏뢴퓓뗄,늢쟒폐뫜뛠닎쫽탨튪룹뻝룸뚨뗄컊쳢뫍뺭퇩뷸탐뗷헻.샽죧,DMOEA훐폐6룶닟싔뫍4룶닎쫽탨튪뗷헻[5].쇭튻랽쏦, MOEA쯣램뫜뫄쪱.쿖퓚,듳늿럖MOEA폐뷏룟뗄볆쯣뢴퓓뛈,웤훐늿럖풭틲퓚폚뛠쒿뇪뗄쫊펦횵횸엉뇈떥쒿뇪튪뢴퓓;쇭튻룶훘튪풭틲퓚폚쯣램퇐뺿헟뫜짙뾼싇볆쯣뢴퓓뛈[15].놾컄뗄퇐뺿쒿뇪뻍쫇짨볆튻룶볲떥떫쫇룟킧뗄MOEA쯣램. 2 햼폅쫷벰웤탔훊 쫊펦횵횸엉쫇MOEA뗄훷튪뫄쪱늿럖[15].뫜뛠폐킧뗄쫊펦횵횸엉틑뺭놻쳡돶살쇋.떫쫇,퓚쫊펦횵횸엉훐폐뫜뛠늻뇘튪뗄뇈뷏.복짙늻뇘튪뗄뇈뷏뿉쓜쫇붵뗍쫊펦횵횸엉뗄볆쯣뢴퓓뛈뗄튻룶뷝뺶. 쿖폐쫊펦횵횸엉뗄늻ퟣ횮뒦?MOEA튻룶훷튪뗄뫄쪱늿럖퓚폚쫊펦횵횸엉[15].쫊펦횵횸엉폐뫜룟뗄볆쯣뢴퓓탔,웤훐늿럖풭틲퓚폚뛠쒿뇪뗄쫊펦횵횸엉쫇튻룶뫜쓑뗄컊쳢;쇭튻룶룼훘튪뗄풭틲퓚폚,퇐뺿헟퓚쫊펦횵횸엉맽돌훐뫜짙샻폃Pareto햼폅뗄탔훊뫍MOP뗄쳘탔살복짙룶쳥횮볤늻뇘튪뗄뇈뷏.늻뇘튪뗄뇈뷏훷튪평솽랽쏦ퟩ돉:튻킩맘쾵뿉평쿖듦뗄맘쾵췆떼돶살;쇭췢,튻킩맘쾵뛔ퟮ훕뻶닟쫇늻뇘튪뗄.퓚놾컄훐,룶쳥횮볤뗄햼폅맘쾵쫇춨맽룶쳥뇈뷏뗃떽뗄.헢킩맘쾵쓜릻뿉쫓뮯,틲듋,뷢횮볤뗄뇈뷏뿉틔폃춼뇭쪾,춼훐뗄튻룶뷡뗣뇭쪾튻룶룶쳥.샽죧,춼1샻폃춼췪좫쿔쪾쇋5룶뷡뗣횮볤뗄맘쾵.컒쏇횱맛뗘랢쿖춼훐폐뫜뛠죟폠맘쾵.쓇쎴,죧뫎쿻돽헢킩맘쾵쓘? 틲캪Pareto햼폅폐랴ퟔ랴뫍뒫뗝탔,뫜뛠맘쾵뿉틔듓쿖폐뗄맘쾵훐췆떼돶살.틔춼1캪샽,N4햼폅N3,N3햼폅N2,틲듋N4햼폅N2,쯹틔,N4뫍N2횮볤뗄뇈뷏쫇쎻폐뇘튪뗄.컒쏇튲힢틢떽쇭튻룶쫂쪵:횻탨튪뗃떽쎿튻듺훖좺훐뗄Paretoퟮ폅벯,틲캪뻶닟헟뎣뎣룹뻝ퟮ폅뷢ퟷ돶뻶닟,쯻쏇늢늻맘힢웤쯻뷢.틲듋,뷢벯훐뗄뫜뛠맘쾵쫇늻탨튪횪뗀뗄,뫜뛠뇈뷏쫇뿉틔뇜쏢뗄.뫜쏷쿔,N1뫍N4릹돉쇋춼1훐5룶뷡뗣뗄Paretoퟮ폅벯.틲캪N4햼폅
508 Journal of Software 죭볾톧놨 , , March 2007 N3,늢쟒N1햼폅N2,틲듋,N2뫍N3뗄뇈뷏쫇늻뇘튪뗄. N4N1 N3N2 N5 Nondominated Parato dominant Illustration of the dominating relationships using graph 춼1 샻폃춼뇭쪾뗄뷡뗣햼폅맘쾵뗄쪾틢춼 햼폅쫷뗄뷡릹 춨맽짏쏦뗄럖컶컒쏇랢쿖,복짙늻뇘튪뗄뇈뷏탨튪싺ퟣ솽룶쳵볾:(1) 뇘탫쿻돽죟폠맘쾵;(2) 캪쇋죝틗헒떽ퟮ폅뷢,뇘탫놣듦뇘튪뗄맘쾵. 뛔뗚1룶쳵볾,컒쏇탨튪뷸튻늽뗘럖컶Pareto햼폅뗄탔훊.SOP훐뷢뗄맘쾵쫇뛾횵뗄:듳폚믲헟킡폚맘쾵(헢샯,컒쏇늻뾼싇뗈폚뗄쟩뿶),MOP훐뷢뗄맘쾵쫇죽횵뗄,뿉틔뚨틥죧쿂: 뚨틥3. Better몯쫽. 1, F(x)pF(x)12 Better(x,x)=2, F(x)pF(x) (2) 12210, NondominatedBetter몯쫽뚨틥쇋MOP훐뷢뗄맘쾵.춼1훐뷡뗣뗄Better맘쾵볻뇭1. Table 1 The Better relationships among nodes in 뇭1 춼1훐뷡뗣뗄Better맘쾵 N1 N2 N3 N4 N5 N1 0 1 0 0 0 N2 2 0 2 2 0 N3 0 1 0 2 0 N4 0 1 1 0 1 N5 0 0 0 2 0 뺭맽럖컶랢쿖,Better몯쫽폐죧쿂탔훊: 탔훊2. If Better(x,x)=1,then Better(x,x)= Better(x,x)=2,then Better(x,x)= Better(x,x)=0,then 1221122112Better(x,x)=0. 21탔훊3. If Better(x,x)=1,Better(x,x)=1,then Better(x,x)=1. 122313탔훊4. If Better(x,x)=1,Better(x,x)=0,then Better(x,x)≠2. 122313쿞폚욪럹풭틲틔벰횤쏷뇈뷏볲떥,헢늿럖뗄횤쏷싔.헢킩탔훊뿉틔복짙뷢횮볤뗄뇈뷏.탔훊2랴펳쇋Pareto햼폅뗄랴ퟔ랴탔.x뫍x뗄맘쾵뻶뚨쇋x뫍x뗄맘쾵,틲듋,x뫍x뗄뇈뷏뿉틔쪡싔.탔훊3랴펳쇋Pareto햼폅122121뗄뒫뗝탔,틲듋,x뫍x뗄뇈뷏뿉틔쪡싔.탔훊4퓚뇈뷏맽돌훐튲쫇뫜폐폃뗄. 13뛔폚뗚2룶쳵볾,뇘탫튪짨볆튻룶뫃뗄랽램,늻뷶죝틗헒떽Paretoퟮ폅벯,뛸쟒튪쪹폃룼짙뗄뇈뷏.헢훖랽램펦룃튪싺ퟣ쿂쏦뗄쳵볾:(1) Paretoퟮ폅벯훐뷡뗣뗄맘쾵뇘탫놣듦틔뇣죝틗헒떽ퟮ폅뷡뗣;(2) 쎿룶뷡뗣뇘탫훁
쪯뒨 뗈:튻훖뿬쯙뗄믹폚햼폅쫷뗄뛠쒿뇪뷸뮯쯣램 509 짙폫웤쯻뷡뗣폐튻룶맘쾵,럱퓲쯼쫇튻룶맂솢뷡뗣;(3) 튻킩훐볤뷡뗣훁짙폫웤쯻뷡뗣폐솽훖맘쾵,럱퓲헢킩뷡뗣늻쫇솬춨뗄.뺭맽럖컶,뛾닦쫷싺ퟣ헢킩쳵볾.춼2쪹폃뛾닦쫷뇭쪾춼1훐뷡뗣뗄맘쾵.죧춼2쯹쪾,Paretoퟮ폅뷢벯캪{N1,N4};훷튪맘쾵놻놣듦늢쟒뫜뛠죟폠맘쾵놻쪡싔.틲듋,쫷뿉틔폐킧뗘놣듦뷢뗄맘쾵,늢쟒쪹폃룼짙뗄뇈뷏.헢뿃쫷늻쫇뒫춳뗄뛾닦쫷,틲듋,컒쏇돆쯼캪햼폅쫷(dominating tree,볲돆DT),튻뿃햼폅쫷뿉틔죧쿂뚨틥: 뚨틥4. 햼폅쫷:튻뿃햼폅쫷쫇뚨틥죧쿂뗄뛾닦쫷: (1) 튻뿃햼폅쫷튪쎴쫇튻룶췢늿뷡뗣믲헟쫇튻룶솬뷓떽솽뿃뛾닦쫷뗄쓚늿뷡뗣,헢솽뿃뛾닦쫷럖뇰뷐ퟷퟳퟓ쫷뫍폒ퟓ쫷; (2) 햼폅쫷훐뗄쎿튻룶뷡뗣폐4룶폲:id,count,left-link,right-link,헢샯:id뇭쪾뷡뗣쯹듺뇭뗄룶쳥;count뇭쪾ퟳퟓ쫷뗄듳킡(냼삨ퟔ짭);left-link 횸쿲ퟳퟓ쫷,룃ퟓ쫷뗄룹뷡뗣놻룃뷡뗣햼폅; right-link횸쿲폒ퟓ쫷,룃ퟓ쫷뗄룹뷡뗣뫍룃뷡뗣컞램뇈뷏. 퓚놾컄훐,햼폅쫷뗄탖뗜솴쫇횸평쫷룹뫍폒솴뷡뗣릹돉뗄솴.틔춼2캪샽,N1뫍N4쫇DT뗄탖뗜솴,룹뷡뗣쫇N4,뛸쟒N3뫍N5튲릹돉쇋탖뗜솴.햼폅쫷뗄뚨틥폫뛾닦닩헒쫷(binary search tree,볲돆BST)쿠쯆.죧맻컒쏇뾼싇햼폅맘쾵뛔펦폚BST훐뗄킡폚맘쾵,늢쟒럇햼폅맘쾵뛔펦폚BST훐뗄듳폚맘쾵,DT뻍돉쇋BST.떫쫇,BST훐뷡뗣맘쾵쫇뛾횵뗄:킡폚뫍듳폚맘쾵;떫쫇,DT훐뗄맘쾵쫇죽횵뗄:0,1,뫍2.틲듋,햼폅쫷뗄릹퓬맽돌폫BST쫇쿠쯆뗄,떫좴튲쫇늻춬뗄. N4 N1 N3 N2 N5 Illustration of the dominating relationships with tree 춼2 폃쫷뇭쪾춼1훐뷡뗣맘쾵뗄쪾틢춼 햼폅쫷업탲쯣램 틲캪햼폅쫷뗄뒴붨맽돌폫뛾닦쯑쯷쫷뗄뒴붨맽돌뇈뷏쿠쯆,햼폅쫷뗄릹퓬쯣램튲쫇튻훖뗝맩쯣램.폫BST늻춬,튻룶탂뷡뗣닥죫떽DT훐폐3훖뿉쓜:떱탂뷡뗣놻룹뷡뗣햼폅쪱,쯼놻닥죫떽룹뷡뗣뗄ퟳퟓ쫷,헢폫BST훐뗄킡폚맘쾵쿠쯆;떱탂뷡뗣뫍룹뷡뗣컞램뇈뷏쪱,쯼놻닥죫떽룹뷡뗣뗄폒ퟓ쫷훐,헢폫BST훐뗄듳폚맘쾵쿠쯆;떫쫇,떱탂뷡뗣햼폅룹뷡뗣쪱,룹뻝탔훊4,룹뷡뗣뗄탖뗜솴훐뗄웤쯻뷡뗣늻뿉쓜햼폅탂뷡뗣.쓇쎴,탂뷡뗣늻뷶쳦듺룹뷡뗣뗄캻훃,죃룹뷡뗣돉캪쯼뗄ퟳퟓ쫷,뛸쟒펦룃볌탸뫍탖뗜솴훐뗄웤쯻뷡뗣뇈뷏.죧맻폐뷡뗣놻탂뷡뗣햼폅,퓲헢킩뷡뗣펦룃듓탖뗜솴훐즾돽,좻뫳닥죫떽탂뷡뗣뗄ퟳퟓ쫷훐. 죧춼3쯹쪾,쯼쿔쪾쇋춼2훐햼폅쫷뗄뒴붨맽돌(뷡뗣샯쏦ퟳ뇟뗄쫽ퟖ쫇뷡뗣뗄id,폒뇟뗄쫽ퟖ쫇쯼뗄count.춼내ퟖ쒸업탲).뷡뗣뗄쫤죫맽돌쫇N1,N2,N3,N4뫍N5;헢킩뷡뗣닥죫떽쫷훐뗄뷡맻럖뇰죧춼3(a)~춼3(e)쯹쪾.5룶뷡뗣닥죫뫳,햼폅쫷죧춼3(e)쯹쪾.뫜쏷쿔,햼폅쫷쫇늻욽뫢뗄,틲캪N4뗄count횵듳폚N1뗄count횵.캪쇋욽뫢뛾닦쫷,N4뫍쯼뗄ퟳퟓ쫷퇘ퟅ탖뗜솴쿲ퟳ틆,죧춼3(f)쯹쪾.헢룶틆뚯쎻폐룄뇤뷡뗣볤뗄맘쾵,떫뿉틔쪹뗃햼폅쫷룼볓욽뫢.춼2뫍춼3(f)뗄뷡맻튻퇹.욽뫢뗄햼폅쫷폐룼뛠폅뗣,헢쪹뗃퓶볓즾돽튻룶뷡뗣쯹뮨럑뗄듺볛룼짙.욽뫢맽돌뛔쳔청닟싔튲쫇맘볼뗄늽훨(볻뗚뷚).햼폅쫷뗄뒴붨맽돌쪵볊짏튲쫇쫊펦횵뗄횸엉맽돌,뷡뗣볤뗄맘쾵놣듦퓚쫷훐.틲듋,컒쏇튲냑햼폅쫷뗄릹퓬쯣램뷐ퟶ햼폅쫷업탲쯣램.
510 Journal of Software 죭볾톧놨 , , March 2007 1|1 1|2 1|2 1|2 1|2 4|3 3|1 4|2 4|3 1|2 2|12|1 2|1 2|1 3|1 3|1 3|1 5|1 2|1 5|1 (a) (b) (c) (d) (e) (f) Illustration of the creating process of the tree in 춼3 춼2훐쫷뗄뒴붨맽돌 믹폚짏쏦뗄럖컶,컒쏇폐햼폅쫷릹퓬쯣램.ConstructTree쫇뒴붨햼폅쫷뗄훷맽돌.쯣램훐폐3룶몯쫽:AddinTree뫍AddinSibling뇭쪾쇋튻룶탂뷡뗣닥죫떽햼폅쫷훐뗄닙ퟷ;떱뷡뗣뗄count횵룄뇤쪱,BalanceTree쪹뗃룃뷡뗣솬춬쯼뗄ퟳ몢ퟓ뷡뗣퇘ퟅ탖뗜솴쿲ퟳ믲헟폒틆뚯,헢퇹쪹뗃햼폅쫷룼볓욽뫢.헢튻쯣램돤럖샻폃쇋Pareto햼폅뗄탔훊,복짙쇋룶쳥횮볤뗄뇈뷏. 쯣램1. 햼폅쫷뗄업탲쯣램. /* Creating a dominating tree. tree is the root of the whole tree. */ Input: all nodes in the population. Output: the dominating tree. Link ConstructTree(){ For each node (newnode) in the population AddinTree(tree,newnode); return tree; } /* Add newnode into the left subtree of the tree whose root node is root when newnode is dominated by root. */ AddinTree(Link root,Link newnode){ root−>count=root−>count+newnode−>count; if (root−>left-link==null) then root−>left-link=newnode; else AddinSibling(root,root−>left-link,newnode); } /* Newnode is compared with child whose parent node is parent when newnode is inserted into parent’s left subtree.*/ AddinSibling(Link parent,Link child,Link newnode){ switch (Better(newnode,child)) case 0: //nondominated if (child−>right-link==null) then child−>right-link=newnode; else AddinSibling(parent,child−>right-link,newnode); case 1: //dominating newnode takes the place of child; AddinTree(newnode,child); while there exists a pnode (a node in the newnode’s sibling chain) and Better(newnode,pnode)==1, do { delete pnode from the sibling chain; AddinTree(newnode,pnode);
쪯뒨 뗈:튻훖뿬쯙뗄믹폚햼폅쫷뗄뛠쒿뇪뷸뮯쯣램 511 } BalanceTree(parent,newnode,L); case 2: //dominated AddinTree(child,newnode); BalanceTree(parent,child,L); } /* Sort the sibling chain of the parent’s left subtree in their count descending order. If the count of movenode (a node in the sibling chain) increases, it moves along the sibling chain in the left direction, or else in the right direction */ BalanceTree(Link parent,Link movenode,int direction){ if (direction==L) while the count of movenode is larger than that of its left nodes which is also in the same sibling chain; do movenode with its left subtree moves along the sibling chain in the left direction. if (direction==R) while the count of movenode is smaller than that of its right nodes which is in the same sibling chain; do movenode with its left subtree moves along the sibling chain in the right direction. } 햼폅쫷뗄탔훊 듓햼폅쫷뗄뒴붨맽돌뿉틔뗃떽햼폅쫷뗄튻킩훘튪탔훊. 뚨샭1. 햼폅쫷뗄룹뷡뗣뗄탖뗜솴횻놣듦룃쫷뗄쯹폐뗄Paretoퟮ폅뷡뗣. 췆떼:죧맻횻폐튻룶뷡뗣,뚨샭뫜쿔좻헽좷.죧맻뛔n룶뷡뗣뚨샭뚼돉솢,룹뻝햼폅쫷업탲쯣램,뛔쿂튻룶뷡뗣pnode폐3훖뿉쓜:죧맻pnode놻룹뷡뗣햼폅,퓲쯼놻닥죫떽룹뷡뗣뗄ퟳퟓ쫷;죧맻pnode폫룹뷡뗣컞램뇈뷏,퓲쯼펦룃뫍햼폅쫷뗄탖뗜솴훐뗄웤쯻뷡뗣뷸탐뇈뷏;죧맻쯼놻웤훐튻룶뷡뗣햼폅,퓲쯼펦룃놻닥죫떽뗚1룶햼폅뷡뗣뗄ퟳퟓ쫷;럱퓲,쯼돉캪탖뗜솴훐뗄튻룶뷡뗣.죧맻pnode햼폅룹뷡뗣,퓲룹뷡뗣펦룃듓탖뗜솴훐즾돽;뛔폚탖뗜솴훐뗄웤쯻뷡뗣,죧맻쯼쏇놻pnode햼폅,퓲쯼쏇튲펦룃듓탖뗜솴훐즾돽.틲듋,릹퓬맽돌뇭쏷,탖뗜솴횻놣듦쯹폐뗄ퟮ폅뷡뗣. 뚨샭2. 햼폅쫷뗄룹뷡뗣햼폅쯼ퟳퟓ쫷뗄쯹폐뷡뗣. 뚨샭3. 햼폅쫷룹뷡뗣뗄count횵뇈웤탖뗜솴훐웤쯻뷡뗣뗄count횵튪듳. 뚨샭2뗄횤쏷뫍뚨샭1샠쯆;뚨샭3평릹퓬쯣램튲뫜죝틗뗃떽,평폚욪럹풭틲,횤쏷쪡싔.뚨샭1뫍뚨샭2쫇햼폅쫷놣듦뗄훷튪맘쾵;뚨샭3놣횤쇋햼폅쫷쫇맦퓲뗄.떱뷡뗣닥죫뫍즾돽쪱,맦퓲뗄햼폅쫷폐룼뫃뗄욽뻹탔쓜. 3 믹폚햼폅쫷뗄뛠쒿뇪뷸뮯쯣램 룹뻝햼폅쫷뗄탔훊,컒쏇뿉틔짨볆튻룶볲떥룟킧뗄뛠쒿뇪폅뮯뷸뮯쯣램. 쳔청닟싔 DTEA뗄쳔청닟싔쫇룹뻝햼폅쫷짨볆뗄,쯼쳔청ퟮ닮뷡뗣.ퟮ닮뷡뗣뚨틥캪폐ퟮ듳count횵뗄햼폅쫷뗄ퟳ튶뷡뗣.룹뻝뚨샭3,ퟮ닮뷡뗣튲뻍쫇햼폅쫷뗄ퟮퟳ튶뷡뗣.샽죧,춼3(f)훐뗄ퟮ닮뷡뗣쫇N3.헢퇹뗄쳔청닟싔쫇뫏샭뗄,틲캪ퟮퟳ튶뷡뗣ퟜ쫇놻햼폅쫷훐뗄튻킩뷡뗣햼폅.쿂쏦룸돶쳔청닟싔뗄쯣램.컒쏇튻듎횻쳔청튻룶뷡뗣,헢퇹쪹뗃쯣램룼볓볲떥컈뚨.쇭튻랽쏦,쳔청닟싔놣횤쇋놻쳔청뗄뷡뗣ퟜ쫇쫷훐놻뫜뛠뷡뗣햼폅뗄뷡뗣. 쯣램2. 쳔청닟싔뗄쯣램. /* Delete the worst node of the dominating tree */ Input: the dominating tree Output: the worst node Link DeleteWorstNode(Link root){
512 Journal of Software 죭볾톧놨 , , March 2007 Link p=root−>left-link; root−>count--; if (p−>left-link == null) root−>left-link = p−>right-link; return p; else return DeleteWorst(root); } Link DeleteWorst(Link root){ Link p=root−>left-link; Link q=p−>left-link; p−>count--; if (q−>left-link==null) p−>left-link=q−>right-link; else q=DeleteWorst(p); BalanceTree(root,p,R); return q; } 쳔청닟싔튲ퟔ좻뗘놣듦쇋훖좺뗄뛠퇹탔.튻룶폐뷏듳count횵뗄뷡뗣틢캶ퟅ쒿뇪뿕볤훐뷏뛠뷡뗣놻룃뷡뗣햼폅,벴놻쯼햼폅뗄뿕볤샯쏦뗄뷡뗣룼펵벷,틲듋,헢킩뷡뗣펦룃폐룼듳뗄룅싊놻쳔청.쳔청폐ퟮ듳count횵뗄햼폅쫷뗄ퟮퟳ튶뷡뗣,웈쪹쯼뗄햼폅뿕볤훐뗄뷡뗣좥웤쯻뗘랽,헢쪹뗃뷡뗣룼볓뻹퓈뗘럖늼퓚쒿뇪뿕볤.헢훖쳔청닟싔늻뷶웈쪹뷡뗣룼볓뻹퓈뗘럖늼,뛸쟒횸떼훖좺뎯ퟮ폅잰퇘뷸뮯.쫂쪵짏,햼폅쫷퓚count폲훐틾몬쇋쏜뛈탅쾢.뷡뗣뗄count횵풽듳,놻쯼햼폅뗄뿕볤샯쏦뗄뗣풽펵벷.컒쏇힢틢떽,떱쯹폐룶쳥뚼컞램뇈뷏쪱,놻쳔청뗄뷡뗣쫇탖뗜솴훐뗄뗚1룶뷡뗣,헢퇹,쳔청닟싔늻퓙웰떽놣돖훖좺뛠퇹탔뗄ퟷ폃쇋.떫쫇쫂쪵짏,훖좺뗄뛠퇹탔늢늻닮,쪵퇩튲횤쪵쇋헢튻뗣. 훷돌탲 룹뻝햼폅쫷뫍쳔청닟싔,컒쏇뿉틔뗃떽DTEA쯣램. DTEA쯣램뗄훷맽돌(웤훐:P뇭쪾훖좺;t뇭쪾퓋탐듺쫽): Step 1. Randomly create P(0) with population size N. Set counter t=0. Step 2. Creating a dominating tree using the construction algorithm. Step 3. If stopping criterion is satisfied, then stop. Step 4. Generate an offspring and insert it into the dominating tree. Step 5. Eliminate a worst individual from the dominating tree. Step 6. t:=t+1, then turn to Step 3. 쯣램쫗쿈쯦믺닺짺튻룶돵쪼뮯듳킡캪N뗄훖좺P(0).t쫇퓋탐듺쫽,쫗쿈놻짨훃캪0.헢킩룶쳥룹뻝햼폅쫷업탲쯣램닺짺튻룶햼폅쫷.퓚뷸뮯뷗뛎,탂닺짺뗄뫳듺놻닥죫떽햼폅쫷훐,놻쳔청뗄룶쳥듓햼폅쫷훐즾돽.헢룶맽돌튻횱훘뢴,횱떽춣믺쳵볾놻싺ퟣ캪횹.퓚룃쯣램훐,뿉틔샻폃룷훖뫏쫊뗄쯣ퟓ닺짺탂뗄뫳듺,샽죧뫳쏦쪵퇩훐쯹폃뗄SBX쯣ퟓ.룃쯣램퓚쪵볊펦폃맽돌훐,쎿튻듺퓋탐퓚뢸듺훐톡퓱죴룉룶룶쳥(틀뻝쯣ퟓ튪쟳),내헕쯣ퟓ닙ퟷ튻듎닺짺죴룉뫳듺,붫쯼쏇닥죫떽햼폅쫷훐,늢춬쪱즾돽쿠춬룶쫽뗄ퟮ닮룶쳥. DTEA쫇튻룶탂펱뗄뛠쒿뇪뷸뮯쯣램,쯼뫜짙쪹폃웤쯻뛠쒿뇪뷸뮯쯣램훐쯹쪹폃뗄벼쫵.틔췹,뫜뛠MOEA퓚뾿뷼잰퇘뫍놣돖뛠퇹탔랽쏦쪹폃쇋늻춬뗄랽램,헢쪹뗃쯣램뫜뢴퓓.떫쫇,DTEA냑쫕솲탔닟싔뫍뛠퇹탔닟싔헻뫏떽햼폅쫷훐,헢퇹늻뷶놣듦쇋뷢뗄햼폅맘쾵,뛸쟒ퟔ좻뗘놣돖쇋훖좺뗄뛠퇹탔.틲듋,DTEA뇈뫜뛠MOEA뚼볲떥.DTEA쫇튻훖컈첬뗄쯣램.틲캪튻듺횻닺짺믲쳔청튻룶뷢,폅탣룶쳥놻쳔청뗄뿉쓜탔쫇뫜킡뗄.튻떩랢쿖튻
쪯뒨 뗈:튻훖뿬쯙뗄믹폚햼폅쫷뗄뛠쒿뇪뷸뮯쯣램 513 룶뫃뗄뷢,횱떽쯼돉캪훖좺훐ퟮ닮뗄뷢닅믡놻쳔청.뷸뮯쯣램쫇튻훖쯦믺쯣램,튻킩MOEA퓚뷸뮯맽돌훐쳔청뫃뗄뷢[7],헢쪹뗃쯣램뇈뷏뗍킧.뺫펢닟싔뻍쫇폃살뷢뻶헢룶컊쳢뗄[6],떫쫇,헢훖랽램퓶볓쇋쪱볤뫍뿕볤뗄뢴퓓탔.DTEA쎻폐쪹폃뛮췢뗄듺볛뻍쪵쿖쇋뺫펢닟싔. 퓚웤쯻뎣폃MOEA(죧SPEA2뫍NSGA-II)뗄쫊펦횵횸엉랽램훐,튪움볛튻룶룶쳥뗄쫊펦횵,탨튪폫훖좺훐뗄웤쯻쯹폐룶쳥뷸탐뇈뷏,틲듋,움볛튻룶룶쳥뗄뇈뷏듎쫽캪N−1(N캪훖좺맦쒣).퓚DTEA훐,움볛튻룶룶쳥횻탨튪붫웤닥죫떽쫷뷡릹훐,퓚튻냣쟩뿶쿂,뇈뷏듎쫽쫇킡폚N뗄.뛸쟒퓚뛠퇹탔닟싔(뛔DTEA뛸퇔뻍쫇쳔청닟싔)훐,쳔청튻룶ퟮ닮룶쳥뗄쪱볤뢴퓓뛈튲쫇킡폚N뗄,뛸뫜뛠MOEA훐뗄뛠퇹탔닟싔뚼쫇O(N)(뛔튻룶룶쳥뛸퇔[8]).틲듋,DTEA튪뇈뫜뛠MOEA뚼튪뿬,쪵퇩튲퇩횤쇋헢튻뗣.DTEA훐쪹폃쇋햼폅쫷뷡릹,쯼뗄뿕볤뢴퓓뛈캪O(N).뫜뛠MOEA뚼쪹폃쇋뺫펢듦떵웷(elite archive),웤뿕볤뢴퓓뛈튲쫇O(N).틲듋,DTEA늢쎻폐쪹폃룼뛠뗄듦뒢뿕볤. 폫DTEA쿠쯆,PAES튲쫇쎿듺닺짺뫍즾돽튻룶뷡뗣.PAES쫇(1+1)뗄뷸뮯닟싔,쯼쪹폃쇋뻖늿쯑쯷뗄쯣ퟓ틔벰뺫펢훖좺,놣듦틑뺭랢쿖뗄뇈뷏뫃뗄뷢[3].PAES횻쪹폃쇋뇤틬쯣ퟓ,떫쫇,냼삨퓓붻뇤틬쯣ퟓ퓚쓚뗄뫜뛠쯣ퟓ뚼뿉틔퓚DTEA훐쪹폃.캪쇋놣돖훖좺뛠퇹탔,PAES훐쪹폃쇋뎬췸룱뗄랽램,떫쫇,DTEA훐쎻폐쏅뗄놣돖뛠퇹탔뗄닟싔.MOEA훐튲쪹폃쇋웤쯻튻킩뫜폐좤뗄쫷뷡릹.Mostaghim샻폃쇋Quad-tree헢훖폐킧뗄쫽뻝뷡릹놣듦ퟮ폅룶쳥[16].떱뺫펢훖좺듳킡늻쫜쿞훆쪱,Fieldsend짨볆쇋dominated/nondominated tree폃폚볓쯙룶쳥뗄닩헒뫍업탲[11].햼폅쫷폫쯼쏇쿠뇈쫇췪좫늻춬뗄:튻랽쏦,햼폅쫷폫웤쯻랽램폐췪좫늻춬뗄쫽뻝뷡릹;쇭튻랽쏦,쯼쏇뷢뻶뗄컊쳢튲늻춬.햼폅쫷쫇튻훖탂뗄쫊펦횵횸엉랽램,쯼듦뒢쯹폐뷢뗄햼폅탅쾢.떫쫇,dominated/ nondominated tree뫍Quad-tree횻폃폚뺫펢훖좺훐뗄룶쳥뗄듦뒢뫍업탲. 4 쪵퇩폫쳖싛 캪쇋볬퇩쯹쳡돶뗄DTEA,컒쏇뇈뷏DTEA폫웤쯻솽룶훸쏻뗄MOEAs-SPEA2뫍NSGA-II-뗄탔쓜.웤쯻솽훖쯣램룹뻝컄쿗[1,2]내헕C폯퇔살쪵쿖.쪵퇩퓋탐퓚3GHz 512M쓚듦퓋탐Windows 2000뗄Pentium IV믺 웷짏. ퟮ돵뗄DTEA틑뺭샻폃튻킩뎣폃뗄닢쫔몯쫽퓚뾿뷼ퟮ폅잰퇘랽쏦뫍튻킩MOEAퟷ뇈뷏 [17].쪵퇩뇭쏷:룃쯣램쓜릻뷓뷼ퟮ폅잰퇘,늢쟒뛔듳늿럖컊쳢뚼놣돖쇋훖좺뗄뛠퇹탔.퓚놾컄훐,컒쏇퓶볓3룶쒿뇪뗄닢쫔몯쫽,늢쟒3훖쯣램붫듓3룶랽쏦뷸탐뇈뷏:뾿뷼ퟮ폅잰퇘놣돖훖좺뛠퇹탔뫍퓋탐쪱볤.헢킩몯쫽톡ퟔ놾쇬폲뗄튻킩훘튪퇐뺿,헢킩몯쫽뗄탅쾢볻뇭2.퓚쪵퇩훐,쎿룶몯쫽볆쯣30듎,쎿듎볆쯣뷡쫸뫳,놣듦떱잰훖좺훐뗄ퟮ폅뷢;뫏늢30듎볆쯣뗄ퟮ폅뷢,퓙쟳돶뫏늢뫳뗄뷢벯훐뗄ퟮ폅뷢,붫웤ퟷ캪ퟮ훕뷡맻.헢퇹ퟶ뗄쒿뗄퓚폚복짙쯣램뗄쯦믺탔뗄펰쿬,쪹웤뷡맻뇈뷏룼볓뿍맛.늻춬쯣램뗄ퟮ뫳뷡맻내헕뇪ힼ뷸탐뇈뷏.퓋탐쪱볤쫇욽뻹퓋탐쪱볤. 뛔SPEA2뫍NSGA-II,컒쏇내헕컄쿗훐붨틩뗄닎쫽짨훃;뛔DTEA,쎻폐쳘뇰뗄닎쫽탨튪짨훃.캪쇋릫욽뇈뷏헢3룶쯣램,쯼쏇뚼쪹폃쇋쒣쓢뛾뷸훆퓓붻(simulated binary crossover,볲돆SBX)뫍뛠쿮쪽뇤틬쯣ퟓ(polynomial mutation)[18].훖좺듳킡쫇100;뺫펢훖좺듳킡쫇100.퓚QV뫍KUR훐,쯣ퟓ뗄닎쫽짨훃캪hc=20뫍hm=20;뛔웤쯻몯쫽짨훃캪hc=15뫍hm=20.퓚QV뫍KUR훐,퓓붻룅싊캪,퓚DTLZ1~DTLZ4,룃횵캪1.뛔쯹폐뗄닢쫔몯쫽,뇤틬룅싊캪1/n,n캪뻶닟뇤솿뗄룶쫽.놻움볛룶쳥뗄쫽쒿짨훃죧쿂:QV뫍KUR캪15 000;DTLZ1뫍DTLZ2캪 30 000;DTLZ3캪50 000;DTLZ4캪20 뫍NSGA-II뗄퓋탐듺쫽캪움볛룶쳥뗄쫽쒿돽틔훖좺맦쒣.틲캪SBX쯣ퟓ튻듎닺짺뫍즾돽솽룶룶쳥,쯹틔,DTEA뗄퓋탐듺쫽캪움볛룶쳥뗄쫽쒿돽틔2. 놾컄쪹폃쇋솽룶뎣폃뗄움볛뇪ힼ.컒쏇샻폃C(X,Y)살뇈뷏솽룶ퟮ폅뷢벯뾿뷼잰퇘뗄돌뛈[10].C(X,Y)=1뇭쪾Y훐쯹폐뷢뚼놻X훐뗄뷢햼폅.쿠랴뗘,C(X,Y)=0뇭쪾Y훐쎻폐뷢놻X훐뗄뷢햼폅.힢틢떽,C(X,Y)뫍C(Y,X)뚼탨튪놻뾼싇,틲캪C(Y,X)늢늻튻뚨뗈폚1−C(X,Y).D뇭쪾쇋뷢벯뗄럖즢돌뛈[20],튻룶뫃뗄럖즢탔붫믡쪹뗃D뷓뷼0.헢솽룶움볛뇪ힼ쫇뛀솢폚ퟮ폅잰퇘뗄,쯼쏇퓚튻뚨돌뛈짏랴펳쇋뷢뗄훊솿,늢쟒튲뿉틔펦폃퓚룟캬쒿뇪뿕볤훐.
514 Journal of Software 죭볾톧놨 , , March 2007 Table 2 Test problems used in the study 뇭2 쪵퇩닢쫔몯쫽 Problem n Domain Objective functions Comments 12f1(x)=∑n(x−10cos(2pix)+10)ni=1iiQV[2]n 2 objectives 100 [−5,5] 12f2(x)∑n=((x−)−10cos(2ð(x−))+10)ni=1ii∑n−1(x)=(−10expf2 objectives 111KUR[1,2]i=−+ii+ 3 [−5,5]n nonconvex x∑=x+xdisconnected 2()(||5sin)i=1ii1f1(x)=x1x2(1+g(xM))21f2(x)=x1(1−x2)(1+g(xM)) DTLZ1[19]7 [0,1]n 23 objectives hyper-plane 1f3(x)=(1−x1)(1+g(xM))2g(xM)=100xM+∑2(||∈((x−)−cos(20ð(x−))))xxiiiMf1(x)=(1+g(xM))cos(x1ð/2)cos(x2ð/2)f2(x)=(1+g(xM))cos(x1ð/2)sin(x2ð/2)DTLZ2[19] 3 objectives 12 [0,1]n f3(x)=(1+g(xM))sin(x1ð/2)spherical gx2(M)=∑∈(x−)xxMiif1(x)=(1+g(xM))cos(x1ð/2)cos(x2ð/2)f2(x)=(1+g(xM))cos(x1ð/2)sin(x2ð/2)DTLZ3[19] 3 objectives 7 [0,1]n f3(x)=(1+g(xM))sin(x1ð/2)spherical g(xM)=100(|xM|+∑∈((x−)−cos(20ð(x−))))xxiiiMf(x)=(1+g(x1001001M))cos(x1ð/2)cos(x2ð/2)f(x)=(1+g(x1001002M))cos(x1ð/2)sin(xDTLZ4[19]2ð/2) 3 objectives 12 [0,1]n fx=+gx1003()(1(M))sin(x1ð/2)spherical gx2(M)=∑∈(x−)xxiiM뇭3쿔쪾쇋3훖쯣램샻폃쟷뷼잰퇘뗄움볛뇪ힼC뗃떽뗄뇈뷏뷡맻(D뇭쪾DTEA;S뇭쪾SPEA2;N뇭쪾NSGA-II).뛔닢쫔몯쫽QV뫍KUR,DTEA뫜쏷쿔뗘룼뾿뷼잰퇘.떫쫇,뛔DTLZ1몯쫽,DTEA뗄뷡맻뷏닮;뛔웤쯻몯쫽,쯼쏇뗄탔쓜쿠떱.뫜쏷쿔:뛔헢킩닢쫔몯쫽뛸퇔,퓚뷓뷼ퟮ폅잰퇘뗄탔쓜짏,DTEA쿠뇈웤쯻쯣램쫇뫜폐뺺헹솦뗄. Table 3 Convergence comparison of different algorithms using C 뇭3 늻춬쯣램샻폃C뇈뷏쟷뷼잰퇘뗄뷡맻 QV KUR DTLZ1 DTLZ2 DTLZ3 DTLZ4 C(D,S) 1 C(D,N) 1 C(S,D) 0 C(N,D) 0 뇭4쿔쪾뗄쫇3훖쯣램샻폃럖즢탔움볛뇪ힼD뗃떽뗄뇈뷏뷡맻.퓚놣돖뛠퇹탔랽쏦,돽쇋KUR,DTEA늢늻뇈웤쯻솽훖쯣램닮.쪵퇩뷡맻쿔쪾:DTEA훐뗄쳔청닟싔쫇폐킧뗄,쯼놣돖쇋훖좺뗄뛠퇹탔.뗚뷚훐틑뺭쳡떽:떱쯹폐뗄뷡뗣컞램뇈뷏쪱(듋쪱,햼폅쫷퇝뇤돉튻룶횻폐폒솴뗄뛓쇐),DTEA훐뗄쳔청닟싔늻퓙웰떽놣돖훖좺뛠퇹탔뗄ퟷ폃.떫쫇,DTEA쯣램폫웤쯻쯣램튻퇹뷏뫃뗘놣돖쇋훖좺뛠퇹탔.ퟜ뗄살쮵,튻랽쏦,탂닺짺뗄뷡뗣뇈풭쿈뗄뷡뗣튪뫃,뛸탂닺짺뗄럇햼폅뷡뗣튻냣업탲떽햼폅쫷뗄탖뗜솴뗄쒩뛋,틲듋,놻즾돽뗄뷡뗣ퟜ쫇뇈뷏닮뗄뷡뗣;쇭튻랽쏦,떱탂닺짺뗄뷡뗣햼폅폚탖뗜솴훐뗄튻룶뷡뗣쪱,헢룶뛓쇐폖뇤돉쇋튻뿃햼폅쫷.틲듋,쳔청닟싔퓚듳늿럖쪱볤뚼쫇폐킧뗄.
쪯뒨 뗈:튻훖뿬쯙뗄믹폚햼폅쫷뗄뛠쒿뇪뷸뮯쯣램 515 Table 4 Distribution comparison of different algorithms using D 뇭4 늻춬쯣램샻폃D뗃떽뗄뛠퇹탔뇈뷏뷡맻 QV KUR DTLZ1 DTLZ2 DTLZ3 DTLZ4 DTEA SPEA2 NSGA-II 뇭5쿔쪾쇋헢3훖쯣램뗄퓋탐쪱볤.DTEA뗄퓋탐쪱볤뫜쏷쿔뗘킡폚웤쯻솽훖쯣램.틲캪NSGA-II훐쪹폃쇋폐킧뗄쏜뛈맀볆쯣램뫍뿬쯙럇햼폅업탲쯣램[1],NSGA-II뫜쏷쿔뿬폚SPEA2.쪵퇩뷡맻쿔쪾,햼폅쫷업탲좷쪵볓뿬쇋쫊펦횵횸엉맽돌. Table 5 Comparison of different algorithms on running time (ms) 뇭5 늻춬쯣램뗄퓋탐쪱볤 (뫁쏫) QV KUR DTLZ1 DTLZ2 DTLZ3 DTLZ4 DTEA 955 236 619 1083 1105 720 SPEA2 4 237 3 095 10 333 10 630 17 611 8 339 NSGA-II 1 642 772 2 039 2 553 3 502 1 753 춨맽짏쏦뗄럖컶뫍뇈뷏,컒쏇랢쿖:퓚쟷뷼ퟮ폅잰퇘뫍놣돖뷢뗄럖즢탔랽쏦,DTEA폫SPEA2뫍NSGA-II쿠뇈쫇뫜폐뺺헹솦뗄;쳘뇰쫇퓚퓋탐쪱볤랽쏦,쯼뇈쇭췢솽훖쯣램튪뿬뗃뛠.ퟜ횮,햼폅쫷쫇튻훖룟킧뗄쫊펦횵횸엉랽램,뛸쟒,믹폚햼폅쫷뗄쳔청닟싔튲폐킧뗘놣듦쇋훖좺뗄뛠퇹탔. 5 ퟜ 뷡 폃뷸뮯볆쯣뷢뻶뛠쒿뇪폅뮯컊쳢쫇놻맣랺퇐뺿뗄폐킧랽램,떫쫇,쒿잰뫜뛠쯣램뚼뇈뷏뢴퓓,쪱볤뢴퓓뛈뷏룟.헫뛔헢훖쟩뿶,놾컄쳡돶튻훖탂뗄뛠쒿뇪뷸뮯쯣램뿉틔놻룅삨캪:(1) 쪹폃쇋Better몯쫽(튻룶3횵몯쫽)뇈뷏뷢뗄뫃뮵;(2) 쳡돶쇋햼폅쫷헢훖쫽뻝뷡릹,폃폚놣듦뷢횮볤뗄햼폅탅쾢,늢쟒낵몬쇋쏜뛈탅쾢.헢훖랽램췪좫샻폃쇋Pareto햼폅뗄탔훊,늢쟒쿔훸복짙쇋룶쳥횮볤뗄뇈뷏;(3) 믹폚햼폅쫷뗄쳔청닟싔,뿉틔늻탨튪뛮췢뗄듺볛뻍놣돖훖좺뛠퇹탔.DTEA붫쫕솲탔뫍뛠퇹탔닟싔헻뫏떽햼폅쫷훐,틲듋,DTEA뇈뫜뛠쯣램뚼볲떥.틲캪쯣램뗄컈첬쳘헷,DTEA늻탨튪죎뫎뛮췢뗄듺볛뻍쪵쿖쇋뺫펢닟싔.춨맽뇈뷏쪵퇩,컒쏇랢쿖:퓚6룶닢쫔몯쫽짏,DTEA좡뗃쇋폫NSGA-II뫍SPEA2쿠뇈탔쓜쿠떱뗄뷢,떫쫇,DTEA뇈쯼쏇튪뿬뗃뛠. References: [1] Deb K, Pratab A, Agarwal S, MeyArivan T. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation, 2002,6(2):182−197. [2] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-Report 103, 2001. [3] Knowles JD, Corne DW. The Pareto archived evolution strategy: A new baseline algorithm for Pareto multi-objective optimization. In: Proc. of the 2003 IEEE Conf. on Evolutionary Computation. 1999. 98−105. [4] Atashkari K, Nariman-Zadeh N, Pilechi A, Pilechi A, Yao X. Thermodynamic Pareto optimization of turbojet engines using multi-objective genetic algorithm. Int’l Journal of Thermal Sciences, 2005,:1−11. [5] Yen G, Lu H. Dynamic multiobjective evolutionary algorithm: Adaptive cell-based rank and density estimation. IEEE Trans. on Evolutionary Computation, 2003,7(3):253−274. [6] Zitzler E, Thiele L. Multi-Objective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Trans. on Evolutionary Computation, 1999,3(4):257−271. [7] Veldhuizen DAV, Lamont GB. Multi-Objective evolutionary algorithms: Analyzing the state-of-the-art. IEEE Trans. on Evolutionary Computation, 2000,18(2): 125−147. [8] Fonseca CM, Fleming PJ. Multi-Objective optimization and multiple constraint handling with evolutionary algorithmsPart I: A unified formulation. IEEE Trans. on Systems, Man and CyberneticsPart A: Systems and Humans, 1998,28(1):26−37.
516 Journal of Software 죭볾톧놨 , , March 2007 [9] Xin Y, Xu Y. Recent advances in evolutionary computation. Journal of Computer Sciences and Technology, 2006,21(1):1−18. [10] Zitzler E, Deb K, Thiele L. Comparison of multi-objective evolutionary algorithms: Empirical results. IEEE Trans. on Evolutionary Computation, 2000,18(2):173−195. [11] Fieldsend JE, Everson RM, Singh S. Using unconstrained elite archives for multi-objective optimization. IEEE Trans. on Evolutionary Computation, 2003,7(3):305−323. [12] Cui XX, Lin C. A preference-based multi-objective concordance genetic algorithm. Journal of Software, 2005,16(5):761−770 (in Chinese with English abstract). [13] Lei DM, Wu ZM. Crowding-Measure based multi-objective evolutionary algorithm. Chinese Journal of Computers, 2005,28(8): 1320−1326 (in Chinese with English abstract). [14] Zeng SY, Wei W, Kang LS, Yao SZ. A multi-objective evolutionary algorithm based on orthogonal design. Chinese Journal of Computers, 2005,28(7):1153−1162 (in Chinese with English abstract). [15] Jensen MT. Reducing the run-time complexity of multi-objective EAs: The NSGA-II and other algorithms. IEEE Trans. on Evolutionary Computation, 2003,7(5):503−515. [16] Mostaghim S, Teich J, Tyagi A. Comparison of data structures for storing Pareto-sets in MOEAs. In: Proc. of the World Congress on Computational Intelligence. 2002. 843−849. 7875/ 21693/ &arnumber= 1007035 [17] Shi C, Li Y, Kang LS. A new simple and highly efficient multi-objective optimal evolutionary algorithm. In: Proc. of the 2003 IEEE Conf. on Evolutionary Computation. 2003. 1536−1542. iel5/9096/28878/ &arnumber=1299855 [18] Deb K, Agrawal RB. Simulated binary crossover for continuous search space. Complex Systems, 1994,l(9):115−148. [19] Deb K, Thiele L, Laumanns M, Zitzler E. Scalable multi-objective optimization test problems. In: Proc. of the 2002 Congress on Evolutionary Computation. 2002. 825−830. 21693/ 1007032 [20] Deb K, Samir A, Pratap A, Meyarivan T. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Technical Report. 뢽훐컄닎뾼컄쿗: [12] 듞톷톧,쇖뒳.튻훖믹폚욫뫃뗄뛠쒿뇪뗷뫍틅뒫쯣램.죭볾톧놨,2005,16(5):761−770. [13] 샗뗂쏷,컢훇쏺.믹폚룶쳥쏜뛈뻠샫뗄뛠쒿뇪뷸뮯쯣램.볆쯣믺톧놨,2005,28(8):1320−1326. [14] 퓸죽폑,캺캡,뾵솢즽,튦쫩헱.믹폚헽붻짨볆뗄뛠쒿뇪퇝뮯쯣램.볆쯣믺톧놨,2005,28(7):1153−1162. ?? 쪯뒨(1978),쓐,뫾놱뫩뫾죋,늩쪿짺,훷쪷훒횲(1941),쓐,퇐뺿풱,늩쪿짺떼튪퇐뺿쇬폲캪틅뒫쯣램,믺웷톧쾰. 쪦,CCF룟벶믡풱,훷튪퇐뺿쇬폲캪죋릤훇쓜,믺웷톧쾰,짱뺭볆쯣,죏횪뿆톧. 샮쟥폂(1979),쓐,늩쪿짺,훷튪퇐뺿쇬폲?캪믺웷톧쾰,춼쿱샭뷢,쫓뻵탅쾢췚뻲.?
