Distributed Multi-objective Evolutionary Algorithm In Community Detection And Change Detection

As a research result of mutual combination and inspiration of various disciplines,the multi-objective evolutionary algorithm has been developed into a comprehensive technique with self-organization and self-adaptation.Since the objective function is not required to have a clear analytic expression,the multi-objective evolutionary algorithm can provide a general framework for solving optimization problems of complex systems.Although the theoretical derivation is not as perfect as the traditional optimization algorithm,the multi-objective evolutionary algorithm has strong robustness for different kinds of optimization problems.It can be applied in a wide range of fields and has been successfully applied in computer science,management science,social science,engineering technology and other fields.A large number of engineering or scientific research problems in the real world can be modeled as multi-objective optimization problems.The optimal solution is obtained by maximizing or minimizing a set of objective functions.Compared with the single-objective optimization method,the multi-objective optimization method can balance multiple conflicting objective functions and improve the accuracy of community detection and the performance of change detection in multi-temporal SAR images.Although a large number of multi-objective optimization methods have been developed to solve these two types of problems,it is still necessary to conduct in-depth research on the establishment of objective functions and the selection of optimization method,so as to further improve the accuracy of the algorithm.At the same time,in this era of explosive data growth,multi-objective optimization technology often faces the problem of big data processing.For example,for the community detection problem in large-scale networks,the number of nodes in the network may vary from tens of thousands to millions.In this case,the computer needs to have tremendous computing power to deal with the multi-objective optimization problem.In the face of massive data,the centralized computing method is obviously inadequate.The method may require too long processing time,or even cannot be implemented.The distributed computing technology based on computer clusters has significantly improved the performance of using evolutionary algorithms to deal with such multi-objective optimization problems.It is worth mentioning that due to the natural parallel property in evolutionary algorithm,the parallelization can be achieved via distributed computing technology.This thesis studies the application of multi-objective evolutionary algorithm in community detection problem in large scale complex networks and change detection problem in multi-temporal SAR images.This paper model these two problems into multi-objective optimization problems.Based on the characteristics of the problem and the evolutionary algorithm,efficient multi-objective evolutionary algorithms are designed to solve the simulated optimization problems.When solving the community detection problem in large-scale complex networks,Apache Spark,which is a cluster computing platform,is used to implement the distributed algorithm.The research work carried out in this paper are as follows:(1)The distributed multi-objective evolutionary algorithm for community detection is studied in large-scale complex networks.For the community detection problem in very large scale complex networks,the traditional community detection algorithm is often inadequate.Based on Apache Spark,this paper proposes a distributed multi-objective evolutionary algorithm for community detection in large-scale networks.Combined with the characteristics of the Apache Spark platform,this paper designs a distributed population structure based on the resilient distributed dataset(RDD).The proposed distributed multi-objective community detection algorithm optimizes a group of evolutionary populations,which evolve with different genetic parameters.Besides,an external repository is set up to store as the elite individuals.Moreover,the genetic operator and evolutionary strategy in the evolutionary algorithm are improved to deal with the large-scale community detection problem and the distributed framework.(2)The discrete particle swarm optimization(PSO)algorithm based on the RDD is studied for community detection in large-scale complex networks.With the deep study of community detection in large-scale networks and distributed evolutionary algorithms,we find that there are few interactions between particles in the PSO algorithm and the algorithm structure is suitable for parallel processing.Therefore,this paper further proposes a community detection method based on distributed discrete PSO.The community detection problem is modeled as a multi-objective optimization problem,but the objective functions are adjusted via the characteristics of the PSO algorithm.Since community detection is a discrete optimization problem,this paper designs an effective discrete particle representation method and proposes the corresponding update strategy.Specifically,the population design is based on the RDD and the distributed algorithm is implemented on the Apache Spark computing platform.(3)The discrete particle swarm optimization(PSO)algorithm based on the resilient distributed property graph(RDPG)is studied for community detection in large-scale complex networks.To further improve the execution efficiency of the proposed distributed discrete PSO algorithm,this paper introduces the RDPG into the previous work.The large-scale network data are translated into distributed graph and are stored in a distributed file system.In this way,a new distributed population structure can be achieved.Due to change of the population structure and the data storage mode,the method of calculating objective functions is switched from the traditional matrix method to the message propagation method based on the concept of distributed graph.It further improves the efficiency of the proposed algorithm.(4)The application of multi-objective evolutionary algorithm in detecting positive and negative changes of SAR image is studied.In most of the existing work,the change detection problem of temporal SAR image is usually regarded as a binary classification problem,that is,the user detects if the change is happened or not.However,in many cases,the backscattering value of the multi-temporal SAR image increases or decreases,which means that the types of changes are not same.Therefore,the change detection problem in multi-temporal SAR images can be further subdivided into unchanged area detection,positive change detection and negative change detection.To detect positive and negative changes in multi-temporal SAR images,this paper proposes a new change detection method based on three objective functions and optimizes the proposed objectives using the multi-objective evolutionary algorithm.Firstly,the MR operator,the LR operator and the NR operator are modified to contain positive and negative change information.Secondly,due to the presence of the speckle noise,single validity measure does not work well to detect the positive and negative changes.The FCM measure,the XB index and the FCM based local term are used as the objective functions.Finally,the proposed method is able to obtain a set of nondominated solutions for representing the trade-off among these objectives.