Skip to content

genetic algorithm usage for routing optimization ( pyqt )

Notifications You must be signed in to change notification settings

levibyte/pyqt_genetic_algo

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

24 Commits
 
 
 
 
 
 
 
 

Repository files navigation

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 )