Dual-phase evolution

DPE occurs where a system has an underlying network. That is, the system's components form a set of nodes and there are connections (edges) that join them. For example, a family tree is a network in which the nodes are people (with names) and the edges are relationships such as "mother of" or "married to". The nodes in the network can take physical form, such as atoms held together by atomic forces, or they may be dynamic states or conditions, such as positions on a chess board with moves by the players defining the edges.

In mathematical terms (graph theory), a graph ${\displaystyle \textstyle G=\langle N,E\rangle }$ is a set of nodes ${\displaystyle \textstyle N}$ and a set of edges ${\displaystyle \textstyle E\subset \{(x,y)\mid x,y\in N\}}$. Each edge ${\displaystyle \textstyle (x,y)}$ provides a link between a pair of nodes ${\displaystyle \textstyle x}$ and ${\displaystyle \textstyle y}$. A network is a graph in which values are assigned to the nodes and/or edges.

Graphs and networks have two phases: disconnected (fragmented) and connected. In the connected phase every node is connected by an edge to at least one other node and for any pair of nodes, there is at least one path (sequence of edges) joining them.

The Erdős–Rényi model shows that random graphs undergo a connectivity avalanche as the density of edges in a graph increases.[2] This avalanche amounts to a sudden phase change in the size of the largest connected subgraph. In effect, a graph has two phases: connected (most nodes are linked by pathways of interaction) and fragmented (nodes are either isolated or form small subgraphs). These are often referred to as global and local phases, respectively.

Fragmented graph.

Connected graph.

An essential feature of DPE is that the system undergoes repeated shifts between the two phases. In many cases, one phase is the system's normal state and it remains in that phase until shocked into the alternate phase by a disturbance, which may be external in origin.

In each of the two phases, the network is dominated by different processes.[1] In a local phase, the nodes behave as individuals; in the global phase, nodes are affected by interactions with other nodes. Most commonly the two processes at work can be interpreted as variation and selection. Variation refers to new features, which typically appear in one of the two phases. These features may be new nodes, new edges, or new properties of the nodes or edges. Selection here refers to ways in which the features are modified, refined, selected or removed. A simple example would be new edges being added at random in the global phase and edges being selectively removed in the local phase.

The effects of changes in one phase carry over into the other phase. This means that the processes acting in each phase can modify or refine patterns formed in the other phase. For instance, in a social network, if a person makes new acquaintances during a global phase, then some of these new social connections might survive into the local phase to become long-term friends. In this way, DPE can create effects that may be impossible if both processes act at the same time.

DPE is capable of producing social networks with known topologies, notably small-world networks and scale-free networks.[3] Small world networks, which are common in traditional societies, are a natural consequence of alternating local and global phases: new, long-distance links are formed during the global phase and existing links are reinforced (or removed) during the local phase. The advent of social media has decreased the constraining influence that space used to impose on social communication, so time has become the chief constraint for many people.

The alternation between local and global phases in social networks occurs in many different guises. Some transitions between phases occur regularly, such as the daily cycle of people moving between home and work. This alternation can influence shifts in public opinion.[4] In the absence of social interaction, the uptake of an opinion promoted by media is a Markov process. The effect of social interaction under DPE is to retard the initial uptake until the number converted reaches a critical point, after which uptake accelerates rapidly.

DPE models of socio-economics interpret the economy as networks of economic agents.[5] Several studies have examined the way socioeconomics evolve when DPE acts on different parts of the network. One model[6] interpreted society as a network of occupations with inhabitants matched to those occupations. In this model social dynamics become a process of DPE within the network, with regular transitions between a development phase, during which the network settles into an equilibrium state, and a mutating phase, during which the network is transformed in random ways by the creation of new occupations.

Another model[7] interpreted growth and decline in socioeconomic activity as a conflict between cooperators and defectors. The cooperators form networks that lead to prosperity. However, the network is unstable and invasions by defectors intermittently fragment the network, reducing prosperity, until invasions of new cooperators rebuild networks again. Thus prosperity is seen as a dual phase process of alternating highly prosperous, connected phases and unprosperous, fragmented phases.

In a forest, the landscape can be regarded as a network of sites where trees might grow.[8] Some sites are occupied by living trees; others sites are empty. In the local phase, sites free of trees are few and they are surrounded by forest, so the network of free sites is fragmented. In competition for these free sites, local seed sources have a massive advantage, and seeds from distant trees are virtually excluded.[1] Major fires (or other disturbances) clear away large tracts of land, so the network of free sites becomes connected and the landscape enters a global phase. In the global phase, competition for free sites is reduced, so the main competitive advantage is adaptation to the environment.

Most of the time a forest is in the local phase, as described above. The net effect is that established tree populations largely exclude invading species.[9] Even if a few isolated trees do find free ground, their population is prevented from expanding by established populations, even if the invaders are better adapted to the local environment. A fire in such conditions leads to an explosion of the invading population, and possibly to a sudden change in the character of the entire forest.

This dual phase process in the landscape explains the consist appearance of pollen zones in the postglacial forest history of North America, Europe, as well as the suppression of widespread taxa, such as beech and hemlock, followed by huge population explosions. Similar patterns, pollen zones truncated by fire-induced boundaries, have been recorded in most parts of the world

Dual phase evolution is a family of search algorithms that exploit phase changes in the search space to mediate between local and global search. In this way they control the way algorithms explore a search space, so they can be regarded as a family of metaheuristic methods.

Problems such as optimization can typically be interpreted as finding the tallest peak (optimum) within a search space of possibilities. The task can be approached in two ways: local search (e.g. hill climbing) involves tracing a path from point to point, and always moving "uphill". Global search involves sampling at wide-ranging points in the search space to find high points.

Many search algorithms involve a transition between phases of global search and local search.[3] A simple example is the Great Deluge algorithm in which the searcher can move at random across the landscape, but cannot enter low-lying areas that are flooded. At first the searcher can wander freely, but rising water levels eventually confine the search to a local area. Many other nature-inspired algorithms adopt similar approaches. Simulated annealing achieves a transition between phases via its cooling schedule. The cellular genetic algorithm places solutions in a pseudo landscape in which they breed only with local neighbours. Intermittent disasters clear patches, flipping the system into a global phase until gaps are filled again.

Some variations on the memetic algorithm involve alternating between selection at different levels. These are related to the Baldwin effect, which arises when processes acting on phenotypes (e.g. learning) influence selection at the level of genotypes. In this sense, the Baldwin effect alternates between global search (genotypes) and local search (phenotypes).