Research On Metaheuristic Algorithm And Metaheuristic Algorithm For Network Disintegration

Metaheuristic algorithms are widely used in engineering design,optimization decision making,smart home,express delivery,aerospace,biomedical and other fields due to their excellent global search capability,strong self-adaptability and easy implementation.Initialization is a crucial step of the metaheuristic algorithm,which seriously affects the convergence speed and solution accuracy of the algorithm.However,there has been a lack of systematic in-depth research on algorithm initialization.In addition,the robustness of complex networks plays a vital role for many infrastructures and societal functionalities,including the smooth supply of energy,water,food and materials,smart city planning,epidemic control,environmental protection,etc.Identifying the key nodes in the network that maintain the network's structure and performance is essential for protecting beneficial networks and dismantling harmful networks.Finding the minimum set of key nodes is an NP-hard problem.Although there have been a lot of studies,the existing methods still have many limitations:they do not optimize the problem globally,ignore the cascading of nodes and combination effects,etc.Therefore,this thesis will systematically study the effect of initialization on the algorithm and solve the network disintegration problem using metaheuristic algorithms.The innovative results of this paper are as follows:1.This thesis presents a systematic comparison of many different initialization methods on the performance of three optimizers:differential evolution(DE),particle swarm optimization(PSO),and cuckoo search(CS).We have used a large number of test functions with different properties and modalities to compare the possible effects of initialization,population sizes and the numbers of iterations.Rigorous statistical ranking tests indicate that DE is less sensitive to initialization,while both PSO and CS are more sensitive to initialization.The most commonly used initialization methods:random method,uniform distribution,Latin hypercube sampling,etc.are not the most efficient methods,and some probability distributions such as the Beta distribution,exponential distribution and Rayleigh distribution can usually lead to better performance.In addition,the population size can also have a significant impact on the performance of the algorithm.PSO usually requires a larger population,while CS needs only a small population size.DE depends more heavily on the number of iterations,a relatively small population with more iterations can lead to better results.2.A metaheuristic algorithm:neighborhood information-based probabilistic evolutionary algorithm(NIPA),is proposed to find the optimal set of key nodes in the network that maintains the network's structure and performance.By defining a new Vulnerability Measure(VM)which can better reflect the criticality of nodes in the network disintegration problem.Considering the interdependence and combinatorial effects between nodes in networks,the reservation mechanism is designed to pass useful combination information to the next generation.NIPA has been tested for different network benchmarks and experiments suggest that NIPA is very effective.In general,NIPA can identify the most crucial nodes with higher effectiveness,and the set of optimal key nodes found by our proposed NIPA is much smaller than that by heuristic centrality prediction.In addition,many previously neglected weakly connected nodes are identified.3.Most previous researches are based on an implicit assumption that the cost of attacking any one node is equivalent regardless of the connectivity of the node.In this thesis,Based on a more reasonable assumption:the removal cost is a function of the degree of the node,the network disintegration problem with heterogeneous cost is transformed into a multi-objective problem,and an elitism based multi-objective evolutionary algorithm(MOEEA)is proposed.By combining cost and node importance,a new unit cost vulnerability measure is defined.An elitism strategy is used to guide the population to move to more potential areas,thereby improving the convergence speed of the algorithm,and designing an ingenious update mechanism to achieve the dynamic balance of the algorithm's global search and local search.As a multi-objective algorithm,MOEEA can obtain a set of Pareto optimal solutions and provide more choices for decision makers.A series of experiments were carried out on some actual networks and some model networks,the results show that our method is better than some state-of-the-art attack strategies.MOEEA can usually find a low-cost network decomposition solution.At the same time,through testing different cost functions,we find that the stronger the cost heterogeneity,the more outstanding the performance of our algorithm is.