# 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"?

• 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

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.