智能計(jì)算大作業(yè)

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

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

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

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

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

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

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

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

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

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

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

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

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

14、3-197. 4 王改唐，李平. 基于自適應(yīng)變異的動(dòng)態(tài)粒子群優(yōu)化算法J. 科技通報(bào)，2010，657-661.5. 梁昌勇，柏樺，蔡美菊.量子遺傳算法研究進(jìn)展J.計(jì)算機(jī)應(yīng)用研究.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