Patent ID: 11886786
Assignee: FUZHOU UNIVERSITY
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 7:
8. The two-step X-architecture Steiner minimum tree construction method according to claim 1, wherein the particle update formula in S13 is specifically as follows:
to enable the particle swarm optimization algorithm to better solve a discretization problem, namely to construct the XSMT, mutation and crossover operators are introduced; the particles follow the following update formula:

Xit=F3(F2(F1(Xit−1,w),c1),c2)  (5)

wherein, w is an inertia weight factor which determines the probability of particle mutation; c1 and c2 are acceleration factors which determine the probabilities of particle crossovers; F1 is a mutation operation and represents an inertia component; F2 and F3 are crossover operations and represent the components of individual cognition and social cognition of the particles respectively; a specific update process is as follows:
the inertia component:
the algorithm completes velocity update of the particles through F1, which is expressed as follows:, W
      i
      t
     
     =
     
      
       
        F
        1
       
       (
       
        
         X
         i
         
          t
          -
          1
         
        
        ,
        w
       
       )
      
      =
      
       {
       
        
         
          
           M
           ⁡
           (
           
            X
            i
            
             t
             -
             1
            
           
           )
          
         
         
          
           
            r
            1
           
           <
           w
          
         
        
        
         
          
           
            X
            i
            
             t
             -
             1
            
           
           ,
          
         
         
          otherwise
         
        
       
      
     
    
   
   
    
     (
     6
     )
    
   
  
 

wherein, w determines the probability of the mutation operation of the particles and follows the chaotic decreasing formula (4), and r1 is a random number within [0, 1];
The mutation operation is specifically as follows: a two-point mutation is adopted; if the random number generated meets r1<w, the particle swarm optimization algorithm selects two edges randomly and changes selections of the two edges: or, if the random number generated meets r1≥w, the routing tree remains unchanged;
the individual cognition component:
the algorithm completes individual cognition through F2, which is expressed as follows:, S
      i
      t
     
     =
     
      
       
        F
        2
       
       (
       
        
         W
         i
         t
        
        ,
        
         c
         1
        
       
       )
      
      =
      
       {
       
        
         
          
           
            
             C
             p
            
            (
            
             W
             i
             t
            
            )
           
           ,
          
         
         
          
           
            r
            2
           
           <
           
            c
            1
           
          
         
        
        
         
          
           
            W
            i
            t
           
           ,
          
         
         
          otherwise
         
        
       
      
     
    
   
   
    
     (
     7
     )
    
   
  
 

wherein, c1 determines the probability that each particle crosses with its individual historical optimum (XiP), and r2 is a random number within [0, 1]; the individual cognition component reflects a self-experience learning process of the particles;
the social cognition component:
the algorithm completes social cognition of the particles through F3, which is expressed as follows:, X
      i
      t
     
     =
     
      
       
        F
        3
       
       (
       
        
         S
         i
         t
        
        ,
        
         c
         2
        
       
       )
      
      =
      
       {
       
        
         
          
           
            
             C
             p
            
            (
            
             S
             i
             t
            
            )
           
           ,
          
         
         
          
           
            r
            3
           
           <
           
            c
            2
           
          
         
        
        
         
          
           
            S
            i
            t
           
           ,
          
         
         
          otherwise
         
        
       
      
     
    
   
   
    
     (
     8
     )
    
   
  
 

wherein, c2 determines the probability that each particle crosses with the historical optimum (XkP) of any particle in the example pool, and r3 is a random number within [0, 1]; the social cognition component reflects information sharing and exchange between the particles;
the crossovers in formulas (7, 8) are as follows: when the random number generated meets r2<c1 (or r3<c2), the crossover F2 (or F3) is performed, and for a Steiner tree comprising n pins: the particle swarm optimization algorithm randomly generates a continuous interval [Cstart,Cend] in which the crossover is to be performed, and Cstart and Cend are random integers within [1, n−1]; then, a code of a learning object (XiP or XkP) of the particle Xi within an interval [3×Cstart,3×Cend] is found; finally, the numeral of the Xi within the interval is replaced by the code of the learning object in the interval; through the crossover, the particle Xi is able to learn part of genes from better particles and approaches a global optimal position gradually by repeated iterative learning; and it is set that the acceleration factor c1 adopts a linearly decreasing strategy and c2 adopts a linearly increasing strategy.