Skip to content

Latest commit

 

History

History
108 lines (72 loc) · 4.85 KB

README.md

File metadata and controls

108 lines (72 loc) · 4.85 KB
Raw

PEAviz

Python Evolutionary Algorithm Visualistaion toolkit on DEAP

Requirements Status

PEAviz bridges DEAP with graph analysis tools like graph-tool. The aim of PEAviz is to enable tracking of evolutionary dynamics and present a network of individuals that encodes all that you want.

Evolutionary dynamics are not very well understood yet, and the network generated by PEAviz can provide not just experimental data but analysis might uncover previously unknown facts and patterns. The analysis might also provide proof for known hypothesis on GA behaviours!

Alas, as of mid 2017, there is no universally accepted way of tranforming dynamics into a network, and the default transformation (which is called Encoding Strategy) implemented in PEAviz, is not necessarily the best one.

Default Encoding Strategy

For each individual added into the population,

  1. A node is created.
    • two or more nodes can encode the same individual (genetic material) because the same individual can be added into the population at different iterations, possibly with different parents.
    • Thus, nodes are NOT UNIQUE.
  2. Edges are added from parents to this node.
    • The network might have parallel edges, as the selection process of a GA might allow the same individual to be picked twice, as a parent!

To find out more about the approach refer

Davendra, Donald, et al. "Complex network analysis of differential evolution algorithm applied to flowshop with no-wait problem." Differential Evolution (SDE), 2014 IEEE Symposium on. IEEE, 2014.

on IEEE Xplore

The paper above uses this strategy to study a Self Organising Migrating Algorithm, but the strategy can be used to study other EAs too.

Architecture

PEAviz is composed of 3 elements, Adapter, Tracker and Encoding strategy.

Adapter : Interface that implements all actions required to create the Graph representation and maintain it. This could be, a graph-tool Graph or, a neo4j DB connection or, a Gephi GraphStream Object.

Encoding Strategy : This details what an individual is, its attributes and when or how edges are created, whether they are directed or undirected, etc.

Tracker : Your GA creates an instance of this and connects it to the desired Adapter(s). Tracker uses the Encoding Strategy to invoke Adapter methods and create the desired evolutionary network.

architecture

Trackers and Encoding Strategy are highly coupled, ie, a new Tracker is required for a new Encoding Strategy.

Elements

  1. Adapters
    • graph-tool 💯
    • Neo4j 🔜
    • GraphStream 🔜
  2. Trackers
    • Base tracker for the default strategy. 💯
  3. Encoding Strategies
    • Default Strategy 💯

💯 denotes completed.
🔜 denotes future goals.

Usage

  • Implement your GA in DEAP
  • Use peaviz elements to track the dynamics.
    • Decide Encoding Strategy, or use the default.
    • Implement a Tracker Interface for your Encoding Strategy.
    • Use an Adapter, or implement your own.
  • Execute GA, upon completion PEAviz provides a network.
  • Export the network to desired analysis tool (we use graph-tool).
  • Analyse.

Why DEAP

DEAP is a very flexible framework to run evoultionary algorithms. We can fine tune all aspects of the evolution and individuals.

Why graph-tool

GT is an excellent python package which allows scripted analysis Graph filtering and GraphViews that are ideal for manipulating and visualising graph objects.

Installation

PEAviz has not yet been pacakged, see #5

  1. Install the python requirements:
    • pip install -r requirements.txt
  2. Optionally install graph-tool. Instructions

Results

Testing onemax.py

Force Atlas Layout: Animated gif (2.5MB)

A different layout of the same graph: img-onemax-gephi-sfdp

A different graph: knapsack-filtered-graph

This work is part of our Undergraduate Degree Course Work.