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

Question

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

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

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}. Однако я не понимаю этого решения.

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

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.
}

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

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

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

0

artificial-intelligence c++machine-learning simulated-annealing

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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

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

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

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

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

При высоких температурах молекулы свободно перемещаются

При низких температурах молекулы «застревают»

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

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

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

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

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

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

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

2