I have a combinatorial optimization problem for which I have a genetic algorithm to approximate the global minima.

Given X elements find: min f(X)

Now I want to expand the search over all possible subsets X* of X and to find the one subset where its global minimum is maximal compared to all other subsets.

X* are the subsets of X, find: max min f(X*)

The example plot shows all solutions of three subsets (one for each color). The black dot indicates the highest value (maximum) of all three global minima.

image: solutions over three subsets

The main problem is that evaluating the fitness between subsets runs agains the convergence of the solution within a subset. Further the solution is actually a local minimum.

How can this problem be generally described? I couldn't find a similar problem in the literature so far. For example if its solvable with a multi-object genetic algorithm.

Any hint is much appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.