Лучший алгоритм для оптимизации решений в симуляции

Question

Я ищу лучший алгоритм для оптимизации решений, принимаемых одновременно, чтобы найти быстрый результат за разумное время. Simultaion делает несколько «галочек», и иногда необходимо принять решение. В конечном итоге целевое состояние достигается. (Было бы возможно никогда не достичь целевого состояния, если вы принимаете очень плохие решения)

Есть много много целевых состояний. Я хочу найти целевое состояние с наименьшим числом тактов (тик примерно равен секунде в реальной жизни. "Я в основном хочу решить, какие решения принять, чтобы достичь цели за несколько секунд, насколько это возможно,

Некоторые замечания по проблемной области:

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

Алгоритмы:

• Мне нужно обработать эту проблему в течение примерно 10 секунд, а затем дать лучший ответ, который я могу.
• Я верю, что * найдет мне оптимальный солютон. Проблема в том, что дерево решений будет настолько большим, что я не смогу рассчитать его достаточно быстро.
• IDA * даст мне хорошие первые несколько вариантов за 10 секунд, но мне нужен путь до цели.

В данный момент я думаю, что начну с известного неоптимального пути к цели, а затем, возможно, использую имитацию отжига и попытаюсь улучшить ее в течение 10 секунд.

Какой будет хороший алгоритм исследования, чтобы попытаться решить проблему такого рода?

Answer 1

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

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

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

Answer 2

Давайте рассмотрим несколько фактов.

1) Единственный способ точно определить, какое решение является лучшим, - это проверить каждое возможное решение и оценить результат на основе некоторых критериев.

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

3) Мы вряд ли сделаем лучший ход ~ когда-либо ~. Не просто часто, а всегда. Если у вас нет только пары решений, скорее всего, каждый раз, когда вы принимаете решение, было лучшее, к которому вы не попали.

4) Мы можем использовать наши предыдущие решения в наших интересах.

Соберите все это вместе. Скажем, когда у нас есть решение, мы оцениваем то, что произойдет, через 30 тиков в будущем, за 30 тиков мы можем проверить, соответствует ли то, что на самом деле произошло, тому, что мы смоделировали 30 тиков назад. Если это так, мы знаем, что это решение приводит к предсказуемым результатам, и мы должны использовать это решение меньше. Если мы этого не сделали или получилось лучше, чем мы надеялись, мы должны использовать это решение чаще.

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