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

วิธีการลอกแบบ (อังกฤษ: Memetic Algorithm: MA) เป็นกระบวนการที่นำขั้นตอนวิธีเจนิติกมาไฮบริด กับเทคนิคการค้นหาแบบเฉพาะที่ ซึ่งขั้นตอนวิธีนี้ได้แนวคิดมาจากทฤษฎีมีมีติกของ Richard Dawkins ขั้นตอนวิธีการลอกแบบนี้จะคล้ายกับขั้นตอนวิธีเจนิติก และในส่วนประกอบของโครโมโซมจะถูกเรียกว่า มีม (Meme) แทนคำว่ายีน (Gene)

บทนำ

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

โดยทั่วไปการใช้ไอเดียของมีมีติก ภายในกรอบการคำนวณจะถูกเรียกว่า Memetic Computing(MC) การใช้ Memetic Computing ทำให้ลักษณะของ Universal Darwinism มีความเหมาะสมมากขึ้น เมื่อมองในมุมนี้ การลอกแบบ หรือมีมีติกขั้นตอนวิธีจะเป็นแนวคิดที่จำกัดขึ้นของ Memetic Computing หรืออีกนัยหนึ่งการลอกแบบเป็นเพียงส่วนหนึ่งของ Memetic Computing โดยเฉพาะอย่างยิ่งในการจัดการกับพื้นที่ของขั้นตอนวิธีวิวัฒนาการที่เกี่ยวข้องกับเทคนิคการปรับแต่งอื่น ๆ เพื่อเพิ่มประสิทธิภาพในการแก้ปัญหา Memetic Computing ได้ขยายแนวคิดของ memes ให้ครอบคลุมแนวความคิดของวิธีการเพิ่มประสิทธิภาพความรู้ หรือข้อคิดเห็น

รหัสเทียม

เริ่มต้น;

สร้างรูปแบบของประชากรแบบสุ่มจำนวน P รูปแบบ;

ตั้งแต่ i = 1 ไปจนถึงจำนวนทั้งหมดของรูปแบบ;

{สลับสายพันธุ์}

เลือกพ่อแม่มา 2 ชนิดแบบสุ่ม (i_a และ i_b);

สร้างลูก (i_c) ที่เกิดจาการสลับสายพันธุ์ของพ่อและแม่;

{กลายพันธุ์}

สุ่มเลือกโครโมโซมหนึ่งจาก i;

สร้างลูก (i_c) ที่เกิดจาการกลายพันธุ์ของ i;

i ที่เป็นสมาชิกของ P: ทำการค้นหาแบบเฉพาะที่ (Local Search);

i ที่เป็นสมาชิกของ P: ประเมินค่าความเหมาะสม (Fitness Evaluation);

คัดเลือกโครโมโซมด้วยกระบวนการวงล้อรูเลท (Roulette Wheel Selection);

นำโครโมโซมที่คัดเลือกเป็น i ตัวถัดไป;

จบการทำงาน;

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

ขั้นตอนการทำงานเริ่มต้นจากการกำหนดส่วนประกอบของตัวแทนผลเฉลย หรือคำตอบที่ต้องการค้นหา โดยจะสร้างกลุ่ม หรือประชากรของคำตอบเริ่มต้น ด้วยการสุ่มเพื่อเข้าสู่กระบวนการทางพันธุกรรม (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 เป็นการศึกษาเปรียบเทียบประสิทธิภาพการหาคำตอบระหว่างขั้นตอนวิธีเจนิติก และวิธีการลอกแบบ(มีมีติกอัลกอรึทึม)

ผลจากการทดลองพบว่าวิธีการลอกแบบ(มีมีติกอัลกอรึทึม) มีประสิทธิภาพในการหาค่าผลเฉลยได้ดีกว่าสามารถหาค่าผลเฉลยได้เข้าใกล้ค่าที่ดีที่สุดได้มากกว่าขั้นตอนวิธีเจนิติก แต่ใช้ระยะเวลาในการประมวลผลนานมากกว่าเล็กน้อย

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

• IEEE Workshop on Memetic Algorithms (WOMA 2009). Program Chairs: Jim Smith, University of the West of England, U.K.; Yew-Soon Ong, Nanyang Technological University, Singapore; Gustafson Steven, University of Nottingham; U.K.; Meng Hiot Lim, Nanyang Technological University, Singapore; Natalio Krasnogor, University of Nottingham, U.K.
• Memetic Computing Journal, first issue appeared in January 2009.
• 2008 IEEE World Congress on Computational Intelligence (WCCI 2008), Hong Kong, Special Session on Memetic Algorithms.
• Special Issue on 'Emerging Trends in Soft Computing - Memetic Algorithm', Soft Computing Journal, Completed & In Press, 2008.
• IEEE Computational Intelligence Society Emergent Technologies Task Force on Memetic Computing
• IEEE Congress on Evolutionary Computation (CEC 2007), Singapore, Special Session on Memetic Algorithms.
• 'Memetic Computing' by Thomson Scientific's Essential Science Indicators as an Emerging Front Research Area.
• Special Issue on Memetic Algorithms, IEEE Transactions on Systems, Man and Cybernetics - Part B, Vol. 37, No. 1, February 2007.
• Recent Advances in Memetic Algorithms, Series: Studies in Fuzziness and Soft Computing , Vol. 166, ISBN 978-3-540-22904-9, 2005.
• Special Issue on Memetic Algorithms, Evolutionary Computation Fall 2004, Vol. 12, No. 3: v-vi.

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

Genetic algorithm

Mutation

Crossover

อ้างอิง

บทความวิจัยเรื่อง การประยุกต์ใช้เทคนิคซัฟเฟิลฟรอกลิปปิงเพื่อเพิ่มประสิทธิภาพการทำงานของมีมีติกอัลกอริธึม โดย สุภัคกานดา ชมภูมิ่ง ประพล อิทธิพงษ์ และภูพงษ์ พงษ์เจริญ (บทความวิจัยนี้ได้รับการอนุญาตจากเจ้าของแล้ว)

Alkan, A. & Özcan, E. (2003). Memetic algorithms for timetabling. Yeditepe University. 34755 Kayisdagi - Istanbul/Turkey. Amiri, B., Fathian, M. & Maroosi, A. (2007). Application of shuffled frog-leaping algorithm on clustering. Iran University of Science and Technology.

Aytug, H., Khouja, M. & Vergara F.E. (2003) Use of genetic algorithm to solve production and operation management problems: a review. International Journal of Production Research, 41, 3955-4009.

Chainate, W., Thapatsuwan, P., Kaitwanidvilai, S., Muneesawang, P. & Pongcharoen, P. (2006). Improving Hopfield Neural Network Performance and Parameters Investigation, KMITL Science Journal, 6(2a), 266-273.

Chaudhry, S.S. & Luo, W. (2005) Application of genetic algorithms in production and operation management: a review. International Journal of Production Research 43, 4083-101.

Dawkins, R. (1976). The selfish gene. University Press, Oxford.

Duan, H. & Yu, X. (2007). Hybrid Ant Colony Optimization Using Memetic Algorithm for Traveling Salesman Problem. Proceedings of the IEEE Symposium on Approximate Dynamic Programming and Reinforcement Learning, 92-95.

Emad, E., Tarek, H. & Donald, G. (2005). Comparison among five evolutionary-based optimization algorithm. Advanced Engineering Informatics, 19, 43-53.

Freisleben, B. & Merz, P. (1996). A Genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. Proceedings of IEEE International Conference on Evolutionary Computation, 616-621.

Gyori, S., Petres, Z. & Varkonyi-Koczy, A.R. (2001). Genetic Algorithms in Timetabling A New Approach. Academic research, Budapest University of Technology and Economics, Budapest.

Montgomery, D.C. (1997). Design and analysis of experiments. New York, John Wiley and Sons.

Moscato, P. & Norman, M.G. (1992). A memetic approach for the travelling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing system. Proceedings of the International Conference on Parallel Computing and Transputer Application. Amsterdam, Holland, 177-186.

Genetic algorithms for flow shop scheduling problemsMurata, T., Ishibuchi, H. & Tanaka, H. (1996). . Computers and Industrial Engineering, 30 (4), 1061-1071.

Nearchou, A.C. (2004). The effect of various operators on the genetic search for large scheduling problems. International Journal of Production Economics, 88 (2), 191-203.

Applying designed experiments Pongcharoen, P. Stewardson, D.J., Hicks, C. & Braiden, P.M. (2001). to optimize the performance of genetic algorithms used for scheduling complex products in the capital goods industry. Journal of Applied Statistics, 28(3), 441-455.

Pongcharoen, P., Hicks, C., Braiden, P.M. & Stewardson, D.J. (2002). Determining optimum genetic algorithm parameters for scheduling the manufacturing and assembly of complex products, International Journal of Production Economics, 78(3), 311-322.

Pongcharoen, P., Hicks, C. & Braiden, P.M. (2004). The development of genetic algorithms for the finite capacity scheduling of complex products, with multiple levels of products structure, European Journal of Operational Research, 152(1), 215-225.

Stochastic optimisation timetabling Pongcharoen, P., Promtet, W., Yenradee, P. & Hicks, C. (2007). tool for university course scheduling, Revised and submitted to the International Journal of Production Economics.

Sermpattarachai, P. & Luangpaiboon, P. (2005). Response Surface Methodology via Ant colony Optimisation. Department of Industrial Engineering Faculty of Engineering. Thammasat University, Thailand.