2003/9 Vol. J86 D I No. 9 GA GA [8] [10] GA GA GA SGA GA SGA2 SA TS GA C1: C2: C3: 1 C4: C5: 692

Similar documents
2007/8 Vol. J90 D No. 8 Stauffer [7] 2 2 I 1 I 2 2 (I 1(x),I 2(x)) 2 [13] I 2 = CI 1 (C >0) (I 1,I 2) (I 1,I 2) Field Monitoring Server


発達心理学研究 第24巻 第3号

258 5) GPS 1 GPS 6) GPS DP 7) 8) 10) GPS GPS ) GPS Global Positioning System

○広島大学船員就業規則

MDD PBL ET 9) 2) ET ET 2.2 2), 1 2 5) MDD PBL PBL MDD MDD MDD 10) MDD Executable UML 11) Executable UML MDD Executable UML

A Feasibility Study of Direct-Mapping-Type Parallel Processing Method to Solve Linear Equations in Load Flow Calculations Hiroaki Inayoshi, Non-member

2. CABAC CABAC CABAC 1 1 CABAC Figure 1 Overview of CABAC 2 DCT 2 0/ /1 CABAC [3] 3. 2 値化部 コンテキスト計算部 2 値算術符号化部 CABAC CABAC

(a) (b) (c) Canny (d) 1 ( x α, y α ) 3 (x α, y α ) (a) A 2 + B 2 + C 2 + D 2 + E 2 + F 2 = 1 (3) u ξ α u (A, B, C, D, E, F ) (4) ξ α (x 2 α, 2x α y α,

ID 3) 9 4) 5) ID 2 ID 2 ID 2 Bluetooth ID 2 SRCid1 DSTid2 2 id1 id2 ID SRC DST SRC 2 2 ID 2 2 QR 6) 8) 6) QR QR QR QR

DPA,, ShareLog 3) 4) 2.2 Strino Strino STRain-based user Interface with tacticle of elastic Natural ObjectsStrino 1 Strino ) PC Log-Log (2007 6)

9_18.dvi

2 (S, C, R, p, q, S, C, ML ) S = {s 1, s 2,..., s n } C = {c 1, c 2,..., c m } n = S m = C R = {r 1, r 2,...} r r 2 C \ p = (p r ) r R q = (q r ) r R

Fig. 2 Signal plane divided into cell of DWT Fig. 1 Schematic diagram for the monitoring system

mobicom.dvi

sakigake1.dvi

1 DHT Fig. 1 Example of DHT 2 Successor Fig. 2 Example of Successor 2.1 Distributed Hash Table key key value O(1) DHT DHT 1 DHT 1 ID key ID IP value D

Fig. 3 Flow diagram of image processing. Black rectangle in the photo indicates the processing area (128 x 32 pixels).

(2004 ) 2 (A) (B) (C) 3 (1987) (1988) Shimono and Tachibanaki(1985) (2008) , % 2 (1999) (2005) 3 (2005) (2006) (2008)

3_23.dvi

Auerbach and Kotlikoff(1987) (1987) (1988) 4 (2004) 5 Diamond(1965) Auerbach and Kotlikoff(1987) 1 ( ) ,

[3] M.C. Escher Escher 1 Escher Escherization Problem [5] Escherization Problem S ( 1 ) T S ( 2 ) T T [5] Escherization Problem isohedral isohe

1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The Boston Public Schools system, BPS (Deferred Acceptance system, DA) (Top Trading Cycles system, TTC) cf. [13] [

Study on Application of the cos a Method to Neutron Stress Measurement Toshihiko SASAKI*3 and Yukio HIROSE Department of Materials Science and Enginee

soturon.dvi

1 UD Fig. 1 Concept of UD tourist information system. 1 ()KDDI UD 7) ) UD c 2010 Information Processing S



信州大学?Curtin University of Technology　間学術交流協定にもとづく

Vol.55 No (Jan. 2014) saccess 6 saccess 7 saccess 2. [3] p.33 * B (A) (B) (C) (D) (E) (F) *1 [3], [4] Web PDF a m

2 DS SS (SS+DS) Fig. 2 Separation algorithm for motorcycle sound by combining DS and SS (SS+DS). 3. [3] DS SS 2 SS+DS 1 1 B SS SS 4. NMF 4. 1 (NMF) Y

Japanese Journal of Applied Psychology

3D UbiCode (Ubiquitous+Code) RFID ResBe (Remote entertainment space Behavior evaluation) 2 UbiCode Fig. 2 UbiCode 2. UbiCode 2. 1 UbiCode UbiCode 2. 2

EQUIVALENT TRANSFORMATION TECHNIQUE FOR ISLANDING DETECTION METHODS OF SYNCHRONOUS GENERATOR -REACTIVE POWER PERTURBATION METHODS USING AVR OR SVC- Ju

& Vol.5 No (Oct. 2015) TV 1,2,a) , Augmented TV TV AR Augmented Reality 3DCG TV Estimation of TV Screen Position and Ro

Vol. 48 No. 4 Apr LAN TCP/IP LAN TCP/IP 1 PC TCP/IP 1 PC User-mode Linux 12 Development of a System to Visualize Computer Network Behavior for L

ActionScript Flash Player 8 ActionScript3.0 ActionScript Flash Video ActionScript.swf swf FlashPlayer AVM(Actionscript Virtual Machine) Windows

<30312D C839397AA97F02E696E6464>

,,,,., C Java,,.,,.,., ,,.,, i

( ) [1] [4] ( ) 2. [5] [6] Piano Tutor[7] [1], [2], [8], [9] Radiobaton[10] Two Finger Piano[11] Coloring-in Piano[12] ism[13] MIDI MIDI 1 Fig. 1 Syst

log F0 意識 しゃべり 葉の log F0 Fig. 1 1 An example of classification of substyles of rap. ' & 2. 4) m.o.v.e 5) motsu motsu (1) (2) (3) (4) (1) (2) mot

１　発病のとき

ICT a) Caption Presentation Method with Speech Expression Utilizing Speech Bubble Shapes for Video Content Yuko KONYA a) and Itiro SIIO 1. Graduate Sc

LM Watt Stereo Class D Audio Pwr Amp w/Stereo Headphone Amplifier (jp)

1: 2: 3: 4: 2. 1 Exploratory Search [4] Exploratory Search 2. 1 [7] [8] [9] [10] Exploratory Search

23 Fig. 2: hwmodulev2 3. Reconfigurable HPC 3.1 hw/sw hw/sw hw/sw FPGA PC FPGA PC FPGA HPC FPGA FPGA hw/sw hw/sw hw- Module FPGA hwmodule hw/sw FPGA h

97-00

Transcription:

Comparisons of Genetic Algorithms for Timetabling Problems Hiroaki UEDA, Daisuke OUCHI, Kenichi TAKAHASHI, and Tetsuhiro MIYAHARA GA GA GA GA GA SGA GA SGA2SA TS 6 SGA2 GA GA SA 1. GA [1] [12] GA Faculty of Information Sciences, Hiroshima City University, Hiroshima-shi, 731 3194 Japan Compaq Computer K.K, Utsunomiya-shi, 320 0811 Japan GA GA GA [3] GA [4] D I Vol. J86 D I No. 9 pp. 691 701 2003 9 691

2003/9 Vol. J86 D I No. 9 GA GA [8] [10] GA GA GA SGA GA SGA2 SA TS 6 2. 3. GA 4 4. 2. 1 10 20 1 1 5 C1: C2: C3: 1 C4: C5: 692

4 C6: C7: C8: C9: C6 C7 2 C8 C9 4 R1: R2: R3: R4: 9 4 GA GA SGA SGA2 4.4 0 3. GA 3. 1 GA 2 GA [8] [10] GA 1 SI ID C i R j 2 GA GA 2 (a) The genotype for class scheduling. (b) The genotype for room allocation. 1 Fig. 1 The genotype. 693

2003/9 Vol. J86 D I No. 9 Table 1 1 An example of a timetable before the repair operation. Class Period 1 Period 2 Period 3 Period 4 Period 5 Subject-1 Subject-5 Subject-6 A-1 Staff-1 Staff-5 Staff-5 Subject-2 Subject-7 B-1 Staff-2 Staff-6 and Staff-7 Subject-3 Subject-1 C-1 Staff-3 Staff-1 Subject-1 Subject-4 Subject-2 Subject-8 D-1 Staff-1 Staff-4 Staff-2 Staff-3 2 GA Fig. 2 A flow diagram of TGA. 1 <C i,r j > 2 1 C2 C2 3 SI SI (S 1) S 1 SI (S 2) S 2 C3 S 2 S 1 SI S 1 1 D-1 Subject-1 S 1 Subject-2 D-1 Subject-4 Subject-8 S 2 Subject-2 S 1 SI Subject-1 Subject-4 Subject-2 4 C2 1. n c C nc + c 2. 3. S {p 1,p 2,..., p c} 694

2 Table 2 An example of a timetable after the repair operation. Class Period 1 Period 2 Period 3 Period 4 Period 5 Subject-5 Subject-1 Subject-6 A-1 Staff-5 Staff-1 Staff-5 Subject-2 Subject-7 B-1 Staff-2 Staff-6 and Staff-7 Subject-3 Subject-1 C-1 Staff-3 Staff-1 Subject-2 Subject-1 Subject-4 Subject-8 D-1 Staff-2 Staff-1 Staff-4 Staff-3 4. p i S p i p i S S 1 Subject-1 Subject-2 Subject- 1 Subject-2 1 4+3 = 7 2 4+2 = 10 Subject-2 Subject-2 Period1 2 / Subject-1 Period2 Subject-2 Subject-1 Period3 2 5 C i CC(C i) CC(C i) C1-3 C6 C8 R1-3 C i 6 7 R j RC(R j) RC(R j) R j C4 C5 C9 R4 RCC(C i,r j) RCC(C i,r j) CC(C i) RC(R j) 1. CC(C i) N RC(R j) M 2. 1 RCC(C i,r j) 3. (1) (2) CC(C i) (3) fitness(c i) CC(C i) CC(C i) + min(rcc(c i,r j)) (1) j CC(C i) CC(C i) + average(min(rcc(c k,r j))) k j + std(min(rcc(c k,r j))) (2) k j fitness(c i) = max(cc(c k )) CC(C i) (3) k (1) 1 C i (2) C i min() average() std() max() CC(C i)+rc(r j) 0 <C i,r j > 3. 2 GA GA SGA SGA GA 695

2003/9 Vol. J86 D I No. 9 (4) Cost(i) i fitness(i) = max(cost(k)) Cost(i) (4) k 3. 3 GA GA GA GA 1. C1-3 C6 C8 R1-3 CC(C i) (3) CC(C i) 0 2 2. RC (R j) 1 R j C4 C5 C9 R4 RC (R j) 0 3. 4 3 GA SGA SGA2 SGA2 4. 4. 1 3. 4 1 696

2. C6-9 1. 1 2. 1 3. 4. 2 0.8 0.2 1 N N 1 2 2 1 4. 2 3 HCU 97 697

2003/9 Vol. J86 D I No. 9 3 Table 3Timetabling problems. HCU 97 NC NL NCL NR NCR 4 20 4 4 4 4 0.48 0.68 0.89 0.69 0.67 0.69 0.19 0.16 0.230.40 0.18 0.24 0.49 0.19 0.230.40 0.19 0.22 0.5 2.41 2.47 2.45 9.9 2.46 127 0 0 0 0 0 0 0 0 0 0 44 4 Table 4 Penalty values for room allocation. 0.0 1.0 1.0 1.0 0.2 0.0 1.0 1.0 0.5 0.2 0.0 1.0 0.5 0.5 0.2 0.0 5 4 3 1 5 0.7 0.2 2.5 4 0 NC the Number of Classes 20 60 NL the Number of Lectures 0.9 NCL the Number of Complex Lectures 0.4 NR the Number of Rooms 12.5 NCR the Number of Constraints or Requests 3 NR 12.5 9.9 C4 1 C4 4 0.1 1 1 Subject-2 C2 2 2 2 (2 1) 2=2 4. 3 3. 4 C Sun Ultra10 333 MHz 100 100% 1% 500 GA 10 HCU 97 NC 30000 5 50 698

5 Table 5 Experimental results. GA SGA GA SGA2 SA TS HCU 97 1.2 (92.0s) 1.9 (187s) 1.5 (66.0s) 0.3(25.0s) 0.4 (20.2s) 14.0 (80.2s) NC 10.6 (10.4h) 15.4 (11.2h) 0.0 (2.4h) 0.0 (1.1h) 36.0 (2.7h) NL 0.0 (8.5s) 0.0 (27.6s) 0.0 (8.4s) 0.0 (3.7s) 0.0 (25.8s) 3.0 (289s) NCL 0.0 (13.5s) 0.0 (4.1s) 0.0 (26.8s) 0.0 (2.3s) 0.02 (13.0s) 7.5 (132s) NR 0.5 (235s) 2.5 (298s) 3.6 (148s) 0.0 (5.0s) 0.0 (11.6s) 4.00 (80.5s) NCR 0.18 (613s) 0.41 (611s) 0.50 (597s) 0.19 (503s) 0.10 (239s) 1.64 (352s) SA TS SA adapitve cooling reheating [11] 30 NC 5 GA 4 SA SI TS 2 + /2 30 TS GA 4 HCU 97 GA 4 TS TS SA HCU 97 0 GA 37 SGA 17 GA 12 SGA2 46 SA 45 TS 0 SGA2 SA GA 70% SGA2 SA 4 GA SGA TS 4 TS TS SGA2 GA NC GA SGA2 NC GA GA SGA SA 0 TS 24 13 TS NC 5 NL TS NL GA GA SGA2 GA SGA SA NCL TS NCL / 699

2003/9 Vol. J86 D I No. 9 SGA SGA2 NR SGA2 SA GA C4 GA GA 50% SGA2 SA NCR 0 GA SGA2 SA NCR 0 HCU 97 0 GA SGA2 SA 70% 0 0 NCR 4. 4 GA SGA GA SGA2 SA TS SGA2 C10: C11: SGA2 5 SGA2 C10 C11 SGA2 5 SA GA GA 5. 4 4 SGA2 GA GA 700

[1] M. Mitchell, An Introduction to Genetic Algorithm, The MIT Press, Cambridge, 1998. [2] M.W. Carter and G. Laporte, Recent developments in practical course timetabling, ed. E. Burke and M. Carter, The practice and theory of automated timetabling: Selected papers. Lecture Notes in Computer Science, vol.1408, pp.3 19, Springer-Verlag, Berlin, 1998. [3] (D-I), vol.j82-d-i, no.6, pp.883 885, June 1998. [4] D.C. Rich, A smart genetic algorithm for university timetabling, ed. E. Burke and R. Ross, The practice and theory of automated timetabling: Selected papers. Lecture Notes in Computer Science, vol.1153, pp.181 197, Springer-Verlag, Berlin, 1996. [5] W. Erben and J. Keppler, A genetic algorithm solving a weekly course-timetabling problem, ed. E. Burke and P. Ross, The practice and theory of automated timetabling: Selected papers. Lecture Notes in Computer Science, vol.1153, pp.198 211, Springer- Verlag, Berlin, 1996. [6] E. Burke and J-P. Newall, Multi-stage evolutionary algorithm for timetable problem, IEEE Trans. Evol. Comput., pp.1085 1092, 1999. [7] B. Peachter, R.C. Rankin, and A. Cumming, Improving a lecture timetabling system for universitywide use, ed. E. Burke and M. Carter, The practice and theory of automated timetabling: Selected papers. Lecture Notes in Computer Science, vol.1408, pp.156 165, Springer-Verlag, Berlin, 1998. [8] AI-99-53, 1999. [9] H. Ueda, D. Ouchi, K. Takahashi, and T. Miyahara, Co-evolving timeslot/room assignment genetic algorithm technique for university timetabling, ed. E. Burke and W. Erben, The practice and theory of automated timetabling: Selected papers. Lecture Notes in Computer Science, vol.2079, pp.48 63, Springer- Verlag, Berlin, 2001. [10] 11 pp.473 476, 2001. [11] M.A.S. Elmohamed, P. Coddington, and G. Fox, A comparison of annealing techniques for academic course scheduling, ed. E. Burke and M. Carter, The practice and theory of automated timetabling: Selected papers. Lecture Notes in Computer Science, vol.1408, pp.92 112, Springer-Verlag, Berlin, 1998. [12] K.A. Dowsland, Off-the-peg or made-to-measure? Timetabling and scheduling with SA and TS, ed. E. Burke and M. Carter, The practice and theory of automated timetabling: Selected papers. Lecture Notes in Computer Science, vol.1408, pp.37 52, Springer- Verlag, Berlin, 1998. 14 10 11 15 2 24 2 4 7 IEEE 10 12 52 54 62 6 IEEE 59 61 63 63 8 8 701

2026 © docsplayer.net プライバシー | 利用規約 | フィードバック