The SDBV near-hardness conjecture for the (1+1)-EA
Statement
Let SDBV (Switching Dynamic Binary Value) be the dynamic monotone function defined in the paper, and let denote the expected number of generations required by the -EA to optimize a dynamic monotone function . SDBV near-hardness conjecture. If is a hardest dynamic monotone function, then
The paper proves that SDBV minimizes drift and gives its runtime for the standard mutation rate, while experiments suggest that the gap to the truly hardest function decreases with dimension; whether SDBV itself maximizes expected runtime remains open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.