untitled

Size: px

Start display at page:

Download "untitled"

弦虞廉
8 years ago
Views:

1 ISS -985, CODE RUXUEW E-mal: Journal of Software, Vol., o.6, June, pp do:.374/sp.j Tel/Fax: by Insttute of Software, the Chnese Academy of Scences. All rghts reserved.,, + (, 483) Hybrd Self-Adaptve Orthogonal Genetc Algorthm for Solvng Global Optmzaton Problems JIAG Zhong-Yang, CAI Z-Xng, WAG Yong + (School of Informaton Scence and Engneerng, Central South Unversty, Changsha 483, Chna) + Correspondng author: E-mal: [email protected] Jang ZY, Ca ZX, Wang Y. Hybrd self-adaptve orthogonal genetc algorthm for solvng global optmzaton problems. Journal of Software,,(6): Abstract: Ths paper presents a hybrd self-adaptve orthogonal genetc algorthm (HSOGA) based on orthogonal expermental desgn method for solvng global optmzaton problems. In HSOGA, the orthogonal expermental desgn method s utlzed to desgn crossover operator, and as a result, a self-adaptve orthogonal crossover operator s proposed. The self-adaptve orthogonal crossover operator self-adaptvely adjusts the number of orthogonal array s factors and the locaton for dvdng the s nto several sub-vectors accordng to the smlarty of the two s, n order to produce a small but representatve set of ponts as the potental offsprng. In addton, n HSOGA the self-adaptve orthogonal crossover operator s also adopted to generate an ntal populaton that s scattered unformly over the feasble soluton space n order to mantan the dversty. Moreover, a local search scheme s ncorporated nto HSOGA n the purpose of enhancng the local search ablty and speedng up the convergence of HSOGA. HSOGA s tested wth fourteen benchmark functons. The expermental results suggest that HSOGA s generc and effectve. Key words: orthogonal genetc algorthm; local search; global optmzaton; orthogonal expermental desgn : (hybrd self-adaptve orthogonal genetc algorthm, HSOGA),,.,,.,,.. 4 Supported by the atonal atural Scence Foundaton of Chna under Grant os.983, 6857 (); the Specalzed Research Foud for the Doctoral Program of Hgher Educaton of Chna under Grant o ( ); the Graduate Innovaton Fund of Hu nan Provnce of Chna under Grant o.cx9b39 (); the Graduate Degree Thess Innovaton Foundaton of Central South Unversty of Chna under Grant o ( ) Receved 8-3-3; Revsed 8-8-7; Accepted 9--6

2 : 97 Benchmark : ;;; : TP8 : A, mnmze f (x), x = ( x,..., x) S = [ l, u] (), f(x), l = ( l, l,..., l ), u= ( u, u,..., u ),[l,u].,,., [],,.,, [ 5].Zhang Leung [],,,,,.Leung Wang [3] (OGA/Q). [4],.Wang [5]..,,.,.. [,3], F, Q, Q F,, Q F. Q F, Q F., L M (Q F ),,.L M (Q F ) F Q, L,M.L M (Q F ) M,. L M (Q F ), M, M Q F. L 9 (3 4 ),(), 4 3, L 9 (3 4 ), 9,, 3 4 =8.,, L9 (3 ) = 3 () , L M (Q F )=[a,j ] M F, j a,j,a,j {,,,Q}. 3 J [a,j ] M F j a j, j=,,( Q ) ( Q ) +,..., ( Q ) ( Q ) +, a j,. [3] L M (Q F ),,,. =

3 98 Journal of Software Vol., o.6, June Q, M=Q J,J (3),, Q, L M (Q F ) F,, M.. L M (Q F ). F J Q J Step. Select the smallest J fulfllng ( Q ) ( Q ) F J J Step. If ( Q ) ( Q ) = F,then F =F else F = ( Q ) ( Q ) Step 3. Construct the basc columns as follows: for k= to J do k Q j = + ; Q for = to Q J do a end for end for = mod Q ;, j J Q Step 4. Construct the non-basc columns as follows: for k= to J do k Q j = + ; Q for s= to j do end for for t= to Q do a = j ( s )( q ) t ( a s t aj) mod Q; end for end for Step 5. Increment a,j by one for all M and j F F Step 6. Delete the last F F columns of L ( Q ) to get L M (Q F ) where M=Q J J Q Q (3),[3,5],,,,,,.,,,.,, (self-adaptve orthogonal crossover, SOC). SOC., SOC, (hybrd self-adaptve orthogonal genetc algorthm, HSOGA)..,a b,c d, a = (3,.5), b = (.5,3), c = (3.5,3.5), d = (4,4), a b

4 : 99 [(.5,.5),(3,3)] A,c d [(3.5,3.5),(4,4)] B. L 5 (5 ), Q=5,F=,M=5,, M,., L M (Q F ) Q, F, M., c d, B,,,.,,. Fg. Dstrbuton of the offsprng generated by usng orthogonal array to arrange the crossover operaton of the chromosome,,.,,,.,,.,,. p = ( p,, p,,..., p, ), p = ( p,, p,,..., p, ), p,p l = [mn( p,, p,),mn( p,, p,),...,mn( p,, p, )] [ l, u ],. u = [max( p,, p,),max( p,, p,),...,max( p,, p, )],:. δ = p p, =,,,.δ p,p. p p,δ, p, p., δ > δ ( δ ), p,p. p, p ( ) (4) = d = p p, p p,δ, p p., p, p d, p,p [ l, u ]., [ l, u ] p,p. J p,p,: J = { p p > δ, =,,..., } (5) p,p t, t. p,p t t, Z.,p,p [ l, u ] p,p, Z. p,p t, t, [ l, u ] Z. p,p Z,, [ l, u ].

5 3 Journal of Software Vol., o.6, June, p =(,4,5,7),p =(,3,5,7), p,p [ l, u ] = [(,3,5,7),(,4,5,7)],δ =.5, t=.p,p t, Z = [(,3),(,4)]. s s Q=, L M (Q F ), L 4 ( ). L4( ) = (6) p,p, factor factor, p,p 3 4 factor,,(7). factor factor. p,p. L 4 ( ), P,(7): p : (, 4, 5, 7) p :(, 3, 5, 7) (, 4, 5, 7) (, 3, 5, 7) P = (, 4, 5, 7) (, 3, 5, 7) p,p, factor, p,p 3 4, factor,(8). factor factor. p,p. L 4 ( ), P,(8): (, 4, 5, 7) p :(, 4, 5, 7) (, 4, 5, 7) P = (8) p :(, 3, 5, 7) (, 3, 5, 7) (, 3, 5, 7) P, t Z = [(,3),(,4)]. P, P.,.,p,p p,p [ l, u ],, Z,, Z,, [ l, u ]. p,p δ,δ t, δ, p,p,p,p, Step, Q., t Q, L M (Q F ), M, F=t.. Q=,,, t=,.,,,.,,,,,,.. (self-adaptve orthogonal crossover, SOC). Step. p = ( p,, p,,..., p, ), p = ( p,, p,,..., p, ), p p [ l, u ]. [ l, u ] Q, β,,β,,, (7)

6 : 3 β,q, {,,,}, β = ( β,, β,,..., β, Q),, mn( p,, p, ), j = p, j p, j βj = mn( p,, p, ) + ( j ), j Q (9) Q max( p,, p, ), j = Q Step. k = [ k, k,..., k t ],:k J k < k <... < kt,j=,,,t, J (5),t p,p,δ. k p,p,. x p,p, x = ( x, x,..., x ) t, x : f = ( x,..., xk ) f = ( xk +,..., xk ) ()... ft = ( xk,..., x ) t + k =, f Q f() = ( βk,, β,,...,,) k β + + k f() = ( βk,, β,,...,,) k β + + k ()... f( Q) = ( βk,,,,...,, ) Q βk Q β + + k Q Step 3. L ( F M Q ) = [ b, j] M F, F=t. L M (Q F )() t () Q, M : ( f( b,), f( b,),..., ff( b, F) ( f( b,), f( b,),..., ff( b, F) ()... ( f ( bm,), f ( bm, ),..., ff( bm, F) p = (,,6,4,,), p = (,3,8,4,,), Q=3., p,p,: Step. p,p [ l, u ] = [(,,6,4,,),(,3,8,4,,)], [ l, u ] β : β = (,,) β = (,,3) β3 = (6,7,8) (3) β4 = (4,4,4) β5 = (,,) β6 = (,,) Step. δ =.5,(5) J={,,3},t=3,F=3, k=[,,3].(), x = ( x, x, x3, x4, x5, x6) 3 : f = ( x), f = ( x), f3 = ( x3, x4, x5, x6). Step 3. L 9 (3 3 ),, 9 :

7 3 Journal of Software Vol., o.6, June. (,, 6, 4,, ) (,, 7, 4,, ) (, 3, 8, 4,, ) (,, 7, 4,, ) (,, 8, 4,, ) (, 3, 6, 4,, ) (,, 8, 4,, ) (,, 6, 4,, ) (, 3, 7, 4,, ) (4),,,,.,,,,,.,,., [l,u],,[l,u] S, 3, L M (Q F ), L M (Q F ) SOC,. 3.. Step. s,s : u l = max{ u l} (5) s s Step. [l,u] s S [ l(), u()],[ l(), u()],...,[ l( S), u( S )]. us ls l () = l+ ( ) Is S, =,,..., S (6) us ls u () = u ( S ) Is S I = [ c ], c, s, j j, j = s =., j =.3,,[],.,,.,,(SPX) [6,7].,,,.,. [l,u], P n,,o, P P.:, P = { p, p,..., p n } n,, m, m=3., SPX m (, S), g (, S ), g=, P. 4,.

8 : o = ( x, x,..., x ), k =, P = ; whle( k < n/ m ) S =, S = ; P o p j,j {,,,n k }; S={p j } {P p j m }; P=P S, P = { p, p,..., p nk }; S = SPX( S) ; P = P S ; k=k+; End.4 Step.. [l,u] S, 3. Q, SOC, P,, P n P. Step. P gen gen, P gen, p c P gen. P gen, P gen P gen. Step 3.. P, SOC,, gen C gen., Q. Step 4. P gen, L gen 4. Step 5. P p = ( p,, p,,..., p, ), {,,..., n}, p m.: gen j [,], r [,]; p, = l + r( u l ). P G gen. Step 6. j j j j,(p gen +C gen +L gen +G gen ) n 7% P gen+,(p gen +C gen +L gen +G gen ), n n 7% P gen+. Step 7. :,, Step. 3 (HSOGA), 4 Benchmark,. f f 6 f f 4,=3, f 7 f 9,=. f f 8,, f 7!= ,,. = ( ( )) f = xsn x, 5 x 5. ( cos( ) ), = f = x π x + x

9 34 Journal of Software Vol., o.6, June f x x x 3 = π + + exp. exp cos( ) exp(), 3 3. = = x f4 = x cos +, 6 x 6. 4 = = π f = { sn ( π y ) + ( y ) + sn ( π y ) + + ( y ) } + u( x,,,4 ), 5. x = = 4, y = + ( x + ), ( ) ( ) m k x a, x > a u x, a, k, m =, a x a. m k( x a), x < a f6 = sn ( 3 π x) + ( x ) sn ( 3 x ) ( x ) sn ( x) + u( x,5,,4 ), 5 x 5. + π + + π + = = x f7 = sn( x) sn, x π. = π f = x 6x + 5 x, x ( ) = ( + ) ( ) f = x x + x, 5 x. 9 j j j j= 4 = j = f = x, x. [ ) f = x + random,,.8 x.8. f = x + x, x. = = f3 = xj, x. = j= { } f4 = max x, =,,...,, x. MATLAB,, n=,q =,Q=,S=5,P c =.6,P m =., δ =.5, HSOGA gen=,., 5,(),()(St. dev)., (HSOGA) OGA/Q [3] LEA [8], f 5 f 9,. f 7 5, x* f 7 (x*)= 99.68,x* 3,[3,8 ] ,. OGA/Q,HSOGA f, f f, f, f, f OGA/Q, f, f, f f 4,HSOGA OGA/Q. f 6,f 7,HSOGA OGA/Q, OGA/Q. LEA,HSOGA f f, f f, f f LEA. f 7, HSOGA LEA, LEA, f 4,HSOGA LEA..

10 : 35, (HSOGA),,. HSOGA, SOC HSOGA HGA, f,f 6,f 7 HSOGA HGA. : HSOGA, n=,q =,Q=,S=5,P c =.6,P m =.,δ =.5, ; HSOGA,HGA Q,δ, HSOGA., 5,(best),(medan)(worst) ()(). 3 HSOGA HGA. Table Comparson of three algorthms (OGA/Q [3],LEA [8], and HSOGA) on 4 benchmark functons 3(OGA/Q [3],LEA [8],HSOGA) 4. Functon/ optmal F / F / f 3 / f 4 / f 5 / f 6 / f 7 / f 8 / f 9 / f / f / f / f 3 / f 4 / Status Algorthm OGA/Q LEA HSOGA

11 36 Journal of Software Vol., o.6, June Table The optmal soluton x* of f 7 found by HSOGA HSOGA f 7 x* x* =( , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ), f 7 (x*)= Table 3 Comparson of two algorthms (HSOGA and HGA) on functons f, f 6, and f 7 3 (HSOGA,HGA) f,f 6,f 7 Functon/optmal Method Best Medan Worst f / HSOGA HGA f 6 / HSOGA HGA f 7 / HSOGA HGA ,,HSOGA f HGA ; f 6,f 7,HSOGA 5 HGA., HSOGA HGA,SOC HSOGA. 4,.:,,,,.,,,.. References: [] Chen GL, Wang XF, Zhuang ZQ, Wang DS. Genetc Algorthm and Its Applcatons. Bejng: People s Post & Telecommuncatons Publshng House, 996 (n Chnese). [] Zhang Q, Leung YW. An orthogonal genetc algorthm for multmeda multcast routng. IEEE Trans. on Evolutonary Computaton, 999,3():53 6. [do:.9/ ] [3] Leung YW, Wang YP. An orthogonal genetc algorthm wth quantzaton for global numercal optmzaton. IEEE Trans. on Evolutonary Computaton,,5():4 53. [do:.9/ ] [4] Zeng SY, We W, Kang LS, Yao SZ. A mult-objectve evolutonary algorthm based on orthogonal desgn. Chnese Journal of Computers, 5,8(7):53 6 (n Chnese wth Englsh abstract). [5] Wang Y, Lu H, Ca Z, Zhou Y. An orthogonal desgn based constraned evolutonary optmzaton algorthm. Engneerng Optmzaton, 7,39(6): [do:.8/ ]

12 : 37 [6] Tsutsu S, Yamamura M, Hguch T. Mult-Parent recombnaton wth smplex crossover n real-coded genetc algorthms. In: Proc. of the Genetc and Evolutonary Computaton Conf [7] Ca ZX, Wang Y. A multobjectve optmzaton-based evolutonary algorthm for constraned optmzaton. IEEE Trans. on Evolutonary Computaton, 6,(6): [do:.9/tevc ] [8] Wang YP, Dang CY. An evolutonary algorthm for global optmzaton based on level-set evoluton and Latn squares. IEEE Trans. on Evolutonary Computaton, 7,(5): [do:.9/tevc ] [9] Tsa JT, Lu TK, Chou J H. Hybrd Taguch-genetc algorthm for global numercal optmzaton. IEEE Trans. on Evolutonary Computaton, 4,8(4): [do:.9/tevc ] [] Zhang Q, Sun J, Tsang E, Ford J. Hybrd estmaton of dstrbuton algorthm for global optmzaton. Engneerng Computatons, 4,():9 7. [do:.8/ ] [] Guo GQ, Yu SY, He SL. Theoretc analyss and acceleratng of a class of self-adaptve nchng genetc algorthms. Chnese Journal of Computers, 3,6(6): (n Chnese wth Englsh abstract). [],,,..:,996. [4],,,..,5,8(7):53 6. [],,..,3,6(6): (98 ),,,, (98),,,,,,,,.. (938),,,,CCF,,,.

201515

201515 ,() Computer Engneerng and Applcatons 计算机工程与应用多智能体布谷鸟算法的网络计划资源均衡优化宋玉坚, 叶春明,, 黄佐钘 SONG Yujan, YE Chunmng, HUANG Zuoxng,. 上海理工大学管理学院, 上海. 上海期货交易所, 上海.Bussness