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

กมลลักษณ์ สุขเสน

dc.contributor.advisor	ประภาส จงสถิตย์วัฒนา
dc.contributor.author	กมลลักษณ์ สุขเสน
dc.contributor.other	จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์
dc.date.accessioned	2022-11-02T09:44:11Z
dc.date.available	2022-11-02T09:44:11Z
dc.date.issued	2564
dc.identifier.uri	http://cuir.car.chula.ac.th/handle/123456789/80794
dc.description	วิทยานิพนธ์ (วศ.ด.)--จุฬาลงกรณ์มหาวิทยาลัย, 2564
dc.description.abstract	งานวิจัยทางด้านคอมพิวเตอร์เชิงควอนตัม (Quantum computer) ยังคงเป็นความท้าทายสำหรับนักวิจัยในการพัฒนาเทคนิคต่างๆเพื่อให้การประมวลผลข้อมูลควอนตัมขนาดใหญ่สามารถทำได้จริง มีงานวิจัยหลากหลายสาขาเกี่ยวกับการจำลองระบบควอนตัม โดยเฉพาะด้านอัลกอริทึมควอนตัมสำหรับแก้ปัญหา NP-hard ซึ่งใช้เวลาแก้ปัญหานานเกินกว่าจะเป็นไปได้จริงในเครื่องคอมพิวเตอร์ดั้งเดิม งานวิจัยนี้นำเสนอขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดควอนตัม ซึ่งเป็นการนำข้อได้เปรียบจากการประมวลผลเชิงควอนตัม ได้แก่ สภาวะซ้อนทับของสถานะควอนตัม และการประมวลผลควอนตัมแบบขนานในอัลกอริทึมการค้นหาของโกรเวอร์ (Grover's search algorithm) มาประยุกต์ใช้ในกระบวนการคัดเลือกโครโมโซมของขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดดั้งเดิมที่มีการคัดเลือกโครโมโซมที่ดี เพื่อให้ได้ขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดควอนตัมที่มีประสิทธิภาพดีขึ้นในแง่ของความถูกต้องของคำตอบ ขั้นตอนวิธีที่นำเสนอสามารถแก้ปัญหา traveling salesman ขนาดเล็กได้บนเครื่องจำลองคอมพิวเตอร์ควอนตัม เนื่องจากจำนวนคิวบิตที่มีอย่างจำกัดจึงไม่สามารถทำการทดลองกับปัญหา traveling salesman ขนาดใหญ่ได้ แม้ว่าจำนวนฟังก์ชันที่ใช้ในการประเมินค่าความเหมาะสมของขั้นตอนวิธีที่นำเสนอมีแนวโน้มเพิ่มขึ้นเป็นเอ็กโปเน็นเชียลเมื่อจำนวนเมืองเพิ่มขึ้น แต่ยังสามารถหาคำตอบที่ถูกต้องได้ดีกว่าขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดดั้งเดิม นอกจากนี้ผลการทดลองแสดงให้เห็นว่าจำนวนรอบของโกรเวอร์ที่เหมาะสมช่วยเพิ่มประสิทธิภาพในการหาคำตอบที่เหมาะสมที่สุด ในขณะที่จำนวนช็อตหรือจำนวนรอบที่รันอัลกอริทึมช่วยเพิ่มความน่าเชื่อถือให้กับคำตอบที่ได้จากการวัดค่าสถานะคิวบิต
dc.description.abstractalternative	Research in the field of quantum technology remains a great challenge to researchers in the future to develop techniques for making large-scale quantum information processing a reality. The simulation of quantum systems is an important problem in many fields. A quantum algorithm is one of the topics being studied for solving NP-hard problems that take too long to solve on classical computers. This paper aims to propose the Quantum compact genetic algorithm, that exploits the advantages of quantum computing. There is quantum superposition and quantum parallelism in Grover's search algorithm. It was combined with a compact genetic algorithm with an elite (cGA with an elite) in the selection process to get a higher performance in term of the solution quality. The proposed algorithm can be run on an IBM QASM simulator to solve the small-sized traveling salesman problem (TSP). Although the number of function evaluations of the proposed algorithm grows exponentially as the number of cities grows, it still outperforms the cGA with an elite in finding the optimal solution. The results also showed that utilizing the right number of Grover iterations increases the efficiency in finding the optimal solution, whereas the number of shots increases the reliability of the answers.
dc.language.iso	th
dc.publisher	จุฬาลงกรณ์มหาวิทยาลัย
dc.relation.uri	http://doi.org/10.58837/CHULA.THE.2021.952
dc.rights	จุฬาลงกรณ์มหาวิทยาลัย
dc.subject.classification	Computer Science
dc.subject.classification	Computer Science
dc.subject.classification	Computer Science
dc.title	ขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดควอนตัมสำหรับปัญหายาก
dc.title.alternative	Quantum compact genetic algorithm for hard problems
dc.type	Thesis
dc.degree.name	วิศวกรรมศาสตรดุษฎีบัณฑิต
dc.degree.level	ปริญญาเอก
dc.degree.discipline	วิศวกรรมคอมพิวเตอร์
dc.degree.grantor	จุฬาลงกรณ์มหาวิทยาลัย
dc.identifier.DOI	10.58837/CHULA.THE.2021.952