Abstract: This study presented a novel quantum-inspired binary gravitational search algorithm method for solving the optimal power quality monitor placement problem in power systems for voltage sag assessment. In this algorithm, the standard binary gravitational search algorithm is modified by applying the concept and principles of quantum behaviour as to improve the search capability with faster convergence rate. The optimization considers multi objective functions and handles observability constraint determined by the concept of the topological monitor reach area. The overall objective function consists of three functions which are based on the number of required monitor, monitor overlapping index and sag severity index. The proposed algorithm is applied on the radial 69-bus distribution system and the IEEE 118-bus transmission system. To show the effectiveness of the proposed algorithm, its performance is compared to the other optimization techniques, namely, binary gravitational search algorithm and binary particle swarm optimization and quantum-inspired binary particle swarm optimization.
INTRODUCTION
Power quality has been treated as a prominent issue which demands utilities to deliver good quality of electrical power to end users especially to industries having sensitive equipment. Among all power disturbances, voltage sags are the most frequent type of disturbance and give severe impact on sensitive loads (Bollen and Gu, 2006). It has gain a significant attraction among researchers to study as to minimize the voltage sags and improve the power system’s voltage profile (Hedayati et al., 2010; Sirjani et al., 2010; Chettih et al., 2011). This type of voltage disturbance is defined by IEEE standard 1159-1995 as a voltage reduction in the RMS voltage to between 0.1 and 0.9 p.u. for duration between half of a cycle and less than 1 minute (Vilathgamuwa et al., 2004). It may cause failure or malfunction of sensitive equipment in industries (Shareef et al., 2009) which eventually leads to huge economic losses. Therefore, it is important to identify the source location of this power disturbance from the power quality monitoring program before any mitigation actions could be taken (Zayandehroodi et al., 2010).
Voltage sags are usually monitored by means of the conventional power quality monitoring practice in which monitors are installed at all buses in a power distribution network. The disadvantage of this approach is the widespread installation of PQMs. Reducing the number of monitors will reduce the total cost of power quality monitoring system and also reduces redundancy of data being measured by monitors (Eldery et al., 2004). Furthermore, the measurement at unmonitored buses could be done using estimation method (Kazemi et al., 2011). Thus, some methods are required for determining minimum number and the strategic location of PQMs to ensure that voltage sags are captured by the monitors. In Eldery et al. (2004), Olguin et al. (2006), Reis et al. (2008), Almedia and Kagan (2009) and Haghbin and Farjah (2009), the concept of monitor observability is utilized to find optimal placement of PQMs in transmission systems. However, this concept is not suitable for radial distribution networks (Ibrahim et al., 2010). Therefore, there is a need to develop a new optimal PQM placement method that is applicable for both transmission and distribution systems.
A few optimization techniques have been used to solve the optimal PQM placement problem in the last few years. In Eldery et al. (2004), the PQM placement method was developed by using the GAMS software as an integer linear program. In Reis et al. (2008), the branch and bound algorithm is applied by dividing the solution space into smaller spaces to make it easier to solve. However, it may give totally a wrong solution when there is a mistake in selecting a branch in earlier stages. In other words, it has a potential to be trapped in local minima and this is the main drawback of integer programming likes branch and bound (Mohammadi-Ivatloo, 2009). In Almedia and Kagan (2009), Haghbin and Farjah (2009) and Ibrahim et al. (2010), Genetic Algorithm (GA) is used for solving the optimal PQM placement problem. It seems that GA is preferred for solving this optimization problem but the disadvantage of GA is that it could not ensure better fitness in a new generation due to competitive selection and crossover operation which is biased toward experienced solution (Borji, 2008). Thus, an alternative optimization technique with better performance such as Binary Particle Swarm Optimization (BPSO) (Elbeltagi et al., 2005) and Binary Gravitational Search Algorithm (BGSA) (Rashedi et al., 2010) are suggested to be implemented.
The main aim of this study was to develop a new algorithm for solving the optimal PQM placement problem in power systems by applying the quantum behaviour to enhance the conventional BGSA. The merging between quantum computing and heuristic optimization technique is used in this work because of its capability to avoid premature convergence and improve the efficiency (Han and Kim, 2002; Vlachogiannis and Lee, 2008; Farzi, 2010; Jeong et al., 2010; Chou et al., 2011). The performance of the developed algorithm is then compared to another quantum-inspired computing method, namely, Quantum-inspired Binary Particle Swarm Optimization (QBPSO). In order to show the improvement of conventional method by using the quantum computing, the BGSA and BPSO are also included in this comparison.
AN OVERVIEW OF BINARY GRAVITATIONAL SEARCH ALGORITHM
Recently, heuristic optimization techniques are evolving rapidly in optimizing problems because they are found to be more robust and efficient in optimizing multidimensional problems in various fields (Rabii et al., 2011). The Binary Gravitational Search Algorithm (BGSA) is one of the most recent probabilistic optimization techniques which was introduced and developed by Rashedi et al. (2010). The conventional GSA was originally designed to solve problems in continuous valued space (Rashedi et al., 2009). The search algorithm is based on the metaphor of gravitational interaction between masses in the Newton theory. A jth bit of the ith agent (xij) in a system is represented as a bit 0 or 1 where a combination of bits gives the ith agent position. In this algorithm, the GSA operators calculate agent‘s acceleration (aij) based on gravitational force and its mass in each iteration using the following equations:
| (1) |
| (2) |
| (3) |
| (4) |
Where:
| G0 | : | Initial gravity constant; |
| T | : | Total number of iterations; |
| F | : | Gravitational force action; |
| M | : | Agent gravitational mass; |
| Rik | : | Hamming distance between ith agent and kth agent; |
| ε | : | Small positive coefficient, 2-52 |
| r | : | Uniform random variable in interval [0,1] |
| Kbest | : | Selection number of the best agent applying force to system which decreases monotonously in percentage from Kbestmax to Kbestmin along the iteration |
The next agent’s velocity (vij) is calculated based on its current velocity and its acceleration as expressed in Eq. 5. Then, a new agent’s position (xij) is updated using a condition as shown in Eq. 6. However, the velocity is limited in interval [-6,6] as to achieve a good convergence rate.
| (5) |
| (6) |
QUANTUM-INSPIRED BINARY GRAVITATIONAL SEARCH ALGORITHM
Quantum computing: The first quantum inspired computing method was introduced by Moore and Nayaranan (1995). It is a numerical computational method that utilizes the principle of quantum mechanics. The smallest unit for quantum computing which is known as quantum bit (Q-bit) may be in the “1” state, in the “0” state or in superposition of the two corresponding to weighting factors of complex number (α, β) (Han and Kim, 2002) as represented in (7). The |α|2 and |β|2 in the representation gives a probability that the Q-bit will be in the “0” state and the “1” state, respectively. Thus, the state probability can be normalized to unity as |α|2+|β|2 = 1:
| (7) |
Similar to agent’s position in BGSA, all decision variables (xij) can be represented by a string of Q-bits as a single representation called Q-bit individual. In the quantum computing, the Q-bit individual is updated using a quantum gate (Q-gate) which is a reversible gate and can be represented as a unitary operator, U. It is either a rotation gate, NOT gate, controlled NOT gate or the Hadamard gate etc. (Hey, 1999) used to change the probability of the Q-bit state so as to promise a reversible of the formation. In this study, the rotation gate is considered since it has been applied in many heuristic search algorithms (Han and Kim, 2002; Vlachogiannis and Lee, 2008; Jeong et al., 2010; Chou et al., 2011). The rotation gate is expressed as follows:
| (8) |
BGSA with quantum computing: As refer to the traditional BGSA, many random variables are used in the calculation which causes the main idea to implement the gravitation on the search algorithm will not give significant effects. Therefore, the random variables in Eq. 12 and 14 are removed as to reduce too much dependence on randomise exploration process. Furthermore, the small positive coefficient, ε can be neglected because it is not significant to apply in the binary domain where the distance between two agents is only exist in integer number. As a result, the agent’s acceleration aij calculation in (1) to (4) can be summarized as follows:
| (9) |
In the proposed QBGSA, a rotation angle (Δθ) is utilized in order to implement the quantum computing in this algorithm and the parameter will be used to update the agent’s position, xij. Therefore, the concept of acceleration, aij updating procedure in the BGSA should be modified as to obtain the rotation angle where the gravitational mass is replaced to the magnitude of the rotation angle (θ). According to Eq. 9, the gravitational force acting on the particular agent depends on other masses, Mk and distance between other agents to the particular agent. These two elements are given by a decision parameter, ε in the proposed QBGSA. In this study, the same variation operators as suggested by Jeong et al. (2010) are used which are called coordinate rotation gate and dynamic magnitude rotation angle approach. As a result, there is no pre-determined lookup table and the rotation angle calculation is proposed as in the following expression:
| (10) |
where, θ is the magnitude of rotation angle which monotonously decreases from θmax to θmin along iteration and can be obtained using the following conditions:
| (11) |
| (12) |
where, τ is a maximum of different number of bits between ith agent and kth agent obtained from the percentage of total bits which is to be considered as effective force acting on the ith agent. That means attraction force by a far agent is very small and can be neglected. However, the best fitness agent with the highest mass can give effective force on the agent even its position is far to ith agent and it will give twice more force than the other forces when its position is near to the ith agent. On the other hand, the lighter agent can move easily as compared to heavier agent due to inertia mass action against the motion (Rashedi et al., 2009). As for that reason, only the heavier kth agent can give effective acceleration on ith agent.
Then, the QBGSA operators update the Q-bit individual string based on the obtained rotation angle using the rotation gate as shown in Eq. 13. The agent’s position (xij) is updated based on probability of |β|2 stored in the Q-bit individual using criteria as given in Eq. 14:
| (13) |
| (14) |
APPLICATION ON PQM PLACEMENT PROBLEM
The monitor coverage concept: The monitor coverage is the most important entity in the determination of PQM placement. It is used to evaluate the placement so as to guarantee the observability of the whole power network. The conventional monitoring coverage concept is called the Monitor Reach Area (MRA) (Olguin et al., 2006). In this study, the Topological Monitor Reach Area (TMRA) is utilized to make it applicable for all systems including distribution systems (Ibrahim et al., 2011). The TMRA matrix is a combination of MRA matrix and topology (T) matrix by using operator ‘AND’ as shown in Eq. 15. The T matrix is used to give more restriction on the monitor coverage so as to fulfill the radial topology which usually exists in the distribution system. The TMRA matrix columns represent bus number and its rows are correlated to fault location for all different types of fault.
TMRA(j,k) = MRA(j,k)xT(j,k) |
(15) |
PQM problem formulation: There are three common elements required in the binary optimization technique, namely, decision vectors, objective function and optimization constraints. Thus, each element is formulated and explained in order to obtain the optimal solution for the PQM placement.
Decision vector: To satisfy the solution process in this study, the Monitor Placement (MP) vector is introduced to represent the binary decision vector (xij) in bits in the optimization process. The bits of this vector indicate the positions of monitors that are either needed or not in power system network. The dimension of the vector corresponds to the number of buses in the system. A value 0 (zero) in the MP (n) indicates that no monitor is needed to be installed at bus n whereas a value 1 (one) indicates that a monitor should be installed at bus n. Thus, the MP vector is described by the following expression:
| (16) |
Objective function: The use of optimization tool is to determine the minimum number of PQM with the best placement while maintaining the observation capability of any fault occurrences which may lead to voltage sag events in power system. Thus, the objective function is formulated to solve two objectives, namely, optimal number of required monitors and optimal locations to install the monitors. The number of required monitors (NRM) to be minimized can easily be obtained and expressed as:
| (17) |
To determine the best locations to install the monitors, additional parameters are required to achieve the goals. There are two indices, namely, Monitor Overlapping Index (MOI) and Sag Severity Index (SSI) to be used for evaluating the suggested PQM placement in the optimization process (Ibrahim et al., 2011). The MOI indicates the level of overlapping in the PQMs coverage which is given by the suggested placement. Therefore, the MOI value should be minimized to find the best PQM placement. The MOI value can be calculated using the following expression:
| (18) |
where, NFLT is the total number of fault locations considering all types of faults.
Meanwhile, the SSI index indicates a severity level of a specific bus towards voltage sag, where any fault occurrence causes a large drop in voltage magnitudes for most of the buses in the system. Therefore, the highest SSI value among the same NRM should also be obtained to find the best PQM placement. In order to calculate SSI, the Severity Level (SL) based on threshold (t) in p.u. should be derived first as follow:
| (19) |
where:
| NSPB | : | Number of phases experiencing voltage sag with magnitudes below t p.u. |
| NTPB | : | Total number of phases in the system |
Then, the SSI value is obtained by considering five threshold levels; 0.1, 0.3, 0.5, 0.7 and 0.9 p.u. where the lowest t value is assigned with the highest weighting factor, k and vice versa as in (20). The SSI values are stored in a matrix where its column correlated to bus number and its row correlated to Fault type (F).
| (20) |
To combine the MOI and SSI indices, both of them should have similar optimal criteria of either maximum or minimum. In this case, the SSI matrix should be modified to give a minimum criterion in optimization to make it similar to the case of minimization of MOI. It is important to note that a maximum value of SSI element is equal to 1. Thus, it can be obtained by using complementary matrix of SSI. Then, a Negative Severity Sag Index (NSSI) is introduced to evaluate the best placement of monitors in the system. The NSSI can be obtained using Eq. 21. As a result, a lower NSSI value indicates a better arrangement of PQMs in the power system.
| (21) |
where:
| ONE | : | Matrix with all entries ‘1’ where its dimension is the same as the SSI matrix; |
| NFT | : | Number of fault types |
All the above functions can be combined in single objective function by using the summation method since all the functions have similar optimal criteria. However, the objective functions should be independent and should not influence each other in finding the optimal solution. The single multi-objective function to solve optimization problems in this study is expressed in Eq. 22. The concept is based on weighted sum method that has been commonly used to solve multi-objective problems (Marler and Arora, 2010). However, it is not exactly similar to weighted sum method since the relative weight of NRM is automatically increases when the NSSI increases due to more PQM placements in the system so as to maintain the selection priority.
| (22) |
System constraints: The optimization algorithm must run while satisfying all the constraints that are used to find optimal number of PQMs for the system. As given in Eq. 23, the multiplication of the TMRA matrix by the transposed MP matrix gives the number of monitors that can detect voltage sags due to a fault at a specific bus. If one of the resulting matrix elements is 0 (zero) then it means that no monitor is capable of detecting sag caused by faults at a particular bus, whereas if the value is greater than 1 (one), that means more than one monitor have observed a fault at the same bus. For that reason, the following restrictions must be fulfilled to make sure that each fault is observed by at least one monitor:
| (23) |
Implementation of the QBGSA: The optimization explores the optimal solution as defined in the objective function through the bits manipulation of decision vector subject to the optimization constraints in each generation. The process is iterated for a fixed number of times or until a convergence criterion is achieved. The following are the steps of QBGSA algorithm as to obtain the optimal PQM placement in power system:
| • | Randomly initialize all entries of the MPs (agent’s positions, xij) in the system within feasible arrangement. Initialize the Q-bit individual values: |
| (24) |
| • | Evaluate performance of each MP vector using the formulated objective function (f) as based on equations in 17, 18, 21 and 22. Record all fitness values for each agent, fi(t). Then, update the best and the worst fitness values using the following equations: |
| (25) |
| (26) |
| • | Update each agent’s mass using the following equations: |
| (27) |
| (28) |
| • | Update for ith agent the rotation angle, Δθij(t+1) as given in (10) with respective conditions in (11) and (12) |
| • | Obtain the new pair (α(t+1),β(t+1)) of each Q-bit individual, Q-bitij(t+1) as given in (13) |
| • | Update MP vector by bit updating, xij(t+1) using the given criteria in (14) |
| • | Evaluate the new MP vector using the optimization constraints as in Eq. 23. Then, reject the MP vector which does not fulfill the constraints |
| • | Repeat step (vi) to (vii) until all agents take suitable positions and the population size becomes the same as the initial population size |
| • | Repeat step (ii) to (viii) until optimization convergence criteria is achieved. In this study, the convergence criterion is based on maximum iteration number |
RESULTS AND DISCUSSION
To demonstrate the performance of the proposed QBGSA optimization technique in solving the optimal PQM placement problem, two test systems are used in this case study, namely, the 69-bus distribution system and the IEEE 118-bus transmission system. In this study, bolted three-phase (LLL) faults, Double-line to Ground (DLG) faults and Single-phase to Ground (SLG) faults were simulated at each bus in the system using the DIgSILENT software to obtain the FV matrix. The new QBGSA is implemented and compared to the conventional BGSA (Rashedi et al., 2010), QBPSO (Jeong et al., 2010) and BPSO (Kennedy and Eberhart, 1997) as to illustrate its performance in solving the same problem.
All the optimization parameters are standardized where population size and
maximum population are set to 40 and 150, respectively. In the BPSO, two positive
coefficients are set to 2 (c1 = c2 = 2) and inertia weight,
w monotonously decrease from 0.9 (wmax) to 0.4 (wmin).
In the BGSA, initial gravity constant, G0 is set to 100 and the best
applying force, Kbest monotonously decrease from 100% (Kbestmax)
to 2.5% (Kbestmin). In the QBPSO, the magnitude of rotation angle,
θ monotonously decrease from 0.05π (θmax) to 0.001π
(θmin) and all initial Q-bit individual (α0+jβ0)
is set as
Case I: the 69-bus test system: The 69-bus test system is a balanced radial distribution system that is fed by external grid to feeder nominal voltage at 12.66 kV. The system consists of 69 buses interconnected by 73 lines including 5 tie lines. The 69-bus test system data are provided in Rugthaicharoencheep and Sirisumrannukul, (2009).
Table 1 shows the worst, average, best and standard deviation, σ from the adopted algorithms’ performances in terms of convergence rate and quality of optimal solution after performing 25 runs at α = 0.85 p.u. for the 69-bus distribution system. Figure 1 illustrates the convergence characteristics of the algorithms in obtaining the best optimal solution for the test system. Here, BPSO is the fastest in convergence but the worst in term of optimal solution as compared to the other algorithms. This shows a premature convergence in BPSO. Beside this, BGSA gives better optimal solution than BPSO but its convergence rate is the worst. In this case, merged quantum computing to BPSO and BGSA has shown a significant improvement in escaping from the premature convergence and to give much better optimal solution. Although QBPSO provides better solution than BPSO, it requires more iterations as to explore over a search space for the solution. The QBGSA has obtained the best optimal solution with the lowest standard deviation but its convergence is relatively slow. However, the proposed QBGSA shows an overall improvement on the convergence rate of the traditional BGSA. Hence, the best optimal solution given by QBGSA is taken as the PQM placement in this study. The PQM placement for this case study is buses 1, 6, 29, 32, 36, 38, 48 and 57.
Case II: the IEEE 118-bus test system: The IEEE 118-bus test system is a balanced transmission system which consists of two voltage levels which are 138 kV and 345 kV. There are 34 generating stations, 20 synchronous condensers and 9 transformers.
| Fig. 1: | The convergence characteristics of BPSO, BGSA, QBPSO and QBGSA for 69-bus case study |
| Fig. 2: | The convergence characteristics of BPSO, BGSA, QBPSO and QBGSA for 118-bus case study |
| Table 1: | Performance of BPSO, BGSA, QBPSO and QBGSA to solve optimal PQM placement in 69-bus system for α at 0.85 p.u. |
| Table 2: | Performance of BPSO, BGSA, QBPSO and QBGSA to solve optimal PQM placement in 118-bus system for α at 0.85 p.u. |
The test system consists of 118 buses which are interconnected by 177 lines. The IEEE 118-bus test system data are provided in Christie (1993).
Table 2 shows the worst, average, best and standard deviation, σ from the adopted algorithms’ performances in terms of convergence rate and quality of optimal solution after performing 25 runs at α = 0.85 p.u. for the 118-bus transmission system. Figure 2 illustrates the convergence characteristics of the algorithms in obtaining the best optimal solution for the test system. As can be seen in the table, BPSO is the fastest in convergence. However, it yields highly unacceptable suboptimal solutions as compared to the other three methods which show a premature convergence as in the 69-bus case. On the other hand, BGSA gives better optimal solution than BPSO but the worst in terms of convergence rate. Again, the merged quantum computing to BPSO and BGSA has proven that they are able to escape from the premature convergence as to give much better optimal solution. Although the QBPSO and QBGSA provide better solution than BPSO, they require more iteration. In comparison between QBGSA and QBPSO, the QBGSA has obtained a better optimal solution with the lowest standard deviation and its convergence is comparable to the QBPSO. Hence, the PQM placement for this case study is buses 6, 22, 43, 56, 62, 71, 87, 93, 98 and 108 which is taken from QBGSA optimal solution since it is the best solution.
CONCLUSIONS
This study presented a novel QBGSA and a comparative performance of QBGSA, QBPSO, BGSA and BPSO in solving the multi-objective optimization problems for optimal PQM placement in a distribution test system. The optimization problem formulation is mainly based on the use of the TMRA and the two placement evaluation indices, namely, the SSI and the MOI. The optimization techniques have been tested on the 69-bus distribution system and the IEEE 118-bus transmission system for determining the best optimal PQM placements. The comparative results reveal that the proposed QBGSA is the most effective and precise among the aforementioned optimization techniques.