Генетический алгоритм - найти максимум свернутых подмножеств

Question

У меня есть комбинаторная задача оптимизации, для которой у меня есть генетический алгоритм для аппроксимации глобальных минимумов.

По заданным X элементам найти: min f(X)

Теперь я хочу расширить поиск по всем возможным подмножествам и найти одно подмножество, где его глобальный минимум максимален по сравнению со всеми другими подмножествами.

X * является подмножеством X, найдите: max min f(X*)

Пример графика показывает все решения трех подмножеств (по одному для каждого цвета). Черная точка указывает самое высокое значение из всех трех глобальных минимумов.

изображение: решения более трех подмножеств

Основная проблема заключается в том, что оценка соответствия между подмножествами повторяет сходимость решения в подмножестве. Далее решение на самом деле является локальным минимумом.

Как вообще можно описать эту проблему? Я не мог найти подобную проблему в литературе до сих пор. Например, если это разрешимо с многообъектным генетическим алгоритмом.

Любой намек очень ценится.

Answer 1

Хотя он не всегда может обеспечивать точно самые высокие минимумы (или самые низкие максимумы), способ поддержания локальных оптимумов с помощью генетических алгоритмов состоит в реализации метода niching. Это способы сохранения разнообразия населения.

Например, в Niching Methods для генетических алгоритмов Самира У. Махфуда 1995 года можно найти следующее предложение:

Используя построенные модели распределения пригодности, это исследование выводит нижние границы на численность населения, необходимого для поддержания, с вероятностью гамма, фиксированного числа желаемых ниш.

Если вы знаете количество ниш и реализуете упомянутое решение, теоретически вы можете получить локальный оптимальный вариант, который вы ищете.