การค้นหาแบบโลคอลที่มีคำแนะนำ (Guided local search)เป็น วิธีการค้นหาแบบ เมตาฮิวริสติก (Metaheuristic search method) เมตาฮิวริสติกคือวิธีการที่ทำงานอยู่บนอัลกอริทึมการค้นหาแบบโลคอลเพื่อเปลี่ยนแปลงพฤติกรรมของมัน

การค้นหาแบบโลคอลที่มีคำแนะนำ (Guided Local Search: GLS) จะสร้างค่าปรับขึ้นระหว่างการค้นหา โดยใช้ค่าปรับเหล่านี้เพื่อช่วยให้อัลกอริทึมการค้นหาแบบโลคอลหลุดพ้นจากจุดต่ำสุดและจุดคงที่ เมื่ออัลกอริทึมการค้นหาแบบโลคอลที่กำหนดไว้ติดอยู่ในจุดเหมาะสมที่สุดเฉพาะที่ GLS จะปรับเปลี่ยนฟังก์ชันเป้าหมายโดยใช้แผนการเฉพาะ (อธิบายด้านล่าง) จากนั้นการค้นหาแบบโลคอลจะทำงานโดยใช้ฟังก์ชันเป้าหมายที่ปรับปรุงแล้ว ซึ่งออกแบบมาเพื่อนำการค้นหาออกจากจุดเหมาะสมที่สุดเฉพาะที่ กุญแจสำคัญอยู่ที่วิธีการปรับเปลี่ยนฟังก์ชันเป้าหมาย

วิธีการในรูปแบบปัจจุบันได้รับการพัฒนาโดย ดร. คริสตอส วูดูริส และมีรายละเอียดอยู่ในวิทยานิพนธ์ปริญญาเอกของเขา^{[ 1 ]} GLS ได้รับแรงบันดาลใจและขยายมาจาก GENET ซึ่งเป็นสถาปัตยกรรมเครือข่ายประสาทเทียมสำหรับการแก้ปัญหา Constraint Satisfaction Problems ซึ่งพัฒนาโดย Chang Wang, Edward Tsang และ Andrew Davenport กลไกของทั้ง GLS และ GENET ในการหลุดพ้นจากจุดต่ำสุดเฉพาะที่นั้นคล้ายคลึงกับการเรียนรู้แบบเสริมแรง

ในการประยุกต์ใช้ GLS จำเป็นต้องกำหนดคุณลักษณะของคำตอบสำหรับปัญหาที่กำหนด คุณลักษณะของคำตอบถูกกำหนดขึ้นเพื่อแยกแยะคำตอบที่มีลักษณะแตกต่างกัน เพื่อให้สามารถระบุและหลีกเลี่ยงบริเวณที่มีความคล้ายคลึงกันรอบ ๆ จุดเหมาะสมที่สุดเฉพาะที่ได้ การเลือกคุณลักษณะของคำตอบขึ้นอยู่กับประเภทของปัญหา และในระดับหนึ่งก็ขึ้นอยู่กับอัลกอริธึมการค้นหาเฉพาะที่ด้วย สำหรับแต่ละคุณลักษณะจะมีการกำหนด ฟังก์ชันต้นทุน${\displaystyle f_{i}}$${\displaystyle c_{i}}$

แต่ละคุณลักษณะจะถูกกำหนดค่าปรับ(เริ่มต้นที่ 0) เพื่อบันทึกจำนวนครั้งที่คุณลักษณะนั้นปรากฏในจุดต่ำสุดเฉพาะที่ ${\displaystyle p_{i}}$

คุณลักษณะและต้นทุนมักมาจากฟังก์ชันเป้าหมายโดยตรง ตัวอย่างเช่น ในปัญหาพนักงานขายเดินทาง “การเดินทางจะตรงจากเมือง X ไปยังเมือง Y หรือไม่” สามารถกำหนดให้เป็นคุณลักษณะได้ และระยะทางระหว่าง X กับ Y สามารถกำหนดให้เป็นต้นทุนได้ ในปัญหา SAT และ weighted MAX-SAT คุณลักษณะอาจเป็น “เงื่อนไข C เป็นไปตามที่กำหนดโดยการจัดสรรปัจจุบันหรือไม่”

ในระดับการนำไปใช้งาน เรากำหนดฟังก์ชันตัวบ่งชี้ สำหรับแต่ละคุณลักษณะ โดยฟังก์ชัน นี้จะระบุว่าคุณลักษณะนั้นมีอยู่ในโซลูชันปัจจุบันหรือไม่ โดยจะมีค่าเป็น 1 เมื่อโซลูชันมีคุณสมบัติดังกล่าวและมีค่าเป็น 0 ในกรณีอื่น ๆ ${\displaystyle i}$${\displaystyle I_{i}}$${\displaystyle I_{i}}$${\displaystyle x}$${\displaystyle i}$

GLS คำนวณค่าประโยชน์ของการลงโทษแต่ละคุณลักษณะ เมื่ออัลกอริธึมการค้นหาแบบโลคอลส่งคืนค่าต่ำสุดเฉพาะที่ x แล้ว GLS จะลงโทษคุณลักษณะทั้งหมด (โดยการเพิ่มค่าลงโทษให้กับคุณลักษณะเหล่านั้น) ที่มีอยู่ในโซลูชันนั้น ซึ่งมีค่าประโยชน์สูงสุดตามที่กำหนดไว้ด้านล่าง ${\displaystyle \operatorname {util} (x,i)}$

${\displaystyle \operatorname {util} (x,i)=I_{i}(x){\frac {c_{i}(x)}{1+p_{i}}}.}$

แนวคิดคือการลงโทษคุณสมบัติที่มีต้นทุนสูง แม้ว่าประโยชน์ของการทำเช่นนั้นจะลดลงเรื่อยๆ เมื่อมีการลงโทษคุณสมบัตินั้นบ่อยขึ้นก็ตาม

GLS ใช้ฟังก์ชันต้นทุนเสริม (ที่กำหนดไว้ด้านล่าง) เพื่อช่วยนำทางอัลกอริธึมการค้นหาเฉพาะที่ออกจากจุดต่ำสุดเฉพาะที่ โดยการลงโทษคุณลักษณะที่มีอยู่ในจุดต่ำสุดเฉพาะที่นั้น แนวคิดคือการทำให้จุดต่ำสุดเฉพาะที่นั้นมีต้นทุนสูงกว่าพื้นที่การค้นหาโดยรอบ ซึ่งไม่มีคุณลักษณะเหล่านั้นอยู่

${\displaystyle g(x)=f(x)+\lambda a\sum _{1\leq i\leq m}I_{i}(x)p_{i}}$

พารามิเตอร์ λ สามารถใช้เพื่อปรับเปลี่ยนความเข้มข้นของการค้นหาคำตอบได้ ค่า λ ที่สูงขึ้นจะส่งผลให้การค้นหามีความหลากหลายมากขึ้น โดยจะค้นหาบริเวณที่ราบสูงและแอ่งน้ำอย่างหยาบๆ ในขณะที่ค่า λ ที่ต่ำจะส่งผลให้การค้นหาคำตอบมีความเข้มข้นมากขึ้น โดยจะค้นหาบริเวณที่ราบสูงและแอ่งน้ำในภูมิทัศน์การค้นหาอย่างละเอียดมากขึ้น สัมประสิทธิ์นี้ใช้เพื่อให้ส่วนค่าปรับของฟังก์ชันเป้าหมายมีความสมดุลกับการเปลี่ยนแปลงในฟังก์ชันเป้าหมาย และขึ้นอยู่กับปัญหาเฉพาะ วิธีง่ายๆ ในการตั้งค่าคือ บันทึกค่าเฉลี่ยของการเปลี่ยนแปลงในฟังก์ชันเป้าหมายจนถึงค่าต่ำสุดเฉพาะที่แรก จากนั้นตั้งค่าเป็นค่านี้หารด้วยจำนวนคุณลักษณะ GLS ในตัวอย่างปัญหา ${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$

มิลส์ (2002) ได้อธิบายถึงการค้นหาแบบโลคอลที่มีคำแนะนำแบบขยาย (EGLS) ซึ่งใช้การเคลื่อนที่แบบสุ่มและเกณฑ์ความปรารถนาที่ออกแบบมาโดยเฉพาะสำหรับแผนการแบบใช้ค่าปรับ อัลกอริทึมที่ได้นี้ช่วยปรับปรุงความทนทานของ GLS ในช่วงการตั้งค่าพารามิเตอร์ต่างๆ โดยเฉพาะอย่างยิ่งในกรณีของปัญหาการจัดสรรแบบกำลังสองเวอร์ชันทั่วไปของอัลกอริทึม GLS ซึ่งใช้ตัวปีนเขาแบบใช้ความขัดแย้งน้อยที่สุด (มินตันและคณะ 1992) และอิงตาม GENET บางส่วนสำหรับการแก้ปัญหาข้อจำกัดและการเพิ่มประสิทธิภาพ ก็ได้รับการนำไปใช้ในโครงการเขียนโปรแกรมข้อจำกัดโดยใช้คอมพิวเตอร์ช่วยด้วยเช่นกัน

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

GLS สร้างขึ้นบนพื้นฐานของ GENET ซึ่งได้รับการพัฒนาโดย Chang Wang, Edward Tsang และ Andrew Davenport

วิธีการ Breakoutคล้ายคลึงกับ GENET มาก โดยได้รับการออกแบบมาเพื่อแก้ปัญหาข้อจำกัดต่างๆ

การค้นหาแบบ Tabu searchเป็นกลุ่มของวิธีการค้นหาที่สามารถนำไปใช้กับวิธีการเฉพาะได้ GLS สามารถมองได้ว่าเป็นกรณีพิเศษของการค้นหาแบบ Tabu search

โดยการนำ GLS มาวางซ้อนบนอัลกอริทึมทางพันธุกรรม Tung-leng Lau ได้คิดค้นอัลกอริทึมการเขียนโปรแกรมทางพันธุกรรมแบบมีคำแนะนำ (GGA) ซึ่งประสบความสำเร็จในการนำไปประยุกต์ใช้กับปัญหาการจัดสรรทั่วไป (ในการจัดตารางเวลา) ปัญหาการกำหนดค่าโปรเซสเซอร์ (ในการออกแบบอิเล็กทรอนิกส์) และชุดปัญหาการจัดสรรความถี่ลิงก์วิทยุ (การประยุกต์ใช้ในด้านการทหารในรูปแบบนามธรรม)

Choi และคณะได้นำเสนอ GENET ในฐานะการค้นหาแบบลากรางจ์

• Alsheddy, A., การจัดตารางเวลาเพื่อเสริมศักยภาพ: แนวทางการเพิ่มประสิทธิภาพหลายวัตถุประสงค์โดยใช้การค้นหาแบบโลคอลที่มีคำแนะนำ, วิทยานิพนธ์ปริญญาเอก, คณะวิทยาการคอมพิวเตอร์และวิศวกรรมอิเล็กทรอนิกส์, มหาวิทยาลัยเอสเซ็กซ์, 2011
• Choi, KMF, Lee, JHM และ Stuckey, PJ, การสร้างใหม่แบบลากรางจ์ของ GENET, ปัญญาประดิษฐ์, 2000, 123(1-2), 1-39
• Davenport A., Tsang EPK, Kangmin Zhu และ CJ Wang, GENET: สถาปัตยกรรมแบบเชื่อมโยงสำหรับการแก้ปัญหาความพึงพอใจข้อจำกัดโดยการปรับปรุงแบบวนซ้ำ, Proc., AAAI, 1994, หน้า 325-330
• Lau, TL และ Tsang, EPK, การแก้ปัญหาการกำหนดค่าโปรเซสเซอร์ด้วยอัลกอริทึมทางพันธุกรรมแบบใช้การกลายพันธุ์, วารสารนานาชาติว่าด้วยเครื่องมือปัญญาประดิษฐ์ (IJAIT), World Scientific, เล่มที่ 6, ฉบับที่ 4, ธันวาคม 1997, หน้า 567-585
• Lau, TL และ Tsang, EPK, อัลกอริทึมพันธุกรรมแบบมีคำแนะนำและการประยุกต์ใช้กับปัญหาการจัดสรรความถี่ลิงก์วิทยุ, Constraints, Vol.6, No.4, 2001, 373-398
• Lau, TL และ Tsang, EPK, อัลกอริทึมพันธุกรรมแบบมีคำแนะนำและการประยุกต์ใช้กับปัญหาการจัดสรรทั่วไป, การประชุมวิชาการนานาชาติ IEEE ครั้งที่ 10 ว่าด้วยเครื่องมือปัญญาประดิษฐ์ (ICTAI'98), ไต้หวัน, พฤศจิกายน 1998
• Mills, P. & Tsang, EPK, การค้นหาแบบโลคอลที่มีคำแนะนำสำหรับการแก้ปัญหา SAT และ MAX-SAT แบบถ่วงน้ำหนัก, วารสาร Automated Reasoning, ฉบับพิเศษว่าด้วยปัญหาความพึงพอใจ, Kluwer, เล่มที่ 24, 2000, หน้า 205-223
• Mills, P. & Tsang, EPK & Ford, J., การประยุกต์ใช้การค้นหาแบบท้องถิ่นที่มีคำแนะนำแบบขยายในการแก้ปัญหาการจัดสรรแบบกำลังสอง, วารสารการวิจัยปฏิบัติการ, สำนักพิมพ์ Kluwer Academic Publishers, เล่มที่ 118, 2003, หน้า 121-135
• Minton, S., Johnston, M., Philips, AB และ Laird, P., การลดความขัดแย้งให้น้อยที่สุด: วิธีการซ่อมแซมแบบฮิวริสติกสำหรับปัญหาความพึงพอใจตามข้อจำกัดและการจัดตารางเวลา, ปัญญาประดิษฐ์ (ฉบับพิเศษว่าด้วยการให้เหตุผลตามข้อจำกัด), Vol.58, Nos.1-3 1992, 161-205
• Tsang, EPK และ Voudouris, C., การค้นหาแบบโลคอลที่รวดเร็วและการค้นหาแบบโลคอลที่มีคำแนะนำ และการประยุกต์ใช้กับปัญหาการจัดตารางเวลาพนักงานของ British Telecom, Operations Research Letters, Elsevier Science Publishers, Amsterdam, Vol.20, No.3, มีนาคม 1997, 119-127
• Voudouris, C., Tsang, EPK, ปัญหาการแก้ข้อจำกัดบางส่วนและการค้นหาเฉพาะที่แบบมีคำแนะนำ, รายงานการประชุมนานาชาติครั้งที่สองว่าด้วยการประยุกต์ใช้เทคโนโลยีข้อจำกัดในทางปฏิบัติ (PACT'96), หน้า 337-356, ลอนดอน, สหราชอาณาจักร, 1996
• Voudouris, C, การค้นหาเฉพาะที่แบบมีคำแนะนำสำหรับปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัดเรียง, วิทยานิพนธ์ปริญญาเอก, ภาควิชาวิทยาการคอมพิวเตอร์, มหาวิทยาลัยเอสเซ็กซ์, โคลเชสเตอร์, สหราชอาณาจักร, กรกฎาคม 1997
• Voudouris, C., การค้นหาแบบโลคอลที่มีคำแนะนำ—ตัวอย่างประกอบในการปรับปรุงฟังก์ชัน, BT Technology Journal, Vol.16, No.3, กรกฎาคม 1998, 46-50
• Voudouris, C., Tsang, E., การแก้ปัญหาการจัดสรรความถี่วิทยุโดยใช้การค้นหาแบบโลคอลที่มีคำแนะนำ ในรายงานการประชุมสัมมนา NATO ว่าด้วยการจัดสรร การแบ่งปัน และการอนุรักษ์ความถี่ในระบบ (AEROSPACE) AGARD เอกสารหมายเลข 14 อัลบอร์ก เดนมาร์ก 5-7 ตุลาคม 1998
• Voudouris, C. & Tsang, EPK, การค้นหาแบบโลคอลที่มีคำแนะนำและการประยุกต์ใช้กับปัญหาพนักงานขายเดินทาง, European Journal of Operational Research, Anbar Publishing, Vol.113, Issue 2, มีนาคม 1999, 469-499
• Voudouris, C. และ Tsang, EPK, การค้นหาเฉพาะที่แบบมีคำแนะนำเข้าร่วมกลุ่มชั้นนำในการเพิ่มประสิทธิภาพแบบไม่ต่อเนื่อง, DIMACS Series in Discrete Mathematics and Theoretical Computer Science เล่มที่ 57, 2001, 29-39
• Voudouris, C. และ Tsang, EPK, การค้นหาแบบโลคอลที่มีคำแนะนำ ใน F. Glover (บรรณาธิการ), คู่มือเมตาฮิวริสติกส์, Kluwer, 2003, 185-218
• Voudouris, C., Tsang, EPK และ Alsheddy, A., การค้นหาแบบโลคอลที่มีคำแนะนำ บทที่ 11 ใน M. Gendreau และ JY Potvin (บรรณาธิการ), Handbook of Metaheuristics, Springer, 2010, 321-361
• Voudouris, C., Tsang, E., Alsheddy, A., การค้นหาแบบมีคำแนะนำในพื้นที่, สารานุกรมการวิจัยปฏิบัติการและวิทยาการจัดการของ Wiley, Wiley, 2010
• Voudouris, C., Tsang, E., Alsheddy, A., การประยุกต์ใช้การค้นหาแบบมีคำแนะนำอย่างมีประสิทธิภาพ, สารานุกรมการวิจัยปฏิบัติการและวิทยาการจัดการของ Wiley, Wiley, 2010

• หน้าหลักการค้นหาในพื้นที่แบบมีคำแนะนำ
• แหล่งข้อมูลการค้นหาในพื้นที่แบบมีคำแนะนำ
• Google OR-Tools - การค้นหาในพื้นที่แบบมีคำแนะนำ