On Mutual Relations amongst Evolutionary Algorithm Dynamics and Its Hidden Complex Network Structures: An Overview and Recent Advances

1. Introduction

In this chapter synthesis of two partially different areas of research is done: complex networks and evolutionary algorithms dynamics. The possibility to convert evolutionary dynamics of various evolutionary algorithms into complex network structure is discussed in this chapter (the case study on differential evolution is done in the next chapter), as well as possibilities of its analysis (via complex networks math. tools) and control. Ideas, results and methodologies reported and mentioned here are based on our previous results and experiments that are fully reported here for detailed study in case of reader's interest. Therefore this chapter is proposed as an overview-survey of this research. We report here our latest results as well as propositions on further research that is in process in our group (http://navy.cs.vsb.cz/).

It is clear that topic discussed here is a fusion of two significantly distinct areas, thus for better understanding of evolutionary algorithms and dynamics it is recommended to read Zelinka I. et.al. 2010. In order to understand what the main idea is, let’s first discuss an overview of the two contributing areas: complex networks and evolutionary algorithms. Because this book is devoted to complex networks, we will focus more attention on evolutionary algorithms.

Large-scale networks, exhibiting complex patterns of interaction amongst vertices exist in both nature and in man-made systems (i.e., communication networks, genetic pathways, ecological or economical networks, social networks, networks of various scientific collaboration, Internet, World Wide Web, power grid etc.). The structure of complex networks thus can be observed in many systems. The title “complex networks” (Dorogovtsev S. N., 2002; Boccaletti S., et. al., 2006) comes from the fact that they exhibit substantial and non-trivial topological features with patterns of connection between vertices that are neither purely regular nor purely random. Such features include a heavy tail in the degree distribution, a high clustering coefficient and hierarchical structure, amongst other features. In the case of directed networks, these features also include reciprocity, triad significance profile and other features. Amongst many studies, two well-known and much studied classes of complex networks are the scale-free networks and small-world networks (see examples in Figure 1 and Figure 2), whose discovery and definition are vitally important in the scope of this research. Specific structural features can be observed in both classes i.e. so called power-law degree distributions for the scale-free networks and short path lengths with high clustering for the small world networks. Research in the field of complex networks has joined together researchers from many areas, which were outside of this interdisciplinary research in the past like mathematics, physics, biology, chemistry computer science, epidemiology etc. Complex networks, in general, are exhibiting complex patterns of interaction amongst vertices exist in both nature and man-made systems (i.e., communication networks, genetic pathways, ecological or economical networks, social networks, networks of various scientific collaboration etc.) and are a part of our daily life.

Figure 1.

Example of a complex network

Figure 2.

Another example of complex network with edges and self-loops visualized in a different way; color of vertices represents level of InDegree/OutDegree and self-loops are red.

For more recent details about research on complex networks and its applications it is recommended to read for example (Broom M., et. al. 2010; Barrat A., et. al. 2008).