[3],. [4]. [5],. [6],. [7].., ;,..,,.,,, [8]. 2 (Description of magnetism materials group furnace problem) 2.1 (Definition of group furnace),

Size: px

Start display at page:

Download "[3],. [4]. [5],. [6],. [7].., ;,..,,.,,, [8]. 2 (Description of magnetism materials group furnace problem) 2.1 (Definition of group furnace),"

耶炀乌雅
5 years ago
Views:

1 DOI: /CTA Control Theory & Applications Vol. 31 No. 9 Sep. 2014,, (, ) :,.,..,. 1 N,., ;,.,,. : ; ; ; ; : TP18 : A Application of improved genetic algorithm to magnetic materials group furnace optimization problem LIU Ye-feng, PAN Quan-ke, CHAI Tian-you (State Key Laboratory of Integrated Automation for Process Industries, Northeastern University, Shenyang Liaoning , China) Abstract: Grade, due date, priority, and demand are attributes of magnetic material production work orders. Planners are required to seek the optimal combination of production work orders to minimize the cost and improve the efficiency based on these attributes. To deal with the lengthy furnace-grouping time and the non-optimal furnace-grouping result in magnetic materials enterprises, we build a mathematical model for solving the furnace-grouping optimization problem with unknown charge number. This problem is first transformed into a pseudo traveling salesman problem and then is solved by using an improved genetic algorithm. Natural number coding from 1 to N is the coding scheme that this paper adopted. An initial population generation method is designed following the sort criteria of Earliest Completion Date (ECD). An elite strategy and an improved greedy three-crossover operator (3PM) are introduced to enhance the convergence speed and precision, whereas a reverse operator is applied to improve the exploitation for the presented algorithm. Simulation results based on practical production data show that the built model is appropriate and the proposed algorithm is effective. Key words: furnace-grouping; genetic algorithm; reverse operator; traveling salesman problem; magnetic materials 1 (Introduction) ( ),,.,.,,.,..,..,,,.,. [1],,. [2], : ; : lyf-327@163.com; Tel.: : ( , ); (NCET ); ( ); ( ); (N , N ); ( ); (2013ZCX02).

2 [3],. [4]. [5],. [6],. [7].., ;,..,,.,,, [8]. 2 (Description of magnetism materials group furnace problem) 2.1 (Definition of group furnace), ( ),,,. 2.2 (Description of artificial group furnace process),, :. 1.,.,, ,,,,. 3.,,,,,. 1 Fig. 1 Schematic diagram of artificial group furnace process 2.3 (Existing problems of artificial group furnace process) Excel,., : 1),.,,,. 100, 20, 2 20,,. 2),

3 9 : 1223.,.,.,. 3,.,.,.,,,.,.,,,. 3 (Group furnace optimization model and algorithm of magnetism materials) 3.1 (Mathematical model), (pseudo traveling salesman problem, PTSP),. 1). 1, M max = 580 kg. N ; i, j i j, : i, j {1, 2,, N}; w i i (kg); g i i ; p i i ; k F W (k). d i i, d i {1, 2,, 7}; A i i, A i {1, 2,, 5}. 2). : W i (k) i k, k = 1, 2,, K, K. 3). a)...., : min f 1 = K k=1 i=1 k W i(k)d i F W (k). (1) (1) k,..,., : max f 1 = K W i (k)a i k F W (k). (2) k=1 i=1 (2) k,. min f 1 = F 1 f F 2 = F 1 k=1 i=1 f 1 k W i(k)d i F W (k) +F 2 k=1 i=1 1 W i (k)a i k F W (k). (3) b) ( )., C 3 ij : M, p i p j, Cij 3 = g i g j, p i = p j g i g j, (4) 0, g i = g j, : p i, p j i j, p i {1, 2,, 7}, p j {1, 2,, 7}. p i p j, i j,,, M =1000. p i =p j, g i g j, i j, g i g j, g i g j {1, 2, 3,, 10}; g i = g j,, 0. min f 2 = K C 3 ij X i (k)x j (k). (5) k=1 j=1 i=1 c).,, ;,.,. K, K: min f 3 = K, (6), 3. : { { 1, Wi (k)>0, 1, X i (k)= 0, W i (k)=0, X Wj (k)>0, j(k)= 0, W j (k)=0, N = 40, K [18, 45].

4 ). Z(k) = 580 N W i (k)x i (k). (10) i=1 {. 1, Wi (k) > 0, (10), X p i, p j i j i (k) =, k = 1, 2,, 0, W i (k) = 0,, p i {1, 2,, 7}, p j {1, 2,, 7}, i j k, K, W i (k) i k,.. p i X i (k) = p j X j (k) (7) : { { 1, Wi (k)>0, 1, X i (k)= 0, W i (k)=0, X Wj (k)>0, j(k)= 0, W j (k)=0, W i (k), W j (k) i j k,..,. w i i ; W i (k) i k ; i k, W i (k)x i (k) 0, k : W i (k)x i (k), k=1 w i, W i (k)x i (k) = w i, i = 1,, N. (8) k=1 : { { 1, Wi (k)>0, 1, X i (k)= 0, W i (k)=0, X Wj (k)>0, j(k)= 0, W j (k)=0, N = 40, K [18, 45]..,. W i (k) i k ; i k, W i (k)x i (k) 0. k, IW (k) : IW (k) = N W i (k)x i (k). (9) i=1 (9) : { 1, Wi (k) > 0, X i (k) = 0, W i (k) = 0, { 1, Wj (k) > 0, X j (k) = 0, W j (k) = 0, N = 40. k IW (k)+ k Z(k) 580 kg, :, : min f 1 = F 1 f F 2 = F 1 k=1 i=1 min f 2 = K f 1 k W i(k)d i F W (k) + F 2 k=1 j=1 i=1 1, W i (k)a i k=1 i=1 k F W (k) (11) C 3 ij X i (k)x j (k), (12) min f 3 = K, (13) s.t. p i X i (k) = p j X j (k), (14) W i (k)x i (k) = w i, i = 1, 2, N, (15) k=1 W i (k)x i (k) + Z(k) = 580, (16) i=1 { 1, Wi (k) > 0, X i (k) = 0, W i (k) = 0, { 1, Wj (k) > 0, X j (k) = (17) 0, W j (k) = 0, k = 1, 2,, K, i = 1, 2,, N, j =1, 2,, N, N =40, K [18, 45]. : (11) ; (12) ( ) ; (13) K; (14) ; (15) ; (16) ; (17). 3.2 (PTSP model of group furnace optimization of magnetism materials integrated production), (traveling salesman problem, TSP) NP hard, :,,,. TSP

5 9 : 1225,,,, TSP, (PTSP). 2 8 PTSP.., : , 1 3, 3 1, 3 1 ;, 4 1 3, 4 1 3, 4 1., 4 1 3, 4 1 3, ( 1), 4, 2., 1 2,,. 3 1, 3, 4, 9, 2, 8 2, 5, 6, Fig. 2 Schematic diagram of group furnace 3 Fig. 3 Chromosome coding, k n, T W k (18) : T W k = n W ik X ik, i = 1, 2,, n. (18) i=1, (n + 1), T W k + W (n+1)k + Z Gp (k) M max, (19), (n + 1) ;, n. (n + 1). 3.3 (Improved genetic algorithm) (genetic algorithm) (, ). J. Holland 1975.,, [9 10, 12],., [11].,,,.,,, 3PM,,,,. 1). 1 N. 1 N, ,,, TSP, (PTSP).,,,.,., 3 12 : ( ),,. 2).,..,.,,.,., (earliest complete date, ECD), ECD :,

6 ,,. 4, , ; ; ,, , 2 9,3,8, 3 7,10, 3. 4 ECD Fig. 4 Sample of the initial population generation based on the ECD rules ECD,,. 3).,, ( ), ( ),., 3.,,, (20) : min Z = αz 1 + βz 2 + γz 3, (20) : α, β, λ, Z 1, Z 2, Z 3, [0.1, 0.9]. Z 1 = (Z 1 min) ( ), (21) (max min) Z 2 = (Z 2 min) ( ), (22) (max min) Z 3 = (Z 3 min) p ( ), (23) (max min) min, max. (21) (23) min max; min = max,,, (21) (23) (max min) ε, 3 0,, Z 1, Z 2, Z (20) 3 : 1 ; 2 ( ) ; 3. (20) f = Value Z, (24) Value. 4) 3PM.,,. 2PM, 2 1, 2,,. 1, 3PM. 2PM,, 3 1,,,., : 3 ; 1, 4, 1 4;, 3 1 ; fitness(a, b) a b, fitness(a, b 1 ), fitness(a, b 2 ), fitness(a, b 3 ), b 1, b 2, b 3 3 a,, fitness(a, b 3 ), b 3, 1,, n 1, Fig. 5 The first place that randomly produced by three parents 6 1 Fig. 6 The result of first right rotation

7 9 : n 1 Fig. 7 A new offspring produced by n 1 times right rotation : 3 ;, 5, 5;, 3 ; fitness(b, a) b a, fitness(b 1, a), fitness(b 2, a), fitness(b 3, a) b, fitness(b 2, 5), b 2, 1,, n 1,., 3, 3,,,. 5).,.,,.,. (improved genetic algorithm, IGA).,,. : 8, 1 2 5; 2 4 9; Fig. 8 Random generation two variation positions in every father generation among three father generations 9 3 Fig. 9 Variation results of three father generations 6).,,,,., , 2 3, 6 7, , 12, 6543, 789 ( ),,,.,. 7). 3PM,, Pop Size. Pop Size- Pop Size,.,. Pop Size, Pop Size. 3.4 (Algorithm flow chart) : 1 ( ). t 0 ; T ; M P (t); 2 ( ). (27), P (t) ; 3. t >= T,.., t t + 1 4; 4 (, ); 5 ( ). 3, 3PM ; 6 ( )., ; 7 ( )., ; 8., ;

8 Fig. 10 Flow chart of improved GA 1 Table 1 Information of production orders 4 (Practical data operation and analysis) / 20/40, MATLAB. P c P m [12]., 2, P c >0.8 P m < 0.1, ; P c < 0.8 P m > 0.1,, P c = 0.8, P m = 0.1; : N, 10/20/40, 100, 5000, GGAP = 0.9., F 1 F 2 ; 3 : 3 α, β λ. 3, 3,., 20, ( 3), 3 α=β =λ=1; Value=1000. /kg (1 ) (1 ) /kg /kg EH EH H SH SH SH SH UH UH P c, P m Table 2 The selection of crossover probability P c and mutation probability P m (P c, P m) (10) (20) (40) /s /s /s (0.8, 0.05) (0.8, 0.2) (0.7, 0.1) (0.9, 0.1) (0.8, 0.1)

9 9 : (α, β, γ) Table 3 The selection of weighting coefficient (α, β, γ) (10) (20) (40) (1, 1, 1) (1, 10, 1) (10, 1, 100) (100, 1, 1) (10, 10, 1) PM, /20/ , 10/ 20/40, 20, 5000, , 3PM,, 1926, ;,, 2213,, 3PM, 1829,,. 5 [1], [2] +, 20, ,, [1] [2]. 4 3 Table 4 Contrast of three genetic algorithms 3PM /s /s /s

10 , 3.25/ /1.3, 2 6, 0.05/0.9 6.,,,, Fig. 11 Three GAs iteration curve of group furnace optimization 5 [1 2] Table 5 Algorithms contrast of this paper s improved GA with reference[1 2] [1] Z 1 Z 2 Z 3 /s [2] Z 1 Z 2 Z 3 /s Z 1 Z 2 Z 3 /s ,.,, , 4 15, 1, 1, kg/ kg 543 kg/ kg, 90.17%/62.20% 93.62%/82.20%, 63.10% 73.61%,, 580 kg. 6 Table 6 Group furnace results comparison of improved genetic algorithm and artificial /kg /% /% 1 2, 5, 1, , 7, , 11, , 8, 15, 16, , , /kg /% /% 1 2, 5, 15, 1, , 7, , 11, , 8, 12, 16, 14, , (Conclusions),,., 3PM ;,.,,. (References): [1],,,. [J]., 2004, 21(6):

11 9 : 1231 (WANG Xiaodong, JIN Jiling, LIU Quanli, et al. Improved genetic algorithm and its application in optimal combination stacks of steel roll [J]. Control Theory and Applications, 2004, 21(6): ) [2],,. [J]., 2009, 38(2): (LIU Ying, LIU Quanli, WANG Wei. Optimizing model and algorithm for combination stacking of bell-type batch annealing [J]. Infromation and Control, 2009, 38(2): ) [3],,. [J]., 2007, 24(2): (NING Shushi, WANG Wei, PAN Xuejun. Integrated method of steelmaking and continuous casting planning [J]. Control Theory & Applications, 2007, 24(2): ) [4],,. [J]., 2011, 17(7): (XUE Yuncan, ZHENG Dongliang, YANG Qiwen. Optimum charge plan of steelmaking continuous casting based on the modified discrete particle swarm optimization algorithm [J]. Computer Integrated Manufacturing Systems, 2011, 17(7): ) [5],,. [J]., 2010, 27(4): (WANG Wanlei, YANG Jingping, FU Hongguang. Optimization of charge design with quality constraints based on particle swarm optimization [J]. Control Theory & Applications, 2010, 27(4): ) [6] FALKENAUER E. A new representation and operators for genetic algorithms applied to grouping problems [J]. Evolutionary Computation, 1994, 2(2): [7],,. [J]., 2010, 17(2): (WANG Zhigang, LIU Quanli, WANG Wei. Improved modelling and optmial algorithm for combination stacking [J]. Control Engineering, 2010, 17(2): ) [8],. TSP [J]., 2010, 46(5): (WANG Yinnian, GE Hongwei. Improved simulated annealing genetic algorithm for solving TSP problem [J]. Computer Engineering and Applications, 2010, 46(5); ) [9] SRINIVAS M, PATNAIK L M. Genetic algorithms: a survey [J]. Computer, 1994, 27(6): [10] BROWN E, SUMICHRAST R. Impact of the replacement heuristic in a grouping genetic algorithm [J]. Computers and Operations Research, 2003, 30(11): [11],,. [J]., 2011, 28(5): (YANG Kun, OUYANG Guangyao, CHEN Hailong. Optimization of unit commitment of marine power system using improved genetic algorithm [J]. Control Theory & Applications, 2011, 28(5): ) [12] SRINIVAS M, PATNAIK L M. Adaptive probabilities of crossover and mutation in genetic algorithms [J]. IEEE Transaction on Systems, Man and Cybernetics, 1994, 24(4): : (1981 ),,,, lyf-327@163.com; (1971 ),,,,, panquanke@gmail.com; (1947 ),,,,,, tychai@mail.neu.edu.cn.

2 3. 1,,,.,., CAD,,,. : 1) :, 1,,. ; 2) :,, ; 3) :,; 4) : Fig. 1 Flowchart of generation and application of 3D2digital2building 2 :.. 3 : 1) :,

2 3. 1,,,.,., CAD,,,. : 1) :, 1,,. ; 2) :,, ; 3) :,; 4) : Fig. 1 Flowchart of generation and application of 3D2digital2building 2 :.. 3 : 1) :, 3 1 Vol. 3. 1 2008 2 CAA I Transactions on Intelligent Systems Feb. 2008, (,210093) :.,; 3., 3. :; ; ; ; : TP391 :A :167324785 (2008) 0120001208 A system f or automatic generation of 3D building models