0-1規劃問題的膜計算算法

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

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

?

0-1規劃問題的膜計算算法

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

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

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

膜計算;活性膜;規則

0 引言

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

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

1 活性膜P系統定義與相關研究

下面給出與本文工作相關的活性膜P系統的定義,完整詳細的定義可參見[5]與[6].

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

活性膜P系統的一般形式是：

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

其中：m≥1,表示初始狀態時膜結構中包含的膜的數目;

O是符號表(它是非空有限的,每個符號表示膜結構中的一種物質);

H是膜的標簽集;

μ是膜結構,初始狀態時膜的標記為1,2,……m,極性為0,其它狀態下膜的極性集合為{+,-, 0};

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

R是有限的進化規則集,具有以下形式：

如果膜h可以通過規則(e)分裂,同時h中的物質可以通過規則(a)進化.那么通過進化規則得到新膜的過程是：假定先執行規則(a)來改變物質,然后膜進行分裂,在新產生的標記為h的兩個膜中,我們都能得到改變后的物質，當然,這個過程只在一步內完成.

2 0-1規劃問題的膜計算方法

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

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

(1)

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

具體的膜計算規則歸結如下：

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

將變量與其對應的參數進行反應,如果變量值為zi的話將其對應的參數物質溶解掉.如果為oi,將其參數物質轉化為c或g.

這組規則比2)的規則優先級低.

成功匹配,則生成s,否則生成f.如果生成f,這個細胞膜溶解掉,如果生成s,則繼續進行反應(這組規則比3)的優先級低).

我們要使得其中一個組合的極性為負,然后進行分裂;當遇到其膜為中性的并溶解掉這層膜時,則不斷繼續前面的反應.

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

根據組合的個數來分裂次層膜.對每個組合再次進行判斷,沒有用的膜溶解掉,有用的組合保留下來.

7)[r]j→λ.

膜溶解.

3 應用實例

下面通過一個例子來進一步闡明膜計算方法的規則應用：

minz=2x+3y+2z,

(2)

首先,將約束條件轉化為統一形式：

minz=2x+3y+2z,

(3)

然后運用前文的進化規則進行演化.具體演化規則在下面將羅列出來.

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

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

1)初始膜結構：約束條件由內向外表示,膜1為所要求的最優問題

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

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

3)對約束條件(1)進行判定

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

……

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

……

6)求解最優問題

根據膜反應的最后結果,我們知道當x和z取1,y取0時,得到的最優解為4.

4 結論

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

[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]張民, 正偉, 董笑菊. 活性細胞膜計算的可執行性描述與實現[J].上海交通大學學報, 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]殷志祥, 許進. 分子信標芯片計算在0-1整數規劃問題中的應用[J].生物數學學報, 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

海南省高等學校科學研究項目( Hjkj2013-54);海南省自然科學基金項目(614246)

邢潔清(1977-),男,海南文昌人, 海南瓊臺師范高等專科學校信息技術系副教授,碩士,研究方向為為軟件應用和自然計算.

王春騰(1976-),男,海南萬寧人,瓊州學院電子信息工程學院副教授, 碩士,研究方向為軟件工程學和譜聚類.

TP311

A

1008-6722(2015) 02-0020-04

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