Написание алгоритма имитации отжига для ранца 0-1 в C # - PullRequest
3 голосов
/ 02 августа 2010

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

Я нашел этот отличный код на CP:

http://www.codeproject.com/KB/recipes/simulatedAnnealingTSP.aspx

Я почти уверен, что понимаю, как все это работает сейчас (за исключением всего условия Больцмана, насколько я понимаю, это черная магия, хотя я понимаю оизбегая местных оптимумов и, видимо, именно это и делает).Я хотел бы переделать это, чтобы решить проблему ранцев 0-1.По сути, я кладу один из 5000 объектов в 10 мешков, и мне нужно оптимизировать его для наименьшего неиспользуемого пространства.Фактическая «оценка», которую я назначаю решению, немного сложнее, но не связана с алгоритмом.

Это кажется достаточно простым.Это означает, что функция Anneal () будет в основном такой же.Я должен был бы реализовать функцию GetNextArrangement (), чтобы соответствовать моим потребностям.В задаче TSM он просто меняет два случайных узла вдоль пути (т. Е. Он вносит очень небольшие изменения в каждую итерацию).

Для моей задачи на первой итерации я выбрал бы 10 случайных объектов ипосмотрите на оставшееся место.Для следующей итерации я бы выбрал 10 новых случайных объектов?Или мне лучше всего поменять несколько объектов, например, половину или хотя бы один из них?Или, может быть, количество предметов, которые я поменяю, должно быть относительно температуры?Любое из них кажется мне выполнимым, мне просто интересно, есть ли у кого-нибудь совет по поводу лучшего подхода (хотя я могу возиться с улучшениями, когда у меня будет работать код).1015 * Mike

Ответы [ 2 ]

3 голосов
/ 19 августа 2010

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

Для TSP это означает обмен соседними городами.Для вашей задачи я бы предложил алгоритм условного выбора соседей следующим образом:

  1. Если есть объекты, которые помещаются в пустое пространство, то он всегда помещает самый большой в.
  2. Если в пустое пространство не помещаются никакие объекты, выберите объект, который нужно поменять, но предпочитайте поменять объекты одинакового размера.

То есть объекты имеют вероятность, обратную к разнице их размеров.Возможно, вы захотите использовать что-то вроде выбора рулетки здесь, с размером среза, например, (1 / (size1 - size2) ^ 2).

2 голосов
/ 02 августа 2010

Ах, я думаю, что нашел свой ответ в Википедии ... Он предлагает перейти в "соседнее" государство, которое обычно подразумевает изменение как можно меньше (например, обмен двух городов в проблеме TSM) ..

From: http://en.wikipedia.org/wiki/Simulated_annealing

"Соседи состояния являются новыми состояниями проблемы, которые возникают после изменения данного состояния определенным образом. Например, в задаче коммивояжера каждыйсостояние обычно определяется как конкретная перестановка городов, которые необходимо посетить. Соседи некоторой конкретной перестановки - это перестановки, которые создаются, например, путем обмена парой соседних городов. Действия, предпринимаемые для изменения решения с целью поиска соседних решений.называется «ход», а разные «ходы» дают разных соседей. Эти перемещения обычно приводят к минимальным изменениям решения , как показано в предыдущем примере, чтобы помочь алгоритму оптимизировать решение до максимумастепень, а также сохранитьУже оптимальные части раствора и влияют только на субоптимальные части.В предыдущем примере части решения являются частями тура. "

Так что я считаю, что моя функция GetNextArrangement хотела бы заменить случайный элемент на элемент, не использованный в наборе.

...