Hacker News Reader

Comment by ttyprintk | Hacker News Reader

Yet the author mentioned simulated annealing, so was probably not even trying a neural net, since SA does not compute a gradient.

View on HN

Simulated annealing has long been one of the classic metaheuristic methods applied to autorouting in circuit design. It was widely used in early research and some commercial tools because its probabilistic approach helps escape local minima in these NP‐hard problems. Today, while many modern autorouters in industry tend to favor faster or more specialized hybrid methods, simulated annealing remains a common benchmark in academic studies and research prototypes for routing and related tasks like floorplanning.

Source: I once wrote a simulated annealer for VLSI wiring. It was cool.

Simulated annealing works great for placing map labels. Lets say you have to label POI with flags, you do not want the flags to overlap and you can only place the labels NSEW of the POI.

1. Plop the labels down in random* directions.

2. Calculate the total overlap.

3. Randomly* move 10% of the labels.

4. Calculate the total overlap again, If the overlap is improved, keep your changes, If things got worse, then backtrack.

5. Sometimes you randomly keep changes that make things worse, this is the annealing part. This is how you escape local minima.

* The randomness does not have to be 100%, you can try smartly avoiding nearest neighbors 2/3 of the time and then do a random move 1/3 of the time. If you always try and be smart you will tend get trapped in a local minima.

Reply on news.ycombinator.com