Имитация отжига с максимизацией реального значения

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

float weight[5]={2, 3, 5, 4, 3}; // weight
float value[5]={10, 20, 15, 25, 5}; // value of corresponding item
float bagSize = 11.0;

Путем жестких вычислений мы знаем, что лучшим решением является {1,1,0,4,1,0}. Однако я не понимаю этого решения.

Я объясню свой код на С++ в псевдокоде, чтобы избежать длинных кодов.

While (temperate > 1){
  1) Generate random values between (0,1) to fill the 5 sized array for each item
  2) Perform random swapping of values in the 5D array above.
  3) Calculate the fitness and new weight
  4) Save the best solution. 
}

В основном это мой код вкратце. Мой вопрос

  1. На шаге 2 при выполнении замены в настоящее время я меняю местами элементы массива. Это правильно? Или я должен отслеживать предыдущее решение и менять текущий элемент (i) на предыдущий элемент решения? (Это всего лишь идея).
  2. При использовании реальных значений в массиве, как я могу сообщить системе во время выполнения, что предыдущее решение было близко к максимальной границе, потому что в моей текущей реализации я непрерывно генерирую случайные значения на первом этапе, который повторяется до тех пор, пока система не остынет.

Наконец, возможно, в моей реализации есть какая-то огромная ошибка, я очень признателен, если мне помогут в этой проблеме.


c++ machine-learning artificial-intelligence simulated-annealing
person rish    schedule 04.11.2013    source источник
comment
Это даже не похоже на симуляцию отжига, вы должны исправить свой псевдокод, а лучше - включить реальную реализацию, так как она должна быть не более 20 строк.   -  person lejlot    schedule 04.11.2013
comment
Также обратите внимание, что смоделированный отжиг не гарантирует нахождения глобального максимума, за исключением определенных классов задач и при очень медленном охлаждении (даже в этом случае, поскольку Метрополис-Гастингс сходится к равномерной выборке из мод распределения, вы должны быть уверены, вы видите все моды, а затем вычисляете пригодность для каждой из них.) И особенно для этих болезненных комбинаторных задач имитация отжига может быть очень хрупкой. Выполнение X итераций приводит к близкому решению, но вам нужно X * (10 ^ 6) итераций, чтобы иметь разумный шанс получить лучшее в мире.   -  person ely    schedule 04.11.2013
comment
(Это может не иметь значения, если размер экземпляра вашей проблемы очень мал, но из вашего вопроса все равно кажется, что вы ожидаете, что имитация отжига просто даст вам правильный ответ.)   -  person ely    schedule 04.11.2013
comment
На самом деле, мое первое предположение было таким, но позже я понял, что решение, которое я получаю, может быть близко к Gobal Max, но может и не быть Gobal Max.   -  person rish    schedule 12.11.2013

Ответы (1)


arrow_upward
2
arrow_downward

Ваш псевдокод не имитирует отжиг. Вы беспорядочно прыгаете в пространстве поиска без какой-либо цели.

Ваш первый вопрос:

На шаге 2 при выполнении замены в настоящее время я меняю местами элементы массива. Это правильно? Или я должен отслеживать предыдущее решение и менять текущий элемент (i) на предыдущий элемент решения? (Это всего лишь идея).

Вы должны реализовать функцию под названием perturb. Это возмущение должно заменить ваши значения массива. Имитация отжига, как следует из названия, использует концепцию отжига. Это означает, что вы начинаете горячо. Ваша функция возмущения резко меняет значения. Затем ваше решение начинает остывать, что означает, что ваша функция возмущения меняет значения лишь незначительно.

См. следующую презентацию.

z Постепенное охлаждение жидкости …

  • При высоких температурах молекулы движутся свободно.
  • При низких температурах молекулы «застревают».

Согласно вашему решению, вы получаете свою случайность в следующей строке.

2) Выполните случайную замену значений в массиве 5D выше.

Вот как вы должны реализовать постепенное охлаждение.

  • 2а) int MaxRandomValueToAddToArrayValues ​​= 20;
  • 2b) Как я нашел 20, это знание предметной области. В соответствии с вашими ценностями и лучшим решением 20 кажется хорошим значением.
  • 2c) Выполните случайную замену значений в массиве 5D выше, используя эту границу
  • 2d) постепенно уменьшайте MaxRandomValueToAddToArrayValues. Например, для каждых 10 итераций вы можете уменьшить его на 0,1.

Ваш второй вопрос:

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

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

person Atilla Ozgur    schedule 05.11.2013
comment
Спасибо за ваше объяснение. Я вижу все, что я делал не так. Просто вопрос, в моем заявлении выше, как вы сказали, я просто ищу без цели, и я думаю, что это первый шаг? Если я исключаю первый шаг и где я случайным образом присваиваю значения и реализую что-то вроде возмущения, как вы сказали. Извините, я совершенно потерялся в этих вещах AI. - person rish; 11.11.2013
comment
Также на самом деле я получил этот псевдокод из Википедии, и он говорит, что выберите некоторых соседей, для которых я реализовал шаг 1 в цикле выше. en.wikipedia.org/wiki/Simulated_annealing - person rish; 11.11.2013
comment
о, спасибо, кажется, помогло. У меня есть несколько вопросов, если бы вы могли мне помочь в этом. 1) Как вы сказали, уменьшайте его постепенно, скажем, после 10 итераций. Означает ли это, что моя максимальная температура равна 20, или я должен поместить цикл внутри цикла while, чтобы я уменьшал максимальное значение массива при каждом снижении температуры и получал лучшее фитнес-решение? - person rish; 12.11.2013