Dual-phase evolution

Dual phase evolution (DPE) is a process that drives self-organization within complex adaptive systems.
It arises in response to phase changes within the network of connections formed by a system's components. DPE occurs in a wide range of physical, biological and social systems. Its applications to technology include methods for manufacturing novel materials and algorithms to solve complex problems in computation.

Introduction

Dual phase evolution (DPE) is a process that promotes the emergence of large-scale order in complex systems. It occurs when a system repeatedly switches between various kinds of phases, and in each phase different processes act on the components or connections in the system. DPE arises because of a property of graphs and networks: the connectivity avalanche that occurs in graphs as the number of edges increases.

Social networks provide a familiar example. In a social network the nodes of the network are people and the network connections (edges) are relationships or interactions between people. For any individual, social activity alternates between a ''local phase'', in which they interact only with people they already know, and a ''global phase'' in which they can interact with a wide pool of people not previously known to them. Historically, these phases have been forced on people by constraints of time and space. People spend most of their time in a local phase and interact only with those immediately around them (family, neighbors, colleagues). However, intermittent activities such as parties, holidays, and conferences involve a shift into a global phase where they can interact with different people they do not know. Different processes dominate each phase. Essentially, people make new social links when in the global phase, and refine or break them (by ceasing contact) while in the local phase.

The DPE mechanism

The following features are necessary for DPE to occur.

Underlying network

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 $\textstyle G = \langle N,E\rangle$ is a set of nodes $\textstyle N$ and a set of edges $\textstyle E \subset \$. Each edge $\textstyle (x,y )$ provides a link between a pair of nodes $\textstyle x$ and $\textstyle y$. A network is a graph in which values are assigned to the nodes and/or edges.

Phase shifts

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.
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.

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.

Selection and variation

In each of the two phases, the network is dominated by different processes. 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.

System memory

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.

Examples

DPE has been found to occur in many natural and artificial systems.

Social networks

DPE is capable of producing social networks with known topologies, notably small-world networks and scale-free networks.
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.
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.

Socio-economics

DPE models of socio-economics interpret the economy as networks of economic agents.
Several studies have examined the way socioeconomics evolve when DPE acts on different parts of the network. One model
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
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.

Ecology

In a forest, the landscape can be regarded as a network of sites where trees might grow. 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. 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. 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 consistent 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-phases also occur in the course of foraging by animals.
Many species (e.g. ants) exhibit two modes of foraging:
exploration and
exploitation.

In ant colonies, for instance, individuals search at random (exploration) until food is found. They lay pheromone trails to the source. Other ants follow these trails, switching their behaviour from searching to gathering (exploitation).

Search algorithms

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. 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).

Related processes

Dual phase evolution is related to the well-known phenomenon of '' self-organized criticality'' (SOC). Both concern processes in which critical phase changes promote adaptation and organization within a system. However, SOC differs from DPE in several fundamental ways. Under SOC, a system's natural condition is to be in a critical state; in DPE a system's natural condition is a non-critical state. In SOC the size of disturbances follows a power law; in DPE disturbances are not necessarily distributed the same way. In SOC a system is not necessarily subject to other processes; in DPE different processes (e.g. selection and variation) operate in the two phases.

References

{{reflist

Nature-inspired metaheuristics