Search for: All records

When Partition Crossover is used to recombine two parents which are local optima, the ospring are all local optima in the smallest hyperplane subspace that contains the two parents. The ospring can also be organized into a non-planar hypercube "lattice." Fur- thermore, all of the ospring can be evaluated using a simple linear equation. When a child of Partition Crossover is a local optimum in the full search space, the linear equation exactly determines its evaluation. When a child of Partition Crossover can be improved by local search, the linear equation is an upper bound on the evaluation of the associated local optimum when minimizing. This theoret- ical result holds for all k-bounded Pseudo-Boolean optimization problems, including MAX-kSAT, QUBO problems, as well as ran- dom and adjacent NK landscapes. These linear equations provide a stronger explanation as to why the "Big Valley" distribution of local optima exists.