A bi-population QUasi-Affine TRansformation Evolution algorithm for global optimization and its application to dynamic deployment in wireless sensor networks

In the last few decades, there have been many optimization demands arising not only from the scientific community but also from various real-world applications. Generally, the approach to solving these optimization problems often begins with designing the objective function which can model the objectives of optimization problems [1]. Many optimization approaches have been proposed to meet these demands aiming at finding optimal solutions. Some Swarm-based intelligence optimization algorithms, such as particle swarm optimization (PSO) [2], ant colony optimization (ACO) [3], differential evolution (DE) [1], artificial bee colony (ABC) optimization [4], and QUasi-Affine TRansformation Evolution (QUATRE) algorithm [5], and so on, have been developed to tackle these complex optimization problems.

QUATRE algorithm was first presented by Meng et al. in [5] that discussed the relationship between QUATRE algorithm and the other two swarm-based intelligence algorithms PSO and DE. In 1995, Kennedy and Eberhart firstly introduced the PSO algorithm [2]. As PSO is simple, powerful, and straightforward to implement, many researchers have studied this technique and developed various improved variants [6‐8]. DE was introduced by Storn and Price [1] in 1995, which was arguably one of the most powerful optimization algorithms. As well, many DE variants have been proposed to enhance the performance of DE algorithm [9‐11], and QUATRE algorithm is one of them proposed to conquer representational or positional bias of DE algorithm [12]. QUATRE’s conventional notation is “QUATRE/x/y” which denotes types of QUATRE variants. It is worth noting that the notation of QUATRE is more general than the DE’s notation “DE/x/y/z” [13].

The canonical QUATRE algorithm and its variants can be found in literatures [12‐17]. The QUATRE has the advantages of simplicity, few control parameters to set, and convenient to be used, but it has some weaknesses as the DE algorithm such as it will be premature convergence, and will search stagnation and may be easily trapped into local optima. Population diversity plays important role in alleviating these weaknesses. Therefore, it is important to keep the balance between diversity and convergence. In [16], S-QUATRE has been proposed which uses sort strategy to improve the performance of QUATRE algorithm. And S-QUATRE divides the population into the better and the worse groups and evolves the individuals in the worse group. The other algorithms which partition population into two groups or several subpopulations to maintain population diversity and to enhance the performance of algorithms, such as CMA-ES, PSO, DE and CSO, can be found in previous literature [18‐22]. On the other hand, both mutation strategies and control parameter scale factor F have significant effects on the performance of QUATRE variants. Different mutation strategies in QUATRE algorithm have different performance over various optimization problems [13] because different mutation strategy has different search ability and convergence rate. Usually, similar to the DE algorithm, adopting larger F value in QUATRE algorithm means the algorithm is more focused on exploration, while a smaller F value means more exploitation [23]. Therefore, in this paper, in order to improve the performance of QUATRE algorithm, we propose a novel Bi-Population QUATRE algorithm with a sort strategy and a linear decrease scale factor F (BP-QUATRE), and each subpopulation has a different mutation strategy.

The remainder of the paper is arranged as follows. In Section 2, we briefly review the QUATRE algorithm. Our proposed Bi-Population QUasi-Affine TRansformation Evolution (BP-QUATRE) algorithm is given in Section 3. In Section 4, we apply the proposed algorithm to dynamic deployment in wireless sensor networks. What is more, the experimental analysis of our proposed algorithm under CEC2013 test suite and simulation results in wireless sensor networks are presented in Section 4. Finally, Section 6 gives the conclusion.

Meng et al. have proposed the QUATRE algorithm for solving optimization problems [5]. QUATRE is an abbreviation of QUasi-Affine TRansformation Evolution, and the reason the authors naming the algorithm QUATRE is that individuals in QUATRE algorithm evolve by using an affine transformation-like equation. The detailed evolution equation of QUATRE is as follows.where M is an evolution matrix and \( \overline{\mathbf{M}} \) is a binary inverted matrix of M. The elements of them are either 0 or 1. The binary invert operation means to invert the values of the matrix. The reverse values of zero elements are ones, while the reverse values of one elements are zeros. Equation 2 shows an example of binary inverse operation.

M is transformed from an initial matrix M_ini which is initialized by a lower triangular matrix with the elements equaling to ones. Transforming from M_ini to M contains two consecutive steps. In the first step, every element in each row vector of M_ini is randomly permuted. In the second step, the sequence of the row vectors is randomly permuted with all elements of each row vector unchanged. An example of the transformation with ps = D is given in Eq. 3. Usually, the population size ps is larger than the dimension, while the matrix M_ini needs to be extended according to population size ps. Equation 4 shows an example of ps = 2D + 2. Generally, when ps % D = k, the first k rows of the D × D lower triangular matrix are included in M_ini and adaptively change M according to M_ini [12].

X = [X_{1, G}, X_{2, G},  … , X_{i, G},  … , X_{ps, G}]^Tis the population matrix with ps individuals. X_{i, G} = [x_i1, x_i2,  … , x_iD] is the ith row vector of the matrix X, which denotes the location of ith individual of the Gth generation, and each individual X_{i, G} is a candidate solution for an optimization problem, and D denotes the dimension number of objective function, where i ∈ {1, 2,  … , ps}. The operation “⊗” stands for component-wise multiplication of the elements in each matrix, which is the same as “.*” operation in Matlab software. B = [B_{1, G}, B_{2, G}, … , B_{i, G}, …, B_{ps, G}]^T is the donor matrix, and it has several different calculation schemes (mutation strategies) which are listed in Eqs. (5)–(8) [7].

X_{gbest, G} = [X_{gbest, G}, X_{gbest, G},  … , X_{gbest, G}]^TX_{gbest, G} = [X_{gbest, G}, X_{gbest, G},  … , X_{gbest, G}]^T denotes a row vector-duplicated matrix with each row vector equaling to the global best individual X_{gbest, G} of the Gth generation. F can be considered as amplification factor, whose value region is (0, 1] for most optimization problems. X_{r1, G}, X_{r2, G} and X_{r3, G} are a set of random matrices which are generated by randomly permutating the sequence of row vectors in the matrix X of the Gth generation.

In this section, we describe the main idea of our proposed algorithm BP-QUATRE. As mentioned above, because easily trapping into local optima and premature convergence is the weakness of QUATRE algorithm. In order to alleviate the above weaknesses, BP-QUATRE consisting of population initialization, population division, subpopulation evolution, subpopulation merging, and an approach to update the parameter scale factor F, is proposed in this paper. The main framework of BP-QUATRE is shown in Fig. 1.

In this section, we apply the proposed BP-QUATRE algorithm to dynamic deployment in wireless sensor networks (WSN). The WSN becomes a popular research field [25‐29] due to its great value in real-world applications such as environment monitoring, healthcare applications, and forest fire detection. The WSN is composed of a large number of battery-powered, multifunctional, and resources-constrained sensor nodes. The performance of the whole WSN depends on the position of the sensors which affect the coverage, connectivity, energy efficiency, and network lifetime. In some applications, the locations of the sensors are predetermined by static ways. However, in some cases such as battlefield, underwater, and disaster-affected regions where is difficult to predetermine the locations by static ways, only dynamic deployment strategies can be adopted. In dynamic deployment, the sensors are first randomly placed within the area of interest and then sensors can relocate their locations by using information from other sensor nodes. But random initial deployment may not ensure effective coverage. In order to enhance the coverage rate of the whole WSN, a number of algorithms have been developed for dynamic node deployment, including virtual force [30], Voronoi diagram [31], and swarm intelligence algorithms [33‐36]. Many swarm intelligence algorithms are employed in sensor deployment, such as the particle swarm optimization (PSO) [32, 33], artificial bee colony algorithm (ABC) [34], differential evolution (DE) [35], and so forth. In this study, the proposed QUATRE algorithm is first applied to dynamic deployment in WSN with the aim of improving the coverage rate. The proposed algorithm is compared with PSO-based and DE-based dynamic deployment algorithm.

A set of experiments was conducted to evaluate the performance of the proposed algorithm BP-QUATRE and its application to dynamic deployment in WSN.

This paper proposes a novel BP-QUATRE algorithm for optimization problems. In BP-QUATRE, the population is divided into two subpopulations with sort strategy, and each subpopulation employs a different mutation strategy to balance between the diversity and convergence rate. In addition, adjusting scale factor with linear decrease strategy is adopted in BP-QUATRE algorithm to balance between exploration and exploitation ability. The proposed algorithm is verified under CEC2013 test suite. The experimental results demonstrate that the proposed BP-QUATRE algorithm not only has better performance than QUATRE variants “QUATRE/target-to-best/1” and “QUATRE/best/1,” but also has better performance than the PSO-IW algorithm and DE algorithm. We also apply the proposed BP-QUATRE algorithm to dynamic deployment in WSN. The simulation results demonstrate that the proposed BP-QUATRE algorithm has better coverage rate than the other competing algorithms. In the future work, we will apply BL-QUATRE algorithm to classify music genre [41].