Алгоритм поиска оптимумов в огромной дискретной вселенной

Question

В настоящее время я ищу алгоритм, который бы вернул оптимальную (или, по крайней мере, одну из лучших субоптимальных) комбинацию предметов с учетом размера и юниверса (в общем, между 10- 15 из 50, так что около нескольких миллионов миллиардов возможностей ...) и функция подсчета очков, которая дает производительность каждой комбинации в прошлом (функция оптимизации занимает от 2 мсек до 1 сек для запуска в зависимости от сложности, которую я выбираю). Основная проблема для меня - обработать количество итераций, которые нужно выполнить, если мне нужно проверить все возможные комбинации (я не могу даже сохранить все возможности комбинации в списке списков ... и использовать генератор для этого каждая оценка, если я не хочу исчерпать память). К сожалению, для некоторых функций я не могу использовать так называемый «генетический» алгоритм, основанный на итерациях (исходя из лучших из 2, лучших, из 3, ... корзин из n и т. Д. ... с некоторыми проверками на подпункте -baskets при добавлении нового элемента). Этот тип алгоритма довольно быстрый и дает довольно хороший результат большую часть времени.

Я уже пробовал смоделированный отжиг (версия scipy.basinhopping или специальная версия, которую я закодировал), но для каждой итерации требуется слишком много времени, если я выхожу за пределы 15 среди 25-30, так как я не могу хранить все комбинации в начале алгоритм и должен использовать генератор для каждой оценки. Более того, иногда я не очень удовлетворен оптимальным.

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

спасибо!

Answer 1

Я понимаю, что нет ни одного наилучшим решением на ваш вопрос, но вот некоторые предложения:

• ветвей и границ (если вы можете создать хорошую связанную функцию)
• симуляция отжига (попробовать разные остывать ставки и размер окрестности)
• муравейник колонии (как правило, менее эффективные, чем SA)
• мегаполис (как правило, менее эффективные, чем SA)
• поиск с запретами (не дает много O улучшение е, но хорошо, даже для трудных задач)
• линейного программирования (если задача может быть сформулирована в этих терминах)

Также распространено объединить несколько методов на самом деле трудной проблемой. Существует также библиотека python, реализующая многие из этих методов (и многие другие), or-tools. К сожалению, это не очень хорошо документировано

Я не думаю, что вам нужен полный набор комбинаций для имитированного отжига, поскольку это метод локального поиска. В типичном сценарии вы создаете новое состояние (например, добавляя случайную дельта к случайному параметру или выбираете случайную точку в радиусе в проблемном пространстве), а затем принимайте решение, согласитесь ли вы принять это изменение с использованием формулы вероятности , То есть одним из его преимуществ является точно малый объем памяти