胡 娟, 殷志祥 ,張麗麗

1 引 言

1994年, Adleman博士在Science上發(fā)表論文，首次用DNA計(jì)算成功地解決了有向Hamilton路問題[1],人類從此進(jìn)入了借助DNA分子的生化反應(yīng)來進(jìn)行計(jì)算的嶄新時(shí)代。此后DNA分子生物算法用它運(yùn)算的高度并行性﹑大容量和低消耗幫助很多的學(xué)者解決了許多NP完全問題，1997年，Ouyang就利用分子生物學(xué)技術(shù)解決了圖的最大團(tuán)問題[2]，建立了一個(gè)與六頂點(diǎn)群整體相對(duì)應(yīng)的DNA分子池，并進(jìn)行了一系列的選擇過程，這項(xiàng)工作證明了DNA計(jì)算具有解決NP完整搜索問題的能力。此后Paun G等在1998年，編著了《DNA Computing：New Computing Paradigms》,在此專著中就用Sticker模型很好的解決了NP問題集合的最小覆蓋問題[3]，再一次證明了DNA計(jì)算NP問題能力。2000年Lila Kari等又用DNA計(jì)算很好地解決了限定郵路一致性問題[4]。

排課問題在高校教務(wù)管理系統(tǒng)中是一項(xiàng)重要又復(fù)雜的問題，早在1975年，N.L.Lawri,D.C.Wood和S.Even等人就證明了此問題為NP完全問題[5]，很多學(xué)者用各種方法來解決這個(gè)問題，如動(dòng)態(tài)規(guī)劃[6]、圖像著色法[7-8]等。近些年來更多的學(xué)者用智能算法如粒子群算法﹑遺傳算法[9]等作用于解決排課問題，也都取得了很好的效果。此后，研究DNA計(jì)算方法的學(xué)者也成功地將DNA計(jì)算很好地應(yīng)用于解決排課問題。如2007年周康等給出了閉環(huán)DNA計(jì)算模型[10]；2012年殷志祥等給出了AcryditeTM分離技術(shù)DNA模型[11]；2014年單靜怡﹑殷志祥給出了基于表面DNA計(jì)算模型解決排課問題[12]。本文在0-1規(guī)劃問題[13]的基礎(chǔ)上給出了一種基于芯片的DNA計(jì)算模型解決排課問題，并對(duì)模型進(jìn)行了簡要分析。

2 排課表問題與生物算法

排課表問題是涉及到教師﹑教室﹑班級(jí)﹑課程和時(shí)間的NP完全問題。其主要目標(biāo)就是按照教學(xué)計(jì)劃將教師﹑教室﹑班級(jí)﹑課程合理的安排在一周內(nèi)某一個(gè)不發(fā)生沖突的時(shí)間里[14]。簡單的排課問題與0-1規(guī)劃問題的思想基本相同。本文在0-1規(guī)劃的基礎(chǔ)上，提出了基于芯片的DNA計(jì)算模型，在實(shí)驗(yàn)中，采用熒光標(biāo)記技術(shù)，通過觀察熒光將每次結(jié)果進(jìn)行記錄，通過比較，就可以得到需要解決問題的可行解[15]。

排課表問題有軟約束和硬約束，怎樣在所給定的約束條件下得出最優(yōu)的排課表是我們需要解決的問題。

下面簡單的構(gòu)造一個(gè)排課表DNA計(jì)算模型。假設(shè)有4個(gè)班級(jí)需要3名教師，怎樣用最少的課時(shí)排課。3名教師分別用t1,t2,t3表示，4個(gè)班級(jí)分別用s1,s2,s3,s4表示，2間教室分別用c1,c2表示，班級(jí)對(duì)應(yīng)的上課情況為D=(dij) 如下：

(1)

其中行表示為4個(gè)班級(jí)，列表示為3名教師，0表示這名教師在此班級(jí)沒有課，1則表示有課。

這里我們給定一定的約束條件：一個(gè)班級(jí)在一個(gè)課時(shí)不能參加兩門課的學(xué)習(xí)，一名教師在一個(gè)課時(shí)不能給兩個(gè)班級(jí)上課。具體要求為：班級(jí)s4只能夠在第二課時(shí)由教師t3上課，班級(jí)s1,s4只能夠在c1教室上課，而班級(jí)s2卻只能夠在c2教室上課。

圖1變量的編碼圖

圖2所有課時(shí)情況芯片點(diǎn)樣矩陣

生物算法：(1)對(duì)不同的變量生成相對(duì)應(yīng)的DNA鏈，按照問題的要求，將一定量點(diǎn)樣于事先已處理好的芯片上，用黃熒光對(duì)相應(yīng)變量的補(bǔ)鏈進(jìn)行標(biāo)記。(2)將上述芯片與一定量變量的補(bǔ)鏈混合，由于補(bǔ)鏈會(huì)與其對(duì)應(yīng)的變量相雜交并產(chǎn)生黃色熒光，由熒光成像技術(shù)就能找到符合問題要求的芯片點(diǎn)列。(3)加熱表面，在嚴(yán)格條件下沖洗沒有雜交上芯片，恢復(fù)其DNA鏈。(4)重復(fù)(2)、(3)，依次檢驗(yàn)所有芯片點(diǎn)列(不再考慮已經(jīng)符合要求的芯片點(diǎn)列)，分析每次的結(jié)果即可得滿足約束條件的課時(shí)安排。

3 DNA計(jì)算的算法及其實(shí)現(xiàn)過程

3.1 編碼

對(duì)于上面的實(shí)例，給定編碼如下：

3.2 生物操作

3.2.1 由公式(1)班級(jí)上課的情況，將一定量的DNA鏈s1,s2,s3,s4, c1,c2點(diǎn)樣于事先已處理好的芯片上(如圖2)，列表示為教師t1,t2,t3給班級(jí)上課的情況，空為此教師在此班級(jí)沒有課或此班級(jí)不限制在此教室上課。經(jīng)過驗(yàn)證點(diǎn)樣排列的矩陣是可以尋址的,因此方法是有效的。

3.2.2 先對(duì)第一課時(shí)進(jìn)行選擇，在這一循環(huán)過程中，我們分三步進(jìn)行。

圖3加入的雜交反應(yīng) 圖4加入的雜交反應(yīng)

圖5加入的雜交反應(yīng) 圖6加入的雜交反應(yīng)

3.3 實(shí)驗(yàn)分析

從這一實(shí)驗(yàn)中得知，要想得到滿足需要的課程安排，可由熒光顏色得到，結(jié)果如表1。

表1 課程安排

在此類排課表問題中，若dij≥2,即教師ti給班級(jí)sj至少需要上兩節(jié)課時(shí)，可增加班級(jí)sj1,sj2,…,sjm，使m=dij-1,給D增加m行,使其僅含有0,1，即可用此模型來計(jì)算。

4 結(jié)論分析

文章對(duì)排課表這一數(shù)學(xué)中的NP完全問題，提出了一種基于DNA芯片的計(jì)算模型。該模型可以不改變所給問題的初始的點(diǎn)列，采用熒光標(biāo)記技術(shù)，通過觀察熒光將每次結(jié)果進(jìn)行記錄，通過比較，就可以得到需要解決問題的可行解。對(duì)于研究規(guī)模較大的問題簡單方便。模型應(yīng)用了DNA的芯片技術(shù)，能有效地解決更多此類問題，從而實(shí)現(xiàn)自動(dòng)化。