Research On Differential Evolution For Constrained Optimization Problems And Community Detection In Complex Networks

In the fields of science and engineering, there exist a great number of constrained optimization problems (COPs). Since COPs usually include various kinds of non-linear constraints, multi-model objective functions and concave feasible regions, solving COPs is very difficult and the research on solving COPs is very important in both theory and practice. Moreover, the complex systems widely exist in the real world and are usually transformed into the complex networks. However, the complex networks commonly have a large number of nodes and very complex topological structures which has impeded the research and analysis on complex networks. The complex networks generally have significant community structures. Research on the community detection in complex networks is very useful for the analysis of the structures and functions of complex networks. In addition, the differential evolution (DE) has drawn lots of attention and been widely applied to many domains in recent years.This thesis aims at solving COPs and the community detection in complex networks based on DE, the main contributions of which can be summarized as follows.1. The (μ+λ)-constrained differential evolution ((μ+λ)-CDE) is a DE based constrained optimization evolutionary algorithm which has been proposed recently, and has very excellent performance for solving COPs. However, in (μ+λ)-CDE the tolerance value for equality constraints should be changed dynamically. Moreover, both the initial value and the change rate of the tolerance value are problem-dependent. To overcome the above drawbacks of (μ+λ)-CDE, this thesis proposes an improved version of (μ+λ)-CDE, named ICDE, to solve COPs. ICDE mainly consists of an improved (μ+λ)-differential evolution (IDE) and a novel archiving-based adaptive tradeoff model (ArATM). Therein, IDE employs several mutation strategies and the binomial crossover of DE to generate the offspring population. Since the population may undergo three different situations (i.e., the infeasible situation, the semi-feasible situation, and the feasible situation) during the evolution, ArATM designs one constraint-handling mechanism for each situation. In the constraint-handling mechanism of the infeasible situation, ArATM adopts a hierarchical non-dominated individual selection scheme and an individual archiving technique to maintain the diversity of the population. Moreover, in the constraint-handling mechanism of the semi-feasible situation, ArATM uses an adaptive fitness transformation mechanism based on the feasibility proportion of the combined population to effectively handle the constraints. The performance of ICDE has been tested on24well-known benchmark test functions collected for the special session on constrained real-parameter optimization of the2006IEEE Congress on Evolutionary Computation (IEEE CEC2006). The experimental results demonstrate that ICDE not only overcomes the above drawbacks of (μ+λ)-CDE but also obtains very competitive performance compared with other state-of-the-art methods in the community of constrained evolutionary optimization.2. For the community detection in complex networks, this thesis proposes a new algorithm named Differential Evolution based Community Detection (DECD). DECD employs DE as the search engine and uses the network modularity as the fitness function to search for an optimal community partition of a network. Moreover, DECD designs a modified binomial crossover to effectively transmit some important information about the community structure in evolution. In addition, a biased process and a clean-up operation are employed in DECD to improve the quality of the community partitions detected in evolution. It is noteworthy that, unlike those traditional community detection algorithms, DECD does not require any prior knowledge about the community structure, which is particularly useful for its application to real-world complex networks where prior knowledge is usually not available. Finally, based on several artificial and real-world networks, we evaluate DECD and compare it with many other community detection algorithms. Experimental results show that DECD has very competitive performance compared with other state-of-the-art community detection algorithms.