อัลกอริทึมสำหรับการจัดสรรโมบายล์เอเจนต์ในระบบการสืบค้นข้อมูล

Abstract

วิทยานิพนธ์ฉบับนี้ได้เสนออัลกอริทึมที่ใช้ในการกำหนดเส้นทางให้กับโมบายล์เอเจนต์ โดยใช้อัลกอริทึม Simulated Annealing และอัลกอริทึม Tabu Search มาประยุกต์ใช้ควบคู่กับอัลกอริทึมฮิวริสติกที่คิดขึ้น และทำการเปรียบเทียบผลลัพธ์ที่ได้กับอัลกอริทึม Brute Force Search (BF) อัลกอริทึม Simulated Annealing (SA) อัลกอริทึม Tabu Search (Tabu) อัลกอริทึม Modified Compact Genetic Algorithm (McGA) (ซึ่งประยุกต์มาจากอัลกอริทึม Compact Genetic Algorithm : cGA) และอัลกอริทึมกำหนดเส้นทางแบบสุ่มที่มีการกระจายแบบยูนิฟอร์ม (Random Uniformly : RU) สำหรับพารามิเตอร์ที่นำมาใช้วิเคราะห์เปรียบเทียบคือค่าต้นทุนที่ต่ำที่สุดของเส้นทางย่อยที่มีค่าสูงที่สุด (Minimum of Maximum Sub-Route Cost : MMSRC) และเวลาที่ใช้ในการประมวลผล ผลลัพธ์ที่ได้จากการวิเคราะห์แสดงให้เห็นว่า กรณีจำนวนโนดในเนตเวิร์กมีค่าต่ำ อัลกอริทึมฮิวริสติกจะให้ค่า MMSRC ที่มีค่ามากกว่าค่า MMSRC ที่ได้จากอัลกอริทึม BF, SA, Tabu และ McGA แต่ให้ค่า MMSRC ที่ต่ำกว่ามากเมื่อเทียบกับอัลกอริทึม RU เมื่อวิเคราะห์กรณีจำนวนโนดในเนตเวิร์กมีค่าสูงอัลกอริทึมฮิวริสติกจะให้ค่า MMSRC ที่ต่ำกว่าค่า MMSRC ที่ได้จากอัลกอริทึม SA และจากการวัดค่าเวลาประมวลผลของแต่ละอัลกอริทึม ผลลัพธ์แสดงให้เห็นว่าอัลกอริทึมฮิวริสติกจะใช้เวลาประมวลผลโดยเฉลี่ยน้อยกว่าอัลกอริทึมกำหนดเส้นทางชนิดอื่น ๆ อย่างเห็นได้ชัด ในการพัฒนากรรมวิธีการกำหนดเส้นทางให้กับโมบายล์เอเจนต์ของงานวิจัยนี้ อาศัยการประยุกต์แนวคิดมาจากปัญหาการเดินทางของเซลส์แมน (Traveling Salesman Problem : TSP) โดยมีข้อกำหนดว่า เซลส์แมนไม่สามารถเดินย้อนเส้นทางเดิมได้ ซึ่งแตกต่างจากกรณีการกำหนดเส้นทางให้กับโมบายล์เอเจนต์ โดยโมบายล์เอเจนต์สามารถเดินย้อนกลับผ่านเส้นทางเดิมได้ ดังนั้นเพื่อศึกษาถึงผลกระทบของข้อจำกัดดังกล่าว วิทยานิพนธ์จึงได้พิจารณาเพิ่มเติมโดยนำรีดิวซ์เมตริกซ์มาประยุกต์ใช้เพื่อช่วยในการวิเคราะห์การกำหนดเส้นทางให้กับโมบายล์เอเจนต์กรณีย้อนกลับเส้นทางเดิมได้ ซึ่งการใช้งานรีดิวซ์เมตริกซ์ในวิทยานิพนธ์ฉบับนี้ได้แบ่งออกเป็น 2 วิธี คือวิธีแทนค่า และวิธีประยุกต์ จากผลลัพธ์แสดงให้เห็นว่า วิธีประยุกต์โดยส่วนใหญ่จะให้ผลลัพธ์ที่ดีกว่าวิธีแทนค่า อย่างไรก็ตามในบางกรณี วิธีประยุกต์อาจให้ค่า MMSRC ที่เลวกว่ากรณีไม่ใช้รีดิวซ์เมตริกซ์ ในขณะที่วิธีแทนค่าจะให้ค่า MMSRC ที่ดีกว่ากรณีไม่ใช้รีดิวซ์เมตริกซ์เสมอ แม้ว่าการนำรีดิวซ์เมตริกซ์มาใช้แม้ว่าจะให้ค่า MMSRC ที่ลดลง แต่ความแตกต่างของค่า MMSRC ที่ลดลงนั้นอยู่ในช่วงร้อยละ 10 ดังนั้นจึงกล่าวได้ว่า การกำหนดเส้นทางให้กับโมบายล์เอเจนต์แบบอนุญาตกลับเส้นทางเดิมได้ ส่งผลกระทบต่อต้นทุนโดยรวมของการกำหนดเส้นทางให้กับโมบายล์เอเจนต์ไม่มากนัก