¿Cuáles son los enfoques populares para optimizar la función booleana

Question

La optimización de una función de valor real es un campo popular en el que se han propuesto muchos algoritmos de optimización como el descenso de gradiente, levenberg-marquardt,...

Sin embargo, supongamos que la función es booleana y se define como f:{0, 1}^n:-->R, por lo que en este caso no podemos utilizar los algoritmos citados anteriormente. Entonces, ¿cuál es el enfoque y los algoritmos populares utilizados para optimizar tales funciones? ¿Es posible hacer una regresión lineal o no lineal en este caso?

Answer 1

Optimizar una función booleana es NP-Difícil en general, así que no diría que hay un enfoque popular que funcione siempre. Hay métodos exactos y heurísticos. Los métodos exactos pueden no ser lo suficientemente rápidos dependiendo de la complejidad de la función booleana y no hay garantías de que la heurística encuentre alguna vez la solución óptima.

Un buen punto de partida sería programación entera . Es posible reducir la programación entera a SAT. Los algoritmos más populares para encontrar soluciones a problemas NP-Hard tendrían que ser solucionadores SAT, por lo que se podría utilizar un solucionador SAT para optimizar f. Esta es una forma de optimizar f con solucionadores fácilmente disponibles, aunque podría no ser la forma más eficiente en cuanto a tiempo, ya que una reducción a menudo implica una mayor complejidad computacional.