遺傳算法的改進研究及在背包問題中的應(yīng)用.pdf

1、進化計算，作為一種新興的強大的智能優(yōu)化技術(shù)，已經(jīng)廣泛地應(yīng)用在工程科學(xué)的幾乎所有領(lǐng)域。與傳統(tǒng)優(yōu)化方法相比，進化計算在全局優(yōu)化、復(fù)雜設(shè)計區(qū)域、復(fù)雜目標(biāo)函數(shù)及易用性等方面都顯示出了其優(yōu)越性。遺傳算法是進化計算中最重要的算法之一。遺傳算法(Genetic Algorithm—GA)，是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，它是由美國Michigan大學(xué)的John Holland教授于1975年首先提出的。遺傳算法主要的特點在于

2、：簡單、通用、魯棒性強。經(jīng)過三十多年的發(fā)展，遺傳算法已經(jīng)在組合優(yōu)化、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、機器學(xué)習(xí)等領(lǐng)域得到成功的應(yīng)用。 目前，許多學(xué)者已經(jīng)提出了各種遺傳算法，如：量子遺傳算法、免疫遺傳算法、佳點集遺傳算法、自適應(yīng)遺傳算法以及各種改進的遺傳算法等等。本文在眾多學(xué)者研究的基礎(chǔ)上，對已有自適應(yīng)遺傳算法進行深入剖析，進而提出兩個新的自適應(yīng)遺傳算法，并且用于解決0-1背包問題。 1.已有學(xué)者提出了一種只有變異的自適應(yīng)遺傳算法(MO

3、GA)，本文在MOGA的基礎(chǔ)上，引入變換算子和對非法個體的貪婪處理，形成新算法MTGA(Mutation and TranspositionGenetic Algorithm)，它能夠隨時間和個體的適應(yīng)度大小自動調(diào)整變換概率和變異概率，而不需要輸入。 MTGA用在解決0-1背包問題上，編制c程序，在vc++上編譯運行。實驗表明，與簡單遺傳算法相比，從“結(jié)果超過貪婪算法的解的次數(shù)”和“最好求解結(jié)果”上得出：MTGA在解的質(zhì)量上有

4、很大的改進；從“結(jié)果超過貪婪算法解時的平均進化代數(shù)”上得出：MTGA在求解速度方面有很大改進。與混合遺傳算法相比，二者在解的質(zhì)量方面比較接近；而在求解速度方面，MTGA算法明顯好于混合遺傳算法。另外，MTGA也明顯地優(yōu)于MOGA。 2.在基于和環(huán)境進行能量交換的開放系統(tǒng)中存在著復(fù)雜性不斷增長的結(jié)構(gòu)，Prigog—ine將其發(fā)展為常規(guī)的熱力學(xué)概念——耗散結(jié)構(gòu)?？梢园押纳⒔Y(jié)構(gòu)理論引入到遺傳算法中進行分析，初始基因和選擇、交叉、變異算

5、子的作用造就了種群的向前發(fā)展，因而形成一種耗散結(jié)構(gòu)。耗散結(jié)構(gòu)逐漸消失時，算法陷入局部最優(yōu)，交叉和變異算子對遺傳算法的收斂性起著決定作用，所以可以通過對變異算子的操作來改善。在原來基礎(chǔ)上增大變異概率，相當(dāng)于與外界進行更多的物質(zhì)和能量交換，以促進系統(tǒng)繼續(xù)向前發(fā)展。 本文在含有交叉和變異的自適應(yīng)遺傳算法基礎(chǔ)上，引入耗散結(jié)構(gòu)理論，在交叉成功的個體數(shù)和變異概率之間建立聯(lián)系，使交叉成功的個體影響變異概率，并且對非法個體進行貪婪處理，形成新算