จีเนติกอัลกอริทึมแบบหลายจุดประสงค์สำหรับแก้ปัญหาการจัดตารางสอนของโรงเรียน

บทที่ 1 บทนำ 1.1 ความเป็นมาและความสำคัญของปัญหา การจัดการเรียนการสอนของสถานศึกษาต่าง ๆ ให้เป็นไปอย่างมีประสิทธิภาพสอดคล้องกับ พระราชบัญญัติการศึกษา พ.ศ. 2544 (กระทรวงศึกษาธิการ, 2544) สถานศึกษาจำเป็นต้องเตรียมการ ด้านต่าง ๆ ให้พร้อมก่อนเปิดภาคเรียนแต่ละภาค โดยเฉพาะการจัดตารางสอน ซึ่งนับเป็นงานสำคัญ งานหนึ่งของการบริหารงานวิชาการ ที่จะต้องจัดทำให้สอดคล้องกันระหว่างบุคลากร สถานที่สอน เวลา และการจัดรายวิชาต่าง ๆ การจัดตารางสอนในปัจจุบันนี้ มีปัญหาต่าง ๆ มากมายเพราะจำนวนผู้เรียนเพิ่มขึ้น ห้องเรียน มากขึ้น รายวิชาเพิ่มเติมที่มีความเข้มข้นหลากหลายให้ผู้เรียนได้เรียนตามความถนัด ความสนใจ ความต้องการ และความแตกต่างระหว่างบุคคลมากขึ้น ทำให้การจัดตารางสอนมีความซับซ้อนมาก ขึ้น ในการจัดตารางสอนแต่ละครั้ง จะต้องพบกับเงื่อนไขต่าง ๆ เช่น ผู้สอนหนึ่งท่านไม่สามารถ สอนผู้เรียนหลายกลุ่มในวันและเวลาเดียวกัน หรือผู้เรียนหนึ่งกลุ่มไม่สามารถเรียนกับผู้สอนหลาย ท่านพร้อมกันในวันและเวลาเดียวกัน หรือผู้สอนต้องสอนในวิชาที่ตนเองรับผิดชอบ เป็นต้น จะ เห็นได้ว่าการจัดตารางสอนด้วยคน จะใช้เวลานานมาก และต้องทำซ้ำหลายๆ ครั้ง ซึ่งปัญหานี้ สามารถใช้คอมพิวเตอร์มาช่วยได้ และมีนักวิจัยพยายามคิดค้นวิธีการต่าง ๆ มาช่วยในการจัด ตารางสอน ซึ่งปัญญาประดิษฐ์ (Artificial Intelligence) (Luger, 2002) เป็นวิธีหนึ่งที่ประยุกต์ขึ้นมา เพื่อช่วยแก้ปัญหาดังกล่าว เช่น การใช้โครงข่ายประสาทเทียม (Artificial Neural Network) จัด ตารางเรียน (Yu, 1990) และ การใช้ทฤษฎีฝูงมด (Ant Colony Theory) เข้ามาแก้ปัญหาการจัดตาราง เรียนในมหาวิทยาลัย (Krzysztof Socha, Michael Sampels and Max Manfrin, 2002) จีเนติกอัลกอริทึม (Genetic Algorithm) ซึ่งเป็นหนึ่งในวิธีปัญญาประดิษฐ์ที่จำลองการทำงาน ทางชีววิทยาในการให้กำเนิดประชากรรุ่นใหม่ โดยอาศัยพื้นฐานของการวิวัฒนาการทางพันธุกรรม ในการถ่ายทอดลักษณะต่าง ๆ ไปยังรุ่นลูกหลาน (Mitchell, 1996) ซึ่งปฏิบัติตามหลักการทาง พันธุศาสตร์นำมาประยุกต์ใช้ในการแก้ปัญหาเพื่อหาคำตอบที่ดีที่สุดหรือใกล้เคียงที่สุด 2 จากแนวความคิดข้างต้นจะเห็นว่าจีเนติกอัลกอริทึม เป็นเทคนิคที่เหมาะสมในการหาคำตอบ ที่เหมาะสมที่สุด ดังนั้นจึงนำจีเนติกอัลกอริทึมมาใช้ในการจัดตารางสอน แต่เนื่องจากการจัด ตารางสอนมีเงื่อนไขต่าง ๆ มากมาย เพื่อให้การจัดตารางสอนมีความเหมาะสมที่สุด จึงใช้จีเนติก อัลกอริทึมแบบหลายจุดประสงค์ (Multi Objective Genetic Algorithm) ช่วยให้การจัดตารางสอน เป็นไปอย่างมีคุณภาพ ตรงตามเงื่อนไขต่างๆ ประหยัดแรงงาน เวลา และค่าใช้จ่าย 1.2 วัตถุประสงค์ 1.2.1 เพื่อพัฒนาจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ สำหรับแก้ปัญหาการจัดตารางสอน ของโรงเรียน 1.2.2 เพื่อทดสอบประสิทธิภาพของจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ สำหรับแก้ปัญหา การจัดตารางสอนของโรงเรียน 1.3 ขอบเขตของการวิจัย งานวิจัยนี้เป็นการพัฒนาจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ สำหรับแก้ปัญหาการจัด ตารางสอนของโรงเรียนเพื่อใช้ในการค้นหาข้อมูลที่ดีที่สุด ซึ่งมีขอบเขตของการวิจัยดังนี้ 1.3.1 สร้างจีเนติกอัลกอริทึมแบบหลายจุดประสงค์สำหรับแก้ปัญหาการจัดตารางสอนของ โรงเรียน โดยใช้โปรแกรม Microsoft Visual Basic 6.0 1.3.2 สร้างโปรแกรมจัดตารางสอนโดยใช้โปรแกรม Microsoft Visual Basic 6.0 1.3.3 ข้อมูลที่ใช้ในการวิจัย ประกอบด้วย 3.1.1 ผู้สอน 3.1.2 กลุ่มเรียน 3.1.3 ห้องเรียน 3.1.4 วิชาเรียน 3.1.5 จำนวนคาบเรียนต่อวัน 3.1.6 จำนวนวันเรียนต่อสัปดาห์ 3.1.6 เงื่อนไขต่างๆ 1.3.4 สามารถบันทึกและจัดพิมพ์ตารางสอนออกมาได้ โดยใช้โปรแกรม Microsoft Excel 1.3.5 ข้อมูลที่นำมาใช้ มาจากแบบฟอร์มอัตรากำลังของแต่ละกลุ่มสาระการเรียนรู้ คือ ข้อมูล อาจารย์, ข้อมูลวิชาที่สอน, ข้อมูลนักเรียนที่สอน และจำนวนคาบเรียน 3 1.3.6 เครื่องมือที่ใช้ในการพัฒนา 1.3.6.1 Hardware ที่ใช้ในการพัฒนาระบบประกอบด้วย 1.3.6.1.1 CPU Intel Pentium III ขึ้นไป 1.3.6.1.2 หน่วยความจำสำรอง ตั้งแต่ 256 MB ขึ้นไป 1.3.6.1.3 เนื้อที่ว่างบน Hard disk อย่างน้อย 2 MB ขึ้นไป 1.3.6.2 Software ที่ใช้ในการพัฒนาระบบประกอบด้วย 1.3.6.2.1 ระบบปฏิบัติการ Microsoft Windows XP 1.3.6.2.2 โปรแกรม Microsoft Visual Basic 6.0 1.3.6.2.3 โปรแกรม Microsoft Access 2003 1.3.6.2.4 โปรแกรม Microsoft Excel 2003 1.4 ประโยชน์ที่คาดว่าจะได้รับ 1.4.1 ได้โปรแกรมจัดตารางสอน ที่พัฒนาโดยใช้จีเนติกอัลกอริทึมแบบหลายจุดประสงค์ ซึ่ง สามารถลดปัญหาการจัดตารางสอนซึ่งมีความยุ่งยากซับซ้อน 1.4.2 ประยุกต์ใช้ในการจัดตารางสอน ตามสถานศึกษาต่าง ๆ 1.4.3 เป็นต้นแบบสำหรับพัฒนาเพื่อประยุกต์ใช้งานจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ บทที่ 2 ทฤษฎีและงานวิจัยที่เกี่ยวข้อง การวิเคราะห์ปัญหาต่าง ๆ ที่เกิดขึ้นในทุกสาขาอาชีพไม่ว่าจะเป็นงานในแวดวงวิชาการ ใน วงการธุรกิจ หรือในด้านอุตสาหกรรม พบว่าจะต้องประสบกับปัญหาที่เกี่ยวข้องกับการดำเนินงาน หรือกิจการต่าง ๆ ที่ต้องการความเหมาะสมที่สุดอยู่เสมอ ซึ่งการแก้ปัญหาต่าง ๆ นั้น ขึ้นอยู่กับการ วิเคราะห์ทางคณิตศาสตร์อย่างมาก แต่การแก้ปัญหาบางอย่างด้วยการวิเคราะห์ทางคณิตศาสตร์มี ความซับซ้อนมาก ทำให้เกิดวิธีการใหม่ ๆ ขึ้นมา ไม่ว่าจะเป็นจีเนติกอัลกอริทึม (Genetic Algorithm) โดยมีพื้นฐานมาจากหลักการทางพันธุศาสตร์ ระบบอาณาจักรมด (Ant Colony System) โดยมีพื้นฐานมาจากพฤติกรรมการหาอาหารของมด หรือการหาค่าเหมาะสมแบบกลุ่มอนุภาค (Particle Swarm Optimization) โดยมีพื้นฐานมาจากพฤติกรรมการอพยพของฝูงนก หรือการเรียนรู้ ของฝูงปลา เพื่อนำมาใช้แก้ปัญหาแทนวิธีการทางคณิตศาสตร์ การจัดตารางสอนก็เป็นปัญหาหนึ่งที่มีเงื่อนไขต่าง ๆ มากมาย จึงได้นำจีเนติกอัลกอริทึมแบบ หลายจุดประสงค์ (Multi Objective Genetic Algorithm) เข้ามาช่วยในการแก้ปัญหา ซึ่งทฤษฎีและ งานวิจัยที่เกี่ยวข้องมีดังนี้ 1. การหาจุดเหมาะสมที่สุด (Optimization) 2. จีเนติกอัลกอริทึมแบบหลายจุดประสงค์ (Multi Objective Genetic Algorithm) 3. การจัดตารางสอน (Time Tabling) 4. งานวิจัยที่เกี่ยวข้อง 2.1 การหาจุดเหมาะสมที่สุด (Optimization) ในงานด้านต่างๆ เช่น งานวิศวกรรมศาสตร์ วิทยาศาสตร์ การจัดการ และ อื่นๆ บ่อยครั้งที่เรา จะเกี่ยวข้องกับการหาจุดที่เหมาะสมที่สุด หรือจุดที่ดี ที่สุด ตัวอย่างเช่น การออกแบบเครื่องบินให้มี น้ำหนักต่ำสุดและมีความแข็งแกร่งสูงสุด การหาเส้นทางโคจรของดาวเทียมให้ได้ระยะที่เหมาะสม ที่สุด การออกแบบโครงสร้างของอาคารให้มีค่าใช้จ่ายที่ต่ำที่สุด การออกแบบแหล่งเก็บน้ำเช่นเขื่อน เพื่อป้องกันน้ำท่วมให้มีความแข็งแกร่ง การพยากรณ์พฤติกรรมของโครงสร้างโดยที่ลดพลังงานให้ มากที่สุด การตัดแผ่นโลหะให้มีค่าใช้จ่ายต่ำที่สุด การออกแบบปั๊มและอุปกรณ์ส่งถ่ายความร้อนให้ ได้ประสิทธิภาพสูงสุด หาจุดที่เครื่องกำเนิดไฟฟ้าจะกำเนิดไฟฟ้าได้สูงสุดโดยที่มีพลังงาน 5 สูญเสียน้อยที่สุด หาจุดที่เหมาะสมที่สุดสำหรับการวางแผนและจัดการเวลา เป็นต้น มีวิธีการทาง คณิตศาสตร์มากมายที่สามารถประยุกต์ใช้เพื่อหาจุดที่ดีที่สุด การหาจุดที่ดีที่สุด (optimization or mathematical programming) ก็คือ การหาค่า x ซึ่งทำให้ f(x) มีค่าต่ำสุดหรือสูงสุด โดยที่ di(x) . ai, i = 1, 2, …, m (2-1) ei(x) = bi, i = 1, 2, …, p (2-2) โดยที่ x เป็นเวคเตอร์ n มิติของฟังก์ชั่นเป้าหมาย (objective function) di(x) เป็นข้อจำกัดที่ไม่ เท่ากัน (inequality constraints) ei(x) เป็นข้อจำกัด ที่เท่ากัน (equality constraints) และ ai และ bi เป็นค่าคงที่ การหาจุดที่ดีที่สุดสามารถแยกป็นรูปแบบพื้นฐานของ f(x) ถ้า f(x) และข้อจำกัดเป็นเชิง เส้น จะเป็นการแก้ปัญหาแบบเชิงเส้น (linear programming) ถ้า f(x) เป็นพจน์กำลังสอง (quadratic) และข้อจำกัดเป็นเชิงเส้น จะเป็นการแก้ปัญหาแบบกำลังสอง (quadratic programming) ถ้า f(x) ไม่ เป็นเชิงเส้นและข้อจำกัดไม่เป็นเชิงเส้น จะเป็นการแก้ปัญหาแบบไม่เชิงเส้น (nonlinear programming) การหาจุดที่ดีที่สุด (global optimum) แบ่งเป็นสองลักษณะ คือ การหาจุดสูงสุด (global maximum) และการหาจุดที่ต่ำที่สุด (global minimum) ของฟังก์ชัน ฟังก์ชันที่ต้องการหาจุดที่สูง ที่สุดหรือจุดที่ต่ำที่สุดนั้นอาจจะมีหลายจุด ที่เป็นลักษณะคล้ายกับจุดที่สูงที่สุด (local maximum) หรือ จุดที่คล้ายกับจุดที่ต่ำที่สุด (local minimum) เราเรียกเป็น multi-modal functions ในการแยกจุด ที่เป็นจุดที่ดีที่สุดจริงๆ (global optimum) ออกจาก จุดที่ดีที่สุดบริเวณแคบ (local optimum) นั้นเป็น ปัญหาที่ยากมาก ซึ่งวิธีการหาจุดที่ดีที่สุดนั้นก้อมีขั้นตอนวิธีการต่าง ๆ มากมาย เช่น จีเนติก อัลกอริทึม (Genetic Algorithm) ระบบอาณาจักรมด (Ant Colony System) การหาค่าเหมาะสมแบบ กลุ่มอนุภาค (Particle Swarm Optimization) เป็นต้น 2.1.1 จีเนติกอัลกอริทึม (Genetic Algorithm : GA) ถูกคิดค้นโดยจอห์น ฮอลแลนด์ (John Holland) ในปี 1975 เป็นเทคนิคการหาค่าเหมาะสมที่สุดที่มีลักษณะการทำงานในรูปแบบของการ ค้นหาคำตอบแบบขั้นตอนเชิงฮิวริสติก (Heuristic) ซึ่งมีรากฐานแนวคิดมาจากทฤษฎีวิวัฒนาการ ของชาร์ล ดาร์วิน (Charles Darwin) โดยอิงจากแนวคิดการอยู่รอดของผู้ที่แข็งแรงที่สุด (Survival of the fittest) ซึ่งการทำงานของจีเนติกอัลกอริทึมนี้จะเป็นไปในลักษณะของการหาคำตอบแบบ คู่ขนาน (Parallel Search) โดยคำตอบที่ได้จากการหาคำตอบในหนึ่งรุ่น (Generation) จะผ่านการ แปลง (Transformation) เพื่อที่จะนำไปสู่การค้นหาคำตอบที่ดีขึ้นในรุ่นถัดไป การเปลี่ยนแปลงที่ เกิดขึ้นกับคำตอบ (Solution) หรือสมาชิกของประชากร (Individual) ภายในประชากร (Population) หนึ่งนั้นจะเป็นไปเพื่อการสำรวจพื้นที่ในการค้นหา (Search Space) และส่งเสริมให้มีการถ่ายทอด 6 คุณลักษณะที่ดี (Fit Characteristics) ของคำตอบที่ค้นพบในรุ่นปัจจุบันไปยังรุ่นถัดไป สมาชิกของ ประชากรที่มีคุณลักษณะที่ดี (Fit Individual) หรือคำตอบที่มีคุณลักษณะดี จะมีอยู่หลายคำตอบ ด้วยกัน ซึ่งจะนำไปสู่คำตอบที่มีค่าเหมาะสมที่สุด (Optimum Solution) นั่นคือสมาชิกของประชากร ที่มีลักษณะดีที่สุด (Fittest Individual) จีเนติกอัลกอริทึมมีความแตกต่างจากเทคนิคการหาคำตอบที่เหมาะสมที่สุดแบบมาตรฐาน อื่น ๆ คือ จีเนติกอัลกอริทึมจะทำการค้นหาคำตอบในพื้นที่การค้นหาของตัวแปรตัดสินใจ (Decision Variable) ของปัญหาของค่าที่เหมาะสมที่สุด (Optimization Problem) โดยที่ตัวแปร ตัดสินใจจะถูกเข้ารหัสเป็นสายรหัส จีเนติกอัลกอริทึมจะทำการหาคำตอบจากหลาย ๆ จุดพื้นที่ที่ เป็นไปได้ในการหาคำตอบ ทำให้โอกาสการค้นหาคำตอบที่เป็นค่าเหมาะสมที่สุดเฉพาะที่ (Local Optimum) ลดน้อยลง จีเนติกอัลกอริทึมจะใช้ข้อมูลที่เป็นผลที่เกิดจากค่าจุดประสงค์ (Objective Value) ในการกำหนดทิศทางในการหาคำตอบในพื้นที่การค้นหา ซึ่งเทคนิคอื่นจะใช้ข้อมูลที่ได้มา จากอนุพันธ์ (Derivative) ของฟังก์ชันจุดประสงค์ (Objective Function) ในการกำหนดทิศทางใน การหาคำตอบ จีเนติกอัลกอริทึมจะใช้กฎการส่งผ่านเชิงความน่าจะเป็น (Probabilistic transmission rule) ในกระบวนการหาคำตอบ ซึ่งเทคนิคอื่นจะใช้กฎการส่งผ่านเชิงกำหนด (Deterministic transmission rule) ในกระบวนการหาคำตอบ เนื่องจากจีเนติกอัลกอริทึมมีรากฐานมาจากทฤษฎีการวิวัฒนาการ จึงมีศัพท์เฉพาะทางจีเนติก อัลกอริทึมเกี่ยวกับด้านชีววิทยา ดังนี้ ตารางที่ 2-1 คำศัพท์เฉพาะทางจีเนติกอัลกอริทึม คำศัพท์ ความหมาย โครโมโซม สายรหัส ยีน สายรหัสหรือตัวอักษร อัลลีล ค่าที่เป็นไปได้ในแต่ละตำแหน่งของสายรหัส โลคัส ตำแหน่งของรหัสบนสายรหัส จีโนไทป์ ลักษณะเฉพาะบนสายรหัส ฟีโนไทป์ ตัวแปรของการตัดสินใจหลังการถอดรหัส จีเนติกอัลกอริทึมจะทำการค้นหาคำตอบจากกลุ่มของคำตอบในพื้นที่การค้นหา ซึ่งคำตอบ เหล่านี้จะถูกกำหนดโดยใช้สายรหัสเพื่อแทนคุณลักษณะของตัวแปรตัดสินใจของปัญหาค่า เหมาะสมที่สุด โดยสายรหัสของคุณลักษณะเหล่านี้จะถูกเรียกว่าโครโมโซม (Chromosome) 7 โครโมโซมหนึ่ง ๆ จะประกอบด้วยกลุ่มของรหัส เรียกว่ายีน (Gene) โดยที่ยีนหนึ่ง ๆ จะมีตำแหน่ง อยู่บนโครโมโซมที่แน่นอน โดยที่ตำแหน่งของยีนนั้นจะเรียกว่าโลคัส (Locus) และตามปกติยีน หนึ่งยีนจะมีค่าหรือสถานะที่เป็นไปได้หลายค่า แต่ละค่าที่เป็นไปได้นี้เรียกว่าอัลลีล (Allele) ซึ่งเป็น ตัวกำหนดลักษณะของตัวแปรตัดสินใจของคำตอบ ลักษณะของยีนที่ปรากฎอยู่ในโครโมโซมจะ เรียกว่าจีโนไทป์ (Genotype) หลังจากถอดรหัสแล้วค่าที่ได้จะเป็นตัวแปรของการตัดสินใจ เรียกว่าฟีโนไทป์ (Phenotype) ขั้นตอนการทำงานของจีเนติกอัลกอริทึมแบบง่ายเป็นขั้นตอนการทำงานที่มีความซับซ้อน น้อยที่สุดในบรรดาขั้นตอนการทำงานของจีเนติกอัลกอริทึมแบบต่าง ๆ ดังภาพที่ 2-1 ในขั้นตอน แรกเป็นการกำหนดค่าเริ่มต้นของสมาชิกของโครโมโซมโดยการสุ่ม เมื่อสุ่มค่าสมาชิกของ โครโมโซมครบทุกตัวแล้ว ขั้นตอนต่อไปคือการถอดรหัสสมาชิกของโครโมโซมซึ่งจะได้เป็นค่า ของตัวแปรตัดสินใจ (Decision value) จากนั้นเป็นการหาค่าจุดประสงค์ (Objective value) ของ สมาชิกของโครโมโซม โดยการแทนค่าตัวแปรตัดสินใจของสมาชิกโครโมโซมในฟังก์ชัน จุดประสงค์ หาค่าความแข็งแรงจากฟังก์ชันจุดประสงค์ (Fitness value) จากนั้นใช้ตัวดำเนินการ ทั้งสามคือการคัดเลือก (Selected) การสลับสายพันธุ์ (Crossover) การกลายพันธุ์ (Mutate) ใน การเปลี่ยนแปลงสมาชิกของโครโมโซม ซึ่งจะได้เป็นโครโมโซมใหม่ จากนั้นทำการถอดรหัสและ คำนวณซ้ำจนกระทั่งถึงรุ่นสุดท้าย (Max Generation) ที่กำหนดไว้ อัลกอริทึมของจีเนติกอัลกอริทึมแบบง่าย ดังภาพที่ 2-1 ภาพที่ 2-1 อัลกอริทึมของจีเนติกอัลกอริทึมแบบง่าย Initialize of random individuals for first generation For (i=1; i=Max Generation; i+) { Decision value = Decode(Individual); Objective value = Objective Function (Decision value); Fitness value = Fitness Function (Objective value); Selected individual = Selection (Individual); Crossover individual = Crossover (Selected Individual, Pc); Mutate individual = Mutation (Crossover Individual, Pm); Individual = Mutate Individual; } 8 ขั้นตอนการทำงานของจีเนติกอัลกอริทึมแบบทั่วไปจะมีความแตกต่างจากขั้นตอนการ ทำงานของจีเนติกอัลกอริทึมแบบง่าย คือ ขั้นตอนการทำงานของจีเนติกอัลกอริทึมแบบทั่วไปจะมี ตัวดำเนินการที่ใช้ในการค้นหาคำตอบมากกว่าขั้นตอนการทำงานของจีเนติกอัลกอริทึมแบบง่าย คือจะมีการปรับมาตราความแข็งแรง และการแบ่งมาตราความแข็งแรงในการทำงานด้วย ดังภาพที่ 2-2 อัลกอริทึมของจีเนติกอัลกอริทึมแบบทั่วไป ดังภาพที่ 2-2 ภาพที่ 2-2 อัลกอริทึมของจีเนติกอัลกอริทึมแบบทั่วไป ขั้นตอนการทำงานของจีเนติกอัลกอริทึมแบบทั่วไป จะเริ่มจากการกำหนดค่าต่าง ๆ ให้ เรียบร้อยก่อน คือ กำหนดฟังก์ชันจุดประสงค์ และ กำหนดรูปแบบโครโมโซม เมื่อกำหนดค่าต่าง ๆ เสร็จแล้วจะเข้าสู่กระบวนการทำงาน คือ การเข้ารหัสโครโมโซม การหาค่าความแข็งแรง การ คัดเลือก การสลับสายพันธุ์ และการกลายพันธุ์ 2.1.1.1 กำหนดฟังก์ชันจุดประสงค์ (Objective Function) เป็นการกำหนดฟังก์ชันที่ เกี่ยวกับเงื่อนไขต่าง ๆ ที่ต้องการขึ้นมา เพื่อใช้ในการหาค่าความแข็งแรง 2.1.1.1.1 ฟังก์ชันแบบจุดประสงค์เดียว (Single Objective Function) เป็นการ กำหนดฟังก์ชันขึ้นมาหนึ่งฟังก์ชัน ที่ต้องการเพียงคำตอบเดียว ซึ่งเหมาะสำหรับปัญหาที่มีความ ซับซ้อนน้อย และไม่ขัดแย้งกัน Initialize of random individuals for first generation For (i=1; i=Max Generation; i+) { Decision value = Decode(Individual); Objective value = Objective Function (Decision value); Fitness value = Fitness Function (Objective value); Selected individual = Selection (Individual); Crossover individual = Crossover (Selected Individual, Pc); Mutate individual = Mutation (Crossover Individual, Pm); Individual = Mutate Individual; } 9 2.1.1.1.2 ฟังก์ชันแบบหลายจุดประสงค์ (Multi Objectives Function) เป็นการ กำหนดฟังก์ชันขึ้นมาหลาย ๆ ฟังก์ชัน ที่ต้องการคำตอบหลาย ๆ คำตอบ แต่ละคำตอบจะเป็น คำตอบที่เป็นคู่แข่งกัน (Candidate) ซึ่งเหมาะกับปัญหาที่มีความซับซ้อนมาก และขัดแย้งกัน 2.1.1.2 กำหนดรูปแบบโครโมโซม (Format Chromosome) เป็นการกำหนดว่า โครโมโซมที่จะเลือกใช้ มีขนาดเท่าไร รูปแบบไหน แต่ละตัวมีความหมายว่าอะไร 2.1.1.3 การเข้ารหัสโครโมโซม (Chromosome Encoding) เป็นการสร้างโครโมโซม ขึ้นมาเพื่อแทนค่าของตัวแปรตัดสินใจ ซึ่งเป็นขั้นตอนที่สำคัญมากก่อนที่จะเข้าสู่กระบวนการของ จีเนติกอัลกอริทึม รูปแบบการเข้ารหัสของโครโมโซมมีดังนี้ 2.1.1.3.1 การเข้ารหัสแบบเลขฐานสอง (Binary Encoding) เป็นวิธีที่ง่ายที่สุด ในการเข้ารหัสโครโมโซม โดยยีนแต่ละตัวจะมีอัลลีลเป็น 0 หรือ 1 ดังภาพที่ 2-3 X1 = 0 1 0 1 X2 = 1 0 0 1 ภาพที่ 2-3 การเข้ารหัสแบบเลขฐานสอง 2.1.1.3.2 การเข้ารหัสแบบเลขจำนวนเต็ม (Integer Encoding) จะมีความยาว น้อยกว่าการเข้ารหัสแบบเลขฐานสอง โดยยีนแต่ละตัวจะมีอัลลีลเป็น 0 ถึง n ที่เป็นค่าจำนวนเต็ม ซึ่ง n จะเป็นค่าสุดท้ายที่ใช้แทนตัวแปรตัดสินใจแต่ละตัว ดังภาพที่ 2-4 X1 = 5 X2 = 9 ภาพที่ 2-4 การเข้ารหัสแบบเลขจำนวนเต็ม 2.1.1.3.3 การเข้ารหัสแบบเลขจำนวนจริง (Real Encoding) ต้องกำหนดช่วง การทำงานหรือช่วงของค่าตัวแปรตัดสินใจแต่ละตัว โดยยีนแต่ละตัวจะมีอัลลีลเป็นค่าจำนวนจริง ซึ่งความแม่นยำของคำตอบ สามารถกำหนดได้จากจำนวนตำแหน่งของทศนิยมที่ใช้ ดังภาพที่ 2-5 10 X1 = 5.213 X2 = 9.432 ภาพที่ 2-5 การเข้ารหัสแบบเลขจำนวนจริง 2.1.1.4 การหาค่าความแข็งแรง (Fitness Evaluation) โดยทั่วไปค่าความแข็งแรง ของสมาชิกแต่ละตัวในกลุ่มประชากรได้มาจากการหาค่าจุดประสงค์ของโครโมโซม นำมา ถอดรหัสให้กลายเป็นตัวแปรตัดสินใจ หลังจากนั้นค่าจุดประสงค์ของแต่ละคำตอบสามารถคำนวณ ได้จากตัวแปรตัดสินใจ โดยผ่านการใช้ฟังก์ชันจุดประสงค์ ซึ่งฟังก์ชันจุดประสงค์อาจจะเป็น ฟังก์ชันค่าใช้จ่าย (Cost Function) หรือฟังก์ชันกำไร (Profit Function) ถ้าฟังก์ชันจุดประสง์เป็น ฟังก์ชันกำไร ค่าความแข็งแรงจะแปรผันตรงกับค่าจุดประสงค์ 2.1.1.5 การคัดเลือก (Selection) เป็นการสนับสนุนให้สมาชิกที่มีความเหมาะสมจากรุ่น ปัจจุบันถูกส่งไปยังรุ่นถัดไป หลังจากผ่านกระบวนการคัดเลือกแล้ว ประชากรรุ่นใหม่ที่เกิดขึ้นจะ มาจากสมาชิกที่มีความเหมาะสมจากรุ่นก่อน ซึ่งความเหมาะสมนี้จะมาจากค่าความแข็งแรงของ สมาชิกแต่ละตัว เมื่อเทียบกับผลรวมของค่าความแข็งแรงของสมาชิกทั้งหมดในรุ่นก่อน ทำให้ สมาชิกที่มีค่าความแข็งแรงสูงมีสัดส่วนมากที่จะถูกพิจารณาหรือรับเลือกให้เข้าสู่ในรุ่นถัดไป ใน ขณะเดียวกันสมาชิกที่มีค่าความแข็งแรงต่ำก็จะมีสัดส่วนน้อยที่จะถูกพิจารณาให้เข้าสู่ในรุ่นถัดไป ในกระบวนการคัดเลือกนี้จะมีเทคนิคในการคัดเลือกอยู่หลายเทคนิคที่จะนำมาช่วยให้กระบวนการ คัดเลือกทำงานได้ดีขึ้น เช่น 2.1.1.5.1 การคัดเลือกแบบวงล้อรูเล็ต (Roulette Wheel Selection) เป็นวิธีการ คัดเลือกที่มีหลักการจากการเลียนแบบการเล่นรูเล็ต หลักการทำงานคือ กำหนดความกว้างของช่อง แต่ละช่อง ของวงล้อรูเล็ตจากค่าความแข็งแรงของสมาชิกแต่ละตัว ทำให้เป็นวงล้อรูเลตที่มีความ ลำเอียง (Bias Roulette Wheel) จากนั้นทำการกำหนดตัวชี้ตำแหน่งตายตัว (Fixed Point) และทำการ หมุนวงล้อรูเล็ต เมื่อวงล้อหยุดหมุนจะเลือกสมาชิกของกลุ่มประชากรที่มีตัวชี้ตำแหน่งชี้อยู่ ทำเช่นนี้ซ้ำจนได้สมาชิกของกลุ่มประชากรครบตามจำนวนในหนึ่งรุ่น วิธีการเลือกลักษณะนี้จะเห็น ได้ว่ามีความลำเอียงในการเลือกค่อนข้างมาก เนื่องจากถ้ามีสมาชิกของกลุ่มประชากรตัวใดที่มีค่า ความแข็งแรงสูงจะมีโอกาสในการถูกเลือกซ้ำหลายครั้ง ทำให้สมาชิกของกลุ่มประชากรภายในรุ่น ถัดไปของการทำงานมีลักษณะของสมาชิกของกลุ่มประชากรตัวนั้น ๆ หลายตัว 2.1.1.5.2 การเลือกสุ่มตัวอย่างแบบเฟ้นสุ่มสากล (Stochastic Universal Sampling Selection) จะมีหลักการคัดเลือกเหมือนกับการคัดเลือกแบบวงล้อรูเล็ต ต่างกันที่หลังจาก 11 กำหนดจุดชี้ตำแหน่งโดยการสุ่มในครั้งแรกแล้ว ทำการเลือกสมาชิกของกลุ่มประชากรที่มีตัวชี้ ตำแหน่งชี้อยู่เป็นตัวแรก ต่อจากนั้นทำการเลื่อนตัวชี้ตำแหน่งจากจุดเดิมทีละขั้น โดยที่แต่ละขั้นนั้น จะเท่ากับ 360 องศา ต่อจำนวนสมาชิกของกลุ่มประชากร แล้วทำการเลือกสมาชิกของกลุ่ม ประชากรที่มีตัวชี้ตำแหน่งชี้อยู่จนครบตามจำนวนสมาชิกของกลุ่มประชากรในหนึ่งรุ่น ดังนั้นการ คัดเลือกพันธุ์แบบการสุ่มเลือกตัวอย่างแบบเฟ้นสุ่มสากลนี้สามารถลดความลำเอียงในการคัดเลือก ได้ เนื่องจากโอกาสที่สมาชิกของกลุ่มประชากรตัวใดจะถูกเลือกซ้ำหลาย ๆ ครั้ง จะเกิดขึ้นต่อเมื่อ สมาชิกของกลุ่มประชากรตัวนั้น ๆ มีค่าความแข็งแรงสูงมาก ๆ 2.1.1.6 การสลับสายพันธุ์ (Crossover) จะนำสมาชิกของประชากรที่ผ่านการคัดเลือก มาแล้วสองตัวกำหนดให้เป็นสมาชิกรุ่นพ่อกับสมาชิกรุ่นแม่ (Parent Individual) จากนั้นทำการ แลกเปลี่ยนยีนระหว่างสมาชิกรุ่นพ่อกับสมาชิกรุ่นแม่ จะทำให้เกิดเป็นสมาชิกรุ่นลูก (Offspring Individuals) สองตัว สมาชิกรุ่นนี้จะถูกนำไปเป็นสมาชิกของประชากรรุ่นถัดไป การสุ่มเลือก สมาชิกรุ่นพ่อกับสมาชิกรุ่นแม่มาทำการสลับสายพันธุ์จะถูกกำหนดโดยความน่าจะเป็นในการสลับ สายพันธุ์ (Crossover Probability) วิธีการสลับสายพันธุ์มีอยู่ด้วยกันหลายวิธี เช่น 2.1.1.6.1 การสลับสายพันธุ์แบบหลายส่วน (N-point crossover) การกำหนดจุด และเปลี่ยนยีนระหว่างคู่โครโมโซมพ่อแม่เพื่อสร้างโครโมโซมลูกนั้น จะเกิดขึ้นที่ข้างใดข้างหนึ่ง ของตำแหน่งการแลกเปลี่ยนยีน และจะเกิดเฉพาะในช่วงของสองตำแหน่งของการแลกเปลี่ยนยีนที่ อยู่บนโครโมโซม ซึ่งตำแหน่งการแลกเปลี่ยนยีนจะเกิดจากเลขสุ่มในช่วง [1, (ความยาวของ โครโมโซม – 1)] โดยที่ความยาวของโครโมโซมนับจากจำนวนบิตที่ใช้ในการนำเสนอโครโมโซม และ n จะเป็นตัวกำหนดจำนวนของตำแหน่งของการแลกเปลี่ยน โดยที่ n ต้องมากกว่า 1 ดังภาพที่ 2-6 ถึงภาพที่ 2-8 กำหนดให้ P คือสมาชิกรุ่นพ่อแม่ และ O คือสมาชิกรุ่นลูก P1 = 1 1 1 1 1 P2 = 0 0 0 0 0 O1 = 1 1 0 0 0 O2 = 0 0 1 1 1 ภาพที่ 2-6 การสลับสายพันธุ์แบบหนึ่งส่วน (One – Point Crossover) 12 P1 = 1 1 1 1 1 P2 = 0 0 0 0 1 O1 = 1 1 0 0 1 O2 = 0 0 1 1 0 ภาพที่ 2-7 การสลับสายพันธุ์แบบสองส่วน (Two – Point Crossover) P1 = 1 1 1 1 1 1 … 1 1 1 1 1 1 P2 = 0 0 0 0 0 0 … 0 0 0 0 0 0 O1 = 1 1 1 0 0 1 … 1 0 0 1 1 1 O2 = 0 0 0 1 1 0 … 0 1 1 0 0 0 ภาพที่ 2-8 การสลับสายพันธุ์แบบหลายส่วน (N – Point Crossover) 2.1.1.6.2 การสลับสายพันธุ์แบบเอกรูป (Uniform Crossover) ในการสลับสาย พันธุ์ด้วยวิธีนี้ ยีนในแต่ละโลคัสของสมาชิกรุ่นลูกตัวหนึ่งจะได้จากการสุ่มเลือกคู่ยีนในตำแหน่งที่ ตรงกันของสมาชิกรุ่นพ่อแม่ทั้งสอง โดยกำหนดให้ความน่าจะเป็นในการเลือกยีนแต่ละตัวจาก สมาชิกรุ่นพ่อแม่มีค่าเท่ากัน เมื่อยีนหนึ่งถูกเลือกให้สมาชิกรุ่นลูกตัวหนึ่งแล้ว ยีนที่เหลือก็จะถูก ส่งผ่านไปให้สมาชิกรุ่นลูกอีกตัว การสลับสายพันธุ์แบบเอกรูปจะทำการและเปลี่ยนยีนเป็นอิสระ ต่อตำแหน่งของยีนนั้น ทำให้โอกาสที่แต่ละโลคัสจะถูกแลกเปลี่ยนยีนมีโอกาสเท่า ๆ กัน ซึ่งเป็น การเพิ่มความสามารถในการสำรวจพื้นที่การค้นหา ซึ่งวิธีนี้เหมาะที่จะนำไปใช้กับกลุ่มประชากรที่ มีขนาดเล็ก หรือใช้ในขณะที่สมาชิกในกลุ่มประชากรมีลักษณะคล้ายคลึงกันจนนำไปสู่การได้ คำตอบที่ดีเฉพาะที่ การสลับสายพันธุ์แบบนี้จึงถือได้ว่าเป็นเครื่องมือหนึ่งที่ช่วยเพิ่มความแตกต่าง ในหมู่ประชากร ดังภาพที่ 2-9 โครโมโซมเดิม โครโมโซมที่สลับสายพันธุ์แล้ว 1 1 1 1 1 0 0 0 0 0 ภาพที่ 2-9 การสลับสายพันธุ์แบบเอกรูป 1 0 0 1 0 0 1 1 0 1 13 2.1.1.7 การกลายพันธุ์ (Mutation) เป็นการแลกเปลี่ยนยีนภายในสมาชิกแต่ละตัวเท่านั้น จะไม่เกิดขึ้นกับสมาชิกทั้งหมด โดยขึ้นอยู่กับความน่าจะเป็น (Mutation Probability) เทคนิคการ กลายพันธุ์มีอยู่หลายวิธี เช่น 2.1.1.7.1 การกลายพันธุ์แบบกลับบิต (Bit-Flipped Mutation) เป็นเทคนิคการ กลายพันธุ์ที่ใช้กับ โครโมโซมแบบเลขฐานสอง สามารถทำได้โดยการกลับค่าบิตเป็นค่าตรงกันข้าม จากค่าเดิม (Complement) คือจาก 0 เป็น 1 หรือ 1 เป็น 0 จากตำแหน่งที่สุ่มได้ตามค่าความน่าจะเป็น ของการกลายพันธุ์ ดังภาพที่ 2-10 กำหนดให้ P คือสมาชิกรุ่นพ่อแม่ และ O คือสมาชิกรุ่นลูก P = 0 1 1 1 0 1 0 0 O = 0 1 1 1 0 1 1 0 ภาพที่ 2-10 การกลายพันธุ์แบบกลับบิต 2.1.1.7.2 การกลายพันธุ์แบบผกผัน (Inversion Mutation) เป็นการสลับ ตำแหน่งแบบหลังไปหน้า โดยสุ่มเลือกสมาชิกมาหนึ่งตัว สุ่มเลือกช่วงที่จะทำการกลายพันธุ์ และ ทำการสลับตำแหน่งภายในช่วงการตัด ดังภาพที่ 2-11 กำหนดให้ P คือสมาชิกรุ่นพ่อแม่ และ O คือ สมาชิกรุ่นลูก P = 1 2 3 4 5 6 7 8 O = 1 2 6 5 4 3 7 8 ภาพที่ 2-11 การกลายพันธุ์แบบผกผัน 2.1.1.7.3 การกลายพันธุ์แบบแทรก (Insertion Mutation) เป็นการเปลี่ยน ตำแหน่งโดยการแทรกตำแหน่ง ซึ่งจะสุ่มเลือกสมาชิกมาหนึ่งตัว สุ่มเลือกช่วงที่ต้องการจะแทรก สุ่มเลือกยีนที่จะนำมาแทรก แล้วนำยีนที่สุ่มได้มาแทรกตรงที่สุ่มเลือกช่วงที่ต้องการแทรก ดังภาพที่ 2-12 กำหนดให้ P คือสมาชิกรุ่นพ่อแม่ และ O คือสมาชิกรุ่นลูก P = 1 2 3 4 5 6 7 8 O = 1 2 6 3 4 5 7 8 ภาพที่ 2-12 การกลายพันธุ์แบบแทรก 14 2.1.1.7.4 การกลายพันธุ์แบบเคลื่อนตำแหน่ง (Displacement Mutation) เป็น การเปลี่ยนตำแหน่งโดยแทรกเป็นช่วงของตำแหน่ง ซึ่งจะสุ่มเลือกสมาชิกมาหนึ่งตัว สุ่มเลือก ตำแหน่งที่ต้องการจะแทรก สุ่มเลือกช่วงตำแหน่งยีนที่จะนำมาแทรก แล้วนำช่วงที่สุ่มได้ มาแทรก หน้าตำแหน่งที่สุ่มไว้ ดังภาพที่ 2-13 กำหนดให้ P คือสมาชิกรุ่นพ่อแม่ และ O คือสมาชิกรุ่นลูก P = 1 2 3 4 5 6 7 8 O = 1 2 6 7 3 4 5 8 ภาพที่ 2-13 การกลายพันธุ์แบบเคลื่อนตำแหน่ง 2.1.1.7.5 การกลายพันธุ์แบบสลับตำแหน่ง (Reciprocal Exchange Mutation) เป็นการเปลี่ยนตำแหน่งยีนสองยีน ซึ่งจะสุ่มเลือกสมาชิกมาหนึ่งตัว สุ่มเลือกตำแหน่งที่ต้องการจะ สลับตำแหน่งยีนสองตำแหน่ง แล้วสลับตำแหน่งระหว่างยีนทั้งสองตัวที่สุ่มได้ ดังภาพที่ 2-14 กำหนดให้ P คือสมาชิกรุ่นพ่อแม่ และ O คือสมาชิกรุ่นลูก P = 1 2 3 4 5 6 7 8 O = 1 2 6 4 5 3 7 8 ภาพที่ 2-14 การกลายพันธุ์แบบสลับตำแหน่ง 2.1.2 ระบบอาณาจักรมด (Ant Colony System) ถูกคิดค้นโดย Marco Dorigo และ Vittorio Maniezzo ซึ่งเป็นการค้นหาคำตอบที่เหมาะสมที่สุดแบบสุ่ม ได้มาจากพฤติกรรมการหาอาหารของ มด คือมดทุกตัวจะสร้างเส้นทางจากรังไปยังแหล่งอาหารทางไหนก็ได้โดยวิธีการเดาสุ่ม และทิ้ง สารฟีโรโมนไว้ตามทางที่มันเดินผ่าน แต่เมื่อพบร่องรอยของสารฟีโรโมน มดก็จะเดินตามสาร ฟีโรโมนนั้นไปจนพบแหล่งอาหาร แล้วมันก็จะกลับรังในเส้นทางที่มีสารฟีโรโมนมาก พร้อมกับ ทิ้งสารฟีโรโมนลงไปอีก เพื่อให้มดตัวอื่นที่อยู่ใกล้เคียงได้กลิ่นสารฟีโรโมน มดก็จะเดินไปตาม เส้นทางนั้นและเพิ่มสารฟีโรโมนในเส้นทางนั้นมากขึ้นอีก เมื่อเวลาผ่านไปสารฟีโรโมนที่อยู่ใน เส้นทางอื่นก็จะระเหยไปทำให้เหลือเส้นทางที่สั้นที่สุดที่มดจะเดินเพียงเส้นทางเดียว 2.1.2.1 พฤติกรรมการหาอาหารของมด โดยธรรมชาติแล้ว มดจะพยายามหาเส้นทางที่ สั้นที่สุดจากแหล่งอาหารกลับไปยังรังของมัน โดยอาศัยสารฟีโรโมนที่มดตัวอื่นทิ้งไว้ก่อนหน้านี้ 15 และเมื่อมดตัวหลังเดินตามมาก็จะทิ้งสารฟีโรโมนลงไปอีก ยิ่งความเข้มข้นของสารฟีโรโมนบน เส้นทางไหนที่มาก ก็มีความน่าจะเป็นที่มดแต่ละตัวจะเลือกเดินบนเส้นทางนั้นมากขึ้นด้วย ภาพที่ 2-15 เส้นทางระหว่างรังมดกับแหล่งอาหาร ภาพที่ 2-16 เส้นทางที่มดเลือกเดินทางจากแหล่งอาหารกลับไปยังรังมด จากภาพที่ 2 – 15 แสดงเส้นทางระหว่างรังมดกับแหล่งอาหาร เริ่มต้นจากแบ่งมดเป็น 2 กลุ่ม เท่า ๆ กันแล้วให้เดินไปใน 2 เส้นทาง คือ เส้นทางบนกับเส้นทางล่าง แต่เนื่องจากเส้นทางล่างสั้น กว่าเส้นทางบน เมื่อเวลาผ่านไปเส้นทางด้านล่างจะมีจำนวนสารฟีโรโมนที่มดทิ้งไว้มากกว่า ด้านบน เพราะเส้นทางที่สั้นกว่ามดจะเดินผ่านมามากกว่า จากภาพที่ 2 – 16 แสดงเส้นทางที่มดเลือก เดินทางจากแหล่งอาหารกลับไปยังรังมด จะเห็นได้ว่าเมื่อมดพบอาหารแล้วจึงเลือกเส้นทางที่มี ปริมาณสารฟีโรโมนมากกว่ากลับไปยังรังของมัน 16 2.1.2.2 อัลกอริทึมของระบบอาณาจักรมด ดังภาพที่ 2-17 ภาพที่ 2-17 อัลกอริทึมของระบบอาณาจักรมด 2.1.2.3 เปรียบเทียบประสิทธิภาพของอาณาจักรมดกับจีเนติกอัลกอริทึม 2.1.2.3.1 การสุ่มหาเส้นทางของมด ไม่สามารถแก้ปัญหาได้ทุกอย่าง เมื่อ สภาพแวดล้อมเปลี่ยนไป กลุ่มมดที่เคยสามารถหาคำตอบที่เหมาะสมที่สุดในปัญหาหนึ่ง อาจไม่พบ คำตอบที่เหมาะสมที่สุดในอีกปัญหาหนึ่งก็ได้ 2.1.2.3.2 มดตัวที่ได้คำตอบที่ดีที่สุดอาจไม่ใช่คำตอบที่เหมาะสมที่สุดของ ปัญหานั้น 2.1.3 การหาค่าความเหมาะสมแบบกลุ่มอนุภาค (Particle Swarm Optimization : PSO) ซี่งถูก คิดค้นโดย Russell Eberhart และ James Kennedy ในปี 1995 เป็นการหาที่เหมาะสมที่สุดแบบกลุ่ม อนุภาคโดยใช้เทคนิคการหาค่าเหมาะสมที่สุดแบบสุ่ม (Stochastic) เป็นวิธีการหาค่าความเหมาะสม โดยอาศัยพื้นฐานของความน่าจะเป็น ทั้งคู่ได้รับแรงจูงใจมาจากพฤติกรรมทางสังคมในการอพยพ ของฝูงนก และการเรียนรู้ของฝูงปลา หลักการของการหาค่าความเหมาะสมแบบกลุ่มอนุภาค คือ เรียนรู้สถานการณ์และใช้ข้อมูล ร่วมกัน ทำให้สามารถแก้ปัญหาเกี่ยวกับการหาคำตอบที่เหมาะสม ในการหาค่าความเหมาะสมแบบ กลุ่มอนุภาคนั้น แต่ละคำตอบที่เป็นไปได้จะมีค่าความเหมาะสมกำกับไว้ (Fitness Value) ซึ่งบริเวณ Initialization Repeat /* มดทุกตัวเดินครบรอบ */ Each ant is positioned on an arbitrary staring node Repeat /* มดแต่ละตัวเดินครบรอบ */ Each ant moves to a next node according to the state transition rule Apply the local pheromone updating rule Until all ants have completed their tours Apply the global pheromone updating rule Until end conditions 17 ที่ใช้ในการค้นหาแต่ละรอบ เรียกว่าพาร์ทิเคิล (Particle) โดยพาร์ทิเคิลแต่ละตัวจะมีแนวโน้มที่จะ ติดตามพาร์ทิเคิลเฉพาะตัวที่มีข้อมูลที่ดีและเหมาะสมที่สุดขณะนั้น 2.1.3.1 ขั้นตอนการหาค่าความเหมาะสมแบบกลุ่มอนุภาค สมมติสถานการณ์สร้าง แบบจำลองการค้นหาอาหารของฝูงนก ถ้าในบริเวณที่ต้องการหามีอาหารเพียงที่เดียว นกทั้งฝูงจะ ไม่รู้ว่าอาหารอยู่ที่ไหนแต่เมื่อผ่านการค้นหาในแต่ละรอบ ถึงจะรู้ว่าอาหารอยู่ใกล้นกตัวไหน แล้ว ตามนกตัวที่อยู่ใกล้อาหารมากที่สุด ในการประเมินค่าความเหมาะสมจะใช้สมการต่อไปนี้ Eval = [ (presentx-xg)2 + (presenty-yg) ]0.5 (2-3) โดยที่ Eval คือค่าที่ประเมินได้จากตำแหน่งของนก ณ ตำแหน่งปัจจุบันจากข้อมูลหรือ คำตอบที่ดีที่สุดในหน่วยความจำ และค่า xg , yg คือ ตำแหน่งของคำตอบที่ดีที่สุดในแต่ละพาร์ทิเคิล ดังนั้นถ้าหาก presentx = xg และ presenty = yg แสดงว่า ฝูงนกหาเป้าหมายที่ต้องการได้แล้ว วิธีการหาค่าความเหมาะสมแบบกลุ่มอนุภาคนั้น จะเริ่มต้นจากการสุ่มค่าของพาร์ทิเคิลก่อน ต่อจากนั้นจะหาเส้นทางที่เหมาะสมที่สุด โดยการปรับปรุงประชากรในแต่ละรุ่น แล้วพาร์ทิเคิลจะ ปรับเปลี่ยนโดยใช้ค่าที่ดี 2 ค่า ซึ่งค่าแรก คือ pBest เป็นค่าความเหมาะสมเท่าที่มี ณ ขณะนั้น ส่วน ค่าที่สองคือค่า gBest เป็นค่าความเหมาะสมที่สุด ณ ขณะนั้นของประชากรทั้งหมดในรุ่น ถ้าหากว่า พาร์ทิเคิลเลือกใช้ค่าความเหมาะสมของเพื่อนบ้านซึ่งเป็นค่าที่ดีกว่าค่า pBest แต่เป็นค่าที่ดีเฉพาะที่ เรียกค่านี้ว่า lBest เมื่อได้ค่าที่ดี 2 ค่าแล้ว คือ pBest และ gBest แต่ละพาร์ทิเคิลจะปรับค่าความเร็ว และตำแหน่ง โดยใช้สมการ (2-4) และ (2-5) ตามลำดับ V (t + 1) = V (t) + C1 rand (.1) (pBest (t) – present (t) + C2 rand (.2) (gBest (t) – present (t)) (2-4) present (t+1) = present (t) + V(t) (2-5) โดยที่ V(t) เป็นค่าความเร็วของพาร์ทิเคิลโดยต้องปรับทั้งในแนวแกน x คือ Vx(t) และ แนวแกน y คือ Vy (t) ณ เวลา t ส่วน present (t) คือข้อมูลหรือคำตอบที่ดี ณ ตำแหน่งปัจจุบันของ พาร์ทิเคิล (เวลา t) ซึ่งต้องปรับทั้งแกน x คือ presentx (t) และแกน y คือ presenty (t) สำหรับค่า rand (.1) และ rand (.2) เป็นค่าสุ่มมีค่าระหว่าง 0 - 1 และ C1 , C2 เป็นค่าแฟกเตอร์ ของการเรียนรู้ โดยที่ค่า C1 มีผลต่ออัตราความเร็วในการเข้าหาคำตอบที่ดีเท่าที่รู้ของตำแหน่งปัจุบัน ส่วนค่า C2 มีผลต่อการลู่เข้าสู่คำตอบที่ดีที่สุดจากตำแหน่งปัจจุบันเห็นได้ว่าตัวแปรทั้ง 2 มีผลอย่าง มากต่อการลู่เข้าสู่คำตอบ และอัตราความเร็วในการลู่เข้าสู่เป้าหมาย ดังนั้นการเลือกค่าที่เหมาะสม สำหรับแต่ละตัวแปรจึงมีความสำคัญอย่างยิ่ง 18 ถ้าหากค่า C1 และ C2 มีค่าสูงทั้งคู่ การลู่เข้าสู่คำตอบจะเร็ว แต่ถ้า C1 และ C2 มีค่าต่ำทั้งคู่แต่ละ กลุ่มย่อยจะลู่เข้าสู่คำตอบอย่างประสานงานกัน แม้ว่าความเร็วจะช้า แต่ก็จะได้รับคำตอบที่ เหมาะสมที่สุด ถ้าค่า C1 สูงกว่าค่า C2 ทำให้การค้นหากระจัดกระจาย ไม่เป็นรูปแบบที่สอดคล้อง กันทำให้ไม่สามารถลู่เข้าสู่คำตอบได้ แต่ถ้าค่า C2 สูงกว่าค่า C1 จะเป็นการลู่เข้าสู่คำตอบอย่าง รวดเร็วแต่ส่วนใหญ่คำตอบที่ได้จะเป็นคำตอบที่เหมาะสมเฉพาะที่ (Local) ไม่ใช่คำตอบที่ เหมาะสมที่สุดของทั้งหมด (Global) ดังนั้นการสุ่มค่า C1 และ C2 ที่เหมาะสม จะขึ้นอยู่กับปัญหา โดยปกติมีค่าอยู่ระหว่าง 0 – 4 แต่ที่นิยมใช้กันคือ C1 = C2 = 2 2.1.3.2 อัลกอริทึมของการหาค่าความเหมาะสมแบบกลุ่มอนุภาค ภาพที่ 2-18 อัลกอริทึมของการหาค่าความเหมาะสมแบบกลุ่มอนุภาค 2.1.3.3 เปรียบเทียบประสิทธิภาพของการหาค่าเหมาะสมแบบกลุ่มอนุภาคกับจีเนติก อัลกอริทึม 2.1.3.3.1 การหาค่าเหมาะสมแบบกลุ่มอนุภาคมีความคล้ายกับจีเนติก อัลกอริทึมที่เริ่มจากกำหนดค่าเริ่มต้นของประชากรแบบสุ่มแล้วหาค่าเหมาะที่สุดโดยการปรับค่าใน แต่ละรุ่น แต่ที่การหาค่าความเหมาะสมแบบกลุ่มอนุภาคแตกต่างกับจีเนติกอัลกอริทึมก็คือ ไม่มีตัว For each particle /*กำหนดค่าเริ่มต้น*/ Initialize particle End Do For each particle /*ประเมินค่าความเหมาะสมของแต่ละ particle*/ Calculate fitness value If the fitness value is better than the best fitness value (pBest) in history then set current value as the new pBest End Choose the particle with the best fitness value of all the particles as the gBest For each particle /*ปรับข้อมูลและความเร็วในการมุ่งสู่เป้าหมาย*/ Calculate particle velocity according equation (2-4) Update particle position according equation (2-5) While maximum iterations or minimum error criteria is not attained 19 ดำเนินการ (Operation) เช่น การสลับสายพันธุ์ (Cross Over) และ การกลายพันธุ์ (Mutation) ซึ่งการ หาค่าความเหมาะสมแบบกลุ่มอนุภาคในที่นี้หมายถึง คำตอบที่เป็นไปได้ในการหาคำตอบที่ เหมาะสมที่สุดของฝูงนก 2.1.3.3.2 การหาค่าความเหมาะสมแบบกลุ่มอนุภาคจะลู่เข้าสู่เป้าหมายโดยใช้ ค่าความเหมาะสมที่ดีที่สุดค่าเดียวเลย ทำให้มีโอกาสผิดพลาดได้ ถ้าค่านั้นไม่ใช่ค่าที่ดีที่สุดของ ทั้งหมด แต่เป็นค่าที่ดีที่สุดเฉพาะที่ 2.2 จีเนติกอัลกอริทึมแบบหลายจุดประสงค์ (Multi Objective Genetic Algorithm) ปัญหาโดยส่วนใหญ่ไม่ว่าจะเป็นทางด้านอุตสาหกรรมหรือวงการธุรกิจหรือแวดวงวิชาการ นั้น จะเป็นแบบฟังก์ชันหลายจุดประสงค์ และแต่ละจุดประสงค์มักจะมีความขัดแย้งกัน ซึ่งปัญหาที่ มีหลายจุดประสงค์และขัดแย้งกันเองนั้น รูปแบบคำตอบที่ดีที่สุดของปัญหานั้น ๆ จะมีลักษณะ พิเศษ คือ เป็นกลุ่มคำตอบที่ดีที่สุด โดยที่คำตอบแต่ละคำตอบนั้นเป็นคำตอบที่ดีที่สุดของปัญหา และไม่มีคำตอบอื่นครอบงำ (Dominate) เลย จีเนติกอัลกอริทึมแบบหลายจุดประสงค์ที่นำเสนอโดย Fonseca และ Flemming (Fonseca and Flemming, 1993) จะใช้หลักการของการถูกครอบงำในการกำหนดค่าความแข็งแรงให้กับ สมาชิกของกลุ่มประชากร ซึ่งในการพิจารณาการถูกครอบงำนั้นสามารถกำหนดได้ด้วยเงื่อนไข เช่น สมมติต้องการหาคำตอบที่น้อยที่สุดของปัญหาที่มี n จุดประสงค์ เวคเตอร์จุดประสงค์ a จะ ครอบงำเวคเตอร์จุดประสงค์ b ก็ต่อเมื่อ บางค่าของเวคเตอร์จุดประสงค์ a น้อยกว่าบางค่าของ เวคเตอร์จุดประสงค์ b หรือได้ตามสมการต่อไปนี้ 1,..., ap 1 (3-5) 30 อัลกอริทึมของ f1 ดังภาพที่ 3-5 ภาพที่ 3-5 อัลกอริทึมของ f1 สมการของ f2 คือ ใน 1 สัปดาห์ผู้สอนจะสอนวิชาที่กำหนดเท่ากับจำนวนคาบของวิชานั้น กำหนดให้ Tl หมายถึง ผู้สอนคนที่ l เมื่อ l = 1,…,L PBlij หมายถึง การสอนของผู้สอนคนที่ l ในวันที่ i คาบที่ j เมื่อ l = 1,…,L, i = 1,…,R และ j = 1 … M PCl หมายถึง จำนวนคาบที่สอนของผู้สอนคนที่ l เมื่อ l = 1,…,L TPl หมายถึง จำนวนคาบที่ต้องสอนของผู้สอนคนที่ l เมื่อ l = 1,…,L SDli หมายถึงวันที่มีการสอนของอาจารย์คนที่ l วันที่ i เมื่อ l = 1,…,L และ i = 1,…,R For i = 1 To R For j = 1 To M For l = 1 To L count = 0 For k = 1 To N If T(l) = T(i,j,k) Then count = count + 1 End If Next k If count = 1 Then f1= f1 + count End If If count > 1 Then f1= f1 - count + 1 End If Next l Next j Next i 31 ซึ่งค่า PB มีสมาชิกดังสมการที่ 3-6 PB1 = {PB1,1,1 , PB1,1,2 , PB1,1,3 , … , PB1,1,M , PB1,2,1 , PB1,2,2 , PB1,2,3 , … ,PB1,2,M , PB1,3,1 , PB1,3,2 , PB1,3,3 , … , PB1,3,M ,… , PB1,R,1 , PB1,R,2 ,PB1,R,3 , … , PB1,R,M} PB2 = {PB2,1,1 , PB2,1,2 , PB2,1,3 , … , PB2,1,M , PB2,2,1 , PB2,2,2 , PB2,2,3 , … ,PB2,2,M , PB2,3,1 , PB2,3,2 , PB2,3,3 , … , PB2,3,M ,… , PB2,R,1 , PB2,R,2 ,PB2,R,3 , … , PB2,R,M} . . . . . . PBL = {PBL,1,1 , PBL,1,2 , PBL,1,3 , … , PBL,1,M , PBL,2,1 , PBL,2,2 , PBL,2,3 , … ,PBL,2,M , PBL,3,1 , PBL,3,2 , PBL,3,3 , … , PBL,3,M , … , PBL,R,1 , PBL,R,2 ,PBL,R,3 , … , PBL,R,M} (3-6) ตรวจสอบว่าผู้สอนแต่ละคนมีสอนในคาบใดบ้าง ดังสมการที่ 3-7 0 ; if Tl . Tijk PBlij = 1 ; if Tl = Tijk (3-7) แล้วนำค่า PBlij ที่ได้มารวมกัน ดังสมการที่ 3-8 PCl = lij Mj R i . . PB =1 =1 (3-8) สมการของ f2 ที่ได้เป็นดังสมการที่ 3-9 1 ; if PCl = TPl f2 = -1 ; if PCl . TPl (3-9) 32 อัลกอริทึมของ f2 ดังภาพที่ 3-6 ภาพที่ 3-6 อัลกอริทึมของ f2 สมการ f3 คือ ใน 1 สัปดาห์ผ้สอนจะมีจำนวนวันที่สอนเท่ากับจำนวนครั้งของวิชานั้น กำหนดให้ Tl หมายถึง ผู้สอนคนที่ l เมื่อ l = 1,…,L DBlij หมายถึง การสอนของผู้สอนคนที่ l ในวันที่ i คาบที่ j เมื่อ l = 1,…,L, i = 1,…,R และ j = 1 … M DCl หมายถึง จำนวนวันที่สอนแต่ละกลุ่มของผู้สอนคนที่ l เมื่อ l = 1,…,L TDl หมายถึง จำนวนวันที่ต้องสอนแต่ละกลุ่มของผู้สอนคนที่ l เมื่อ l = 1,…,L SDli หมายถึงวันที่มีการสอนของอาจารย์คนที่ l วันที่ i เมื่อ l = 1,…,L และ i = 1 … R For k = 1 To N For l = 1 To L count = 0 For i = 1 To R For j = 1 To M If T(l) = T(i,j,k) Then count = count + 1 End If Next j Next i If count = TPl Then f2 = f2 + 1 End If If count <> TPl Then f2 = f2 - 1 End If Next l Next k 33 ซึ่งค่า DBl มีสมาชิกดังนี้ DBl,1 = {DBl,1,1 ,DBl,1,2 , DBl,1,3 , … , DBl,1,M} DBl,2 = {DBl,2,1 ,DBl,2,2 , DBl,2,3 , … , DBl,2,M} DBl,3 = {DBl,3,1 ,DBl,3,2 , DBl,3,3 , … , DBl,3,M} . . . . . . DBl,R = {DBl,R,1 ,DBl,R,2 , DBl,R,3 , … , DBl,R,M} (3-10) ตรวจสอบว่าผู้สอนแต่ละคนมีสอนในวันนั้น ๆ หรือไม่ ดังสมการที่ 3-11 ถึงสมการที่ 3-13 0 ; if Tl . Tijk DBlij = 1 ; if Tl = Tijk (3-11) 0 SDli = 1 ; if .=. Mj lij DB 1 1 (3-12) DCl = .= R i li SD 1 (3-13) สมการของ f3 ที่ได้ดังสมการที่ 3-14 1 ; if DCl = TDl f3 = -1 ; if DCl . TDl (3-14) 34 อัลกอริทึมของ f3 ดังภาพที่ 3-7 ภาพที่ 3-7 อัลกอริทึมของ f3 สมการ f4 คือ ถ้ามีการกำหนดคาบไว้ก่อน ผู้สอนต้องสอนในคาบนั้น กำหนดให้ Tl หมายถึง ผู้สอนคนที่ l เมื่อ l = 1,…,L LPlij หมายถึง คาบที่ถูกกำหนดให้สอนก่อน เมื่อ l=1,…L, I=1,…,R และ j=1…M NPlij หมายถึง จำนวนที่ผู้สอนได้สอนในคาบที่กำหนด เมื่อ l=1,…,L, i=1,…,R และ j=1,…,M ตรวจสอบว่าผู้สอนสอนในคาบที่กำหนดหรือไม่ ดังสมการที่ 3-15 0 ; if LPlij . Tijk NPlij = 1 ; if LPlij = Tijk (3-15) For k = 1 To N For l = 1 To L count = 0 For i = 1 To R For j = 1 To M If T(l) = T(i,j,k) Then count = count + 1 goto #1 End If Next j #1: Next i If count = TDl Then f3 = f3 + 1 End If If count <> TDl Then f3 = f3- 1 End If Next l Next k 35 สมการของ f4 ที่ได้ดังสมการที่ 3-16 f4 = 1 - . .. . . .. .. . .= = = Mj lij R i L l NP 1 1 1 (3-16) อัลกอริทึมของ f4 ดังภาพที่ 3-8 ภาพที่ 3-8 อัลกอริทึมของ f4 สมการ f5 คือ ถ้ามีการกำหนดคาบไม่ว่างไว้ก่อน ผู้สอนจะต้องไม่ได้สอนในคาบที่ไม่ว่าง กำหนดให้ Tl หมายถึง ผู้สอนคนที่ l เมื่อ l = 1,…,L LSlij หมายถึง คาบที่ถูกกำหนดให้ไม่ว่าง เมื่อ l=1,…,L, i=1,…,R, j=1,…,M NSlij หมายถึง จำนวนที่ผู้สอนได้สอนในคาบที่กำหนดให้ไม่ว่าง เมื่อ l=1,…,L, i=1,…,R และ j=1,…,M ตรวจสอบว่าผู้สอนสอนในคาบที่ไม่ว่างหรือไม่ ดังสมการที่ 3-17 0 ; if LSlij . Tijk NSlij = 1 ; if LSlij = Tijk (3-17) For i = 1 To R For j = 1 To M For l = 1 To L count = 0 For k = 1 To N If LPlij = NPlij Then f4 = f4 + 1 End If Next k Next l Next j Next i 36 สมการของ f5 ที่ได้ดังสมการที่ 3-18 f5 = 1 - . .. . . .. .. . .= = = Mj lij R i L l NS 1 1 1 (3-18) อัลกอริทึมของ f5 ดังภาพที่ 3-9 ภาพที่ 3-9 อัลกอริทึมของ f5 3.4.5 การหาค่าลำดับ (Ranked Value) หาได้จากการนำค่าของแต่ละจุดประสงค์มาจัดลำดับ โดยเรียงจากมากไปน้อย เนื่องจากโครโมโซมที่มีความเหมาะสมมากกว่าจะมีค่าความแข็งแรง มากกว่า มีขั้นตอนดังนี้ 3.4.5.1 ถ้าในโครโมโซมที่ 1 มีค่า f1 = 10 f2 = 40 f3 = 30 โครโมโซมที่ 2 มีค่า f1 = 20 f2 = 50 f3 = 20 โครโมโซมที่ 3 มีค่า f1 = 30 f2 = 30 f3 = 10 For i = 1 To R For j = 1 To M For l = 1 To L count = 0 For k = 1 To N If LSlij = NSlij Then f5 = f5 - 1 End If Next k Next l Next j Next i 37 3.4.5.2 จัดลำดับในแต่ละค่าจุดประสงค์ โครโมโซมที่ 1 มีค่า f1 = 10 โครโมโซมที่ 2 มีค่า f1 = 20 โครโมโซมที่ 3 มีค่า f1 = 30 10, 20, 30 จัดลำดับได้ตามลำดับดังนี้ 3, 2, 1 โครโมโซมที่ 1 มีค่า f2 = 40 โครโมโซมที่ 2 มีค่า f2 = 50 โครโมโซมที่ 3 มีค่า f2 = 30 40, 50, 30 จัดลำดับได้ตามลำดับดังนี้ 2, 1, 3 โครโมโซมที่ 1 มีค่า f3 = 30 โครโมโซมที่ 2 มีค่า f3 = 20 โครโมโซมที่ 3 มีค่า f3 = 10 30, 20, 10 จัดลำดับได้ตามลำดับดังนี้ 1, 2, 3 3.4.6 หาค่าความแข็งแรง (Fitness Value) นำค่าลำดับที่ได้จากการหาค่าลำดับมารวมกัน ดังนี้ โครโมโซมที่ 1 มีค่าความแข็งแรง = 3 + 2 + 1 = 6 โครโมโซมที่ 2 มีค่าความแข็งแรง = 2 + 1 + 2 = 5 โครโมโซมที่ 3 มีค่าความแข็งแรง = 3 + 3 + 3 = 7 ค่าความแข็งแรงที่จะถูกเลือก เพื่อนำไปใช้เป็นโครโมโซมในรุ่นถัดไปจะเลือกจาก โครโมโซมที่มีค่าความแข็งแรงน้อยที่สุด เพราะการจัดลำดับค่าที่มากที่สุด จะมีลำดับเป็น 1 ดังนั้น โครโมโซมที่มีค่าความแข็งแรงน้อยที่สุด จึงเป็นโครโมโซมที่ดีที่สุดที่หาได้ในรุ่นปัจจุบัน 3.4.7 การคัดเลือก (Selection) จะคัดเลือกโครโมโซมที่มีความเหมาะสมที่จะนำไปใช้เป็น โครโมโซมพ่อ-แม่ (Mating Pool) โดยใช้วิธีวงล้อรูเล็ต (Roulette Wheel) ในการเลือก โครโมโซมขึ้นมา มีขั้นตอนดังนี้ 3.4.7.1 หาค่าความน่าจะเป็นที่สุ่มได้ในแต่ละครั้งของแต่ละโครโมโซม (pSelect) 3.4.7.2 หาค่าความถี่สะสม (q) ของค่าความน่าจะเป็นของแต่ละโครโมโซม 3.4.7.3 สร้างเลขสุ่มจำนวนจริง (r) ในช่วง [0.0 – 1.0] 3.4.7.4 เลือกโครโมโซมลำดับที่ r ซึ่ง r มีค่าอยู่ระหว่าง qi-1 และ qi 38 นำเข้าข้อมูล ประมวลผล แสดงผล 3.4.8 การสลับสายพันธุ์ (Crossover) จะนำโครโมโซมที่ได้จากการคัดเลือกมา 2 โครโมโซม แล้วทำการสุ่มตำแหน่งที่จะสลับสาย พันธุ์ มีขั้นตอนดังนี้ 3.4.8.1 กำหนดค่าความน่าจะเป็นของการสลับสายพันธุ์ (Probability Crossover : Pc) เป็น 0.5 ให้เป็นค่ากลาง ๆ ไว้ เพื่อให้มีโอกาสในการสลับสายพันธุ์และไม่สลับสายพันธุ์เท่ากัน 3.4.8.2 สุ่มค่าขึ้นมาในช่วง [0.0 – 1.0] 3.4.8.3 ถ้าค่าที่สุ่มได้น้อยกว่าหรือเท่ากับค่าความน่าจะเป็นของการสลับสายพันธุ์ จะ ทำการสลับสายพันธุ์ 3.4.8.4 การสลับสายพันธุ์จะทำได้โดย 3.4.8.4.1 สุ่มตำแหน่งที่จะสลับสายพันธุ์ จะมีค่าตั้งแต่ 1 ถึง ความยาว โครโมโซม - 1 3.4.8.4.2 แลกเปลี่ยนค่าในแต่ละบิต ตั้งแต่ตำแหน่งที่จะสลับสายพันธุ์ถึง ความยาวโครโมโซม 3.4.9 การกลายพันธุ์ (Mutation) จะนำโครโมโซมที่ได้จากการคัดเลือกมา 1 โครโมโซม แล้วทำการสุ่มตำแหน่งที่จะกลายพันธ์ แล้วสุ่มค่าใหม่ขึ้นมาแทนค่าเดิม ซึ่งในงานวิจัยนี้จะใช้ค่า ความน่าจะเป็นของการกลายพันธุ์ (Probability Mutation : Pm) เป็น 0.1 เพราะถ้าน้อยกว่านี้ โอกาสในการกลายพันธุ์จะน้อยเกินไปทำให้โอกาสที่จะได้โครโมโซมที่เหมาะสมช้าลง แต่ถ้ามาก เกินไปโอกาสในการกลายพันธุ์มีมาก โครโมโซมใหม่ที่ได้อาจมีค่าความเหมาะสมน้อยลง ค่าความ น่าจะเป็นในการกลายพันธุ์จึงควรมีค่าน้อย ๆ เพื่อให้มีโอกาสในการกลายพันธุ์ด้วย 3.5 ขั้นตอนของการออกแบบหน้าจอ ระบบจัดตารางสอนของโรงเรียน จากขั้นตอนการศึกษาข้อมูลที่ใช้ในการจัดตารางสอน การเตรียมข้อมูล ศึกษาการทำงานและ ออกแบบอัลกอริทึมแล้วนั้น สามารถออกแบบหน้าจอจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ สำหรับการแก้ปัญหาการจัดตารางสอนของโรงเรียนได้ดังภาพที่ 3-10 ภาพที่ 3-10 ขั้นตอนการออกแบบหน้าจอระบบจัดตารางสอนของโรงเรียน 39 3.5.1 ส่วนของการนำเข้าข้อมูลแบ่งเป็น 4 ส่วนหลัก ๆ ดังนี้ 3.5.1.1 ฐานข้อมูลผู้สอน เป็นส่วนของการนำเข้าข้อมูลผู้สอนโดยมีรายละเอียด คือ รหัสผู้สอน ชื่อผู้สอน และห้องที่ดูแล ดังภาพที่ 3-11 ภาพที่ 3-11 การออกแบบฐานข้อมูลผู้สอน 3.5.1.2 ฐานข้อมูลกลุ่มเรียน เป็นส่วนของการนำเข้าข้อมูลจำนวนกลุ่มเรียนในแต่ละ ระดับชั้น ดังภาพที่ 3-12 3.5.1.3 ฐานข้อมูลห้องเรียน เป็นส่วนของการนำเข้าข้อมูลห้องเรียนโดยมีรายละเอียด คือ รหัสห้องเรียน และชื่อห้องเรียน ดังภาพที่ 3-13 3.5.1.4 ฐานข้อมูลวิชาเรียน เป็นส่วนของการนำเข้าข้อมูลวิชาเรียนโดยมีรายละเอียด คือ รหัสวิชา ชื่อวิชา จำนวนคาบ และจำนวนครั้ง ดังภาพที่ 3-14 ภาพที่ 3-12 การออกแบบฐานข้อมูลกลุ่มเรียน ฐานข้อมูลกลุ่มเรียน จำนวนกลุ่มเรียนระดับชั้นที่ 1 จำนวนกลุ่มเรียนระดับชั้นที่ 2 จำนวนกลุ่มเรียนระดับชั้นที่ 3 จำนวนกลุ่มเรียนระดับชั้นที่ 4 จำนวนกลุ่มเรียนระดับชั้นที่ 5 จำนวนกลุ่มเรียนระดับชั้นที่ 6 ฐานข้อมูลผู้สอน รหัสผู้สอน ชื่อผู้สอน ห้องที่ดูแล 40 ภาพที่ 3-13 การออกแบบฐานข้อมูลห้องเรียน ภาพที่ 3-14 การออกแบบฐานข้อมูลวิชาเรียน 3.5.2 ส่วนของการประมวลผล เป็นส่วนของการค้นหาผลลัพธ์ของตารางสอนที่ต้องการ ด้วยจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ ซึ่งได้มาจากการออกแบบจีเนติกอัลกอริทึมแบบหลาย จุดประสงค์ที่ใช้ในการจัดตารางสอน ดังภาพที่ 3-15 ภาพที่ 3-15 การออกแบบส่วนของการประมวลผล ฐานข้อมูลวิชาเรียน รหัสวิชา ชื่อวิชา จำนวนคาบ จำนวนครั้ง ฐานข้อมูลห้องเรียน รหัสห้องเรียน ชื่อห้องเรียน ประมวลผล เริ่มการประมวลผล 0% 100% 41 3.5.3 ส่วนของการแสดงผล เป็นส่วนของการแสดงผลลัพธ์สุดท้ายที่ได้จากการประมวลผล ด้วยจีเนติกอัลกอริทึม ดังภาพที่ 3-16 ตารางที่ 3-2 การออกแบบส่วนของการแสดงผล ม.1/1 ม.1/2 ม.1/3 ม.1/4 ม.1/5 จันทร์ คาบที่ 1 อาจารย์ อาจารย์ อาจารย์ อาจารย์ อาจารย์ คาบที่ 2 อาจารย์ อาจารย์ อาจารย์ อาจารย์ อาจารย์ คาบที่ 3 อาจารย์ อาจารย์ อาจารย์ อาจารย์ อาจารย์ คาบที่ 4 อาจารย์ อาจารย์ อาจารย์ อาจารย์ อาจารย์ คาบที่ 5 อาจารย์ อาจารย์ อาจารย์ อาจารย์ อาจารย์ อังคาร คาบที่ 1 อาจารย์ อาจารย์ อาจารย์ อาจารย์ อาจารย์ คาบที่ 2 อาจารย์ อาจารย์ อาจารย์ อาจารย์ อาจารย์ คาบที่ 3 อาจารย์ อาจารย์ อาจารย์ อาจารย์ อาจารย์ คาบที่ 4 อาจารย์ อาจารย์ อาจารย์ อาจารย์ อาจารย์ คาบที่ 5 อาจารย์ อาจารย์ อาจารย์ อาจารย์ อาจารย์ 3.6 ขั้นตอนของการพัฒนาระบบจัดตารางสอนของโรงเรียน เมื่อทำการวางแผนและออกแบบหน้าจอแล้ว ขั้นตอนต่อมาคือขั้นตอนของการพัฒนาจีเนติก อัลกอริทึมแบบหลายจุดประสงค์ สำหรับแก้ปัญหาการจัดตารางสอนของโรงเรียนโดยใช้โปรแกรม ไมโครซอฟท์วิชวลเบสิก เป็นเครื่องมือสำหรับพัฒนาโปรแกรม ซึ่งสามารถเขียนเป็นลำดับได้ดังนี้ 3.6.1 ขั้นตอนของการสร้างหน้าจอ ในขั้นตอนนี้จะยึดตามการออกแบบที่ได้วางแผนไว้ เป็นการสร้างหน้าจอที่เกี่ยวข้องกับ ระบบทั้งหมด รวมถึงการสร้างปุ่มควบคุมและเมนูต่าง ๆ สำหรับแต่ละหน้าจอ 3.6.2 ขั้นตอนการเขียนโปรแกรม ในขั้นตอนนี้จะทำการเขียนโปรแกรมเพื่อควบคุมการทำงานของระบบโดยใช้จีเนติก อัลกอริทึมแบบหลายจุดประสงค์ 3.7 ขั้นตอนของการทดสอบและปรับปรุงจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ 3.7.1 ทดสอบโปรแกรม 3.7.1.1 ตรวจสอบลำดับการทำงานของโปรแกรม 3.7.1.2 ตรวจสอบการเชื่อมโยงระหว่างหน้าจอและปุ่มควบคุมต่างๆ 42 3.7.1.3 ตรวจสอบความถูกต้องของข้อความที่แสดงในแต่ละหน้าจอ 3.7.1.4 ตรวจสอบผลลัพธ์ที่ได้จากการคำนวณ 3.7.2 ทดสอบการทำงานของอัลกอริทึม โดยตรวจสอบผลลัพธ์ที่ได้จากการประมวลผลของ จีเนติกอัลกอริทึมแบบหลายจุดประสงค์ บทที่ 4 ผลการดำเนินงาน จากการศึกษาข้อมูลที่เกี่ยวข้อง การออกแบบการดำเนินงานต่าง ๆ และการพัฒนานั้น ผลการ ดำเนินงานเป็นดังนี้ 4.1 ผลการพัฒนาจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ สำหรับแก้ปัญหาการจัดตารางสอนของ โรงเรียน เมื่อเข้าสู่จีเนติกอัลกอริทึมแบบหลายจุดประสงค์ สำหรับแก้ปัญหาการจัดตารางสอนของ โรงเรียนนั้นจะปรากฎหน้าแรกของระบบดังภาพที่ 4-1 ภาพที่ 4-1 หน้าแรกของจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ สำหรับแก้ปัญหา การจัดตารางสอนของโรงเรียน 44 แบ่งการทำงานเป็น 5 ส่วนดังนี้ 1) จัดตารางสอน 2) กำหนดค่า 3) ฐานข้อมูล 4) กำหนดคาบ 5) แสดงตารางสอน ซึ่งมีรายละเอียดดังนี้ 4.1.1 จัดตารางสอน การทำงานในส่วนนี้เป็นการประมวลผลการจัดตารางสอน โดยใช้จีเนติกอัลกอริทึม แบบหลายจุดประสงค์ ดังภาพที่ 4-2 ภาพที่ 4-2 หน้าจอการประมวลผล 4.1.2 กำหนดค่า การกำหนดค่าเป็นการกำหนดข้อมูลที่มีการเปลี่ยนแปลงไม่บ่อยนัก ซึ่งเป็นข้อมูล ประจำของแต่ละโรงเรียน แบ่งรายการย่อยอีก 3 รายการดังภาพที่ 4-3 คือ 1) ข้อมูลโรงเรียน 2) ข้อมูลวัน – เวลาเรียน 3) ข้อมูลระดับชั้น 4.1.2.1 ข้อมูลโรงเรียน เป็นการกำหนดข้อมูลหลักของโรงเรียน คือ ชื่อโรงเรียน ที่อยู่ ของโรงเรียน และรูปแบบระดับการศึกษาว่าเป็นการศึกษาระดับอนุบาล ประถมศึกษา มัธยมศึกษา ปวช. ปวส. หรือระดับอุดมศึกษา ดังภาพที่ 4-4 45 ภาพที่ 4-3 หน้าจอรายการย่อยของการกำหนดค่า ภาพที่ 4-4 หน้าจอการกำหนดค่าข้อมูลโรงเรียน 46 4.1.2.2 ข้อมูลวัน – เวลาเรียน แบ่งเป็น 2 ส่วน คือ ส่วนแรกเป็นการกำหนดข้อมูล หลักของโรงเรียนที่กำหนดไว้ว่ามีการเรียนการสอนในวันอะไรบ้าง เพราะแต่ละโรงเรียนอาจจะมี วันที่มีการเรียนการสอนไม่ตรงกัน เช่น โรงเรียนมัธยมเรียนวันจันทร์ ถึงวันศุกร์ โรงเรียนช่างกล อาจจะเรียนวันอังคาร ถึงวันเสาร์ เป็นต้น ดังภาพที่ 4-5 ส่วนที่สองเป็นการกำหนดข้อมูลเวลาเรียนที่บอกว่าแต่ละวันมีการเรียนการสอนกี่คาบเรียน (Period) และคาบเรียนละกี่นาที เพราะแต่ละโรงเรียนอาจจะมีเวลาของการเรียนการสอนใน 1 คาบ เรียนไม่เท่ากัน อาจจะเป็น 50 นาที หรือ 60 นาที ดังภาพที่ 4-6 ภาพที่ 4-5 หน้าจอกำหนดค่าข้อมูลวันเรียน 4.1.2.3 ข้อมูลระดับชั้น เป็นส่วนบอกข้อมูลระดับชั้นว่าแต่ละระดับชั้นมีกี่กลุ่มเรียน เพราะในแต่ละระดับชั้นอาจจะมีจำนวนกลุ่มเรียนไม่เท่ากัน และในแต่ละโรงเรียนก็มีข้อมูลจำนวน กลุ่มเรียนไม่เท่ากันก็เป็นได้ ดังภาพที่ 4-7 47 ภาพที่ 4-6 หน้าจอกำหนดค่าเวลาเรียน ภาพที่ 4-7 หน้าจอกำหนดค่าข้อมูลระดับชั้น 48 4.1.3 ฐานข้อมูล จะเก็บรายละเอียดของข้อมูลต่าง ๆ ที่จะนำมาใช้ในการประมวลผล เป็น ข้อมูลที่มีความสำคัญ และเป็นข้อมูลปัจจุบันของโรงเรียน ซึ่งมีรายการย่อยอีก 4 รายการ ดังภาพที่ 4-8 คือ 1) ฐานข้อมูลผู้สอน 2) ฐานข้อมูลกลุ่มเรียน 3) ฐานข้อมูลวิชาเรียน 4) ฐานข้อมูลห้องเรียน ภาพที่ 4-8 หน้าจอฐานข้อมูล 4.1.3.1 ฐานข้อมูลผู้สอน จะทำการเก็บข้อมูลต่าง ๆ ของผู้สอนดังนี้ รหัสผู้สอน, ชื่อ ผู้สอน และห้องที่ดูแล ซึ่งห้องที่ดูแลจะมีความสัมพันธ์กับผู้สอน เพราะผู้สอนจะเป็นผู้ดูแล ห้องเรียน ใน 1 ห้องเรียนจะมีผู้ดูแล 1 คน หรือมากกว่านั้น ถ้าผู้สอนมากกว่า 1 คน และห้องดูแลซ้ำกัน จะให้อาจารย์ที่มีชื่อคนแรกก่อน และจะทำการค้นหาห้องที่ว่างถัดไป ให้อาจารย์คนต่อไป ดัง ภาพที่ 4-9 49 ภาพที่ 4-9 หน้าจอฐานข้อมูลผู้สอน 4.1.3.2 ฐานข้อมูลกลุ่มเรียน จะแสดงผลลัพธ์จากการกำหนดค่าข้อมูลเวลาเรียน เช่น กำหนดค่าข้อมูลเวลาเรียน จำนวนระดับเป็น 2 ระดับ ระดับที่ 1 มี 3 กลุ่มเรียน ระดับที่ 2 มี 5 กลุ่ม เรียน เมื่อบันทึกข้อมูลแล้วผลลัพธ์ที่ได้เป็นดังภาพที่ 4-10 รหัสกลุ่ม 101 ชื่อกลุ่ม 1/1 ระดับชั้น 1 กลุ่มที่ 1 รหัสกลุ่ม 102 ชื่อกลุ่ม 1/2 ระดับชั้น 1 กลุ่มที่ 2 รหัสกลุ่ม 103 ชื่อกลุ่ม 1/3 ระดับชั้น 1 กลุ่มที่ 3 รหัสกลุ่ม 201 ชื่อกลุ่ม 1/1 ระดับชั้น 2 กลุ่มที่ 1 รหัสกลุ่ม 202 ชื่อกลุ่ม 1/2 ระดับชั้น 2 กลุ่มที่ 2 รหัสกลุ่ม 203 ชื่อกลุ่ม 1/3 ระดับชั้น 2 กลุ่มที่ 3 รหัสกลุ่ม 204 ชื่อกลุ่ม 1/4 ระดับชั้น 2 กลุ่มที่ 4 รหัสกลุ่ม 205 ชื่อกลุ่ม 1/5 ระดับชั้น 2 กลุ่มที่ 5 4.1.3.3 ฐานข้อมูลวิชาเรียน จะทำการเก็บข้อมูลต่าง ๆ ของวิชาเรียนดังนี้ รหัสวิชา, ชื่อวิชา, จำนวนคาบ และจำนวนครั้ง การประมวลผลจะมีการตรวจสอบว่าจากจำนวนคาบกับ จำนวนครั้ง หารกันแล้วได้ว่า แต่ละครั้งที่สอนจะเป็นวิชาที่สอนเพียงคาบเดียว หรือ 2 คาบติด หรือ 3 คาบติด ดังภาพที่ 4-11 50 ภาพที่ 4-10 หน้าจอฐานข้อมูลกลุ่มเรียน ภาพที่ 4-11 หน้าจอฐานข้อมูลวิชาเรียน 51 4.1.3.4 ฐานข้อมูลห้องเรียน จะทำการเก็บข้อมูลต่าง ๆ ของห้องเรียนดังนี้ รหัส ห้องเรียน และชื่อห้องเรียน ซึ่งข้อมูลนี้จะนำไปใช้รวมกับข้อมูลผู้สอน เป็นห้องที่ผู้สอนดูแล ดัง ภาพที่ 4-12 ภาพที่ 4-12 หน้าจอฐานข้อมูลห้องเรียน 4.1.4 กำหนดคาบ เป็นส่วนที่นำข้อมูลจากฐานข้อมูลมากำหนดค่าต่าง ๆ ที่เกี่ยวกับการจัด ตารางสอน และมีการเปลี่ยนแปลงเกิดขึ้นบ่อย หรือทุกครั้งที่มีการจัดตารางสอน ซึ่งมีรายการย่อย 3 รายการ ดังภาพที่ 4-13 คือ 1) อัตรากำลัง 2) กำหนดคาบก่อน 3) ยกเว้นคาบ 4.1.4.1 อัตรากำลัง เป็นส่วนสำคัญของระบบที่จะบอกว่า ผู้สอนคนไหน สอนวิชา อะไรของกลุ่มเรียนใด ดังภาพที่ 4-14 52 ภาพที่ 4-13 หน้าจอกำหนดคาบ ภาพที่ 4-14 หน้าจออัตรากำลัง 53 4.1.4.2 กำหนดคาบ เป็นส่วนที่กำหนดรายวิชาที่ต้องมีการจัดการเรียนการสอนไว้ ก่อน เช่น มีกลุ่มเรียนที่เรียนวิชาเดียวกันหลายกลุ่มดังภาพที่ 4-15 4.1.4.3 ยกเว้นคาบ เป็นส่วนที่กำหนดคาบเรียนที่ผู้สอนไม่ว่างหรือไม่สะดวก ในวัน และเวลานั้น ๆ ดังภาพที่ 4-16 ภาพที่ 4-15 หน้าจอกำหนดคาบก่อน 4.1.5 แสดงตารางสอน ส่วนการแสดงตารางสอนนั้นจะเรียกโปรแกรม Microsoft Excel ขึ้นมาเพื่อแสดงผลตามความต้องการ ดังภาพที่ 4-17 โดยแบ่งเป็น ตารางสอนผู้สอน จะแสดงผล โดยมีผู้สอนเป็นหลัก จะเป็นตารางสอนของผู้สอนแต่ละคน ดังภาพที่ 4-18, ตารางสอนกลุ่มเรียน จะแสดงผลโดยแยกเป็นแต่ละกลุ่มเรียน ดังภาพที่ 4-19 และตารางสอนรวม จะแสดงตารางสอน ทั้งหมดที่มีทั้งผู้สอน, กลุ่มเรียน และห้องเรียน ดังภาพที่ 4-20 54 ภาพที่ 4-16 หน้าจอยกเว้นคาบ ภาพที่ 4-17 หน้าจอแสดงตารางสอน 55 ชื่อผู้สอน อ.สงกรานต์ 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ม. 1/6 ม. 1/8 อังคาร ม. 1/13 พุธ ม. 1/4 พฤหัสบดี ม. 1/12 ศุกร์ ม. 1/6 ม. 1/2 ชื่อผู้สอน อ.นงเยาว์ 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ม. 1/10 ม. 1/10 อังคาร ม. 1/13 ม. 1/13 พุธ ม. 1/12 ม. 1/12 ม. 1/2 ม. 1/2 พฤหัสบดี ม. 1/8 ม. 1/8 ม. 1/6 ม. 1/6 ศุกร์ ม. 1/15 ม. 1/15 ม. 1/4 ม. 1/4 ชื่อผู้สอน อ.เพ็ญนี 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ม. 1/13 ม. 1/9 ม. 1/13 อังคาร ม. 1/11 ม. 1/3 ม. 1/5 ม. 1/13 ม. 1/14 พุธ ม. 1/13 พฤหัสบดี ม. 1/3 ม. 1/11 ม. 1/11 ศุกร์ ม. 1/9 ม. 1/1 ม. 1/1 ม. 1/7 ชื่อผู้สอน อ.ปุณณภา 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ม. 1/1 ม. 1/1 ม. 1/15 ม. 1/14 อังคาร ม. 1/9 ม. 1/9 ม. 1/3 ม. 1/3 พุธ ม. 1/5 ม. 1/5 ม. 1/1 พฤหัสบดี ม. 1/9 ม. 1/3 ม. 1/15 ม. 1/15 ศุกร์ ม. 1/5 ม. 1/14 ม. 1/14 ชื่อผู้สอน อ.ขวัญหทัย 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ม. 1/7 ม. 1/7 ม. 1/9 ม. 1/9 อังคาร ม. 1/12 ม. 1/12 พุธ ม. 1/8 ม. 1/8 พฤหัสบดี ม. 1/10 ม. 1/10 ศุกร์ ม. 1/11 ม. 1/11 ภาพที่ 4-18 ตัวอย่างผลการจัดตารางสอนของผู้สอน 56 ระดับชั้น ม. 1/1 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ( อ.ปุณณภา ) ( อ.ปุณณภา ) ค้นคว้า( อ.เรณู-ติร ) ( พัก ) ต 10( อ.ภัทรมน ) ( อ.เสริมศักดิ์ ) ( อ.เสริมศักดิ์ ) ( ชุมนุม ) อังคาร ต 11( Mr.A ) ต 11( Mr.A ) ท 10( อ.วราภรณ์ ) ( พัก ) ค 10( อ.จันทนา ) ท 10( อ.วราภรณ์ ) ( ประชุม ) ( ซ่อมเสริม ) พุธ ค 10( อ.จันทนา ) ต 10( อ.ภัทรมน ) ( อ.จรรยา ) ( พัก ) ( อ.ปุณณภา ) ( อ.นงเยาว์ ) ( อ.นงเยาว์ ) ( คณะสี ) พฤหัสบดี ( แนะแนว ) ลูกเสือ(อ.เกียรติศักดิ์) ต 10( อ.ภัทรมน ) ( พัก ) ค 10( อ.จันทนา ) ค้นคว้า( อ.เรณู-ติร ) ( คณาจารย์ ) ( คณาจารย์ ) ศุกร์ ส 01( อ.สิริเพ็ญ ) ส 10( อ.เพ็ญนี ) ส 10( อ.เพ็ญนี ) ส 01( อ.สิริเพ็ญ ) ( พัก ) ( รด ) ( รด ) ( รด ) ระดับชั้น ม. 1/2 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ต 11( Mr.A ) ค 10( อ.กุหลาบ ) ต 10( อ.แพรวพรรณ ) ( พัก ) ส 01( อ.สิริเพ็ญ ) ต 10( อ.แพรวพรรณ) ลูกเสือ( อ.เกียรติกดิ์) ( ชุมนุม ) อังคาร ต 10( อ.แพรวพรรณ ส 10( อ.เพ็ญนี ) ต 10( อ.แพรวพรรณ ) ( พัก ) ( อ.ปุณณภา ) ( อ.ปุณณภา ) ( ประชุม ) ( ซ่อมเสริม ) พุธ ง 031( อ.แสงจันทร์ ) ( อ.เสริมศักดิ์ ) ( อ.เสริมศักดิ์ ) ( พัก ) ( อ.จรรยา ) ค 10( อ.กุหลาบ ) ต 10( อ.แพรวพรรณ) ( คณะสี ) พฤหัสบดี ( แนะแนว ) ส 01( อ.สิริเพ็ญ ) ( อ.ปุณณภา ) ( พัก ) ส 10( อ.เพ็ญนี ) ท 10( อ.ศรีอรทัย ) ( คณาจารย์ ) ( คณาจารย์ ) ศุกร์ ง 031( อ.แสงจันทร์ ) ค 10( อ.กุหลาบ ) ( อ.นงเยาว์ ) ( อ.นงเยาว์ ) ( พัก ) ( รด ) ( รด ) ( รด ) ระดับชั้น ม. 1/3 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ส 01( อ.สิริเพ็ญ ) ท 10( อ.วราภรณ์ ) ส 10( อ.เพ็ญนี ) ( พัก ) ต 10( อ.เนาวรัตน์ ) ( อ.สุรางคนา ) ( อ.สุรางคนา ) ( ชุมนุม ) อังคาร ต 10( อ.เนาวรัตน์ ) ค 10( อ.จันทนา ) ส 10( อ.เพ็ญนี ) ( พัก ) ( คณาจารย์ ) ( คณาจารย์ ) ( ประชุม ) ( ซ่อมเสริม ) พุธ ( อ.ปุณณภา ) ( อ.ปุณณภา ) ค 10( อ.จันทนา ) ( พัก ) ค้นคว้า( อ.เรณู-ติร ) ( อ.จรรยา ) ท 10( อ.วราภรณ์ ) ( คณะสี ) พฤหัสบดี ( แนะแนว ) ค 10( อ.จันทนา ) ลูกเสือ( อ.เกียรติศักดิ์) ( พัก ) ส 01( อ.สิริเพ็ญ ) ส 01( อ.สิริเพ็ญ ) ( อ.นงเยาว์ ) ( อ.นงเยาว์ ) ศุกร์ ( อ.ปุณณภา ) ง 031( อ.แสงจันทร์ ) ต 10( อ.เนาวรัตน์ ) ท 10( อ.วราภรณ์ ) ( พัก ) ( รด ) ( รด ) ( รด ) ระดับชั้น ม. 1/4 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ต 10( อ.แพรวพรรณ) ง 031( อ.สงกรานต์ ) ท 10( อ.สมเกียรติ ) ( พัก ) ลูกเสือ( อ.เกียรติกดิ์) ( คณาจารย์ ) ( คณาจารย์ ) ( ชุมนุม ) อังคาร ท 10( อ.สมเกียรติ ) ( อ.สิทธิรัตน์ ) ต 10( อ.แพรวพรรณ ) ( พัก ) ท 10( อ.สมเกียรติ ) ค 10( อ.จันทนา ) ( ประชุม ) ( ซ่อมเสริม ) พุธ ส 10( อ.นันทนา ) ส 01( อ.วิถีชัย ) ส 01( อ.วิถีชัย ) ( พัก ) ค 10( อ.จันทนา ) ( อ.สุรางคนา ) ( อ.สุรางคนา ) ( คณะสี ) พฤหัสบดี ( แนะแนว ) ( อ.สิทธิรัตน์ ) ( อ.สิทธิรัตน์ ) ( พัก ) ต 11( Mr.A ) ( อ.จรรยา ) ( อ.นงเยาว์ ) ( อ.นงเยาว์ ) ศุกร์ ง 031( อ.สงกรานต์ ) ส 01( อ.วิถีชัย ) ต 10( อ.แพรวพรรณ ) ค้นคว้า(อ.เดือนภา) ( พัก ) ( รด ) ( รด ) ( รด ) ระดับชั้น ม. 1/5 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ( อ.ขวัญหทัย ) ( อ.ขวัญหทัย ) ง 031( อ.แสงจันทร์ ) ( พัก ) ค 10( อ.กุหลาบ ) ( คณาจารย์ ) ( คณาจารย์ ) ( ชุมนุม ) อังคาร ค 10( อ.กุหลาบ ) ค้นคว้า( อ.เรณู-ติร ) ต 10( อ.ภัทรมน ) ( พัก ) ( อ.สิทธิรัตน์ ) ( อ.สิทธิรัตน์ ) ( ประชุม ) ( ซ่อมเสริม ) พุธ ง 031( อ.แสงจันทร์ ) ต 11( Mr.A ) ง 031( อ.แสงจันทร์ ) ( พัก ) ส 01( อ.สิริเพ็ญ ) ต 10( อ.ภัทรมน ) ลูกเสือ( อ.เกียรติกดิ์) ( คณะสี ) พฤหัสบดี ( แนะแนว ) ( อ.นงเยาว์ ) ( อ.นงเยาว์ ) ( พัก ) ( อ.สิทธิรัตน์ ) ต 10( อ.ภัทรมน ) ส 10( อ.เพ็ญนี ) ( อ.จรรยา ) ศุกร์ ค 10( อ.กุหลาบ ) ท 10( อ.ศรีอรทัย ) ส 01( อ.สิริเพ็ญ ) ส 10( อ.เพ็ญนี ) ( พัก ) ( รด ) ( รด ) ( รด ) ระดับชั้น ม. 1/8 08.00-08.50 08.50-09.40 09.40-10.30 10.30-11.20 11.20-12.10 12.10-13.00 13.00-13.50 13.50-14.40 จันทร์ ส 01( อ.วิถีชัย ) ค 10( อ.ธรรศธฤต ) ค้นคว้า(อ.พรรณกนก) ( พัก ) ง 031( อ.สงกรานต์ ) ต 10( อ.เนาวรัตน์ ) ต 10( อ.เนาวรัตน์ ) ( ชุมนุม ) อังคาร ต 10( อ.เนาวรัตน์ ) ท 10( อ.สมเกียรติ ) ส 01( อ.วิถีชัย ) ( พัก ) ลูกเสือ(อ.เกียรติศักดิ์) ท 10( อ.สมเกียรติ ) ( ประชุม ) ( ซ่อมเสริม ) พุธ ( อ.สิทธิรัตน์ ) ( อ.สิทธิรัตน์ ) ( อ.จรรยา ) ( พัก ) ท 10( อ.สมเกียรติ ) ( อ.ขวัญหทัย ) ( อ.ขวัญหทัย ) ( คณะสี ) พฤหัสบดี ( แนะแนว ) ( อ.นงเยาว์ ) ( อ.นงเยาว์ ) ( พัก ) ท 10( อ.สมเกียรติ ) ต 10( อ.เนาวรัตน์ ) ต 11( Mr.A ) ค 10(อ.ธรรศธ ฤต) ศุกร์ ( อ.สิทธิรัตน์ ) ค 10( อ.ธรรศธฤต ) ( คณาจารย์ ) ( คณาจารย์ ) ( พัก ) ( รด ) ( รด ) ( รด ) ภาพที่ 4-19 ตัวอย่างผลการจัดตารางสอนของกลุ่มเรียน 57 ม.1/1 ม.1/2 ม.1/3 ม.1/4 ม.1/5 ม.1/6 ม.1/7 ม.1/8 จันทร์ คาบที่ 1 อ.ปุณณภา อ.สมเกียรติ Mr.A อ.ภัทรมน อ.สิริเพ็ญ อ.แพรวพรรณ อ.ขวัญหทัย อ.วิถีชัย คาบที่ 2 อ.ปุณณภา อ.สิทธิรัตน์ อ.กุหลาบ อ.เดือนนภา อ.วราภรณ์ อ.สงกรานต์ อ.ขวัญหทัย อ.ธรรศธฤต คาบที่ 3 อ.เรณู-ติร อ.สิทธิรัตน์ อ.แพรวพรรณ อ.ธรรศธฤต อ.เพ็ญนี อ.สมเกียรติ อ.แสงจันทร์ อ.พรรณกนก คาบที่ 4 พัก พัก พัก พัก พัก พัก พัก พัก คาบที่ 5 อ.ภัทรมน อ.เกียรติศักดิ์ อ.สิริเพ็ญ อ.ภัทรมน อ.เนาวรัตน์ อ.เกียรติศักดิ์ อ.กุหลาบ อ.สงกรานต์ คาบที่ 6 อ.เสริมศักดิ์ อ.เกียรติศักดิ์ อ.แพรวพรรณ อ.นันทนา อ.สุรางคนา คณาจารย์ คณาจารย์ อ.เนาวรัตน์ คาบที่ 7 อ.เสริมศักดิ์ อ.เกียรติศักดิ์ อ.เกียรติศักดิ์ อ.เกียรติศักดิ์ อ.สุรางคนา คณาจารย์ คณาจารย์ อ.เนาวรัตน์ คาบที่ 8 ชุมนุม ชุมนุม ชุมนุม ชุมนุม ชุมนุม ชุมนุม ชุมนุม ชุมนุม อังคาร คาบที่ 1 Mr.A อ.นันทนา อ.แพรวพรรณ อ.สิทธิรัตน์ อ.เนาวรัตน์ อ.สมเกียรติ อ.กุหลาบ อ.เนาวรัตน์ คาบที่ 2 Mr.A อ.เกียรติศักดิ์ อ.เพ็ญนี อ.ภัทรมน อ.จันทนา อ.สิทธิรัตน์ อ.เรณู-ติร อ.สมเกียรติ คาบที่ 3 อ.วราภรณ์ อ.นันทนา อ.แพรวพรรณ อ.ธรรศธฤต อ.เพ็ญนี อ.แพรวพรรณ อ.ภัทรมน อ.วิถีชัย คาบที่ 4 พัก พัก พัก พัก พัก พัก พัก พัก คาบที่ 5 อ.จันทนา อ.เสริมศักดิ์ อ.ปุณณภา คณาจารย์ คณาจารย์ อ.สมเกียรติ อ.สิทธิรัตน์ อ.เกียรติศักดิ์ คาบที่ 6 อ.วราภรณ์ อ.เสริมศักดิ์ อ.ปุณณภา คณาจารย์ คณาจารย์ อ.จันทนา อ.สิทธิรัตน์ อ.สมเกียรติ คาบที่ 7 ประชุม ประชุม ประชุม ประชุม ประชุม ประชุม ประชุม ประชุม คาบที่ 8 ซ่อมเสริม ซ่อมเสริม ซ่อมเสริม ซ่อมเสริม ซ่อมเสริม ซ่อมเสริม ซ่อมเสริม ซ่อมเสริม พุธ คาบที่ 1 อ.จันทนา อ.ธรรศธฤต อ.แสงจันทร์ อ.สมเกียรติ อ.ปุณณภา อ.นันทนา อ.แสงจันทร์ อ.สิทธิรัตน์ คาบที่ 2 อ.ภัทรมน Mr.A อ.เสริมศักดิ์ อ.สุรางคนา อ.ปุณณภา อ.วิถีชัย Mr.A อ.สิทธิรัตน์ คาบที่ 3 อ.จรรยา อ.เนาวรัตน์ อ.เสริมศักดิ์ อ.สุรางคนา อ.จันทนา อ.วิถีชัย อ.แสงจันทร์ อ.จรรยา คาบที่ 4 พัก พัก พัก พัก พัก พัก พัก พัก คาบที่ 5 อ.ปุณณภา อ.สิทธิรัตน์ อ.จรรยา อ.นันทนา อ.เรณู-ติร อ.จันทนา อ.สิริเพ็ญ อ.สมเกียรติ คาบที่ 6 อ.นงเยาว์ อ.นงเยาว์ อ.กุหลาบ อ.วิถีชัย อ.จรรยา อ.สุรางคนา อ.ภัทรมน อ.ขวัญหทัย คาบที่ 7 อ.นงเยาว์ อ.นงเยาว์ อ.แพรวพรรณ อ.สงกรานต์ อ.วราภรณ์ อ.สุรางคนา อ.เกียรติศักดิ์ อ.ขวัญหทัย คาบที่ 8 คณะสี คณะสี คณะสี คณะสี คณะสี คณะสี คณะสี คณะสี พฤหัสบดี คาบที่ 1 แนะแนว แนะแนว แนะแนว แนะแนว แนะแนว แนะแนว แนะแนว แนะแนว คาบที่ 2 อ.เกียรติศักดิ์ อ.สมเกียรติ อ.สิริเพ็ญ อ.จรรยา อ.จันทนา อ.สิทธิรัตน์ อ.นงเยาว์ อ.นงเยาว์ คาบที่ 3 อ.ภัทรมน อ.พรรณกนก อ.ปุณณภา อ.สมเกียรติ อ.เกียรติศักดิ์ อ.สิทธิรัตน์ อ.นงเยาว์ อ.นงเยาว์ คาบที่ 4 พัก พัก พัก พัก พัก พัก พัก พัก คาบที่ 5 อ.จันทนา อ.จรรยา อ.เพ็ญนี อ.เกียรติศักดิ์ อ.สิริเพ็ญ Mr.A อ.สิทธิรัตน์ อ.สมเกียรติ คาบที่ 6 อ.เรณู-ติร อ.วิถีชัย อ.ศรีอรทัย อ.เกียรติศักดิ์ อ.สิริเพ็ญ อ.จรรยา อ.ภัทรมน อ.เนาวรัตน์ คาบที่ 7 คณาจารย์ คณาจารย์ คณาจารย์ อ.สิทธิรัตน์ อ.นงเยาว์ อ.นงเยาว์ อ.เพ็ญนี Mr.A คาบที่ 8 คณาจารย์ คณาจารย์ คณาจารย์ อ.สิทธิรัตน์ อ.นงเยาว์ อ.นงเยาว์ อ.จรรยา อ.ธรรศธฤต ศุกร์ คาบที่ 1 อ.สิริเพ็ญ อ.เกียรติศักดิ์ อ.แสงจันทร์ อ.ธรรศธฤต อ.ปุณณภา อ.สงกรานต์ อ.กุหลาบ อ.สิทธิรัตน์ คาบที่ 2 อ.เพ็ญนี อ.สงกรานต์ อ.กุหลาบ Mr.A อ.แสงจันทร์ อ.วิถีชัย อ.ศรีอรทัย อ.ธรรศธฤต คาบที่ 3 อ.เพ็ญนี อ.สมเกียรติ อ.นงเยาว์ อ.นงเยาว์ อ.เนาวรัตน์ อ.แพรวพรรณ อ.สิริเพ็ญ คณาจารย์ คาบที่ 4 อ.สิริเพ็ญ อ.สมเกียรติ อ.นงเยาว์ อ.นงเยาว์ อ.วราภรณ์ อ.เดือนนภา อ.เพ็ญนี คณาจารย์ คาบที่ 5 พัก พัก พัก พัก พัก พัก พัก พัก คาบที่ 6 รด รด รด รด รด รด รด รด คาบที่ 7 รด รด รด รด รด รด รด รด คาบที่ 8 รด รด รด รด รด รด รด รด ภาพที่ 4-20 ตัวอย่างผลการจัดตารางสอนรวม 58 4.2 ผลการทดลอง การทดลองนี้เป็นการเปรียบเทียบประสิทธิภาพในการทดสอบจำนวนรุ่น (Generation) เพื่อ หาคำตอบที่ดีที่สุด โดยมีฟังก์ชันที่ใช้ในการทดสอบดังตารางที่ 4-1 ทดสอบโดยเปรียบเทียบ คำตอบภายในจำนวนโครโมโซมแต่ละชุด ตารางที่ 4-1 พารามิเตอร์ที่ใช้ในการทดสอบจำนวนรุ่น พารามิเตอร์ ค่าพารามิเตอร์ ความน่าจะเป็นของการกลายพันธุ์ 0.1 ความน่าจะเป็นของการสลับสายพันธุ์ 0.5 4.2.1 กำหนดจำนวนโครโมโซมเป็น 10 โครโมโซม โดยใช้พารามิเตอร์ในการทดสอบตาม ตารางที่ 4-1 และได้ผลการทดลองตามตารางที่ 4-2 ซึ่งคำตอบที่ได้จากการทดสอบในจำนวนรุ่นที่ 100 ค่าความแข็งแรงที่ได้มีค่า 277.8 รุ่นที่ 200 ค่าความแข็งแรงที่ได้มีค่า 308.4 รุ่นที่ 300 ค่า ความแข็งแรงที่ได้มีค่า 344.5 รุ่นที่ 400 ค่าความแข็งแรงที่ได้มีค่า 355.2 และรุ่นที่ 500 ค่าความ แข็งแรงที่ได้มีค่า 363.5 จากการทดลองพบว่า เมื่อจำนวนรุ่นเพิ่มขึ้น ค่าความแข็งแรงจะมีค่าดีขึ้น ตามไปด้วย ตารางที่ 4-2 ผลการทดสอบจำนวนรุ่นที่มีจำนวนโครโมโซมเป็น 10 โครโมโซม จำนวนรุ่น (Generation) ค่าความแข็งแรง (Fitness Value) 100 277.8 200 308.4 300 344.5 400 355.2 500 363.5 4.2.2 กำหนดจำนวนโครโมโซมเป็น 20 โครโมโซม โดยใช้พารามิเตอร์ในการทดสอบตาม ตารางที่ 4-1 และได้ผลการทดลองตามตารางที่ 4-3 ซึ่งคำตอบที่ได้จากการทดสอบในจำนวนรุ่นที่ 100 ค่าความแข็งแรงที่ได้มีค่า 278.2 รุ่นที่ 200 ค่าความแข็งแรงที่ได้มีค่า 319.35 รุ่นที่ 300 ค่า ความแข็งแรงที่ได้มีค่า 341.55 รุ่นที่ 400 ค่าความแข็งแรงที่ได้มีค่า 348.75 และรุ่นที่ 500 ค่า ความแข็งแรงที่ได้มีค่า 353.55 จากการทดลองพบว่า เมื่อจำนวนรุ่นเพิ่มขึ้น ค่าความแข็งแรงจะมีค่า ดีขึ้นตามไปด้วย 59 ตารางที่ 4-3 ผลการทดสอบจำนวนรุ่นที่มีจำนวนโครโมโซมเป็น 20 โครโมโซม จำนวนรุ่น (Generation) ค่าความแข็งแรง (Fitness Value) 100 278.2 200 319.35 300 341.55 400 348.75 500 353.55 4.2.3 กำหนดจำนวนโครโมโซมเป็น 30 โครโมโซม โดยใช้พารามิเตอร์ในการทดสอบตาม ตารางที่ 4-1 และได้ผลการทดลองตามตารางที่ 4-4 ซึ่งคำตอบที่ได้จากการทดสอบในจำนวนรุ่นที่ 100 ค่าความแข็งแรงที่ได้มีค่า 281.13 รุ่นที่ 200 ค่าความแข็งแรงที่ได้มีค่า 309.57 รุ่นที่ 300 ค่า ความแข็งแรงที่ได้มีค่า 324.57 รุ่นที่ 400 ค่าความแข็งแรงที่ได้มีค่า 337.17 และรุ่นที่ 500 ค่า ความแข็งแรงที่ได้มีค่า 348.9 จากการทดลองพบว่า เมื่อจำนวนรุ่นเพิ่มขึ้น ค่าความแข็งแรงจะมีค่าดี ขึ้นตามไปด้วย ตารางที่ 4-4 ผลการทดสอบจำนวนรุ่นที่มีจำนวนโครโมโซมเป็น 30 โครโมโซม จำนวนรุ่น (Generation) ค่าความแข็งแรง (Fitness Value) 100 281.13 200 309.57 300 324.57 400 337.17 500 348.9 4.2.4 กำหนดจำนวนโครโมโซมเป็น 40 โครโมโซม โดยใช้พารามิเตอร์ในการทดสอบตาม ตารางที่ 4-1 และได้ผลการทดลองตามตารางที่ 4-5 ซึ่งคำตอบที่ได้จากการทดสอบในจำนวนรุ่นที่ 100 ค่าความแข็งแรงที่ได้มีค่า 284.35 รุ่นที่ 200 ค่าความแข็งแรงที่ได้มีค่า 308.25 รุ่นที่ 300 ค่า ความแข็งแรงที่ได้มีค่า 321.5 รุ่นที่ 400 ค่าความแข็งแรงที่ได้มีค่า 329.9 และรุ่นที่ 500 ค่าความ แข็งแรงที่ได้มีค่า 336.1 จากการทดลองพบว่า เมื่อจำนวนรุ่นเพิ่มขึ้น ค่าความแข็งแรงจะมีค่าดีขึ้น ตามไปด้วย ตารางที่ 4-5 ผลการทดสอบจำนวนรุ่นที่มีจำนวนโครโมโซมเป็น 40 โครโมโซม จำนวนรุ่น (Generation) ค่าความแข็งแรง (Fitness Value) 100 284.35 200 308.25 300 321.5 400 329.9 500 336.1 60 4.2.5 กำหนดจำนวนโครโมโซมเป็น 50 โครโมโซม โดยใช้พารามิเตอร์ในการทดสอบตาม ตารางที่ 4-1 และได้ผลการทดลองตามตารางที่ 4-6 ซึ่งคำตอบที่ได้จากการทดสอบในจำนวนรุ่นที่ 100 ค่าความแข็งแรงที่ได้มีค่า 292.54 รุ่นที่ 200 ค่าความแข็งแรงที่ได้มีค่า 308.56 รุ่นที่ 300 ค่า ความแข็งแรงที่ได้มีค่า 319.46 รุ่นที่ 400 ค่าความแข็งแรงที่ได้มีค่า 329.68 และรุ่นที่ 500 ค่า ความแข็งแรงที่ได้มีค่า 338.78 จากการทดลองพบว่า เมื่อจำนวนรุ่นเพิ่มขึ้น ค่าความแข็งแรงจะมีค่า ดีขึ้นตามไปด้วย ตารางที่ 4-6 ผลการทดสอบจำนวนรุ่นที่มีจำนวนโครโมโซมเป็น 50 โครโมโซม จำนวนรุ่น (Generation) ค่าความแข็งแรง (Fitness Value) 100 292.54 200 308.56 300 319.46 400 329.68 500 338.76 4.2.6 กำหนดจำนวนโครโมโซมเป็น 60 โครโมโซม โดยใช้พารามิเตอร์ในการทดสอบตาม ตารางที่ 4-1 และได้ผลการทดลองตามตารางที่ 4-7 ซึ่งคำตอบที่ได้จากการทดสอบในจำนวนรุ่นที่ 100 ค่าความแข็งแรงที่ได้มีค่า 283.72 รุ่นที่ 200 ค่าความแข็งแรงที่ได้มีค่า 313.7 รุ่นที่ 300 ค่า ความแข็งแรงที่ได้มีค่า 334.35 รุ่นที่ 400 ค่าความแข็งแรงที่ได้มีค่า 344 และรุ่นที่ 500 ค่าความ แข็งแรงที่ได้มีค่า 351.33 จากการทดลองพบว่า เมื่อจำนวนรุ่นเพิ่มขึ้น ค่าความแข็งแรงจะมีค่าดีขึ้น ตามไปด้วย ตารางที่ 4-7 ผลการทดสอบจำนวนรุ่นที่มีจำนวนโครโมโซมเป็น 60 โครโมโซม จำนวนรุ่น (Generation) ค่าความแข็งแรง (Fitness Value) 100 283.72 200 313.7 300 334.35 400 344 500 351.33 4.2.7 กำหนดจำนวนโครโมโซมเป็น 70 โครโมโซม โดยใช้พารามิเตอร์ในการทดสอบตาม ตารางที่ 4-1 และได้ผลการทดลองตามตารางที่ 4-8 ซึ่งคำตอบที่ได้จากการทดสอบในจำนวนรุ่นที่ 100 ค่าความแข็งแรงที่ได้มีค่า 282.73 รุ่นที่ 200 ค่าความแข็งแรงที่ได้มีค่า 311.44 รุ่นที่ 300 ค่า ความแข็งแรงที่ได้มีค่า 325.2 รุ่นที่ 400 ค่าความแข็งแรงที่ได้มีค่า 335.74 และรุ่นที่ 500 ค่าความ 61 แข็งแรงที่ได้มีค่า 343.36 จากการทดลองพบว่า เมื่อจำนวนรุ่นเพิ่มขึ้น ค่าความแข็งแรงจะมีค่าดีขึ้น ตามไปด้วย ตารางที่ 4-8 ผลการทดสอบจำนวนรุ่นที่มีจำนวนโครโมโซมเป็น 70 โครโมโซม จำนวนรุ่น (Generation) ค่าความแข็งแรง (Fitness Value) 100 282.73 200 311.44 300 325.2 400 335.74 500 343.36 4.2.8 กำหนดจำนวนโครโมโซมเป็น 80 โครโมโซม โดยใช้พารามิเตอร์ในการทดสอบตาม ตารางที่ 4-1 และได้ผลการทดลองตามตารางที่ 4-9 ซึ่งคำตอบที่ได้จากการทดสอบในจำนวนรุ่นที่ 100 ค่าความแข็งแรงที่ได้มีค่า 276.7 รุ่นที่ 200 ค่าความแข็งแรงที่ได้มีค่า 308.34 รุ่นที่ 300 ค่า ความแข็งแรงที่ได้มีค่า 325.25 รุ่นที่ 400 ค่าความแข็งแรงที่ได้มีค่า 336.84 และรุ่นที่ 500 ค่า ความแข็งแรงที่ได้มีค่า 345.11 จากการทดลองพบว่า เมื่อจำนวนรุ่นเพิ่มขึ้น ค่าความแข็งแรงจะมีค่า ดีขึ้นตามไปด้วย ตารางที่ 4-9 ผลการทดสอบจำนวนรุ่นที่มีจำนวนโครโมโซมเป็น 80 โครโมโซม จำนวนรุ่น (Generation) ค่าความแข็งแรง (Fitness Value) 100 276.7 200 308.34 300 325.25 400 336.84 500 345.11 4.2.9 กำหนดจำนวนโครโมโซมเป็น 90 โครโมโซม โดยใช้พารามิเตอร์ในการทดสอบตาม ตารางที่ 4-1 และได้ผลการทดลองตามตารางที่ 4-10 ซึ่งคำตอบที่ได้จากการทดสอบในจำนวนรุ่น ที่ 100 ค่าความแข็งแรงที่ได้มีค่า 271.72 รุ่นที่ 200 ค่าความแข็งแรงที่ได้มีค่า 309.56 รุ่นที่ 300 ค่าความแข็งแรงที่ได้มีค่า 329.47 รุ่นที่ 400 ค่าความแข็งแรงที่ได้มีค่า 341.3 และรุ่นที่ 500 ค่า ความแข็งแรงที่ได้มีค่า 347.6 จากการทดลองพบว่า เมื่อจำนวนรุ่นเพิ่มขึ้น ค่าความแข็งแรงจะมีค่าดี ขึ้นตามไปด้วย 62 ตารางที่ 4-10 ผลการทดสอบจำนวนรุ่นที่มีจำนวนโครโมโซมเป็น 90 โครโมโซม จำนวนรุ่น (Generation) ค่าความแข็งแรง (Fitness Value) 100 271.72 200 309.56 300 329.47 400 341.3 500 347.6 4.2.10 กำหนดจำนวนโครโมโซมเป็น 100 โครโมโซม โดยใช้พารามิเตอร์ในการทดสอบ ตามตารางที่ 4-1 และได้ผลการทดลองตามตารางที่ 4-11 ซึ่งคำตอบที่ได้จากการทดสอบในจำนวน รุ่นที่ 100 ค่าความแข็งแรงที่ได้มีค่า 286.46 รุ่นที่ 200 ค่าความแข็งแรงที่ได้มีค่า 317.3 รุ่นที่ 300 ค่าความแข็งแรงที่ได้มีค่า 331.84 รุ่นที่ 400 ค่าความแข็งแรงที่ได้มีค่า 340.94 และรุ่นที่ 500 ค่า ความแข็งแรงที่ได้มีค่า 346.68 จากการทดลองพบว่า เมื่อจำนวนรุ่นเพิ่มขึ้น ค่าความแข็งแรงจะมีค่า ดีขึ้นตามไปด้วย ตารางที่ 4-11 ผลการทดสอบจำนวนรุ่นที่มีจำนวนโครโมโซมเป็น 100 โครโมโซม จำนวนรุ่น (Generation) ค่าความแข็งแรง (Fitness Value) 100 286.46 200 317.3 300 331.84 400 340.94 500 346.68 4.3 สรุปผลการทดลอง จากการทดสอบจำนวนรุ่นที่มีค่าความน่าจะเป็นในการกลายพันธุ์เป็น 0.1 ค่าความน่าจะเป็น ในการสลับสายพันธุ์เป็น 0.5 และจำนวนโครโมโซมตั้งแต่ 10, 20, 30,…, 100 พบว่าคำตอบที่ได้รับ จะมีค่าความแข็งแรงของจำนวนรุ่นที่ดีขึ้นเรื่อย ๆ ในแต่ละกลุ่มของจำนวนโครโมโซมที่ใช้ในการ ทดลอง บทที่ 5 สรุปผลและข้อเสนอแนะ สารนิพนธ์นี้ได้นำเสนอขั้นตอนของจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ เพื่อใช้ในการ แก้ปัญหาการจัดตารางสอนของโรงเรียน โดยการพัฒนาขั้นตอนของจีเนติกอัลกอริทึมแบบหลาย จุดประสงค์ (Multi Objective Genetic Algorithm) สำหรับแก้ปัญหาการจัดตารางสอนของโรงเรียน นั้น ใช้โปรแกรม Microsoft Visual Basic 6.0 ในการเขียนโปรแกรม โปรแกรม Microsoft Access 2003 เป็นระบบจัดการฐานข้อมูล และแสดงผลโดยใช้โปรแกรม Microsoft Excel 2003 5.1 สรุปผล ผลการพัฒนาโปรแกรมประยุกต์เพื่อการจัดตารางสอน โดยการนำจีเนติกอัลกอริทึมแบบ หลายจุดประสงค์ โดยมีการทำงานหลักของการจัดตารางสอน ได้แก่ (1) การกำหนดข้อมูลพื้นฐาน เช่น ข้อมูลโรงเรียน ข้อมูลวัน-เวลาเรียน และข้อมูลระดับชั้น (2) การจัดการเกี่ยวกับฐานข้อมูล เช่น เพิ่ม ลบ ข้อมูลผู้สอน ข้อมูลกลุ่มเรียน ข้อมูลวิชาเรียน และข้อมูลห้องเรียน (3) การกำหนดคาบเวลา เช่น กำหนดอัตรากำลัง กำหนดคาบก่อน และยกเว้นคาบ (4) การประมวลโดยใช้จีเนติกอัลกอริทึม แบบหลายจุดประสงค์ (5) การแสดงผลตารางสอนแบบต่าง ๆ เช่น ตารางสอนผู้สอน ตารางสอน กลุ่มเรียน และตารางสอนรวม จากผลการทดลองการพัฒนาจีเนติกอัลกอริทึมแบบหลายจุดประสงค์ เพื่อใช้ในการแก้ปัญหา การจัดตารางสอนของโรงเรียน โดยมีค่าความน่าจะเป็นในการกลายพันธุ์เป็น 0.1 ค่าความน่าจะเป็น ในการสลับสายพันธุ์เป็น 0.5 และจำนวนโครโมโซมตั้งแต่ 10, 20, 30,…, 100 ผลที่ได้รับพบว่า ตารางสอนที่มีขนาดเล็ก ๆ สามารถจัดได้อย่างถูกต้อง โดยใช้จำนวนโครโมโซมไม่มากนัก และ จำนวนรุ่นน้อย ๆ การจัดตารางสอนจะใช้เวลาสั้น ๆ สำหรับตารางสอนขนาดใหญ่ ๆ จำนวน โครโมโซมที่ใช้ต้องมากและจำนวนรุ่นต้องมากด้วย 64 5.2 ข้อเสนอแนะ การพัฒนาจีเนติกอัลกอริทึมแบบหลายจุดประสงค์มาใช้ในการจัดตารางสอนนั้น คำตอบที่ ได้รับมีความเหมาะสม แต่ต้องใช้ข้อมูลนำเข้าจำนวนมาก ซึ่งมีข้อมูลบางส่วนอาจจะไม่ต้องใส่ลง ในระบบทุกครั้งที่ต้องจัดการเรียนการสอนก็ได้ เช่น ข้อมูลผู้สอนต้องใส่ลงในระบบทุกครั้งที่มีการ เปลี่ยนแปลง ถ้าเก็บข้อมูลผู้สอนรวมทั้งคุณวุฒิการศึกษา จะใช้วุฒิการศึกษาเป็นตัวคัดเลือกความ เหมาะสมในการจัดผู้สอนลงในตารางสอน หรือนำอัลกอริทึมตัวอื่นมาพัฒนาร่วมด้วย เช่นใน ขั้นตอนการสลับสายพันธุ์ มีการสุ่มตำแหน่งที่จะสลับสายพันธุ์ อาจจะใช้อัลกอริทึมตัวอื่นเข้ามา ช่วยในการสุ่มตำแหน่ง เพื่อทำให้ได้รุ่นลูกที่มีประสิทธิภาพที่ดีขึ้น