ล งก ข ามภาษา ในบทความน ม ไว ให ผ อ านและผ ร วมแก ไขบทความศ กษาเพ มเต มโดยสะดวก เน องจากว ก พ เด ยภาษาไทยย งไม ม บทความด

วิธีการลอกแบบ (อังกฤษ: 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' 2011-09-27 ที่ เวย์แบ็กแมชชีน, Soft Computing Journal, Completed & In Press, 2008.
IEEE Computational Intelligence Society Emergent Technologies Task Force on Memetic Computing 2011-09-27 ที่ เวย์แบ็กแมชชีน
IEEE Congress on Evolutionary Computation (CEC 2007) 2010-03-06 ที่ เวย์แบ็กแมชชีน, Singapore, Special Session on Memetic Algorithms 2008-02-16 ที่ เวย์แบ็กแมชชีน.
'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, , 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.