第三章-遺傳算法的理論基礎(chǔ)

#/11到破壞，只有較少的共享模板得以保留。3?重組策略(RecombinationStrategies)重組策略就是使用交叉算子。在某種程度上，交叉操作試圖產(chǎn)生與其父輩不同的個(gè)體，從而使產(chǎn)生的群體更具多樣性。能使交叉操作更具有活力的最簡單的方法就是，增加其使用的頻率和使用動態(tài)改變適應(yīng)度函數(shù)的方法，如共享函數(shù)方法。列一種方法是把交叉點(diǎn)選在個(gè)體的具有不同值的位上。只要父輩個(gè)體至少有兩位不同，所產(chǎn)生的子代個(gè)體就會與其父輩不相同。維持群體多樣性的更基本的方法是，使用更具有破壞性的交叉算子，如均勻交叉算子0該算子試圖交叉近一半的不同位，因而保留的模板比單點(diǎn)或兩點(diǎn)交叉所保留的模板要少得多。總之，重組策略主要是從使用頻率和交叉點(diǎn)兩方而考慮，來維持群體的多樣性。這對采用隨機(jī)選擇配對個(gè)體進(jìn)行交叉操作可能有特肚的意義，但對成比例選擇方式，其效果則不一定明顯。4替代策略(ReplacementStrategies)匹配策略和重組策略分別是在選擇、交叉階段，通過某種策略來維持群體的多樣性。而替代策略是確泄在選擇、交叉產(chǎn)生的個(gè)體中，選擇哪一個(gè)個(gè)體進(jìn)入新一代群體。DeJong采用排擠(Crowding)模式，用新產(chǎn)生的個(gè)體去替換父輩中類似的個(gè)體。Syscuda和Whilclcy也采用類似的方法，他們僅把與父輩各個(gè)個(gè)體均不相似的新個(gè)體添加到群體中。這種替換策略僅從維持群體的多樣性出發(fā)，存在一立的負(fù)而影響，即交叉操作會破壞較多模板，但這種影響比前兩種策略的要少。3?5性能評估遺傳算法的實(shí)現(xiàn)涉及到它的五個(gè)要素：參數(shù)編碼、初始群體的設(shè)左、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)和控制參數(shù)設(shè)左，而每個(gè)要素又對應(yīng)不同的環(huán)境，存在各種相應(yīng)的設(shè)計(jì)策略和方法。不同的策略和方法決左了各自的遺傳算法具有不同的性能或特征。因此，評估遺傳算法的性能對于研究和應(yīng)用遺傳算法是十分重要的。目前，遺傳算法的評估指標(biāo)大多采用適應(yīng)度值。特別在沒有具體要求的情況下，一般采用各代中最優(yōu)個(gè)體的適應(yīng)度值和群體的平均適應(yīng)度值。以此為依據(jù)，DeJong提出了兩個(gè)用于宦量分析遺傳算法的測度：離線性能(Off-linePerformance)測度和在線性能(On-linePerformance)測度，得到兩個(gè)評估準(zhǔn)則。1?在線性能評估準(zhǔn)則定義3?8設(shè)X。(5)為環(huán)境e下策略s的在線性能，/；(/)為時(shí)刻f或第/代中相應(yīng)于環(huán)境e的目標(biāo)函數(shù)或平均適應(yīng)度函數(shù)，則x(s)可以表示為e1/Xg芍孕;(1)(3.9)式(3.9)表明，在線性能可以用從第一代到當(dāng)前的優(yōu)化進(jìn)程的平均值來表示。2?離線性能評估準(zhǔn)則定義3?9設(shè)X；(s)為環(huán)境e下策略s的離線性能，則有1TXO=〒工￡(/)(3.10)式中，fj(t)=best｛femje(2),...￡(小。式(3.10)表明，離線性能是特左時(shí)刻或特左代的最佳性能的累積平均。具體地說，在進(jìn)化過程中，每進(jìn)化一代就統(tǒng)計(jì)目前為I匕的各代中的最佳適應(yīng)度或最佳平均適應(yīng)度，并計(jì)算對進(jìn)化代數(shù)的平均值。Jong指出：離線性能用于測量算法的收斂性，在應(yīng)用時(shí)，優(yōu)化問題的求解可以得到模擬，在一左的優(yōu)化進(jìn)程停止準(zhǔn)則下，當(dāng)前最好的解可以被保存和利用；而在線性能用于測量算法的動態(tài)性能，在應(yīng)用時(shí)，優(yōu)化問題的求解必須通過真實(shí)的實(shí)驗(yàn)在線實(shí)現(xiàn)，可以迅速得到較好的優(yōu)化結(jié)果。但是，從遺傳算法的運(yùn)行機(jī)理可知，在遺傳算子的作用下，群體的平均適應(yīng)度呈現(xiàn)增長的趨勢，因此，左義3.8和左義3.9中的厶(1)和￡；(/)相差不大，它們所反映的性質(zhì)也基本一樣。下而以最優(yōu)化方法的收斂速度和收斂準(zhǔn)則來討論遺傳算法的性能。一般優(yōu)化問題可描述為求x=(冋，孔，…，九)’，使/(X)達(dá)到最小(或最大)。最優(yōu)化方法通常采用迭代方法求它的最優(yōu)解，其基本思想為：給肚一個(gè)初始點(diǎn)心，按照某一迭代規(guī)則產(chǎn)生一個(gè)點(diǎn)列｛旺｝，使得當(dāng)｛兀｝為有窮點(diǎn)列時(shí)，英最后一個(gè)點(diǎn)是最優(yōu)化問題的最優(yōu)解。當(dāng)｛兀｝是無窮點(diǎn)列時(shí)，它有極限點(diǎn)，且苴極限點(diǎn)是最優(yōu)化問題的最優(yōu)解。一個(gè)好的優(yōu)化算法為：當(dāng)能穩(wěn)左地接近全局極小點(diǎn)(或極大點(diǎn))的鄰域時(shí)，迅速收斂于x，當(dāng)滿足給定的收斂準(zhǔn)則時(shí)，迭代終止。假設(shè)一算法產(chǎn)生的迭代點(diǎn)列｛￡｝在某種范數(shù)意義下收斂，即liinll^-x*=0式中，兀+1=xi+ai?ai為步長因子。若存在實(shí)數(shù)a>0及一個(gè)與迭代次數(shù)無關(guān)的常數(shù)0>0,使得則稱此算法產(chǎn)生的迭代點(diǎn)列｛九｝具有q-a階收斂速度(a為迭代步長因子)。因?yàn)?1%-x.il是*-打的一個(gè)估計(jì)，所以在實(shí)際中，一般用||和-對代替卜廠打，作為迭代終止判決條件。當(dāng)a=1,?>0時(shí),稱｛易｝具有§線性收斂速度。當(dāng)1va<2,“>0或a=1,°=0時(shí)，稱｛易｝具有q超線性收斂速度。當(dāng)a=2時(shí)，稱｛兀｝具有q二階收斂速度。具有超線性收斂速度和二階收斂速度的迭代算法的收斂速度比較快.關(guān)于算法的終I匕準(zhǔn)則，實(shí)際應(yīng)用中可以使用各種不同的方法進(jìn)行確定。Himmeblau提岀了而的終止準(zhǔn)則。當(dāng)卜』>￡和|/(無)|>￡時(shí)'采用(3.13)否則采用\XM~Xi\<e或\f(XM)-f(Xi)\<￡(3」4)式中，￡為根據(jù)實(shí)際問題要求精度給出的適當(dāng)小的正數(shù)。根據(jù)以上Himmeblau提岀的終止準(zhǔn)則，實(shí)際中可以用各代適應(yīng)度函數(shù)的均值之差來衡量遺傳算法的收斂特性。左義收斂性測量函數(shù)為：17QG)=〒工［/；(『+1)-力⑴］(3.15)i『■】式中，/;(/)為時(shí)刻/或第f代中相應(yīng)于環(huán)境e的目標(biāo)函數(shù)或平均適應(yīng)度函數(shù)。從優(yōu)化問題中尋找最優(yōu)解或最優(yōu)解組的角度考慮，可以左義部分在線特性:1T人G)=(3.16)1i-\式中，f為群體中對應(yīng)于最優(yōu)解或最優(yōu)解組的個(gè)體適應(yīng)度的均值。3.6小生境技術(shù)和共享函數(shù)Cavicchio提出只有在子串的適應(yīng)度超過父代的情況下，子串才能替代父串進(jìn)入下一代群體的預(yù)選擇機(jī)制，該機(jī)制趨向于替換與其本身相似的個(gè)體，能夠維持群體的分布特性，并且不斷地以優(yōu)秀個(gè)體來更新種群，使種群不斷被優(yōu)化。DeJong提岀基于排擠的機(jī)制，苴思想來源于一個(gè)有趣的生物現(xiàn)象：在一個(gè)有限的生存空間中，各種不同的生物為了延續(xù)生存，必須相互競爭各種有限的生存資源。差別較大的個(gè)體由于生活習(xí)性不同而很少競爭。處于平衡狀態(tài)的大小固泄的種群，新生個(gè)體將代替與之相似的舊個(gè)體。排擠機(jī)制可以維護(hù)當(dāng)前種群的多樣性，排擠機(jī)制用海明距離來度量個(gè)體之間的相似性。這就是小生境技術(shù)。Glodberg和Richardson利用共享函數(shù)來度量兩個(gè)個(gè)體的相鄰關(guān)系和程度。給左個(gè)體g,它的共享函數(shù)由它與種群中其它個(gè)體的相似程度決左。將g與種群中英它個(gè)體逐個(gè)比較