Index

Abstract

Nonlinear single-unit commitment problem (NSUCP) is a NP-hard nonlinear mixed-integer optimization problem, encountered as one of the toughest problems in power systems. This paper presents a new algorithm for solving NSUCP using genetic algorithm (GA) based clustering technique. The proposed algorithm integrates the main features of binary-real coded GA and K-means clustering technique. Clustering technique divides population into a specific number of subpopulations. In this way, different operators of GA can be used instead of using one operator to the whole population to avoid the local minima and introduce diversity. The effectiveness of the proposed algorithm is validated by comparison with other well-known techniques. By comparison with the previously reported results, it is found that the performance of the proposed algorithm quite satisfactory.

Keywords: Nonlinear, single-unit, commitment, problem, , Genetic, algorithm , Clustering, technique , Optimization

Received: 26 October 2016 / Revised: 18 January 2017 / Accepted: 16 February 2017 / Published: 15 March 2017

Contribution/ Originality

This study presents a new algorithm for solving nonlinear single-unit commitment problem using genetic algorithm based clustering technique; where it integrates the main features of binary-real coded genetic algorithm and K-means clustering technique. The tests demonstrated that the proposed approach has a satisfactory performance compared to previous studies.


1. INTRODUCTION

NSUCP, one of the most important tasks of operational planning of power systems, which has a significant influence on secure and economic operation of power systems [1]. An efficient commitment scheduling save millions of dollars per year in fuel and related costs, increases the system reliability, and maximizes the energy capability of reservoirs [2, 3]. The NSUCP involves determining on/off status as well as the real power outputs of the generating units to meet forecasted demand and reserve requirements at minimal operating cost over the planning period subject to various system - and generator-based constraints [1].

The NSUCP is a complex mathematical optimization problem with large amount of 0-1 decision values as well as continuous variables, and a wide spectrum of equality and inequality constraints [4]. Research efforts have been concentrated on efficient and near-optimal NSUCP algorithms that can be applied to the realistic power systems and have reasonable storage and computation time. Such alternative algorithms studied for the NSUCP include both deterministic methods and meta-heuristic techniques. The investigated deterministic methods include priority list (PL) [5] dynamic programming (DP) [6] branch-and-bound method [7] Lagrangian relaxation (LR) [8] and Mixed integer linear programming (MILP) [9]. Among these methods, the PL method is simple and fast, but the quality of final solution is not guaranteed. The DP suffers from the problem of dimensionality; where with increase in the problem size, the solution time increases rapidly with the number of generating units to be committed. Branch-and-bound method suffer from the “curse of dimensionality” if the size of a system is large. The integer and mixed-integer methods have only been applied to small NSUCPs and have required major assumptions that limit the solution space because it is difficult achieve a balance between the efficiency and the accuracy of the model. The LR method is capable of solving large-scale NSUCP problems within short execution times. Nevertheless; the LR method may not provide feasible solutions to the relaxed problem due to the inherent non-convexity of the NSUCP [10].

Because of the inadequacy of deterministic methods in handling large-size instances and/or non-convex search space of the NSUCP, various meta-heuristics algorithms are investigated such as: artificial neural network (ANN) [11]; GA [12-16] evolutionary programming (EP) [17] simulated annealing (SA) [18, 19] shuffled frog leaping algorithm [20] particle swarm optimization (PSO) [21] tabu search (TS) [19, 22] fuzzy Logic [23] harmony search algorithm (HSA) [24] and artificial bee colony algorithm (ABC) [25]. The practical advantage of meta-heuristic methods lies in both their effectiveness and general applicability.

Furthermore, the combination between meta-heuristics and deterministic methods or other meta-heuristics are investigated in order to utilize the feature of one method to overcome the drawback of another method [26-33]. In Sudhakaran1 and Ajay-D-Vimal Raj [26] the authors proposed a memetic algorithm, which combined a real coded GA with local search (LS) and TS for solving large NSUCP. First, a set of feasible generator schedule is formulated by real coded GA method. Then these pre-committed schedules are optimized by ordinary LS and TS. In Nayak and Sharma [27] a hybrid between ANN and SA approach is presented to solve NSUCP. The ANN is used to determine the discrete variables corresponding to the state of each unit at each time interval. While the SA method is used to generate the continuous variables corresponding to the power output of each unit and the production cost. In Rajan and Mohan [29] the authors presented a new approach to solving the short-term NSUCP using an EP-based TS method. EP is used to solve NSUCP and TS is used to increase the efficiency of algorithm and avoid entrapment in local minima. In Todosijević, et al. [30] the authors proposed a hybrid approach which combines variable neighborhood search meta-heuristic and mathematical programming to solve NSUCP. In addition, the economic dispatch problem is solved by the Lambda iteration method for each period. Also in Dieu and Ongsakul [31] an enhanced merit order (EMO) and augmented Lagrange Hopfield network (ALHN) are proposed for solving hydrothermal scheduling (HTS) problem with pumped-storage units; where EMO is efficient in unit scheduling, whereas ALHN can properly handle generation ramp rate limits, and time coupling constraints such as limited fuel, water discharge for hydro units, and water balance for pumped-storage units. In Singhal, et al. [32] a hybrid approach based on a novel binary artificial bee colony (NBABC) algorithm and LS is developed to solve the NSUCP. Finally, in Zheng [33] a combined GAs with SA algorithm is proposed to solve NSUCP. In this approach the global convergence of GA can be improved by introducing annealing algorithm to the evaluation functions and the selection manipulation. The hybridization reduces the search space for large scale NSUCP and thereby, reduces the execution time.

GA is a powerful tool in optimization problems, especially in the non-convex problems [34]. The important characteristics of GA are their compatibility with nonlinear and/or discrete problems and parallel search in complicated spaces. the limitation of GA is that it can be converge to local minima. This limitation can be handled by using clustering with GA. Clustering is a process of divided huge group of data into groups of similar elements. Each group, called cluster, consists of elements that are similar between themselves and dissimilar to elements of other groups [35]. Clustering techniques have been used in a wide range of disciplines such as psychiatry [36-47]. The K-means is possibly the most commonly-used clustering algorithm because of its simplicity and accuracy [48].
In this paper, we propose a new approach for solving NSUCPs using a new algorithm for solving NSUCP using GA based K-means clustering technique to integrate the main features of the both algorithms. We have used binary-real coded GA; where the binary part deals with the scheduling of units and the real determines the amounts of power generated by committed units. K-means clustering technique divides population into a specific number of K subpopulations. In this way, different K operators of GA are allowed to use instead of using the same operator with the whole population and avoids the local problem minima and introduces diversity.

This paper is organized as follows: Section 2 provides the mathematical formulation of the NSUCP. Section 3 briefly introduces the basics of GA. In section 4, clustering technique is briefly introduced. In Section 5, the proposed algorithm is described. The computational results and discussions are presented in Section 6. Finally, the paper is concluded in Section 7.

2. NSUCP MATHEMATICAL FORMULATION

The NSUCP involves the determination of the startup and shut down times as well as the power output levels of all generating unit at each time step, over a specified scheduling period T [1]. The problem is formulated as described below.

2.1. Objective Functions

The objective of the NSUCP is minimizing the total production cost which includes fuel cost, startup cost, and shut down cost.
 

3. BASICS OF GA

GAs are general-purpose search techniques based on principles inspired from the genetic and evolution mechanisms observed in natural systems and populations of living beings. GA basic principle is the maintenance of a population of solutions to a problem (genotypes) as encoded information individuals that evolve in time [50, 51]. GA starts with initialization of random population called chromosomes (solutions). Each chromosome evaluated by the fitness function (objective function), giving a measure of the solution quality called the fitness value. Finally, selection, recombination, crossover and mutation are being performed to improve these chromosomes. These steps are repeated until the termination criterion is met, and the best chromosome of the last generation is reported as the final solution

4. CLUSTERING TECHNIQUES

Clustering is process of Finding groups of elements such that the elements in a group will be similar (or related) to each other and different from (or unrelated to) the elements in other groups [35]. Several algorithms for clustering have been proposed in the literature [43-47]. The K-means clustering algorithm is the most popular clustering tool used in scientific and industrial applications [48]. It proceeds as follows: Firstly, K centroids are defined. Secondly, for each of the remaining elements, based on the distance between the element and the center, an element is assigned to the cluster to which it is the most similar. Finally, the new center for each cluster is re-calculated and the process iterates until no more changes are done. In other words centroids do not move any more [52]. K-means algorithm for 2-dimensional dataset with three clusters is illustrated in Fig. 1.

Fig-1. Illustration of K-means algorithm (Taken from Jain [53])

5. GA BASED CLUSTERING TECHNIQUE FOR SOLVING NSUCP

In this section, GA based clustering technique is presented to solve NSUCP. The algorithm integrates the features of binary-real coded GA and K-means clustering technique. The binary-real-coded GA is used to tackle both unit scheduling and load dispatch problems instead of using two different approaches. The binary coded GA is applied to the unit scheduling problem, while the real coded GA is used for the load dispatch problem. Clustering technique represented in K-means clustering divides population to a specific number of K subpopulations. So, different operators of GA can be applied instead of using one operator to the whole population. The details are addressed in the following subsections:

5.1. Chromosome Representation and Initialization

Fig-2. Representation of the chromosome

5.2. Handling Constraints

Using GA to solve constrained optimization problem yields infeasible solutions, so the constraints must be handled [54]. Constraint handling techniques can be roughly classified as follows [55, 56]:

Repairing technique is used in this paper to handle with infeasible solution. The idea of this technique is to convert any infeasible individuals to a feasible solution by repairing the sequential possible violations constraints in the NSUCP problem. The following four repairing mechanisms taking from literature [16, 55, 57-59] are incorporated in the proposed algorithm.

Spinning reserve constraint is satisfied by applying a heuristic algorithm in which uncommitted units are committed [16] in ascending order of their average full load cost. The average full-load cost of unit i can be expressed as:

Minimum up and down-time constraints are satisfied by adjusting unit status [57]. The state of the unit is evaluated from the first hour. If at time‘t’ the minimum up or down time constraint is violated, the state (on/off) of the unit at that hour is reversed and updated. The process continues until the last hour.

Excessive spinning reserve is not desirable due to the high operation cost. Therefore, a heuristic algorithm is used to de-commit some units one by one [3] in descending order of their average full load costs, until the spinning reserve constraint is just satisfied at any time instant. However, such de-commitment is made subject to the satisfaction of the up/down time constraints of a unit, i.e., a unit will be de-committed only if no up/down time constraint of the unit is violated from such de-commitment [16].

For adjusting the system power balance at time instant, the power balance constraint repairing is applied to the following two cases [16]:

5.3. Selection Operation

The selection operator takes GA search towards promising regions in the search space [60]. The binary tournament selection operator [61] is applied in this paper; where two individuals are chosen at random and the better objective value of the two individuals is selected and copied in mating pool. This is repeated until the size of the mating pool equals to the original population.

5.4. K-Means Clustering Technique

To keep diversity and avoid trapping in local minima, the K-means cluster algorithm is implemented. In this step, the population in mating pool is split to K separated subpopulations with dynamic size, as illustrated in Fig. 3.

Fig-3. The population is split into K separated subpopulations with dynamic size

5.5. Crossover Operator

Crossover operator used to exchange information between two parents and produce two new offspring for the next population [62]. In our study, common crossover operators are used; which are given below.  

In horizontal band crossover [63] two random numbers are generated, and information inside the horizontal region of the grid (matrix) determined by the numbers is exchanged between two parents to generate two off-springs based on a fixed probability. Fig. 4 shows how the horizontal band crossover works.

Fig-4. Horizontal band crossover

In this crossover [64] the bits are exchanged between the parent points to create two new offspring points by using randomly generated mask. In the random mask ‘1’ represent bit swapping and ‘0’ denotes bits unchanged as shown in Fig. 5.

Fig-5. uniform crossover operator

5.6. Mutation Operator

The aim of this operator is to help the population to go away from local minimum. It is applied to each offspring in the population with a known probability [62]. In our study, common mutation techniques are used; which are explained below.

Fig-6. Mutation operator

This operator [66] looks for (10) or (01) in commitment schedule. These combinations are randomly changed to 11 or 00 as in Fig. 7.

Fig-7. Intelligent mutation operator

5.7. Combination Stage

In this stage, a new population is created by combining all subpopulations, as illustrated in Fig. 8.

Fig-8. Commination stage

5.8. Elite-Preserving Operator

This operator serves to keep the best solutions found by saving a group of them for the next generation. It can be implemented by copying the best chromosomes from the current population to the next generation [67].

6. COMPUTATIONAL RESULTS AND DISCUSSIONS

In this section, computational verification of the proposed algorithm is carried out. The proposed algorithm is executed and evaluated on two test power systems 10 and 60 units systems over a 24-h time horizon taken from the literature [16, 65]. The proposed algorithm is coded using MATLAB programming language. Table 1 shows the parameters setting in the computational results, while the properties of the 10 units test system are given in Table 2. The hourly forecast load demand  is presented in Table 3. The unit related data given in Table 2 for the 10-unit system and hourly power demands are duplicated 6 times to give the data of the 60-unit system. In the two systems, the minimum spinning reserve requirement is considered to be 10% of the forecasted power demand at that time instant. In Table 2:  is the status of unit i. It indicates how long the unit was on/off prior to the start of the time horizon. A positive/negative value means that unit i was on/off for that number of time.

Table-1. The proposed algorithm parameters

Parameter
Values
Prolem1
Prolem2
Population size
500
1000
Crossover rate
1
0.95
Mutation rate
0.01
0.01
Iteration
100
100
Number of cluster (k)
1&2&3
1&2&3

Table-2. The properties of the 10 units system

Table-3.  The hourly forecast load demand

Hour
1
2
3
4
5
6
7
8
9
10
11
12
Demand(MW)
700
750
850
950
1000
1100
1150
1200
1300
1400
1450
1500
Hour
13
14
15
16
17
18
19
20
21
22
23
24
Demand(MW)
1400
1300
1200
1050
1000
1100
1200
1400
1300
1100
900
800

The best and worst production costs as well as the average and standard deviation for each power system at different number of cluster, obtained over 10 independent runs, are presented in Table 4. From the table, we can observe the consistency of the proposed algorithm over the different 10 runs. In addition, we can infer the robustness of the proposed algorithm; where that the gap between the best and the worst solutions is very small.

Table-4. Statistical analysis of the solutions obtained from 10 independent runs for each power system

Number of unit
10-unit
60- unit
Number of K
K=1(without cluster)
K=2
K=3
K=1(without cluster)
K=2
K=3
Best cost
565690
564280
564230
3370500
3368400
3368100
Worst cost
566000
565000
565350
3380100
3373500
3369800
Average
565866
564615
564481
3374500
3369800
3368610
Standard deviation
131.6207
251.047
103.58
350.6
236.39
184.63

In addition, the best production costs of 10-unit and 60-unit power system of the proposed algorithm with different number of cluster are shown in Fig. 9. It is clear that the production cost of the proposed algorithm at k=3 is smaller than those at k=1 and k=2, therefore we can say that if the number of clusters increased, the production cost decreased.

Fig-9.  Comparison of the best production cost of each power system of the proposed algorithm at different number of cluster (k=1,k=2 and k=3)

Furthermore, the best solutions of the 10-unit power system and 60-unit power system obtained by the proposed algorithm are presente d in Table 5 and Table 6 respectively. While, Fig.10 shows the convergence of the best solutions of the 10-unit power system and 60-unit power system at k=1 (without cluster), k=2 and k=3.

Table-5. The obtained best solution of the 10-unit power system

Hour
Unit schedule
Power generated by units (MW)
cost
1
2
3
4
5
6
7
8
9
10
Production
Startup
1
1.1E+09
455
245
0
0
0
0
0
0
0
0
13683.13
0
2
1.1E+09
455
295
0
0
0
0
0
0
0
0
14554.5
0
3
1.1E+09
455
370
0
0
25
0
0
0
0
0
16809.449
900
4
1.1E+09
455
455
0
0
40
0
0
0
0
0
18597.668
0
5
1.101E+09
455
430.1015
0
89.8985
25
0
0
0
0
0
20042.085
560
6
1.111E+09
455
455
41.0574
123.9426
25
0
0
0
0
0
22440.678
1100
7
1.111E+09
455
455
85
130
25
0
0
0
0
0
23284.396
0
8
1.111E+09
455
455
130
130
30
0
0
0
0
0
24150.341
0
9
1.111E+09
455
455
130
130
85
20
25
0
0
0
27251.056
860
10
1.111E+09
455
455
130
130
162
33
25
10
0
0
30057.55
60
11
1.111E+09
455
455
130
130
162
73
25
10
10
0
31916.061
60
12
1.111E+09
455
455
130
130
162
80
27.4613
40.5387
10
10
33893.895
60
13
1.111E+09
455
455
130
130
162
33
25
10
0
0
30057.55
0
14
1.111E+09
455
455
130
130
85
20
25
0
0
0
27251.056
0
15
1.111E+09
455
455
130
130
30
0
0
0
0
0
24150.341
0
16
1.111E+09
455
455
65.1721
49.8279
25
0
0
0
0
0
21596.038
0
17
1.111E+09
455
381.0243
33.2035
105.7722
25
0
0
0
0
0
20704.525
0
18
1.111E+09
455
443.61259
73.2606
103.12678
25
0
0
0
0
0
22429.461
0
19
1.111E+09
455
455
130
130
30
0
0
0
0
0
24150.341
0
20
1.111E+09
455
455
130
130
162
33
25
10
0
0
30057.55
490
21
1.111E+09
455
455
130
130
85
20
25
0
0
0
27251.056
0
22
1.1E+09
455
455
0
0
145
20
25
0
0
0
22735.521
0
23
1.1E+09
455
425
0
0
0
20
0
0
0
0
17645.364
0
24
1.1E+09
455
345
0
0
0
0
0
0
0
0
15427.42
0
564230$

Table-6. The obtained best solution of the 10-unit power system (production cost of 3368100$)

Unit number
Time (1–24 h)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
7
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
8
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
9
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
10
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
11
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
12
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
13
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
14
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
15
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
16
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
17
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
18
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
19
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
20
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
21
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
22
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
23
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
24
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
25
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
26
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
27
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
28
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
29
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
30
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
31
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
32
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
33
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
34
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
35
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
36
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
37
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
38
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
39
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
40
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
41
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
42
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
43
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
44
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
45
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
46
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
47
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
48
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
49
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
50
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
51
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
52
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
53
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
54
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
55
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
56
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
57
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
58
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
59
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
60
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Finally, the comparison between the proposed algorithm at k=1, k=2 and k=3  for each system and other meta-heuristic-based techniques [5, 12, 14, 17, 18, 20, 65, 66, 68, 69] is presented in Table 7. The production costs of the selective approaches for each system are shown in Fig. 11. From the Table and the Figure we can see that, the best solution obtained by the proposed algorithm at k=1 (i.e. without cluster) is better than the solutions obtained by LR [12] and ESA [18] for the two systems. On the other hand, the proposed algorithm at k=2 gives solutions better than the solutions obtained by EP [17] ICGA [69] PL [5] and ESA [18]. But, the solution obtained by the proposed algorithm at k=3 is better than the solutions obtained by all techniques which means the superiority of proposed algorithm at k=3. In other words, the increasing of the number of clusters in the proposed algorithm gives better results than the proposed algorithm without clustering technique. Also, it is clear that the saving percentage of cost is high compared to these methods.

Fig-10. Convergence curves of the best solutions for each power system of the proposed algorithm at k=1, k=2 and k=3

Table-7. Comparison between proposed algorithm and other algorithms

Method
Objective  value (production cost $ )
10-unit
60-unit
564800
3371079
565825
3394066
564244
3367366
564769
3368257
565828
-
564950
3371178
566404
3378108
563977
3375065
564551
3371611
564094
3368375
Proposed algorithm at k=1
565690
3370500
Proposed algorithm at k=2
564280
3368400
Proposed algorithm at k=3
564230
3368100

 

Fig-11. The comparison between the proposed algorithm for each power system and other approaches

7. CONCLUSION

This paper provides a new algorithm to solve the NSUCPs. This new algorithm is called: GA based on K-mean clustering algorithm; where it integrates the main features of binary-real-coded GA and K-means clustering technique. The K-means clustering algorithm divided the population to a K of subpopulations. So, different GA operators can be applied to each one of subpopulations instead of one GA operators applied to the whole population. Two test systems are solved at different number of cluster and compared with the previous studies. Careful observations show the following benefits of this algorithm:

  1. It can obtain feasible and satisfactory solutions of NSUCPs.
  2. Incorporating GA with K-means clustering gave  diversity of solutions and helped the algorithm to avoid local minima
  3. Use of Binary-real-coded GA show that GA can tackle both scheduling of the unit and load dispatch problems.
  4. The result demonstrates that when the cluster number increased in the proposed algorithm, the production cost. 
  5. The tests demonstrated that the proposed approach has a satisfactory performance compared to previous studies.
Funding: This study received no specific financial support.
Competing Interests: The authors declare that they have no competing interests.
Contributors/Acknowledgement: All authors contributed equally to the conception and design of the study.

REFERENCES

[1]          A. J. Wood and B. F. Wollenberg, Power generation, operation and control. New York: John Wiley & Sons, 1996.

[2]          X. H. Guan, P. B. Luh, H. Yan, and J. A. Amalfi, "An optimization-based method for unit commitment," International Journal of Electrical Power & Energy Systems, vol. 14, pp. 9–17, 1992.View at Google Scholar | View at Publisher

[3]          Y. W. Jeong, J. B. Park, J. R. Shin, and K. Y. Lee, "A thermal unit commitment approach using an improved quantum evolutionary algorithm," Electric Power Components and Systems, vol. 37, pp. 770–786, 2009. View at Google Scholar | View at Publisher

[4]          N. P. Padhy, "Unit commitment-A bibliographical survey," IEEE Transactions on Power Systems, vol. 19, pp. 1196–1205, 2004. View at Google Scholar | View at Publisher

[5]          T. Senjyu, T. Miyagi, A. Y. Saber, N. Urasaki, and T. Funabashi, "Emerging solution of large-scale unit commitment problem by stochastic priority list," Electrical Power and Energy Systems, vol. 76, pp. 283–292, 2006.View at Google Scholar | View at Publisher

[6]          A. Rong, H. Hakonen, and R. Lahdelma, "A dynamic regrouping based sequential dynamic programming algorithm for unit commitment of combined heat and power systems," Energy Conversion and Management, vol. 50, pp. 1108–1115, 2009.View at Google Scholar | View at Publisher

[7]          C. L. Chen and S. C. Wang, "Branch-and-bound scheduling for thermal generating units," IEEE Trans. Energy Convers, vol. 8, pp. 184- 189, 1993. View at Google Scholar | View at Publisher

[8]          P. K. Singhal, "Generation scheduling methodology for thermal units using lagrangian relaxation," in Proc. 2nd IEEE Int. Conf. Current  Trends in Technology, 2011, pp. 1-6.

[9]          A. Frangioni, C. Gentile, and F. Lacalandra, "Tighter approximated MILP formulations for unit commitment problems," IEEE Transactions on Power Systems, vol. 24, pp. 105–113, 2009. View at Google Scholar | View at Publisher

[10]        G. B. Sheble and G. N. Fahd, "Unit commitment literature synopsis," IEEE Transactions on Power Systems, vol. 9, pp. 128–135, 1993. View at Google Scholar | View at Publisher

[11]        K. Swarup and P. Simi, "Neural computation using discrete and continuous Hopfield networks for power system economic dispatch and unit commitment," Neurocomputing, vol. 70, pp. 119–129, 2006. View at Google Scholar | View at Publisher

[12]        S. A. Kazarlis, A. G. Bakirtzis, and V. Petridis, "A genetic algorithm solution to the unit commitment problem," IEEE Transactions on Power Systems, vol. 11, pp. 29–36, 1996. View at Google Scholar | View at Publisher

[13]        M. A. El-Shorbagy, A. A. Mousa, and S. M. Nasr, "A chaos-based evolutionary algorithm for general nonlinear programming problems," Chaos, Solitons and Fractals, vol. 85, pp. 8–21, 2016. View at Google Scholar | View at Publisher

[14]        C. Dang and M. Li, "A floating-point genetic algorithm for solving the unit commitment problem," European Journal of Operational Research, vol. 181, pp. 1370-1395, 2007.View at Google Scholar | View at Publisher

[15]        W. F. Abd El-Wahed, A. A. Mousa, and M. A. El-Shorbagy, "Integrating particle swarm optimization with genetic algorithms for solving nonlinear optimization problems," Journal of Computational and Applied Mathematics, vol. 235, pp. 1446–1453, 2011. View at Google Scholar | View at Publisher

[16]        D. Datta, "Unit commitment problem with ramp rate constraint using a binary-real-coded genetic algorithm," Applied Soft Computing, vol. 13, pp. 3873–3883, 2013. View at Google Scholar | View at Publisher

[17]        K. A. Juste, H. Kita, E. Tanaka, and J. Hasegawa, "An evolutionary programming solution to the unit commitment problem," IEEE Transactions on Power Systems, vol. 14, pp. 1452-1459, 1999. View at Google Scholar | View at Publisher

[18]        N. Simopoulos, S. Kavatza, and C. Vournas, "Unit commitment by an enhanced simulated annealing algorithm," IEEE Transactions on Power Systems, vol. 21, pp. 68–76, 2006. View at Google Scholar | View at Publisher

[19]        A. H. Mantawy, Y. L. Abdel-Magid, and S. Z. Selim, "Integrating  genetic algorithms, tabu search, and simulated annealing for the unit commitment problem," IEEE Transactions on Power Systems, vol. 14, pp. 829 -836, 1999. View at Google Scholar | View at Publisher

[20]        J. Ebrahimi, S. H. Hosseinian, and G. B. Gharehpetian, "Unit commitment problem solution using shuffled frog leaping algorithm," IEEE Transactions on Power Systems, vol. 26, pp. 573 - 581, 2011. View at Google Scholar | View at Publisher

 [21]       A. A. Mousa, M. A. El-Shorbagy, and W. F. Abd El-Wahed, "Local search based hybrid particle swarm optimization for multiobjective optimization," International Journal of Swarm and Evolutionary Computation, vol. 3, pp. 1-14, 2012. View at Google Scholar | View at Publisher

[22]        A. H. Mantawy, Y. L. Abdel-Magid, and S. Z. Selim, "Unit commitment by Tabu search," IEE Proceedings-Generation, Transmission and Distribution, vol. 145, pp. 56–64, 1998.View at Google Scholar | View at Publisher

[23]        M. M. El-Saadawi, M. A. Tantawi, and E. Tawfik, "A fuzzy optimization-based approach to large scale thermal unit commitment," Electric Power Systems Research, vol. 72, pp. 245–252, 2004.View at Google Scholar | View at Publisher

[24]        Y. Pourjamal and S. N. Ravadanegh, "HSA based solution to the UC problem," International Journal of Electrical Power & Energy Systems, vol. 46, pp. 211-220, 2013. View at Google Scholar | View at Publisher

[25]        K. Chandrasekaran, S. Hemamalini, S. P. Simon, and N. P. Padhy, "Thermal unit commitment using binary/real coded artificial bee colony algorithm," Electric Power Systems Research, vol. 84, pp. 109-119, 2012. View at Google Scholar | View at Publisher

[26]        M. Sudhakaran1 and P. Ajay-D-Vimal Raj, "Integrating genetic algorithms and tabu search for unit commitment problem," International Journal of Engineering, Science and Technology, vol. 2, pp. 57-69, 2010. View at Google Scholar 

[27]        R. Nayak and J. Sharma, "A hybid neural network and simulated annealing approach to the unit commitment problem," Computers & Industrial Engineering, vol. 26, pp. 461-477, 2000. View at Google Scholar | View at Publisher

[28]        T. Sum-Im, "Lagrangian relaxation combined with differential evolution algorithm for unit commitment problem," Emerging Technology and Factory Automation (ETFA) IEEE, pp. 1–6, 2014.

[29]        C. C. A. Rajan and M. R. Mohan, "An evolutionary programming-based tabu search method for solving the unit commitment problem," IEEE Transactions on Power Systems, vol. 19, pp. 577–585, 2004.View at Google Scholar | View at Publisher

[30]        R. Todosijević, M. Mladenović, S. Hanafi, and I. Crévits, "VNS based heuristic for solving the unit commitment problem," Electronic Notes in Discrete Mathematics, vol. 39, pp. 153–160, 2012. View at Google Scholar | View at Publisher

[31]        V. N. Dieu and W. Ongsakul, "Enhanced merit order and augmented Lagrange Hopfield network for hydrothermal scheduling," Electrical Power and Energy Systems, vol. 30, pp. 93–101, 2008 View at Google Scholar | View at Publisher

[32]        P. K. Singhal, R. Naresh, and V. Sharma, "A novel strategy-based hybrid binary artificial bee colony algorithm for unit commitment problem," Arabian Journal for Science and Engineering, vol. 40, pp. 1455-1469, 2015.View at Google Scholar | View at Publisher

[33]        X. J. Zheng, "Optimal dispatching methods for unit commitment based on hybrid genetic-simulated annealing algorithm," Applied Mechanics and Materials, vol. 463, pp. 1076-1080, 2013.

[34]        Z. Michalewiz, Genetic algorithms+data structures=evolution programs, 3rd ed.: Springer-Verlag, 1996.

[35]        M. Verma, M. Srivastava, N. Chack, A. K. Diswar, and N. Gupta, "A comparative study of variou clustering algorithms in data mining," International Journal of Engineering Reserch and Applications (IJERA), vol. 2, pp. 1379-1384, 2012. View at Google Scholar 

[36]        S. Levine, I. Pilowski, and D. M. Boulton, "The classication of depression by numerical taxonomy," British Journal of Psychiatry, vol. 115, pp. 937-945, 1969.View at Google Scholar | View at Publisher

[37]        S. Dolnicar, "Using cluster analysis for market segmentation-typical misconceptions, established methodological weaknesses and some recommendations for improvemen, University of Wollongong Research Online," 2003.

[38]        F. R. Hodson, Numerical typology and prehistoric archaeology, In F.R. Hodson, D.G. Kendall, and P.A. Tautu, editors, Mathematics in the Archaeological and Historical Sciences. Edinburgh: University Press, 1971.

[39]        D. Pratima, N. Nimmakanti, and P. Recognition, "Algorithms for cluster identification problem," Special Issue of International Journal of Computer Science & Informatics (IJCSI), vol. 2, pp. 2231–5292, 2011.

[40]        K. S. H. Doreswamy, "Similarity based cluster analysis on engineering materials data sets," Advances in Intelligent Systems and Computing, vol. 167, pp. 161-168, 2012. View at Google Scholar | View at Publisher

[41]        D. Dilts, J. Khamalah, and A. Plotkin, "Using cluster analysis for medical resource decision making," Cluster Analysis for Resource Decisions, vol. 15, pp. 333-347, 1995. View at Google Scholar | View at Publisher

[42]        C. C. Aggarwal and C. K. Reddy, Data clustering algorithms and applications. New York (USA): CRC Press Taylor & Francis Group, 2014.

[43]        K. Arai and X. Q. Bu, "ISODATA clustering with parameter (Threshold for Merge and Split) estimation based on GA: Genetic algorithm," Reports of the Faculty of Science and Engineering, vol. 36, pp. 17-23, 2007.View at Google Scholar 

[44]        R. T. Ng and J. Han, "CLARANS: A method for clustering objects for spatial data mining," IEEE Transactions Knowledge Data Engineering, vol. 14, pp. 1003–1016, 2002. View at Google Scholar 

[45]        D. Judd, P. K. McKinley, and A. K. Jain, "Large-scale parallel data clustering," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, pp. 871-876, 1998. View at Google Scholar 

[46]        D. R. Edlaa and P. K. Janaa, "A prototype-based modified DBSCAN for gene clustering," Procedia Technology, vol. 6, pp. 485–492, 2012.View at Google Scholar | View at Publisher

[47]        Y. Rani, Manju, and H. Rohil, "Comparative analysis of BIRCH and CURE hierarchical clustering algorithm using WEKA 3.6.9," SIJ Transactions on Computer Science Engineering & its Applications (CSEA), vol. 2, pp. 25-29, 2014. View at Google Scholar 

[48]        J. B. MacQueen, "Some methods for classification and analysis of multivariate observation," in Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1967, pp. 281-297.

[49]        R. P. Priya, N. Sivaraj, and M. Muruganandam, "A solution to unit commitment problem with V2G using harmony search algorithm," International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering, vol. 4, pp. 1208-1214, 2015. View at Google Scholar | View at Publisher

[50]        D. E. Goldberg, Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison Wesley, 1989.

[51]        J. J. Grefenstette, "Optimization of control parameters for genetic algorithms," IEEE Trans. Syst. Man Cybern., vol. 16, pp. 122–128, 1986. View at Google Scholar | View at Publisher

[52]        M. Sakthi and A. S. Thanamani, "An effective determination of initial centroids in K-means clustering using kernel PCA," International Journal of Computer Science and Information Technologies, vol. 2, pp. 955-959, 2011. View at Google Scholar 

[53]        A. Jain, "Data clustering: 50 years beyond k-means," Pattern Recognition Letters, vol. 31, pp. 651–666, 2010. View at Google Scholar | View at Publisher

[54]        A. Kumar and N. N. Jani, "Network design problem using genetic algorithm- an empirical study on selection operator," International Journal of Computer Science and Applications (IJCSA), vol. 3, pp. 48-52, 2010. View at Google Scholar 

[55]        W. Xing and F. F. Wu, "Genetic algorithm based unit commitment with energy contracts," International Journal of Electrical Power & Energy Systems, vol. 24, pp. 329-336, 2002.View at Google Scholar | View at Publisher

[56]        M. Gen, R. Cheng, and L. Lin, Network models and optimization: Multi-objective genetic algorithm approach: Springer Science & Business Media, 2008.

[57]        Y. W. Jeong, W. N. Lee, H. H. Kim, J. B. Park, and J. R. Shin, "Thermal unit commitment using binary differential evolution," Journal of Electrical Engineering & Technology, vol. 4, pp. 323–329, 2009. View at Google Scholar | View at Publisher

[58]        A. S. Uyar, B. Türkay, and A. Keles, "A novel differential evolution application to shortterm electrical power generation scheduling," Electrical Power and Energy Systems, vol. 33, pp. 1236–1242, 2011.View at Google Scholar | View at Publisher

[59]        X. Yuan, A. Su, H. Nie, Y. Yuan, and L. Wang, "Application of enhanced discrete Differentia evolution approach to unit commitment problem," Energy Conversion & Management, vol. 50, pp. 2449–2456, 2009. View at Google Scholar | View at Publisher

[60]        R. N. Mohd and J. Geraghty, "Genetic algorithm performance with different selection strategies in solving TSP," in Proceedings of the World Congress on Engineering II, 2011.

[61]        R. Sivaraj and T. Ravichandran, "A review of selection methods in genetic algorithm," International Journal of Engineering Science and Technology, vol. 3, pp. 3792-3797, 2011. View at Google Scholar 

[62]        G.-H. Tzeng and J.-J. Huang, Fuzzy multiple objective decision making: Chapman and Hall/CRC Press, 2013.

[63]        C. A. Anderson, K. F. Jones, and J. Ryan, "A two-dimensional genetic algorithm for the ising problem," Complex Systems, vol. 5, pp. 327- 333, 1991. View at Google Scholar 

[64]        C.-P. Cheng and C. W. Liu, "Unit commitment by annealing genetic algorithm," International Journal Electrical Power & Energy Systems, vol. 24, pp. 149–158, 2002.View at Google Scholar | View at Publisher

[65]        L. Sun, Y. Zhang, and C. Jiang, "A matrix real-coded genetic algorithm to the unit commitment problem," Electric Power Systems Research, vol. 76, pp. 716–728, 2006. View at Google Scholar | View at Publisher

[66]        T. Senjyu, H. Yamashiro, K. Uezato, and T. Funabashi, "A unit commitment problem by using genetic algorithm based on unit characteristic classification," IEEE Power Engineering Society Winter Meeting, vol. 1, pp. 58 - 63, 2002.

[67]        S. Kumar and R. Naresh, "Efficient real coded genetic algorithm to solve the non-convex hydrothermal scheduling problem," Electrical Power and Energy Systems, vol. 29, pp. 738–747, 2007.View at Google Scholar | View at Publisher

[68]        C.-P. Cheng, C.-W. Liu, and C.-C. Liu, "Unit commitment by Lagrangian relaxation and genetic algorithms," IEEE Transactions on Power Systems, vol. 15, pp. 707–714, 2000. View at Google Scholar | View at Publisher

[69]        I. Damousis, A. Bakirtzis, and P. Dokopoulos, "A solution to the unit-commitment problem using integer-coded genetic algorithm," IEEE Transactions on Power Systems, vol. 19, pp. 1165–72, 2004. View at Google Scholar | View at Publisher