A Novel Hybrid Algorithm of Max-Min Ant System with Quadratic Programming to Solve the Unit Commitment Problem

Unit commitment problem (UCP) is a combinatorial optimization problem that consists of planning the switching schedule of a set of production units [1-3]. Moreover, UCP allows us to determine over a precise planning period the power that each unit should produce in order to meet energy demand while respecting the economic or environmental constraints imposed [4]. UCP is therefore a complex problem that involves both binary variables and continuous variables and for which several solutions are proposed in the literature. UCP was proposed for the first time by Lowery in 1966. The dynamic programming method was used to overcome the major difficulty of enumerative methods. Indeed, the enumerative methods consists in testing all possible combinations of supply with the units considered in order to choose the optimal solution. This procedure may require significant resources for a large number of units.

Nevertheless, various methods have been used to solve the UCP. Amongst these methods are the Lagrangian method [5], Tabu search [6], Neural network [7], Fuzzy logic [8], Corridors of observations method [9], Particle swarm optimization [10], Artificial bee colony algorithm [11], and Ant colony algorithm [12]. Ant Colony optimization algorithm is a metaheuristic method which was introduced by Dorigo et al. in 1991 [13]. This method is inspired by the behavior of ant when searching their food. This algorithm is focused on artificial ants building their solutions in a given optimization problem and exchanging the quality of their solutions by a mechanism inspired from the behavior of real ants [14]. Even if their major drawback its slowness of convergence, in particular when solving large scale problems, Ant Colony algorithms is widely used for their great flexibility due to their distributed and adaptive nature [1]. This nature gives them average performance in the static case, but seem more suited for dynamic problems.

The first and original version of ACO called Ant system (AS) was applied for the first time to solve the traveler salesman problem [13, 15]. Unfortunately, the results obtained while using the original version of the AS were not competitive compared to those solutions from other algorithms such as GA, PSO [1]. As matter of fact, several improved versions were developed such as the ACS (Ant Colony System) version [16], MMAS (MAX-MIN Ant System) version [17]. In fact, AS algorithm follows proportional random transition rule [18]; the pheromone is deposited and evaporated in each path proportionally to the length of the path. Ant colony System (ACS) [16] version use a pseudo-random transition rule and the pheromone are deposited and evaporated only on best solutions [18]. MAX-MIN Ant System (MMAS) [19] is an improved version of AS developed by Stützle and applied to solve few optimization problem [19, 20].

Several studies have proposed MMAS approaches to solve some problems. Stützle et al. [20] proposes an extension of MAX-MIN Ant System and apply it to Traveling Salesman Problems and Quadratic Assignment Problems. He made two main changes, namely the modification of the transition rule and the addition of a local search method. The proposed version presents better results than the ACS and MMAS algorithms. Otherwise, the obtained results show that this algorithm can be used to efficiently find near-optimal solutions to hard combinatorial optimization problems and that it is one of the best methods for solving structured quadratic assignment problems.

Zecchin et al. proposes in 2003 [21] a method for optimizing a water distribution system using the MMAS algorithm. The proposed algorithm was tested on two systems of different sizes and the results were compared with those obtained with Ant System and the Genetic Algorithm. For the first system, the developed MMAS algorithm produced better results in terms of costs and computation time than the AS and GA algorithms [21]. For the second system, even if the proposed algorithm could not lead to the optimal solution, there is however a significant reduction in the computation time compared to the GA algorithms which provided a better cost.

Bai et al. in 2009 implements a parallel version of the MMAS algorithm on GPUs with a CUDA architecture [22]. The algorithm was tested on the traveling salesman problem and the results were compared to a sequential version of MMAS. The results show that the parallel version reduces solution costs and improves computational speed by a factor greater than 2 for different size of problem.

Santos et al. in 2016 applied the MMAS algorithm to the path planning problem for a mobile autonomous robot [23]. The compared results pointed that the MMAS algorithm was more efficient for this task than GA. Moreover, MMAS was able to find the optimal solution for all the topological maps tested.

Al-Shihabi et al. propose in 2017 a method of solving the financial planning problem based on the MMAS algorithm [24]. Three versions of MMAS using different heuristic functions during solution generation have been implemented and tested on 60 sample problems. The results obtained have been compared with those produced with Branch and Bound approaches (BB) and show that MMAS allows the lowest computation time.

Yu et al. developed in 2010 a hybrid approach for solving the unit commitment problem based on the MMAS version of ACO and the lambda iteration method [25]. Here, the lambda iteration method is used to determine economic dispatching and MMAS to determine the on/off schedule for the units over the planning period. This method was simulated in the MATLAB environment on 4 systems of different sizes. In order to improve the computation efficiency, the solution of unit commitment is coded into unit operation sequence, making the space complexity fall. The results obtained demonstrated the efficiency of this method and that its more suitable than the Genetic Algorithm (GA), Evolutionary Programming (EP) and Priorty List (PL) algorithms.

Lai et al. in 2012 [26] implements an MMAS version of ACO and an improved version by adding a local update process suitable for the UCP. Both versions were tested on a 10-unit system over a running period of 24-hour horizon and the results obtained are better than those obtained by the Hybrid Particle Swarm Optimization (HPSO), GA, Here-And-Now (HN) approach and the classic version of the ACO.

Taking into consideration the advantages of the MMAS algorithm previously highlighted, several authors have exploited this method for solving optimization problems such as Traveling Salesman [22], optimization of water distribution system [21], path planning [23], financial planning [24], and unit commitment [26]. MMAS (Max-Min Ant System) has the capacity of avoiding stagnation while others versions fail to it. Furthermore, the pheromone is bounded between a minimal value $\tau^{\min }$ and a maximal value $\tau^{\max }$. With the MMAS, only best ants are allowed to update the pheromone in their path, thus this yield to best solutions found in each iteration of algorithm. The drawbacks of Ant colony algorithm in general are that probability distribution change by iteration, time to convergence is uncertain (but convergence is guaranteed), research is experimental rather than theorical [1, 27]. These weaknesses of the MMAS could be strengthen by combining it with quadratic programming.

Quadratic programming is one of the most successful approaches for solving nonlinearly constrained optimization problems since its popularization in the late 1970s.This method has been used sole or combined with others algorithms (hybridization) in the literature by several authors and has produced satisfactory and very encouraging results for a wide variety of problems. Among these problems, we have electrical power management problems as the economic load dispatch [28], optimal power flow [29] and unit commitment [30].

This paper proposes of course a new hybrid Ant Colony algorithm for solving the unit commitment problem combining MMAS algorithm and Quadratic programming.

In this hybridization Quadratic programming method is used to optimize economic load dispatch (ELD) and the on/off switching program of units is ensured by MMAS algorithm.

The rest of the paper is organized as follows: Following the introduction, section 2 presents the mathematical formulation of unit commitment problem. Section 3 describe the keys steps of MMAS algorithm. Section 4 focusses on the proposed hybrid method for solving UCP. MAX-MIN Ant system algorithm and Quadratic programming method are developed. Section 5 clarify the setting of the initial heuristic parameters. Then section 6 is devoted to the presentation of the results and section 7 offers a conclusion.

MAX-MIN Ant System algorithm has been defined and used by some authors for solving a number of problems. This is the case in the ref. [24] for financial planning problem and for path planning problem in the ref. [23]. In this work, MAX-MIN Ant system is used to solve the unit commitment problem. The approach adopted is that the trials limits values are calculated for each period and we use a pheromone matrix for each time transition. This means that we are using N pheromone matrices for a horizon of N hours. Let us recall here the transition rule and the pheromone update rule of MMAS.

3.1 MMAS state transition rule

In the MMAS algorithm, ants build a solution in a probabilistic way step by step by using information related to pheromone and specifics heuristics information of the given problem. Thus, the probability for an ant k to moves from state i to the state j, is given by Eq. (8).

$P_{i, j}^{k}=\frac{\tau_{i, j}^{\alpha} \cdot \eta_{i, j}^{\beta}}{\sum_{k=1}^{c} \tau_{i, k}^{\alpha} \cdot \eta_{i, k}^{\beta}}$                (8)

with α, β: are respectively the relative importance of intensity and visibility.

$\eta_{i, j}$ : Visibility of the solution.

$\tau_{i j}:$ Pheromone intensity of the path.

3.2 MMAS pheromone updating rule

The pheromone update is done after each iteration. The update rule in each path is given by Eq. (9).

$\left\{\begin{array}{c}\tau_{i, j} \leftarrow(1-\rho) \cdot \tau_{i, j}+\Delta \tau_{i, j}^{\text {best }} \text { if } \tau^{\min }<\tau_{i, j}<\tau^{\max } \\ \tau_{i, j} \leftarrow \tau^{\max } \text { if } \tau_{i, j}>\tau^{\max } \\ \tau_{i, j} \leftarrow \tau^{\min } \text { if } \tau_{i, j}<\tau^{\min }\end{array}\right.$              (9)

$\Delta \tau_{i, j}^{\text {best }}$ is defined by the Eq. (10):

$\Delta \tau_{i, j}^{b e s t}=\left\{\begin{array}{c}\frac{1}{L_{b e s t}} \text { if the path }(i, j) \text { is the best } \\ \text { amongst the solution } \\ \text { 0 elsewhere. }\end{array}\right.$              (10)

where:

$\rho$ : pheromone evaporation coefficient.

$L_{\text {best }}$ : best solution cost.

The setting of initial heuristic parameters of an algorithm can have direct consequences on convergence behaviour. It is therefore necessary in this work to set heuristic parameters through criteria such as cost and speed. 2. Thus we have done manual adjustment of heuristic parameters with emphasis on the impact of each heuristic parameters on algorithm behaviour as the total generation cost and the execution time. This is one of the main contributions of this work. The settings are done on numerical for 4-unit system and 10-unit system whose generator characteristics and load demand are given in Appendix.

Apart from the $P_{\text {best }}$ and Q parameters whose values were respectively adjusted to 0.05 and 0.9 by considering the results produced in literature [33, 34] and the verification tests carried out, the other parameters are adjusted here. The parameters are adjusted by sampling and interpreting several measurements. The idea is to maintain the values of the other parameters and vary the one that the best value must be determined within the defined interval. The advantage of this method is to extract the best values of the parameters at the same time as we study their impact on the performance of the algorithm.

For each parameter, the simulations were repeated 30 times. The desired parameters α, β, ρ, m and maxIter have been bounded as follows: 0≤α≤5; 0≤β≤87; 0<ρ<1; 0<m≤1100; 0<maxIter≤1000 for 10-unit system and 0≤α≤5; 0≤β≤25; 0<ρ<1; 0<m≤1100; 0<maxIter≤1000 for 4-unit system.

where:

α: relative importance of the pheromone trail.

β: relative importance of the visibility.

ρ: pheromone evaporation coefficient.

m: number of ants.

maxIter: maximum number of iterations.

This section records some measurements that can justify the choice made for the values of heuristic parameters respectively for 4-unit system and 10-unit system.

Even if all the statistics do not appear, it should be noted that the choice of the values of the parameters takes into account a compromise between the values of the Total average generation cost, the best costs, the worst costs and the execution time for a given number of iterations.

5.1 Choice of the ρ parameter

This part deals with choosing an optimal value for the $\rho$ parameter. The fixed initial parameters are m=50; α=0.8; β=30; maxIter=70 for 10-unit system and m=200; α=0.3; β=0; maxIter=100 for 4-unit system.

Figure 2 shows the evolution of average total generation cost as function of $\rho$ for $\alpha$  values ranging from 0.5 to 5. It appears that the production cost function diverges for values of rho greater than 0.9. For this reason, only the values of rho lower than 0.9 will be considered in the rest of this paper.

As shown in Table 1 and Table 2, a statistical treatment of the different values makes it possible to choose as the optimal value of ρ=0.3 for 4-unit system, and ρ=0.7 for 10-unit system. It should be noted that this parameter does not have significant influence on the execution time.

2.png

Figure 2. Average total generation cost as function of ρ parameter for some values of α

Table 1. Impact of the ρ parameter for 4-unit system

Table 2. Impact of the ρ parameter for 10-unit system

TGC: Total Generation Cost

5.2 Choice of the α parameter

For this part, the fixed initial parameters are:

ρ=0.3; m=100; β=5; maxIter=50 for 4-unit system and ρ=0.7; m=50; β=30; maxIter=70 for 10-unit system and 4-unit system. Table 3 and Table 4 shows the influence of the α parameter on Mean total generation cost and mean execution time respectively for 4-unit system and 10-unit system. Table 3 shows an increasing of average total generation cost with a relatively constant execution time. It appears that α=0 present the best results for 4-unit system. Table 4 shows that for 10-unit system, the best value for α is 1.5 with a best total generation cost and good coefficients of variation for cost and execution time. It should be noted, as in the case of ρ, that the α parameter do not have a significant influence on the computation time.

Table 3. Impact of α parameter for 4-unit system

Table 4. Impact of α parameter for 10-unit system

5.3 Choice of the β parameter

For this part, the fixed initial parameters are ρ=0.3 α=0; m=100; maxIter=50 for 4-unit system and ρ=0.7; α=1.5; m=100; maxIter=20 for 10-unit system.

Figure 3 and Figure 4, and Tables 5 and 6 shows the total generation cost as well as the average execution time as a function of β parameters.

For ρ varying from 0.1 to 0.9, we obtain in figure 3 and figure 4 the curves that shows the evolution of the average total generation cost as a function of β. For the 4-unit system, β values are considered in the interval 0 to 25 and for 10-unit system are considered in the interval 5 to 87. Figure 3 shows for 4-unit system that the total generation cost increases significantly with increasing of β. For 10-unit system, as show in Figure 4, the total generation cost decreases with increasing of β and converge. The details given by the associated statistical study are recorded in the Tables 5 and 6. It therefore appears that the increase and decrease in β respectively for 4-unit system and 10-unit system improves the Total generation cost without degradation of time. The chosen β value is 0 for 4-unit system and 86 for 10-unit system, given the fact that they present best results.

5.4 Choice of the number of ants

The fixed initial parameters are ρ=0.3; α=0; β=0; maxIter=50 for 4-unit system and ρ=0.7; α=1.5; β=86; maxIter=20 for 10-unit system.

Tables 7 and 8 give the total generation cost and iteration time according to the number of ants. By varying the number of ants from 50 to 1100 for 4-unit system and from 10 to 1100 for 10-unit system, it appears that this parameter significantly improves the total generation cost. However, the major drawback remains the increase of execution time. It is therefore appropriate, depending on the needs, to make a good choice of m. In this paper, the choice of m is made so that we have a reduced cost and a short time as far as possible. Taking this into account the values of m chosen are 200 for 4-unit system and 300 for 10-unit system.

3.png

Figure 3. Average total generation cost as function of β parameter for 4-unit system

4.png

Figure 4. Average total generation cost as a function of β parameter

Table 5. Impact of β parameter on Total Generation cost and mean iteration time for 4-unit system

Table 6. Impact of β parameter on Total Generation cost and mean execution time

Table 7. Total generation cost and mean execution time depending of the number of ants for 4-unit system

Table 8. Total generation cost and mean execution time depending of the number of ants for 10-unit system

Taking into account all the previous considerations, the values retained for the parameters for 4-unit system and 10-unit system are given in Table 9.

Table 9. Optimal parameters retained

In this article, a new hybrid algorithm for solving the thermal unit commitment problem was proposed and performed.

This new approach is based on the MMAS (MAX-MIN Ant System) algorithm coupled with Quadratic Programming. The implementation on MATLAB environment.

Several repetitive and consecutive tests of our algorithm were carried out on two datasets, namely a set of 4 thermal units and one of 10 thermal units. Considering the 4-unit system, we got a best total generation cost of \$73,444.69 with an execution time of 3.0155s and for the 10-unit system a best total generation cost of \$83,371.2087 with an execution time of 4.0641s. In both cases, the results obtained were compared with those existing in the literature.

Comparisons show that for the majority of cases, the proposed algorithm significantly improves the quality of the solution in terms of cost while improving execution time.