1
$\begingroup$

Is there any algorithm that can learn/search efficiently the best sequence of 1's and 0's of length $n$ to fulfill certain performance? The search is performed in a high-dimensional binary data space. This means that the search space is of $2^n$ where $n$ usually is in the order of hundreds. I know that Discrete Particle Swarm Optimization, Simulated Annealing or Genetic Algorithms can be used for this purpose, but I'm afraid they tend to get stuck in local optima and/or can not work efficiently in high-dimensional spaces.

$\endgroup$
  • $\begingroup$ without info about your specific problem, this is hard to answer. Care to elaborate? $\endgroup$ – Memming Dec 9 '16 at 5:11
0
$\begingroup$

This question could search for be the analog of a (almost-polynomial) n-SAT algorithm, but no such algorithm is currently available (or may never be if P <> NP), so an optimisation method like SA or GA, should be the best option under your requirements

Additionaly, there is an algorithm called Deterministic Annealing (DA) which performs quite well on many circumstances, maybe check it out

$\endgroup$
2
$\begingroup$

You may be able to formulate your problem as a binary integer program, which even though in general they are NP hard, some instances can be solved very quickly through branch and cut algorithms (if the problem is linear). If your problem is non linear there are MINLP solvers that can give you an optimal answer. Nonetheless I must say that if your problem is particularly hard the most appropriate way to proceed will be metaheuristic.

I suggest that you attempt a linear or quadratic formulation of you problem and try some of the MILP/MIQP solvers available out there. If you are having issues formulating your problem in this framework check some linear programming/integer programming modeling books or post a question here.

$\endgroup$

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.