An Improved Chaotic Bat Algorithm for Solving Integer Programming Problems

Published Online August 2014 in MECS DOI: 10.5815/ijmecs.2014.08.03

The real world optimization problems are often very challenging to solve, and many applications have to deal with NP-hard problems [1]. To solve such problems, optimization tools have to be used even though there is no guarantee that the optimal solution can be obtained. In fact, for NP problems, there are no efficient algorithms at all. As a result of this, many problems have to be solved by trial and errors using various optimization techniques [2]. In addition, new algorithms have been developed to see if they can cope with these challenging optimization problems. Among these new algorithms, many algorithms such as particle swarm optimization, cuckoo search and firefly algorithm, have gained popularity due to their high efficiency. In this paper we have used IBACH algorithm for solving integer programming problems. Integer programming is NP-hard problems [3-10].The name

“linear integer programming “is referred” to the class of combinatorial constrained optimization problems with integer variables, where the objective function is a linear function and the constraints are linear inequalities.” The Linear Integer Programming (also known as LIP)

optimization problem can be stated in the following general form:

Max cx(1)

s.t. Ax ≤ b,(2)

x∈Zn(3)

where the solution x ∈ Zn is a vector of n integer variables: x = (x 1 , x 2 , …, x n )^T and the data are rational and are given by the m×n matrix A, the 1×n matrix c, and the m×1 matrix b. This formulation includes also equality constraints, because each equality constraint can be represented by means of two inequality constraints like those included in eq. (2).

Integer programming addresses the problem raised by non-integer solutions in situations where integer values are required. Indeed, some applications do allow a continuous solution. For instance, if the objective is to find the amount of money to be invested or the length of cables to be used, other problems preclude it: the solution must be discrete [3]. Another example, if we are considering the production of jet aircraft and x1 = 8.2 jet airliners, rounding off could affect the profit or the cost by millions of dollars. In this case we need to solve the problem so that an optimal integer solution is guaranteed.

The possibility to obtain integer values is offered by integer programming:  as a pure integer linear programming, in which all the variables must assume an integer value, or as a mixed-integer linear programming which allows some variables to be continuous, or a 0-1 integer model, all the decision variables have integer values of zero or one[10].

A wide variety of real life problems in logistics, economics, social sciences and politics can be formulated as linear integer optimization problems. The combinatorial problems, like the knapsack-capital budgeting problem, warehouse location problem, travelling salesman problem, decreasing costs and machinery selection problem, network and graph problems, such as maximum flow problems, set covering problems, matching problems, weighted matching problems, spanning trees problems and many scheduling problems can also be solved as linear integer optimization problems [11-14].

Exact integer programming techniques such as cutting plane techniques [15-17]. The branch and the bound both have high computational cost, in large-scale problems [18-19]. The branch and the bound algorithms have many advantages over the algorithms that only use cutting planes. One example of these advantages is that the algorithms can be removed early as long as at least one integral solution has been found and an attainable solution can be returned although it is not necessarily optimal. Moreover, the solutions of the LP relaxations can be used to provide a worst-case estimate of how far from optimality the returned solution is. Finally, the branch method and the bound method can be used to return multiple optimal solutions.

Since integer linear programming is NP-complete, for that reason many problems are intractable. So instead of the integer linear programming, the heuristic methods must be used. For example, Swarm intelligence metaheuristics, amongst which an ant colony optimization, artificial bee colony optimization particle swarm optimization [20-24]. Also Evolutionary algorithms, differential evolution and tabu search were successfully applied into solving integer programming problems [25-27]. Heuristics typically have polynomial computational complexity, but they do not guarantee that the optimal solution will be captured. In order to solve integer programming problems, most of the heuristics truncate or round the real valued solutions to the nearest integer values. In this paper, Bat algorithm is applied to integer programming problems and the performance was compared with other harmony search algorithms.

This paper is organized as follows: after introduction, the original Bat Algorithm is briefly introduced in section 2. Section 3 introduces the meaning of chaos. In section 4, the proposed algorithm is described, while the results are discussed in section 5. Finally, conclusions are presented in section 6.

• II.    The original Bat Algorithm

  Bat Algorithm has been developed by Xin-She Yang in 2010 [28]. The algorithm exploits also called echolocation of bats. Bats use sonar echoes to detect and avoid obstacles. It is generally known that sound pulses are transformed to frequency which is reflected from obstacle. Bats can use time delay from emission for

reflection and use it for navigation. They typically emit short and loud sound impulses and the pulse rate is usually defined as 10 to 20 times per second. After hitting and reflecting, bats transform their own pulses to useful information to gauge how far away the prey is. Bats use wavelengths, that vary from range (0.7, 17) mm or inbound frequencies (20,500) kHz. By implementation, pulse frequency and pulse rates have to be defined. Pulse rate can be simply determined from range 0 to 1, where 0 meaning there is no emission and 1 meaning bats are emitting maximum (5-8). This behaviour can be used to formulate the new bat algorithm. Yang [28] used three generalized rules for Bat Algorithm:

I All bats use echolocation to sense distance, and they also predict the difference between food/prey and background barriers in some magical way.

II Bats fly randomly with velocity vi at position xi with a fixed frequency fmin, varying wavelength λ and loudness A0 to search for prey. They can automatically adjust the wavelength (or frequency) of their emitted pulses and adjust the rate of pulse emission r ∈ [0, 1], depending on the proximity of their target.

III III. Although the loudness can vary in many ways, we assume that the loudness varies from a large (positive) A0 to a minimum constant value Amin. Initialization of the bat population is performed randomly. Generating the new solutions is performed by moving virtual bats according the following equations:

fi = fmin + (fmax - fmin)β ,(4)

vit = vit-1 +(xit-1 - best)fi,(5)

xit = xit-1 + vit ,(6)

where β ∈ [0, 1] is a random vector drawn from a uniform distribution. Here X is the current global best solution which is located after comparing all the solutions among all the bats.

For the local search part, once a solution is selected among the current solutions, a new solution for each bat is generated located using random walk [29-33].

x new

= x_o ld + ε A_t

where ε is the scaling factor and A i^t is the loudness, the loudness A₀ and the rate r_i of pulse emission have to be updated accordingly as the iterations proceed. These equations are:

A i^t+1 = α A i^t r i^t+1 = r ⁰i [1- exp(- γ t)]

where α and γ are constants.

The basic steps of BA can be summarized as the pseudocode shown in Figure 1.

Bat Algorithm

Begin

Objective function f (x), x = (x 1 , ...,x d )^T

Initialize the bat population x i and v i for (i = 1,2, ...,n )

Define pulse frequency f i at x i

Initialize pulse rates r i and the loudness A i

While (t

Generate new solutions by adjusting frequency and,

Updating velocities and locations/solutions (equations 4 to 6) if (rand (0,1)> r i )

Select a solution among the best solutions

Generate a local solution around the best solution

End if

Accept the new solutions

Increase r i and reduce A i

End if

Rank the bats and find the current best

End while

Post process results and visualization

End

Fig. 1 Pseudo code of the bat algorithm

• 2    . The Sine map

The Sine map is written as the following equation:

Yn+1 = sin(πYn)Yϵ (0,1) 0<μ≤4

• 3    . Iterative chaotic map

The iterative chaotic map with infinite collapses is described as:

Yn+1 =sin( ? ) μ∈(0,1)

• 4    . Circle map

The Circle map is expressed as:

Yn+1 =Y n +α-(  ) sin(2πY n ) mod 1

• III.    Chaos Theory

Generating random sequences with longer periods and good consistency is very important for easily simulating complex phenomena, sampling, numerical analysis, decision making and especially in heuristic optimization [34]. Its quality determines the reduction of storage and computation time to achieve a desired accuracy [35]. Chaos is a deterministic, random-like process found in a nonlinear, dynamical system, which is non-period, nonconverging and non-bounded. Moreover, it depends on its initial condition and parameters [36-38]. Applications of chaos has several disciplines including operations research, physics, engineering, economics, biology, philosophy and computer science [39-41].

Recently chaos has been extended to various optimization areas because it can more easily escape from local minima and improve global convergence in comparison with other stochastic optimization algorithms [37-42]. Using chaotic sequences in Bat Algorithm can be helpful to improve the reliability of the global optimality, and they also enhance the quality of the results.

• A. Chaotic maps

  At random-based optimization algorithms, the methods using chaotic variables instead of random variables are called chaotic optimization algorithms (COA) [37]. In these algorithms, due to the non-repetition and ergodicity of chaos, it can carry out overall searches at higher speeds than stochastic searches that depend on probabilities [4352]. To resolve this issue, herein one-dimensional and non-invertible maps (are mathematical systems that model a single variable as it evolves over discrete steps in time) are utilized to generate chaotic sets. We will illustrate some of well-known one-dimensional maps as:

• 1    . Logistic map

The Logistic map is defined by:

Yn+1 = μ Y n (1- Y n ) Ү∈(0,1) 0 < µ ≤ 4

• 5    . Chebyshev map

The family of Chebyshev map is written as the following equation:

Y n+1 = cos(kcos-1 (Y n)) Ү∈(-1,1)

• 6    . Sinusoidal map

• 7 . Gauss map

• 8 . Sinus map

This map can be represented by

Y n+1=μYк sin(πYn)

The Gauss map is represented by:

0Y =0

Y n+1 = { £ mod 1  Yn≠0

Sinus map is formulated as follows:

Y n+1 = 2.3(Yn) 2sin (nYn)

• 9 . Dyadic map

Also known as the dyadic map bit shift map, 2x mod 1 map, Bernoulli map, doubling map or saw tooth map. Dyadic map can be formulated by a mod function:

Yn+1 =2Y_n mod 1            (18)

• 10    . Singer map

• 11 .Tent map

Singer map can be written as:

Yn+1 = μ(7.86Yn - 23.31Y2 + 28.75Y - 13.3YП

µ between 0.9 and 1.08

This map can be defined by the following equation:

μY n         Yn<0.5

n+l ={μ(1-Y n )   Y n ≥0.5

• IV.    The Proposed Algorithm (IBACH) for Solving Integer Programming Problems

In the proposed chaotic Bat algorithm, we used chaotic maps to tune the Bat algorithm parameters and improve the performance [40]. The steps of the proposed chaotic Bat Algorithm for solving integer programming problems are as follows:

Step 1 Set the initial conditions: population x i (i = 1, 2 ...n) and V i , pulse frequency fiat x i and pulse rates r i and the loudness A i

Step 2 Calculate the average position and the optimal position of the bat colony.

Step 3 Using the equations 4 to 6 update velocities and locations/solutions and Generate new solutions by adjusting frequency.

fi = fmin + (fmax -fmin)Si ,where si ≡ chaotic map(21)

vit = vit-1 + (xit-1-best)fi*Si(22)

xit = xit-1 + vit(23)

Step 4 If (rand > ri) then select a solution among the best solutions and generate a local solution around the selected best solution with the following equation xnew=xold+εAt(24)

Where ε ∈ [-1,1] If not, skip this step.

Step 5 If (rand < A_i &f(x_i) < f(x)) then accept the new solutions. Increase r_i and reduce A_i with the following two equations

A i^t+1 = α A i^t                  (25)

r i^t+1 = r i⁰ [1-exp(- γ t)]                (26)

If not, skip this step.

Step 6 Rank the bats and find the current best X .

Step 7 If the iterations attain to the maximum number, then stopped and output the global optimal solution. If not, go to step 2 to continue the search.

• A. Handling Constraints

One of the well-known techniques of handling constraints is using penalty function, which transforms constrained problem into unconstrained ones, consisting of a sum of the objective and the constraints weighted by penalties. By using penalty function methods, the objectives are inclined to guide the search toward the feasible solutions. Hence, in this paper the corresponding objective function used in is defined and described as:

K minF(x) = f (x)+λ∑max(0,gn)

^{n = 1}                        (27)

where f(x) is the objective function for assignment problem, λ is the penalty coefficient and it is set to 107 in this paper , K is the number of constraints and gn the constraints of the problem.

• V.    Numerical Results

  Several examples have been done to verify the weight of the proposed algorithm. The initial parameters setting of the algorithms is as follows: HMS=50 and itermax=1000, HMCR = 0.9; PAR max = 1; PAR min =0.1; bw_max = 1; bw_min = 0.01; n= 40, f_min= 0 ,f_max= 2, A 0 = 0.5 ,r = 0.5. The results of IBACH algorithm are

conducted from 50 independent runs for each problem and measured according to the best values in these runs .The selected chaotic map for all examples is the Sinusoidal map, whose equation is shown below:

Y n+1 = µ Y k ²sin( π Y n )               (28)

Where n is the iteration number, all the experiments were performed on a Windows 7 Ultimate 64-bit operating system; processor Intel Core i5 760 running at 2.81 GHz; 4 GB of RAM and codes were implemented in C#.

• A.    Test Problem 1

Max z= 7x1+9x2 s.t.

• -x₁+3x₂≤6 7x 1 +x 2 ≤35 x₁, x₂ ≥ 0 and integer.

• B.    Test Problem 2

Max w= 4x1+6x2+2x3 s.t.

4x 1 -4x 2 ≤ 5

• -x₁+6x₂≤5

• -x₁+x₂+x₃≤5

x1,x2,x3 ≥ 0 and integer.

• C.    Test Problem 3

Min z = -5x1+7x2+10x3-3x4+x5 s.t.

x₂-2x₃-x₄+x₅ ≤ -2 x₁+3x₂-5x₃+x₄+4x₅ ≥ 0 2x₁+6x₂-3x₃+2x₄+2x₅ ≥ 4 x i = 0 or 1 ,i=1,2,…,5.

• D.    Test Problem 4

Max z= 3x1-2x2+4x3+5x4+x5+x6+2x7-6x8+x9-x10 s.t.

x1+5x2+3x3 ≥8 x7+5x8+2x9+x10 = 7 4x1+x2+3x3+x4+x7 ≤4 6x1+x5+x6+3x8-2x9 ≤5 4x1-2x2+3x3-4x4+5x5 ≥2 -x1+x2+2x3-x4+x5+7x7 ≤3 -3x1-x2+4x3-x4+2x5+5x6+9x8+x10 =10 xi≥ 0 , i=1,2,…,10 and integer

• E.    Test Problem 5

Min z = 3x₁ -2x₂ + 5x₃ + x₄ - x₅ + 2x₆ + 7x₇ + 3x₈ + 11x₉ + 22x₁₀ -15x₁₁ + 9x₁₂ + 7x₁₃ -13x₁₄ + x₁₅ + 8x₁₆ + 19x₁₇ + 4x₁₈ -9x 19 + 10x 20 s.t.

x 16 +3x 18 + 9x 19 + x 20 ≥ 11

3x8 + 7x17 + 8x19 + x20 ≥ 18

x7 + x13 + x15 + 3x16 + 3x18 ≤ 25

x1 + x2 +12x7 + 5x8 + 6x15 - x18 ≤ 6

• - 3x₃ -2x₄ + 7x₅ -9x₆ + x₁₃ +5x₁₇ ≥ 21

x6 -7x10 + 3x11 + x12 + 8x13 -9x14 ≥ 4

• - 3x₁ + x₂ + 8x₃ + x₁₅ +22x₁₉ - x₂₀ ≤ 83

5x1 + 8x2 + 7x3 + x6 + 2x7 + 9x12 + 7x15 ≤ 9

10x1 + 2x6 - x10 + 6x11 + 11x13 + 8x15 -9x19 = 40

2x1 + 3x2 -7x4 + 4x5 + 18x9 + x11 9x15 + 4x16 ≥ 10

3x1 -7x2 -2x4 + 3x6 + 8x8 -4x10 + 11x12 + 5x14 + 7x19 ≥ 32 22x1 + 8x3 + 8x5 + 18x7 + 4x8 -3x10 + 19x11 -8x17 + x18 ≥ 17 x1 + 3x2 - x3 + 7x4 + 11x5 + 18x8 + 5x14 + 11x17 + x18 +4x20 ≥ 22

• - 8x₁ + 5x₃ - x₅ + x₇ + x₉ + 5x₁₀ -7x₁₁ + x₁₃ + x₁₅ + 8x₁₇ + 2x₂₀ ≥ 9

4x₁ + 5x₆ + x₈ +14x₁₀ + 11x₁₂ + x₁₃-5x₁₄ + x₁₅ + 11x₁₆ + 3x₁₈ + 3x 20 ≥ 16

xi ≥0, i=1,2,…,20 and integer.

• F.    Test Problem 6

max Z= x1 + 2x2 + 7x3 + 2x4 + x5 + 4x6 + x7 -5x8 + x9 +

2x₁₀ + 4x₁₁ + 7x₁₂ + 5x₁₃ + 3x₁₄ + 9x₁₅ + 5x₁₆ + x₁₈ + 8x₁₉ + 6x 20 + x 21 -3x 22 + 7x 23 - x 24 -3x 25 + 2x 26 + x 27 + 9x 28 + 7x 29 + 4x 30

s.t.

2x1 + 2x3 + x12+ 9x15 -3x20 + 3x29 ≤ 70

2x1 + 5x5+ 2x13 + 2x15 + 2x16 + 2x28 ≤ 19

x2 + x3 + x4 + x7 + 2x8 + x11+8x14 + 2x25 ≤ 20

2x 8 - x 11 -3x 12 -3x 13 + 2x 19 + x 20 +3x 22 + x 23 ≤ 11

• -3x₁₁ + x₁₄ + 3x₁₅ + 2x₁₆ + x₁₈+ 2x₂₂ + 2x₂₆ ≤ 95

2x12 + x14 + 2x15 + 2x18 + 2x24 + 2x25 + 3x27 ≤ 40

x2 + x3 + x4+ 2x8 + 2x10 + x17 + x18 + x20 + x21 + x22 ≤ 35

4x1 + 2x9 + x10+3x13 + 3x16 -9x17 + x18 + x24 + 5x27 + 4x29 + x30 ≤ 40

• -3x₅ + x₉ +2x₁₂ + 5x₁₃ + 4x₁₆ + x₁₇ + x₁₉ + x₂₁+ 4x₂₅ -3x₂₇ + 2x 30 ≤ 100

5x₁ + x₃ + x₅ + 2x₆ + x₈ + 2x₉ - x₁₀+5x₁₂ + x₁₄ + x₁₅ + 3x₁₆-9x 17 + x 18 ≤ 7

x₁+ 2x₆ + 2x₇ + 2x₁₄ + 11x₁₅ + x₁₆ -3x₂₁ + 10x₂₄ + 2x₂₅ + 8x₂₆ -3x 28 + 11x 29 ≤ 62

x2 + x4 + x7 + x9 + 2x11 -9x13 + 2x17 + 5x18 + x20 + x21 4x24

+ 3x26 + 5x27 + 4x30 ≤ 51

x1 + x3 + 2x4 + 2x6 + 3x7 + 2x8 -2x10 + 2x13 -5x15 + 2x19 +

3x 20 + 4x 21 + 3x 23 + 4x 28 ≤ 22

2x₂ + x₄ + 5x₅ + 4x₆ + 2x₇ + 3x₁₃ + 8x₁₇ + 2x₁₉ + x₂₁ + 2x 22 + 2x 23 + 2x 24 + 10x 25 -3x 26 + 2x 27 + 3x 28 + 2x 29 + x 30 ≤ 60

xi ≥0, i=1,2,…,30 and integer.

Table 1 Optimal solution of selected problems

	Exact method		The Best Solution
	Optimal sol.	Optimal values	PSO[24]	HS[53]	IHS[54]	BA[28]	IBACH
problem1	55	X i =(4,3)	55	55	55	55	55
problem2	26	X i =(2,1,6)	24	21	25	24	26
problem3	9	X i =(1,1,0,0,0)	8	7	9	9	9
problem4	9	X i =(0,2,0,2,3,1,0,0,2,3)	7	6	7	7	9
problem5	16	X i =(0,0,0,0,0,0,0,0,0,1,4,0,4,3,0,2,4,0,3,0)	14	11	13	14	16
problem6	446	X i =(0,0,0,0,0,0,0,0,0,16,20,4,4,0,3,0,0,0,24,3,0,0,0,0,0,4,0,1,0,8)	443	405	422	440	446

Table 1 shows the results of IBACH algorithm are privileged compared with the results of particle swarm optimization (PSO), Standard harmony search algorithm (HS), standard bat algorithm (BA) and improved harmony search algorithm (IHS). In comparison with exact values we find that the results of IBACH algorithm are very close to the exact values of selected problems under the study. If a large number of variables are to be found, then it is hard to go past the classical methods. More usually, though, users will choose to use the proposed algorithm, to save their own time and to gain reliability. for example when we solved test problem number 6 by proposed algorithm it took time 7 seconds ,but when we solved it by branch and bound(exact method) it took time 396 seconds .

The reason for getting better results than the other algorithms considered is that the search power of bat algorithm. Adding to this, using chaos improves the performance of the algorithm.

• VI.    Conclusions

This paper has introduced an improved Bat Algorithm by blending with chaos for solving integer programming problems. Several examples have been used to prove the effectiveness of the proposed methods. The proposed algorithm managed to solve a large scale of problems that traditional method could not solve due to exponential growth in time and space complexities. The solution procedure will not face the same time waste in going through non-converging iterations as traditional methods do. IBACH algorithm is superior to both HS and IHS in terms of both efficiency and success rate. This implies that IBACH is potentially more powerful in solving NP-hard problems.