# Black-box combinatorial optimization problem over permutations

I am solving general black-box optimization problems like: x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is represented by stand-alone computer code and x represents configuration of complex system with the response simulated by f(x).

I learned, that in this case I can use many heuristic methods. But, most of these methods use always some kind of local search, which require suitable distance metric at search space (space of permutations x in my case). Under suitable distance metric I mean the metric which fulfill the "locality" property, e.g. small change of permutation x produce small change of objective function f(x). In my case is not known any suitable distance metric with this property, so any kind of local search is nearly the random search.

I have a few questions:

1. Are there available any heuristic black-box combinatorial optimization methods, which does not use local search and/or any distance metric at search space? I need to overcome the low "locality" of the problem or simply the fact, that any suitable distance metric at search space is unknown.

2. Is the "locality" property really so restricted at combinatorial optimization in general? May be I miss something..., but the most of real-world black-box combinatorial problem has low or very low "locality" due to the fact, that the common permutation distance metrics (Hamming, Kendal, etc.) are not suitable metrics in general.

3. Is there any general method how to find suitable distance metric at search space to satisfy at least approximately the "locality"?

Additional remarks:

• In real, the black-box function f(x) is realized by stand-alone deterministic simulation code, where x plays a role of discrete configuration of the simulated physical system. So, function f(x) has definitely well defined properties, but this properties are so difficult, that is not possible to simple exploit it.

• Because of above mentioned complicated internal properties of function f(x) is not possible to find proper distance metric d(x,x') in search space which fulfill "locality" (similar x and x' in a sense of any distance metric produce similar responses f(x) and f(x'))

• So, finally, I am looking for any optimization heuristics, which are able to find any suitable sub-optimal solutions only by informations available by properties of f(x) at fitness space. Like EDA's (Estimation of Distribution Algorithms) for example.

The main reason of this question is, what types of optimization heuristics are suitable to solve this kind of problems.

• Does "stand-alone computer code" mean that you only have the ability to evaluate f(x) on inputs x of your choice, but you don't know anything about the structure or form of x? – D.W. Feb 12 '18 at 17:01
• Yes, this is exactly what I mean. – michal Feb 12 '18 at 17:02
• If you can't tell us anything about what nice properties f has, we probably can't help you identify heuristics that are suitable for us. You've given us no information about f so I don't see much to work with here. – D.W. Feb 13 '18 at 17:24
• I understand your effort to get any useful properties of f(x), but this is extremely complicated question. My f(x) is represented by very complex nuclear reactor simulation code. Permutation x represents configuration of different fuel types at separate positions of reactor core. f(x) is highly nonlinear. There are a lot of empirically defined properties, but nobody is able to transform them to mathematically consistent conditions. But, the problem is still very actual at reactor physics community. So finally, is there any methodology how to extract required properties of Blackbox functions? – michal Feb 13 '18 at 18:30
• OK, got it. There may be some techniques, but my experience is that using domain knowledge is often the most effective place to start. For instance, maybe you know that if you slightly increase the amount of fuel of one type, then often this causes a not-too-large change in the value of f. Or maybe you know that if you swap two adjacent elements of the permutation, some fraction of the time this causes a not-too-large change in the value of f. Or maybe you know that two types of fuel are similar so swapping fuel between those two types often makes only a small change to f. (continued) – D.W. Feb 13 '18 at 20:59

## 1 Answer

In general if you know nothing about f and it can be totally arbitrary, then there is nothing you can do: you cannot do better than brute-force. If f has no structure, no properties, no regularities, and is just totally random, then it is easy to see that any algorithm has to compute f on all $N!$ possible permutations to find the minimum.

In practice it is common to deal with functions f that do have some degree of structure. For instance, if x,x' are similar (for some notion of similarity), then f(x),f(x') might have a good chance of being similar. In those cases you can use techniques like local search. But if you don't have that property, then you can't use local search, and you may be back to a situation where you cannot do any better than brute force.

There are other approaches in other situations: e.g., if we know the symbolic expression for f, we might be able to use a SAT solver, especially if that symbolic expression is not too large. But again this requires f to have some structure and not be totally arbitrary.

There are no silver bullets. You need to know something about f to have a hope of doing anything.

• What about Estimation of Distribution Algorithms, which are based only on evaluated values of f(x) at fitness space? These algorithms build probability distribution model for sampling of x at next iteration? – michal Feb 12 '18 at 17:09
• @michal, those are another heuristic that assume that f has some nice properties. They don't work for an arbitrary f with no structure. There are many heuristics, each with their advantages and disadvantages, but each one requires the function f to have some structure. So a good first step is to figure out what structure your function f has, and use that to inform the choice of a method. – D.W. Feb 12 '18 at 17:12
• Of course, function f(x) has definitely some "nice" properties, because it is represented by deterministic stand-alone algorithm. And the EDA's should find these properties at least approximately. I just want to be sure, that EDA is probably only one heuristic, which doesn't need explicitly any distance metric at search space. – michal Feb 12 '18 at 17:31