Study On Invulnerability Optimization And Application Of Complex Network Based On PSO Algorithm

Because of the profound application background, more attention has been paid to thestudy of invulnerability for complex networks, and it has become a challenging frontierresearch subject. Combined with complex network theory，PSO algorithm and knowledgefrom multiple fields including graph theory, statistical physics, matrix theory and computersimulation technology, this dissertation focuses on topological invulnerability optimization ofcomplex network and its application to engineering network, such as multi-robot network andtrain-scheduling network. The main results and contributions of this dissertation are asfollows:(1) Aiming at the optimization problem of topology invulnerability of complex network,an optimal algorithm based on adding combined edges is proposed in this paper. Firstly, thecandidate edge set is reflected into a continuous space of integers. And then a DirectedChaos-mutation Sorted Discrete Particle Swarm Optimization (DCSD-PSO) algorithm isproposed to search the optimal solution in integer space by using the Algebraic Connectivityas measure, in which three characteristics are as follows:1) the alposition average mechanismis proposed to initiate the position variable and velocity variable of particles;2) the sortedmechanism is proposed to make the position relationship between ordinary particles andoptimal particle be consistent, and so the search range in every dimension is reduced while theglobal search is guaranteed;3) the directed chaos-mutation operator enlarge the search abilityon local range, in which the directed mechanism make the ordinary particle approach optimalparticle rapidly and is used to balance the ability of local search and global search bycombining with the randomness and ergodicity property of chaos-mutation. Finally, comparedwith Bisection Algorithm in solving optimization problem of topology connectivity ofcomplex network, the simulation results prove the advantages and feasibility of the proposedalgorithms.(2) The optimizing path planning of multi-robot system is investigated in unweightednetwork model, which makes use of the PSO algorithm to search the next path planning targetnode and gets the algebraic connectivity as the invulnerability of the multi-robot localnetwork topologies. This node can make the local network get a better invulnerability, and itwill be taken as the optimizing path planning end point. Then, aiming at the limited space environment of the multi-robot system, an optimal path planning algorithm based on adaptiveregional grid is presented. Firstly, the algorithm relative to the center axis constituted bybeginning point and end point and through the shape heart of the obstacles’ vertical projectionmake orthogonal parallel linear cluster, which divide the environment into regional grid, andput forward a concept of block degree to reduce the search space dimension to optimize theregional grid’s division. Secondly, an adaptive multidimensional variation of particle swarmoptimization algorithm is proposed, which implement random mutation in the horizontal axisdimension of reconstructed coordinates that can effectively balance the efficiency with theprecision in search of the optimal solution in complex environment combined with thedirectional variation of the longitudinal axis dimension. At the same time, in order to furtherimprove the ability of jumping local optimum in complex environment, a random disturbanceis added to the speed update formula of particle swarm optimization. Then a method based onleast-squares curve fitting is proposed to smooth the optimal solution path and performcollision detection. Finally, by comparison with the classical NDW-PSO and the frontierC-PSO optimization planning algorithm, the simulation result prove the feasibility and theadvanced of this method.(3) In order to reduce the number of the train affected by the railway breakdown becauseof disasters as possible as, a quantitative analysis method on invulnerability optimization fortrain scheduling scheme is proposed in this paper. Firstly, train scheduling network model isproposed based on present train scheduling scheme, in which the real railway station isdescribed as a vertex, and the railway line is described as an edge, the number of trains on therailway lines is designed as the weight of edge. Secondly a new evaluation index calleddegree and weight effect is proposed, which can be used to evaluate importance of node. Andthe standard deviation of nodes’degree and weight effect is regarded as fitness function toevaluate the invulnerability of the train scheduling network. Finally this fitness function isoptimized by using improved particle swarm optimization (PSO) algorithm, and theinvulnerability measurement value calculated results of the original scheme and the optimalscheme is0.0044and0.0036respectively which show the proportionality of the optimalscheme is better than original scheme. Simulation results show that the quantitative analysismethod can be used to measure the invulnerability of train scheduling network andcomparison of invulnerability between the original scheme and the optimal scheme withselective attack and random fault patterns are analyzed, which get the original scheme and theoptimal scheme percentage of the affected train number in the total train number of the trainscheduling network is71.2and62.6respectively under the selective attack, and simulationsshow that the original train scheduling network is easier to paralyze under random fault.