2
$\begingroup$

I'm working on a complex engineering problem that I've essentially reduced to this problem:

I have a set of natural numbers $1,N$ and a grid (square or hexagonal) of exactly $N$ cells. I have to map each number to each cell so that the distribution (in a geometric sense) is as flat as possible. I'm still working on the definition of flat, but so far

  1. The average of the numbers of a cell and its nearest neighbours must be as close to $N/2$ as possible, for every cell.

  2. The average of the distance between a cell and each neighbour must be as large as possible.

If a cell has a number $n$ and its neighbour $m$ the distance between these neighbours is $min(|n-m|,N-|n-m|)$. It's essentially cyclical.

If $.$ represents a small number and # a large number I'm looking chessboard-like configurations like

.#.#.#.#
#.#.#.#.
.#.#.#.#

I need to find the best configuration (or a very good one) without using brute force.

Can you point me to some good algorithms that may be useful for this problem? I could only get above-average results on my own.

In my problem $N\approx~500$ and there is no runtime constraint.

$\endgroup$
  • $\begingroup$ Random assignment probably gives a pretty good solution. $\endgroup$ – Yuval Filmus Jan 8 '16 at 17:51
  • $\begingroup$ I've tried a random assignment but it's not good enough. After a solution is found I have to evaluate an engineering constraint that is pretty expensive to calculate. It's also not an option to feedback this evaluation to the distribution algorithm. So it's basically a (smart) trial and error. Not so lucky so far... $\endgroup$ – Fequi Jan 8 '16 at 18:19
  • $\begingroup$ BTW, I've been doing an initial assignment (not random) and several types of sorting. $\endgroup$ – Fequi Jan 8 '16 at 18:21
  • $\begingroup$ Do you already know how to solve the problem in the 1-dimensional case? (I understand that this is not the case that you would like to solve, but solving it for 1D first might help to understand better what kind of strategies might work for 2D.) $\endgroup$ – Jukka Suomela Jan 8 '16 at 19:17
  • $\begingroup$ Your first step is you need to find a single objective function you are maximizing. You can't simultaneously optimize multiple metrics. So, you have two numbers that are both important. How do you want to combine them into a single number? The sum? Set a hard constraint on one and ask to optimize the other? Something else? Without that, "best" is not well-defined. $\endgroup$ – D.W. Jan 8 '16 at 19:46
1
$\begingroup$

Simulated Annealing might work well for this problem.

The idea is to introduce a "temperature" component to your heuristic function to avoid getting stuck at local optima. Temperature corresponds to how willing the heuristic function is to accept an inferior arrangement. With simulated annealing, temperature starts off high and decreases until an optimal solution is found.

Here is solution to the Travelling Salesman Problem using simulated annealing

You can tinker with the starting temperature and its rate of change to try and find an optimal arrangement.

$\endgroup$
  • $\begingroup$ Thank you for your answer. Coincidentically, I'm having issues getting stuck in local minima. I've read the basics of the method and I think it will be very helpful; definitely worth a try. $\endgroup$ – Fequi Jan 11 '16 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.