一維裝箱問題畢業(yè)論文

1、<p><b>　　摘 要</b></p><p>　　一維裝箱問題來源于人們的長期以來的生產實踐，是一種組合優(yōu)化問題。給定有窮個物體，每個物體的重量是已知的正實數(shù)。給定足夠多個空箱子，問題是要在滿足兩個約束條件的前提下，將所有物體放到箱子中去，使得所用箱子的個數(shù)盡可能地少。兩個約束條件是：第一，每個物體均保持完整，恰好放到一個箱子中去。不能將物體分割成幾塊。第二，每個箱子中所放

2、的物體的重量之和均不能超過一個相同的上限，這個上限是一個已知的正實數(shù)。</p><p>　　一維裝箱問題具有很高的理論價值和實際價值。一方面，學者已經證明一維裝箱問題是一個NP難度問題，因此一維裝箱問題具有很高的理論價值。另一方面，一維裝箱問題出現(xiàn)在實際生產的一些領域，因此也具有很高的實際價值。</p><p>　　迄今為止，國內外學者提出了許多用來求解一維裝箱問題的嚴格算法和近似算法。一

3、方面，嚴格的最優(yōu)算法所花時間太長，實際部門無法忍受。另一方面，近似算法由于可能快速地生成最優(yōu)解或者接近最優(yōu)解而為實際生產部門所廣泛采用。</p><p>　　人類把物體往容器中裝，已有幾千年以上的經驗。這些生活經驗可引導出高效率的算法。本文提出了一種擬人算法。算法由三個部分組成。第一部分是降序最佳適合算法，用于生成初始解。第二部分是鄰域搜索算法。給定一個解，用鄰域搜索算法可以通過迭代改進這個解。本文的鄰域定義的思

4、想來源于“天之道損有余而補不足”。第三部分是跳坑策略。跳坑策略用于跳出局部最優(yōu)解，將搜索引向有希望的區(qū)域，從而提高算法的效率。跳坑策略的思想來源是“三十六計走為上”。</p><p>　　本文的程序計算了一組共17個國際公認的問題實例。這組問題實例分為兩類。第一類為8個問題實例，目前尚未確定其客觀最優(yōu)解。第二類為9個問題實例，目前已經確定了其客觀最優(yōu)解。擬人算法對第一類問題實例中的6個問題實例找出了與當前已知最好

5、解質量相同的解。擬人算法還證明了TEST0068這個問題實例的目前已知最好解正是客觀最優(yōu)解。擬人算法快速地找出了第二類問題實例中全部9個問題實例的客觀最優(yōu)解。</p><p>　　計算結果表明，擬人算法是一種有效的求解一維裝箱問題的近似算法。</p><p>　　關鍵詞： NP難度； 擬人； 鄰域搜索； 跳坑； 裝箱</p><p><b>　　Abstr

6、act</b></p><p>　　The one dimensional bin packing problem, which is a famous combinatorial optimization problem, comes from long term practice of human being. The definition of the one dimensional bin p

7、acking problem discussed in this paper is as following. Given items and enough identical bins, the weight of each item is a known positive real number. The capacities of all bins are equal. The problem is to pack all it

8、ems into the bins with the objective of minimizing the number of occupied bins, subject to two f</p><p>　　The one dimensional bin packing problem is of both highly theoretical and practical values. On one ha

9、nd, the one dimensional bin packing problem has been proved to be NP-hard. On the other hand, the one dimensional bin packing problem appears in some real world factories.</p><p>　　So far, many exact algorit

10、hms and approximation algorithms have been proposed to solve the one dimensional bin packing problem. Exact algorithms require too much computing time and cannot be accepted by workers. On the other hand, approximation a

11、lgorithms are widely used by workers, since they may give optimal or near optimal solutions quickly.</p><p>　　Mankind have more than several thousands of years of experience to pack items into containers. Th

12、e experience can induce efficient algorithm. A quasi-human algorithm is presented in this paper, which is composed of three parts. The first part is best fit decreasing algorithm to generate initial solution. The second

13、part is local search algorithm. Given a solution, local search algorithm is used to improve this solution by iterative steps. The idea of the definition of the neighborhood comes from</p><p>　　Computational

14、experiments are carried out on a set of 17 benchmark problems. This set of 17 benchmark instances can be divided into two classes. The first class consists in 8 instances whose optimal solutions are still unknown. The se

15、cond class consists in 9 instances whose optimal solutions are already known. For 6 out of 8 instances of the first class, our algorithm finds out solutions which are equal to the best known solutions up to now. Our algo

16、rithm proves that the best known solution for </p><p>　　The results show that the quasi-human algorithm is an efficient algorithm for the one dimensional bin packing problem.</p><p>　　Keywords:

17、 NP-hard; Quasi-human; Local search; Off-trap; Bin packing</p><p><b>　　目 錄</b></p><p><b>　　1 緒論1</b></p><p><b>　　1.1 引言1</b></p>&

18、lt;p>　　1.2 問題描述1</p><p>　　1.3 研究現(xiàn)狀2</p><p>　　1.4 本論文的主要結構5</p><p><b>　　2 算法描述6</b></p><p>　　2.1 擬人算法的大致框架6</p><p>　　2.2 生成初始解7&l

19、t;/p><p>　　2.3 鄰域搜索7</p><p>　　2.4 跳坑策略9</p><p>　　3 程序設計11</p><p>　　3.1 程序流程11</p><p>　　3.1.1 讀取文本文件中的數(shù)據(jù)13</p><p>　　3.1.2 生成初始解13</

20、p><p>　　3.1.3 鄰域搜索14</p><p>　　3.1.4 釋放內存15</p><p>　　3.2 調試程序15</p><p>　　4 計算結果16</p><p><b>　　5 結論18</b></p><p><b>　　參

21、考文獻19</b></p><p><b>　　致謝21</b></p><p><b>　　1 緒論</b></p><p><b>　　1.1 引言</b></p><p>　　當前世界經濟高速發(fā)展，人口日益增加，資源日漸緊張。人們在生產生活中希望提高效

22、率，節(jié)約資源，以實現(xiàn)可持續(xù)發(fā)展。在運籌學領域有一類所謂最優(yōu)化問題。最優(yōu)化問題的一般形式是：在滿足約束條件的前提下，給出自變量的值，使得目標函數(shù)值最優(yōu) (通常是使得目標函數(shù)值最小或者最大)。</p><p>　　一維裝箱問題[1]來源于人們的長期以來的生產實踐，是一種最優(yōu)化問題，一維裝箱問題具有很高的理論價值和實際價值。</p><p>　　一方面，學者已經證明一維裝箱問題是一個NP難度問題

23、，因此一維裝箱問題具有很高的理論價值。在現(xiàn)實的工業(yè)、商業(yè)、交通、通信、軍事等領域出現(xiàn)了大量的所謂NP難度問題，例如車間調度問題、貨郎擔問題等等。人們雖然目前不能證明，但是強烈相信NP難度問題不存在時間復雜度為多項式的完整算法。所謂完整算法，對于優(yōu)化問題來說就是能保證找到最優(yōu)解的算法，對于判定問題來說就是能夠保證正確判定的算法。</p><p>　　另一方面，一維裝箱問題出現(xiàn)在實際生產的一些領域，因此也具有很高的實

24、際價值。</p><p>　　世界各國學者已經對一維裝箱調度問題做了數(shù)十年的研究，人們還提出了許多種算法來求解一維裝箱調度問題。</p><p>　　另外，在現(xiàn)實中存在二維、三維、多維的裝箱問題。本文僅討論一維裝箱問題。</p><p><b>　　1.2 問題描述</b></p><p>　　本文研究的這種一維裝箱問

25、題的描述如下。給定有窮個物體，每個物體的重量是已知的正實數(shù)。給定足夠多個空箱子，問題是要在滿足兩個約束條件的前提下，將所有物體放到箱子中去，使得所用箱子的個數(shù)盡可能地少。兩個約束條件是：第一，每個物體均保持完整，恰好放到一個箱子中去。不能將物體分割成幾塊。第二，每個箱子中所放的物體的重量之和均不能超過一個相同的上限，這個上限是一個已知的正實數(shù)。</p><p>　　為了將問題描述得確切，本文提出一種形式化描述。&

26、lt;/p><p><b>　　表示物體的集合。</b></p><p><b>　　表示物體的重量。</b></p><p>　　表示每個箱子所能容納的物體的重量之和的上限。</p><p>　　表示所用箱子的集合。</p><p>　　，，是已知的。和是變量。</p&g

27、t;<p>　　問題是要在滿足如下兩個約束條件的前提下，使得所用箱子的個數(shù)盡可能地小。</p><p><b>　　(1.1)</b></p><p><b>　　(1.2)</b></p><p><b>　　其中，。</b></p><p>　　1.3 研究

28、現(xiàn)狀 </p><p>　　當前求解NP難度問題的算法分為兩類：完整算法和近似算法。以一維裝箱問題為例，本文介紹這兩類算法。</p><p>　　完整算法[2]也稱為嚴格算法，其本質是毫無遺漏的窮舉，因此能保證找到問題的最優(yōu)解，這是完整算法的優(yōu)點。完整算法的缺點是計算時間太長，實際部門無法忍受，因此只能用于計算較小規(guī)模的問題實例。</p><p>　　近似算法是

29、當前研究的主要方向。當今時代，在純粹科學研究，通信、交通運輸、工程設計和企事業(yè)管理部門，在社會的軍事、政治和商業(yè)的斗爭中涌現(xiàn)出大量NP難度的問題。若按經典的純粹數(shù)學家們所熟悉的窮舉方法來求解，則計算時間動輒達到天文數(shù)字，根本沒有實用價值。學術界許多有經驗的人認為對于這些問題根本上就不存在完整、精確而不是太慢的求解算法。</p><p>　　于是人們寄希望于非完整的啟發(fā)式算法。啟發(fā)式算法屬于近似算法。這種算法對于很

30、刁鉆古怪的例子可能會失敗，但在通常面臨的實際情況下卻能算得既精確又相當?shù)乜臁?lt;/p><p>　　到哪里去尋求啟發(fā)？這是一個根本的難點。中國古代的畫論有“外師造化內得心源”的說法，即認為智慧應源于大自然與自身的心靈。事實上，自然界中的各種現(xiàn)象以及人類共同生活中的社會經驗，尤其是處理相互關系中許多矛盾的各種公關手腕都是很好的源泉。許多數(shù)學中的概念方法與策略事實上都是來源于人類對大自然的觀察，來源于他們在社會中生存奮

31、斗的社會經驗。</p><p>　　擬物擬人的途徑，本來就是科學的正統(tǒng)，而不是邪門歪道。隨著新的有意義的困難問題例如NP難度問題的涌現(xiàn)，公理化符號化的方法會逐漸顯出自己的不足，樸素的擬物擬人的途徑會逐漸被人們所選用。</p><p>　　特別值得指出的是，對于所得的啟發(fā)式算法，在遇到刁鉆的實例而表現(xiàn)出疲軟失敗的時候，人們可以十分自然地通過分析算法在該次失敗中的表現(xiàn)而對它有針對性地加以改善和

32、強化。經過若干次自然的改善和強化之后，一個從實用角度看來叫人很是滿意的算法就會呈現(xiàn)在我們的面前[3]。</p><p>　　人們或者運用自身的智慧，或者從大自然得到啟發(fā)，同時運用良好的編程技術，經常能設計出很好的近似算法，有可能在較短時間內求解大規(guī)模問題實例，并達到令人滿意的精確度。這種方法被實際部門廣泛的使用。這是一條現(xiàn)實的路線。近似算法主要分為以下幾種類型：</p><p>　?、贁M物

33、算法和擬人算法。擬物算法和擬人算法是黃文奇提出的用于求解NP-hard難度問題的近似算法。擬物方法[4]是一個許多人會感到有趣有用的方法。其工作路徑是，到物理世界中去尋找出與原始數(shù)學問題等價的自然現(xiàn)象，然后觀察其中物質運動的演化規(guī)律，從中受到啟發(fā)以得出形式化的、對于數(shù)學問題的求解算法。單純的擬物方法就已能解決許多問題[5][6]。在遇到刁鉆的問題時還可以將擬物方法和擬人方法聯(lián)合使用形成所謂擬物擬人方法[7]。對其工作的方式可作如下解釋、

34、描敘和評論。</p><p>　　由于物理狀態(tài)的演化天然地是按照使其Lagange函數(shù)的時間積分達到最小值的方式進行，這就決定了擬物算法最終在數(shù)學上落實為優(yōu)化問題。然而用數(shù)學方法求解優(yōu)化問題，常常會碰到計算落入局部極小值陷阱的困難境地，對于如何跳出局部極小值陷阱，讓計算走向前景更好的區(qū)域中去的問題，擬物方法已無能為力。但是，人類在最近幾千年的共同生活中形成了豐富的社會經驗，利用這些經驗往往可以啟發(fā)出好的“跳出陷阱

35、”的策略。我們可以將這種把人類的社會經驗形式化為算法用以求解某些特殊困難問題的數(shù)學問題的方式稱為擬人途徑[8]。</p><p>　　擬物擬人算法的效率通常比生物遺傳算法、神經網(wǎng)絡算法、淬火算法要高，其原因是它有針對性地為具體問題找到了非常貼切的物理世界，而不是像在遺傳、神經網(wǎng)絡、淬火方法中那樣依賴于一個惟一的始終不變的因而往往是不太貼切的物理體系。另外，擬人方法是向人學習，而人比遺傳、神經網(wǎng)絡、淬火世界里的那些

36、蛋白質、單個的神經元及晶體顯然有高得多的智慧。當然，這里的關鍵在于合適的數(shù)學形式化前夜的藝術和手段，要得到它們也不是一件很容易的事情，需要長期艱苦細心的工作。這種得出算法的過程的艱苦性，可以說是擬物擬人途徑的一個缺點。</p><p>　　另外，生物遺傳算法、神經網(wǎng)絡法、淬火法雖然針對性較差，但其適應性較強，并且亦有其深刻的思想根源和自然背景。在肯動腦筋并且機遇好的時候，擬物擬人與生物遺傳算法、神經網(wǎng)絡法、淬火法

37、能結合得很好，能產生新的效能更高的算法。</p><p>　　至于純粹的擬人方法[9][10]，其途徑是將人類在最近幾千年的生存斗爭中所形成的某些經驗某些作法說完整說清楚，然后加以抽象化形式化，最后形成算法以求解NP難度問題。</p><p>　　此方法的關鍵難點在于為給定的NP難度問題找到相應的有悠久歷史的人類活動。但是一旦找到，必然能很順利地發(fā)展為高效能的求解算法。</p>

38、<p>　?、趦?yōu)先分配規(guī)則算法。人們最早提出的求解一維裝箱問題的近似算法是優(yōu)先分配規(guī)則算法。優(yōu)先分配規(guī)則算法以某種優(yōu)先序依次給定將所有物體裝入某個箱子。優(yōu)先分配規(guī)則算法的速度非常快，但是其生成解的質量仍有改進的余地。因為優(yōu)先分配規(guī)則算法速度很快，所以很多學者采用優(yōu)先分配規(guī)則算法來生成初始解。本文介紹降序首次適合算法（first fit decreasing）和降序最佳適合（best fit decreasing）算法。降序

39、首次適合算法是將所有物體按照重量從大到小的順序排成一個物體序列，然后依次取出序列中的一個物體，在所有能放下這個物體的箱子中，選取序號最小的箱子，把物體放進去。降序最佳適合算法是將所有物體按照重量從大到小的順序排成一個物體序列，然后依次取出序列中的一個物體，在所有能放下這個物體的箱子中，選取空余最小的箱子，把物體放進去。</p><p>　?、劬植克阉?local search)算法。局部搜索算法給出的解的質量比優(yōu)

40、先分配規(guī)則算法高。局部搜索算法的工作過程是一個迭代的過程：從初始給定的解開始，所有物體裝在有窮個箱子中。取出第一個箱子中的所有物體，裝入其他箱子。此時某些箱子可能會超重，這是一個格局，稱為一個點。然后在與當前格局相近的格局集合(即當前點的鄰域)中搜索比當前格局更好的格局。如果在鄰域中找到了比當前格局更好的格局，那么接受這個更好的格局，然后繼續(xù)做迭代。如果當前格局的鄰域中沒有比當前格局更好的格局，也就是說，當前格局是局部最優(yōu)解，那么算法停

41、機。具體來說，有兩種搜索策略。第一種搜索策略叫做 “見好就收”：檢查當前格局的鄰域，一旦找到比當前格局好的格局，就接受這個格局，這樣就做完了一次迭代，然后繼續(xù)做迭代；如果當前格局的鄰域中沒有比當前格局更好的格局，那么鄰域搜索停止。第二種搜索策略是找到鄰域中最好的格局，如果比當前格局好，就接受這個格局，這樣就做完了一次迭代，然后繼續(xù)做迭代；如果當前格局的鄰域中沒有比當前格局更好的格局，那么鄰域搜索停止。當鄰域搜索停止時，如果對應一個解，則

42、接受這個解，繼續(xù)從新解開始做鄰域搜索。如果不對</p><p>　?、芙伤阉?tabu search)算法。禁忌搜索算法是基于局部搜索的一種算法，它可以看作是局部搜索算法的一種改進算法。禁忌搜索算法由Glover[11]提出。禁忌搜索算法可用于求解各種組合優(yōu)化問題人們已經提出了多種求解一維裝箱問題的禁忌搜索算法[12]。禁忌搜索算法生成解的質量較高。禁忌搜索算法的工作過程是一個迭代的過程。從初始給定的解開始，所

43、有物體裝在有窮個箱子中。取出第一個箱子中的所有物體，裝入其他箱子。此時某些箱子可能會超重，這是一個格局，稱為一個點。然后在與當前格局相近的格局集合(即當前點的鄰域)中搜索比當前格局更好的格局。算法找到當前格局的鄰域中目標函數(shù)值最小的格局，不論這個格局的目標函數(shù)值是否比當前格局小，都接受這個格局。這樣就做了一次迭代。然后繼續(xù)做迭代。像這樣做迭代，很容易陷入循環(huán)。為了防止循環(huán)，禁忌搜索算法設置一個名為禁忌表的數(shù)據(jù)結構。禁忌表中記錄著在最近若

44、干次迭代中訪問過的格局，如果這些格局在當前格局的鄰域中，那么就把它們從鄰域中清除掉。這樣就能夠在一定程度上避免循環(huán)，從而提高搜索效率。因為禁忌搜索會接受比當前格局差的格局，所以它能夠跳出局部最優(yōu)點。當禁忌搜索因為</p><p>　　⑤模擬退火算法。模擬退火算法也是基于局部搜索的一種算法。模擬退火算法也可用于求解各種組合優(yōu)化問題，包括一維裝箱問題[13]。模擬退火算法檢查當前格局的鄰域中的格局，如果鄰域中的這個格

45、局比當前格局好，則一定接受這個格局；否則以一個大于0 同時小于1 的概率接受這個格局。與禁忌搜索算法一樣，模擬退火算法也能跳出局部最優(yōu)點。</p><p>　?、捱z傳算法。遺傳算法可用于求解一維裝箱問題[14]。遺傳算法的工作過程也是迭代的過程。與局部搜索算法、禁忌搜索算法和模擬退火算法不同的是，遺傳算法是將當前一組格局更新為另外一組格局，而不是將當前一個格局更新為另外一個格局。遺傳算法首先隨機生成一組格局做為所

46、謂初始種群，然后對種群做迭代：從當前種群(當前這組格局)中選擇一些格局，對這些格局做遺傳操作(交叉、變異等)，從而得到一組新的格局(即一個新的種群)。</p><p>　　1.4 本論文的主要結構</p><p>　　本學位論文主要由五個部分組成，其內容具體安排如下：</p><p>　　第一部分是緒論。主要介紹了本課題的來源、選題背景、問題描述和論文的主要結構。

47、</p><p>　　第二部分介紹算法描述。</p><p>　　第三部分介紹程序設計。</p><p>　　第四部分介紹程序運行的結果。</p><p>　　第五部分是本課題研究的結論。</p><p><b>　　2 算法描述</b></p><p>　　人類把物體往

48、容器中裝，已有幾千年以上的經驗。我們可以利用這些生活經驗來發(fā)展出高效率的算法。</p><p>　　本文提出的這種算法是一種擬人算法。算法由三個部分組成。第一部分是降序最佳適合算法（best fit decreasing）用于生成初始解。第二部分是鄰域搜索算法。給定一個解，用鄰域搜索算法可以通過迭代改進這個解。第三部分是跳坑策略。跳坑用于跳出局部最優(yōu)解，將搜索引向有希望的區(qū)域，從而提高算法的效率。算法三個部分的思

49、想來源均為人類的生產和生活經驗，本算法是由擬人途徑得到的。</p><p>　　定義2.1 某些物體在箱子里，其余物體在箱子外，這稱為一個格局。</p><p>　　初始格局是所有物體均在箱子外，所有箱子均為空。與初始格局對稱的終止格局是所有物體均在箱子里。</p><p>　　終止格局的形式化描述為：整數(shù)變元，…，的一組指派表示一個終止格局，其中表示物體放在箱子

50、中，，。把對整數(shù)變元，…，的一組指派看成空間中的一個點，將與點在一個、兩個或更多個變元上取值不同的點的集合稱為的鄰域。</p><p>　　考慮一個終止格局，如果每個箱子中所裝的物體的重量之和均不超過上限，則此終止格局對應著一個解。</p><p>　　2.1 擬人算法的大致框架</p><p>　　步驟一（初始解的生成）：調用一種簡單好想的構造型算法生成初始解。

51、該構造型算法見2.2節(jié)。轉步驟二。</p><p>　　步驟二（判斷停機條件）：判斷停機條件是否滿足，若滿足則停機，輸出本次計算過程中所找到的最好的解。若不滿足停機條件，則轉步驟三。停機條件恰有兩個：第一，客觀最優(yōu)解已經找到。第二，跳坑次數(shù)已經達到上限。只要滿足其中一個條件，則算法停機。</p><p>　　步驟三（鄰域搜索）：從當前解出發(fā)，調用鄰域搜索算法進行計算，試圖尋找一個比當前解更

52、好的解。該鄰域搜索算法見2.3節(jié)和2.4節(jié)。鄰域搜索算法執(zhí)行完畢后，轉步驟二。</p><p>　　2.2 生成初始解</p><p>　　步驟一：開局。將所有物體按照重量從大到小的順序排好序。這個物體序列記為。所有物體均在箱子外面。將物體放在箱子中。轉步驟二。</p><p>　　步驟二：考慮當前格局。如果所有物體均在箱子里面，則生成了初始解。如果至少有一個物體

53、在箱子外面，則按照如下手法將一個物體放入箱子。在當前格局中，物體在箱子里，物體在箱子外。如果箱子中的每一個均不能容納，則將放入箱子。如果箱子中的若干個箱子能容納，則選取在當前格局空余最小的箱子（如果空余最小的箱子不止一個，則選取其中編號最小的箱子），將放入，從而演化到新格局。轉步驟二。</p><p><b>　　2.3 鄰域搜索</b></p><p>　　本文提

54、出的鄰域搜索的思路來源于人們用箱子裝物體的實際經驗。當個物體裝在個箱子中，首先任意取一個裝了物體的箱子，取出其中全部物體，裝到其它已裝有物體的箱子中去。此時很可能有某些箱子中的物體重量超過上限。然后根據(jù)某種方法進行調整，試圖使得每個箱子中的物體重量均不超過上限。最終鄰域搜索的結果恰有兩種：或者成功，或者失敗。</p><p>　　步驟一：考慮當前解。將當前解的格局記錄下來，記為。物體放在箱子中。令。轉步驟二。&l

55、t;/p><p>　　步驟二：如果，則鄰域搜索結束。如果，則取出箱子中的所有物體，將的編號改為，…，將的編號改為。按照從重量大到小的順序，依次將物體放入已裝物體重量之和最小的箱子（如果已裝物體重量之和最小的箱子不止一個，則選取序號小的箱子），從而演化到新格局。如果無超重的箱子，則新格局是一個解。將這個解作為當前解，鄰域搜索結束。如果有超重的箱子，無不滿的箱子，則當前解是客觀上的最優(yōu)解，停機。如果既有超重的箱子，又有不

56、滿的箱子，則轉步驟三。</p><p>　　步驟三：進行調整。如果經過調整后，得到了一個比當前解更好的解，則接受這個解，鄰域搜索結束。如果沒有找到一個比當前解更好的解，則返回到當前解的格局。。轉步驟二。</p><p>　　所謂調整，是一個迭代的過程。已知一個終止格局，用一個新的終止格局取代老的終止格局，這是迭代的一步。</p><p>　　在敘述如何進行迭代之前，

57、要給出鄰域的定義。</p><p>　　取一個超重的箱子，記為。取一個不滿的箱子，記為?，F(xiàn)在要將中的若干物體放入中，將中的若干物體放入中。目的是要減輕中物體的重量，增加中物體的重量。中國人有句格言“天之道損有余而補不足[15]”。我們所設計的鄰域是基于這句格言的。</p><p>　　我們采用的目標函數(shù)是由Fleszar和Hindi[16]提出的目標函數(shù)。給定一個終止格局，目標函數(shù)值等于所

58、有箱子中的物體重量的平方的和。調整的目的是要在所用箱子數(shù)不變的前提使得目標函數(shù)值盡可能地小。形式化描述如下：</p><p>　　minimize (2.1)</p><p>　　其中是所用箱子數(shù)，是箱子中所裝物體重量。</p><p>　　對于點，是的一個鄰點。若，則稱為

59、的鄰域中的下降點。</p><p>　　第一種鄰域記為。將超重的箱子中的一個物體取出放入不滿的箱子。</p><p>　　第二種鄰域記為。將超重的箱子中的一個物體與不滿的箱子中的一個物體交換。</p><p>　　第三種鄰域記為。將超重的箱子中的一個物體與不滿的箱子中的兩個物體交換。</p><p>　　第四種鄰域記為。將超重的箱子中的一個物

60、體與不滿的箱子中的三個物體交換。</p><p>　　可以推廣到,...,，其中是箱子中所裝的物體個數(shù)。</p><p>　　因為有了，則不必考慮?？梢杂脙纱稳〈?。</p><p>　　第五種鄰域記為。將超重的箱子中的兩個物體與不滿的箱子中的一個物體交換。</p><p>　　第六種鄰域記為。將超重的箱子中的兩個物體與不滿的箱子中的兩個物體交

61、換。</p><p>　　可以推廣到,...,，其中是箱子中所裝的物體個數(shù)。</p><p>　　Loh，Golden和Wasil[1]提出了兩種鄰域和。Fleszar和Hindi[16]提出了兩種鄰域和。本文提出的鄰域與這些鄰域類似。差別在于本文考慮一個超重的箱子和一個不滿的箱子。文獻[1][16]考慮任意兩個箱子。已知一個點，考慮其鄰域，若一個鄰點對應的目標函數(shù)值嚴格小于當前點對應的目

62、標函數(shù)值，則這個點稱為下降點。</p><p>　　微調的思路如下所述。</p><p>　　第一，從一個給定的終止格局開始，這是初始點。</p><p>　　第二，設在任一時刻的值已算出，首先按照某種自然的順序依次考慮當前點的鄰點。若下降點集非空，則用第一個下降點作為在時刻的值。我們將這種從到的過渡稱為下降步驟。若下降點集為空，則已知點為函數(shù)的局部最小值點，于是按

63、照某種基于擬人思路的“跳坑”策略將計算從點跳到其鄰域中的一個確定的新點。我們可將這種從到的過渡稱為逃出步驟。</p><p>　　以上思路雖然是本質的，但有一個小漏洞需要補平。即在逃出步驟中，若點按照跳坑策略逃出到，則很可能從的角度來看，老點是的鄰域中的下降點，于是很有可能從出發(fā)的下降步驟是回到。即計算走了回頭路。</p><p>　　為補平這一漏洞，我們可以設置變元禁集。這樣，我們的尋優(yōu)

64、搜索的思路框架被發(fā)展為如下步驟：</p><p>　　步驟一：從一個給定的終止格局開始，這是初始點。將變元禁集之初始集賦為空集。轉步驟二。</p><p>　　步驟二：考慮當前點的鄰域。有些鄰點是由對禁集中的變元賦值而得到的。除去這樣的鄰點不考慮。按照某種自然的順序考察鄰域，如果找到了一個下降點，則見好就收，接受此下降點。如果對鄰域搜索完畢，沒有找到下降點，則按跳坑策略跳到一個點。轉步驟三

65、。</p><p>　　步驟三：若當前點對應一個解，則停止。若計算時間已超限，則停止。否則更新變元禁集。</p><p>　　以下我們描述跳坑策略和更新變元禁集的步驟。</p><p><b>　　2.4 跳坑策略</b></p><p>　　當前點為局部最小值點，在所有超重的箱子中均勻地隨機選取一個箱子，在這個箱子中

66、的所有物體中均勻地隨機選取一個物體，在所有不滿的箱子中均勻地隨機選取一個箱子，將從中取出，放入。</p><p>　　這個跳坑策略的思想來源依然是“天之道損有余而補不足”。</p><p>　　變元禁集的演化規(guī)則如下：</p><p>　　第一，如果從老點到是按下降步驟操作的，則置變元禁集為空。</p><p>　　第二，如果從老點到是按逃出

67、步驟操作的，則將對應的變元加入變元禁集。</p><p><b>　　3 程序設計</b></p><p>　　本文的程序設計采用已故卓越美籍荷蘭裔計算機科學家Edsger Wybe Dijkstra提出的結構化程序設計思想。</p><p>　　Edsger Wybe Dijkstra早在1951年就學習了計算機程序設計，然后參與了一些荷蘭

68、的大工程例如Fokker友誼飛機的開發(fā)，其中機翼震動的計算需要編寫程序。因為編寫龐大程序的需要，Edsger Wybe Dijkstra提出了結構化程序設計思想。</p><p>　　結構化程序設計可歸納為“自頂向下，逐步求精”。結構化程序設計由計算機科學家提出，但是其思想根源并不是純粹科學，而是人類在長期生存斗爭中的經驗。軍事家提出“分而治之”，“集中優(yōu)勢兵力，各個殲滅敵人”。這些說法是結構化程序設計思想的來源

69、。在軍事上，如果敵人多而且強，則設法將敵人分割，集中兵力和火力將敵人各個殲滅。作者在寫程序時，如果程序難而且復雜，不好寫，則首先將程序分成一些模塊，然后集中思維和時間去寫每一個模塊的程序。</p><p>　　所謂“自頂向下”是指首先將程序分割為幾個大模塊，從而寫出主函數(shù)main()的程序，然后對復雜的大模塊，再分割成若干小模塊，如果小模塊仍然較復雜，則依此類推，繼續(xù)分割，直到小模塊容易被編程者寫出程序為止。&l

70、t;/p><p>　　所謂“逐步求精”是指在分割程序的過程中，程序的面貌越來越清晰，針對每個小模塊，寫出清晰的程序。最終將所有模塊合并，成為所需要的完整的程序。</p><p>　　作者對面向對象的程序設計也曾經淺嘗。結構化程序設計思想與面向對象的程序設計思想并無實質性矛盾，在需要引入對象概念的場合，這兩者可以很好地結合。例如可以采用結構化程序設計來寫底層的核心的程序，采用面向對象的程序設計來

71、設計外表的吸引人的界面。</p><p><b>　　3.1 程序流程</b></p><p>　　整個程序的流程如圖3.1所示。整個程序可分為四個模塊。</p><p>　　第一個模塊是讀取文本文件中問題實例的數(shù)據(jù)，調用庫函數(shù)malloc()為各種數(shù)據(jù)結構分配內存。這個模塊的程序簡單，無需再分解。</p><p>　

72、　第二個模塊是生成初始解。這個模塊的程序較簡單，無需再分解。</p><p>　　第三個模塊是鄰域搜索。這個模塊是重點，程序復雜，本身需分成一些更小的模塊。</p><p>　　第四個模塊是釋放內存。這個模塊的程序最簡單，只需調用庫函數(shù)free()就可以，無需再分解。</p><p>　　圖3.1 整個程序的流程</p><p>　　作者寫程

73、序時遵循如下四條原則。</p><p>　　第一，要有整塊的時間來寫程序，不要煩，不要急。</p><p>　　第二，要有好的草稿紙，舉個例子，畫圖輔助自己寫程序。</p><p>　　第三，草稿紙要寫得干凈，不要折，寫上頁碼，作為原始文檔好好保存。</p><p>　　第四，自頂向下，逐步求精。</p><p>　　

74、3.1.1 讀取文本文件中的數(shù)據(jù)</p><p>　　一個benchmark問題實例存儲在一個文本文件中，以名為TEST0005的問題實例為例，存儲在名為TEST0005.txt的磁盤文件中，其格式如下。</p><p>　　第1行：57表示物體的重量總共恰有57種不同的重量。</p><p>　　第2行：10000表示箱子的容量是100

75、00。</p><p>　　第3行：49643表示重量為4964的物體恰有3個。</p><p><b>　　依此類推。</b></p><p>　　第59行：402表示重量為40的物體恰有2個。</p><p>　　在C語言中，要讀取文本文件中的數(shù)據(jù)，首先定義一個FILE類型的指針FP，然后利

76、用庫函數(shù)fopen()來打開文件，例如FP = fopen("e:\\TEST0005.txt","r")，其中e:\\TEST0005.txt是文本文件所在目錄以及文件名，r表示以只讀方式打開文件，最后利用庫函數(shù)fscanf()文件指針,格式字符串，變量地址)來讀取文本文件中的數(shù)據(jù)，例如fscanf(FP,"%d",&numberOfDifferentItemWeig

77、hts)表示讀取FP指針指向的文本文件中一個符號串，將其轉化為十進制整數(shù)，存儲在變量numberOfDifferentItemWeights中。</p><p>　　本文的程序采用庫函數(shù)malloc()來給數(shù)據(jù)分配內存。與之對稱地，當程序運行結束的前夕，調用庫函數(shù)free()來釋放用malloc()分配的內存。</p><p>　　本模塊中使用的主要數(shù)據(jù)結構如下。</p>&

78、lt;p>　　int NUMBER_M_OF_DIFFERENT_ITEM_WEIGHTS表示物體總共有多少種不同的重量。</p><p>　　int CAPACITY_C_OF_THE_BINS表示箱子容量。</p><p>　　int * ITEM_WEIGHTS是整型數(shù)組名，此數(shù)組記錄所有不同的重量的值。</p><p>　　int * NUMBER_O

79、F_ITEMS_OF_WEIGHTS是整型數(shù)組名，此數(shù)組記錄每種重量的物體有多少個。</p><p>　　int NUMBER_OF_ITEMS表示物體總數(shù)。</p><p>　　int * WEIGHT_OF_ITEMS是整型數(shù)組名，此數(shù)組記錄每個物體的重量。</p><p>　　NUMBER_M_OF_DIFFERENT_ITEM_WEIGHTS，CAPACIT

80、Y_C_OF_THE_BINS，ITEM_WEIGHTS，NUMBER_OF_ITEMS_OF_WEIGHTS是題目給定的，可以直接從文本文件中讀取。NUMBER_OF_ITEMS，WEIGHT_OF_ITEMS可以根據(jù)已知的信息算出。</p><p>　　3.1.2 生成初始解</p><p>　　生成初始解的函數(shù)命名為generate_initial_solution()。此模塊中所

81、使用的主要數(shù)據(jù)結構如下。</p><p>　　int * BIN_NUMBER_OF_ITEMS記錄在初始解中，每個物體放在哪個箱子中。</p><p>　　int * SPARE_SPACE_OF_BINS記錄每個箱子的剩余空間。</p><p>　　int NUMBER_OF_OCCUPIED_BINS表示使用的箱子數(shù)。</p><p>

82、　　int ** ITEMS_NUMBER_IN_EACH_BIN是二維整型數(shù)組名，其中記錄每個箱子中放了哪些物體。</p><p>　　程序生成初始解后，將初始解作為當前解。有_IN_CURRENT_SOLUTION_PATTERN后綴的變量是屬于對應當前解的終止格局的。</p><p>　　int * BIN_NUMBER_OF_ITEMS_IN_CURRENT_SOLUTION_PA

83、TTERN表示在對應當前解的終止格局中，每個物體放在哪個箱子中。</p><p>　　int NUMBER_OF_OCCUPIED_BINS_IN_CURRENT_SOLUTION_PATTERN表示在當前解中使用的箱子數(shù)。</p><p>　　int ** ITEMS_NUMBER_IN_EACH_BIN_IN_CURRENT_SOLUTION_PATTERN是二維整型數(shù)組，其中記錄在當

84、前解中每個箱子中放了哪些物體。</p><p>　　int * LOAD_OF_EACH_BIN_IN_CURRENT_SOLUTION_PATTERN記錄在當前解中每個箱子中物體的重量之和。</p><p>　　INCREASING_SEQUENCE_OF_BINS_BY_LOAD_IN_CURRENT_SOLUTION_PATTERN是一個整型數(shù)組，其中記錄在當前解中箱子按照重量從小到

85、大的序列。</p><p>　　3.1.3 鄰域搜索</p><p>　　鄰域搜索函數(shù)命名為local_search()。此模塊中所使用的主要數(shù)據(jù)結構如下。</p><p>　　有_IN_CURRENT_FINAL_PATTERN后綴的變量是屬于當前終止格局的，很可能并不對應一個解。</p><p>　　int * BIN_NUMBER_O

86、F_ITEMS_IN_CURRENT_FINAL_PATTERN表示在當前終止格局中使用的箱子數(shù)。</p><p>　　int NUMBER_OF_OCCUPIED_BINS_IN_CURRENT_FINAL_PATTERN是二維整型數(shù)組，其中記錄在當前終止格局中每個箱子中放了哪些物體。</p><p>　　int ** ITEMS_NUMBER_IN_EACH_BIN_IN_CURREN

87、T_FINAL_PATTERN表示在當前終止格局中，每個物體放在哪個箱子中。</p><p>　　int * LOAD_OF_EACH_BIN_IN_CURRENT_FINAL_PATTERN記錄在當前終止格局中每個箱子中物體的重量之和。</p><p>　　INCREASING_SEQUENCE_OF_BINS_BY_LOAD_IN_CURRENT_FINAL_PATTERNint 是一

88、個整型數(shù)組，其中記錄在當前終止格局中箱子按照重量從小到大的序列。</p><p>　　3.1.4 釋放內存</p><p>　　釋放函數(shù)命名為free_memory()。此函數(shù)調用庫函數(shù)free()來釋放用庫函數(shù)malloc()分配的內存空間。</p><p>　　以ITEMS_NUMBER_IN_EACH_BIN為例，此二維數(shù)組所占用的內存是采用malloc(

89、)函數(shù)分配的。程序如下：</p><p>　　ITEMS_NUMBER_IN_EACH_BIN = (int **)malloc(sizeof(int *) * (NUMBER_OF_OCCUPIED_BINS+1));</p><p>　　for(j=1; j<=NUMBER_OF_OCCUPIED_BINS; j++)</p><p>　　ITEMS_NU

90、MBER_IN_EACH_BIN[j] = (int *)malloc(sizeof(int) * (MAXIMAL_NUMBER_OF_ITEMS_IN_A_BIN+1));</p><p>　　在釋放二維數(shù)組的內存時，程序應為：</p><p>　　for(j=1; j<=NUMBER_OF_OCCUPIED_BINS; j++)</p><p>　　fr

91、ee(ITEMS_NUMBER_IN_EACH_BIN[j]);</p><p>　　free(ITEMS_NUMBER_IN_EACH_BIN);</p><p><b>　　3.2 調試程序</b></p><p>　　在調試程序的過程中，作者遵循的四條原則如下。</p><p>　　不熬夜，保證在腦筋清醒的狀態(tài)下

92、調試程序。</p><p>　　用折半查找，找到第一個出錯的地方。</p><p>　　第三，用放大鏡仔細看第一個出錯的地方，也就是顯示各個變量的值，就能看出錯在哪里。</p><p>　　第四，將調試過程中發(fā)現(xiàn)的錯誤以及改正的手段記錄在紙上作為原始文檔以備忘。</p><p>　　作者在調試本文的程序時所找出并糾正的錯誤按順序列舉如下。&l

93、t;/p><p>　　① local_search()函數(shù)中一個for循環(huán)沒有用花括號將循環(huán)體括起來。</p><p>　?、?將箱子按照重量從小到大排序的算法有錯，改為用冒泡排序的算法。</p><p>　?、?generate_initial_solution()函數(shù)生成初始解后，要將其信息記錄在各種數(shù)據(jù)結構中。最初版的程序沒有記錄這些信息，從而導致出錯。</

94、p><p>　?、?swap_one_zero()函數(shù)中，從一個超重的箱子取一個物體放在一個不滿的箱子中，需修改這兩個箱子的重量值，然后更新箱子按照重量從小到大排序的序列。更新序列的程序有錯，交換兩個數(shù)組元素的值時寫錯了。</p><p><b>　　4 計算結果</b></p><p>　　我用C語言編程序實現(xiàn)了本文提出的算法。編譯器是微軟公司

95、的Visual C++ 6.0。我采用最快速度選項來編譯源程序。程序在CPU為AMD 3.0 GHz的個人電腦上運行。</p><p>　　本文的程序計算了一組共17個benchmark問題實例。這17個benchmark問題實例由Wäscher 和 Gau 于1996年提出。這組問題實例可通過網(wǎng)絡下載，網(wǎng)址為http://paginas.fe.up.pt/~esicup/index.php。</

96、p><p>　　這17個實例可分為兩類。第一類有8個問題實例名為TEST0005、TEST0014、TEST0022、TEST0030、TEST0058、TEST0065、TEST0068、TEST0082，目前尚未確定其客觀最優(yōu)解。第二類有9個問題實例名為TEST0044、TEST0049、TEST0054、TEST0055_52、TEST0055_64、TEST0075、TEST0084、TEST0095、TES

97、T0097，目前已經確定了其客觀最優(yōu)解。</p><p>　　第一類8個問題實例的計算結果見表5.1。本文的程序標記為擬人算法。在這一組共8個benchmark問題實例中，擬人算法對6個問題實例找出了與當前最好解質量相同的解。擬人算法還證明了TEST0068這個benchmark問題實例的目前已知最好解正是客觀最優(yōu)解。在表5.1中以粗體顯示TEST0068的計算結果。</p><p>　　

98、表5.1 擬人算法對Wäscher 和 Gau提出的尚未確定客觀最優(yōu)解的8個實例的計算結果</p><p>　　TEST000529 29 0.22</p><p>　　TEST001424 24 0.14</p><p>　　T

99、EST002215 15 0.05</p><p>　　TEST003028 28 0.22</p><p>　　TEST005820 21 0.10</p><p>　　TE

100、ST006516 16 0.06</p><p>　　TEST006812 12 0.03</p><p>　　TEST008224 25 0.16</p><p>　　第二類

101、9個問題實例的計算結果見表5.2。擬人算法找到了全部9個問題實例的客觀最優(yōu)解。</p><p>　　表5.2 擬人算法對Wäscher 和 Gau提出的已經確定客觀最優(yōu)解的9個實例的計算結果</p><p>　　TEST004414 14 0.03</p><p>　　TEST004911

102、 11 0.01</p><p>　　TEST005414 14 0.05</p><p>　　TEST0055_5215 15 0.03</p><p>　　TEST0055_6

103、420 20 0.04</p><p>　　TEST007513 13 0.02</p><p>　　TEST008416 16 0.04</p><p>　　TEST0095

104、16 16 0.03</p><p>　　TEST009712 12 0.01</p><p><b>　　5 結論</b></p><p>　　一維裝箱問題具有很高的理論價值和實踐價值。一維裝箱問題是一種NP難度問

105、題，因此具有很高的理論價值。一維裝箱問題在生產實踐中有應用，因此也具有很高的實踐價值。如果能夠設計出求解一維裝箱問題的高效算法，就能提高生產效率。</p><p>　　數(shù)十年來，世界各國學者對一維裝箱問題做了廣泛而又深入的研究。求解一維裝箱問題的分為完整算法和近似算法兩類。完整算法的本質是毫無遺漏的窮舉，雖然能保證找到問題的最優(yōu)解，但是計算時間太長，實際部門無法忍受，因此只能用于計算較小規(guī)模的問題實例。</

106、p><p>　　近似算法是當前研究的主要方向。我們深入細致地研究了一維裝箱問題，提出了一種求解一維裝箱問題的擬人算法，此算法屬于近似算法。</p><p>　　擬人方法的工作途徑是將人類在最近幾千年的生存斗爭中所形成的某些經驗某些做法說完整說清楚。對于裝箱，人類有超過幾千年的生活經驗。</p><p>　　本文的算法主要基于鄰域搜索和跳坑策略。本文的鄰域定義的思想來源是

107、“天之道損有余而補不足”。具體策略是把超重的箱子中的物體取出放到不滿的箱子中去。當鄰域搜索遇到局部最優(yōu)解時，本文采用所謂跳坑策略跳出局部最優(yōu)解，將搜索引向有希望的方向。跳坑策略的思想來源是“三十六計走為上”。中國老百姓的這兩句格言暗示作者，使得作者順利地得到了本文的算法。</p><p>　　檢驗算法的辦法有兩種：理論分析和實驗測試。對于求解困難問題的較為有效的算法，絕對嚴格的理論分析（包括算法的精度的分析和算法

108、復雜度的分析兩個方面）經常是既做不到又無必要。因此當前國際上對于求解NP難度問題的算法的檢驗主要采用實驗測試。</p><p>　　本文采用實驗測試的辦法來檢驗算法。本文的算法計算了一組共17個benchmark問題實例，這組問題實例分為兩類。第一類為8個問題實例，目前尚未確定其客觀最優(yōu)解。第二類為9個問題實例，目前已經確定了其客觀最優(yōu)解。擬人算法對第一類問題實例中的6個問題實例找出了與當前已知最好解質量相同的解