PaperlayerView exact revision on arXiv

Source-linked AI summary

The evolutionary origins of hierarchy

Henok Mengistu, Joost Huizinga, Jean-Baptiste Mouret, Jeff Clune

arXiv:1505.06353v1cs.NE

TL;DR

The paper asks why hierarchy evolves and tests whether connection costs can promote it in networks. It reports that connection costs promote functional hierarchy and that hierarchy improves evolvability independently of modularity, while noting unresolved scope and sparsity questions.

  • Problem

    Why hierarchy evolves under natural selection remains open, and computational experiments have rarely found it emerging on its own.

    Source: Introduction · pp. 1–2

  • Method

    The study uses layered feed-forward network models to examine how connection costs relate to the evolution of hierarchy.

    Source: Introduction · p. 2, Network model and its biological… · p. 12

  • Results

    Connection costs promote functional hierarchy, and hierarchy improves evolvability even when modularity is discouraged.

    Source: Introduction · p. 2, Discussion · p. 8

  • Takeaways & Limitations

    Connection costs offer an explanation for how sufficient hierarchy can emerge before evolvability benefits can be selected for.

    Source: Introduction · p. 2, Discussion · p. 8

    The experiments cover variants of hierarchical logic problems, leaving generality across non-hierarchical problems open; sparsity may also explain some or all evolvability benefits.

    Source: Discussion · pp. 8–9

Abstract

from arXiv · show

Hierarchical organization -- the recursive composition of sub-modules -- is ubiquitous in biological networks, including neural, metabolic, ecological, and genetic regulatory networks, and in human-made systems, such as large organizations and the Internet. To date, most research on hierarchy in networks has been limited to quantifying this property. However, an open, important question in evolutionary biology is why hierarchical organization evolves in the first place. It has recently been shown that modularity evolves because of the presence of a cost for network connections. Here we investigate whether such connection costs also tend to cause a hierarchical organization of such modules. In computational simulations, we find that networks without a connection cost do not evolve to be hierarchical, even when the task has a hierarchical structure. However, with a connection cost, networks evolve to be both modular and hierarchical, and these networks exhibit higher overall performance and evolvability (i.e. faster adaptation to new environments). Additional analyses confirm that hierarchy independently improves adaptability after controlling for modularity. Overall, our results suggest that the same force--the cost of connections--promotes the evolution of both hierarchy and modularity, and that these properties are important drivers of network performance and adaptability. In addition to shedding light on the emergence of hierarchy across the many domains in which it appears, these findings will also accelerate future research into evolving more complex, intelligent computational brains in the fields of artificial intelligence and robotics.

Introduction

The section asks why hierarchy evolves and reports that connection costs promote hierarchical, modular networks and faster adaptation. It further tests whether hierarchy contributes to evolvability independently of modularity.

Results

  • Connection costs produce significantly more hierarchical and modular networks and reduce the generations needed to solve the main problem.The comparison is between performance-and-connection-cost (P&CC) and performance-alone (PA) treatments.Source: Results · p. 3, Figure 2 · p. 4
  • P&CC networks solve the problem by recursively combining subproblem solutions, whereas PA networks tend to process inputs monolithically.P&CC networks also solve significantly more subproblems than PA networks.Source: Results · pp. 3, 5, Figure 2 · p. 4
  • Subproblem solving correlates positively with hierarchy (r = 0.96) and modularity (r = 0.87).Both correlations are reported as significant.Source: Figure 3 · p. 5, Results · p. 5
  • Across three base-to-target problem experiments, P&CC networks take fewer generations to adapt and solve more target subproblems than PA networks.Evolvability is measured as generations required to solve the target problem.Source: Results · p. 5, Figure 4 · p. 6
  • Random valid networks show an association between lower connection cost and higher hierarchy, offering a structural explanation for why cost selection promotes hierarchy.These networks were neither evolved nor evaluated for performance.Source: Results · p. 6, Figure 5 · p. 7
  • When modularity is discouraged, P&CC-NonMod networks remain more hierarchical than PA networks and adapt faster, supporting an independent contribution from hierarchy.Their modularity is not significantly different from PA networks.Source: Results · p. 7, Figure 6 · p. 8
  • Across additional hierarchical Boolean-logic problems, P&CC networks are more hierarchical and modular, solve more subproblems, and evolve high-performing solutions faster.The comparison is with PA networks.Source: Results · p. 7, Figure 8 · p. 10

Discussion

  • The authors identify connection-cost selection as one likely driver of hierarchy, while noting that sparsity may explain some or all evolvability benefits and needs to be disentangled.They also leave the generality across non-hierarchical problems open.Source: Discussion · pp. 8–9

Experimental setup

The experiments used 30 independent evolutionary trials per treatment, each running for 25,000 generations with a population of 1,000. Analyses generally used each trial’s highest-performing network.

  • Each treatment comprised 30 trials, each an independent evolutionary process initialized with a different random seed.Source: Experimental setup · p. 10
  • Trials ran for 25,000 generations with a population size of 1,000.Source: Experimental setup · p. 10
  • Unless otherwise stated, analyses and visualizations used the highest-performing network per trial, with ties broken randomly.Source: Experimental setup · p. 10

Statistics

The paper used rank-sum tests for significance unless noted otherwise and reported medians with bootstrapped confidence intervals, smoothing the intervals for visual clarity.

  • Statistical significance was tested with the Mann-Whitney-Wilcoxon rank-sum test unless otherwise stated.Source: Statistics · p. 10
  • Results were reported as medians with 95% bootstrapped confidence intervals calculated from 5,000 resamples.Source: Statistics · p. 10
  • For visual clarity, confidence intervals were smoothed with a median filter of window size 101.Source: Statistics · p. 10

Evolutionary algorithm

Networks evolved using NSGA-II, with a probabilistic variant used to vary how often connection cost affected selection. The default setting was p = 1, at which the variants are identical.

  • Networks evolved with the multi-objective NSGA-II algorithm, while probabilistic NSGA-II (PNSGA) varied how often the connection-cost objective influenced selection.Source: Evolutionary algorithm · p. 11
  • In PNSGA, performance influenced selection 100% of the time, while connection cost influenced selection p percent of the time.Source: Evolutionary algorithm · p. 11
  • Preliminary tests found qualitatively similar results for p = 0.25, 0.5, and 1.0; p = 1 was chosen as the default, making PNSGA and NSGA-II identical.Source: Evolutionary algorithm · p. 11

Behavioral diversity

The algorithm promoted behavioral diversity as an independent selection objective because this technique was needed to reliably evolve functional networks. Diversity was measured by comparing networks’ binary output vectors using normalized Hamming distance.

  • Behavioral diversity was added as an independent objective, rewarding individuals whose behavior differed from others in the population.Source: Behavioral diversity · p. 11
  • The diversity objective influenced selection 100% of the time, and preliminary tests found it necessary for reliably producing functional networks in either treatment.Source: Behavioral diversity · p. 11
  • For each input, network outputs were stored as binary vectors and compared with other population members using normalized Hamming distance.Outputs greater than zero were stored as 1 and all others as 0; the normalized diversity measure ranged from 0 to 1.Source: Behavioral diversity · p. 11

Connection cost

Connection cost is measured after optimally placing hidden nodes to minimize total cost. The cost is the sum of squared connection lengths.

Connection cost

  • Connection cost is the summed squared length of all network connections after hidden nodes are optimally placed.Input and output node locations remain fixed during placement.Source: Connection cost · p. 11
  • Network nodes occupy two-dimensional Cartesian space, with hidden-node locations set by their cost-minimizing placement.Source: Connection cost · p. 11
  • Inputs lie along y = 0 and the output at (0,4), except the Fig. 8 right problem, whose output is at (0,5).Source: Connection cost · p. 11

Network model and its biological relevance

The study uses a multilayered feed-forward network model, a common systems-biology model, with the same architecture across treatments. Nodes process inputs layer by layer through a nonlinear activation function.

Network model and its biological relevance

  • The multilayered feed-forward architecture is common in systems-biology studies and is held constant across treatments.The authors note that this architecture may contribute to elevated hierarchy, but compare hierarchy levels with and without connection costs.Source: Network model and its biological… · p. 12
  • Information flows one layer at a time, and each node receives connections only from the preceding layer and sends them only to the next.Source: Network model and its biological… · p. 12
  • For the main AND-XOR-AND problem, networks use 8 input nodes, hidden layers of 4, 4, and 2 nodes, and 1 output node.Source: Network model and its biological… · p. 12
  • A node’s output applies tanh to its weighted inputs plus bias, yielding values from −1 to 1; λ is set to 20.The bias sets the input value at which output switches from negative to positive.Source: Network model and its biological… · p. 12
  • Initial networks have randomly chosen connection counts from 11 to 58, and results are qualitatively unchanged when evolution starts with sparser networks.Source: Network model and its biological… · p. 12

Mutations

The methods specify how networks mutate and how modularity and hierarchy are quantified. Hierarchy is based on differences in node influence, with influence assessed from directed reachability.

Mutations

  • Offspring copy a parent and mutate connections, node biases, or connection weights with specified probabilities and allowed-value limits.Connections have a 20% chance of addition and a 20% chance of removal; bias and weight mutations are also described.Source: Mutations · p. 12

Modularity

  • Modularity uses an approximation of Q, which compares within-module edges with their expected number in an equivalent randomly connected network.The metric also uses node degrees, the network connectivity matrix, and whether node pairs belong to the same module.Source: Modularity · pp. 12–13

Hierarchy

  • Hierarchy is measured as heterogeneity in node influence, where influence reflects the portion of the directed network reachable from a node; connection strengths are ignored.The path length between nodes is counted by outgoing connections.Source: Hierarchy · p. 13

Functional hierarchy

Functional hierarchy is estimated by measuring how many logic sub-problems are solved by parts of a network. A sub-problem counts as solved when neuron outputs separate its True and False cases across all possible inputs.

Functional hierarchy

  • Functional hierarchy is proxied by the percentage of an overall logic problem’s sub-problems solved by part of the network.Source: Functional hierarchy · p. 13
  • A neuron or same-layer neuron group solves a sub-problem when its output or summed outputs admit a threshold separating True from False for every possible input.Source: Functional hierarchy · pp. 13–14
  • Each sub-problem is counted only once, and the search stops after a solution is found.Source: Functional hierarchy · p. 14

XOR XOR

With connection costs, the highest-performing networks were more hierarchical, modular, and functionally hierarchical than networks evolved for performance alone.

  • Networks evolved with performance and connection costs were more hierarchical, modular, and functionally hierarchical than performance-alone networks.The figure shows the highest-performing networks at the end of each trial.Source: XOR XOR · p. 15
  • Networks are sorted by fitness, then hierarchy, then modularity, and nodes are colored when they solve a logic subproblem.Source: XOR XOR · p. 15
  • The comparison uses the AND-XOR-AND logic problem.Source: XOR XOR · p. 15

EQU EQU

Across several hierarchical logic problems, connection-cost networks showed greater hierarchy and modularity than performance-alone networks, and adapted faster in two additional problems. Further analyses found that hierarchy improved evolvability independently of modularity.

  • On AND-EQU-AND, end-of-run P&CC networks were more hierarchical, modular, and functionally hierarchical than PA networks.Source: EQU EQU · p. 16
  • The same qualitative pattern held on OR-XOR/EQU-EQU, whose networks had an extra hidden layer because of the more complex final logic gate.Source: EQU EQU · p. 17
  • Connection costs promoted hierarchy even when an explicit pressure favored non-modularity, producing mostly hierarchical networks with low modularity.Source: EQU EQU · p. 18
  • In the first evolvability experiment, each base-environment winner seeded 30 target-environment runs, totaling 900 replicates per treatment.Source: EQU EQU · p. 19
  • Hierarchy improved evolvability in networks that were hierarchical but non-modular, indicating an effect independent of modularity.Source: EQU EQU · p. 25
  • Hierarchy and modularity were strongly positively correlated (Pearson’s r = 0.92; p < 0.00001).Source: EQU EQU · p. 26
  • P&CC evolved high-performing networks faster than PA on AND-EQU-AND and OR-XOR/EQU-EQU.Source: EQU EQU · p. 26

PA P&CC 0.0

The authors used an evolutionary algorithm to compare network traits under different starting connectivity conditions. P&CC networks retained higher hierarchy, modularity, and subproblem-solving rates when initialized sparsely.

  • With sparse initialization, end-of-run P&CC networks had significantly higher hierarchy, modularity, and percent of subproblems solved.The authors report that the results were qualitatively unchanged; initial networks had 11–20 connections, with at least 11 needed to solve the problem.Source: PA P&CC 0.0 · p. 27
  • The study used NSGA-II, which ranks parents and offspring by Pareto dominance and selects the best N networks for the next generation.N offspring are produced by randomly mutating selected current networks.Source: PA P&CC 0.0 · p. 28
  • Network nodes process weighted inputs and bias into output signals, with the paper using tanh(20x) as the activation function.Outputs range from -1 to 1.Source: PA P&CC 0.0 · p. 28
Loading 1505.06353v1…