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.
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
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.