Algorithm For Solving Bin Packing Problem Biology Essay

Prof. Bhagwan Swain Rajdeep Ghosh

Dept. of Information technology, Dept. of Information technology,

Assam University,Silchar Assam University,Silchar

Silchar,India Silchar,India

Email:1980bhagaban@gmail.com Email:grajdeep.21@gmail.com

Abstract-Quantum computing is a relatively new but very promising field of computer science. It provides an alternative way of building computers which are significantly better than current day’s classical computers. Here in this paper, we attempt to develop an algorithm which makes use of the concepts of quantum computers but are actually run on classical computers. Hence this is rather a novel approach. The algorithm is actually an optimization algorithm for solving the much famous bin packing problem (bpp). The algorithm further merges the methodologies followed by evolutionary algorithms.

So, at first we model an overall algorithm based on these concepts. Our algorithm is termed as quantum inspired evolutionary algorithm. With this basic approach we represent each individual solution with a chromosome representation and perform crossover and mutation.

later on we compare these results with standard optimal solution for the problem and present a comparison for the same.

Keywords-Quantum inspired algorithm; Evolutionary Algorithm; Crossover;Mutation;Q-bit;QEA;Bin packing Problem;BPP.

I. INTRODUCTION

Quantum computing is a new field in computer science which has induced intensive investigations and researches during the last decade. It takes its origins from the foundations of the quantum physics. The parallelism that the quantum computing provides reduces obviously the algorithmic complexity. Such an ability of parallel processing can be used to solve efficiently optimization problems. Since there are no powerful quantum machines till today, some ideas such as simulating quantum algorithms on conventional computers or combining them to existing methods have been suggested to get benefit from this new science. In this paper we are using a combination of evolutionary algorithms and quantum computing principles which has already proved its usefulness in solving many problems such as the knapsack problem,multiobjecive image segmentation etc. The proposed approach use quantum bit representation instead of classical bits and use the evolutionary algorithm in addition with particle swarm optimization for obtaining an optimal solution for multi-travelling salesman problem.

II. BIN PACKING PROBLEM

Bin Packing Problem is the problem of packing objects of different weight into a finite number of equal-sized bins in a way that minimizes the number of bins used. Even though this problem seems to be rather simple it is a NP-hard combinatorial optimization problem, i.e., no procedure is able to solve each problem instance in polynomial time. There are so many real life application of Bin Packing Problem, such that Machine scheduling, Recording of all of a composer's music, where the length of the pieces to be recorded are the weights and the bin capacity is the amount of time that can be stored on an audio CD.

A. Formal statement

Given a bin size V and a list of n items with sizes a1,a2,…….,an the aim is to find an integer B and a partition S1US2U.......USn.The objective is to minimize B[5].

B= (1) such that

(2)

and subject to

(3)

(4)

(5)

(6)

III. QUANTUM COMPUTING

Quantum computing is a new theory which has emerged as a result of merging computer science and

quantum mechanics. Its main goal is to investigate all

the possibilities a computer could have if it followed the laws of quantum mechanics. The origin of quantum computing goes back to the early 80 when Richard Feynman observed that some quantum mechanical effects could be used efficiently in computing. During the last decade, quantum computing has attracted widespread interest and has induced intensive investigations and researches since it appears more powerful than its classical counterpart. Indeed, the parallelism that the quantum computing provides reduces obviously the algorithmic complexity. Such an ability of parallel processing can be used to solve combinatorial optimization problems which require the exploration of large solutions spaces. The basic definitions and laws of quantum information theory are beyond the scope of this paper.

A. Qubit

In classical computers there are two bits representing data. But a quantum computer maintains Q-bits. Q-bit has a quaternary nature. The Q-bit is the quantum analogue of the bit, the classical fundamental unit of information. Classical bits can be either in 0 or 1 state. But Q-bits can be in two states denoted by |0〉 or |1〉 or a linear superposition of these two states. The notation | 〉 is called a state, a vector or a ket. A Q-bit is a bit of information that can be both zero and one simultaneously. A Q-byte is made up of eight Q-bits and can have all values from zero to 255 simultaneously. In general the physical state of a Q-bit is the superposition of two states and is given by:

|ψ〉 = α|0〉+β|1〉 (7)

Where, |ψ〉 is the superposition state. α,β are complex numbers. |α|2 represents the probability of finding |ψ〉 in state 0. |β|2 represents the probability of finding |ψ〉 in state 1. This formalism for a quantum bit is a direct extension of one way to describe a classical computer. That is, way may write that a classical bit | ψ 〉 is in the state α|0〉+β|1〉. The only difference is α and β are defined not over the complex numbers but rather from the set {0, 1}. That is {α, β} ϵ {0, 1}.[1],[2]

IV GENETIC ALGORITHM

Genetic algorithms derive from the evolution theory. They were introduced in 1975 by John Holland and his team as a highly parallel search algorithm .In genetic algorithms, this principle is transduced into the problem of finding the best individuals represented by chromosomes.

So, each chromosome encodes a possible solution for the given problem and, starting from a population of chromosomes, the evolution process performs a parallel search through the solutions' space. The fitness is measured for each individual by a function related to the objective function of the problem to be solved. Basically, a genetic algorithm consists of three major operations: selection, crossover, and mutation. The selection evaluates each individual and keeps only the fittest ones in the population. In addition to those fittest individuals, some less fit ones could be selected according to a small probability. The others are removed from the current population. The crossover recombines two individuals to have new ones which might be better. The mutation operator induces changes in a small number of chromosomes units. Its purpose is to maintain the population diversified enough during the optimization process.[8]

V. QUANTUM EVOLUTIONARY ALGORITHM(QEA)

They can be classified into two fields. One concentrates on generating new quantum algorithms using automatic programming techniques such as genetic programming. The other concentrates on quantum-inspired evolutionary computing for a classical computer, a branch of study on evolutionary computing that is characterized by certain principles of interference, coherence, superposition etc. A Q-bit individual is defined by a string of Q-bits. The Q-bit individual has the advantage that it can represent a linear superposition of states (binary solutions) in search space probabilistically. Thus, the Q-bit representation has a better characteristic of population diversity than other representations.[3]

A. Quantum Individual Representation

A Q-bit is defined as the smallest unit of information. A Q-bit individual is defined as a string of Q-bits.

Q(t) = {qt1 , qt2 ,……., qtn} (8)

at generation t ,where, n is the population size, qtj , j = 1,2,….,n , is each Q-bit individual.Since the Q-bit representation is able to express as a linear superposition of states probabilistically, it is profitable for generating diversity in the evolutionary process.

A Q-bit individual is defined as:

(9)

Where,m is the number of Q-bits, and i.e., the string length of the Q-bit individual, and j = 1, 2… n and

|αtj|2 + |β tj|2 = 1. (10)

Initially, QEA can represent diverse individuals probabilistically because a Q-bit individual represents the linear superposition of all possible states with the same probability. As the probability of each Q-bit approaches either |1〉 or |0〉 by the Q-gate, the Q-bit individual converges to a single state and diversity property disappears gradually.[1]

VI. SOLUTION APPROACH

A solution procedure for designing a quantum inspired evolutionary algorithm for bin packing problem as follows: Here all the individuals of the population are represented by as set of chromosomes each representing a possible solution to a problem. The number of chromosomes m represents a population and each chromosome represents a solution and in an individual chromosome each gene or the positive integer in a chromosome represents an item. Each chromosome represents a possible arrangement of items .In each generation new sets of individuals are formed from the existing sets using the genetic procedures crossover and mutation.

The cost of all the individuals in each generation is calculated and are stored which are compared with the cost of individuals of other generations. The lowest cost thus obtained gives the best resulting arrangement.

The Procedure QIEA is as follows:

Begin

For i=1 to popsize //popsize is the population size

t ← 0

initialize Q(t)

make P(t)

repair P(t)

evaluate the cost of individuals

End for

initialize gbest

While (not termination condition) do {

For i=1 to popsize

tt+1

perform crossover Q(t)

perform mutation Q(t)

make P(t) by observing the states of Q(t)

repair P(t)

evaluate the cost of individuals

End for

store gbest

}

End while

End

Where, Q(t) is the Q-bit individual for the number of items to be packed. P(t) is the measured Q-bit individual for the items. Initialize Q(t):In this procedure, at t←0,the chromosomes i.e the Qbit individuals, qtj i.e. are initialized with random probabilities assigned to each of them, such that |α|2+|β|2 =1.It means that in each m-Q-bits, qtj represents the linear superposition of all possible states with the random probability. The Make P(t) can be implemented for each Q-bit individual as follows. When observing the state of Q(t), the value xtj = 0 or 1 of P(t) can be determined by the probability of ||2 or ||2 as follows :After generating the binary string, corresponding decimal value is obtained by converting the binary string into decimal values whereas the procedures repair P(t) are used for repairing the matrices in a accordance with a specific criterion of the packing of bin ,the crossover Q(t) and mutation Q(t) are evolutionary operators used for performing crossover and mutation over the population of individuals . The process in continued until for a fixed number of generations we choose and finally gives the best optimal result for the number of bins.

The Procedure Crossover Q(t)

Crossover is a genetic operator that combines two parent chromosomes to produce a new chromosome (offspring). The idea behind crossover is that the new chromosome may be better than both of the parents if it takes the best characteristics from each of the parents. Crossover occurs during evolution according to a user-defined crossover probability.[3],[8]

Here the procedure crossover is applied to the initially generated population so that new generations are created. We have used the one point crossover technique, which is shown as follows:

If the chromosome is as follows and if the crossover point is at index 4 ,

1

2

3

4

5

8

9

7

6

10

Then the chromosome after crossover would be

5

8

9

7

6

10

1

2

3

4

The pseudocode is as follows:

*rand(); //n is number of items

crossis a temporary array of size (2,n*b); //

k=1;

While (k<m*2+1)

For i=1: point*b

Cross (1,i)=Q(1,i);

Cross (2,i)= Q (2,i);

Q(1, i) = Q(k, i);

Q (2, i) = Qc (k+1,i);

Q (k, i) = cross (1,i);

Q (k+1,i)=cross(2,i);

End for

k=k+2

End While

The Procedure Mutation Q(t)

After the crossover is done, mutation is performed.

Mutation is a genetic operator used to maintain genetic diversity from one generation of a population of chromosomes to the next. Mutation occurs during evolution according to a user-defined mutation probability. Mutation alters one or more gene values in a chromosome from its initial state. This can result entirely in new gene values being added to the gene pool. With the new gene values, the genetic algorithm may be able to arrive at better solution than was previously possible.

Mutation is an important part of the genetic search, it helps to prevent the population from stagnating at any local optima.

The pseudocode for Mutation Q(t) is:

k=1;

While (k<m*2+1

point= ⌈n*rand()⌉ //n is the number of items

a= Qc (k, point);

Qc(k,point)= Qc (k+1,point);

Qc(k+1,point)=a;

k=k+2;

End While

V. RESULT AND COMPARISION

The proposed algorithm is coded in Matlab and implemented on a intel core i3,2.4 GHZ,(2GB RAM), operation system is windows 7. The solution of the

proposed algorithm (QIEA) is compared with the instances from websource1 and was found to give much optimal solutions comparable with the instances in websource1.

Table1:Result and comparision

Problem Instance

Items

Capacity

Best solution Available

Solution Obtained by QIEA

N1C1W1_A

50

100

25

25

N1C1W1_B

50

100

31

31

N1C2W4_B

50

120

32

32

N4C3W4_A

500

150

216

218

N1W1B1R0

50

1000

18

18

N4W1B2R3

500

1000

166

166

HARD0

200

100000

56

57

HARD1

200

100000

57

58

HARD2

200

100000

56

56

D:\Users\Rajdeep\Desktop\bin\data\n1c2w4a copy.jpg

Figure1:Figure showing an instance of N1C2W4_B

1 Prof. Dr. Armin Scholl, Dr. Robert Klein, "http://www.wiwi.uni-jena.de/Entscheidung/binpp/ "publishes the various sized instances along with optimal solutions

D:\Users\Rajdeep\Desktop\bin\data\instances\AS\untitled copy.jpg

Figure2:Figure showing an instance of N1W1B1R0

The program is run for a population size of 5 and a generation size of 5000 and the above results are obtained.

VI. CONCLUSION

This paper proposes an algorithm based on the concepts of Q-bits and inspired by Quantum computing for solving the bin packing problem and have obtained optimal solution for the various problem instances obtained from websource1 .

Moreover ,it has been applied to various other NP Hard problems such as the Knapsack Problem, TSP etc. Thus Quantum Computing has opened new frontiers for solving a variety of optimization problems