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
A Study of Effective Application of CG Multimedia Contents for Help of Understandings of the Working Principles of the Internal Combustion Engine (The

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


a) Extraction of Similarities and Differences in Human Behavior Using Singular Value Decomposition Kenichi MISHIMA, Sayaka KANATA, Hiroaki NAKANISHI a

発達心理学研究 第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 3


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 α,

Q [4] 2. [3] [5] ϵ- Q Q CO CO [4] Q Q [1] i = X ln n i + C (1) n i i n n i i i n i = n X i i C exploration exploitation [4] Q Q Q ϵ 1 ϵ 3. [3] [5] [4]

2. Eades 1) Kamada-Kawai 7) Fruchterman 2) 6) ACE 8) HDE 9) Kruskal MDS 13) 11) Kruskal AGI Active Graph Interface 3) Kruskal 5) Kruskal 4) 3. Kruskal

H1-H4*.ai

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

(a) Picking up of six components (b) Picking up of three simultaneously. components simultaneously. Fig. 2 An example of the simultaneous pickup. 6 /

a m 1 mod p a km 1 mod p k<s 1.6. n > 1 n 1= s m, (m, = 1 a n n a m 1 mod n a km 1 mod n k<sn a 1.7. n > 1 n 1= s m, (m, = 1 r n ν = min ord (p 1 (1 B

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

THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE. TV A310

04.™ƒ”R/’Ô”�/’Xfl©

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

大規模マルチエージェントシミュレーションに基づく社会システムデザインの可能性

mobicom.dvi

知能と情報, Vol.30, No.5, pp

sakigake1.dvi

i Version 1.1, (2012/02/22 24),.,..,.,,. R-space,, ( R- space),, Kahler (Kähler C-space)., R-space,., R-space, Hermite,.

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

7 July 005 n SSP n n SSP SSP SSP n n. Selected Sequence-PairSSP. Sequence-PairSeq-Pair sequence-pair ) seq-pair n Γ + Γ (Γ + ;Γ ) n (n!) Γ + (i) Γ + i

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

特集_03-07.Q3C

(Kiyoshi Kitahara) Department of Engineering, Kogakuin University (Takayuki Abe) (Masataka Kaneko) (Satoshi Yamashita) Departmen

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

3_23.dvi

1_26.dvi

n 2 n (Dynamic Programming : DP) (Genetic Algorithm : GA) 2 i

4. C i k = 2 k-means C 1 i, C 2 i 5. C i x i p [ f(θ i ; x) = (2π) p 2 Vi 1 2 exp (x µ ] i) t V 1 i (x µ i ) 2 BIC BIC = 2 log L( ˆθ i ; x i C i ) + q

COM COM 4) 5) COM COM 3 4) 5) COM COM 6) 7) 10) COM Bonanza 6) Bonanza Hearts COM 7) 10) Hearts 3 2,000 4,000

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

Vol.53 No (Mar. 2012) 1, 1,a) 1, 2 1 1, , Musical Interaction System Based on Stage Metaphor Seiko Myojin 1, 1,a

08_眞鍋.indd

2003/3 Vol. J86 D II No Fig. 1 An exterior view of eye scanner. CCD [7] CCD PC USB PC PC USB RS-232C PC

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] [

2 A A 3 A 2. A [2] A A A A 4 [3]

<31302D8EC091488CA48B862D8E E7190E690B691BC2D3296BC976C2E706466>

Vol.57 No (Mar. 2016) 1,a) , L3 CG VDI VDI A Migration to a Cloud-based Information Infrastructure to Support

1

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

2 (March 13, 2010) N Λ a = i,j=1 x i ( d (a) i,j x j ), Λ h = N i,j=1 x i ( d (h) i,j x j ) B a B h B a = N i,j=1 ν i d (a) i,j, B h = x j N i,j=1 ν i

IPSJ SIG Technical Report Vol.2014-CE-123 No /2/8 Bebras 1,a) Bebras,,, Evaluation and Possibility of the Questions for Bebras Contest Abs

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

44



信州大学?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

NP 1 ( ) Ehrgott [3] ( ) (Ehrgott [3] ) Ulungu & Teghem [8] Zitzler, Laumanns & Bleuler [11] Papadimitriou & Yannakakis [7] Zaroliagis [10] 2 1

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

< >

IPSJ SIG Technical Report Vol.2009-DPS-141 No.23 Vol.2009-GN-73 No.23 Vol.2009-EIP-46 No /11/27 t-room t-room 2 Development of

MMXVC_H1

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

IPSJ SIG Technical Report Vol.2010-SLDM-144 No.50 Vol.2010-EMB-16 No.50 Vol.2010-MBL-53 No.50 Vol.2010-UBI-25 No /3/27 Twitter IME Twitte

MANET MANET MANET (DTN: Delay Tolerant Network) DTN DTN DTN DTN [7], [3], [11] [8] % N M m M n N D(m, n) Size(m) m MD(m) m M, n N, MD(m) = max{d

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

IPSJ SIG Technical Report 1, Instrument Separation in Reverberant Environments Using Crystal Microphone Arrays Nobutaka ITO, 1, 2 Yu KITANO, 1

16) 12) 14) n x i, (1 i < n) x 1 = x 2 = = x n. (6) L = D A (1) D = diag(d 1,d 2,,d n ) n n A d i = j i a i j 9) 0 a 12 a 13 a 14 A = a 21 0 a

Memetic 26 2 (125T208T)

2006 [3] Scratch Squeak PEN [4] PenFlowchart 2 3 PenFlowchart 4 PenFlowchart PEN xdncl PEN [5] PEN xdncl DNCL 1 1 [6] 1 PEN Fig. 1 The PEN

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

<30312D C839397AA97F02E696E6464>

untitled

,,,,., 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

１　発病のとき

3_39.dvi

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

Vol.54 No (May 2013) 7 1,a) , e e Factors and Strategies for Accelerating the Diffusion of Electronic Money Based

Optical Flow t t + δt 1 Motion Field 3 3 1) 2) 3) Lucas-Kanade 4) 1 t (x, y) I(x, y, t)

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

1.pdf

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

IPSJ SIG Technical Report Vol.2013-GN-86 No.35 Vol.2013-CDS-6 No /1/17 1,a) 2,b) (1) (2) (3) Development of Mobile Multilingual Medical

Mhij =zhij... (2) Đhij {1, 2,...,lMhij}... (3)

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

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