Implementing in Prolog an Effective Cellular Solution to the Knapsack Problem

Implementing in Prolog an Effective Cellular Solution to the Knapsack Problem Andr´es Cord´on-Franco, Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, Agustin Riscos-N´u˜nez, and Fernando Sancho-Caparrini Abstract. In this paper we present an implementation in Prolog of an effective solution to the Knapsack problem via a family of deterministic P systems with active membranes using 2-division. 1 Introduction The aim of this work is to present an effective solution to the Knapsack problem through a simulator, written in Prolog, implementing deterministic P systems with active membranes using 2-division. The different variants of P systems found in the literature are generally thought as generating devices, and many of them have been proved to be computationally complete. Nevertheless, it is not usual to find in these variants effective solutions to hard numerical problems. The model we study here, P systems with active membranes (see [4], section 7.2.), works with symbol–objects, and one of its most relevant features is that it provides rules for division of membranes. These rules enable the creation of an exponential workspace in linear time, allowing thus the design of efficient cellular solutions. The paper is organized as follows: Section 2 briefly presents a linear-time solution to the decision Knapsack problem using a family of deterministic P systems with active membranes; Section 3 gives some ideas about the simulator developed in Prolog used to implement this solution; a standard work session with the interface provided with the simulator is included in Section 4; finally, in Section 5 some conclusions and future work about the subject of this paper are presented. 2 Solving the Decision Knapsack Problem in Linear Time The decision Knapsack problem can be stated as follows: Given a knapsack of capacity k ∈ N, a set A of n elements, where each element has a “weight” wi ∈ N and a “value” vi ∈ N, and a constant c ∈ N, decide whether or not there exists a subset of A such that its weight does not exceed k and its value is greater than or equal to c. We will represent the instances of the problem using tuples of the form (n, (w1,... ,w n),(v1,...v n),k,c), where nis the size of the set A;(w1,... ,w n) and (v1,...v n) are the weights and values, respectively, of the elements of A; moreover, kand care the two bound constants. We can define in a natural way additive functions wand vthat correspond to the data in the instance. A family of language recognizer P systems with active membranes using 2- division, without cooperation nor dissolution nor priority among rules solving this problem is presented in [5]. We refer the reader to this paper for a complete understanding of the process followed by this family, and for the formal verification that this family in fact solves the Knapsack problem. The family presented there is Π={(Π(n, c, k),Σ(n, c, k),i(n, c, k)):(n, c, k)∈N3}, where n, c, kis a bijection from N3to Ninduced by the pair function x, y= [(x+y)(x+y+1)/2] + xnamely, n, c, k=n, c,k; the input alphabet is Σ(n, c, k)={x1,... ,x n,y 1,... ,y n}; the input membrane is i(n, c, k)=eand the P system Π(n, c, k)=(Γ(n, c, k),{e, s},µ,Ms,Me,R) is defined as follows: •Working alphabet: Γ(n, c, k)={a0,a,¯a0,¯a, b0,b,¯ b0,¯ b,ˆ b0,ˆ b, d+,d −,e 0,... ,e n,q 0,... ,q 2k+1, q, ¯q, ¯q0,... ,¯q2c+1,x 0,... ,x n,y 0,... ,y n, yes, no, z0,... ,z 2n+2k+2c+6,#}. •Membrane structure: µ=[ s[e]e]s. •Initial multisets: Ms=z0;Me=e0¯ak¯ bc. •The set of evolution rules, R, consists of the following rules: (a) [eei]0 e→[eq]− e[eei]+ e,for i=0,... ,n. [eei]+ e→[eei+1]0 e[eei+1]+ e,for i=0,... ,n−1. (b) [ex0→¯a0]0 e;[ ex0→]+ e;[ exi→xi−1]+ e,for i=1,... ,n. [ey0→¯ b0]0 e;[ ey0→]+ e;[ eyi→yi−1]+ e,for i=1,... ,n. (c) [eq→¯qq0]− e;[ e¯a0→a0]− e;[ e¯a→a]− e;[ e¯ b0→ˆ b0]− e;[ e¯ b→ˆ b]− e. (d) [ea0]− e→[e]0 e#; [ea]0 e→[e]− e#. (e) [eq2j→q2j+1]− e, for j=0,... ,k;[ eq2j+1 →q2j+2]0 e, for j=0,... ,k−1. (f) [eq2j+1]− e→[e]+ e#,for j=0,... ,k. (g) [e¯q→¯q0]+ e;[ eˆ b0→b0]+ e;[ eˆ b→b]+ e;[ ea→]+ e. (h) [eb0]+ e→[e]0 e#; [eb]0 e→[e]+ e#. (i) [e¯q2j→¯q2j+1]+ e, for j=0,... ,c;[ e¯q2j+1 →¯q2j+2]0 e, for j=0,... ,c−1. (j) [e¯q2c+1]+ e→[e]0 eyes;[ e¯q2c+1]0 e→[e]0 eyes. (k) [szi→zi+1]0 s,for i=0,... ,2n+2k+2c+5;[ sz2n+2k+2c+6 →d+d−]0 s. (l) [sd+]0 s→[s]+ sd+;[ sd−→no]+ s;[ syes]+ s→[s]0 syes;[ sno]+ s→[s]0 sno. Notice that the membrane labelled with eis the input membrane where the weights and values are provided. This is done via a multiset over the alphabet Σ that is introduced into membrane ebefore starting the computation. Therefore, at the beginning, the multiplicities of objects xjand yj(with 1 ≤j≤n) encode the weights and the values, respectively, of the corresponding elements of A. The multiplicities of ¯aand ¯ bencode the constants kand c, respectively, while the weight and value of the subset associated with each membrane will be encoded as the multiplicity of objects ¯a0and ¯ b0, respectively. The other elements of the working alphabet are used due to technical reasons. 3 The Simulator We use a new version of the P system simulator presented in [2]. This simulator is written in Prolog1. This language is expressive enough to handle symbolic knowledge in a natural way and to deal with complex structures, in our case, configurations of P systems. On one hand, the tree-based data structure and the use of infix operators defined ad hoc by the programmer allow us to imitate the natural language and the user can follow the evolution of the system without any knowledge of Prolog. On the other hand, the structure of membranes and the rules of the systems are Prolog facts and the design of the inference engine that performs the evolutions of the system has a natural treatment from a programmer point of view. In the current version2, the simulator has two different parts. First, we can consider the inference engine. It is a Prolog program which takes as input an initial configuration of a P system and a set of rules, and carries out the evolution. The simulator only explores one branch of the computation tree; therefore, a necessary condition to ensure a faithfully evolution of the system is dealing with aconfluent P system (i.e., all the computations with the same initial configuration must give the same output). Let us emphasize that the inference engine is completely general, that is, it does not depend on the P system considered at all. The second part of the simulator provides a generator tool to automatically build the initial configuration and the set of the rules for concrete instances of some well known NP–complete problems (e.g., SAT, Validity, Subset Sum and, of course, the Knapsack problem). The design of this generator tool allows future additions of specific modules for new problems. These modules could be easily designed by any Prolog user for carrying out his own experiments. The new version of the simulator improves the previous one. The main improvements are related to programming techniques. From an user point of view, the new version provides an easier way of introducing the parameters and offers a broader set of type of problems to solve. Nevertheless, the formal representation 1A good starting point for Prolog can be [1] or [8]. 2Available from the website http://www.cs.us.es/gcn in Prolog of the basic structures of P systems is the same as the one introduced in [2]. In order to clarify the format used for representing the configurations and rules of the system, let us remember that a given configuration for the membrane structure will be expressed by means of a labelled tree. In short,[]istheposition to denote the root of the tree and it will be associated with the skin; then [i] will denote the position of the i-th inner membrane to the skin. In a general form, to denote that in the t-th step of its evolution, a P system Phas a membrane at position [pos] with label h, polarity α, and mas multiset, we shall write P:: hec αat [pos]with mat time t. The rules are also represented as literals, according to the following format: •[hx→y]α h Prule xevolves to [y]in hec α. •x[h]α1 h→[hy]α2 h Prule xout of hec α1sends in yof hec α2. •[hx]α1 h→[h]α2 hy Prule xinside of hec α1sends out yof hec α2. •[hx]α1 h→[hy]α2 h[hz]α3 h Prule xinside of hec α1divides into yinside of hec α2 and zinside of hec α3. It is worth pointing out that each rule is indeed a Prolog fact. Several operators (such as inside of,divides into,... ) have been defined ad hoc in order to obtain a natural-language-like appearance. The simulator also deals with dissolution rules although they are not used in the presented solution to solve the Knapsack problem. 4 A Prolog Session In this section we show a session for one instance of the problem. We consider a set A={a1,a 2,a 3,a 4}with four elements (n= 4), with weights w(a1)=3, w(a2)=2,w(a3)=3,w(a4) = 1, and values v(a1)=1,v(a2)=3,v(a3)=3, v(a4) = 2. The question is to decide whether or not there exists B⊆Asuch that the weights of the elements in Bdo not exceed 3 (k= 3) and their values are greater than 4 (c= 4). According to the design presented in [5], the P system that solves this instance is Π(4,3,4) with input x3 1x2 2x3 3x4y1y3 2y3 3y2 4. The initial configuration associated with the previous instance of the problem is shown in Fig. 1. The following two Prolog facts allow us to represent3this initial configuration (we have chosen the name p1 to denote the P system that solves the above instance of the problem). 3Note that we use ASCII symbols to represent the objects of the alphabet; e.g., a stands for ¯a,b0g stands for ˆ b0, and so on. ' & $ % e0 ¯a3 ¯ b4 x3 1x2 2x3 3x4 y1y3 2y3 3y2 4 0 e ' & $ % z00 s Fig. 1. Initial configuration p1 :: s ec 0 at [] with [z0] at_time 0. p1 :: e ec 0 at[1] with [e0, a_, a_, a_, b_, b_, b_, b_, x1, x1, x1, x2, x2, x3, x3, x3, x4, y1, y2, y2, y2, y3, y3, y3, y4, y4] at_time 0. The simulator automatically generates them from the data typed by the user and stores them in a text file. Observe that the multiplicities of the objects xjand yjcorrespond to the weights and values of the elements aj, respectively. Also, there are three copies of ¯a(k= 3) and four copies of ¯ b(c= 4). In the same way as above, the simulator automatically generates the set of rules associated with the instance of the problem. This generation is done by instantiating several schemes of rules to the concrete values of the parameters. This produces a text file containing the rules that can be easily edited, modified or reloaded by the user. We would like to remark that the set of rules only depends on the parameters n,k, and c. Consequently, if we want to solve several instances with the same parameters, we only need to generate the set of rules once. In this example, we have obtained 89 rules. Some of them are listed in the Appendix. To start with the simulation of the evolution of the P system p1 from the time 0, we type the following command: ?- evolve(p1,0). The simulator returns the configuration at time 1 and the set of used rules indicating how many times they have been used. Moreover, if the skin sends out any object, then this will be reported to the user. The multisets are represented as lists of pairs obj–n, where obj is an object and nis the multiplicity of obj in the multiset. ?- evolve(p1,0). p1 :: s ec 0 at [] with [z1-1] at_time 1 p1 :: e ec -1 at [1] with [a_-3, b_-4, q-1, x1-3, x2-2, x3-3, x4-1, y1-1, y2-3, y3-3, y4-2] at_time 1 p1 :: e ec 1 at [2] with [a_-3, b_-4, e0-1, x1-3, x2-2, x3-3, x4-1, y1-1, y2-3, y3-3, y4-2] at_time 1 Used rules in the step 1: * The rule 1 has been used only once * The rule 57 has been used only once In this step only rules 1 and 57 have been applied. Rule 1 is a division rule, the membrane labelled by eat position [1] divides into two membranes that are placed at positions [1] and [2]; rule 57 is an evolution rule, z0evolves to z1in the skin membrane. To obtain the next configuration in the evolution of p1, now we type: ?- evolve(p1,1). p1 :: s ec 0 at [] with [z2-1] at_time 2 p1 :: e ec -1 at [1] with [a-3, bg-4, q0-1, q_-1, x1-3, x2-2, x3-3, x4-1, y1-1, y2-3, y3-3, y4-2] at_time 2 p1 :: e ec 0 at [2] with [a_-3, b_-4, e1-1, x0-3, x1-2, x2-3, x3-1, y0-1, y1-3, y2-3, y3-2] at_time 2 p1 :: e ec 1 at [3] with [a_-3, b_-4, e1-1, x0-3, x1-2, x2-3, x3-1, y0-1, y1-3, y2-3, y3-2] at_time 2 Used rules in the step 2: * The rule 6 has been used only once * The rule 14 has been used 3 times * The rule 15 has been used 2 times ... evolution rules from set (b) (see Appendix) ... * The rule 22 has been used only once * The rule 25 has been used 4 times * The rule 26 has been used 3 times * The rule 58 has been used only once In this step, the first relevant membrane (that is, one of the membranes having negative charge and containing an object q0) appears at position [1]. This membrane is associated with the empty set. The membrane at position [2] will continue dividing to generate new membranes. All the subsets associated with these descendent membranes will contain the object a1. On the other hand, the membrane at position [3] is responsible of the membranes corresponding to all the nonempty subsets that do not contain object a1. Notice that rules from (b) have been applied. That is, the weight and values calculation stage has already begun. This stage takes place in parallel with the generation one. Immediately after an element ajis added to the associated subset (i.e., when an object ej appears in a membrane with neutral charge), w(aj) new copies of a0 and v(aj) new copies of b0 are generated in the membrane. This process is controlled by the rules in (b), according to the polarity changes produced by the division rules in (a). The purpose of the system’s first stage is to generate a single relevant membrane for each subset of A, i.e., 2n=2 4= 16 relevant membranes in all. Other non relevant membranes are generated as well due to technical reasons. This is done in the first 2n+ 2 = 10 steps of the computation. The simulator also allows us to ask for a configuration at time twithout showing the previous steps by typing the following command. ?- configuration(p1,4). ... p1 :: e ec -1 at [2] with [a-3, a0-3, b0g-1, bg-4, q0-1, q_-1, x1-2, x2-3, x3-1, y1-3, y2-3, y3-2] at_time 4 ... In this step the second relevant membrane is obtained. Note that the electric charge is negative and the object q0 belongs to it. The subset associated with this membrane is the unitary subset {a1}. Let us observe that there are three copies of a0 (w(a1) = 3) and one copy of b0g (v(a1) = 1). ?- evolve(p1,4). ... p1 :: e ec 0 at [2] with [a-3, a0-2, b0g-1, bg-4, q1-1, q_-1, x1-2, x2-3, x3-1, y1-3, y2-3, y3-2] at_time 5 p1 :: e ec -1 at [3] with [a-3, a0-2, b0g-3, bg-4, q0-1, q_-1, x1-3, x2-1, y1-3, y2-2] at_time 5 ... Used rules in the step 5: ... * The rule 27 has been used only once ... In this step, the membrane at position [2] starts the checking stage for the weight function w(note that rule 27 from the set (d) has been applied, see Appendix). A new relevant membrane appears at position [3]. The subset associated with this membrane is the unitary subset {a2}. In the following steps new relevant membranes appear and their corresponding checking stages start. ?- configuration(p1,10). ... p1 :: e ec -1 at [12] with [a-2, a0-2, b0g-5, bg-4, q2-1, q_-1] at_time 10 ... p1 :: e ec -1 at [24] with [a-3, a0-9, b0g-9, bg-4, q0-1, q_-1] at_time 10 ... In this step the relevant membrane associated with the total subset appears at position [24]. It is the last relevant membrane to be generated, that is, no more division will take place in the rest of the computation and no new relevant membranes will appear. Let us focus on the membrane at position [12]. This membrane encodes the subset {a2,a 4}, which is the only solution for the instance considered in our example. There have already been carried out two steps of the checking stage for w(note the counter q2). ?- configuration(p1,16). ... p1 :: e ec 1 at [12] with [b0g-5, bg-4, q_-1] at_time 16 ... The checking stage is finished in this membrane. There was the same amount of objects aand a0 so the checking has been successful. Next, a transition step is carried out that leads to the checking stage for the values. This stage mainly consists in applying rules 44 and 45 (see Appendix) alternatively until we run out of objects b0 or b. ?- configuration(p1,25). ... p1 :: e ec 1 at [12] with [b0-1, q_8-1] at_time 25 ... Notice that the checking for the values has been finished and it has been successful because the number of objects b0 was greater than the number of objects b. Let us pay attention now to the answer stage. ?- evolve(p1,25). p1 :: s ec 0 at [] with [# -127, z26-1] at_time 26 ... p1 :: e ec 0 at [12] with [q_9-1] at_time 26 ... The inner membrane at position [12] is now ready to send to the skin an object yes (see rule 56 in the Appendix). ?- evolve(p1,26). p1 :: s ec 0 at [] with [# -127, yes-1, z27-1] at_time 27 ... p1 :: e ec 0 at [12] with [] at_time 27 ... Used rules in the step 27: * The rule 56 has been used only once * The rule 83 has been used only once Due to technical reasons (cf. [5]) the counter in the skin will wait two more steps before releasing the special objects d+and d−. ?- configuration(p1,29). p1 :: s ec 0 at [] with [# -127, d1-1, d2-1, yes-1] at_time 29 ... In this step all inner processes are over. The only object that evolves is z28 (see the set of rules (k) in Section 2 and note that 28 = 2n+2k+2c+ 6). ?- evolve(p1,29). p1 :: s ec 1 at [] with [# -127, d2-1, yes-1] at_time 30 ... Used rules in the step 30: * The rule 86 has been used only once The P-system has sent out d1 at step 30 In this step the object d1 leaves the system and the skin gets positive charge. ?- evolve(p1,30). p1 :: s ec 0 at [] with [# -127, no-1] at_time 31 ... Used rules in the step 31: * The rule 87 has been used only once * The rule 88 has been used only once The P-system has sent out d1 at step 30 The P-system has sent out yes at step 31 In this step the object yes is sent out of the system. To check the system we try to evolve one more time, though this is a halting configuration. ?- evolve(p1,31). No more evolution! The P-system p1 has already reached a halting configuration at step 31