智能優(yōu)化理論- 課件 第3、4章 遺傳算法、DNA計(jì)算

第3章遺傳算法目錄contents遺傳算法尋優(yōu)的基本思路遺傳算法的理論基礎(chǔ)遺傳算法的實(shí)現(xiàn)及改進(jìn)算法遺傳算法尋優(yōu)的基本思路01遺傳算法是一種基于自然選擇和基因遺傳學(xué)原理的搜索算法，將“適者生存”這一基本的達(dá)爾文進(jìn)化原理引入串結(jié)構(gòu)，并且在串之間進(jìn)行有組織但又隨機(jī)的信息交換。伴隨著算法的運(yùn)行，優(yōu)良的品質(zhì)被逐漸保留并加以組合，從而不斷產(chǎn)生出更佳的個體。好的特征被不斷地繼承下來，壞的特性被逐漸淘汰。新一代個體中包含著上一代個體的大量信息，新一代的個體不斷地在總體特性上勝過舊的一代，從而使整個群體向前進(jìn)化發(fā)展。遺傳算法尋優(yōu)的基本思路研究遺傳算法的目的主要有兩個：一是通過它的研究來進(jìn)一步解釋自然界的適應(yīng)過程；二是為了將自然生物系統(tǒng)的重要機(jī)理運(yùn)用到人工系統(tǒng)的設(shè)計(jì)中。遺傳算法的中心問題是魯棒性，它能在許多不同的環(huán)境中通過效率及功能之間的協(xié)調(diào)平衡以求生存。人工系統(tǒng)很難達(dá)到如生物系統(tǒng)那樣的魯棒性。遺傳算法正是吸取了自然生物系統(tǒng)“適者生存”的進(jìn)化原理，使它能夠提供一個在復(fù)雜空間中進(jìn)行魯棒搜索的方法。遺傳算法尋優(yōu)的基本思路輸入標(biāo)題02010403遺傳算法尋優(yōu)的基本思路遺傳算法具有計(jì)算簡單及功能強(qiáng)的特點(diǎn)，它對于搜索空間基本上不需要什么限制性的假設(shè)（如連續(xù)、導(dǎo)數(shù)存在及單峰等）。枚舉法最大缺點(diǎn)是計(jì)算效率太低，對于一個實(shí)際問題，常常由于太大的搜索空間而不可能將所有的情況都搜索到。枚舉法可以克服上述解析法的兩個缺點(diǎn)，即它可以尋找到全局的極值，而且也不需要目標(biāo)函數(shù)是連續(xù)光滑的。常規(guī)的尋優(yōu)方法主要有3種類型：解析法、枚舉法和隨機(jī)法。解析法尋優(yōu)通過讓目標(biāo)函數(shù)的梯度為零，進(jìn)而求解一組非線性方程來尋求局部極值。遺傳算法的理論基礎(chǔ)0203表現(xiàn)型生物個體表現(xiàn)出來的性狀，即具有特定基因型的個體在一定環(huán)境條件下表現(xiàn)出來的性狀特征的總和。01基因是DNA分子片段，含有大量遺傳信息，是控制生物體性狀的基本遺傳單位。02染色體包含一定數(shù)目的基因，是基因的物質(zhì)載體，也是細(xì)胞中遺傳信息的物質(zhì)載體。遺傳算法的基本概念遺傳算法的基本概念01種群：每個物種由一定數(shù)量的個體組成，所有個體的總和稱為種群。02適應(yīng)度：用于衡量種群中每個個體的優(yōu)劣程度，是度量每個個體對其生存環(huán)境的適應(yīng)能力的標(biāo)準(zhǔn)。03遺傳算法中，適應(yīng)度函數(shù)根據(jù)目標(biāo)函數(shù)設(shè)定，它的大小直接影響到種群中每個個體的生存概率。04一種群為遺傳算法提供了搜索解的遺傳進(jìn)化搜索空間。010203通過一個簡單的例子詳細(xì)描述遺傳算法的基本操作過程，目的在于清晰地展現(xiàn)遺傳算法的理論基礎(chǔ)。設(shè)需要求解的優(yōu)化問題為尋找當(dāng)自變量x在0-31之間取整數(shù)值時函數(shù)的最大值。枚舉的方法是將x取盡所有可能值，觀察是否得到最高的目標(biāo)函數(shù)值。盡管對如此簡單的問題該法是可靠的．但這是一種效率很低的方法。下面運(yùn)用遺傳算法來求解這個問題。遺傳算法的基本操作針對本例中自變量的定義域，可以考慮采用二進(jìn)制數(shù)來對其編碼，這里恰好可用5位數(shù)來表示，如01010對應(yīng)11111對應(yīng)。許多其他的優(yōu)化方法是從定義域空間的某個單個點(diǎn)出發(fā)來求解問題，并且根據(jù)某些規(guī)則，它相當(dāng)于按照一定的路線，進(jìn)行點(diǎn)到點(diǎn)的順序搜索。遺傳算法的第一步是將x編碼為有限長度的串。編碼的方法很多，這里僅舉一種簡單易行的方法。遺傳算法的基本操作對于多峰值問題的求解很容易陷入局部極值。而遺傳算法則是從一個種群（由若干個串組成，每個串對應(yīng)一個自變量值）開始，不斷地產(chǎn)生和測試新一代的種群。這種方法一開始便擴(kuò)大了搜索的范圍，因而可期望較快地完成問題的求解。初始種群的生成往往是隨機(jī)產(chǎn)生的。對于本例，若設(shè)種群大小為4，即含有4個個體，則需按位隨機(jī)生成4個5位二進(jìn)制串，如可以通過擲硬幣的方法來生成隨機(jī)的串。遺傳算法的基本操作若用計(jì)算機(jī)，可考慮首先產(chǎn)生0-l之間均勻分布的隨機(jī)數(shù)．然后規(guī)定產(chǎn)生的隨機(jī)數(shù)在0-0.5之間代表0，0.5-1之間的隨機(jī)數(shù)代表1。若用上述方法，隨機(jī)生成以下4個位串：01101，11000，01000，10011。位串1-4可分別解碼為如下十進(jìn)制的數(shù)遺傳算法的基本操作位串1位串3位串2遺傳算法的基本操作這樣便完成了遺傳算法的準(zhǔn)備工作。位串4選擇、交叉和變異。下面來介紹遺傳算法的3個基本操作步驟遺傳算法的基本操作01適應(yīng)度越大，被選中的概率就越大．從而遺傳到下一代的概率越大。優(yōu)良個體在種群中具有較強(qiáng)的繁殖能力，而適應(yīng)度較差的個體會受到排擠，甚至被淘汰。在選擇算子的作用下，種群的整體質(zhì)量得到逐步提高。在遺傳算法中，以適應(yīng)度為指標(biāo)，把當(dāng)前種群中適應(yīng)度較高的個體選擇出來，為下一步遺傳操作做準(zhǔn)備。020304遺傳算法的基本操作123遺傳算法的特點(diǎn)之一是它不對實(shí)際決策變量直接進(jìn)行操作，而是對表示解的個體編碼進(jìn)行選擇、交叉、變異等遺傳運(yùn)算。編碼是應(yīng)用遺傳算法時要解決的首要問題，也是設(shè)計(jì)遺傳算法時的一個關(guān)鍵步驟。好的編碼方法可以使得交叉運(yùn)算、變異運(yùn)算等遺傳操作簡單易行，而差的編碼方法則可能使得這些操作難以實(shí)現(xiàn)。遺傳個體編碼遺傳個體編碼假設(shè)某一個體的編碼是則對應(yīng)的解碼公式為進(jìn)制編碼方法有下述一些優(yōu)點(diǎn)：編碼、解碼操作簡單易行。遺傳個體編碼03便于利用模式定理對算法進(jìn)行理論分析。01交叉、變異等遺傳操作便于實(shí)現(xiàn)。02符合最小字符集編碼原則。遺傳個體編碼遺傳算法在進(jìn)化搜索中基本不利用外部信息，僅以適應(yīng)度函數(shù)(fitnessfunction)為依據(jù)，利用種群中每個個體的適應(yīng)度值來進(jìn)行搜索。適應(yīng)度函數(shù)的選取至關(guān)重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)轉(zhuǎn)換而成的。對目標(biāo)函數(shù)值域的某種映射變換稱為適應(yīng)度的尺度變換。幾種常見的適應(yīng)度函數(shù)：直接以待求解的目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù)，改進(jìn)的“界限構(gòu)造法”和保守估計(jì)法。適應(yīng)度函數(shù)的作用：在選擇操作時會出現(xiàn)一些問題，如超常個體和種群中個體適應(yīng)度差異較小的情況。適應(yīng)度函數(shù)的設(shè)計(jì)：通常，適應(yīng)度函數(shù)設(shè)計(jì)主要滿足以下條件：單值、連續(xù)、非負(fù)和最大化；合理性和一致性；計(jì)算量小；通用性強(qiáng)。適應(yīng)度函數(shù)及其尺度變換遺傳算法的實(shí)現(xiàn)及改進(jìn)算法03遺傳算法需要提前設(shè)定控制參數(shù)，包括種群大小、交叉概率、變異概率和終止條件。種群大小影響算法效率，太小會降低多樣性，太大則會影響收斂速度。交叉概率一般為0.400～0.990，變異概率在0.001～0.100范圍內(nèi)。遺傳算法的實(shí)現(xiàn)終止條件分為兩類：一類是預(yù)先設(shè)定的最大函數(shù)評價次數(shù)NFE，另一類是未找到最優(yōu)解則終止算法。交叉操作借鑒生物進(jìn)化中兩性繁殖的作用方式，對兩個個體進(jìn)行基因?qū)Q操作產(chǎn)生新個體。變異操作通過對染色體的某些基因位點(diǎn)進(jìn)行突變來產(chǎn)生新的個體，變異的主要作用在于保持種群的多樣性。010203遺傳算法的實(shí)現(xiàn)遺傳算法的實(shí)現(xiàn)在種群中多數(shù)個體趨同的情況下，交叉操作能夠產(chǎn)生的不同于父代個體的數(shù)量非常有限，甚至重復(fù)產(chǎn)生相同的解，而變異操作可以較為有效地異化種群中的個體，增加多樣性，從而在一定程度上避免算法陷入早熟收斂。遺傳算法的改進(jìn)研究編碼策略是遺傳算法的基礎(chǔ)工作之一，在問題求解中扮演著重要的角色。實(shí)際工程優(yōu)化問題中的變量往往不能直接被遺傳算法作用，需要采用編碼策略將實(shí)際變量轉(zhuǎn)化為可以被遺傳算法直接操作的對象。編碼過程實(shí)質(zhì)上是一種“映射”過程，即在優(yōu)化問題與算法涉及的操作對象之間建立一個一一對應(yīng)法則。遺傳算法的改進(jìn)研究針對不同的問題，人們提出了不同的編碼方式，包括二進(jìn)制編碼、格雷編碼和實(shí)數(shù)編碼等。格雷碼克服了二進(jìn)制碼的不足，連續(xù)兩個整數(shù)對應(yīng)的編碼之間僅有一個碼位不同，其余完全相同。二進(jìn)制編碼具有最小字符編碼原理和模式定理，但存在局部搜索能力不強(qiáng)、連續(xù)函數(shù)離散化誤差大、不能反映問題固有結(jié)構(gòu)等缺點(diǎn)。實(shí)數(shù)編碼則針對多維、高精度要求的連續(xù)變量優(yōu)化問題，將每個基因值用實(shí)數(shù)表示，提高了編碼的精度和運(yùn)行效率。自適應(yīng)遺傳算法中，交叉概率和變異概率的選擇是影響算法行為和性能的關(guān)鍵所在。交叉概率越大，新個體產(chǎn)生的速度就越快。然而，當(dāng)交叉概率過大時，遺傳模式被破壞的可能性也會變大。如果交叉概率過小，會使搜索過程變得緩慢，甚至停滯不前。遺傳算法的經(jīng)典變體遺傳算法的經(jīng)典變體變異概率太小，不易產(chǎn)生新的個體結(jié)構(gòu)；太大則變成隨機(jī)搜索算法。02Srinivas等首次提出一種自適應(yīng)遺傳算法(AdaptiveGeneticAlgorithm，AGA)，其中交叉概率與變異概率能夠隨著適應(yīng)度的大小而改變。03當(dāng)群體中各個個體的適應(yīng)度值趨于一致或者趨于局部最優(yōu)時，增加交叉和變異概率；而當(dāng)群體適應(yīng)度值比較分散時，減小交叉和變異概率。01遺傳算法的經(jīng)典變體種群中具有最大適應(yīng)值的個體的交叉概率和變異概率為零，這增大了進(jìn)化趨向局部最優(yōu)解的可能性。對適應(yīng)度值高于群體平均適應(yīng)度值的個體，給予較低的交叉和變異概率，使該個體得以保護(hù)進(jìn)入下一代；而低于平均適應(yīng)度值的個體，基于較高的交叉和變異概率，使該個體被淘汰。改進(jìn)的自適應(yīng)遺傳算法使種群中具有最大適應(yīng)值的個體的交叉概率和變異概率不為零。VS一個刻畫種群多樣性的函數(shù)，在此基礎(chǔ)上提出交叉和變異算子的點(diǎn)數(shù)隨種群多樣性而變化?；旌线z傳算法的實(shí)質(zhì)是將不同算法的優(yōu)點(diǎn)有機(jī)結(jié)合，改善單純遺傳算法的性能。遺傳算法的經(jīng)典變體改進(jìn)的遺傳算法舉例01改進(jìn)的遺傳算法在一個高低不同的層次上都使用了遺傳算法。02生物模型中，遺傳算法是對一個群體進(jìn)行操作，該群體相當(dāng)于自然界中的一群人。第一步的選擇是以現(xiàn)實(shí)世界中的優(yōu)勝劣汰現(xiàn)象為背景的。03010203第二步的交叉則相當(dāng)于人類的結(jié)婚和生育。第三步的變異則與自然界中偶然發(fā)生的變異是一致的。包含著對模式的操作，遺傳算法不斷地產(chǎn)生出更加優(yōu)良的個體。改進(jìn)的遺傳算法舉例標(biāo)準(zhǔn)遺傳算法中的幾個典型操作均可與生物（尤其是人類）的進(jìn)化過程相對應(yīng)。一個種群進(jìn)化到某些特征相對優(yōu)勢的狀態(tài)后便不再有很大變化。正如人類不斷向前進(jìn)化一樣。改進(jìn)的遺傳算法舉例定期地大量移民和通婚可以打破各個民族的平衡態(tài)并推動他們達(dá)到更高層的平衡態(tài)。人類完全可以有目的地通過和平的方式來進(jìn)行各民族的移民和通婚，從而達(dá)到人類進(jìn)化的目的。改進(jìn)的遺傳算法舉例THANKYOU感謝觀看第4章DNA計(jì)算目錄概述DNA的結(jié)構(gòu)DNA計(jì)算的原理DNA與遺傳算法的集成復(fù)習(xí)思考題01概述概述計(jì)算機(jī)技術(shù)被認(rèn)為是20世紀(jì)三大科學(xué)革命之一，電子計(jì)算機(jī)為社會的發(fā)展起到了巨大的促進(jìn)作用。02計(jì)算機(jī)科學(xué)家們也將計(jì)算的問題劃分為容易、困難和不可計(jì)算三類。03處理容易類的計(jì)算，目前的電子計(jì)算機(jī)能完全勝任，但處理困難類的問題時，電子計(jì)算機(jī)會隨著問題規(guī)模的增大，計(jì)算所需的時間以指數(shù)級增長。01量子物理學(xué)已經(jīng)成功地預(yù)測出芯片微處理器能力的增長不能長期地保持下去。計(jì)算機(jī)的小型化在技術(shù)上存在明顯的限制。分子水平上進(jìn)行計(jì)算的概念最早是在20世紀(jì)60年代早期由RichardFeynman提出的。概述01但是當(dāng)時尚缺乏適用的材料、工具與方法，F(xiàn)eynman的“超微型計(jì)算機(jī)”想法只能是一種超前的、美好的愿望。02生物領(lǐng)域發(fā)展到了分子水平，使生物學(xué)的研究深入到了分子水平，到了80年代，隨著人們對分子生物學(xué)理論的了解日益加深，現(xiàn)代生物化學(xué)、生物工程技術(shù)的日益完善，分子計(jì)算的條件事實(shí)上巳基本具備。031994年，美國南加州大學(xué)的LeonardM.Adleman博士用DNA計(jì)算的方法解決了有向Hamilton路問題，并成功地利用現(xiàn)代分子生物技術(shù)在DNA溶液的試管中進(jìn)行了實(shí)驗(yàn)。概述概述01這一研究成果很快引起了計(jì)算機(jī)、數(shù)學(xué)、分子生物學(xué)等領(lǐng)域的科學(xué)家們的極大興趣。02它的重要意義不僅在于算法和速度，更在于采用了一種全新的介質(zhì)作為計(jì)算要件。以生物技術(shù)來解決電子計(jì)算機(jī)無法解決的困難問題，并且開發(fā)了這種媒體潛在的并行性。0302DNA的結(jié)構(gòu)DNA中有4種堿基，即腺嘌呤(Adenine，A)、鳥嘌呤(Guanine，G)、胞嘧啶(Cytosine，C)和胸腺嘧啶(Thymine，T)。各種堿基間的不同組合就構(gòu)成了異常豐富的遺傳信息?？茖W(xué)家們指出．DNA含有大量的遺傳密碼，通過生化反應(yīng)傳遞遺傳信息。DNA鏈主要是由一個脫氧核苷酸上的5'-磷酸基和另一個脫氧核苷酸上的3'-羥基共價鍵連接而成。DNA的結(jié)構(gòu)DNA由兩條極長的核苷酸鏈利用堿基之間的氫鍵結(jié)合在一起，形成一條雙股的螺旋結(jié)構(gòu)，且一股的堿基序列與另一股的堿基序列互補(bǔ)。A和T配對．C和G配對。堿熬的上述配對關(guān)系稱為Watson-Crick（WC）配對。DNA有兩個最主要的功能：第一個功能是DNA攜帶遺傳信息，能轉(zhuǎn)錄成RNA，RNA再轉(zhuǎn)譯成蛋白質(zhì)；第二個功能是自我復(fù)制。DNA的結(jié)構(gòu)DNA一般為長而無分支的雙股線型分子，但有些為環(huán)形，也有少些為單股環(huán)形。每個染色體是一段雙股螺旋的DNA。遺傳信息以A、T、C和G在核苷酸中的排列順序而體現(xiàn)，其排列順序的多樣性體現(xiàn)了豐富的遺傳信息。從生物DNA到蛋白質(zhì)的形成過程。首先，通過轉(zhuǎn)錄作用將DNA中攜帶的遺傳信息轉(zhuǎn)錄到信使RNA（mRNA）中。DNA的結(jié)構(gòu)在從DNA到蛋白質(zhì)的形成過程中，大多數(shù)堿基并沒有用來合成蛋白質(zhì)．它們首先從DNA上轉(zhuǎn)錄，將沒有用的部分拼接，拼接后就形成了mRNA。密碼子對應(yīng)于氨基酸的遺傳密碼表如表4.1所示。然后，通過翻譯作用，將mRNA中攜帶的遺傳信息轉(zhuǎn)譯成含特定氨基酸序列的蛋白質(zhì)，蛋白質(zhì)則構(gòu)成了細(xì)胞。在生物DNA中，基因是儲存遺傳信息的基本單位，一個基因開始于起始密碼子ATG，終止于終止密碼子TAA、TAG或TGG。在mRNA中排列著由三個連續(xù)的堿基組成的密碼子，這些密碼子是合成蛋白質(zhì)的密碼。64種密碼子對應(yīng)20種氨基酸。DNA的結(jié)構(gòu)03DNA計(jì)算的原理DNA計(jì)算是一種新的計(jì)算思維方式，同時也是關(guān)于化學(xué)和生物的一種新的思維方式。生物與數(shù)學(xué)的過程有各自的復(fù)雜性，但它們具有一個重要的共性，即生物所具有的復(fù)雜結(jié)構(gòu)實(shí)際上是結(jié)構(gòu)的編碼在DNA序列中的原始信息經(jīng)過一些簡單的生化處理后得到的。求一個含有變量的可計(jì)算函數(shù)的值也可以通過求一系列含變量的簡單函數(shù)的值來實(shí)現(xiàn)。DNA計(jì)算的原理DNA計(jì)算的本質(zhì)就是利用大量不同的核酸分子雜交，產(chǎn)生類似于某種數(shù)學(xué)過程的一種組合的結(jié)果，并根據(jù)限定條件對其進(jìn)行篩選的。大量隨機(jī)的DNA相互雜交后，每個DNA鏈所攜帶的原始信息就會與其他DNA鏈所攜帶的信息重新組合，形成一種類似數(shù)學(xué)組合的結(jié)果。根據(jù)DNA分子之間的Watson-Crick互補(bǔ)原理，不同的DNA分子根據(jù)其不同的末端，從而具有不同的方向性。DNA計(jì)算的原理VS對一種特定的運(yùn)算而言，這種結(jié)果的獲得是通過對DNA進(jìn)行一系列的連續(xù)操作來實(shí)現(xiàn)的。DNA計(jì)算就是利用不同形式的DNA鏈編碼信息，然后將攜有編碼信息的DNA鏈進(jìn)行互補(bǔ)雜交，最后，利用分子生物技術(shù)，如聚合酶鏈?zhǔn)椒磻?yīng)PCR(PolymerizeChainReaction)、并行重疊組裝技術(shù)POA(ParallelOverlapAssembly)、超聲波降解、親和層析、克隆、誘變、分子純化、凝膠電泳、磁珠分離等，捕獲運(yùn)算結(jié)果。DNA計(jì)算的原理經(jīng)典的計(jì)算科學(xué)理論是建立在一系列重要操作上的，大部分自動機(jī)語言理論模型都是這樣的。DNA計(jì)算也是建立在一系列連續(xù)的分子操作上的，這些用于計(jì)算目的的分子生物操作在形式上具有多樣性：切割、粘貼、分離、連接、插入和刪除等。從理論上來講，合理地使用這些分子生物操作可以建立與圖靈機(jī)一樣強(qiáng)大的新的計(jì)算模型。DNA計(jì)算的原理DNA計(jì)算的原理從DNA的原理和一些生物操作工具來看，DNA計(jì)算與數(shù)學(xué)操作非常相似。DNA單鏈可看做由四個不同符號A、G、C和T組成的鏈。它在數(shù)學(xué)上就像計(jì)算機(jī)中的編碼“0”和“1”一樣，可表示成四個字母的集合∑={A，G，C，T）來編碼信息。04DNA與遺傳算法的集成DNA鏈（染色體）表現(xiàn)型DNA湯（群體）倒位基因型遺傳子座是多個遺傳因子的集合，由A、T、C、G編碼集合組成。是遺傳物質(zhì)的主要載體。DNA鏈上遺傳因子的位置，各個位置決定所遺傳的信息。是形成DNA鏈的內(nèi)部表現(xiàn)，它決定了生物體的性狀和特征。由DNA鏈決定形狀的外部表現(xiàn)，或者說是根據(jù)基因型形成的個體。DNA鏈帶有特征的個體的集合，該集合內(nèi)的DNA鏈的多少為DNA湯的大小。在DNA鏈中兩個隨機(jī)選擇位置之問的某些堿基序列進(jìn)行倒位。它可以使在父代中離得很遠(yuǎn)的位在后代中靠在一起．相當(dāng)于重新定義基因塊?；靖拍詈托g(shù)語不過一個是用試管在分子生物學(xué)實(shí)驗(yàn)室里實(shí)施運(yùn)算，一個是用程序語言實(shí)現(xiàn)運(yùn)算，圖4.2給出了它們基本運(yùn)算框架的異同。啟發(fā)人們從兩個不同的領(lǐng)域相互借鑒，利用分子生物學(xué)新理論、新技術(shù)進(jìn)行遺傳算法的擴(kuò)展。遺傳算法和DNA計(jì)算有很多相似之處，如對特定符號集編碼的符號串進(jìn)行操作、具有很高的并行性等。DNA遺傳算法的關(guān)系和假設(shè)一些學(xué)者提出了基于DNA機(jī)理的改進(jìn)的遺傳算法，如帶有雙串DNA的遺傳算法用于促進(jìn)DNA復(fù)制的非對換變異。還提出了基于生物學(xué)DNA編碼方法的遺傳算法，這種方法具有DNA染包體中的重復(fù)性和基因表達(dá)的重疊性．并使交叉和變異操作變得容易。為了避免在DNA計(jì)算中，由于核酸堿基之間化學(xué)反應(yīng)帶來的誤差，一些研究者提出了用于DNA進(jìn)化計(jì)算中好的DNA譯碼算法。DNA遺傳算法的關(guān)系和假設(shè)遺傳算法可以直接使用DNA計(jì)算方法來實(shí)現(xiàn)，如JunghueiChen等人就成功地使用對DNA分子進(jìn)行操作的遺傳算法解決了一個最大數(shù)問題。目前有關(guān)遺傳算法和DNA計(jì)算兩者交叉領(lǐng)域的研究成果并不多見，但鑒于遺傳算法已取得的巨大成功和DNA計(jì)算具有的極大潛力，未來二者結(jié)合會對生物計(jì)算技術(shù)以及相關(guān)領(lǐng)域產(chǎn)生革命性的推進(jìn)作用。DNA遺傳算法的關(guān)系和假設(shè)使用n個具有任意DNA鏈的個體組成初始代群體(DNA湯)一條DNA鏈由4種堿基A、T、C、G的結(jié)合體構(gòu)成．可以表示多個基因。按編碼規(guī)則，將DNA湯中每一個DNA鏈的密碼子按表4.2（或表4.3）轉(zhuǎn)化成所對應(yīng)的參數(shù)值用于求解問題，并按某一標(biāo)準(zhǔn)計(jì)算其評價函數(shù)。DNA遺傳算法的實(shí)現(xiàn)適應(yīng)度的評價初始化及DNA鏈編碼若其評價函數(shù)值高，表示該DNA鏈有較高的適應(yīng)度。由于將DNA的4個堿基中的3個組合成密碼子的情況有64種．在翻譯參數(shù)時可將這64種組合對應(yīng)于[0,63]區(qū)間上的任意一個數(shù)，用于問題的求解。這里考慮的翻譯關(guān)系與生物DNA的遺傳密碼表不同，即不同的密碼子對應(yīng)于不同的參數(shù)。而在生物DNA中．允許不同的密碼子對應(yīng)相同的氨基酸（參見表4.2）。若其值在預(yù)定的范圍內(nèi)變化．那么密碼子的參數(shù)和實(shí)際