A memetic algorithm to optimize critical diameter

Diameter is an important index measuring the connectivity and the transfer efficiency of networks. In the process of minimizing APL (Average Path Length) by adding edges, a fact was found that APL begins to linearly decline after the number of added edges increases to a turning point, which also leads the network diameter decreases to 2. At this point, the state of network was defined as a critical state. Furthermore, we put forward the new concept of critical diameter and explore its properties. Memetic algorithm which combines the advantages of both genetic algorithm and local search has shown good performance in solving combinational explosion problems. The experimental results showed that an efficient transformation to critical diameter can be achieved by applying the memetic algorithm which proposed in this paper.