J. Cent. South Univ. Technol. (2007)01-0144-05

DOI: 10.1007/s11771-007-0029-9               

Energy transmission modes based on Tabu search and particle swarm hybrid optimization algorithm

LI Xiang(李 翔)¹, CUI Ji-feng(崔吉峰)^1,2, QI Jian-xun(乞建勋)¹, YANG Shang-dong(杨尚东)¹

 (1. School of Business Administration, North China Electric University, Beijing 102206, China;

2. State Grid Operation Company Limited, Beijing 100005, China)

Key words:

ultra high voltage(UHV); economical efficiency; Tabu search; particle swarm optimization；

Technical economics comparison between coal transmission and power transmission is a new issue caused by serious imbalance among China’s regional economic developments^[1-2]. Three different comparison methods were proposed during different periods in China, i.e., annual cost comparison, freight rates comparison, and regional price difference analysis^[3-4]. There are mainly following shortcomings among them: 

1) The comparison is based on comparable prices, but the prices deviate from the true values of the resources.

2) These methods all consider very limited factors.

3) The optimizing algorithms applied need to be improved in the aspects of computing efficiency and precision^[5].

An optimizing model was proposed in order to improve efficiency of unit energy, by which the divisor critical value of the economical efficiency comparison between power transmission and coal transmission and the result of optimal allocation of two transmission patterns’ were obtained. As there is a combinatorial optimizing problem with multiple objectives and multiple constraints, the hybrid optimizing algorithm was proposed to increase the efficiency of the model, which is based on mixing Tabu search and particle swarm optimization. The effectiveness of this method proposed in this paper is tested by empirical analysis of the technical and economical comparison between coal transmission and power transmission.

2 Combinatorial optimization model of energy transmission mode

By comparing the economic efficiencies of long-distance coal transfer with the long-distance ultra-high voltage(UHV) transmission efficiency^[5], the energy transfer mode selecting model can be established. However, when considering the minimum cost based on comparable price, some problems occur, because neither China’s electric power price nor coal price are entirely formed under the market. Thus, the price can hardly reflect the real value of the resources. Besides, social outputs of the different energy transfer modes should be considered when comparing the efficiencies of different energy transfer modes. Therefore, an optimizing model, which is from the view of maximum social output per unit of energy with the comparison of different energy transfer modes, was established. In this way, the critical points of their efficiency comparison can be obtained. 

The following three aspects under different transfer modes need to be considered in the new model: First, different social outputs brought by different unit-heating coals under different coal transfer modes; second, the unit heat transmission cost of coal with different ways of heat; third, unit heat used heat’s environmental cost of coal with different ways of heat. In order to maximize P-T_C-C, the following mathematical model can be obtained.

               (1)

         (2)

         (3)

           (4)

              (5)

            (6)

where i∈(1, n) is the types of coals with different heat qualities; i∈(1, m) is the different modes of transfer; r_i is unit heating of coal type i ; w_ij is coal type ith quality in  transfer mode j; p_ij is coal type ith unit heating output in transfer mode j; t_cij is coal type ith unit distance cost in transfer mode j; l_ij is coal type ith freight fare in transfer mode j; c_ij is coal type ith unit heating main pollution’s environmental cost in transfer mode j; s_i is coal type ith pollution level when burning unit heating; U_ft is the available transportation capacity constraint; U_cj is the corresponding environmental capacity limitation in transfer mode j; R is the total heat quantity produced by transferred coals.

3 Optimization hybrid algorithm by Tabu search and particle swarm

3.1 Simple particle swarm optimization(PSO)

PSO stemmed from the research on the prey behavior of a swarm of bird^[6]. In PSO, each solution to the optimized aspect can be treated as a bird, called a particle. Every particle has its fitness value determined by the optimized function and its velocity which will determine its flight course and distance. Particles will follow the optimized one and search among the random particles initialized by PSO in solutions space. And the best solution can be achieved by iteration. The particle updates itself by following two extreme values in each time’s iteration. One extreme value named PBest is the best solution obtained by the particle itself. The other named gBest is the best solution found by the whole swarm at the present. Alternatively, the whole swarm can be substituted by some particles around the best one and the extreme value of the neighboring particles is called partial value^[7]. Before finding these two optimized values, a particle updates its velocity and location according to the following formulae:

X_i(k+1)=X_i(k)+V_i(k+1)Δt            (7)

        (8)

where  X_i is the position of the particle i; v_i represents the velocity of the particle i, v_i∈(v_min, v_max); v_min and v_max are constants in the range of [0, 1]; P_i is the best previous position of particle i; N is the size of population; k is the current step number; w is the internal weight coefficient (i.e. the impact of the previous velocity of particle on its current one); c₁ and c₂ are acceleration constants; r₁ and r₂ are random real numbers in the range of [0, 1]. When the given maximum iteration frequency or fitness value meets the requirement to realize the given value, the calculation is terminated.

3.2 Improved particle swarm optimization(IPSO) with adaptive interior

In PSO, proper control of global exploration and local exploitation is crucial in finding the optimum solution efficiently^[8]. Obviously, the performance of PSO greatly depends on its parameters. It is clear that the first part of Eqn.(2) represents the influence of previous velocity, which provides the necessary momentum for particles to across the search space. The inertia weight w is the modulus that controls the impact of previous velocity on the current one. So, the balance between exploration and exploitation in PSO is dictated by the value of w. Thus proper control of the inertia weight is very important to find the optimum solution accurately and efficiently. It is regarded that a larger inertia weight pressure towards global exploration, while a smaller inertia weight pressure towards fine-tuning of the current search area. Thus, SHI and EBERHART made a significant improvement in the performance of the PSO with a linearly varying inertia weight over the generations, which linearly varies from 0.9 at the beginning of the search to 0.4 at the end. To achieve trade-off between exploration and exploitation, w was set adaptively in response to the objective values of the particles. In particular, the adaptive inertia weight factor (AIWF) is determined as follows.

     (9)      

where w_max and w_min denote the maximum and minimum of w, respectively; f is the current objective value of the particle; f_max and f_min are the average and minimum objective values of all particles, respectively. It can be seen from Eqn.(10) that w varies depending on the objective value of the particle, so that particles with low objective values can be protected while particles with objective values over average will be disrupted. That is, good particles tend to perform exploitation to refine results by local search, while bad particles tend to perform large modification to explore space with large step. In other words, AIWF provides a good way to maintain population diversity and to sustain good convergence capacity.

3.3 Tabu search

Tabu search^[9], like other meta-heuristic approaches, is based on the local search paradigm. Starting from a given initial solution S₀ (e.g., found by a constructive heuristic algorithm), at each iteration t, the method moves from solution S_t-1 to the best solution in its neighborhood N(S_t-1) (i.e. the set of solutions obtained from S_t-1 by applying all the possible moves), even if this causes a deterioration in the objective function value (in order to escape from the local optimum). To avoid cycling, some solutions of the neighborhood are declared forbidden, or Tabu, for a given number of iterations. The search stops whenever a given stopping rule is satisfied. The method can be enhanced by incorporating several features to allow the intensification and diversification of the search process.

Typically, Tabu solutions are declared by forbidding some of the possible moves for a certain number of iterations, and the concept of memory, which records the search process history, is used. Commonly, the most used type of memory is the recency-based one. The more detailed information about it can be referred in Refs.[10-11].

3.4 Tabu search and particle swarm hybrid optimi-

zation algorithm

The proposed algorithm is based on the excellence of both the Tabu search and the particle swarm optimization. The new hybrid algorithm can be defined in two stages. In the first stage, it was mainly based on the sacrifice and memory property of the particle swarm optimization to make global explore. In the second stage, the Tabu search was applied in finding the better particle around the global best particle for its efficiencies in scanning.

   The structure of the proposed Tabu-IPSO hybrid algorithm is shown in Fig.1. In Fig.1 the proposed algorithm will terminate when the setting maximal iteration times achieve expected one. Here the maximal iteration times is set 2 000.

Fig.1 Structure of proposed Tabu-IPSO hybrid algorithm

4 Tabu search and particle swarm optimi- zation hybrid algorithm applied to optimal solution on mixed energy transmission modes

Each particle in particle swarm is defined as some transmission plan. Under constraint condition, the penalty function is introduced to form a new fitness function. For the particles do not satisfy the solution of constraint condition, the penalty factor in fitness function is depended by the violation degree from the restraint constraints. The key parameters are c₁=1, c₂=1, while the size of particle swarm scale is i×j, and w changes according to Eqn.(10).

After initialization of particle swarm position, the computation is carried on according to the steps of Tabu search and particle swarm mixed optimization algorithm. In each iterative, overall situation search is done in particle swarm, then the near territory of excellent particle can be searched, and its partial and the overall situation fitness value can be calculated. Eqn.(8) is used to carry on the renewal in particle swarm’s speed vector. In renewal particle speed foundation, Eqn.(9) is used to carry on particle position renewal in a particle swarm.

Regarding the design of appraisal function of particle fitness design, considering fitness computation of each plan, the fitness appraisal function designed is based on penalty function principle. For the appearance of non-feasible solution, penalty factor is introduced, which can cause large different fitness values gap between the un-feasible solution and the feasible solution, and it may reduce the probability of non-feasible solution’s appearance in the following optimized advancement, and enhances the operation efficiency. Penalty factors l₁，l₂ and l₃ are set corresponding to three constraint conditions in the proposed model which are respectively environmental protection constraint,  transport capacity constraint and overall transmission thermal constraint. The overall fitness appraisal function may be expressed as follows:

F_Ci=[F_i-l₁Σψ₁-l₂Σψ₂-l₃Σψ₃]       (10)

where F_Ci is fitness value of ith particle; F_i is the corresponding goal function value of ith particle; Σψ₁, Σψ₂ and Σψ₃ are violation degree to three restraints.

Finally, when calculation moves to the ending condition set, the energy transmission plan correspond- ing to most superior particle can be obtained.

5 Examples analysis

Taking coal and electric transmission model comparison between Shanxi province and East-Mongolia coal base to Yangtze River Delta area for example. The main indexes gathered are coal caloric index, transport capacity constraint, the authorization rate of wagon,  transportation distance, environmental capacity, and emissions standard, and those are converted the output of unit energy consumption in target area to economic efficiency of the heat unit. Tabu search and particle swarm hybrid optimization algorithm is applied to find the solution. Finally, the economic critical value can be obtained after comparing the long-distance coal transfer mode with the extra-high voltage electric power transmission mode. The result can be seen from Fig.2.

Fig.2 Economy crisis curve of different energy transmission modes

From Fig.2, it can be seen that with the energy(or heat output) of coal increase, the economy superiority appears. Area I of Fig.2 means that the direct coal transmission mode is better choice, while, area II of the curve means that the mode of transmission of electric power should be a right one.

Based on the same sample environment, comparing the transfer efficiency of the proposed model with the traditional three models, the results are listed in Table 1.

From Table 1, it can be seen that the proposed model optimized by Tabu-IPSO hybrid algorithm gains more properly result with low computing time cost, which means the proposed method has the better effect.   

During 2000 iterations, the fitness of the global best particle is shown in Fig.3. It can be seen that the fitness curve is smooth, which means the proper balance between the global search ability and local search ability of the particle swarm.

Table1 Energy transfer efficiencies among different plans gained by different models

Fig.3 Fitness curve of iterations of Tabu-PSO hybrid algorithm

1) Based on the comparable economical efficiency of unit heat, optimal allocation model of the energy transmission modes is established, which can be used to avoid the impact of price signal distortion based on the comparable price differences.

2) The Tabu search and particle swarm hybrid optimization algorithm is proposed to compute and analyze China’s two main energy transfer modes, which namely long-distance coal transfer and ultra-high voltage electric power transmission. The economic critical value of the two modes are found out with comparisons.

3) Based on the result analysis, the Pareto improve- ment for sole transmission mode is obtained. The coal with high heat should be transmitted into the electric power and then be sent to energy demand centers by long-distance ultra-high voltage power transmission.

4) The selection of the energy transmission modes are also affected by many social factors, such as employment and economic structure optimization. Integrated surveying and further quantitative analysis of these influences are to be analysed further.

References

[1] ZHAO Hao, YU Yu-hong. Discussion on several important problems of development UHV AC transmission in China[J]. Power System Technology, 2005, 29(12): 1-9.(in Chinese)

[2] GU Ding-xie. The prospect of developing UHV transmission system in China[J]. High Voltage Engineering, 2002, 28(3): 28-32.(in Chinese)

[3] LU Chong-hui, WAN Qi-fa, GU Ding-xie, et al. The 1 000 kV UHV transmission technology in Japan[J]. High Voltage Engineering, 1998, 24(2): 47-49.(in Chinese)

[4] SCHERER H N, VASSELL G S. Transmission of electric power at ultra-high voltages: Current status and future prospects[J]. Proceedings of the IEEE, 1985, 73(8): 1252-1278.

[5] DING Wei, HU Zhao-guang. The research on the economy comparison of ultra high voltage[J]. Power System Technology, 2006, 30(11): 6-11.

[6] KENNEDY J, EBERHART R C. A discrete binary version particle swarm algorithm[C]// Proceedings of IEEE International Conference on System, Man, and Cybernetics. Orlando, 1997: 4104-4109.

[7] CLERC M, KENNEDY J. The particle swarm-explosion stability, and convergence in a multidimensional complex space[J]. IEEE Trans Evolut Comput, 2002, 6(1): 58-73.

[8] CHATTERJEE A, SIARRY P. Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization[J]. Computers and Operations Research, 2006, 33(3): 859-871.

[9] CHOOBINEH F F, MOHEBBI E, KHOO H. A multi-objective tabu search for a single-machine scheduling problem with sequence- dependent setup times[J]. International Journal of Production Economics, 2006, 103(2): 742-754.

[10] OSMAN I H. A tabu search procedure based on a random roulette diversification for the weighted maximal planar graph problem[J]. Computers and Operations Research, 2006, 33(9): 2526-2546.

[11] BELFARES L, KLIBI W, GUITOUNI N L O. Multi-objectives tabu search based algorithm for progressive resource allocation[J]. European Journal of Operational Research, 2006, 11(10): 1779–1799.

(Edited by CHEN Can-hua)

Foundation item: Project(20050079008) supported by the Specialized Research Fund for the Doctoral Program of Higher Education

Received date: 2006-10-12; Accepted date: 2006-11-22

Corresponding author: LI Xiang, Professor, PhD;Tel:+86-10-80793382;E-mail: cbjlx@126.com