邢潔清, 王春騰, 駱銘鴻, 肖 群

(1. 瓊臺(tái)師范高等專科學(xué)校 信息技術(shù)系,海南 海口571100; 2. 瓊州學(xué)院 電子信息工程學(xué)院,海南 三亞 572022; 3. 重慶大學(xué) 計(jì)算機(jī)學(xué)院,重慶 400044)

?

0-1規(guī)劃問題的膜計(jì)算算法

邢潔清1, 王春騰2, 駱銘鴻3, 肖 群1

(1. 瓊臺(tái)師范高等?？茖W(xué)校 信息技術(shù)系,海南 ?？?71100; 2. 瓊州學(xué)院 電子信息工程學(xué)院,海南 三亞 572022; 3. 重慶大學(xué) 計(jì)算機(jī)學(xué)院,重慶 400044)

膜計(jì)算系統(tǒng)試圖利用分子生化反應(yīng)完成計(jì)算任務(wù),相較于電子計(jì)算機(jī)有諸多優(yōu)勢(shì).研究采用活性膜計(jì)算解決0-1規(guī)劃問題.構(gòu)建出一個(gè)典型的膜系統(tǒng),建立解決0-1規(guī)劃問題的模型,先對(duì)問題編碼,通過規(guī)則刪除不可行解,逐步得到最優(yōu)解.為此類問題的解決提出了新的方法,最后還給出了實(shí)例的應(yīng)用.構(gòu)建出的膜系統(tǒng)也同樣適用于解決其他優(yōu)化問題.

膜計(jì)算;活性膜;規(guī)則

0 引言

膜計(jì)算(Membrane Computing)是自然計(jì)算的一個(gè)新分支,其目的是從活細(xì)胞中以及組織、器官或其他結(jié)構(gòu)的細(xì)胞之間相互協(xié)作的方式中獲得新的計(jì)算思想、設(shè)計(jì)新的計(jì)算模型[1].膜計(jì)算的計(jì)算模型稱為膜系統(tǒng)(也稱為P系統(tǒng)).膜計(jì)算的計(jì)算能力已被證明是圖靈等價(jià)的.膜計(jì)算所具有的最大特點(diǎn)是它的并行性,可將其分為膜內(nèi)并行，膜間并行,膜內(nèi)串行膜間并行等形式.每一個(gè)膜我們都可以將其看作是一個(gè)計(jì)算單元,膜與膜之間通過“物質(zhì)”(物質(zhì)可以是分子、離子、微分子等)進(jìn)行通信,膜內(nèi)的各規(guī)則可以并行地執(zhí)行.

很多相應(yīng)的文章[1-3]中膜只是作為物質(zhì)的分界或是物質(zhì)交換的通道,它們以被動(dòng)的方式來參與整個(gè)反應(yīng)過程.我們所用的是活性膜的計(jì)算模型,它是膜計(jì)算中一種特殊的計(jì)算模型.模型中的細(xì)胞膜具有溶解和分裂性.通過細(xì)胞膜的分裂而使細(xì)胞膜的數(shù)量呈指數(shù)增長(zhǎng),新生成的細(xì)胞膜又可以參與計(jì)算,從而達(dá)到更快的計(jì)算速度[4].可以利用活性細(xì)胞膜計(jì)算在線性時(shí)間內(nèi)解決可滿性問題等NP問題[5].我們用于解決0-1規(guī)劃問題,為此類問題的解決提供了新的思路.

1 活性膜P系統(tǒng)定義與相關(guān)研究

下面給出與本文工作相關(guān)的活性膜P系統(tǒng)的定義,完整詳細(xì)的定義可參見[5]與[6].

定義 一個(gè)膜結(jié)構(gòu)是一個(gè)唯一的膜里面放置了多個(gè)膜(我們把這個(gè)指定唯一的膜也稱其為皮膚).用一對(duì)中括號(hào)來代表一層膜,這個(gè)膜可以被標(biāo)記上+,-或者是0,這代表的是它們的極性.

活性膜P系統(tǒng)的一般形式是：

П=(O,H,μ,w1,……，wm,R);

其中：m≥1,表示初始狀態(tài)時(shí)膜結(jié)構(gòu)中包含的膜的數(shù)目;

O是符號(hào)表(它是非空有限的,每個(gè)符號(hào)表示膜結(jié)構(gòu)中的一種物質(zhì));

H是膜的標(biāo)簽集;

μ是膜結(jié)構(gòu),初始狀態(tài)時(shí)膜的標(biāo)記為1,2,……m,極性為0,其它狀態(tài)下膜的極性集合為{+,-, 0};

wi(i=1,2,……m)是膜i中的多重集;

R是有限的進(jìn)化規(guī)則集,具有以下形式：

如果膜h可以通過規(guī)則(e)分裂,同時(shí)h中的物質(zhì)可以通過規(guī)則(a)進(jìn)化.那么通過進(jìn)化規(guī)則得到新膜的過程是：假定先執(zhí)行規(guī)則(a)來改變物質(zhì),然后膜進(jìn)行分裂,在新產(chǎn)生的標(biāo)記為h的兩個(gè)膜中,我們都能得到改變后的物質(zhì)，當(dāng)然,這個(gè)過程只在一步內(nèi)完成.

2 0-1規(guī)劃問題的膜計(jì)算方法

0-1規(guī)劃問題如(1)式,其變量xi僅取值0或1,這時(shí)xi成為0-1變量,或者二進(jìn)制變量[7].

max(min)z=c1x1+c2x2+…+cnxn,

(1)

0-1規(guī)劃問題在線性整數(shù)規(guī)劃中具有重要的地位,它是運(yùn)籌學(xué)中規(guī)劃論方面的一個(gè)重要問題,當(dāng)前研究出解決它的算法很多,如隱枚舉法,窮舉法等.由于0-1規(guī)劃有廣泛應(yīng)用,故對(duì)它進(jìn)行研究得到的結(jié)果也越來越多,所獲算法的效率也越來越高[4].在此,我們采用活性膜分裂方法從另一角度來解決這一問題.首先構(gòu)造出所有問題的可能解,然后根據(jù)約束條件逐步刪除不滿足的解來得到問題的解空間[2,3,6].

具體的膜計(jì)算規(guī)則歸結(jié)如下：

我們用兩個(gè)變量zi和oi取代了一個(gè)變量xi.這個(gè)膜將被分裂成兩個(gè)膜(分裂后的兩個(gè)膜維持電中性).通過n步我們產(chǎn)生了所有變量所有可能的組合.

將變量與其對(duì)應(yīng)的參數(shù)進(jìn)行反應(yīng),如果變量值為zi的話將其對(duì)應(yīng)的參數(shù)物質(zhì)溶解掉.如果為oi,將其參數(shù)物質(zhì)轉(zhuǎn)化為c或g.

這組規(guī)則比2)的規(guī)則優(yōu)先級(jí)低.

成功匹配,則生成s,否則生成f.如果生成f,這個(gè)細(xì)胞膜溶解掉,如果生成s,則繼續(xù)進(jìn)行反應(yīng)(這組規(guī)則比3)的優(yōu)先級(jí)低).

我們要使得其中一個(gè)組合的極性為負(fù),然后進(jìn)行分裂;當(dāng)遇到其膜為中性的并溶解掉這層膜時(shí),則不斷繼續(xù)前面的反應(yīng).

k≥1,n>k,hiH,0≤i≤n,a0……a6{+,-,0}和{a1,a2}={+,-}.

根據(jù)組合的個(gè)數(shù)來分裂次層膜.對(duì)每個(gè)組合再次進(jìn)行判斷,沒有用的膜溶解掉,有用的組合保留下來.

7)[r]j→λ.

膜溶解.

3 應(yīng)用實(shí)例

下面通過一個(gè)例子來進(jìn)一步闡明膜計(jì)算方法的規(guī)則應(yīng)用：

minz=2x+3y+2z,

(2)

首先,將約束條件轉(zhuǎn)化為統(tǒng)一形式：

minz=2x+3y+2z,

(3)

然后運(yùn)用前文的進(jìn)化規(guī)則進(jìn)行演化.具體演化規(guī)則在下面將羅列出來.

在進(jìn)行具體演化之前,先作如下說明:第0層膜代表皮膚;第1層膜(膜1)代表我們要求解的目標(biāo)函數(shù),其中a的下標(biāo)i代表的是第i個(gè)變量前面的常量,a的上標(biāo)代表的是該常量的個(gè)數(shù);從第2層膜(膜2)往里演化約束反應(yīng)式,物質(zhì)的下標(biāo)代表對(duì)應(yīng)的常量,上標(biāo)代表該常量的個(gè)數(shù),e和d代表負(fù)常量,a代表正常量,b代表約束值;最內(nèi)層的x表示優(yōu)化變量,其下標(biāo)對(duì)應(yīng)不同的變量;c、f、o、s、r、z代表膜物質(zhì),參與反應(yīng),具體參見本文第2節(jié)中的規(guī)則.

我們給出如下具體演化過程：

1)初始膜結(jié)構(gòu)：約束條件由內(nèi)向外表示,膜1為所要求的最優(yōu)問題

2)并行演化如下分裂規(guī)則

可得到全部可能的解,羅列如下：

3)對(duì)約束條件(1)進(jìn)行判定

4)對(duì)符合條件的組合讓其與約束(2)進(jìn)行判定

……

5)滿足的組合對(duì)約束條件(3)進(jìn)行判定

……

6)求解最優(yōu)問題

根據(jù)膜反應(yīng)的最后結(jié)果,我們知道當(dāng)x和z取1,y取0時(shí),得到的最優(yōu)解為4.

4 結(jié)論

膜計(jì)算具有良好的并行性,在解決類似于本文運(yùn)籌學(xué)規(guī)劃論的這一類相關(guān)困難問題時(shí),尤其是完全問題上，具有“硅計(jì)算機(jī)”無法比擬的優(yōu)勢(shì).文中在利用活性膜的基礎(chǔ)上,利用對(duì)每個(gè)約束條件的判斷來不斷地刪除不可解組合,最后得到可行性解.這種思想不僅可以用在0-1規(guī)劃問題上,在其他的組合優(yōu)化問題中也同樣適用.接下來我們將進(jìn)行的研究工作重點(diǎn)是改進(jìn)該算法模型使其更加簡(jiǎn)化.

[1]DassowJ ,Paun G. On the power of membrane computing[J].Journal of Universal Computer Science,1999, 5(2):33-49.

[2]PingGuo, Jing Chen. Arithmetic Operation in Membrane System[DB/OL].(2008-5-27)[2014-11-9].http://www.computer.org/csdl/proceedings/bmei/2008/3118/01/3118a231-abs.html.

[3]Ping Guo, HaiyanZhang. Arithmetic operation in single membrane[DB/OL].(2008-12-14)[2014-11-9].http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4722399.

[4]張民, 正偉, 董笑菊. 活性細(xì)胞膜計(jì)算的可執(zhí)行性描述與實(shí)現(xiàn)[J].上海交通大學(xué)學(xué)報(bào), 2008, 42(10) : 1635-1639.

[5]Paun G. P systems with active membranes:Attacking NP complete Problems[J].Journal of Automata Languages and combinatorics, 2001, 6(1): 75-90.

[6]Paun G. Computing with membranes[J].Journal of Computer and System Science,2000, 61(1):108-143.

[7]殷志祥, 許進(jìn). 分子信標(biāo)芯片計(jì)算在0-1整數(shù)規(guī)劃問題中的應(yīng)用[J].生物數(shù)學(xué)學(xué)報(bào), 2007,22(3):559-564.

P-system Computation for 0-1 Programming Problem

XING Jie-qing1, WANG Chun-teng2, LUO Ming-hong3,XIAO Qun1

(1. Department of information technology, Qiongtai teachers college, Haiko Hainan, 571100, China; 2. College of Electronics and Information Engineering, QiongZhou University, Sanya Hainan 572022, China; 3. Department of Computer Science, Chongqing University, Chongqing 400044, China)

Membrane computing systems attempt to use molecular biological and chemical reaction to complete computing tasks, compared to computer has many advantages. This paper built a typical membrane computing systems, and gave a model to solve 0-1 programming problem. In the membrane system, at first, encoding the problem, then through the rules to delete feasible solution, and gradually get the optimal solution. Membrane system proposed in this paper that can be used to solve other optimization problems.

P-system; active-membranes; rules

2014-11-26

海南省高等學(xué)?？茖W(xué)研究項(xiàng)目( Hjkj2013-54);海南省自然科學(xué)基金項(xiàng)目(614246)

邢潔清(1977-),男,海南文昌人, 海南瓊臺(tái)師范高等專科學(xué)校信息技術(shù)系副教授,碩士,研究方向?yàn)闉檐浖?yīng)用和自然計(jì)算.

王春騰(1976-),男,海南萬寧人,瓊州學(xué)院電子信息工程學(xué)院副教授, 碩士,研究方向?yàn)檐浖こ虒W(xué)和譜聚類.

TP311

A

1008-6722(2015) 02-0020-04

10.13307/j.issn.1008-6722．2015．02．05