ISS -985, CODE RUXUEW E-mal: jos@scas.ac.cn Journal of Software, Vol., o.6, June, pp.96 37 http://www.jos.org.cn do:.374/sp.j...359 Tel/Fax: +86--656563 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: ywang@csu.edu.cn Jang ZY, Ca ZX, Wang Y. Hybrd self-adaptve orthogonal genetc algorthm for solvng global optmzaton problems. Journal of Software,,(6):96 37. http://www.jos.org.cn/-985/359.htm 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.85335 ( ); 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.373-743346 ( ) Receved 8-3-3; Revsed 8-8-7; Accepted 9--6
: 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.,,. 3 3 3 3 4 L9 (3 ) = 3 () 3 3 3 3 3 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 ),,,. =
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
: 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 ].
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)
: 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 :
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,.
: 33 4. 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!=9.33 57,,. = ( ( )) f = xsn x, 5 x 5. ( cos( ) ), 5. 5.. = f = x π x + x
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 5.. 5 = = 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 5. 8 4 ( ) = ( + ) ( ) 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 ] 99.78. 3 4,. OGA/Q,HSOGA f, f f, f, f, f OGA/Q, 3 5 8 9 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, 3 5 6 8 4 HSOGA LEA, LEA, f 4,HSOGA LEA..
: 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 / 569.5 F / f 3 / f 4 / f 5 / f 6 / f 7 / 99.69 f 8 / 78.3336 f 9 / f / f / f / f 3 / f 4 / Status Algorthm OGA/Q LEA HSOGA 3 6 87 365 5 569.453 7 569.454 569.486 6 6.447 4 4.83 4 3.68 5 4 7 5 96 3.74 6 3. 7 3 498 6.4 6.53 7 34 556 6.9 6.59 6 34 43.869 4.65 5 3 773-9.83.66 45 93 78.396 6.88 3 67 863.75.4 559 65 6.3 3 4.69 4 6 576 893 3 83.3 8 3.359 8 4 4.44 6 3.989 7 34 3 64.48 6.76 6 3 3.734 4.5 4 89 863-93..34 43 895 78.3 6.7 3 68 9.569.78 674 4.77 6 6.8 7 93 5.36 3 4.43 4 3 4.47 9 4.36 9 64 6.783 8 5.49 8 5.683 6 6.57 7 8 4 8 4 8 4 98 745.88.544 5 58 4.36 5 3.987 5 36 867-98.987.75 6 47 78.3333.356 7 67 374 5.94 5 4.6 4 8 4 8 4 8 4 8 4 8 4
36 Journal of Software Vol., o.6, June Table The optmal soluton x* of f 7 found by HSOGA HSOGA f 7 x* x* =(.955476538,.57796448648,.8499573476,.9358388896578,.74698689545,.5779634843437,.4544449854,.75686593378,.655774834,.57796364477,.4977883797,.6966633357,.63757369949,.577963764349,.575464487838,.6666568987,.6638793,.5779678834588,.5897584368,.647456357476,.67757973768,.57796363979,.536756578,.6349356943574,.69836698,.577967354,.54435484966,.659597637474,.597647948967,.577969937835,.5455459548466,.693886553,.5944759643859,.5779637993495,.54894567998,.565469649965,.59883448863,.577963334389,.5557875,.695867348,.589836453853538,.57796379784,.5544887839,.669859563659,.588533446,.5779636834,.5539967464775,.5377397553683,.58674357454364,.577964384375,.555344589,.549385,.585545976467,.577963737478,.556456468894,.598599767775,.5845557935,.57795754967596,.557477994377,.5967633647,.583699695586,.5779636948,.55879959957,.54658447977,.534945983,.5779635,.5593695349,.59377644733,.536694938973,.577959435599,.636385633743,.59463984873,.538846648,.5779636976,.5689989984,.5938444886,.5896896,.57796595435,.568996556,.5939548736,.58467844368,.5779448339756,.563593338,.5893865344377,.58936596,.577963798385,.5674737864,.58854586697,.57959595974376,.577963985633,.5647893754,.5877783658658,.57988385934,.5779635479,.56576439846,.587737367687,.57887386957,.577963656836,.56849346659,.58649358735), f 7 (x*)= 99.6866436 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 / 569.5 HSOGA 569.486 6 569.486 6 569.486 6 569.486 6.46 5 HGA 569.486 6 569.486 5 569.438 7 569.484 4.497 f 6 / HSOGA 5.6376 6.4987 5 7.6835 5.9735 5.546 5 HGA 6.933 6 4.773 5..43 4.76 4 f 7 / 99.69 HSOGA 98.6 5 98.46 3 97.86 98. 5.3 6 HGA 9.458 9.463 89.48 9.474 6.46 3 3,,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/435.759] [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/435.9464] [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):75 736. [do:.8/3557854]
: 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. 999. 657 664. [7] Ca ZX, Wang Y. A multobjectve optmzaton-based evolutonary algorthm for constraned optmzaton. IEEE Trans. on Evolutonary Computaton, 6,(6):658 675. [do:.9/tevc.6.87344] [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):579 595. [do:.9/tevc.6.8868] [9] Tsa JT, Lu TK, Chou J H. Hybrd Taguch-genetc algorthm for global numercal optmzaton. IEEE Trans. on Evolutonary Computaton, 4,8(4):365 377. [do:.9/tevc.4.86895] [] Zhang Q, Sun J, Tsang E, Ford J. Hybrd estmaton of dstrbuton algorthm for global optmzaton. Engneerng Computatons, 4,():9 7. [do:.8/644445864] [] 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):753 758 (n Chnese wth Englsh abstract). [],,,..:,996. [4],,,..,5,8(7):53 6. [],,..,3,6(6):753 758. (98 ),,,, (98),,,,,,,,.. (938),,,,CCF,,,.