Genetic Algorithm (ขั้นตอนวิธีเชิงพันธุกรรม)

Genetic Algorithm (ขั้นตอนวิธีเชิงพันธุ์กรรม)  

    ** เนื่องจากภาษาไทยมันยาวต่อไปจะเรียกย่อเป็น GA 

    GA เกิดขึ้นมาจาก 

• ทฤษฎีวิวัฒนาการของ Charles Darwin มีรายละเอียดคราว ๆ ดังนี้  "การคัดเลือกสายพันธุ์ที่มีความเหมาะสม(Fitness) กับสภาพแวดล้อมจะมีโอกาสอยู่รอดได้มากและ มีโอกาสถ่ายทอดลักษณะทางพันธุกรรมไปสู่ลูกหลานรุ่นต่อไป ในขณะที่สายพันธุ์ที่ไม่เหมาะสมกับสภาพแวดล้อมจะมีโอกาสอยู่รอดได้น้อยและมีโอกาสสูญพันธุ์ไปในที่สุด " 

• ทฤษฎีถ่ายทอดลักษณะทางพันธุกรรม Gregor Mendel  คือ ลูกจะได้รับลักษณะเด่น ลักษณะด้อยจากพ่อและแม่ ผ่านการสืบพันธ์ โดยมีอัตราส่วนที่แน่นอน สามารถคำนวณได้ เป็นอัตราส่วน  4:1   ตามลำดับ

GA ใช้ในการแก้ไขปัญหา Optimization, จัดตารางเวลาการผลิตที่มี Factor เยอะ ๆ, จัดตารางการเดินทาง (logistics), หรือคำตอบของ function อนุพันธ์ ต่าง ๆ ผ่านการวิวัฒนาการจนได้รับคำตอบที่ดีที่สุด (Finess)

ขั้นตอนการทำงานของ GA

1. ออกแบบ "รูปแบบคำตอบ" หรือ โครโมโซม โดยรูปแบบโครโมโซมส่วนใหญ่แล้วจะสร้างขึ้นมาในรูปของตัวเลขฐาน 2 
2. กำหนด โครโมโซม ใน รุ่นที่ 1, กำหนด "จำนวนรุ่นที่ต้องการสร้าง" , จำนวนของโครโมโซมที่ต้องการ  ** ถ้าไม่ต้องการกำหนดจำนวนรุ่นที่ต้องการสร้าง อาจจะกำหนดเป็นเงื่อนไขของ ค่า Fitness Function ก็ได้ 
3. ออกแบบ "Fitnesss Function" สำหรับใช้ในการทดสอบความแข็งแรงของ โครโมโซมแต่ละตัว function นี้จะเป็น function หลักที่จะใช้ตรวจสอบว่า โครโมโซมไหนแข็งแรงเพียงพอ ที่จะเป็น พ่อ และแม่พันธ์ุ สำหรับ รุ่นที่ 2
4. ออกแบบวิธีการวิวัฒนาการ พร้อมทั้งกำหนดอัตราส่วนสำหรับวิธีการต่าง ๆ 
1. crossover การสืบพันธ์โดยผสมยีนส์ จากโคโมโซมของพ่อ และแม่ เพื่อสืบลักษณะเด่น 
1. Single - Point CrossOver  คือ การนำยีสต์ ตัวที่เป็นหลักเลขคี่ของพ่อ มารวมกับหลักเลขคู่ของแม่ หรือสลับกันก็ได้ เพื่อให้ได้ โครโมโซมใหม่ (ลูก) 
2. Two - Point CrossOver คล้ายกับแบบ Single แต่ดึงมารวมกับทีละ 2 ยีนส์
3. Uniform Crossover กำหนดรูปแบบการรวมกับเอง 
2. Reproduction เป็นการนำโครโมโซมของรุ่นก่อนหน้าที่มีค่า Fitness ที่ดี มาใช้ใน รุ่นต่อมา
3. Mutation การสร้างโครโมโซมขึ้นมาโดยมีรูปแบบที่ไม่แน่นอน เช่น Random เป็นต้น 
5. ทำการคัดกรอง โครโมโซม รุ่นที่ 1 ผ่าน Fitness Function คัดกรองโดยการเรียงลำดับความแข็งแรง
6. ทำการวิวัฒนาการของโครโมโซม รุ่นที่ 2 โดยใช้ พ่อ แม่ จากรุ่นที่ 1 เมื่อได้จำนวนครบตามที่ต้องการแล้ว ก็กลับไปทำตามข้อ 5 ใหม่ 
7. เมื่อครบ "จำนวนรุ่นที่ต้องการสร้าง" แล้วก็แสดงผลลัพธ์ค่าคำตอบที่ดีที่สุด 

อ้างอิง https://kapitaennem0.wordpress.com/2013/07/17/genetic-algorithm/

โจทก์ตัวอย่าง

   โรงงาน AAA  มีเครื่องจักรทั้งหมด 4 เครื่อง แต่ละเครื่องมีกำลังการผลิต และระยะเวลาทำงานแตกต่างกัน  รายละเอียดดังนี้

ชื่อเครื่องจักร	กำลังการผลิต	เวลาเปิดทำงาน ช.ม.	ค่าไฟฟ้า
M-A	2500	24	1500
M-B	4000	12	2500
M-C	5000	18	3000
M-D	10000	24	10000

โดย มีวัสดุการผลิตเท่ากันทุกเครื่องจักร

มีคำสั่งซื้อ ดังนี้

บริษัท	เวลารับสินค้าห่างจากวันปัจจุบัน (วัน)	จำนวน
CA	3	2000
CB	5	30000
CC	12	100000
CD	8	50000

ออกแบบตารางการผลิต (ระยะเวลา 14 วัน) ที่มีต้นทุนค่าไฟฟ้าถูกที่สุด และส่งของได้ครบภายในวันเวลาที่กำหนด

1. ออกแบบ โครโมโซมจากโจทก์   ตารางการผลิต 14 วัน นับจากปัจจุบัน 
   
   
   
   
   
   
   
   
   
   
   
2. กำหนดจำนวน ต่าง ๆ 
1. จำนวนโครโมโซม ในแต่ละรุ่น  = 100
2. .จำนวน Generation = 100 Gen 
3. ออกแบบ Fitness Function มีเงื่อนไข 
1. ต้องส่งสินค้าได้ัทันกำหนด อ่านข้อมูลจาก "ตารางคำสั่งซื้อ" โดย เทียบจำนวนที่ผลิตได้ในวันที่ต้องส่งสินค้า ว่าผลิตครบตามจำนวนนั้นหรือไม่  โดยกำหนดไว้กรณีแผนการผลิตที่ผลิตไม่่ทัน จะมีคะแนน FitnessScore = 0 ทันที 
2. คำนวน ค่าไฟฟ้าของ แผนการที่มีค่า FitnessScore !=0 แล้วเรียงลำดับจาก ใช้ไฟฟ้าน้อย > ใช้ไฟฟ้ามาก > โครโมโซมที่มีค่า FitnessScore = 0  
4. กำหนดรายละเอียดของการวิวัฒนาการ
1. Re-production (30%) - นำโครโมโซม 30 อันดับแรกจาก ข้อ 3.2  
2. Crossover (60%) -  นำโครโมโซมจากข้อ 4.1  มาเป็น พ่อ - แม่ พันธ์ุ
1. single-point Crossover (25%)  
2. two-point Crossover (25%)
3. uniform Crossover (10%)
3. Mutation (10%) -  Random ค่าโครโมโซมขึ้นมาให้ถูกต้องตามรูปแบบโครโมโซม 
5. นำโครโมโซมรุ่นที่ 1 ทั้งหมดมาผ่าน Fitness Function ตามข้อ 3 
6. ทำการวิวัฒนาการเพื่อสร้าง โครโมโซมรุ่นที่ 2  ตามข้อ 4
7. กลับไปทำตามข้อ 5 ใหม่ จนกระทั้ง ครบจำนวน Gen ที่ต้องการ (100 gen)