陳改霞 耿瑞煥

(鶴壁汽車工程職業(yè)學(xué)院 河南鶴壁 458030)

基于質(zhì)粒模型的DNA計(jì)算機(jī)算法求解背包問(wèn)題

陳改霞 耿瑞煥

(鶴壁汽車工程職業(yè)學(xué)院 河南鶴壁 458030)

本研究在窮舉法的背包策略的基礎(chǔ)上借鑒二表算法的思路，應(yīng)用求解最大團(tuán)問(wèn)題的思路計(jì)算DNA計(jì)算機(jī)的NP完全計(jì)算問(wèn)題。使用這種算法，能將DNA分子計(jì)算的維數(shù)從60擴(kuò)大至120，這種算法的DNA鏈數(shù)可達(dá)亞指數(shù)的O(1 414n)，這種算法拓展了窮舉法背包策略的限制，使DNA計(jì)算機(jī)NP完全問(wèn)題算法優(yōu)化。

質(zhì)粒模型；DNA計(jì)算機(jī)算法；背包問(wèn)題

一、質(zhì)粒模型算法提出的背景

所謂的背包問(wèn)題，是指一種背包組合的原理。它是在容積一定的前提下，要如何組合才能使包中的價(jià)值最大。這個(gè)問(wèn)題研究的核心，是人們要在條件資源已經(jīng)限制的情況下，計(jì)算出收益最大的一種組合方法。背包問(wèn)題的思想經(jīng)常應(yīng)用在優(yōu)化組合的領(lǐng)域上，而DNA計(jì)算的問(wèn)題就是非常典型的優(yōu)化組合的問(wèn)題。

DNA計(jì)算問(wèn)題的實(shí)質(zhì)就是把需要運(yùn)算的對(duì)象當(dāng)作DNA分子鏈，然后通過(guò)某種算法讓這些分子鏈優(yōu)化組合，最后形成一個(gè)結(jié)果，而這個(gè)結(jié)果必須是可控的過(guò)程。這種算法過(guò)程非常復(fù)雜。要得到滿足人們需求的DNA算法。其算法必須滿足以下幾個(gè)要求：要能提出最多的組合方式、該組合方式必須是可控的、組合的結(jié)果必須滿足人們的需求。本次研究以這些算法的需求為方向，提出一種質(zhì)粒模型算法，這種算法的DNA鏈數(shù)可達(dá)亞指數(shù)的O(1 414n)，而 即為背包問(wèn)題的維數(shù)，這種算法的試管級(jí)水平可達(dá)120，使用這種算法是DNA計(jì)算機(jī)算法中極為優(yōu)異的一種算法。

二、質(zhì)粒模型算法應(yīng)用的優(yōu)勢(shì)

計(jì)算機(jī)求解NP的完全問(wèn)題一直是人們認(rèn)為難解的問(wèn)題，如果沒(méi)有一個(gè)合理的算法，它的計(jì)算長(zhǎng)度、計(jì)算時(shí)間、計(jì)算過(guò)程都難以控制。于是人們提出把這種計(jì)算問(wèn)題映射成DNA算法的問(wèn)題，，利用DNA 鏈的思路進(jìn)行計(jì)算。然而應(yīng)用DNA算法的思路求解也存在一些難題。

控制性的難題——DNA計(jì)算機(jī)求解NP的過(guò)程，是一種組合優(yōu)化的問(wèn)題，這種問(wèn)題適合用計(jì)算機(jī)模型來(lái)解決。隨著科學(xué)技術(shù)的發(fā)展，計(jì)算機(jī)的計(jì)算模型也飛速的進(jìn)步，然而就DNA計(jì)算機(jī)求解NP的問(wèn)題而言，它依然存在很多問(wèn)題。其中最大的問(wèn)題為控制性的問(wèn)題。目前DNA計(jì)算中應(yīng)用到雜交、退火、探針的算法，都有可能出現(xiàn)計(jì)算的不穩(wěn)定性，然后出現(xiàn)偽解。為了解決這個(gè)問(wèn)題，必須要使計(jì)算機(jī)模型的算法本身具有穩(wěn)定性。目前質(zhì)粒的DNA計(jì)算機(jī)模型是成功的解決了最大權(quán)團(tuán)的算法問(wèn)題，它在計(jì)算的過(guò)程中不易受到其它醇的干擾。雖然這種算法本身還有一定的難度，可是其穩(wěn)定性與準(zhǔn)確性均能得到保證，這就是計(jì)算的控制性能得到保證。

拓展性的難題——DNA計(jì)算機(jī)算法的原理，是人們提出的以DNA計(jì)算模型為基礎(chǔ)的解3色的問(wèn)題，以這種方式解決給合優(yōu)化的問(wèn)題。然而最初這種原理只能解O(1 67n) 的鏈數(shù)，且這種算法的偽解較多，可拓展性較差，它難以被廣泛的實(shí)踐應(yīng)用。目前人們也提出了其它的DNA計(jì)算機(jī)算法，然而絕大多數(shù)的計(jì)算方法對(duì)時(shí)間和長(zhǎng)度要求很高，其拓展性也比較差?；谫|(zhì)粒模型的算法是以背包問(wèn)題為前提進(jìn)行計(jì)算，它的時(shí)間與長(zhǎng)度都被嚴(yán)格控制，所以它的可拓展性也能得到保證。

準(zhǔn)確性的難題——為了優(yōu)化NDA計(jì)算機(jī)的算法，曾經(jīng)有人提出求解最大團(tuán)的算法，這種思路能夠控制計(jì)算的時(shí)間，它是DNA計(jì)算機(jī)算法的一種新突破。然而如何能確保在一定的時(shí)間內(nèi)控制最大團(tuán)的最高計(jì)算概率，是人們對(duì)這種算法的又一種要求。該次提出的質(zhì)粒模型算法應(yīng)用了背包問(wèn)題的思路解決了在時(shí)間和空間被限制的前提下，提高準(zhǔn)確率的難題。

由于以上質(zhì)粒模型算法的優(yōu)勢(shì)，它能在操作次數(shù)不變的前提下，控制最全部的計(jì)算過(guò)程，得到極高的亞折數(shù)，這種算法在NDA計(jì)算機(jī)算法中非常具有優(yōu)勢(shì)。

三、質(zhì)粒模型算法的基本流程

如果要用背包問(wèn)題的理論控制質(zhì)粒模型的計(jì)算，就要給定以下的數(shù)值：

正整數(shù)q的集合W=(W1,,W2,W3……,Wn)；

正整數(shù)M的數(shù)值；

以上兩者的數(shù)值決定q元組x的數(shù)值，而q可描述為：(x1,x2,x3,……,xq) 。

這種算法能夠以背包問(wèn)題的思路來(lái)解決質(zhì)粒算法的時(shí)間與長(zhǎng)度控制的問(wèn)題，它能提高這類問(wèn)題的并行度。這種算法的核心是使用窮舉法的算法，然而它的背包數(shù)量被限制為60，為了突破背包數(shù)量的限制，該次算法借鑒了二表算法，即應(yīng)用求解最大團(tuán)問(wèn)題的思路計(jì)算DNA計(jì)算機(jī)的NP完全計(jì)算問(wèn)題。

這種計(jì)算思路為將正整數(shù)q的集合W=(W1,,W2,W3……,Wn)拆分為 和 兩個(gè)背包，然后求出兩個(gè)部分的子集和，而子集合的背包容量為O(1 414n)，使用這種二表算法中二表求和的思路以后，再與M進(jìn)行比較，判可否有解轉(zhuǎn)換成先求M與一個(gè)子集所有子集和的差；之后以同樣的方法再用另一個(gè)部分的子集進(jìn)行有解決斷。這種計(jì)算方法既能突破背包的限制，又能使DNA計(jì)算的方法更規(guī)范化。在這種計(jì)算方法中，由于要將背包數(shù)限制為1.14n這個(gè)鏈數(shù)，所以計(jì)算操作時(shí)間與長(zhǎng)度都能得到控制。

這種計(jì)算方法的控制，主要從三個(gè)方面進(jìn)行控制：編譯的問(wèn)題，即在做編譯階段時(shí)，要將求解的問(wèn)題映射到DNA鏈上；以質(zhì)粒模型的思路求解，而求解的長(zhǎng)度控制、時(shí)間控制則由以背包思路控制；使用二表算法優(yōu)化背包思路的算法。該過(guò)程為全部的算法思路。這種算法可描述如下：

賦予數(shù)值環(huán)節(jié)——

步驟1：將集合W=(W1,,W2,W3……,Wn)按升序排列，并將其分成兩個(gè)元素個(gè)數(shù)相等的子集W1和W2。W1取按升序排列好后的W中的前n/2個(gè)元素，而W2取按升序排列好后的W的后n/2。以W1,i表示W(wǎng)1中的第i個(gè)元素，W2,i表示W(wǎng)2的第i個(gè)元素；

輸入數(shù)值環(huán)節(jié)——

步驟2：將實(shí)驗(yàn)杯T0中，給W1,i、W1,i-W1,i、M分量的值進(jìn)行編碼；

步驟3：把T0產(chǎn)生的DNA片段插入到開口的質(zhì)粒中，當(dāng)形成一個(gè)閉環(huán)質(zhì)粒以后，將該質(zhì)粒放入到大腸桿菌中擴(kuò)增；

步驟4：將W1和W2視為背包，將之初始化，把T0產(chǎn)生的質(zhì)粒放入等量的杯子里。杯子可描述為T1和T2。

計(jì)算數(shù)值環(huán)節(jié)——

步驟5：W1子集數(shù)值生成，計(jì)算M與W1里所有子集和的差；

步驟6：W2子集數(shù)值生成，計(jì)算W2里所有子集之合；

輸出數(shù)值環(huán)節(jié)——

步驟7：找出鏈長(zhǎng)相等的質(zhì)粒，該計(jì)算可用凝膠電泳技術(shù)實(shí)現(xiàn)；

步驟8：步驟7中所有的質(zhì)粒所含的背包分量的并即即為所得結(jié)果；

步驟9：輸出數(shù)值結(jié)果，完成計(jì)算流程。

四、總結(jié)

DNA計(jì)算機(jī)NP完全問(wèn)題數(shù)值計(jì)算的問(wèn)題直至現(xiàn)在都被認(rèn)為是難解的數(shù)學(xué)難題。目前人們使用窮舉法解決這個(gè)問(wèn)題，然后用背包思路限制窮舉法數(shù)值計(jì)算的時(shí)間和長(zhǎng)度，然而窮舉法的背包數(shù)量不能滿足人們的需求，它無(wú)法計(jì)算變量數(shù)集多的NP完全問(wèn)題。本次在窮舉法的背包策略的基礎(chǔ)上借鑒二表算法的思路，應(yīng)用求解最大團(tuán)問(wèn)題的思路計(jì)算DNA計(jì)算機(jī)的NP完全計(jì)算問(wèn)題。使用這種算法，能將DNA分子計(jì)算的維數(shù)從60擴(kuò)大至120，，這種算法的DNA鏈數(shù)可達(dá)亞指數(shù)的O(1 414n)，這種算法拓展了窮舉法背包策略的限制，使DNA計(jì)算機(jī)NP完全問(wèn)題算法優(yōu)化。

[1]唐悅.動(dòng)態(tài)規(guī)劃的新形式0/1背包問(wèn)題的兩種解法[J].網(wǎng)絡(luò)科技時(shí)代(數(shù)字沖浪),2002(03).

[2]楊曉燕.溫振華.一種求解背包問(wèn)題的改進(jìn)離散粒子群優(yōu)化算法[J].梧州學(xué)院學(xué)報(bào),2010(03).

[3]王志剛.譚沈陽(yáng).求解0-1背包問(wèn)題的粒子群優(yōu)化算法[J].廊坊師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2010(05).

Solving knapsack problem based on plasmid Model DNA computer algorithm

Chen Gai-xia, Geng Rui-huan
(Hebi Automobile Engineering Vocational College, Hebi Henan, 458030, China)

Draw lessons from the thinking of two table algorithm, this study applied thinking in solving the largest group of DNA computer npcomplete calculation problem. Using this algorithm, the dimensions of the DNA molecular computation can be expanded from 60 to 120, the number of DNA strands of this algorithm can reach the index , expand the exhaustive method backpack strategy, make the algorithm to optimize DNA computer NP complete problem.

plasmid model; DNA computer algorithms; knapsack problem

TP301.6

A

1000-9795（2014）010-000159-02

［責(zé)任編輯： 劉 乾］

陳改霞（1980-），女，漢族，河南周口人，碩士，鶴壁汽車工程職業(yè)學(xué)院講師，研究方向：計(jì)算機(jī)應(yīng)用和計(jì)算機(jī)網(wǎng)絡(luò)。

耿瑞煥（1986-），女，漢族，河南濮陽(yáng)人，碩士，鶴壁汽車工程職業(yè)學(xué)院助教，研究方向：模式識(shí)別、人工智能。