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