16) 12) 14) 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

Size: px

Start display at page:

Download "16) 12) 14) 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"

こごろういさし
5 years ago
Views:

1 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) ) 10) Dept. of Computer Science, National Defense Academy of Japan, Yokosuka, Hashirimizu , Japan 1 c 2009 Information Processing Society of Japan

2 16) 12) 14) 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 D = 0 d d 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

3 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 λ ),17) n G G 3 c 2009 Information Processing Society of Japan

4 α(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 / n C 2 G (18) c 2009 Information Processing Society of Japan

5 λ 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 p p 1 p 5 c 2009 Information Processing Society of Japan

6 5 7. (Optimized) c 2009 Information Processing Society of Japan

7 9 10 Q 2 Q(condition number) Q 8 Q(condition number) Q Q 11 2 Q 7 c 2009 Information Processing Society of Japan

8 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 = p = p = p 8 c 2009 Information Processing Society of Japan

9 ) 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), ) BOLLOBAS,B. Random graphs, Cambridge Univ Pr (2001). 4) BUCK,J.and BUCK,E. Synchronous fireflies, Scientific American, 234 (1976), ) 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), ) 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), ) NEDA,Z., RAVASZ,E., BRECHET,Y., VICSEK,T.and BARABASI,A.L. The sound of many hands clapping, Nature, 403 (2000), ) 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), ) 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), ) STROGATZ, S. H. From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators, Phys. D, 143, 1-4 (2000), ) STROGATZ,S.H. Exploring complex networks., Nature, 410, 6825 (March 2001), ) WATTS,D.J.and STROGATZ,S.H. Collective dynamics of small-world networks., Nature, 393, 6684 (1998), c 2009 Information Processing Society of Japan

k = The Last Samurai Tom Cruise [1] Oracle Ken Watanabe (I) has a Bacon number of 2. 1: 6(k 6) (small world p

k = The Last Samurai Tom Cruise [1] Oracle Ken Watanabe (I) has a Bacon number of 2. 1: 6(k 6) (small world p The size of the world It is a small world Araseki Hitoshi Can you believe that everyone is at most six steps away from any other person on the Earth? This phenomenon, which is called small world phenomenon,