Алгоритм или формула для поиска хороших значений настройки для поиска

Question

У меня проблема с программированием, и мне интересно, есть ли какой-либо алгоритм, класс, формула или процедура, которые могут создавать хорошие поисковые местоположения на основе прошлых результатов. (Я предполагаю, что где-то есть.) Или, было ли решение, которое я выбрал, было хорошо?

Позвольте мне попытаться объяснить на простом примере: Скажем, есть водоем, который составляет 2 х 2 метра и 3 метра в глубину. Я могу поместить свою приманку для рыбалки в любом месте x, y, z (2 X 2 X 3 = 27 мест). Скажем, я рыбаю в каждом месте в течение одного часа (проверяя пруд), и я собираю другое количество рыбы в каждом из 27 мест. Теперь, после того, как я это сделаю, лучшим местом для логической рыбалки является то место, где я поймал большинство рыб, НО только потому, что я поймал больше всего рыбы там, это не значит, что это лучшее место. Мне просто повезло. Вероятно, было бы лучше потратить большой кусок моего времени в этом месте, но все же приключение в процентах от времени, чтобы подтвердить, что это лучшее место.

Одно простое (и плохое?) Решение состоит в том, чтобы ловить рыбу по 10 часов в каждом месте, и там, где большинство рыбы пойманы, вероятно, будет хорошим местом, но это будет очень много времени (270 часов). Скорее всего, если я закончил ketch 15 на некоторых x, y, z и ни один в x2, y2, z2, тогда я не должен тратить много времени на x2, y2, z2.

Второе решение, о котором я думал, состояло в том, чтобы сохранить подсчет часов и общую рыбу, пойманную в каждом месте. А потом что-то вроде: (простой пример)

float catchesByLocation[2,2,3] = {1}; //init all to 1 
float totalTimeSpentByLocation[2,2,3] = {1}; //init all to 1 

While(true) //never really ends 
{ 
    Do x = 0 to 2 
    Do y = 0 to 2 
     Do z = 0 to 3 //depth 
     { 
     float timeToSpendAtThisLoc = catchesByLocation[x,y,z]/totalTimeSpentByLocation[x,y,z]; 
     float catches = GoFishing(x,y,z); 
     catchesByLocation[x,y,z] = catchesByLocation[x,y,z] + catches; 
     totalTimeSpentByLocation[x,y,z] = totalTimeSpentByLocation[x,y,z] + timeToSpendAtThisLoc; 
     } 
} 

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

Итак, у меня есть вопрос - существует ли какой-то логичный подход? Может быть, есть даже верный способ решить эту проблему с помощью математики? Любые мысли о способах атаки на эту проблему? Извините за плохой титул, я не могу придумать, как назвать его, и я открыт для предложений. Спасибо, что прочитал мой вопрос.

Answer 1

Ваша проблема рыбы пруд описывает экземпляр класса задач под названием Explore/Exploit алгоритмов или сторукий Bandit проблемы; см., например, http://en.wikipedia.org/wiki/Multi-armed_bandit. Существует большое тело математической теории и алгоритмических подходов, однако основные допущения примерно следующим образом:

• Рыбалка в месте, где мы видели наибольшее количество рыбы/час оптимизирует ожидаемую кратковременную награду (это то, что мы должны делать, если бы у нас был только один час). Однако, если мы продолжим ловить рыбу в течение некоторого времени, могут быть лучшие пятна, но у нас недостаточно информации.
• Чтобы формализовать эту мысль, мы вводим временную скидку (рыба , пойманная сегодня, более ценна, чем пойманная завтра, скажем, в 0,8 раза). Наша цель - , чтобы максимизировать общую скидку рыбы, в течение заданного периода рыбалки, или на бесконечном горизонте.
• Каждый час мы решаем, ловить рыбу в текущем лучшем месте или получить дополнительную информацию о новой. Простейшая возможная стратегия («epsilon-greedy») будет ловить рыбу в самом красивом месте в настоящее время, например. с вероятностью 90%, и выберите другое местоположение случайным образом в 10% случаев.
• Более сложные стратегии приведут к оценке вероятности того, что местоположение может быть лучше нашего текущего наилучшего местоположения (это зависит как от ожидаемого значения оценки, так и от ее дисперсии, т. Е. От общего времени и рыбы/часа).Затем мы основываем решение по этой вероятности для более информированного выбора (сначала исследуйте места, которые выглядят наиболее перспективными).
• Для проблемы рыбного пруда разумная вероятностная модель может учитывать окрестности (местоположения (x, y, z), вероятно, аналогичны местоположению (x-1, y, z), (x, y-1, z), и т.д).