Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/80794
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorประภาส จงสถิตย์วัฒนา-
dc.contributor.authorกมลลักษณ์ สุขเสน-
dc.contributor.otherจุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์-
dc.date.accessioned2022-11-02T09:44:11Z-
dc.date.available2022-11-02T09:44:11Z-
dc.date.issued2564-
dc.identifier.urihttp://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.abstractalternativeResearch 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.isoth-
dc.publisherจุฬาลงกรณ์มหาวิทยาลัย-
dc.relation.urihttp://doi.org/10.58837/CHULA.THE.2021.952-
dc.rightsจุฬาลงกรณ์มหาวิทยาลัย-
dc.subject.classificationComputer Science-
dc.subject.classificationComputer Science-
dc.subject.classificationComputer Science-
dc.titleขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดควอนตัมสำหรับปัญหายาก-
dc.title.alternativeQuantum compact genetic algorithm for hard problems-
dc.typeThesis-
dc.degree.nameวิศวกรรมศาสตรดุษฎีบัณฑิต-
dc.degree.levelปริญญาเอก-
dc.degree.disciplineวิศวกรรมคอมพิวเตอร์-
dc.degree.grantorจุฬาลงกรณ์มหาวิทยาลัย-
dc.identifier.DOI10.58837/CHULA.THE.2021.952-
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
6071401321.pdf3.68 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.