中北大學2014屆畢業設計說明書頁1引言社會在進步，科技在發展，我們將越來越多的科技產品運用于生產，服務大眾之中，這極大的推動了人們的生活水平，提高了生活的質量。然而，當高端的生產水平遇到老舊的調度方式的時候，造成了一系列低水準的結果。調度是指管理并安排，調度系統則是指在考慮到系統運行時在不同階段的損耗，消耗時間不同的因素下，通過一定的調度方法，策略，從而實現對所研究系統正常運行的最少消耗，路程等[1]。調度系統的使用，提高了處理問題的能力，效率，同時也明顯的減少了資源的損耗。然而，現有的調度系統是存在有一定的缺陷的，以在多個相連地點中尋求任意兩點相連的最短路徑為例，當地點數較少時，我們可以挨個嘗試進而進行比較得出最優解，可是當地點數大到一定程度的時候，窮舉法就不現實了[2]。這正是調度系統也存在的問題，我們既要求調度系統做出正確的路徑，同時要求它在有效的時間做出，這就顯然成為了矛盾的所在。沒有窮舉過自然就無法說某條路徑是最優的，因此折中的辦法就是在有限的時間里，找到一條較優的路徑，而這些正是本課題所研究的。2課題背景2.1什么是調度系統 調度系統是指應用于生產生活中的通過一定的調度算法實現對目標流程的安排及控制，以期望達到減少損耗，提高效率的目的的系統，隨著社會科學技術的飛速發展，人們對高效率生產流程的期待，加速著調度系統的進步。而在調度系統中，調度算法又占到了絕對重要點的比率。因此，一個好的調度系統更多又體現在其使用的調度算法是否適用于對應生產的要求，并需在合理的時間內給出設計。2.2禁忌算法的概念搜索是人工智能的一個基本問題，一個問題的求解過程就是搜索。人工智能在各應用領域中，被廣泛的使用。現在，搜索技術滲透在各種人工智能系統中，可以說沒有哪一種人工智能的應用不用搜索方法[3]。禁忌搜索算法(TabuSearch或TabooSearch,簡稱TS)的思想最早由Glover(美國工程院院士，科羅拉多大學教授)在1977年提出，它是對局部鄰域搜索的一種擴展，是一種全局鄰域搜索算法，是人工智能的一種體現，是一種全局逐步尋優算法，是對人類智力過程的一種模擬。TS算法通過引入一個靈活的存儲結構和相應的禁忌準則來避免迂回搜索，并通過藐視準則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效探索以最終實現全局優化[4]。迄今為止，TS算法在組合優化、生產調度、機器學習、電路設計和神經網絡等領域取得了很大的成功，近年來又在函數全局優化方面得到較多的研究，并大有發展的趨勢。2.3鄰域搜索局部鄰域搜索是基于貪婪思想持續地在當前的鄰域中進行搜索，雖然算法通用易實現，且容易理解，但其搜索性能完全依賴于鄰域結構和初始解，尤其容易陷入局部極小而無法保證全局優化性。這種鄰域搜索方法容易實現理解，容易實現，而且具有很好的通用性，但是搜索結果完全依賴于初始解和鄰域的結構，而且只能搜索到局部最優解。為了實現全局搜索，禁忌搜索采用允許接受劣解來逃離局部最優解[5]。針對局部領域搜索，為了實現全局優化，可嘗試的途徑有：以可控性概率接受劣解來逃逸局部極小，如模擬退火算法；擴大領域搜索結構，如TSP的2-opt擴展到k-opt；多點并行搜索，如進化計算；變結構領域搜索（Mladenovicetal,1997）；另外，就是采用TS的禁忌策略盡量避免迂回搜索，它是一種確定性的局部極小突跳策略。3禁忌搜索算法3.1算法基本思想禁忌搜索算法的基本思想就是在搜索過程中將近期的歷史上的搜索過程存放在禁忌表（TabuList）中，阻止算法重復進入，這樣就有效地防止了搜索過程的循環。禁忌表模仿了人類的記憶功能，禁忌搜索因此得名，所以稱它是一種智能優化算法[6]。具體的思路如下：禁忌搜索算法采用了鄰域選優的搜索方法，為了能逃離局部最優解，算法必須能夠接受劣解，也就是每一次迭代得到的解不必一定優于原來的解。但是。一旦接受了劣解，迭代就可能陷入循環。為了避免循環，算法將最近接受的一些移動放在禁忌表中，在以后的迭代中加以禁止。即只有不在禁忌表中的較好解（可能比當前解差）才能接受作為下一次迭代的初始解。隨著迭代的進行，禁忌表不斷更新，經過一定迭代次數后，最早進入禁忌表的移動就從禁忌表中解禁退后。為了找到“全局最優解”，就不應該執著于某一個特定的區域。局部搜索的缺點就是太貪婪地對某一個局部區域以及其鄰域搜索，導致一葉障目，不見泰山。禁忌搜索就是對于找到的一部分局部最優解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區間。兔子們找到了泰山，它們之中的一只就會留守在這里，其他的再去別的地方尋找。就這樣，一大圈后，把找到的幾個山峰一比較，珠穆朗瑪峰脫穎而出。當兔子們再尋找的時候，一般地會有意識地避開泰山，因為他們知道，這里已經找過，并且有一只兔子在那里看著了。這就是禁忌搜索中“禁忌表（tabulist）”的含義。那只留在泰山的兔子一般不會就安家在那里了，它會在一定時間后重新回到找最高峰的大軍，因為這個時候已經有了許多新的消息，泰山畢竟也有一個不錯的高度，需要重新考慮，這個歸隊時間，在禁忌搜索里面叫做“禁忌長度（tabulength）”；如果在搜索的過程中，留守泰山的兔子還沒有歸隊，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當一個有兔子留守的地方優越性太突出，超過了“besttofar”的狀態，就可以不顧及有沒有兔子留守，都把這個地方考慮進來，這就叫“特赦準則（aspirationcriterion）”[7]。這三個概念是禁忌搜索和一般搜索準則最不同的地方。3.2算法的構成要素禁忌搜索最重要的思想是標記對應已搜索的局部最優解的一些對象，并在進一步的迭代搜索中盡量避開這些對象（而不是絕對禁止循環），從而保證對不同的有效搜索途徑的探索。禁忌搜索涉及到編碼方式（Encode）、適值函數、移動（Moving）與領域（neighborhood）、禁忌表（tabulist）、禁忌長度（tabu1ength）、選擇策略（SelectionStrategy）、候選解（candidate）、藐視準則（candidate）等概念，下面將介紹一下這些概念[8]。3.2.1編碼方法編碼就是將實際問題的解用一種便于算法操作的形式來描述，通常采用數學的形式；算法進行過程中活著算法結束之后，還需要通過解碼來還原到實際問題的解。根據問題的具體情況，可以靈活地選擇編碼方式。3.2.2初始解的獲得禁忌搜索算法可以隨機給出初始解，也可以事先使用其他啟發式等算法給出一個較好的初始解。由于禁忌搜索算法主要是基于鄰域搜索的，初始解的好壞對搜索的性能影響很大[9]。尤其是一些帶有很復雜約束的優化問題，如果隨機給出初始解很可能是不行的，甚至通過多步搜索也很難找到一個可行解，這個時候應該針對特定的復雜約束，采用啟發式方法或其它方法找出一個可行解作為初始解。3.2.3移動與鄰域移動移動是從當前解產生新解的途徑，從當前解可以進行的所有移動構成鄰域，也可以理解為從當前解經過“一步”可以到達的區域。適當的移動規則的設計，是取得高效的搜索算法的關鍵[10]。鄰域移動是從一個解產生另一個解的途徑。它是保證產生好的解和算法搜索速度的最重要因素之一[11]。鄰域移動定義的方法很多，對于不同的問題應采用不同的定義方法。通過移動，目標函數值將產生變化，移動前后的目標函數值之差，稱之為移動值。如果移動值是非負的，則稱此移動為改進移動;否則稱作非改進移動。最好的移動不一定是改進移動，也可能是非改進移動，這一點就保證搜索陷入局部最優時，禁忌搜索算法能自動把它跳出局部最優。3.2.4禁忌表不允許恢復即被禁止的性質稱作Tabu。禁忌表的主要目的是阻止搜索過程中出現循環和避免陷入局部最優，它通常記錄前若干次的移動，禁止這些移動在近期內返回。在迭代固定次數后，禁忌表釋放這些移動，重新參加運算，因此它是一個循環表，每迭代一次，將最近的一次移動放在禁忌表的末端，而它的最早的一個移動就從禁忌表中釋放出來。為了節省記憶時間，禁忌表并不記錄所有的移動，只記錄那些有特殊性質的移動，如記載能引起目標函數發生變化的移動。禁忌表記載移動的方式主要有三種:記錄目標值；移動前的狀態；移禁忌搜索算法在冷藏供應鏈配送網絡中的應用研究動本身。禁忌表是禁忌搜索算法的核心，禁忌表的大小在很大程度上影響著搜索速度和解的質量。如果選擇的好，可有助于識別出曾搜索過的區域。實驗表明，如果禁忌表長度過小，那么搜索過程就可能進入死循環，整個搜索將圍繞著相同的幾個解徘徊;相反，如果禁忌表長度過大，那它將在相當大的程度上限制了搜索區域，好的解就有可能被跳過，同時，不會改進解的效果而增加算法運算時間。因此一個好的禁忌表長度應該是盡可能小卻又能避免算法進入循環。禁忌表的這種特性非常類似于“短期記憶”，因而人們把禁忌表稱作短期記憶函數。禁忌表另一個作用是通過調整禁忌表的大小使搜索發散或收斂。初始搜索時，為提高解的分散性，擴大搜索區域，使搜索路徑多樣化，經常希望禁忌表長度小。相反當搜索過程接近最優解時，為提離解的集中性，減少分散，縮小搜索區域，這時通常希望禁忌表長度大[12]。為達到這樣的目的，最近越來越多的人們允許禁忌表的大小和結構隨搜索過程發生改變，即使用動態禁忌表，實驗結果表明了動態禁忌表往往比固定禁忌表獲得更好的解。禁忌表是用來存放禁忌對象的一個容器，被放入禁忌表中的禁忌對象在解禁之前不能被再次搜索，可見禁忌表模擬了人的記憶機制，防止搜索陷入局部最優，進而探索更多的搜索空間。禁忌表可以使用數組、隊列、棧、鏈表等順序結構實現，每個順序結構的元素定義根據具體問題確定。禁忌對象就是放入禁忌表中的元素，歸納而言，禁忌對象通常可選取狀態（解的編碼）本身或狀態分量或適配值的變化等，禁忌范圍依次擴大。其中選取狀態本身易于理解，也最為常用，禁忌范圍最小。禁忌長度就是每個禁忌對象在禁忌表中的生存時間，也稱為禁忌對象的任期。當一個禁忌對象加入禁忌表時，設置其任期為禁忌長度值，搜索過程每迭代一次，禁忌表中的各禁忌對象的任期自動減1，當某一禁忌對象任期為0時，將其從禁忌表中刪除。任期不為0的禁忌對象處于禁忌狀態，不能被搜索過程選為新解。候選解是當前解鄰域解集的一個子集。搜索中為了減少搜索的代價（包括空間和時間），要求禁忌長度和候選解集盡量小但禁忌長度過小將使搜索無法跳出局部最小，候選解集過小將使搜索早熟收斂。候選解集的大小常根據問題特性和對算法的要求確定，禁忌長度的選取則主要有靜態和動態兩種方法。靜態方法是指在搜索過程中，禁忌長度是一個固定值，比如n，其中n為問題維數或規模。動態方法是指在搜索過程中，禁忌長度也是動態變化的，當算法搜索能力較強時，可以增大禁忌長度從而延續當前的搜索能力，并避免搜索陷入局部最優解，反之亦然。禁忌頻率記錄每個禁忌對象出現在禁忌表中的次數，以此作為搜索過程的重要參考，如若某個對象出現頻繁，則可以增加禁忌長度來避免循環。此外可以把某對象的禁忌頻率作為評價解的因素加入評價函數來指導搜索過程。3.2.5選擇策略選擇策略即擇優規則，是對當前的鄰域移動選擇一個移動而采用的準則。擇優規則可以采用多種策略，不同的策略對算法的性能影響不同。一個好的選擇策略應該是既保證解的質量又保證計算速度。當前采用最廣泛的兩類策略是最好解優先策略和第一個改進解優先策略。最好改進解優先策略就是對當前鄰域中選擇移動值最好的移動產生的解，作為下一次迭代的開始。而第一個改進解優先策略是搜索鄰域移動時選擇第一改進當前解的鄰域移動產生的解作為下一次迭代的開始。最好改進解優先策略相當于尋找最陡的下降，這種擇優規則效果比較好，但是它需要更多的計算時間;而最快的下降對應尋找第一個改進解的移動，由于它無需搜索整個一次鄰域移動，所以它所花計算時間較少，對于比較大的鄰域，往往比較適合。3.2.6停止規則在禁忌搜索中停止規則通常有三種，一種是把最大迭代步數作為停止算法的標準，而不以局優為停止規則;第二種是在給定數目的迭代內所發現的最好解無法改進或無法離開它時，算法停止，最后一種是設定某對象的最大禁忌頻率。如果某對象的禁忌頻率達到了事先給定的值，或者歷史最優值連續若干步迭代得不到改善，則算法停止。3.3禁忌搜索算法流程簡單TS算法的基本思想是：給定一個當前解（初始解）和一種鄰域，然后在當前解的鄰域中確定若干候選解；若最佳候選解對應的目標值優于“bestsofar”狀態，則忽視其禁忌特性，用其替代當前解和“bestsofar”狀態，并將相應的對象加入禁忌表，同時修改禁忌表中各對象的任期；若不存在上述候選解，則選擇在候選解中選擇非禁忌的最佳狀態為新的當前解，而無視它與當前解的優劣，同時將相應的對象加入禁忌表，并修改禁忌表中各對象的任期；如此重復上述迭代搜索過程，直至滿足停止準則。簡單禁忌搜索的算法步驟可描述如下：（1）給定算法參數，隨機產生初始解x，置禁忌表為空。（2）判斷算法終止條件是否滿足？若是，則結束算法并輸出優化結果；否則，繼續以下步驟。（3）利用當前解的鄰域函數產生其所有（或若干）鄰域解，并從中確定若干候選解。（4）對候選解判斷藐視準則是否滿足？若成立，則用滿足藐視準則的最佳狀態y替代x成為新的當前解，即x=y，并用與y對應的禁忌對象替換最早進入禁忌表的禁忌對象，同時用y替換“bestsofar”狀態，然后轉步驟6；否則，繼續以下步驟。（5）判斷候選解對應的各對象的禁忌屬性，選擇候選解集中非禁忌對象對應的最佳狀態為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象元素。（6）轉步驟（2）。可見，簡單的禁忌搜索是在領域搜索的基礎上，通過設置禁忌表來禁忌一些已經歷的操作，并利用藐視準則來獎勵一些優良狀態，其中領域結構、候選解、禁忌長度、禁忌對象、終止準則等是影響禁忌搜索算法性能的關鍵[13]。需要指出的是：（1）首先，由于TS是局部領域搜索的一種擴充，因此領域結構的設計很關鍵，它決定了當前解的領域解的產生形式和數目，以及各個解之間的關系。（2）其次，出于改善算法的優化時間性能的考慮，若領域結構決定了大量的領域解（尤其對大規模問題，如TSP的SWAP操作將產生Cn2個領域解），則可以僅嘗試部分互換的結果，而候選解也僅取其中的少量最佳狀態。（3）禁忌長度是一個很重要的關鍵參數，它決定禁忌對象的任期，其大小直接進而影響整個算法的搜索進程和行為。同時，以上示例中，禁忌表中禁忌對象的替換是采用FIFO方式（不考慮藐視準則的作用），當然也可以采用其他方式，甚至是動態自適應的方式。（4）藐視準則的設置是算法避免遺失優良狀態，激勵對優良狀態的局部搜索，進而實現全局優化的關鍵步驟。（5）對于非禁忌候選狀態，算法無視它與當前狀態的適配值的優劣關系，僅考慮它們中間的最佳狀態為下一步決策，如此可實現對局部極小的突跳（是一種確定性策略）。（6）為了使算法具有優良的優化性能或時間性能，必須設置一個合理的終止準則來結束整個搜索過程。此外，在許多場合禁忌對象的被禁次數（frequency）也被用于指導搜索，以取得更大的搜索空間。禁忌次數越高，通常可認為出現循環搜索的概率越大。我們可以明顯地看到，鄰域函數、禁忌對象、禁忌表和藐視準則，構成了禁忌搜索算法的關鍵[14]。其中，鄰域函數沿用局部鄰域搜索的思想，用于實現鄰域搜索；禁忌表和禁忌對象的設置，體現了算法避免迂回搜索的特點；藐視準則，則是對優良狀態的獎勵，它是對禁忌策略的一種放松。需要指出的是，上述算法僅是一種簡單的禁忌搜索框架，對各關鍵環節復雜和多樣化的設計則可構造出各種禁忌搜索算法。同時，算法流程中的禁忌對象，可以是搜索狀態，也可以是特定搜索操作，甚至是搜索目標值等。同時，與傳統的優化算法相比，TS算法的主要特點是：（1）在搜索過程中可以接受劣解，因此具有較強的“爬山”能力；（2）新解不是在當前解的鄰域中隨機產生，而或是優于“bestsofar”的解，或是非禁忌的最佳解，因此選取優良解的概率遠遠大于其他解。由于TS算法具有靈活的記憶功能和藐視準則，并且在搜索過程中可以接受劣解，所以具有較強的“爬山”能力，搜索時能夠跳出局部最優解，轉向解空間的其他區域，從而增強獲得更好的全局最優解的概率，所以TS算法是一種局部搜索能力很強的全局迭代尋優算法.3.4禁忌搜索算法的應用3.4.1基于禁忌搜索的函數優化對于函數優化問題，設計禁忌搜索算法的目的主要是克服局部極小的影響以高效實現全局優化[15]。3.4.2基于禁忌搜索的多目標優化問題在過去，實際問題必須描述成一種特定的傳統方法能夠求解的形式，然而這是不容易。為了能夠求解，很多實際問題需要經過大量的假設或者修改，例如：變量德爾取整（離散化），放松約束，某種程度上做近似處理，等等，這必然會影響到解的質量。為了解決傳統優化方法中的這些問題，提出了一系列不依賴于問題的啟發式算法，例如本書介紹的禁忌搜索算法、遺傳算法、模擬退火算法等。使用禁忌搜索算法求解多目標問題，最簡單的一個思路就是通過引入權重機制，將多目標問題化為單目標問題，然后求解。這種做法完全屬于多目標問題的處理，求解所用的禁忌搜索算法與普通的禁忌搜索算法沒有任何區別。4系統需求分析4.1功能需求實現禁忌搜索算法，通過該算法尋求tsp問題的“最佳”解。用戶可以通過設置城市數量、運行代數、每次搜索鄰居個數、禁忌長度等系數多方位的執行禁忌搜索算法，并通過執行代碼實現最佳路線出現代數、最佳長度、最佳路徑，進而將其展現在頁面上，以便于查看。可以通過頁面的上傳按鈕實現數據源的配置，數據源即為代碼運行中需要的底層數據，便于改代碼的運用。實現與數據庫的交互，將數據源、查詢結果等信息保存到數據庫中，使用時可以取出，增加查詢界面，可以查看歷史運行記錄，并按要求查詢數據。4.2數據需求本系統采用att48數據，數據為文本類型，格式是“12003000”其中三個數字一行，代表了一個城市的信息，“1”為城市代碼“200，3000”代表了該城市所在的位置，文本中行數代表了城市的數量。庫中保存運行時參數，以及運行時間等，便于問題分析。4.3性能需求（1）系統要有很好的可移植性。（2）系統必須有很好的可維護性，代碼的格式規范。（4）界面設計要求簡潔、美觀、大方。（5）系統運行必須穩定，消耗資源少，代碼效率高。（6）系統運行環境：Windows操作系統，IE瀏覽器。（7）系統開發環境：myeclips，Oracle10g數據庫。中北大學2014屆畢業設計說明書5系統概要設計5.1功能模塊設計系統主要實現三大模塊，有數據執行模塊、數據源配置模塊和數據執行結果查詢模塊，其中數據執行模塊是最主要的模塊，其余兩個模塊是作為附加模塊來對數據執行模塊進行配合。各模塊實現的功能數據執行模塊：實現城市數量、運行代數、每次搜索鄰居個數、禁忌長度的自由設置，點擊查詢按鈕可以實現結果數據的頁面顯示。數據源配置模塊：點擊文件導入，可實現文件的尋找并將城市數量、備注等一些必要的信息錄入，上傳到數據庫中。數據執行結果查詢模塊：將歷史記錄結果從數據庫中取出并顯示。5.2系統分層設計該系統設計的結構主要著眼于分層設計，采用分層結構設計。系統中涉及的包有com包common包dao包service包等。 com包：存放了三大模塊的httpServlet實現類，它們用以接受從前臺請求的數據以及調用后臺方法后返回的數據并實現前后臺的數據交互。 common包：放置的類為連接、關閉數據庫的相關方法以及連接數據庫的配置文件。 dao包：對數據庫的操作。 service包：對傳入數據以及相關業務處理，并調用dao包中的方法處理問題。詳細設計：5.3數據庫設計 數據庫是“按照數據結構來組織、存儲和管理數據的倉庫”。在企業管理的日常工作中，常常需要把某些相關的數據放進這樣的“倉庫”，并根據管理的需要進行相應的處理。數據表本系統創建了兩張表，分別為源數據表（data）和數據執行結果表（result）。各表結構如下所示：字段名字段類型注釋FILENAMEVARCHAR2(100)文件名（保存文件路徑）DATAVARCHAR2(1000)城市數據DETAILVARCHAR2(1000)明細圖5.1源數據表（data）字段名字段類型注釋RESULT_IDNUMBER結果idBESTTVARCHAR2(10)最佳路線出現代數BESTEVALUATIONVARCHAR2(10)最佳長度BESTGHVARCHAR2(1000)最佳路徑CITYNUMVARCHAR2(10)城市數量MAX_GENVARCHAR2(10)運行代數NVARCHAR2(10)每次搜索鄰居個數LLVARCHAR2(10)禁忌長度TIMENUMBER運行時間單位（毫秒）圖5.2數據執行結果表（result）圖5.3源數據表詳實圖5.4數據結果表例6系統展示及代碼實現6.1系統首頁 未進行操作，頁面顯示禁忌算法的相關參數，運算結果為空。圖6.1后臺servlet實現代碼為： protectedvoiddoPost(HttpServletRequestreq,HttpServletResponseresp) throwsServletException,IOException{ //TODOAuto-generatedmethodstub //獲取前臺傳來的必要參數 intcityNum=Integer.parseInt(req.getParameter("cityNum"));//城市數量 intMAX_GEN=Integer.parseInt(req.getParameter("MAX_GEN"));//運行代數 intN=Integer.valueOf(req.getParameter("N")).intValue();//鄰居個數 intll=Integer.valueOf(req.getParameter("ll")).intValue();//禁忌長度 Stringdetail=req.getParameter("resource"); System.out.println(cityNum+"||"+MAX_GEN+"||"+N+"||"+ll); System.out.println(detail); TabuServicetabu=newTabuServiceImpl(); Map<String,Object>map=null; try{ Stringdata=tabu.getData(detail); map=tabu.solute(data,cityNum,MAX_GEN,N,ll); }catch(SQLExceptione){ e.printStackTrace(); } HttpSessionsession=req.getSession(); session.setAttribute("bestEvaluation",map.get("bestEvaluation")); session.setAttribute("bestT",map.get("bestT")); session.setAttribute("cityNum",map.get("cityNum")); session.setAttribute("bestGh",map.get("bestGh")); RequestDispatcherdispatcher=req.getRequestDispatcher("index.jsp"); dispatcher.forward(req,resp); }6.2運行計算點擊尋找，程序調用禁忌搜索算法產生結果。圖6.2禁忌搜索算法主要代碼實現：功能實現初始化數據，將從數據庫中讀取到的數據按照其格式初始化為代碼可解讀的格式，并將其賦予到數組中用以接下來的使用。 publicvoidinit(Stringdata,inta,intd)throwsIOException, SQLException{ ll=d; cityNum=a; int[]x; int[]y; Stringstrbuff; String[]array=data.split(","); distance=newint[cityNum][cityNum]; x=newint[cityNum]; y=newint[cityNum]; for(inti=0;i<cityNum;i++){ strbuff=array[i]; //字符分割 String[]strcol=strbuff.split(""); x[i]=Integer.valueOf(strcol[1]);//x坐標 y[i]=Integer.valueOf(strcol[2]);//y坐標 } //計算距離矩陣 //，針對具體問題，距離計算方法也不一樣，此處用的是att48作為案例，它有48個城市，距離計算方法為偽歐氏距離，最優值為10628 for(inti=0;i<cityNum-1;i++){ distance[i][i]=0;//對角線為0 for(intj=i+1;j<cityNum;j++){ doublerij=Math .sqrt(((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j]) *(y[i]-y[j]))/10.0); //四舍五入，取整 inttij=(int)Math.round(rij); if(tij<rij){ distance[i][j]=tij+1; distance[j][i]=distance[i][j]; }else{ distance[i][j]=tij; distance[j][i]=distance[i][j]; } } } distance[cityNum-1][cityNum-1]=0; Ghh=newint[cityNum]; bestGh=newint[cityNum]; bestEvaluation=Integer.MAX_VALUE; LocalGhh=newint[cityNum]; localEvaluation=Integer.MAX_VALUE; tempGhh=newint[cityNum]; tempEvaluation=Integer.MAX_VALUE; jinji=newint[ll][cityNum]; bestT=0; t=1; random=newRandom(System.currentTimeMillis()); } //初始化編碼Ghh voidinitGroup(){ //System.out.println("進入方法：initGroup()"); inti,j; Ghh[0]=random.nextInt(65535)%cityNum; for(i=1;i<cityNum;)//編碼長度 { Ghh[i]=random.nextInt(65535)%cityNum; for(j=0;j<i;j++){ if(Ghh[i]==Ghh[j]){ break; } } if(j==i){ i++; } } } //復制編碼體，復制編碼Gha到Ghb publicvoidcopyGh(int[]Gha,int[]Ghb){ //System.out.println("進入方法：copyGh(int[]Gha,int[]Ghb)"); for(inti=0;i<cityNum;i++){ Ghb[i]=Gha[i]; } } publicintevaluate(int[]chr){ //System.out.println("進入方法：evaluate(int[]chr)"); //0123 intlen=0; //編碼，起始城市,城市1,城市2...城市n for(inti=1;i<cityNum;i++){ len+=distance[chr[i-1]][chr[i]]; } //城市n,起始城市 len+=distance[chr[cityNum-1]][chr[0]]; returnlen; } //鄰域交換，得到鄰居 publicvoidLinju(int[]Gh,int[]tempGh){ //System.out.println("進入方法：Linju(int[]Gh,int[]tempGh)"); inti,temp; intran1,ran2; for(i=0;i<cityNum;i++){ tempGh[i]=Gh[i]; } ran1=random.nextInt(65535)%cityNum; ran2=random.nextInt(65535)%cityNum; while(ran1==ran2){ ran2=random.nextInt(65535)%cityNum; } temp=tempGh[ran1]; tempGh[ran1]=tempGh[ran2]; tempGh[ran2]=temp; } //判斷編碼是否在禁忌表中 publicintpanduan(int[]tempGh){ //System.out.println("進入方法：panduan(int[]tempGh)"); inti,j; intflag=0; for(i=0;i<ll;i++){ flag=0; for(j=0;j<cityNum;j++){ if(tempGh[j]!=jinji[i][j]){ flag=1;//不相同 break; } } if(flag==0)//相同，返回存在相同 { //return1; break; } } if(i==ll)//不等 { return0;//不存在 }else{ return1;//存在 } } //解禁忌與加入禁忌 publicvoidjiejinji(int[]tempGh){ //System.out.println("進入方法：jiejinji(int[]tempGh)"); inti,j,k; //刪除禁忌表第一個編碼，后面編碼往前挪動 for(i=0;i<ll-1;i++){ for(j=0;j<cityNum;j++){ jinji[i][j]=jinji[i+1][j]; } } //新的編碼加入禁忌表 for(k=0;k<cityNum;k++){ jinji[ll-1][k]=tempGh[k]; } }可以對數據源進行選取操作。圖6.3上傳數據源，用以解決不同的問題。圖6.46.3結果查詢頁面便于對運行結果的查看及比較不同參數設置下的效率與實用性。圖6.5查詢代碼實現： //獲取結果 publicCollectiongetResult(Map<String,Object>map){ Stringcollections=""; conn=Conn.getConnection(); sql="selectt.result_id,t.bestt,t.bestevaluation,t.bestgh,t.citynum,t.max_gen,t.n,t.ll,t.timefromresulttwhere1=1"; if(!("values").equals(map.get("bestt"))){ collections+="ANDbestt='"+map.get("bestt")+"'"; } if(!("values").equals(map.get("bestevaluation"))){ collections+="ANDbestevaluation='"+map.get("bestevaluation")+"'"; } if(!("values").equals(map.get("bestgh"))){ collections+="ANDbestgh='"+map.get("bestgh")+"'"; } if(!("values").equals(map.get("citynum"))){ collections+="ANDcitynum='"+map.get("citynum")+"'"; } if(!("values").equals(map.get("max_gen"))){ collections+="ANDmax_gen='"+map.get("max_gen")+"'"; } if(!("values").equals(map.get("ll"))){ collections+="ANDll='"+map.get("ll")+"'"; } if(!("values").equals(map.get("n"))){ collections+="ANDN='"+map.get("n")+"'"; } Stringorder="orderbybestevaluation"; sql+=collections; sql+=order; System.out.println(sql); Collection<String[]>resultCollection=newArrayList<String[]>(); try{ stmt=conn.createStatement(); res=stmt.executeQuery(sql); while(res.next()){ String[]row=newString[9]; row[0]=res.getString(1); row[1]=res.getString(2); row[2]=res.getString(3); row[3]=res.getString(4); row[4]=res.getString(5); row[5]=res.getString(6); row[6]=res.getString(7); row[7]=res.getString(8); row[8]=res.getString(9); resultCollection.add(row); } DBClose.close(res,stmt,conn