ขั้นตอนวิธีการลอกแบบ

บทนำ

ในปี ค.ศ. 1983 Richard Dawkins ได้ตั้งชื่อทฤษฎี Universal Darwinism ให้กับระบบที่มีการกำกับดูแลที่ซับซ้อนใด ๆ โดยเฉพาะอย่างยิ่งทฤษฎี Universal Darwinism นั้น ชี้ให้เห็นถึงวิวัฒนาการที่ไม่จำกัดเพียงระบบทางชีววิทยา นั่นหมายถึงมันไม่ได้จำกัดอยู่ในกรอบแคบ ๆ ของลักษณะยีน แต่ใช้กับระบบที่ซับซ้อนใด ๆ ที่แสดงหลักการของการสืบทอด การเปลี่ยนแปลง และการเลือก จึงสามารถเติมเต็มลักษณะของระบบวิวัฒนาการ ตัวอย่างเช่น ศาสต์ใหม่ของมีมีติกที่แสดงถึงระบบอนาล็อกใจกลางของพันธุศาสตร์ในการวิวัฒนาการทางวัฒนธรรมที่ทอดยาวข้ามขอบเขตของชีววิทยา ความรู้ และจิตวิทยา ซึ่งได้รับความสนใจอย่างมากในทศวรรษที่ผ่านมา คำว่า "meme" ถูกนิยาม และให้ความหมายโดย Dawkins ในปี ค.ศ. 1976 เป็นหน่วยพื้นฐานของการส่งผ่านทางวัฒนธรรมหรือการเลียนแบบ และในพจนานุกรมภาษาอังกฤษ ฉบับออกซฟอร์ด มีความหมายว่า องค์ประกอบของวัฒนธรรมที่อาจจะส่งผ่านบนโดยวิธีการที่ไม่ใช่ทางพันธุกรรม
โดยทั่วไปการใช้ไอเดียของมีมีติก ภายในกรอบการคำนวณจะถูกเรียกว่า Memetic Computing(MC) การใช้ Memetic Computing ทำให้ลักษณะของ Universal Darwinism มีความเหมาะสมมากขึ้น เมื่อมองในมุมนี้ การลอกแบบ หรือมีมีติกขั้นตอนวิธีจะเป็นแนวคิดที่จำกัดขึ้นของ Memetic Computing หรืออีกนัยหนึ่งการลอกแบบเป็นเพียงส่วนหนึ่งของ Memetic Computing โดยเฉพาะอย่างยิ่งในการจัดการกับพื้นที่ของขั้นตอนวิธีวิวัฒนาการที่เกี่ยวข้องกับเทคนิคการปรับแต่งอื่น ๆ เพื่อเพิ่มประสิทธิภาพในการแก้ปัญหา Memetic Computing ได้ขยายแนวคิดของ memes ให้ครอบคลุมแนวความคิดของวิธีการเพิ่มประสิทธิภาพความรู้ หรือข้อคิดเห็น

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

ขั้นตอนการทำงานเริ่มต้นจากการกำหนดส่วนประกอบของตัวแทนผลเฉลย หรือคำตอบที่ต้องการค้นหา โดยจะสร้างกลุ่ม หรือประชากรของคำตอบเริ่มต้น ด้วยการสุ่มเพื่อเข้าสู่กระบวนการทางพันธุกรรม (Genetic Operations) โดยทำการสลับสายพันธุ์ (Crossover) และการกลายพันธุ์ (Mutation) ซึ่งเป็นปฏิบัติการที่สำคัญของขั้นตอนวิธีเจนิติก แต่ในขั้นตอนวิธีมีมีติกจะมีการเพิ่มขั้นตอนของการค้นหาแบบเฉพาะที่ (Local Search) เพื่อช่วยปรับปรุงประสิทธิภาพให้ประชากรดีขึ้น และให้ได้ผลลัพธ์ที่ดีขึ้น จากนั้นนำผลลัพธ์ไปประเมินค่าความเหมาะสม (Fitness Evaluation) เพื่อคัดเลือกผลลัพธ์หรือโครโมโซมที่ดี (Chromosome Selection) ไปเป็นตัวแทนประชากรของรุ่นถัดไป โดยรายละเอียดการทำงานในแต่ละขั้นตอนสามารถอธิบายได้ดังนี้
ขั้นตอนที่ 1 การกำหนดรูปแบบโครโมโซม (Chromosome Representation) คือจะเริ่มด้วย การเข้ารหัสของปัญหา เพื่อสร้างรายการของหน่วยพันธุกรรม ซึ่งสามารถแทนได้ทั้งแบบตัวเลข, ตัวอักษร และตัวเลขผสมกับตัวอักษร
ขั้นตอนที่ 2 การสร้างประชากรเริ่มต้น (Population Initialization) ซึ่งเป็นการสุ่มค่าของพันธุกรรม เพื่อประกอบกันขึ้นเป็นโครโมโซมหลาย ๆ โครโมโซม ซึ่งจะแทนผลเฉลย หรือคำตอบที่เป็นไปได้ โดยจำนวนโครโมโซมจะถูกสุ่มสร้างขึ้นตามขนาดของประชากรที่กำหนดไว้
ขั้นตอนที่ 3 ขบวนการทางพันธุกรรม (Genetic Operations) ซึ่งประกอบด้วย การสลับสายพันธุ์ และการกลายพันธุ์ โดยจะสุ่มเลือกโครโมโซมพ่อแม่จากประชากรเพื่อสร้างโครโมโซมลูก ซึ่งการสลับสายพันธุ์ คือการสุ่มเลือกโครโมโซมพ่อแม่มาเพื่อดำเนินการตัดและ/หรือสลับรวมลักษณะจากโครโมโซมพ่อแม่ให้ได้โครโมโซมลูก จำนวนของโครโมโซมพ่อแม่จะถูกสุ่มเลือกขึ้นมาตามค่าความน่าจะเป็นในการการสลับสายพันธุ์ที่กำหนดไว้ ขณะที่ การกลายพันธุ์ คือการสุ่มเลือกโครโมโซมต้นแบบขึ้นมาหนึ่งโครโมโซม และสุ่มหน่วยพันธุกรรม ในโครโมโซมเพื่อทำการเปลี่ยนแปลงค่าทำให้ได้โครโมโซมลูกชุดใหม่หนึ่งโครโมโซม จำนวนโครโมโซมต้นแบบจะถูกสุ่มเลือกขึ้นมาตามค่าความน่าจะเป็นในการมิวเตชั่น
ขั้นตอนที่ 4 การค้นหาแบบเฉพาะที่ (Local Search) มักจะถูกใช้หลังจากขบวนการทางพันธุกรรม ด้วยความหวังที่จะเพิ่มประสิทธิภาพของวิธีเจนิติก
ขั้นตอนที่ 5 การประเมินค่าความเหมาะสม (Fitness Evaluation) เป็นขั้นตอนการถอดรหัสโครโมโซม เพื่อคำนวณหาค่าความเหมาะสมตามฟังก์ชันเป้าหมาย หรือฟังก์ชันความเหมาะสมของปัญหาที่ได้กำหนดไว้ ค่าความเหมาะสมของแต่ละโครโมโซมจะถูกใช้กำหนดความน่าจะเป็นในการอยู่รอด
ขั้นตอนที่ 6 การคัดเลือกโครโมโซม (Chromosome Selection) คือการคัดเลือกโครโมโซม เพื่อเป็นประชากรในรุ่นถัดไป กระบวนการคัดเลือก ที่ถือได้ว่ามีชื่อเสียงและเป็นที่รู้จักดีที่สุด คือ Holland’s Proportionate Selection หรือที่เรียกว่า กระบวนการของวงล้อรูเลท ซึ่งจะมีการสุ่มค่าที่อยู่ในช่วง 0-1 จำนวนครั้งในการสุ่มเท่ากับขนาดของประชากร และถ้าสุ่มตกในช่องของโครโมโซมใด โครโมโซมนั้นจะถูกคัดเลือกไปเป็นประชากรในรุ่นถัดไป ขั้นตอนการทำงานจะวนซ้ำกลับไปขั้นตอนที่ 3 จนกว่าจะเป็นไปตามเงื่อนไขของหยุดการทำงาน (Termination Criterion)

การทดสอบประสิทธิภาพวิธีการลอกแบบ(มีมีติกขั้นตอนวิธี)

จากบทความวิจัยได้พัฒนาโปรแกรมที่เขียนขึ้นด้วยภาษา Microsoft Visual Studio .NET 2003 โดยเป็นการทดสอบการแก้ปัญหาสมการคณิตศาสตร์ที่มีผลเฉลยแบบต่อเนื่อง 2 สมการ ได้แก่ สมการพาราโบลิค (Parabolic function) และสมการโพลิโนเมียล (Polynomial function) ด้วยขั้นตอนวิธีแก้ปัญหาแบบขั้นตอนวิธีเจนิติก และวิธีการลอกแบบ(มีมีติกอัลกอรึทึม) เพื่อเปรียบเทียบประสิทธิภาพการหาคำตอบระหว่างสองวิธีนี้
โดยได้แบ่งการศึกษาออกเป็น 3 การทดลอง สำหรับการทดลองแรกเป็นการศึกษาค่าระดับปัจจัยของขั้นตอนวิธีเจนิติก (Genetic Parameters) ที่มีผลต่อการหาผลเฉลยจากสมการทั้ง 2 สมการที่กล่าวไว้ข้างต้น ขณะที่การทดลองที่ 2 เป็นการศึกษาค่าระดับปัจจัยของเทคนิคซัฟเฟิลฟรอกลิปปิง ที่มีผลต่อการหาผลเฉลยจากสมการ และการทดลองที่ 3 เป็นการศึกษาเปรียบเทียบประสิทธิภาพการหาคำตอบระหว่างขั้นตอนวิธีเจนิติก และวิธีการลอกแบบ(มีมีติกอัลกอรึทึม)
ผลจากการทดลองพบว่าวิธีการลอกแบบ(มีมีติกอัลกอรึทึม) มีประสิทธิภาพในการหาค่าผลเฉลยได้ดีกว่าสามารถหาค่าผลเฉลยได้เข้าใกล้ค่าที่ดีที่สุดได้มากกว่าขั้นตอนวิธีเจนิติก แต่ใช้ระยะเวลาในการประมวลผลนานมากกว่าเล็กน้อย

วิธีการ(ขั้นตอนวิธี) ที่เกี่ยวข้อง

Genetic algorithm
Mutation
Crossover