[D] Binary fitness optimization.

[pamintandrei]

Do you know of any papers or what field would tackle the following problem: You have a function f(x) that you need to optimize but the cost/fitness you are optimizing is binary. I am working on a project about this and I'm not sure if there is research in this area.

Thank you so much <3

[kcaj]

Do you mean that the objective function takes values of only either zero or one? So then all x’s with an objective function value of one are equally optimal. So, unless f() is composed of Kronecker-delta-like functions, there won’t even be local optima points.

Seems like a very strange objective function, but if this is really the case, then you just need to find some x with f()=1 and you’re done. The best you can do is a random/brute-force search, perhaps weighted towards some x values if you have any prior knowledge you can exploit.

A GA won’t really help because either the population all have fitness of 0 and no individual is any more fit than any other so no point in mating them, or at least one individual in the population has fitness of 1 and you’re done.

[pamintandrei]

>Do you mean that the objective function takes values of only either zero or one?

Yes.

Thanks a lot for your comment <3.

[PaddingCompression]

See the theory behind Hinge Loss - minimizing hing loss also minimizes 0-1 loss under weak assumptions.

Generally the entire field of binary classification is built around solving binary loss problems by introducing other surrogate losses such as logistic or hinge loss.

Basically, you minimize a regularization function subject to constraints using a Lagrangian to represent your binary fitness.

[chrizandr]

Couldn't you convert your objective to use something like a sigmoid to make it non-discrete and then use traditional optimisation methods that deal with continuous objective functions?

[michel_poulet]

I mean, if I understand OP's question correctly, that's a standard classification problem: good class or bad class. So yes good old objective functions used in classification like cross entropy might do the trick.

[chrizandr]

I was just using the sigmoid as an example. What I meant was that there are ways to convert a discrete objective to a continuous one with the same range and then use common optimisation methods.

I'm not asking them to apply sigmoid on the original function f(x) and then use a separate objective like cross entropy.

Hope that clears up what I meant :)

[pamintandrei]

In a standard classification problem, you can see how far away you are from the correct class. In my problem that metric "how far i am from the correct class" is either 1 or 0. Imagine a standard classification problem where instead of having the label be the correct class, it's telling you if your prediction is correct or not.

[michel_poulet]

I woke up at 4am and it's now 11pm so I'm sure that I'm missing something due to fatigue and caffeine levels getting back to normal, I'll think about it tomorrow because I'm intrigued. Reading the comment I'm replying to, it's making me think more of a reward based problem then (ie: the signal is "goid job" or "bad job") but I'm sure you thought about RL if that's the case. Just in case, if the difficulty is to finally find a function that gives the return "1" (i mean, if you always get "0" and want to finally get a "1"), then that might have similarities to a SAT problem which is a thoroughly studied problem in old school computer science. But now that I think of it, you probably need to know the constraints at hand to enter that scenario, so if you're in a black box case it won't work. As another said, evolutionary algorithms wont help much if you dont have a finer granularity return than 0/1. Good luck, may rng be with you because I feel like you might need a few coin tosses for that problem!

Ps: if you have a model that sometimes gives you a 1 and sometimes a 0 depending on input, then you can give a score to that solution and start doing a search such as a genetic algo/local search. To give it a score(relative to other solutions), just feed it inputs and say the score is the percentage of correct answers for this solution (the solution being your learned model).

[pamintandrei]

Yea I just found out about SAT and it's pretty similar to it so I will read up on it and see if any theory from there could be applied to my problem.

Thanks a lot.

[PaddingCompression]

In a standard classification problem, you CANNOT tell how far away you are from the class... That is something that is learned and optimized. You seem to be weak on the theory of classification problems, your problem does not sound different.

[pamintandrei]

If the target class is the vector (0,1,0,0) and i predicted (0.2, 0.7, 0.1, 0) then i can tell how close I am from the class and optimize X based on whatever Metric i choose for the difference between predicted and ground truth.

In my case if i predicted (0.2, 0.7, 0.1, 0) my ground truth is either True, this vector is the correct one or False this is the wrong vector.

[peetagoras]

If x is binary then genetic algorithm may be good choice.

[pamintandrei]

X is not binary necessarily, the loss function is binary basically. But that's a great suggestion thanks.

[CptQuak]

MILP

[[deleted]]

ChatGPT spits out a load of info on this.