Simulated Annealing : Placement-Routage

Simulated Annealing : Placement-Routage

The problem is to find the optimal configuration of its connection between different blocks of an integrated circuit. It is a difficult optimization problem requiring the use of metaheuristics to find an approximate solution.
In a real implementation, time calculations are very high given the large number of eléléments to treat.
In our case, the blocks are disposed REGULAR on a square grid. Function cost is calculated as the sum of costs of each connection. The cost of a connection is equal to the Manhattan distance between the two blocks of connection.
This problem is well suited to a resolution by simulated annealing.
We perform a random initialization of the grid and then we apply the
following algorithm. The only elemental movement is the permutation of the positions of 2 blocks of the grid.
The blocks switch are randomly selected `at every stage of simulated annealing.
the number of electronic's component dynamically typed, so you have to choose the sqrt of the final number of components, it means if you want to find the optimal placement of 25 component so you have to type 5 ... etc