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

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