Using two-phase evolutionary computation approach for nonlinear constrained signal detectors allocation problems

Abstract

This study is to investigate the nonlinearly constrained various signal detector location allocation problems in which the types of detectors and the corresponding numbers and locations can be determined at the same time so as to minimize the maximum detecting failure rate in a specified area. In other words, the objective of the detector location allocation problem is to minimize the maximum failure rate by determining the best possible conjunction of three types of decision variables, i.e., the type of detector, the numbers of each detector type and where to build up each of them with a limited resources. So, the quality of reliability of event detecting can be assured and consistent. By the way, the signal intensity usually disintegrates proportionally to some power of the distance from the detector. That makes the longer distance far away the detector, the bigger failure rate in detection of the event. The signal detector allocation problem is described as a mixed-integer nonlinear programming model, usually using math programming or heuristic optimization methods for finding the optimal solution or near optimal solution. While using the both methods, the difficulties encountered are the amount of decision variables and the difficulty of not violating the constraints. In this study, a two-phase evolutionary computation approach based on the immune algorithm and particle swarm optimization has been developed for overcoming the difficulties and finding the optimal solutions for the detector allocation problems effectively. Finally, the performance of the proposed methodology has been evaluated with the commercial optimization software. Numerical results illustrate that our approach is with well performance for the constrained detector allocation problems considered in this paper. As reported, solutions acquired by using our approach are as well as or better than those found by using LINGO^®.

Keywords

Location allocation mixed-integer nonlinear programming evolutionary approach

1. Introduction

This research considers the nonlinearly constrained multiple category signal detector location allocation problems in which the types of signal detectors and the corresponding numbers and locations are to be be determined at the same time so as to minimize the maximum detection failure rate that may occurs in anywhere within a specified area. In other words, the objective in this study is to minimize the maximum failure rate by deciding the best possible conjunction of three types of decision variables, i.e., the types of signal detectors, the numbers of each type of detectors and where to build up each of them within a specified zone. Thus, the quality of signal detection can be assured more consistently. Moreover, the signal intensity usually disintegrates proportionally to some power of the distance from the detector. That makes the longer distance be farther from the detector, the bigger failure rate by the detectors is to be caused. The signal detector allocation problem is described as a mixed-integer nonlinear programming model. The difficulties encountered are the amount of decision variables and the difficulty of satisfying constraints.

The applications of this study are quite important and practical. With the development of communication technology and network development, the applications of these informaiotn technologies have boosted the convenience of human beeing’s life. If these information technologies can be used in a good way, and to the needs of users and the promotion of social benefits as the prerequisite, can improve the quality of human life and the immediate prevention of disasters. The realistic application for the proposed model includes the cellular phone transmitter location application. When one is placing a phone call, a transmitter in cell site must recognize the signal of phone call to facilitate the connection. So, the locations of all the transmitters become very significant to provide customers with high quality of phone call services. Other example is the detection of natural disasters: such as, the deployment of seismic detectors is more important for residents with fault zones adjacent to the city. With the deployment and early warning of detectors, people can take advantage of this limited time to reduce the greatest damage to life and property and loss. Similar applications include earth flow detection, forest fire detection and related applications. Such problems must take into account the signal strength will decline with the distance between detector and incident is increasing.

In the literature, very few researchers investigated the relative research. Drezner and Wesolowsky [4] were the pioneers to study the problems. However, in their model, only the locations are to be solved while the number and types of all detectors are given. While one detector location problem in their model, it can be seen as a 1-center or minimax single facility location problem [12]. Moreover, the multiple detector problems resemble the p-center problems [13, 18]. The problems belong to the non-convex problem with many possible local optima. But the detector location problem discussed in our study is more complicated than those studied in the literature. We considers the nonlinearly constrained multiple category signal detector allocation problems in which the types of signal detectors and the corresponding numbers and locations are to be determined a the same time so as to minimize the maximum detection failure rate that may occurs in a specified area. However, the detection signal strength of the detector will decline as the detection distance increases, that is, the failure rate of the event will be detected as the distance increases. So, the above problems are the major difficulties to be solved in this research.

In recent years, the immune algorithms (IAs) originally proposed by Jerne [6] have been widely applied and modified to solve a variety of applications in engineering combinatorial optimization problems. Owing to numerous literature reports of successful applications by using these innovative algorithms, IAs have attracted more recent attention than most other heuristic/metaheuristic methods in various field of optimization, including the reliability problems. For instance, Chen and You [1] used IAs to solve redundancy allocation problems (integer reliability problems) and reported effective solutions. Moreover, particle swarm optimization (PSO) was originally proposed by Kennedy & Eberhart [9] and modified by Shi & Eberhart [14] and was first intended for imitating social behavior [8], as a stylized depiction of the maneuver of organisms in a bird congregation or fish school. The advantage of the heuristic methods described above is that there is little or no assumption needed. By the way, they can search very large heterogeneous condidate solution spaces. However, these heuristic approaches are not able to guarantee that the optimal solution(s) can be acquired. In this study, the proposed approach includes two phases of problem solving processes. In the first phase, the IA has been applied for finding the solutions which includes the types of detectors and the corresponding numbers and locations. After those are provided by IA in the first phase, the problem solving process will then go to the second phase. In the second phase, the location of each detector is tried to be with better adjusted locations by PSO while the type and the number of the detector are fixed. Hsieh et al. [7] applied the similar idea to solve the multiple-type surveillance camera location problems. Moreover, Kuo et al. [19] developed a hybrid approach including PSO and immue genetic algorithm to solve the Bi-level linear programming problem.

This paper is arranged as follows. In Section 2, we illustrated the notations, assumptions and the mathematical model of this signal detector allocation problem. In Section 3, we presented the the process of the two-phase evolutionary computation approach for solving the signal detector allocation problem. In this section, the details of the procedure in both phases were described. Numerical results of the proposed approach are presented and discussed in Section 4 to illustrate the performance of our approach. The summary of this research are concluded in Section 5.

2. Model description and assumptions

Nomenclature

m the number of detector category

x_i the number of detector type i, 1 ≤ i ≤ m

k_i the signal decay exponent of detector type i

a_i the construction cost of detector type i

b the limitation of the total construction cost, i.e., budget

π (d) a monotonically signal decay function related to the distance

X_ij the location of the jth detector of type i i = 1, 2, …, m; j = 1, 2, …, x_i; for all i

d (X, X_ij) the distance between the jth detector of type i and a detection point j = 1, 2, …, x_i; for all i

For mixed integer multiple category detector allocation problems, three types of variables including the types of signal detectors and the corresponding numbers and locations are to be determined at the same time so as to minimize the maximum detection failure rate that may occurs in a specified area. The model of the multiple category detector allocation problems with a linear budget constraint is considered and formulated as a mixed integer nonlinear programming problem. Again, the problem investigated in this paper is much more complicated than the problem discussed by Drezener and Wesolowsky [4].

The signal decay function can be represented by a probability function related to a distance. For most realistic applications, the function can be considered as a monotonically decreasing function to the distance. Given the distance d and signal decay exponent k of detector type i, the signal decay function is then described as: $π (d) = e^{- k_{i} d}$ (1)

Consider that: the probability that an even occurring at location X is not able to be discovered by all the detectors is described as: $\prod_{i = 1}^{m} \prod_{j = 1}^{x_{i}} (1 - π (d (X, X_{ij})))$ (2)

The probability can be looked as the detection failure rate at a location point within a detection zone. While the above failure rate of a location point is defined, the problem therefore can be formulated as: $\min_{X_{ij}} \max_{X} {\prod_{i = 1}^{m} \prod_{j = 1}^{x_{i}} (1 - π (d (X, X_{ij})))}, for all i & j$ (3)

Then, the overall detectors are allocated in the specified area with limited resource constraint(s) to minimize the maximum failure rate. The constraint can be illustrated as: $\sum_{i = 1}^{m} x_{i} a_{i} \leq b, for all i .$ (4)

Where there are m resource-limitations.

3. Two-phase evolutionary computation approach

In this research, our approach adopting the immune algorithm and particle swarm optimization to solve the nonlinearly constrained multiple category signal detector allocation problems in which the types of signal detectors and the corresponding numbers and locations are to be determed at the same time so as to minimize the maximum detection failure rate that may occurs in a specified area. In the proposed approach, the number of detectors with the corresponding categories and the approximated location can be obtained by using immune algorithm in the first stage. In the next stage, the approximated location of each detector is then adjusted by using particle swarm optimization. It is to improve the solutions founded in the first stage, i.e., the approximated locations of all the detectors are fine tuned to minimize the maximum failure rate based on the deployment of the various detectors.

3.1. Concise introduction to immune algorithms

The nature immune system is a very entangled system for protection against the disease causing organisms. There is a double layer of defense in the system, including the innate and the adaptive immune systems. The essential constituents are lymphocytes and antibodies [10]. The cells of the innate immune system are immediately available to counter a wide range of antigenic differences without prior contact with them. The antibody fabrication in answer to a defined infectious agent (antigen) is the adaptive immune response interceded by lymphocytes responsible for the identification and elimination of the disease causing agents [2, 3]. The cells in the adaptive system are all with the immune memory that enable them to recognize the alike antigenic stimulus while given to the organism again. Also, each antibody is produced only for a specific infection. The lymphocytes carry surface receptor molecules that are able to recognize the antigens. The antigen only bind to those receptors that are compatible with it.

The distinction and exclusion of the organism’s intruders are the primary responsibility of the immune system, so the immune system must have the ability of self/non-self identification. Epitopes are part of an antigen recognized by an antibody and play the role of an antigenic determinant. Each antibody is with its own specific antigen determinant, called idiotope. In order to generate sufficient specific effector cells to repel an infection, the activated lymphocytes must propagate for discriminating these effector cells. The above process is called clonal selection. Based on this clonal selection process, a huge clone of plasma cells is then proliferated. Thus, the antibodies are able to be discharged and ready to retain antigens. According to the above actuality, an idiotype network hypothesis based on the clonal selection theory was proposed by Jerne [5]. Based on his assumption, some antigens activate some classes of recognizing groups, which are then producing an antibody. The antibody is then activating other classes of recognizing groups. Eventually, the activation is breeded through whole network of recognizing gruops by antigen-antibody responses. It should be mentioned that the antigen is recognized not by one or more recognizing groups but by the antigen-antibody reciprocal effects [11]. Based on above obersation, we can look the antibody and antigen as the solution and objective function in a mathematical problem. So, it can be developed as a problem solving approach.

3.2. Concise introduction to particle swarm optimization

In Particle Swarm Optimization (PSO), particles (or called individuals) travel through cooperation and competition among themselves. The moving of each particle is regulated by its own experience with other moving information from other accompanists. Each partical portrays a possible solution to a problem.

Each individual represents a potential answer to the problem. The particles move through the solution space by modifying the position of the ith particle at time t as description of the following Equation [9]: $x_{i} (k + 1) = x_{i} (k) + v_{i} (k) \cdot Δ t$ (5)where k is the number of iteration; the current position and velocity are represented by the vector x_i (t) and vector v_i (t) respectively; x_i = (x_i1, x_i2, …, x_iN) and v_i = (v_i1, v_i2, …, v_iN) in which N represents the quantity of independent variables to be solved in a specific problem; Δt is the step value of timing. The best site this particle has occurrenced can be described as p_i = (p_i1, p_i2, …, p_iN), and the best site of the flock as p_g = (p_g1, p_g2, …, p_gN) respectively. The modification of the velocity for each particle is controled by the following Equations [14]:

$\begin{matrix} v_{in} (k + 1) & = & w \cdot v_{in} (k) \cdot Δ t \\ + c_{1} \cdot {rand}_{1 n} () \cdot (p_{in} - x_{in} (k)) / Δ t \\ + c_{2} \cdot {rand}_{2 n} () \cdot (p_{gn} - x_{in} (k)) / Δ t \end{matrix}$ (6)where w represents an inertial weight (0 ≤ w ≤ 1) that decides how much of the particle’s previous velocity has been retained; c₁ & c₂ represent the constants of the positive acceleration; rand_1n () & rand_2n () denote samplings of the uniform random sequences obtained from U(0, 1). In this study, the unit inertia weight (w = 1) and the unit time step (Δt = 1) are adopted. The stop criterion for the computational iterations is set as the number of maximum generations. In this study, the solution representation of the detector’s location is designed as a binary string, which can be decoded into a real number. Moreover, every string consisting of substrings includes the x & y coordinates for all the detectors.

3.3. Computation procedures

The computational processes of the proposed two-phase evolutionary computation approach illustrated in Fig. 1 are described as follows and the discussion comes in sequence:

Fig. 1.

The architecture of two-phase evolutionary computation approach.

Phase I –Approximated solutions searching process

In Phase I, the signal detectors’ categories and the corresponding number and approximate locations are determined.

Step 1.1. Create an initial population of antibodies randomly. The detail of the solution representation is descripted in next section and shown as the Fig. 2.

Fig. 2.

Solution representation of IA in Phase I.

Step 1.2. Evaluate each antibody based on the corresponding value of its affinity by using Equation (8).

Step 1.3. Select the best k antibody with the greatest affinity values and then clone these k antibodies. Thus, temporary population of antibodies is then created.

Step 1.4. Excute the genetic operations (crossover and mutation) [17] in the set of the clones in previous step. So, the new population of the adapted antibodies is created and improved.

Step 1.5. Update the antibodies in the memory set. The process includes suppression and replacement, which are as follows: •

Suppression: in oreder to maintain the diversity of antibodies in the memory set, the antibodies with no significant difference are to be removed.

Replacement: compute the new affinity values of these new antibodies generated in previous step. Choose these new antibodies which are superior to those in the memory set, and the inferior individuals are then switched by the superior ones in the memory set.

Step 1.6. Check the stopping criterion. While the stop criterion is not met then goes to Step 1.3., otherwise goes to the next step. The stopping criterion is the number of the maximum iterations in this study.

Step 1.7. Stop. The best n solutions obtained in memory are then sent to Phase II. The process of the Phase I is then terminated and the computational prcocess of Phase II is then activated.

Phase II –Solutions adjustment process

In this phase, the best n solutions obtained from previous phase are to be adjusted by PSO for improving the solutions individually. It is noted that only the positions of the detectors are adjusted but the categories and the number of detectors are fixed.

Step 2.1. Create an initial population of particles by varying the positions of a antibody randomly. The solution representation is illstrated in next section and shown in Fig. 3.

Step 2.2. Evaluate every particles (coordinations of detector) based on the Equation (3). It is noted that only the location of each dector has been adjusted by using PSO in Phase II. The types and number of all dectors are not changed in this phase so that there is no constraint violation problem in Phase II. For this reason the evaluation of each particle is measured by using Equation (3) instead of using Equation (8).

Fig. 3.

Solution representation of PSO in Phase II.

Step 2.3. Renew the values of p_i (best location the particle i has been through) and p_g (the best position of the colony) respectively.

Step 2.4. Using Equation (6) to adjust the velocity of each particle based on the values of p_i and p_g acquired in previous step.

Step 2.5. Update every particle’s position based on its renewed velocity by using Equation (5) so that the coordinates of each particle is then renewed.

Step 2.6. Check the stopping criterion, if not stop then go to Step 2.2. Otherwise go to next step. The stopping criterion is the number of maximun iterations in this study. While the iteration reach the maximum numbers, the computational procedure is stopped.

Step 2.7. End the coordinates adjustment process. The best-adjusted coordinates are then acquired.

3.4. Mechanism of the solution representation

The solution representations for both of the immune algorithm and particle swarm optimization are designed in the similar manner to that of genetic algorithms and they are to be illustrated separately as follows. In this sutdy, the IA’s solution representation is encoded by strings of binary digits as shown in Fig. 2. Each string is divided into two main substrings and then decoded into several values sequentially. The first binary substring representing the number of signal detectors will be decoded into an integer(g). Any of binary string can be decoded into real numbers [15] and then rounded up to be integers. While the number of signal detectors is decided, the second binary substring is then divided into g substrings in decoding stage 2. For each of g substrings, it contains two sections including the detector category and the approximated location respectively. Thus, the proposed binary string can represent the general form of the solutions.

While the best n solutions including the types of signal detectors and the corresponding numbers and locations found by IAs in the Phase I, these n solutions are then send to PSO in Phase II for adjusting the positions of all detectors in terms of improving the approximated solutions obtained from Phase I. So, the solution representation of PSO is focus on the adjustment of the detector locations without changing the number and categories of signal detectors. The solution representation of PSO is represented by strings of real numbers as shown in Fig. 3. Each string contains g substrings (locations) and each substring represents the coordinate (x, y) of the corresponding signal detector. The value of g depends on the solution given from IAs in Phase I.

3.5. Constrained optimization

For propagating a better new particle for next generations (iterations), the evaluation of each particle is a necessary process for PSO. The aim of particle swarm optimization is to modify the unfeasible solutions (particles) to the feasible solutions (particles), so as to diminish any possible constraint violations of the solution searching to find the optimal or near optimal solutions. For overcoming the difficulty of these constraint violations, a penalty function has to be defined. A penalty will be incurred and generated by a penalty function, when a solution violates any of the constraints. The amount of penalty for an infeasible solution is decided by the distance away from the feasible region. Based on the Equation (2) in the Section 2, for individual k, the penalty of the constraint violation for the kth individual is defined as, ${penalty}_{k} = {\begin{matrix} \frac{\sum_{i = 1}^{m} a_{i} x_{i} - b}{b}, & if \sum x_{i} a_{i} > b \\ 0, & otherwise \end{matrix}$ (7)

When the penalty function has been defined as above, the original fitness function to any individual (Equation 3) of the IAs is then penalized by containing the penalty function (Equation 7). The modified affinity funciton of individual k is as the following:

$\begin{matrix} {Affinity}_{k} & = & \max_{X} {\prod_{i = 1}^{m} \prod_{j = 1}^{x_{i}} (1 - π (d (X, X_{ij})))} + \\ {penalty}_{k}, for all i & j \end{matrix}$ (8)

4. Numerical results and discussion

To evaluate the performance of the proposed two-phase evolutionary computation approach for the multiple category signal detector allocation problems, seventeen testing problems are solved.

The testing problems are in a square area (1 unit length by 1 unit length). A grid of n + 1 by n + 1 signal source points shielding the square is assumed as the set of signal source points. The source point is located at ((i - 1)/n, (j - 1)/n) for i, j = 1, 2, …, n + 1. While the value of n is 10 that 121 signal source points are to be detected in the square area [4]. In these test problems, it is assumed three types of detectors are to be selected and then allocated. The three types of detectors are with various building cost (50, 30, and 20 respectively) and signal decay exponents (1, 3, and 5 respectively). These test problems are solved with changing the limited budget varied increasingly from 120 to 600.

These input data of all the test problems and those of numerical results obtained by using the proposed hybrid meta-evolutionary approach are all shown in Table 1, and then compared with those solved by using LINGO^® in Table 2.

Table 1
Numerical results by the proposed two-phase evolutionary computation approach

Budget Total Cost Detectors Coordination Max. failure rate

Type no.

120 120 A 2 (0.6123, 0.1057) (0.1177, 0.6179) 0.21561

C 1 (0.8887, 0.8790)

150 150 A 3 (0.8985, 0.4793) (0.3411, 0.1881) (0.3791, 0.8609) 0.12566

180 180 A 3 (0.8448, 0.1545) (0.7991, 0.9326) (0.0667, 0.2012) 0.07273

B 1 (0.0992, 0.9011)

210 200 A 4 (0.1286, 0.1243) (0.8756, 0.1286) (0.1243, 0.8713) (0.8713, 0.8756) 0.03993

240 240 A 4 (0.3079, 0.6696) (0.9034, 0.1264) (0.1234, 0.1018) (0.6720, 0.7002) 0.02838

C 2 (0.0728, 0.9514) (0.9523, 0.9256)

270 270 A 5 (0.9173, 0.1150) (0.0606, 0.1224) (0.2985, 0.7466) (0.5115, 0.4093) (0.9022, 0.9121) 0.01464

C 1 (0.0412, 0.9306)

300 300 A 6 (0.0866, 0.0769) (0.9181, 0.9193) (0.0888, 0.9201) (0.9261, 0.0934) (0.4217, 0.5667) (0.5643, 0.4258) 0.00746

330 330 A 6 (0.9211, 0.9211) (0.0553, 0.9133) (0.6175, 0.5046) (0.2945, 0.2904) (0.9117, 0.0519) (0.4788, 0.5971) 0.00550

B 1 (0.0580, 0.0547)

360 350 A 7 (0.3186, 0.3616) (0.6955, 0.4407) (0.4759, 0.6971) (0.0802, 0.0619) (0.9389, 0.9316) (0.0533, 0.9241) (0.9178, 0.0468) 0.00313

390 390 A 7 (0.9490, 0.9367) (0.1727, 0.2305) (0.4855, 0.8487) (0.8208, 0.4533) (0.9272, 0.0413) (0.0521, 0.9503) (0.4603, 0.2215) 0.00221

C 2 (0.0599, 0.5897) (0.0433, 0.0223)

420 420 A 8 (0.2072, 0.7589) (0.9445, 0.9522) (0.6950, 0.6752) (0.3075, 0.3019) (0.9479, 0.0548) (0.6872, 0.3071) (0.0524, 0.0525) (0.3741, 0.6729) 0.00108

C 1 (0.0399, 0.9770)

450 450 A 9 (0.2611, 0.3040) (0.2654, 0.6824) (0.7135, 0.5739) (0.5934, 0.6964) (0.0540, 0.0373) (0.0535, 0.9624) (0.9758, 0.0619) (0.9513, 0.9578) (0.6489, 0.2179) 0.00055

480 480 A 8 (0.6326, 0.7468) (0.1949, 0.8670) (0.1530, 0.1637) (0.6623, 0.5235) (0.6479, 0.4227) (0.8154, 0.1531) (0.9632, 0.9478) (0.1658, 0.5203) 0.00065

C 4 (0.9751, 0.0350) (0.0315, 0.0253) (0.0098, 0.9553) (0.4291, 0.1198)

510 500 A 10 (0.6515, 0.8212) (0.4986, 0.2241) (0.8634, 0.4261) (0.0240, 0.0520) (0.9747, 0.9500) (0.0465, 0.9670) (0.3011, 0.3062) (0.2383, 0.7296) (0.4765, 0.4767) (0.9516, 0.0278) 0.00024

540 530 A 10 (0.4612, 0.2099) (0.9763, 0.9521) (0.1572, 0.1779) (0.0497, 0.9838) (0.9561, 0.0322) (0.7308, 0.6549) (0.5725, 0.7793) (0.1204, 0.6486) (0.4660, 0.6513) (0.7981, 0.2385) 0.00017

B 1 (0.0260, 0.0362)

570 570 A 10 (0.2940, 0.1453) (0.8175, 0.8019) (0.2589, 0.8379) (0.2823, 0.4987) (0.0122, 0.9501) (0.7200, 0.1607) (0.4737, 0.6146) (0.7785, 0.7857) (0.9717, 0.0342) (0.1334, 0.2518) 0.00012

B 1 (0.8854, 0.3616)

C 2 (0.0259, 0.0203) (0.9767, 0.9774)

600 600 A 12 (0.3050, 0.2526) (0.9718, 0.0333) (0.0303, 0.0310) (0.7660, 0.7488) (0.5160, 0.5892) (0.9814, 0.9602) (0.3630, 0.4253) (0.7822, 0.2364) (0.1865, 0.6151) (0.0371, 0.9778) (0.5436, 0.3472) (0.4729, 0.8124) 0.00004

Budget	Total Cost	Detectors	Coordination	Max. failure rate
120	120	A	2	(0.6123, 0.1057) (0.1177, 0.6179)	0.21561
		C	1	(0.8887, 0.8790)
150	150	A	3	(0.8985, 0.4793) (0.3411, 0.1881) (0.3791, 0.8609)	0.12566
180	180	A	3	(0.8448, 0.1545) (0.7991, 0.9326) (0.0667, 0.2012)	0.07273
		B	1	(0.0992, 0.9011)
210	200	A	4	(0.1286, 0.1243) (0.8756, 0.1286) (0.1243, 0.8713) (0.8713, 0.8756)	0.03993
240	240	A	4	(0.3079, 0.6696) (0.9034, 0.1264) (0.1234, 0.1018) (0.6720, 0.7002)	0.02838
		C	2	(0.0728, 0.9514) (0.9523, 0.9256)
270	270	A	5	(0.9173, 0.1150) (0.0606, 0.1224) (0.2985, 0.7466) (0.5115, 0.4093) (0.9022, 0.9121)	0.01464
		C	1	(0.0412, 0.9306)
300	300	A	6	(0.0866, 0.0769) (0.9181, 0.9193) (0.0888, 0.9201) (0.9261, 0.0934) (0.4217, 0.5667) (0.5643, 0.4258)	0.00746
330	330	A	6	(0.9211, 0.9211) (0.0553, 0.9133) (0.6175, 0.5046) (0.2945, 0.2904) (0.9117, 0.0519) (0.4788, 0.5971)	0.00550
		B	1	(0.0580, 0.0547)
360	350	A	7	(0.3186, 0.3616) (0.6955, 0.4407) (0.4759, 0.6971) (0.0802, 0.0619) (0.9389, 0.9316) (0.0533, 0.9241) (0.9178, 0.0468)	0.00313
390	390	A	7	(0.9490, 0.9367) (0.1727, 0.2305) (0.4855, 0.8487) (0.8208, 0.4533) (0.9272, 0.0413) (0.0521, 0.9503) (0.4603, 0.2215)	0.00221
		C	2	(0.0599, 0.5897) (0.0433, 0.0223)
420	420	A	8	(0.2072, 0.7589) (0.9445, 0.9522) (0.6950, 0.6752) (0.3075, 0.3019) (0.9479, 0.0548) (0.6872, 0.3071) (0.0524, 0.0525) (0.3741, 0.6729)	0.00108
		C	1	(0.0399, 0.9770)
450	450	A	9	(0.2611, 0.3040) (0.2654, 0.6824) (0.7135, 0.5739) (0.5934, 0.6964) (0.0540, 0.0373) (0.0535, 0.9624) (0.9758, 0.0619) (0.9513, 0.9578) (0.6489, 0.2179)	0.00055
480	480	A	8	(0.6326, 0.7468) (0.1949, 0.8670) (0.1530, 0.1637) (0.6623, 0.5235) (0.6479, 0.4227) (0.8154, 0.1531) (0.9632, 0.9478) (0.1658, 0.5203)	0.00065
		C	4	(0.9751, 0.0350) (0.0315, 0.0253) (0.0098, 0.9553) (0.4291, 0.1198)
510	500	A	10	(0.6515, 0.8212) (0.4986, 0.2241) (0.8634, 0.4261) (0.0240, 0.0520) (0.9747, 0.9500) (0.0465, 0.9670) (0.3011, 0.3062) (0.2383, 0.7296) (0.4765, 0.4767) (0.9516, 0.0278)	0.00024
540	530	A	10	(0.4612, 0.2099) (0.9763, 0.9521) (0.1572, 0.1779) (0.0497, 0.9838) (0.9561, 0.0322) (0.7308, 0.6549) (0.5725, 0.7793) (0.1204, 0.6486) (0.4660, 0.6513) (0.7981, 0.2385)	0.00017
		B	1	(0.0260, 0.0362)
570	570	A	10	(0.2940, 0.1453) (0.8175, 0.8019) (0.2589, 0.8379) (0.2823, 0.4987) (0.0122, 0.9501) (0.7200, 0.1607) (0.4737, 0.6146) (0.7785, 0.7857) (0.9717, 0.0342) (0.1334, 0.2518)	0.00012
		B	1	(0.8854, 0.3616)
		C	2	(0.0259, 0.0203) (0.9767, 0.9774)
600	600	A	12	(0.3050, 0.2526) (0.9718, 0.0333) (0.0303, 0.0310) (0.7660, 0.7488) (0.5160, 0.5892) (0.9814, 0.9602) (0.3630, 0.4253) (0.7822, 0.2364) (0.1865, 0.6151) (0.0371, 0.9778) (0.5436, 0.3472) (0.4729, 0.8124)	0.00004

Table 2

Comparison of the best solution found by proposed approach with those of LINGO^®

Budget	LINGO (Global solver)						Proposed approach					MPI (%)	Note
	Type			Cost	Slack	Max. failure rate	Type			Cost	Slack	Max. failure rate
	A	B	C				A	B	C
120	2	0	0	100	20	0.25424	2	0	1	120	0	0.21561	15.2%	circledcirc
150	3	0	0	150	0	0.12564	3	0	0	150	0	0.12566	0.0%	vartriangle
180	3	1	0	180	0	0.07273	3	1	0	180	0	0.07273	0.0%	○
210	4	0	0	200	10	0.03993	4	0	0	200	10	0.03993	0.0%	○
240	4	1	0	230	10	0.03756	4	0	2	240	0	0.02838	24.4%	circledcirc
270	5	0	0	250	20	0.01742	5	0	1	270	0	0.01464	16.0%	circledcirc
300	6	0	0	300	0	0.00745	6	0	0	300	0	0.00746	–0.1%	vartriangle
330	6	1	0	330	0	0.00542	6	1	0	330	0	0.00550	–1.5%	vartriangle
360	7	0	0	350	20	0.00312	7	0	0	350	10	0.00313	–0.3%	vartriangle
390	7	1	0	380	10	0.00222	7	0	2	390	0	0.00221	0.5%	circledcirc
420	8	0	1	420	0	0.00137	8	0	1	420	0	0.00108	21.2%	circledcirc
450	9	0	0	450	0	0.00054	9	0	0	450	0	0.00055	–1.9%	vartriangle
480	9	1	0	480	0	0.00105	8	0	4	480	0	0.00065	64.1%	circledcirc
510	10	0	0	500	10	0.00063	10	0	0	500	10	0.00024	61.9%	circledcirc
540	10	1	0	530	10	0.00038	10	1	0	530	10	0.00017	55.3%	circledcirc
570	10	2	0	560	10	0.00012	10	1	2	570	0	0.00012	0.0%	○
600	12	0	0	600	0	0.00004	12	0	0	600	0	0.00004	0.0%	○

Note: circledcirc represents the best solution found is superior to the solution found by LINGO^®. ○ represents the best solution found is as well as the solution found by LINGO^®. vartriangle represents the best solution found is inferior to the solution found by LINGO^®.

Recall that, for each problem, the types of the signal detectors and the corresponding number of detectors and the coordinates are to be determined at the same time. Our proposed approach is coded in MATLAB^® on the Pentium-4 2.0 GHz PC with the following parameters: (1) in IAs: memory size = 80, mutation rate = 0.02, crossover rate = 0.89 and the maximum clone number = 10, (2) in PSO: C₁ = C₂ = 2, V_max = 0.025 and ω = 0.95. Then number of generations for both IAs and PSO are set to be 80. The adjudgement of the above parameters is an important problem for the implementation of the proposed approach. However, there is no any systematic way to solve the problem ideally because various value-combinations of the parameters result in different characteristics as well as different performance of the hybrid evolutionary approach. Therefore, we denote that the most appropriate parameters are very case-dependent and based upon the experience from preliminary runs.

There are seventeen test problems in Table 1. Each of the problems is with different budgets. More budget means the scale of the problem will be larger. While the budget is given for each problem, the types of detectors and the corresponding numbers and locations are to be decided by using the proposed approach simultaneously to minimize the maximum detecting failure rate in a specified area. While the types of detectors and the corresponding numbers in any test problem, the total cost should not be more than the budget. The budgets in the Table 1 is ranged from 120 to 600 and the corresponding number for each type of dectors and their locations are illustrated.

For measuring the performance of the proposed approach, the maximum possible improvement (MPI) approach has been modified and applied to evaluate the amount improvement of the solutions found by the the proposed approach to the former best know solutions [16]. MPI is the fraction that the best feasible solution obtained of the maximum possible improvement in the system reliability failure rates, it is described as: $MPI (%) = (F_{s_LINGO} - F_{s_IAPSO}) / (F_{s_LINGO})$ (9) where F_{s_IAPSO} represents the maximum failure rate obtained by the proposed hybrid meta-evolutionary computation approach and F_{s_LINGO} represents the maximum failure rate obtained by LINGO^®.

The numerical results in Tables 2 illustrate the detailed solutions obtained by the proposed approach for seventeen test problems and they are compared with those obtained by using LINGO^®.

The results in Table 2 indicate that:

compared with the solutions of all test problems obtained by LINGO^®, twelve out of seventeen test problems obtained by the proposed approach are much superior to or as well as those found by using LINGO^®. Solutions of four test problems found by both approaches are the same by using both of the approaches.

the solutions of eight test problems obtained by the proposed approach are superior to those obtained by LINGO^®. The greatest imrpovement of the first three problems are 64.1%, 61.9%, and 55.3% of MPI respectively.

five solutions obtained by using the proposed approach are slightly inferior to the solutions found by LINGO^®. The but those are just worse no more than 2% of MPI. The difference of the largest three inferior solutions are – 1.9%, – 1.5% and –0.3% of MPI respectively.

According to the above observations, we learned that while those solutions found by the proposed approach are superior to those found by LINGO^®, the maximun improvement can be up to 64% of MPI. While the solutions found by our approach are inferior to those found by LINGO^® in the opposite case, the greatest inferior solutons is no more than – 1.9% of MPI. It can be concluded that the proposed approach is an effective approach for solving the signal detector deployment problems investigated in this study.

5. Conclusions

This paper presents a two-phase evolutionary computation approach for solving nonlinearly constrained multiple category signal detector allocation problems in which the types of signal detectors and the corresponding numbers and locations are to be decided simultaneously so as to minimize the maximum detection failure rate that may occurs in a specified area. In this optimization problems, it is to minimize the maximum failure rate by deciding the best possible combination of three types of decision variables, i.e., the number and category of the signal detectors to be located, and where to build up each of them within a specified zone. So, the quality of detection can be assured more consistently. As demonstrated in the previous section, the best solutions of twelve problems found by the proposed hybrid meta-evolutionary approach are better than or tie the best solutions by LINGO^® for the multiple category signal detector allocation problems. Only five solutions found by the proposed is slightly worse than those by LINGO^®. According to the experimental results, it indicates that the proposed two-phase evolutionary computation approach finds solutions, which are of a quality and are comparable to that of LINGO^®. The proposed method achieves the optimal solution or finds a near-optimal solution for each problem tested. In general, the numerical results show that our approach is effective for the multiple category signal detector allocation problems.

Footnotes

Acknowledgments

The research is supported by National Science Council, Taiwan, under contract NSC 94-2213-E-150-015.

References

T.-C.

Chen and

P.-S.

You , Immune algorithm based approach for redundant reliability problems, Computers in Industry 56 (2005), 195–205.

L.N.

de Castro and

Timmis , Artificial Immune Systems: A new Computational Intelligence Approach, Springer, New York, 2000.

L.N.

de Castro and

F.J.

Von Zuben , The clonal selection algorithm with engineering applications, In Workshop Proceedings of the GECCO 2000 (2000), 36–37.

Drezner and

G.O.

Wesolowsky , On the best location of signal detectors, IIE Transactions 29 (1997), 1007–1015.

N.K.

Jerne , The immune system, Scientific America 229(1) (1973), 52–60.

N.K.

Jerne , Clonal selection in lymphocyte network, in: G.M.

Edelman

, ed., Cellular Selection and Regulation in the Immune Response, Raven Press, New York, 1974.

Y.C.

Hsieh ,

Y.C.

Lee ,

P.S.

You and

T.C.

Chen , An immune based two-phase approach for the multiple-type surveillance camera location problem, Expert Systems with Applications 36(7) (2009), 10634–10639.

Kennedy , The particle swarm: Social adaptation of knowledge, Proceedings of IEEE International Conference on Evolutionary Computation, 1997, pp. 303–308.

Kennedy and

R.C.

Eberhart , Particle swarm optimization, in Proceedings of IEEE International Conference on Neural Networks, Perth, Australia, IV, 1995, pp. 1942–1948.

10.

J.D.

Farmer ,

N.H.

Packard and

A.S.

Perelson , The immune system, adaptation, and machine learning, Physica 22 (1986), 187–204.

11.

S.J.

Huang , An immune-based optimization method to capacitor placement in a radial distribution system, IEEE Transaction on Power Delivery 15(2) (2000), 744–749.

12.

R.F.

Love ,

J.G.

Morris and

G.O.

Wesolowsky , Facilities Locaton: Models and Methods, North-Holland, New York, 1988.

13.

Plastria , Continuous location problems, in Facility Location: A Survey of Applications and Methods, Z.

Drezner

, ed., Springer-Verlag, New York, 1995, pp. 225–262.

14.

Shi and

R.C.

Eberhart , A modified particle swarm optimizer, in Proceeding of IEEE Congress on Evolutionary Computation Anchorage, Alaska, 1998, pp. 69–73.

15.

Michalewicz , Genetic Algorithms + Data Structures = Evolution Programs, 3rd Edition, Springer-Verlag Berlin Heidelberg, NY, 1996.

16.

D.W.

Coit and

A.E.

Smith , Reliability optimization of series-parallel systems using a genetic algorithm, IEEE Transaction on Reliability 45 (1996), 254–260.

17.

Michalewicz , Genetic Algorithms + Data Structures = Evolution Programs, 3rd edition, Springer-Verlag, Berlin Heidelberg, New York, 1996.

18.

Drezner ,

Brimberg ,

Mladenovic and

Salhi , New heuristic algorithms for solving the planar p-median problem, Computers & Operations Research 62 (2015), 296–304.

19.

R.J.

Kuo ,

Y.H.

Lee ,

F.E.

Zulvia and

F.C.

Tien , Solving bi-level linear programming problem through hybrid of immune genetic algorithm and particle swarm optimization algorithm, Applied Mathematics and Computation 266 (2015), 1013–1026.