智能計算大作業(yè)

1、精選優(yōu)質文檔-傾情為你奉上1.1 問題描述求解Rastrigin函數(shù)的最小值，函數(shù)Rastrigin表述如下：1.2 算法理論模擬退火算法（simulated annealing,簡稱SA)的思想最早由Metropolis等（1953）提出，1983年Kirkpatrick等將其用于組合優(yōu)化。SA算法是基于Mente Carlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質的退火過程與一般組合優(yōu)化問題之間的相似性。其思想于固體退火過程，將固體加溫至充分高, 再讓其冷卻； 加溫時, 固體內部粒子隨溫升變?yōu)闊o序狀, 內能增大, 而徐徐冷卻時粒子漸趨有序, 在每個溫度都達到平衡態(tài), 最

2、后在常溫時達到基態(tài), 內能減為最小。其物理退火過程由以下三部分組成： （1）加溫過程增強粒子的熱運動，消除系統(tǒng)原先可能存在的非均勻態(tài)； （2）等溫過程對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進行，當自由能達到最小時，系統(tǒng)達到平衡態(tài)； （3）冷卻過程使粒子熱運動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結構。 其中，加溫的過程對應算法的設定初溫，等溫過程對應算法的Metropolis抽樣過程，冷卻過程對應控制參數(shù)的下降。這里能量的變化就是目標函數(shù)，要得到的最優(yōu)解就是能量最低態(tài)。Metropolis準則以一定的概率接受惡化解，這樣就使算法跳離局部最優(yōu)的

3、陷阱。用固體退火模擬組合優(yōu)化問題，將內能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t , 即得到解組合優(yōu)化問題的模擬退火算法。由初始解i和控制參數(shù)初值t開始，對當前解重復“產生新解計算目標函數(shù)差判斷是否接受接受或舍棄”的迭代, 并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解。退火過程由冷卻進度表( Cooling Schedule)控制。包括控制參數(shù)的初值t及其衰減因子t每個t 值時的迭代次數(shù)( 稱為一個Mapkob 鏈的長度) L和停止條件S。1.3 求解步驟SA算法實現(xiàn)過程如下圖所示： 本文具體步驟如下：（1）目標函數(shù)目標函數(shù)即是待優(yōu)化的函數(shù)。在調用函數(shù)simulannealbnd運

4、行模擬退火時，需要編寫該目標函數(shù)的M文件。需要指出的是，SAT是對目標函數(shù)取最小值進行優(yōu)化的。對于最大優(yōu)化問題，只需將目標函數(shù)乘以-1即可化為最小值優(yōu)化問題， （2）溫度 對于模擬退火算法來說，溫度是一個很重要的參數(shù)，它隨著算法的迭代二逐步下降，以模擬固體退火過程中的降溫過程。一方面，溫度用于限制SA產生的新解與當前解之間的距離，也就是SA的搜索范圍；另一方面，溫度決定了SA以多大的概率接受目標函數(shù)值比當前解的目標函數(shù)值差的新解。（3）退火進度表退火進度表是指溫度隨著算法迭代的下降速度。退火過程越緩慢，SA找到全局最優(yōu)解的機會越大，相應的運行時間也會增加。退火進度表包括初始溫度及溫度更新函數(shù)等

5、參數(shù)。（4）Meteopolis準則Meteopolis準則是指SA接受新解的概率。對于目標函數(shù)取最小值的優(yōu)化問題，SA接受新解的概率為 其中，為當前解；為新解；表示解得目標函數(shù)值；為溫度。該過程不斷重復，可以看到，開始時溫度較高，SA接受較差解得概率也相對較高，這使得SA有更大的機會跳出局部最優(yōu)解，隨著退火的進行，溫度逐步下降，SA接受較差解的概率變小。1.4 運行結果（圖、表等）某次得到的當前解目標函數(shù)值歷程曲線1.5 分析小結運行模擬退火算法，得到的最優(yōu)解目標函數(shù)值歷程曲線和當前解目標值歷程曲線分別如上圖，函數(shù)simulannealbnd返回的最優(yōu)解及其對應的目標函數(shù)值在Workspac

6、e中，分別為：需要強調的是，由于算法中使用了函數(shù)randn和函數(shù)rand，因此，每次運行的結果是不一樣的。量子遺傳算法流程如下：（1）初始化種群，隨機生成n個以量子比特位編碼的染色體；（2）對初始化種群中的每個個體進行一次測量，得到對應的確定解；（3）對各確定解進行適應度評估； （4）記錄最優(yōu)個體和對應的適應度；（5）判斷計算過程是否可以結束，若滿足結束條件則退出，否則繼續(xù)計算；（6）對種群中的每個個體實施一次測量，得到相應的確定解；（7）對各個確定解進行適應度評估；（8）利用量子旋轉門對個體實施調整，得到新的種群；（9）記錄最優(yōu)個體和對應的適應度；（10）將迭代次數(shù)t加1，返回步驟（5）。

7、需要說明的是:（1) 在種群初始化中，種群規(guī)模為N，即有N 個量子編碼的個體，每個量子個體都設為，即: （2）對種群每個個體實施一次測量是指對每個個體每個量子位進行測量，過程為隨機生成一個0，1的隨機數(shù)，如果該隨機數(shù)大于等于幾率幅（或），則測量結果取1，否則取0。由此將量子編碼的個體轉換為二進制編碼的個體，得到了N 個二進制編碼的個體。 （3）求解適應度指利用得到的二進制編碼求解函數(shù)的適應度，在數(shù)值優(yōu)化問題中過程為: 先將二進制代碼轉換為十進制數(shù)，然后代入優(yōu)化的函數(shù)中，得到其函數(shù)值即為適應度。 （4）種群更新按照式(1)的方式進行。3.4 運行結果（圖、表等） 量子遺傳算法優(yōu)化200代得到的進

8、化過程圖所示：最優(yōu)解X：12.0998 5.72335最大值Y:17.18853.5 分析小結量子遺傳算法雖然引進了量子計算中的一些概念，但其本質仍是一種遺傳算法，所以在理論上，傳統(tǒng)遺傳算法的應用領域均適用于量子遺傳算法，并且求解效率明顯優(yōu)于傳統(tǒng)遺傳算法。但由于量子遺傳算法是一種新理論，在理論研究、復雜函數(shù)優(yōu)化等方面還不是很成熟。4 免疫優(yōu)化算法在物流配送選址中的應用4.1 問題描述 在物流配送中心選址模型中作如下假設：（1）配送中心的規(guī)模容量可以滿足需求點要求，并由其配送輻射范圍內的需求量確定；（2）一個需求點僅有一個配送中心供應；（3）不考慮工廠到配送中心的運輸費用?；谝陨系募僭O，建立如

9、下模型。該模型是一個選址分配模型，在滿足距離上限的情況下，需要從n個需求點中找出配送中心并向各需求點配送物品。目標函數(shù)是各配送中心到需求點的需求量和距離值的乘積之和最小，目標函數(shù)為約束條件為4.2 算法理論生物免疫系統(tǒng)是一個高度進化的生物系統(tǒng)，它旨在區(qū)分外部有害抗原和自身組織，從而保持有機體的穩(wěn)定。從計算角度，生物免疫系統(tǒng)是一個高度并行、分布、自適應和自組織的系統(tǒng)，具有很強的學習和記憶能力。免疫系統(tǒng)的進化角度來考察免疫信息處理機制( 多樣性、免疫自我調節(jié)、免疫記憶等) , 其實免疫系統(tǒng)作為一個動態(tài)進化系統(tǒng), 與遺傳算法所模仿的自然界生物種群進化的過程有一定的相似之處, 但也有著自己特殊的演化規(guī)

10、律, 免疫系統(tǒng)的動態(tài)變化包括從只有幾毫秒的亞分子事件到幾分鐘、幾年的細胞群體變化, 以及需要無數(shù)代才能完成的免疫基因庫的改變。免疫算法正是受生物免疫系統(tǒng)啟發(fā)，在免疫學理論基礎上發(fā)展起來的一種新興的智能計算方法。一種確定性與隨機性融為一體的方法，具有勘測與開采能力的啟發(fā)式隨機搜索算法，被認為是對自然免疫系統(tǒng)中體液免疫的簡單模擬，這種應答過程通過抗體學習抗原來完成，克隆選擇使親和力較高的抗體被確定性選擇參與進化，細胞克隆使親和力較高的抗體依據(jù)其親和力繁殖克??；克隆抑制消除相同、相似及親和力低的克隆。免疫選擇使母體群參與克隆競爭并按概率選擇存活的母體或克隆募集新成員則隨機產生自我抗體群維持自身平衡，

11、這種由進化鏈：抗體群克隆選擇細胞克隆及記憶細胞演化親和突度免疫選擇募集新成員新抗體群，它利用免疫系統(tǒng)的多樣性產生和維持機制來保持群體的多樣性，克服了一般尋優(yōu)過程尤其是多峰函數(shù)尋優(yōu)過程中難處理的“早熟”問題，最終求得全局最優(yōu)解。與其它算法的相比，免疫算法的研究起步較晚，其發(fā)展歷史只有短短二十幾年。記憶細胞的演化：將抗體細化的部分細胞作為記憶細胞加入記憶池，并清除相同、相似及親和力低的記憶細胞。引入抗原識別及記憶細胞演化的目的，是對于己處理的抗原再次出現(xiàn)或相似抗原出現(xiàn)時，提高算法尋優(yōu)的快速性。若取消這兩個操作，對算法的收斂性無影響?？寺∵x擇：將進化群體中中較好的可行解確定性選擇參與進化，提供勘測更

12、好可行解的機會。當有機體內免疫細胞的多樣性達到一定程度時，每一種抗原侵入機體都能在機體內被識別，同時機體能克隆消滅相應抗原的免疫細胞，使之激活、分化和增殖，進行免疫應答最終消除抗原。細胞克隆及記憶細胞演化：不僅為同類問題的解決提供高效解決的機會，而且為算法的局部搜索提供必要的準備，這一操作與親和突變共同作用，增強算法局部搜索能力，使算法有更多機會控測更好的可行解。細胞克隆(無性繁殖)中父代與子代之間只有信息的簡單復制，這與遺傳算法中的復制一樣的，因為沒有不同信息的交流，無法促進細胞進化，因此需要對進化后的細胞進行處理，如親和突變與克隆抑制。其本質是對抗體進化過程中，在每一代可行解的附近，根據(jù)親

13、和度的大小克隆，產生一個變異解的群體，從而擴大了搜索范圍(即增加了抗體的多樣性，能擺脫局部最優(yōu)，具有爬山的能力)克隆抑制：促使突變的克隆群中相同或相似的克隆被確定清除，不僅可保存好、中、差的克隆，還可為免疫算子選擇存活抗體減輕選擇壓力。免疫選擇：不僅給親和力高的抗體提供更多選擇機會，而且也給低親和力及高濃度抗體提供生存機會，使得存話的抗體群具有多樣性。參考文獻1 史峰，王輝等. MATLAB智能算法30個案例分析M . 北京：北京航空航天大學出版社，2011.2 吳微.神經網絡計算M. 北京: 高等教育出版社，2003.3 于雪晶，麻肖妃.夏斌，動態(tài)粒子群算法J.計算機工程.2010.2,19

14、3-197. 4 王改唐，李平. 基于自適應變異的動態(tài)粒子群優(yōu)化算法J. 科技通報，2010，657-661.5. 梁昌勇，柏樺，蔡美菊.量子遺傳算法研究進展J.計算機應用研究.2012，7，2401-2405.6 LIN Yong-huang, LEE P C. Novel high-precision gray forecasting modelJ. Automation in Construction, 2007, 16(6): 771-777.7 Wu W, Xu Y S. Deterministic convergence of an online gradient method for n