ขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดควอนตัมสำหรับปัญหายาก

Abstract

งานวิจัยทางด้านคอมพิวเตอร์เชิงควอนตัม (Quantum computer) ยังคงเป็นความท้าทายสำหรับนักวิจัยในการพัฒนาเทคนิคต่างๆเพื่อให้การประมวลผลข้อมูลควอนตัมขนาดใหญ่สามารถทำได้จริง มีงานวิจัยหลากหลายสาขาเกี่ยวกับการจำลองระบบควอนตัม โดยเฉพาะด้านอัลกอริทึมควอนตัมสำหรับแก้ปัญหา NP-hard ซึ่งใช้เวลาแก้ปัญหานานเกินกว่าจะเป็นไปได้จริงในเครื่องคอมพิวเตอร์ดั้งเดิม

งานวิจัยนี้นำเสนอขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดควอนตัม ซึ่งเป็นการนำข้อได้เปรียบจากการประมวลผลเชิงควอนตัม ได้แก่ สภาวะซ้อนทับของสถานะควอนตัม และการประมวลผลควอนตัมแบบขนานในอัลกอริทึมการค้นหาของโกรเวอร์ (Grover's search algorithm) มาประยุกต์ใช้ในกระบวนการคัดเลือกโครโมโซมของขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดดั้งเดิมที่มีการคัดเลือกโครโมโซมที่ดี เพื่อให้ได้ขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดควอนตัมที่มีประสิทธิภาพดีขึ้นในแง่ของความถูกต้องของคำตอบ ขั้นตอนวิธีที่นำเสนอสามารถแก้ปัญหา traveling salesman ขนาดเล็กได้บนเครื่องจำลองคอมพิวเตอร์ควอนตัม เนื่องจากจำนวนคิวบิตที่มีอย่างจำกัดจึงไม่สามารถทำการทดลองกับปัญหา traveling salesman ขนาดใหญ่ได้ แม้ว่าจำนวนฟังก์ชันที่ใช้ในการประเมินค่าความเหมาะสมของขั้นตอนวิธีที่นำเสนอมีแนวโน้มเพิ่มขึ้นเป็นเอ็กโปเน็นเชียลเมื่อจำนวนเมืองเพิ่มขึ้น แต่ยังสามารถหาคำตอบที่ถูกต้องได้ดีกว่าขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดดั้งเดิม นอกจากนี้ผลการทดลองแสดงให้เห็นว่าจำนวนรอบของโกรเวอร์ที่เหมาะสมช่วยเพิ่มประสิทธิภาพในการหาคำตอบที่เหมาะสมที่สุด ในขณะที่จำนวนช็อตหรือจำนวนรอบที่รันอัลกอริทึมช่วยเพิ่มความน่าเชื่อถือให้กับคำตอบที่ได้จากการวัดค่าสถานะคิวบิต