Wednesday, July 5, 2017

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
CD850000

ออกแบบตารางการผลิต (ระยะเวลา 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) 



No comments: