การหาค่าพารามิเตอร์ทางเจเนติกอัลกอริทึมในการจัดตารางสอน สำหรับนักศึกษา คณะวิศวกรรมศาสตร์ มหาวิทยาลัยสงขลานครินทร์

บทคัดย่อ

บทคัดย่อ

การจัดตารางสอนเป็นกระบวนที่ค่อนข้างยุ่งยากซับซ้อน มีข้อมูลและเงื่อนไขที่ต้องพิจารณาเป็นจำนวนมากดังนั้นในการจัดตารางสอนแต่ละครั้งต้องใช้เวลานานและเกดิ ความผิดพลาดอยู่เสมอ ในงานวิจัยนี้ได้นำเอาวิธีการของเจเนติกอัลกอริทึมไปใช้ในการพัฒนาโปรแกรมช่วยในการจัดตารางสอนของนักศึกษาคณะวิศวกรรมศาสตร์มหาวิทยาลัยสงขลานครินทร์ มีวัตถุประสงค์เพื่อให้ได้ตารางสอนที่มีความถูกต้อง ขัดแย้งกับเงื่อนไขน้อยที่สุด (Minimize Fitness Value) และลดเวลาที่ใช้การจัดตารางสอนโดยวิธีการทางเจเนติกอัลกอรึทึมที่นำมาประยุกต์ใช้มีขั้นตอนเริ่มจากการสร้างคำตอบที่เป็นไปได้ในรูปแบบโครโมโซม ซึ่งพิจารณาจากความสัมพันธ์ของตัวแปรต่างๆ ที่ใช้ในการจัดตารางสอน ได้แก่ กลุ่มผู้เรียน อาจารย์ผู้สอน วิชาเรียน ห้องเรียน ภายใต้เงื่อนไขต่างๆ ในการจัดตารางสอน แล้วประเมินค่าความเหมาะสมของโครโมโซม จากนั้นทำการสลับสายพันธุ์(Crossover)และทำการกลายพันธุ์ (Mutation) จากผลการทดลองสำหรับข้อมูลที่ประกอบด้วยรายวิชา 425 รายวิชา อาจารย์ 152 คน กลุ่มนักศึกษา 83 กลุ่มและห้องเรียน 59 ห้อง มีพารามิเตอร์ที่เหมาะสมเพื่อกำหนดให้เป็นค่าเริ่มต้นของโปรแกรมคือจำนวนคำตอบเบื้องต้นเท่ากับ 2,500 โครโมโซม จำนวนประชากรเท่ากับ 100โครโมโซมและจำนวนเจนเนอเรชันเท่ากับ 500 เจนเนอเรชันค่าความน่าจะเป็นในการครอสโอเวอร์เท่ากับ 0.8 ค่าความน่าจะเป็นในการมิวเตชันเท่ากับ 0.3 นอกจากนี้การกำหนดค่าน้ำหนักของเงื่อนไขบังคับและเงื่อนไขเพื่อความสมบูรณ์จะมีผลต่อจำนวนเจนเนอชันที่สามารถหาคำตอบที่เป็นไปได้และคำตอบที่ดีที่สุดอีกด้วย

คำสำคัญ: การจัดตารางสอน เจเนติกอัลกอริทึมฮิวริสติก

Abstract

Timetabling procedures are very complex and difficultbecause they have a number of data and constraintsto be considered and determined. It uses a plenty oftime, and always has mistaken at the same time. In thisreport, genetic algorithms has been selected to createa program which can help to generate a timetable forstudents in the faculty of Engineering, Prince of SongklaUniversity. The purposes of this program are providingthe accurate timetable, having minimize conflicts withthe conditions which has minimize fitness value, andreducing the time. The first step of genetic algorithmfor timetabling is a creation of timetable chromosomepatterns which are produced by considering a relationbetween related variables used in timetabling such asstudents, lecturers, subjects and classrooms. Thesechromosomes must be not conflict with the hard constraintsin timetabling. Then these chromosomes are evaluatedby fitness function, crossover and mutation for automaticadjustment to achieve the better timetable for data usedin test, there are 425 subjects, 152 lectures, 83 studentgroups, and 59 classrooms. Moreover, the optimal valuesof GA parameters were 2,500 initializes, 100 population,500 generations probability of crossover was 0.8 andprobability of mutation was 0.3. In addition, the weightof hard and soft constraints will be has effect of thegeneration that is going to be feasible timetable andthe best timetable.

Keywork: Course Timetabling, Genetic Algorithm,Heuristics