1 1, 2 Evolutionary Optimized Synchronization Networks TOSHIHIKO YAMAMOTO 1 and AKIRA NAMATAME 1 Collective behavior in nature, the interaction between agents and factors, there is consensus problem as an important characteristic for coordinated control problem. Consensus problem is closely related to the complex networks. Recently, many studies are being considered in the complex network structure, the question what network is most suitable to the property of the purpose has not been answered yet in many areas. In the previous study, network model has been created under the regular rules, and investigate their characteristics. But in this study, network is evolved to suit the characteristics of the objection by evolutionary algorithm and create optimized network. As a function of the adaptive optimization, we consider the objection that combinate consensus, synchronization index and the density of the link, and create the optimized network which is suitable to the property of the objective function by evolutionary algorithms. As a result, we generate optimal consensus and synchronous network. 1. 6) 18) 1) 2. 2. 4) 10) 1 239-8686 1-10-20 Dept. of Computer Science, National Defense Academy of Japan, Yokosuka, Hashirimizu 1-10-20, Japan 1 c 2009 Information Processing Society of Japan
16) 12) 14) 2.1 2.2 n x i, (1 i < n) x 1 = x 2 = = x n. (6) L = D A (1) D = diag(d 1,d 2,,d n ) n n A d i = j i a i j 9) 0 a 12 a 13 a 14 A = a 21 0 a 23 a 24 a 31 a 32 0 a 34 a 41 a 42 a 43 0 d 1 0 0 0 D = 0 d 2 0 0 0 0 d 3 0 0 0 0 d 4 d i = { i a i j if i = j 0 if i j d 1 a 12 a 13 a 14 L = D A = a 21 d 2 a 23 a 24 a 31 a 32 d 3 a 34 a 41 a 42 a 43 d 4 0 = λ 1 λ 2 λ n. (5) 2 λ 2 λ n (2) (3) (4) x i = α1, 1 i n. (7) 1 [1,,1], α collective decision( ) ẋ i = u i, 1 i n. (8) x i R (state) u i R (input) G = (V,E) G A = [a i j ] (neighbors) N i { j V : a i j 0 }. (9) ( ) j i i j ( ) V = {1,,n} E = {(i, j) V V } G = (V,E) A = [a i j ] ( ) ( ) ẋ i = j N i a i j ( x j (t) x i (t) ),1 i n (10) 2 c 2009 Information Processing Society of Japan
x i = α1 i ẋ i = 0 α = 1 n x i (0). (11) i collective decision( ) average consensus algorithm (10) ẋ = Lx(t) (12) ẋ i = F(x i ) σ L i j H(X i ) (13) j ( ) 2) x i (i 1,2,...,n) F H σ ẋ s = F(x s ) x s α = σλ i [α A,α B ] 2),5) Q = λ n λ 2 (15) Q(condition number) Q λ n λ 2 3. G (n) A = [a i j ] A n n 1 1 α A < σλ 2... σλ n < α B, (14) λ n λ < α B 2 α A 2 λ n λ 2 3.1 8),17) n G G 3 c 2009 Information Processing Society of Japan
α(0 < α 1) α = 1 n nc 2 a i j (16) k=1 <k> = (n 1)α = (n 1) 1 n nc 2 a i j (17) k=1 3.2 (17) A L 2 λ 2,λ n ω(0 ω 1) (18) ω = 0 ω = 1 2 λ 2,λ n Q (17) 2 E(ω) = ωq + (1 ω)<k>(0 ω 1) (18) 4. (Genetic Algorithm : GA) MGG 15) 2 p 0 p 0 7/ n C 2 2 50 0.7 2/ n C 2 G 0 1 0 (18) 2 5. 5.1 3 7 4 c 2009 Information Processing Society of Japan
5.2 4 3 2 λ 2 7),11),12). n k k/2 λ 2 λ 2 p p = 0 0 p 1 C L p p = 1 p 1 p 3) p 1 ( 4) ( 5) 2 ( 6) 5 RG SW ER RR 500 500 6 p p 1 p 5 c 2009 Information Processing Society of Japan
5 7. (Optimized) 2 9 6 5.3 7 4 6 8 6 c 2009 Information Processing Society of Japan
9 10 Q 2 Q(condition number) Q 8 Q(condition number) 10 8 6 2 10 Q 9 8 10 Q 11 2 Q 7 c 2009 Information Processing Society of Japan
12 11 5.4 Q(condition number) x i (0) = i(i = 1,2,,n) (19) n x i, (1 i < n) 2.2 x 1 = x 2 = = x n (20) 12 6 p = 0.2 2 p = 0.2 6532 p = 1 2393 p 8 c 2009 Information Processing Society of Japan
1848 1443 6. 1) ALBERT, R. and BARÁBASI, A. L. Statistical mechanics of complex networks, Reviews of Modern Physics, 74, 1 (2002). 2) BARAHONA, M. Synchronization in Small-World Systems, Physical Review Letters, 89, 5 (2002), 054101. 3) BOLLOBAS,B. Random graphs, Cambridge Univ Pr (2001). 4) BUCK,J.and BUCK,E. Synchronous fireflies, Scientific American, 234 (1976), 74 85. 5) DONETTI,L., HURTADO,P.I.and MUNOZ,M.A. Entangled networks, synchronization and optimal network topology (Oct 2005). 6) ERDŐS,P.and RÉNYI,A. On random graphs. I, Publ. Math. Debrecen, 6 (1959), 290 297. 7) HOVARESHTI, P.and BARAS, J. Consensus Problems on Small World Graphs: A structural Study, Technical report, Institute for Systems Research (Oct 2006). 8) KAUFFMAN,S.A. The Origins of Order: Self-Organization and Selection in Evolution, Oxford University Press (May 1993). 9) MERRIS, R. Laplacian graph eigenvectors, Linear Algebra and its Applications, 278, 1-3 (July 1998), 221 236. 10) NEDA,Z., RAVASZ,E., BRECHET,Y., VICSEK,T.and BARABASI,A.L. The sound of many hands clapping, Nature, 403 (2000), 849 850. 11) OLFATI-SABER, R. Ultrafast consensus in small-world networks, Proceedings Proc. of American Control Conference (2005). 12) OLFATI-SABER, R., FAX, J. A. and MURRAY, R. M. Consensus and Cooperation in Networked Multi-Agent Systems, Proceedings of the IEEE, Vol.95 (2007). 13) OLFATI-SABER, R. and MURRAY, R. M. Consensus problems in networks of agents with switching topology and time-delays, IEEE Transactions on Automatic Control, 49 (2004), 1520 1533. 14) REN, W. and BEARD, R. W. Distributed Consensus in Multi-vehicle Cooperative Control, Communications and Control Engineering, Springer-Verlag (2008). 15) SATO, H., ISAO, O.and SHIGENOBU, K. A New Generation Alternation Model of Genetic Algorithms and Its Assessment., Journal of Japanese Society for Artificial Intelligence, 12, 5 (1997), 734 744. 16) STROGATZ, S. H. From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators, Phys. D, 143, 1-4 (2000), 1 20. 17) STROGATZ,S.H. Exploring complex networks., Nature, 410, 6825 (March 2001), 268 276. 18) WATTS,D.J.and STROGATZ,S.H. Collective dynamics of small-world networks., Nature, 393, 6684 (1998), 440 442. 9 c 2009 Information Processing Society of Japan