數(shù)學(xué)建模遺傳算法與優(yōu)化問(wèn)題-wenkub

　

【正文】 gth)。global Count。x*x+2*x+39。,1,2,2,50)執(zhí)行結(jié)果為：Count = 50Result = BestMember = 圖2 例1的計(jì)算結(jié)果（注：上圖為遺傳進(jìn)化過(guò)程中每一代的個(gè)體最大適應(yīng)度；而下圖為目前為止的個(gè)體最大適應(yīng)度——單調(diào)遞增）我們通過(guò)Matlab軟件實(shí)現(xiàn)了遺傳算法，得到了這題在第一種終止條件下的最優(yōu)解：，．當(dāng)然這個(gè)解和實(shí)際情況還有一點(diǎn)出入（應(yīng)該是取1時(shí)，），但對(duì)于一個(gè)計(jì)算機(jī)算法來(lái)說(shuō)已經(jīng)很不錯(cuò)了．我們也可以編制Matlab程序求在第二種終止條件下的最優(yōu)解．此略，留作練習(xí)．實(shí)踐表明，此時(shí)的遺傳算法只要經(jīng)過(guò)10代左右就可完成收斂，得到另一個(gè)“最優(yōu)解”，與前面的最優(yōu)解相差無(wú)幾．四、自己動(dòng)手1． ，求例1的在第二種終止條件下的最優(yōu)解．提示：一個(gè)可能的函數(shù)調(diào)用形式以及相應(yīng)的結(jié)果為：[Count,Result,BestMember]=Genetic2(22,6,39。global CurrentBest。PopulationFitnessF=FitnessF(PopulationFitness,Fmin)。MaxFitness(Count)=CurrentBest(length(CurrentBest))。 Population=NewPopulation。 PopulationFitnessF=FitnessF(PopulationFitness,Fmin)。 EachMaxFitness(Count)=EachGenMaxFitness。Result=ones(2,Dim(1))。BestMember(2,1)=CurrentBest(MumberLength+1)。PopulationFitness=zeros(1,Dim(1))。for i=1:Dim(2) PopulationData=PopulationData+PopulationCode(i)*(2^(MumberLengthi))。PopulationFitness=double(subs(FunctionFitness,39。PopulationFitnessF=zeros(1,Dim(2))。PopulationProbability=PopulationFitness/SumPopulationFitness。 Index=1。%%PopulationProbability=Probability(PopulationFitness)。if Dim(1)=3 Temp=Population(Dim(1),:)。 Site=SiteArray(1)。endNewPopulation=Population。 if ProbabilityMutationProbability if Population(i,Site(1))==1 Population(i,Site(1))=0。[MinFitness,MinSite]=min(PopulationFitness)。 CurrentBest(MumberLength+1)=PopulationFitness(MaxSite)。 endPopulation(MinSite,:)=CurrentBest(1:MumberLength)。遺傳算法(Genetic Algorithm)是這些技術(shù)中的一種，它是一類模擬生物進(jìn)化過(guò)程而產(chǎn)生的由選擇算子、雜交算子和變異算子三個(gè)基本算子組成的全局尋優(yōu)算法。每個(gè)解用其“適應(yīng)值”評(píng)價(jià)。例如父代染色體為和，在第二個(gè)基因后雜交，產(chǎn)生的后代為和。 遺傳算法的特點(diǎn)：(1). 它不是直接作用于參變量集上，而是作用于參變量的某種編碼形成的數(shù)字串上。優(yōu)勢(shì)：(1). 不容易陷入局部極值，能以很大的概率找到全局最優(yōu)解。假設(shè)每個(gè)變量為域內(nèi)的一個(gè)值，且對(duì)所有的。這樣，對(duì)每個(gè)變量，由串長(zhǎng)為的二進(jìn)制編碼表達(dá)可以滿足精度要求。如果確實(shí)有一些關(guān)于最優(yōu)分布的知識(shí)，可以使用這些信息來(lái)設(shè)定初始潛在解的集合。4） 雜交(crossover)和變異(mutation)——決定新群體的性狀：設(shè)雜交概率為，此概率給出預(yù)計(jì)要進(jìn)行雜交的染色體個(gè)數(shù)。兩個(gè)染色體 和 被他們的子代 和 所替代。隨著選擇、雜交和變異的進(jìn)行，新群體就為下一次的評(píng)價(jià)做好了準(zhǔn)備。假定對(duì)每個(gè)變量要求的精度是小數(shù)點(diǎn)后第4位。由于，因此染色體的第一部分需要15位。3） 根據(jù)適應(yīng)值評(píng)價(jià)解的適應(yīng)程度并據(jù)此生成新群體：現(xiàn)在系統(tǒng)為選擇過(guò)程建立一個(gè)輪盤。雜交按照下面的方法進(jìn)行：對(duì)新群體中的每個(gè)染色體，產(chǎn)生一個(gè)在區(qū)間[0, 1]里的隨機(jī)數(shù)，如果，則選擇一個(gè)給定的染色體進(jìn)行雜交。對(duì)這兩對(duì)中的每一對(duì)，產(chǎn)生區(qū)間[1, 32]（33為染色體總長(zhǎng)度）里的一個(gè)隨機(jī)整數(shù)。這對(duì)染色體在第20位后的部分互換，生成的新的染色體對(duì)為：群體的當(dāng)前版本為： 下一步操作——變異是在一位一位基礎(chǔ)上進(jìn)行的。這說(shuō)明我們必須產(chǎn)生660個(gè)隨機(jī)數(shù)。檢查一下新群體的評(píng)價(jià)過(guò)程，對(duì)每個(gè)染色體進(jìn)行解碼，并計(jì)算解碼后的的適應(yīng)函數(shù)值，得到： 。例如。三、遺傳算法的理論基礎(chǔ)： 遺傳算法的理論基礎(chǔ)是遺傳算法解的二進(jìn)制表達(dá)式及模式的含義。例如，考慮長(zhǎng)度為10的串和模式。很明顯，每種模式精確地代表個(gè)串，這里為通配符(*)在模式模板中的個(gè)數(shù)。有兩個(gè)重要的模式性質(zhì)：階和定義長(zhǎng)度。一個(gè)模式的階定義了模式的特殊性。 模式的定義長(zhǎng)度（由表示），為第一個(gè)和最后一個(gè)固定串位之間的距離。模式的定義長(zhǎng)度在計(jì)算模式雜交的存活概率時(shí)很有用，隨后討論。首先從運(yùn)行一個(gè)例子開(kāi)始來(lái)說(shuō)明所有的定理。注意模式的階，其定義長(zhǎng)度。如在先前的例子中看到的那樣，在一個(gè)單個(gè)串的選擇中，串被選擇的概率，其中為整個(gè)群體在時(shí)刻的總適應(yīng)值。如果假定模式高出平均，即，那么 ，且 ，其中，相應(yīng)于平均值之上的模式；相應(yīng)于平均值之下的模式。特別地，在時(shí)刻，預(yù)計(jì)可以得到3*= （可能有4個(gè)或5個(gè)）被模式匹配；在時(shí)刻，有3*= ，即可能有6個(gè)串，等等。可見(jiàn)，模式在時(shí)刻匹配5個(gè)串：、和。以下依次討論兩個(gè)算子作用于群體中模式的效果。因?yàn)殡s交在一個(gè)后代串上保存了第5，6，7位上的序列“111”。注意模式的定義長(zhǎng)度為，而模式的定義長(zhǎng)度為。這說(shuō)明一個(gè)模式的最小存活概率實(shí)際上為：再一次參考前面例子中的模式()： 注意，盡管雜交位置是在一個(gè)模式的固定位置之間選擇的，該模式仍然有機(jī)會(huì)存活。對(duì)模式：這說(shuō)明短的、平均值之上的模式將在下一代中出現(xiàn)幾何增長(zhǎng)的串?dāng)?shù)：在時(shí)刻，預(yù)測(cè)有3*= ；在時(shí)刻，將有3*= 。再一次考慮群體中的一個(gè)串，設(shè)為： ()和模式。這里只有3位（第5，6和7位，即模式的固定位）是很重要的：變異其中之一將破壞模式。很明顯，在平均值之上的、短的定義長(zhǎng)度和低階的模式將按照幾何增長(zhǎng)的速率被復(fù)制。復(fù)制本身并不能增加新的模式（初始時(shí)刻的復(fù)制除外）。生長(zhǎng)公式(3)的最終結(jié)果可以用下面的定理和假設(shè)表示：定理1 模式定理(Schema Theorem)： 短的、低階、平均之上的模式在遺傳算子的后續(xù)代中將按幾何級(jí)數(shù)增長(zhǎng)。遺傳算法在眾多問(wèn)題領(lǐng)域中的應(yīng)用支持基因塊假設(shè)。總的原則是讓適者生存，即適應(yīng)值大的串生存概率要大。剩余部分的填充方法是：把每個(gè)串對(duì)應(yīng)的的小數(shù)部分進(jìn)行排隊(duì)，按從大到小的順序選擇對(duì)應(yīng)的串，直到填滿。對(duì)余下的小數(shù)部分：a. 有退還剩余隨機(jī)選擇：把的小數(shù)部分作為賭盤選擇的權(quán)，利用賭盤選擇決定取舍；b. 無(wú)退還剩余隨機(jī)選擇：把的小數(shù)部分視為概率，一個(gè)一個(gè)地進(jìn)行貝努利試驗(yàn)，其中小數(shù)部分作為成功概率。遺傳算法的參數(shù)空間包括：群體規(guī)模、雜交率、變異率、代間隙、選擇策略和適應(yīng)值變換等。雜交率越高，群體中的串的更新就越快，算法對(duì)解空間的搜索能力越強(qiáng)。● 代間隙：它被引入算法中是允許出現(xiàn)群體重疊的情形，定義在0到1之間，控制每一代群體被替換的百分率。● 適應(yīng)值變換：目的時(shí)提高算法對(duì)適應(yīng)值變化的敏感度。通俗地講就是希望放大串的適應(yīng)值的間隔，不因適應(yīng)值非常接近而無(wú)法選擇適應(yīng)值更好的串。(2) 冪比例變換冪比例變換是比例適應(yīng)值取為原適應(yīng)值的某個(gè)指定冪： ，值一般是依賴于具體問(wèn)題的，在算法執(zhí)行中需要變化以滿足要求的伸縮范圍，即是代的函數(shù)。參數(shù)的值決定了選擇的側(cè)重，越小，選擇強(qiáng)制越趨向于那些具有最高適應(yīng)值的串，值隨著代的演化而增大。”(Davis, 1989)遺傳算法傳統(tǒng)上使用的二進(jìn)制編碼當(dāng)用于多維、高精度數(shù)值問(wèn)題時(shí)會(huì)有一些障礙。編碼應(yīng)該具有這樣的性質(zhì)：在表達(dá)空間里相互靠近的兩個(gè)點(diǎn)也必須在問(wèn)題空間里靠近，反之亦然。(2). “有限困難”：遺傳算法理論解釋了為什么對(duì)一個(gè)給定的問(wèn)題表達(dá)，能收斂到欲求的最優(yōu)點(diǎn)。過(guò)早收斂問(wèn)題是所有優(yōu)化算法共同的問(wèn)題。參考文獻(xiàn)：Michalewicz, Z. (2000). 演化程序——遺傳算法和數(shù)據(jù)編碼的結(jié)合 (中譯本). 科學(xué)出版社.楊文采 (1997). 地球物理反演的理論與方法. 地質(zhì)出版社.１７０。而遺傳算法的執(zhí)行趨向于在找到最優(yōu)解之前過(guò)早地收斂。主要的原因除了上面的“編碼困難”之外，還有“有限困難”，即：理論假定迭代次數(shù)是無(wú)限的，而實(shí)際上有限制；理論上也假定群體規(guī)模是無(wú)限的，實(shí)際上也有限制。一個(gè)可能的解決途徑是采用浮點(diǎn)編碼，目的是使遺傳算法更接近問(wèn)題空間。這本身會(huì)產(chǎn)生一個(gè)大約是101000的搜索空間。因?yàn)楸磉_(dá)方案嚴(yán)重地限制了系統(tǒng)觀察世界的窗口。指數(shù)比例既可讓非常好的串保持較多的復(fù)制機(jī)會(huì)，同時(shí)又限制了其復(fù)制數(shù)目，以免很快控制整個(gè)群體。(1) 線性變換設(shè)原適應(yīng)函數(shù)為，比例適應(yīng)函數(shù)為，則 稱為線性比例變換。3． 適應(yīng)值變換：注意到賭盤選擇要求適應(yīng)值是正的，而目標(biāo)函數(shù)不一定為正，因此需要對(duì)目標(biāo)函數(shù)做變換，即：其中選取一個(gè)適當(dāng)大的數(shù)。中有個(gè)個(gè)體被隨機(jī)地保留到下一代中。● 變異率：變異是增加群體多樣性的搜索算法。規(guī)模太小，群體中所含的模式太少，對(duì)基因塊采樣增長(zhǎng)速率小，且代表性差，最終解的質(zhì)量不高；規(guī)模大的群體包含大量有廣泛代表性的基因塊，可以阻止算法過(guò)早地收斂到局部最優(yōu)解。事實(shí)上，參數(shù)設(shè)置本身也是個(gè)優(yōu)化問(wèn)題。由于賭盤選擇不能保證把最好的個(gè)體保留下來(lái)，因此又提出最優(yōu)選擇：設(shè)是直到第代最好的個(gè)體，按賭盤產(chǎn)生后，若不在中，則把加入中，并隨機(jī)舍棄一個(gè)個(gè)體。按的整數(shù)部分值，分配給該串一個(gè)拷貝數(shù)。四、遺傳算法實(shí)現(xiàn)中的若干問(wèn)題和討論：前面已給出了遺傳算法運(yùn)行步驟的一般描述，通過(guò)一個(gè)實(shí)例具體地考察了它的運(yùn)行步驟，并給出了遺傳算法的理論基礎(chǔ)。假設(shè)1 基因塊假設(shè)(Building Block Hypothesis)： 遺傳算法是通過(guò)并列短的、低階、高效模式（稱之為基因塊）來(lái)尋求接近最優(yōu)的執(zhí)行效果。另外，變異算子向群體引入了較大的變化性。 注意，公式()是基于適應(yīng)值函數(shù)返回正值的假定：當(dāng)用遺傳算法優(yōu)化可能返回負(fù)值的優(yōu)化函數(shù)時(shí)，需要附加一些適應(yīng)值函數(shù)和優(yōu)化函數(shù)之間的映射。 因?yàn)閱蝹€(gè)位變異的概率為，所以單個(gè)位存活的概率為。根據(jù)前一節(jié)的結(jié)果，在第9位變異，其子代為仍然被模式匹配。其變化為從0到1或者相反。因此，模式的存活概率為 所以，選擇和雜交的結(jié)合給出了一個(gè)新的形式的復(fù)制模式生長(zhǎng)公式： (2)公式(2)告訴我們?cè)谙乱淮衅ヅ淠Ｊ?