Local search heuristics are an impo

Local search heuristics are an important class of algorithms for obtaining goodsolutions for hard combinatorial optimization problems. Important issues forthese heuristics are solution quality and the time needed to obtain a good solution.

Roughly speaking, a local search heuristic starts with an initial solution, e.g.obtained with the help of a constructive heuristic. The local search heuristic then iteratively explores a neighborhood of the current solution and chooses a new solution out of this neighborhood to become the next current solution. Often, only new solutions are considered, which improve on the current one. The local search heuristic halts if some stopping criterion is met, e.g. there exists no better solution in the neighborhood.

The neighborhood is a critical issue in a local search heuristic. It directly influences the local behavior of a local search heuristic, since it restricts the choice of a new solution in a single iteration. This determines the local efficiency of a local search heuristic. On the other side, this local behavior also influences the global behavior, i.e. the sequence of feasible solutions obtained by the local search heuristic. This sequence of solutions represents the navigational behavior of the local search heuristic and determines the global efficiency of a local search heuristic.

A key element is the size of a neighborhood. The size determines how many choices there are to find a better solution. This also designates the time the heuristic needs in every iteration. Since with smaller neighborhoods we may not have (directly or indirectly) considered many solutions at the end of a local search heuristic, the size may also have an influence on the solution quality from a global point of view.

In the first part of the thesis, we consider neighborhoods of large size that can be explored in a fast manner, in order to reach local optima of good quality in less time. We consider the scheduling problems of minimizing the sum of job completion times on a single machine with the presence of release dates, and of minimizing the sum of weighted job completion times on parallel and identical machines. By concentrating on the local efficiency, we develop very large-scale neighborhoods for these two scheduling problems. For all the introduced neighborhoods, we explain what solutions they contain and how the neighborhood is efficiently explored to obtain a better neighbor. We also compare their performance to basic neighborhoods regarding solution quality and running time by conducting computational tests.

For the single machine problem, we first introduce a neighborhood that bases on combining independent operators. These operators form a smaller neighborhood, and by combining several operators we obtain a very large-scale neighborhood. A best neighbor in this very large-scale neighborhood can be obtained by determining a shortest path in an improvement graph. In the computational test, this neighborhood does not perform well. We present a second very large-scale neighborhood that bases on a dominance rule for the considered problem.Here, a best neighbor can be obtained by sorting. In the computational test,this neighborhood is fast but regarding solution quality, it is only successful in combination with another neighborhood.

For the parallel machine problem, we also present a very large-scale neighborhood that bases on combining independent operators of a smaller neighborhood. But here, the best neighbor is obtained by determining a maximum weight matching in an improvement graph. In the computational test, this neighborhood is slightly faster than the underlying smaller neighborhood. A second very large-scale neighborhood is introduced that bases on a restricted version of the considered problem, which can be solved in polynomial time. The best neighbor of this neighborhood is obtained by determining a minimum weight perfect matching. In the computational test, this neighborhood performs comparable to the smaller neighborhood used for obtaining the first very-large scale neighborhood.

In the second part of the thesis, we examine the global efficiency in terms of solution quality obtained at the end of a local search heuristic. We consider the problems of scheduling jobs on parallel identical machines in order to minimize the sum of weighted job completion times and of minimizing the makespan (completion time of last planned job). For these problems, we consider certain neighborhoods and analyze the quality of their local optima. Although the found performance guarantees are worse compared to constructive heuristics (however, for our cases the differences are quite small), the advantage of giving performance guarantees for local optima is that these guarantees hold for all solutions which are locally optimal and not only for a single solution as for most constructive heuristics. It is interesting to see that already simple structured solutions like the local optima allow a reasonable performance guarantee. Since local search heuristics like simulated annealing or tabu search tend to visit a lot of local optima during the search process, we may expect that the best found solution has a much better quality than that given by the performance guarantee.

Roughly speaking, a local search heuristic starts with an initial solution, e.g.obtained with the help of a constructive heuristic. The local search heuristic then iteratively explores a neighborhood of the current solution and chooses a new solution out of this neighborhood to become the next current solution. Often, only new solutions are considered, which improve on the current one. The local search heuristic halts if some stopping criterion is met, e.g. there exists no better solution in the neighborhood.

The neighborhood is a critical issue in a local search heuristic. It directly influences the local behavior of a local search heuristic, since it restricts the choice of a new solution in a single iteration. This determines the local efficiency of a local search heuristic. On the other side, this local behavior also influences the global behavior, i.e. the sequence of feasible solutions obtained by the local search heuristic. This sequence of solutions represents the navigational behavior of the local search heuristic and determines the global efficiency of a local search heuristic.

A key element is the size of a neighborhood. The size determines how many choices there are to find a better solution. This also designates the time the heuristic needs in every iteration. Since with smaller neighborhoods we may not have (directly or indirectly) considered many solutions at the end of a local search heuristic, the size may also have an influence on the solution quality from a global point of view.

In the first part of the thesis, we consider neighborhoods of large size that can be explored in a fast manner, in order to reach local optima of good quality in less time. We consider the scheduling problems of minimizing the sum of job completion times on a single machine with the presence of release dates, and of minimizing the sum of weighted job completion times on parallel and identical machines. By concentrating on the local efficiency, we develop very large-scale neighborhoods for these two scheduling problems. For all the introduced neighborhoods, we explain what solutions they contain and how the neighborhood is efficiently explored to obtain a better neighbor. We also compare their performance to basic neighborhoods regarding solution quality and running time by conducting computational tests.

For the single machine problem, we first introduce a neighborhood that bases on combining independent operators. These operators form a smaller neighborhood, and by combining several operators we obtain a very large-scale neighborhood. A best neighbor in this very large-scale neighborhood can be obtained by determining a shortest path in an improvement graph. In the computational test, this neighborhood does not perform well. We present a second very large-scale neighborhood that bases on a dominance rule for the considered problem.Here, a best neighbor can be obtained by sorting. In the computational test,this neighborhood is fast but regarding solution quality, it is only successful in combination with another neighborhood.

For the parallel machine problem, we also present a very large-scale neighborhood that bases on combining independent operators of a smaller neighborhood. But here, the best neighbor is obtained by determining a maximum weight matching in an improvement graph. In the computational test, this neighborhood is slightly faster than the underlying smaller neighborhood. A second very large-scale neighborhood is introduced that bases on a restricted version of the considered problem, which can be solved in polynomial time. The best neighbor of this neighborhood is obtained by determining a minimum weight perfect matching. In the computational test, this neighborhood performs comparable to the smaller neighborhood used for obtaining the first very-large scale neighborhood.

In the second part of the thesis, we examine the global efficiency in terms of solution quality obtained at the end of a local search heuristic. We consider the problems of scheduling jobs on parallel identical machines in order to minimize the sum of weighted job completion times and of minimizing the makespan (completion time of last planned job). For these problems, we consider certain neighborhoods and analyze the quality of their local optima. Although the found performance guarantees are worse compared to constructive heuristics (however, for our cases the differences are quite small), the advantage of giving performance guarantees for local optima is that these guarantees hold for all solutions which are locally optimal and not only for a single solution as for most constructive heuristics. It is interesting to see that already simple structured solutions like the local optima allow a reasonable performance guarantee. Since local search heuristics like simulated annealing or tabu search tend to visit a lot of local optima during the search process, we may expect that the best found solution has a much better quality than that given by the performance guarantee.

0/5000

จาก: -

เป็น: -

ผลลัพธ์ (ไทย) 1: [สำเนา]

คัดลอก!

ลองผิดลองถูกค้นหาในท้องถิ่นเป็นคลาสที่มีความสำคัญของอัลกอริทึมสำหรับการได้รับ goodsolutions ปัญหาปัญหาปรับยาก ประเด็นสำคัญ forthese ลองผิดลองถูกเป็นโซลูชั่นคุณภาพและเวลาที่ต้องการได้รับการแก้ปัญหาที่ดีพูดหยาบ ๆ heuristic ค้นหาท้องถิ่นเริ่ม มีในโซลูชันเริ่มต้น e.g.obtained ด้วยความช่วยเหลือของ heuristic ที่สร้างสรรค์ Heuristic ค้นหาท้องถิ่นซ้ำ ๆ สำรวจพื้นที่ใกล้เคียงของโซลูชันปัจจุบัน แล้วเลือกปัญหาจากบริเวณนี้จะเป็น การแก้ปัญหาปัจจุบันถัดไป มักจะ โซลูชั่นที่ใหม่เท่านั้นจะพิจารณา ซึ่งในปัจจุบัน Heuristic ค้นหาท้องถิ่นหยุดถ้าเป็นไปตามเกณฑ์บางหยุด เช่น มีวิธีใดดีกว่าในย่านย่านที่เป็นปัญหาสำคัญใน heuristic ค้นหาท้องถิ่น มันโดยตรงมีผลต่อพฤติกรรมของ heuristic ค้นหาท้องถิ่น ท้องถิ่นเนื่องจากมันจำกัดการเลือกปัญหาในการเกิดซ้ำที่เดียวกัน นี้กำหนดประสิทธิภาพของ heuristic ค้นหาท้องถิ่นท้องถิ่น อีกด้านหนึ่ง ลักษณะเฉพาะนี้มีผลต่อพฤติกรรมสากล เช่นลำดับของการแก้ไขปัญหาเป็นไปได้ที่รับ โดย heuristic ค้นหาท้องถิ่นยัง ลำดับนี้โซลูชั่นแสดงถึงพฤติกรรมของ heuristic ค้นหาท้องถิ่นนำทาง และกำหนดประสิทธิภาพของ heuristic ค้นหาท้องถิ่นทั่วโลกองค์ประกอบสำคัญคือ ขนาดของละแวกนั้น ขนาดกำหนดจำนวนตัวเลือกมีการหาทางออกดีกว่า นี้ยังกำหนดเวลาที่ heuristic จำเป็นในการเกิดซ้ำทุก เนื่องจาก มีละแวกใกล้เคียงที่มีขนาดเล็ก เราอาจไม่ได้ (โดยตรง หรือโดยอ้อม) พิจารณาโซลูชั่นในท้ายของ heuristic ค้นหาท้องถิ่น ขนาดอาจยังมีผลต่อคุณภาพการแก้ปัญหาจากจุดมุมมองที่ส่วนกลางในส่วนแรกของวิทยานิพนธ์ เราพิจารณาละแวกใกล้เคียงขนาดใหญ่ที่สามารถสำรวจได้อย่างรวดเร็ว เพื่อที่จะถึงพติท้องถิ่นคุณภาพดีเวลาน้อย เราพิจารณาปัญหาการจัดกำหนดการของการลดผลรวมของเวลาเสร็จงานในเครื่องเดียวมีวันที่วางจำหน่าย และลดผลรวมของเวลาเสร็จงานถ่วงน้ำหนักบนเครื่องเหมือนกัน และขนานกัน โดย concentrating บนประสิทธิภาพท้องถิ่น เราพัฒนาละแวกใกล้เคียงขนาดใหญ่มากสำหรับปัญหาการจัดกำหนดการสองเหล่านี้ สำหรับทั้งหมดที่นำท่องราตรี เราอธิบายวิธีใดประกอบด้วยและวิธีพื้นที่ใกล้เคียงได้อย่างมีประสิทธิภาพอุดมรับเพื่อนบ้านดี นอกจากนี้เรายังเปรียบเทียบการปฏิบัติการพื้นฐานละแวกใกล้เคียงเกี่ยวกับโซลูชั่นคุณภาพ และใช้เวลา โดยทำการทดสอบการคำนวณสำหรับปัญหาเครื่องเดียว เราก่อนแนะนำย่านที่ฐานบนรวมผู้ประกอบการอิสระ ตัวดำเนินการเหล่านี้เป็นย่านที่มีขนาดเล็ก และ โดยรวมหลาย ๆ ตัว เรารับย่านขนาดใหญ่มาก เพื่อนบ้านที่ดีที่สุดในย่านนี้ขนาดใหญ่มากสามารถได้รับ โดยกำหนดเส้นทางสั้นที่สุดในกราฟการปรับปรุง ในการคำนวณทดสอบ ย่านนี้ทำดี เรานำเสนอพื้นที่ใกล้เคียงขนาดใหญ่มากสองที่ฐานบนกฎปกครองพิจารณาปัญหา ที่นี่ เพื่อนบ้านที่ดีที่สุดสามารถได้รับ โดยเรียงลำดับ ในการคำนวณทดสอบ ย่านนี้เป็นอย่างรวดเร็ว แต่เกี่ยวกับโซลูชั่นคุณภาพ เป็นเพียงความสำเร็จร่วมกับพื้นที่ใกล้เคียงอีกสำหรับปัญหาเครื่องขนาน เรายังมีย่านขนาดใหญ่มากที่ฐานบนรวมผู้ประกอบการอิสระของพื้นที่ใกล้เคียงที่มีขนาดเล็ก แต่ที่นี่ เพื่อนบ้านที่ดีที่สุดจะได้รับ โดยกำหนดน้ำหนักสูงสุดที่ตรงกันในการพัฒนากราฟ บริเวณนี้จะไม่เล็กน้อยเร็วกว่าย่านขนาดเล็กต้นแบบในการคำนวณการทดสอบ พื้นที่ใกล้เคียงขนาดใหญ่มากสองแนะนำที่ฐานบนรุ่นจำกัดปัญหาพิจารณา ซึ่งสามารถแก้ไขได้ในเวลาพหุนาม เพื่อนบ้านที่ดีที่สุดของบริเวณนี้จะได้รับ โดยกำหนดน้ำหนักน้อยที่สุดสมบูรณ์แบบจับคู่ ในการคำนวณทดสอบ ย่านนี้ทำเทียบได้กับย่านขนาดเล็กที่ใช้สำหรับรับย่านมากขนาดใหญ่ครั้งแรกในส่วนสองของวิทยานิพนธ์ เราตรวจสอบประสิทธิภาพระดับโลกในด้านโซลูชั่นคุณภาพรับท้ายของ heuristic ค้นหาท้องถิ่น เราพิจารณาปัญหาของการวางแผนงานเกี่ยวกับเครื่องจักรเหมือนกันแบบขนานเพื่อลดผลรวม ของเวลาเสร็จงานถ่วงน้ำหนัก และย่อหน้า makespan (เวลาความสมบูรณ์ของแผนงานสุดท้าย) ปัญหาเหล่านี้ เราพิจารณาเฉพาะละแวกใกล้เคียง และวิเคราะห์คุณภาพของพติของท้องถิ่น ถึงแม้ว่าประสิทธิภาพการทำงานพบรับประกันแย่ลงเมื่อเทียบกับการลองผิดลองถูกสร้างสรรค์ (อย่างไรก็ตาม สำหรับกรณีของเรา แตกต่างค่อนข้างเล็ก), ประโยชน์ของการให้ประกันประสิทธิภาพสำหรับท้องถิ่นพติคือ ว่า ประกันเหล่านี้ถือ การแก้ไขปัญหาทั้งหมดที่ดีที่สุดในประเทศ และไม่ใช่ปัญหาเดียวกับการลองผิดลองถูกที่สุดสร้างสรรค์ เป็นที่น่าสนใจเพื่อดูว่า แล้วเรื่องโครงสร้างโซลูชั่นพติท้องถิ่นอนุญาตรับประกันประสิทธิภาพที่เหมาะสม ตั้งแต่ค้นหาท้องถิ่นที่ต้องลองผิดลองถูกจำลอง การอบเหนียวหรือทาบูค้นหามักจะ แวะมากพติภายในระหว่างการค้นหา เราอาจคาดหวังว่า โซลูชันพบส่วนมีมากคุณภาพที่ดีขึ้นกว่าที่กำหนดรับประกันประสิทธิภาพ

การแปล กรุณารอสักครู่..

ผลลัพธ์ (ไทย) 2:[สำเนา]

คัดลอก!

การวิเคราะห์พฤติกรรมการค้นหาในท้องถิ่นเป็นชั้นที่สำคัญของขั้นตอนวิธีสำหรับการได้รับ goodsolutions สำหรับปัญหาการเพิ่มประสิทธิภาพ combinatorial ยาก ประเด็นที่สำคัญการวิเคราะห์พฤติกรรม forthese วิธีการแก้ปัญหาที่มีคุณภาพและเวลาที่จำเป็นเพื่อให้ได้ทางออกที่ดี. ประมาณพูดแก้ปัญหาการค้นหาในท้องถิ่นเริ่มต้นด้วยการแก้ปัญหาเบื้องต้น egobtained ด้วยความช่วยเหลือของการแก้ปัญหาที่สร้างสรรค์ แก้ปัญหาการค้นหาในท้องถิ่นแล้วซ้ำสำรวจพื้นที่ใกล้เคียงของการแก้ปัญหาในปัจจุบันและเลือกวิธีการแก้ปัญหาใหม่ออกจากละแวกนี้ที่จะกลายเป็นวิธีการแก้ปัญหาในปัจจุบันต่อไป บ่อยครั้งเพียงการแก้ปัญหาที่ได้รับการพิจารณาใหม่ซึ่งปรับปรุงในปัจจุบัน แก้ปัญหาการค้นหาในท้องถิ่นหยุดถ้าหยุดเกณฑ์บางอย่างจะได้พบเช่นมีอยู่ไม่มีวิธีแก้ที่ดีขึ้นในพื้นที่ใกล้เคียง. พื้นที่ใกล้เคียงเป็นปัญหาที่สำคัญในการแก้ปัญหาการค้นหาในท้องถิ่น มันมีผลโดยตรงพฤติกรรมของท้องถิ่นแก้ปัญหาการค้นหาในท้องถิ่นเนื่องจากมีการ จำกัด ทางเลือกของการแก้ปัญหาใหม่ ๆ ในการทำซ้ำเดียว นี้จะกำหนดประสิทธิภาพของการเรียนรู้ในท้องถิ่นการค้นหาในท้องถิ่น ในอีกด้านพฤติกรรมในท้องถิ่นนอกจากนี้ยังมีอิทธิพลต่อพฤติกรรมของโลกคือลำดับของการแก้ปัญหาที่เป็นไปได้ที่ได้จากการแก้ปัญหาการค้นหาในท้องถิ่น ลำดับของการแก้ปัญหานี้แสดงให้เห็นถึงพฤติกรรมการเดินเรือของการแก้ปัญหาการค้นหาในท้องถิ่นและกำหนดประสิทธิภาพระดับโลกของการแก้ปัญหาการค้นหาในท้องถิ่น. องค์ประกอบสำคัญคือขนาดของพื้นที่ใกล้เคียง ขนาดกำหนดวิธีการหลายทางเลือกที่มีที่จะหาทางออกที่ดีกว่า นอกจากนี้ยังกำหนดเวลาที่ความต้องการแก้ปัญหาในทุกซ้ำ ตั้งแต่ละแวกใกล้เคียงที่มีขนาดเล็กที่เราอาจไม่ได้ (ไม่ว่าโดยตรงหรือโดยอ้อม) พิจารณาหลายโซลูชั่นในตอนท้ายของการแก้ปัญหาการค้นหาในท้องถิ่นที่มีขนาดนอกจากนี้ยังอาจมีอิทธิพลต่อคุณภาพการแก้ปัญหาจากจุดทั่วโลกในมุมมองของ. ในส่วนแรกของวิทยานิพนธ์ เราจะพิจารณาในละแวกใกล้เคียงที่มีขนาดใหญ่ที่สามารถสำรวจในลักษณะที่รวดเร็วในการสั่งซื้อที่จะไปถึง Optima ท้องถิ่นที่มีคุณภาพดีในเวลาที่น้อยลง เราพิจารณาปัญหาการจัดตารางเวลาของการลดผลรวมของเวลาที่เสร็จสิ้นงานในเครื่องเดียวกับการปรากฏตัวของวันรุ่นและการลดผลรวมของเวลาที่เสร็จสิ้นงานถ่วงน้ำหนักในเครื่องขนานและเหมือนกัน โดยมุ่งเน้นประสิทธิภาพในท้องถิ่นเราพัฒนาละแวกใกล้เคียงที่มีขนาดใหญ่มากสำหรับทั้งสองปัญหาการตั้งเวลา สำหรับทุกละแวกใกล้เคียงที่แนะนำเราอธิบายสิ่งที่พวกเขามีการแก้ปัญหาและวิธีการที่พื้นที่ใกล้เคียงคือการสำรวจได้อย่างมีประสิทธิภาพเพื่อให้ได้เพื่อนบ้านที่ดีกว่า นอกจากนี้เรายังเปรียบเทียบผลการดำเนินงานของพวกเขาไปสู่ย่านพื้นฐานเกี่ยวกับวิธีการแก้ปัญหาที่มีคุณภาพและเวลาการทำงานโดยการดำเนินการทดสอบการคำนวณ. สำหรับปัญหาเครื่องเดียวเราแนะนำพื้นที่ใกล้เคียงที่อยู่บนฐานการรวมผู้ประกอบการอิสระ ผู้ประกอบการเหล่านี้ในรูปแบบพื้นที่ใกล้เคียงที่มีขนาดเล็กและผู้ประกอบการโดยการรวมหลาย ๆ ที่เราได้รับใกล้เคียงขนาดใหญ่มาก เพื่อนบ้านที่ดีที่สุดในละแวกนี้มากขนาดใหญ่ที่สามารถรับได้โดยการกำหนดเส้นทางที่สั้นที่สุดในกราฟการปรับปรุง ในการทดสอบการคำนวณย่านนี้ไม่ได้ทำงานได้ดี เรานำเสนอเป็นครั้งที่สองใกล้เคียงมากขนาดใหญ่ที่ฐานในการปกครองการปกครองสำหรับการพิจารณา problem.Here เพื่อนบ้านที่ดีที่สุดจะได้รับจากการเรียงลำดับ ในการทดสอบการคำนวณย่านนี้เป็นไปอย่างรวดเร็ว แต่การแก้ปัญหาเกี่ยวกับคุณภาพก็จะประสบความสำเร็จในการรวมกันเฉพาะกับพื้นที่ใกล้เคียงอีก. สำหรับปัญหาเครื่องขนานนี้เรายังนำเสนอพื้นที่ใกล้เคียงมากขนาดใหญ่ที่อยู่บนฐานการรวมผู้ประกอบการที่เป็นอิสระจากพื้นที่ใกล้เคียงที่มีขนาดเล็ก แต่ที่นี่เพื่อนบ้านที่ดีที่สุดจะได้รับโดยการกำหนดน้ำหนักสูงสุดของการจับคู่ในกราฟการปรับปรุง ในการทดสอบการคำนวณย่านนี้เล็กน้อยเร็วกว่าพื้นฐานพื้นที่ใกล้เคียงที่มีขนาดเล็ก พื้นที่ใกล้เคียงที่สองมากขนาดใหญ่ที่เป็นที่รู้จักบนฐานรุ่นที่ จำกัด ของการพิจารณาปัญหาที่สามารถแก้ไขได้ในเวลาพหุนาม เพื่อนบ้านที่ดีที่สุดของละแวกนี้จะได้รับโดยการกำหนดน้ำหนักขั้นต่ำการจับคู่ที่สมบูรณ์แบบ ในการทดสอบการคำนวณย่านนี้มีประสิทธิภาพเทียบเคียงได้กับย่านที่มีขนาดเล็กใช้สำหรับการได้รับย่านขนาดใหญ่มากครั้งแรก. ในส่วนที่สองของวิทยานิพนธ์เราตรวจสอบที่มีประสิทธิภาพระดับโลกในแง่ของคุณภาพที่ได้รับการแก้ปัญหาในตอนท้ายของการค้นหาในท้องถิ่น แก้ปัญหา เราพิจารณาปัญหาของงานการจัดตารางเวลาในเครื่องเหมือนกันขนานเพื่อลดผลรวมของเวลาที่เสร็จสิ้นงานถ่วงน้ำหนักและลด makespan (เวลาแล้วเสร็จของงานที่วางแผนไว้แล้ว) ปัญหาเหล่านี้เราจะพิจารณาละแวกใกล้เคียงบางอย่างและวิเคราะห์คุณภาพของ Optima ในท้องถิ่นของตน แม้ว่าค้ำประกันการปฏิบัติพบว่าจะเลวร้ายยิ่งเมื่อเทียบกับการวิเคราะห์พฤติกรรมที่สร้างสรรค์ (แต่สำหรับกรณีของเราแตกต่างที่มีขนาดเล็กมาก) ประโยชน์ของการให้การค้ำประกันการปฏิบัติงานสำหรับ Optima ท้องถิ่นคือการค้ำประกันเหล่านี้ถือสำหรับการแก้ปัญหาทั้งหมดที่มีในประเทศที่ดีที่สุดและไม่เพียง แต่สำหรับ การแก้ปัญหาเดียวกับการวิเคราะห์พฤติกรรมที่สร้างสรรค์มากที่สุด เป็นที่น่าสนใจที่จะเห็นว่าการแก้ปัญหาที่มีโครงสร้างที่เรียบง่ายอยู่แล้วเช่น Optima ท้องถิ่นอนุญาตให้มีการรับประกันผลการดำเนินงานที่เหมาะสม ตั้งแต่การวิเคราะห์พฤติกรรมการค้นหาในท้องถิ่นเช่นอบจำลองหรือค้นหาห้ามมีแนวโน้มที่จะเยี่ยมชมจำนวนมาก Optima ท้องถิ่นในระหว่างขั้นตอนการค้นหาเราอาจคาดหวังว่าวิธีการแก้ปัญหาที่ดีที่สุดพบว่ามีคุณภาพที่ดีขึ้นกว่าที่ได้รับจากการรับประกันผลการดำเนินงาน

การแปล กรุณารอสักครู่..

ผลลัพธ์ (ไทย) 3:[สำเนา]

คัดลอก!

การวิเคราะห์พฤติกรรมการค้นหาในท้องถิ่นเป็นสำคัญ คลาสของขั้นตอนวิธีการเพิ่มประสิทธิภาพการ goodsolutions ปัญหายาก ที่สำคัญปัญหา forthese ฮิวริสติกมีคุณภาพโซลูชั่น และเวลาที่จำเป็นเพื่อให้ได้ทางออกที่ดี

ประมาณพูด , การค้นหาในท้องถิ่นนี้ เริ่มด้วยโซลูชั่นเริ่มต้น e.g.obtained ด้วยความช่วยเหลือของการสร้างสรรค์แบบศึกษาสำนึกท้องถิ่นค้นหาฮิวริสติกแล้วซ้ำสำรวจละแวกของโซลูชั่นปัจจุบันและเลือกโซลูชั่นใหม่ของย่านนี้เป็นโซลูชั่นที่หน้าปัจจุบัน มักจะถือว่าเป็นโซลูชั่นใหม่เท่านั้น ซึ่งปรับปรุงปัจจุบัน การค้นหาในท้องถิ่นสำหรับหยุด ถ้าหยุดเกณฑ์จะพบ เช่นมีอยู่ไม่มีทางเลือกที่ดีกว่า

อยู่แถวบ้านเพื่อนบ้านเป็นปัญหาสำคัญในการค้นหาในท้องถิ่นแบบศึกษาสำนึก โดยตรงมีผลต่อพฤติกรรมภายในของการค้นหาในท้องถิ่นสำหรับ เนื่องจากเป็นการจำกัดทางเลือกของโซลูชั่นใหม่ในรูปเดียว นี้จะกำหนดประสิทธิภาพของการค้นหาในท้องถิ่นท้องถิ่นแบบศึกษาสำนึก ในด้านอื่น ๆ พฤติกรรมนี้ท้องถิ่นนอกจากนี้ยังมีผลต่อพฤติกรรมระดับโลก ได้แก่ลำดับของโซลูชั่นที่เป็นไปได้ที่ได้รับโดยการค้นหาท้องถิ่นแบบศึกษาสำนึก ลำดับ โซลูชั่น แสดงถึงพฤติกรรมของการค้นหาในท้องถิ่นสำหรับการเดินเรือ และตรวจสอบประสิทธิภาพของการค้นหาในท้องถิ่นสำหรับฮิวริสติก

องค์ประกอบหลักคือขนาดของชุมชน ขนาดกําหนดจํานวนตัวเลือกมีเพื่อหาทางแก้ปัญหาดีกว่านอกจากนี้ยังกำหนดเวลาสำหรับทุกความต้องการในการ . เพราะด้วยย่านเล็กเราอาจไม่ได้ ( โดยตรงหรือโดยอ้อม ) การพิจารณาโซลูชั่นมากมายในตอนท้ายของการค้นหาในท้องถิ่นแบ่งขนาดอาจยังมีอิทธิพลในการแก้ปัญหาคุณภาพจากจุดทั่วโลกในมุมมองของ

ในส่วนแรกของวิทยานิพนธ์เราพิจารณาย่านขนาดใหญ่ที่สามารถสำรวจในลักษณะที่รวดเร็ว เพื่อเข้าถึง Optima ท้องถิ่นที่ดีมีคุณภาพในเวลาที่น้อยลง เราพิจารณาปัญหาของการลดผลรวมของเวลาเสร็จงานบนเครื่องจักรเดี่ยวกับการปรากฏตัวของวันที่ปล่อยและลดผลรวมของน้ำหนักงานเสร็จครั้งบนเครื่องขนานกันและเหมือนกันโดยมุ่งเน้นประสิทธิภาพในประเทศเราพัฒนาย่านมากขนาดใหญ่สำหรับสองสำหรับปัญหา สำหรับทุกแนะนำย่าน เราอธิบายสิ่งที่โซลูชั่นที่พวกเขามีและวิธีการสำรวจเพื่อให้ได้มีประสิทธิภาพในละแวกเพื่อนบ้านดีกว่าเรายังเปรียบเทียบประสิทธิภาพของโซลูชั่นย่านเบื้องต้นเกี่ยวกับคุณภาพและเวลาทํางาน โดยทำการทดสอบการคำนวณ

สำหรับปัญหาเครื่องเดียว เราแรกแนะนำชุมชนที่อยู่บนพื้นฐานของการรวมผู้ประกอบการอิสระ ผู้ประกอบการเหล่านี้รูปแบบชุมชนขนาดเล็กและโดยการรวมหลายผู้ประกอบการได้ใกล้เคียงมาก ขนาดใหญ่ที่ดีที่สุดในละแวกเพื่อนบ้านมากขนาดใหญ่นี้สามารถหาได้โดยการหาเส้นทางที่สั้นที่สุดในการปรับปรุงกราฟ ในการทดสอบการคำนวณ ละแวกนี้ไม่ทำหน้าที่ให้ดี เรานำเสนอสองมากขนาดใหญ่ที่ใกล้เคียงฐานในการปกครองปกครองเพื่อพิจารณาปัญหา ที่นี่ บ้านที่ดีที่สุดที่สามารถรับได้ โดยการเรียงลำดับ ในการทดสอบการคํานวณย่านนี้เป็นเร็ว แต่เรื่องคุณภาพ โซลูชั่น จะประสบความสำเร็จได้ร่วมกับเพื่อนบ้านอีก

สำหรับปัญหาเครื่องขนาน นอกจากนี้เรายังนำเสนอละแวกมากขนาดใหญ่ที่ฐานการอิสระผู้ประกอบการชุมชนขนาดเล็ก แต่ที่นี่ เพื่อนบ้านที่ดีที่สุด จะได้รับ โดยกำหนดน้ำหนักสูงสุดที่ตรงกันในการปรับปรุงกราฟในการทดสอบการคำนวณ ละแวกนี้เล็กน้อยเร็วกว่าต้นแบบเล็กแถวบ้าน ที่สองมาก เพื่อนบ้านแนะนำว่า ฐานขนาดใหญ่ในรุ่น จำกัด ถือเป็นปัญหาที่สามารถแก้ไขได้ในเวลาพหุนาม . เพื่อนบ้านที่แสนดีของละแวกนี้ได้กำหนดน้ำหนักน้อยที่สมบูรณ์แบบที่ตรงกัน ในการทดสอบการคํานวณละแวกนี้มีประสิทธิภาพเทียบเท่ากับชุมชนขนาดเล็กที่ใช้สำหรับการได้รับครั้งแรกที่ใหญ่มาก ขนาดเพื่อนบ้าน

ในส่วนที่สองของวิทยานิพนธ์ เราตรวจสอบประสิทธิภาพระดับโลกในแง่คุณภาพของโซลูชั่นที่ได้รับในตอนท้ายของการค้นหาในท้องถิ่นแบบศึกษาสำนึกเราพิจารณาปัญหาของการจัดตารางงานบนเครื่องเหมือนกันขนานเพื่อลดผลรวมของเวลาเสร็จงานหนักและลดการเกี่ยวข้อง ( เวลาสุดท้ายของการวางแผนงาน ) ปัญหาเหล่านี้เราพิจารณาย่านบาง และวิเคราะห์คุณภาพของ Optima ในท้องถิ่นของตนแม้ว่าพบประสิทธิภาพรับประกันแย่เมื่อเทียบกับอักษรสร้างสรรค์ ( แต่กรณีของเรามีความแตกต่างค่อนข้างเล็ก ) , ประโยชน์ของการให้รับประกันประสิทธิภาพสำหรับ Optima ท้องถิ่นที่รับประกันเหล่านี้ถือสำหรับโซลูชั่นทั้งหมด ซึ่งในประเทศที่ดีที่สุดและไม่เพียงทางออกเดียวสำหรับการวิเคราะห์พฤติกรรมที่สร้างสรรค์มากที่สุด .เป็นที่น่าสนใจเพื่อดูว่าโครงสร้างง่ายแล้วโซลูชั่นชอบ Optima ท้องถิ่นให้รับประกันประสิทธิภาพที่เหมาะสม ตั้งแต่ท้องถิ่นค้นหาฮิวริสติกเหมือนการดำรงอยู่หรือการค้นทาบูมีแนวโน้มที่จะเยี่ยมชมมาก Optima ท้องถิ่นในระหว่างกระบวนการค้นหา เราอาจจะพบทางออกที่ดีที่สุด มีคุณภาพที่ดีกว่าที่กำหนดโดยรับประกันประสิทธิภาพ

การแปล กรุณารอสักครู่..

ภาษาอื่น ๆ

การสนับสนุนเครื่องมือแปลภาษา: กรีก, กันนาดา, กาลิเชียน, คลิงออน, คอร์สิกา, คาซัค, คาตาลัน, คินยารวันดา, คีร์กิซ, คุชราต, จอร์เจีย, จีน, จีนดั้งเดิม, ชวา, ชิเชวา, ซามัว, ซีบัวโน, ซุนดา, ซูลู, ญี่ปุ่น, ดัตช์, ตรวจหาภาษา, ตุรกี, ทมิฬ, ทาจิก, ทาทาร์, นอร์เวย์, บอสเนีย, บัลแกเรีย, บาสก์, ปัญจาป, ฝรั่งเศส, พาชตู, ฟริเชียน, ฟินแลนด์, ฟิลิปปินส์, ภาษาอินโดนีเซี, มองโกเลีย, มัลทีส, มาซีโดเนีย, มาราฐี, มาลากาซี, มาลายาลัม, มาเลย์, ม้ง, ยิดดิช, ยูเครน, รัสเซีย, ละติน, ลักเซมเบิร์ก, ลัตเวีย, ลาว, ลิทัวเนีย, สวาฮิลี, สวีเดน, สิงหล, สินธี, สเปน, สโลวัก, สโลวีเนีย, อังกฤษ, อัมฮาริก, อาร์เซอร์ไบจัน, อาร์เมเนีย, อาหรับ, อิกโบ, อิตาลี, อุยกูร์, อุสเบกิสถาน, อูรดู, ฮังการี, ฮัวซา, ฮาวาย, ฮินดี, ฮีบรู, เกลิกสกอต, เกาหลี, เขมร, เคิร์ด, เช็ก, เซอร์เบียน, เซโซโท, เดนมาร์ก, เตลูกู, เติร์กเมน, เนปาล, เบงกอล, เบลารุส, เปอร์เซีย, เมารี, เมียนมา (พม่า), เยอรมัน, เวลส์, เวียดนาม, เอสเปอแรนโต, เอสโทเนีย, เฮติครีโอล, แอฟริกา, แอลเบเนีย, โคซา, โครเอเชีย, โชนา, โซมาลี, โปรตุเกส, โปแลนด์, โยรูบา, โรมาเนีย, โอเดีย (โอริยา), ไทย, ไอซ์แลนด์, ไอร์แลนด์, การแปลภาษา.