1. 首頁
  2. 問答
  3. 模擬退火算法解決斌包裝

模擬退火算法解決斌包裝

2014-04-21 70 views
0

我在研究關於Bin Packing問題。我目前已經在遺傳編程方式中實現了這個問題。但是當我爲這個問題研究模擬退火算法時，我不太瞭解它。模擬退火算法解決斌包裝

是否有任何良好的鏈接或代碼/ psuedocode這個問題。

來源

2014-04-21 Trần Kim Dự

+0

在下雨之前，我會建議在計算機科學SE上提出這個問題。國際海事組織，你目前形式的問題對於適當的SO問題來說技術太少。你正在尋求廣泛的研究材料，這是「好」，這使得答案有偏見和基於意見。就我個人而言，我只是覺得你會有更多的接待和機會問到那裏。 – luk32

+2

此外，我認爲它可能是稍微更有可能的，你正在研究的「問題」是「垃圾箱」，而不是「垃圾箱」...... – twalberg

回答

4

首先我們定義問題

包一組 N = {1, 2, …, n}項目，每個大小 t_i, i =1, 2,…, n,到相同的垃圾箱，每個容量C 最小化窗口的數量在不違反容量限制

所以退火算法的主要概要將包括：

  • 使用第一配合降低過程
  • 計算構造一個初始溶液和分配權重項歪曲根據 個別二進制位 的包裝解決方案的尺寸
  • 通過交換物品betweenall對倉的執行局部搜索
  • 開展重新加權基於先前 優化運行
  • 的結果根據冷卻時間表
減肥失真

現在做的裝箱問題鄰域搜索是很重要的：通過交換區之間的項目 用下面的目標函數（Fleszar年和2002年印地文）

  • 從目前的解決方案，獲得下一個解決方案

enter image description here

  • 交換方案兩個區間之間 交換物品，然後再進行瑞士法郎ap（1,0），Swap（1,1），Swap（1,2），Swap （2,2）。
  • 交換（1,0）

enter image description here - 然後評估僅在目標函數值的變化

  • 交換（1,1），然後交換（1,2）這樣的： enter image description here

這應該給你一個開始。

來源

2014-04-21 17:40:02 cMinor

+0

我讀過一些鏈接，說'溫度''縮放'參數，並且他們定義了一個公式來計算bin i的權重，例如：'wi = 1 + K * ri'，但是在算法中，我不明白這個公式的作用。你能爲我解釋一下嗎？謝謝:) –

+0

，你能爲我解釋一下swap（0,1）swap（1,2）...更清楚嗎？這是否意味着將bin a上的第0個元素與bin b上的第1個元素交換？還是其他什麼？謝謝:) –

+0

這一點讓我感到困惑:( –

相關問題

 相關問題