6.2. Performance comparison based o

6.2. Performance comparison based on execution time

In addition to evaluating the performance of the algorithms in terms of the quality of the solutions obtained for a fixed number of evaluations, we have also carried out an evaluation in terms of computation time. Basically, we measure the computation time spent by both pairs of algorithms, MA − MAr and ILS − ILSr, to perform k iterations 6 (recall that both approaches, the classical and the restricted, follow the same path, and therefore, after k iterations the same solution will be reached). Particularly, we compare the computation time of the basic approaches with respect to the computation time of the restricted approaches that include: (1) the computation of the restrictions matrix at the beginning of the algorithm, and (2) a greedy local search under the restricted insert neighbourhood which, for each index, reads in the restrictions matrix the range of the positions to which the index can be moved.

It is clear that the execution time needed to perform a given number of iterations with the restricted approaches, ILSr and MAr, depends on the sparsity of the restrictions matrix associated to each particular instance. That is, the higher the number of zero-valued entries, the lower the checked neighbours, and therefore, the faster the greedy local search. In order to obtain a more general picture of the influence of the sparsity in the execution time, in this experiment, apart from the previously used benchmarks, xLOLIB and xLOLIB2, we have included additional instances with different sparsities. Particularly, we have considered the most common benchmarks for the LOP: LOLIB, LMC and MB. The number of iterations was set to k = 10, 000 without any previous experimentation. Results are displayed in Fig. 9 and Fig. 10.

ผลลัพธ์ (ไทย) 1:

6.2. ประสิทธิภาพเปรียบเทียบตามช่วงเวลาที่การดำเนินการนอกจากประเมินประสิทธิภาพการทำงานของอัลกอริทึมในแง่ของคุณภาพของการแก้ปัญหาที่ได้รับสำหรับการประเมินจำนวน เรามียังดำเนินการประเมินในแง่ของเวลาการคำนวณ โดยทั่วไป เราวัดการคำนวณเวลาที่ใช้ โดยทั้งสองคู่ของอัลกอริทึม MA −มี.ค. และ ILS − ILSr การทำซ้ำ k 6 (จำว่า ทำตามทั้งสองวิธี ที่คลาสสิกและจำกัด เส้นทาง และดังนั้น หลังจากการวนซ้ำ k โซลูชันเดียวจะถึง) โดยเฉพาะ เราเปรียบเทียบเวลาการคำนวณของวิธีพื้นฐานเกี่ยวข้องกับเวลาการคำนวณของวิธีจำกัดที่มี: (1) การคำนวณเมทริกซ์จำกัดที่เริ่มต้นของอัลกอริทึม และ (2) การค้นหาท้องถิ่นโลภภายใต้การจำกัดแทรกละแวกซึ่ง สำหรับแต่ละดัชนี อ่านในเมตริกซ์จำกัดช่วงของตำแหน่ง ไปซึ่งดัชนีที่สามารถเคลื่อนย้ายเป็นที่ชัดเจนว่า เวลาดำเนินการที่จำเป็นในการทำซ้ำด้วยวิธีจำกัด ILSr และ MAr จำนวนขึ้นอยู่กับ sparsity ของเมตริกซ์ข้อจำกัดที่เกี่ยวข้องกับแต่ละอินสแตนซ์ นั่นคือ สูงกว่าหมายเลขของรายการมูลค่าศูนย์ ต่ำกว่าประเทศเพื่อนบ้านที่เลือก และดังนั้น เร็วท้องโลภค้น เราได้รวมอินสแตนซ์เพิ่มเติมกับ sparsities แตกต่างกันเพื่อรับรูปภาพเพิ่มเติมของอิทธิพลของ sparsity ในเวลาดำเนินการ ในการทดลองนี้ นอกเหนือจากเกณฑ์มาตรฐานที่ใช้ก่อนหน้านี้ xLOLIB และ xLOLIB2 โดยเฉพาะอย่างยิ่ง ที่เราได้พิจารณาเกณฑ์มาตรฐานทั่วไปสำหรับชาวลพบุรี: LOLIB, LMC และ MB การตั้งค่าทั่วไป k = 10, 000 โดยไม่ต้องทดลองใด ๆ ก่อนหน้านี้ ผลลัพธ์จะถูกแสดงในรูปที่ 9 และ 10 รูป

ผลลัพธ์ (ไทย) 2:

6.2 การเปรียบเทียบผลการดำเนินงานตามเวลาดำเนินการ

นอกจากนี้ในการประเมินประสิทธิภาพการทำงานของอัลกอริทึมในแง่ของคุณภาพของการแก้ปัญหาที่ได้รับเป็นจำนวนคงที่ของการประเมินผลที่เราได้ดำเนินการยังออกประเมินผลในแง่ของเวลาในการคำนวณ โดยทั่วไปเราจะวัดการคำนวณเวลาที่ใช้โดยทั้งคู่ของอัลกอริทึม MA - Mar และ ILS - ILSR เพื่อดำเนิน K ซ้ำ 6 (จำได้ว่าทั้งสองวิธีที่คลาสสิกและ จำกัด ตามเส้นทางเดียวกันและดังนั้นหลังจากการทำซ้ำ K วิธีการแก้ปัญหาเดียวกันจะถึง) โดยเฉพาะอย่างยิ่งเราเปรียบเทียบเวลาในการคำนวณของวิธีการพื้นฐานที่เกี่ยวกับเวลาในการคำนวณของวิธีการที่ถูก จำกัด ที่รวมถึง: (1) การคำนวณเมทริกซ์ข้อ จำกัด ที่จุดเริ่มต้นของขั้นตอนวิธีและ (2) การค้นหาในท้องถิ่นโลภภายใต้ ย่านแทรก จำกัด ซึ่งสำหรับแต่ละดัชนีอ่านในข้อ จำกัด เมทริกซ์ช่วงของตำแหน่งที่ดัชนีสามารถเคลื่อนย้ายได้.

เป็นที่ชัดเจนว่าเวลาดำเนินการที่จำเป็นในการดำเนินการจำนวนที่กำหนดของการทำซ้ำด้วยวิธีการที่ถูก จำกัด , ILSR และ Mar ขึ้นอยู่กับ sparsity ของเมทริกซ์ที่เกี่ยวข้องกับข้อ จำกัด เช่นกันโดยเฉพาะอย่างยิ่ง นั่นคือสูงกว่าจำนวนของศูนย์มูลค่ารายการที่ต่ำกว่าเพื่อนบ้านตรวจสอบและดังนั้นจึงได้รวดเร็วยิ่งขึ้นการค้นหาในท้องถิ่นโลภ เพื่อให้ได้ภาพที่กว้างขึ้นจากอิทธิพลของ sparsity ในเวลาที่ดำเนินการในการทดลองครั้งนี้นอกเหนือจากมาตรฐานใช้ก่อนหน้านี้ xLOLIB และ xLOLIB2 เราได้รวมอินสแตนซ์เพิ่มเติมกับ sparsities ที่แตกต่างกัน โดยเฉพาะอย่างยิ่งที่เราได้มีการพิจารณามาตรฐานที่พบบ่อยที่สุดสำหรับ LOP นี้: LOLIB, LMC และ MB จำนวนการทำซ้ำที่ได้รับการตั้งค่าให้ k = 10, 000 โดยไม่ต้องทดลองก่อนหน้านี้ ผลการค้นหาจะแสดงในรูป 9 รูป 10

ผลลัพธ์ (ไทย) 3:

6.2 . การเปรียบเทียบสมรรถนะในการใช้เวลานอกจากการประเมินสมรรถนะของอัลกอริทึมในแง่คุณภาพของโซลูชั่นที่ได้รับสำหรับจำนวนครั้ง เราได้ทำการประเมินในแง่ของเวลาการคำนวณ . โดยทั่วไป เราวัดค่าเวลาที่ใช้โดยทั้งสองคู่ของขั้นตอนวิธี และ ilsr −−มาร์มาอัตโนมัติ ที่จะแสดง K รอบ 6 ( จำได้ว่า ทั้งแนว คลาสสิก และ จำกัด ตามเส้นทางเดียวกัน ดังนั้น เค ซ้ำวิธีเดียวกันจะถึงหลัง ) โดยเฉพาะอย่างยิ่งเราเปรียบเทียบเวลาในการประมวลผลของวิธีการพื้นฐานเกี่ยวกับการคำนวณเวลาของวิธีการที่จำกัดรวมถึง : ( 1 ) ของข้อ จำกัด ในการคำนวณเมทริกซ์ที่จุดเริ่มต้นของขั้นตอนวิธี และ ( 2 ) โลภค้นหาท้องถิ่นใต้ จำกัด แทรกตาง ๆซึ่งในแต่ละดัชนี ที่อ่านในเมทริกซ์ จำกัด ช่วงของตำแหน่งที่ดัชนีสามารถย้ายเป็นที่ชัดเจนว่าเวลาที่ใช้ในการแสดงจำนวนของการทำซ้ำด้วยวิธีและ ilsr จำกัด , มี.ค. , ขึ้นอยู่กับ sparsity เมทริกซ์ของข้อ จำกัด ที่เกี่ยวข้องกับแต่ละอินสแตนซ์ นั่นคือ สูงกว่าตัวเลขของศูนย์มูลค่ารายการ , ลดการตรวจสอบเพื่อนบ้านและดังนั้นจึงได้เร็วขึ้นการค้นหาในท้องถิ่นโลภ เพื่อให้ได้ภาพทั่วไปมากขึ้นจากอิทธิพลของ sparsity คำพิพากษาในเวลาในการทดลองครั้งนี้ นอกจากก่อนหน้านี้ที่ใช้วัด และ xlolib xlolib2 , เราได้รวมกรณีเพิ่มเติมกับ sparsities แตกต่างกัน โดยเฉพาะอย่างยิ่งเราได้ถือเป็นมาตรฐานที่พบมากที่สุดสำหรับลพบุรี : lolib ใหญ่ และ MB จํานวนซ้ำถูกตั้งค่า K = 10 , 000 โดยการทดลองก่อนๆ ผลลัพธ์จะปรากฏในรูปที่ 9 รูปที่ 10