PyQt Genetic Algo

Simple implementation and visualisation of genetic algorithm in work using Python & Qt.

Backround

Genetic algorithm is special technique for solving optimization problems, specialy in places where there are a lot of combinations and finding optimal solotion by simply brute-forcing is impossible.

The task to solve

The Aim of this project is to achieve optimized cell placement to complete efficient routing. Optimization should meet following criterias.

• Each cell (when moved) should preserve it's connectivity ( parent & child connections )
• Cell position can be adjusted within same colum ( can be moved vertically, but not horizontally )
• Intersections/crossings beetween connections should be minimal.

Self explanatory images : )

Left: Initial placmenet                                                                                  Right: optimized placement

          

Implementation

I've used MVC pattern to abstract the data from renderer. Theortically should be possible to add any view that can will use get_data function returning 2D array of nodes used and renderer them.

More complicated cases

Placement before ( 51 crossings )

Optimized ( 1 crossing )