智能優(yōu)化理論-第13章自由搜索算法

第13章自由搜索算法目錄contents自由搜索算法的提出自由搜索算法的優(yōu)化原理自由搜索算法的數(shù)學(xué)描述自由搜索算法的實(shí)現(xiàn)步驟及流程動(dòng)態(tài)拉伸目標(biāo)函數(shù)的自由搜索算法復(fù)習(xí)思考題自由搜索算法的提出01自由搜索算法（FS）是由英國(guó)學(xué)者Penev和Littlefair在2005年提出的一種群智能優(yōu)化算法。自由搜索算法不是模擬某一種社會(huì)性群居動(dòng)物的生物習(xí)性，而是博采眾長(zhǎng)，模擬多種動(dòng)物的生物特征及生活習(xí)性。自由搜索算法不僅采用螞蟻的信息素通信機(jī)制，以信息素指導(dǎo)其活動(dòng)行為，而且還借鑒高等動(dòng)物感知能力和機(jī)動(dòng)性的生物特征。自由搜索算法模擬了生物界中相對(duì)高等的群居動(dòng)物，如馬牛羊等的覓食過程。自由搜索算法借鑒動(dòng)物個(gè)體存在各異的嗅覺和機(jī)動(dòng)性，提出了靈敏度和鄰域搜索半徑的概念，并利用螞蟻釋放信息素的機(jī)理確定尋優(yōu)目標(biāo)。自由搜索算法對(duì)于函數(shù)優(yōu)化結(jié)果顯示出良好的性能，已用于函數(shù)優(yōu)化、灌溉制度的優(yōu)化、無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位等問題。自由搜索算法的提出自由搜索算法的優(yōu)化原理0203尋優(yōu)過程中，個(gè)體不斷地調(diào)節(jié)其靈敏度，類似于自然界的學(xué)習(xí)和掌握知識(shí)的過程。01自由搜索算法中，個(gè)體模仿高等動(dòng)物覓食行為，利用嗅覺感知、機(jī)動(dòng)性和關(guān)系進(jìn)行抽象建模。02不同個(gè)體具有各異的特征，感知被定義為靈敏度，使個(gè)體在搜索域內(nèi)具有不同的辨別能力。自由搜索算法的優(yōu)化原理010203個(gè)體考慮過去積累的經(jīng)驗(yàn)知識(shí)，并不受限制，可在規(guī)定范圍內(nèi)任意區(qū)域自由搜索。自由搜索算法具有靈活性，個(gè)體可進(jìn)行局部或全局搜索，自己決定搜索步長(zhǎng)。算法模型中，一個(gè)搜索循環(huán)（一代）個(gè)體移動(dòng)一個(gè)搜索步(Walk)，每個(gè)搜索步包含T小步(Step)。自由搜索算法的優(yōu)化原理自由搜索算法的優(yōu)化原理01個(gè)體在多維空間作小步移動(dòng)，其目的是發(fā)現(xiàn)目標(biāo)函數(shù)更好的解。02信息素大小和目標(biāo)函數(shù)解的質(zhì)量成正比，完成一個(gè)搜索步以后，信息索將完全更新。03FS算法的個(gè)體實(shí)際上是搜索過程中的標(biāo)記信息素位置的一種抽象，這種抽象是對(duì)搜索空間認(rèn)知的記憶。自由搜索算法的優(yōu)化原理01每個(gè)個(gè)體對(duì)于信息素都有自己的嗅覺靈敏度和傾向性，利用靈敏度選擇坐標(biāo)點(diǎn)，信息素和靈敏度函數(shù)。02增大靈敏度，個(gè)體將局部搜索，趨近于整個(gè)群體的當(dāng)前最佳值；減小靈敏度，個(gè)體可以在其他鄰域進(jìn)行全局搜索。03在搜索步中，個(gè)體在預(yù)先設(shè)定的鄰域空間內(nèi)小步移動(dòng)，不同個(gè)體的鄰域大小不同，同一個(gè)個(gè)體在搜索過程中鄰域空間也可以變化。04搜索步中的移動(dòng)小步反映了個(gè)體的活動(dòng)能力，它可小可大、可變化。自由搜索算法的數(shù)學(xué)描述03初始種群產(chǎn)生方法選取單一值法：該方法在搜索開始前，將所有個(gè)體都置于同一個(gè)坐標(biāo)點(diǎn)上，然后根據(jù)一定的搜索策略進(jìn)行探索和擴(kuò)展。選取確定值法：該方法在一個(gè)確定的數(shù)上，通過將其作為每個(gè)個(gè)體的初始值來開始搜索。隨機(jī)賦初值法：該方法通過在搜索空間中隨機(jī)選取m個(gè)個(gè)體，并賦予它們初值。除了這三種方法外，還有一些其他的種群初始化策略，如隨機(jī)漫步法、偽隨機(jī)數(shù)法等。在實(shí)際應(yīng)用中，需要根據(jù)具體情況選擇合適的種群初始化方法，以確保優(yōu)化問題的順利解決。個(gè)體j完成第t搜索步后的適應(yīng)度；為完成T搜索步后個(gè)體j最大的適應(yīng)度。算法搜索過程中，對(duì)目標(biāo)函數(shù)的符號(hào)作如下規(guī)定種群完成一次搜索后的最大適應(yīng)度值。信息素定義搜索過程中個(gè)體的行動(dòng)搜索過程中個(gè)體的行動(dòng)靈敏度定義：和分別為靈敏度的最大值和最小值；rand(0,1)是均勻分布的隨機(jī)數(shù)。123規(guī)定和分別為信息素的最大值和最小值。在一輪搜索結(jié)束后，確定下一輪搜索的起點(diǎn)。搜索過程中個(gè)體的行動(dòng)02030401搜索過程中個(gè)體的行動(dòng)更新策略為信息素大于靈敏度的個(gè)體以上一輪標(biāo)記的位置為新一輪的搜索起始點(diǎn)，其他的個(gè)體以上一輪的搜索起始點(diǎn)重復(fù)搜索。式中，k為標(biāo)記位數(shù)，自由搜索算法的終止策略包括以下三種情況：當(dāng)目標(biāo)函數(shù)達(dá)到目前函數(shù)的全局最優(yōu)解時(shí)，可以終止算法。當(dāng)當(dāng)前迭代次數(shù)g達(dá)到終止代數(shù)G時(shí)，可以終止算法。當(dāng)同時(shí)滿足上述兩個(gè)終止條件時(shí)，可以終止算法。010203終止策略自由搜索算法的實(shí)現(xiàn)步驟及流程04初始化設(shè)定搜索初始值種群規(guī)模m，搜索代數(shù)G，搜索小步總數(shù)T和個(gè)體的鄰域半徑。產(chǎn)生初始種群按式之一產(chǎn)生初始種群，其中隨機(jī)值法應(yīng)用最為廣泛。初始化搜索初始化結(jié)束后，根據(jù)上述兩步產(chǎn)生的初始值，生成并釋放初始信息素xk是標(biāo)記信息素的點(diǎn)的坐標(biāo)，k＝1,2…個(gè)體k的信息素Pk和個(gè)體j尋優(yōu)的最優(yōu)位置。計(jì)算靈敏度，按式計(jì)算。搜索步計(jì)算，計(jì)算目標(biāo)函數(shù)，其中由式計(jì)算。釋放信息素，按式計(jì)算信息素，并按式利用信息素得到本次搜索結(jié)果：個(gè)體j的信息素Pj和個(gè)體j尋優(yōu)的最優(yōu)位置。確定初始點(diǎn)，選擇新一輪搜索的起始點(diǎn)。搜索過程判斷終止條件自由搜索算法的流程如圖13.1所示。在搜索過程中，需要不斷根據(jù)搜索結(jié)果和預(yù)設(shè)條件進(jìn)行判斷。如果搜索結(jié)果符合預(yù)設(shè)條件，則可以終止搜索并返回結(jié)果。在開始搜索前，先要確定搜索的目標(biāo)和范圍。動(dòng)態(tài)拉伸目標(biāo)函數(shù)的自由搜索算法05要有效解決多模態(tài)函數(shù)的全局優(yōu)化問題，必須使優(yōu)化問題及時(shí)從各局部極值點(diǎn)逃逸出來，以保證以較大幾率收斂于全局最優(yōu)解。ParsopoulosKE等人提出了基于拉伸技術(shù)的粒子群優(yōu)化算法。拉伸技術(shù)根據(jù)已經(jīng)探測(cè)到的局部極值點(diǎn)信息，對(duì)原始目標(biāo)函數(shù)進(jìn)行兩次拉伸變化。優(yōu)化問題中，目標(biāo)函數(shù)可能存在多個(gè)局部極值或全局極值，導(dǎo)致以較大概率收斂于某些局部極值，即“早熟”。動(dòng)態(tài)拉伸技術(shù)動(dòng)態(tài)拉伸技術(shù)兩個(gè)變換函數(shù)如下所示:γ1、γ2、μ為任意參數(shù):γ1控制原目標(biāo)函數(shù)向上拉伸的幅度。γ2控制變換函數(shù)作用范圍。μ控制局部極值點(diǎn)提升的幅度。引入拉伸技術(shù)前，對(duì)所有個(gè)體進(jìn)行一次基本FS優(yōu)化。當(dāng)搜索到某一局部極值點(diǎn)x*后，根據(jù)f(x)信息把函數(shù)解空間劃分為兩個(gè)部分A:在R1內(nèi)，原目標(biāo)函數(shù)不變。剔除了函數(shù)值高于f(x*)的部分極值。第二次變換G(x)→H(x)，函數(shù)進(jìn)一步向上拉伸，距離x*越近，且函數(shù)值越接近f(x*)的點(diǎn)，其拉伸程度越大。進(jìn)一步縮小了后續(xù)搜索空間。拉伸技術(shù)有效地降低了目標(biāo)函數(shù)的復(fù)雜性，但未改變搜索目標(biāo)，把它與全局優(yōu)化算法FS結(jié)合，降低了后續(xù)搜索難度，從而提高了算法的搜索效率和精度。B:在R2內(nèi)，原目標(biāo)函數(shù)經(jīng)歷兩次拉伸變化。第一次變化f(x)→G(x)，原目標(biāo)函數(shù)每一函數(shù)值均向上拉伸，離x*越遠(yuǎn)的點(diǎn)其函數(shù)值被拉伸的幅度越大。動(dòng)態(tài)拉伸技術(shù)動(dòng)態(tài)拉伸自由搜索算法的實(shí)現(xiàn)步驟包括初始化、搜索過程和終止判斷。在步驟1中，需要設(shè)定搜索初始值、種群規(guī)模m、搜索代數(shù)G、搜索小步數(shù)T和個(gè)體的鄰域半徑Rji。產(chǎn)生初始種群按照式產(chǎn)生初始種群；初始化搜索，根據(jù)初始值生成初始信息素，釋放初始信息素Pj→xk，得到初始搜索結(jié)果Pk和xkp。在步驟2中，搜索過程包括計(jì)算靈敏度、確定初始點(diǎn)、搜索步計(jì)算和利用兩個(gè)變換函數(shù)對(duì)fj進(jìn)行轉(zhuǎn)換。計(jì)算信息素Pj;按照式釋放信息素Pj→xk，得到本次搜索結(jié)果。在步驟3中，需要判斷終止條件，若不滿足則跳轉(zhuǎn)至步驟2；若滿足則輸出搜索結(jié)果，由于群體在整個(gè)搜索空間遍歷，所以FS算法是全局漸進(jìn)收斂的。實(shí)現(xiàn)動(dòng)態(tài)拉伸自由搜索算法復(fù)習(xí)思考題06自由搜索算法的優(yōu)化原理是指通過一定的方法和技術(shù)，在搜索空間中快速地找到目標(biāo)函數(shù)的最優(yōu)解或近似最優(yōu)解。動(dòng)態(tài)拉伸目標(biāo)函數(shù)的自由搜索算法具有很多優(yōu)勢(shì)，如能夠更好地適應(yīng)不同形狀和尺寸的目標(biāo)函數(shù)、提高搜索效率和精度等。自由搜索算法的實(shí)現(xiàn)步驟主要包括：定義搜索空間、目標(biāo)函數(shù)和優(yōu)化準(zhǔn)則；初始化搜索路徑；在搜索路徑上不斷擴(kuò)展和收縮，直到找到目標(biāo)函數(shù)的最優(yōu)解或近似最優(yōu)解。復(fù)習(xí)思考題輸入標(biāo)題02010403復(fù)習(xí)思考題具體實(shí)現(xiàn)步驟包括：定義動(dòng)態(tài)拉伸目標(biāo)函數(shù)、選擇合適的拉伸參數(shù)和搜索策略、對(duì)搜索結(jié)果進(jìn)行評(píng)估和優(yōu)化等