การจำลองการอบอ่อน ( SA ) เป็นเทคนิคเชิงความน่าจะเป็นสำหรับการประมาณค่าที่เหมาะสมที่สุดทั่วโลกของฟังก์ชัน ที่กำหนด โดยเฉพาะอย่างยิ่ง เป็นเมตาฮิวริสติกสำหรับการประมาณค่าที่เหมาะสมที่สุดทั่วโลกในพื้นที่การค้นหา ขนาดใหญ่ สำหรับปัญหาการหาค่าที่เหมาะสมที่สุดสำหรับค่าที่เหมาะสมที่สุดเฉพาะที่จำนวนมาก SA สามารถค้นหาค่าที่เหมาะสมที่สุดทั่วโลกได้^{[ 1 ]}มักใช้เมื่อพื้นที่การค้นหาเป็นแบบไม่ต่อเนื่อง (ตัวอย่างเช่นปัญหาพนักงานขายเดินทางปัญหาความพึงพอใจของบูลีนการทำนายโครงสร้างโปรตีนและการจัดตารางงานในโรงงาน ) สำหรับปัญหาที่มีทรัพยากรการคำนวณคงที่ การค้นหาค่าที่เหมาะสมที่สุดทั่วโลกโดยประมาณอาจมีความสำคัญมากกว่าการพยายามค้นหาค่าที่เหมาะสมที่สุดเฉพาะที่ที่แม่นยำ ในกรณีเช่นนี้ SA อาจเป็นที่ต้องการมากกว่าอัลกอริทึมที่แม่นยำ เช่นการไล่ระดับความชันหรือการแบ่งและขอบเขตปัญหาที่แก้ไขโดย SA ในปัจจุบันได้รับการกำหนดโดยฟังก์ชันวัตถุประสงค์ ของตัวแปรหลายตัว ซึ่งอยู่ภายใต้ ข้อจำกัดทางคณิตศาสตร์หลายประการในทางปฏิบัติ การละเมิดข้อจำกัดสามารถถูกลงโทษเป็นส่วนหนึ่งของฟังก์ชันวัตถุประสงค์ได้

เทคนิคที่คล้ายกันนี้ได้รับการนำเสนออย่างอิสระในหลายโอกาส รวมถึง Pincus (1970) ^{[ 2 ]} Khachaturyan et al. (1979, ^{[ 3 ]} 1981 ^{[ 4 ]} ), Kirkpatrick, Gelatt และ Vecchi (1983) และ Cerny (1985) ^{[ 5 ]}ในปี 1983 วิธีการนี้ถูกใช้โดย Kirkpatrick, Gelatt Jr. และ Vecchi ^{[ 6 ]}เพื่อแก้ปัญหาการเดินทางของพนักงานขายพวกเขายังเสนอชื่อปัจจุบันของวิธีการนี้ว่า การอบชุบแบบจำลอง (simulated annealing) ^{[ 7 ]}

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

การจำลองสามารถทำได้โดยการแก้สมการจลนศาสตร์สำหรับฟังก์ชันความหนาแน่นของความน่าจะเป็น^{[ 8 ] [ 9 ] หรือโดยใช้วิธีการสุ่มตัวอย่างแบบสุ่ม [ 6} ] ^{[ 10 ]วิธีนี้}เป็นการดัดแปลงอั^{ลกอริทึมMetropolis – Hastings}ซึ่งเป็นวิธีMonte Carloเพื่อสร้างสถานะตัวอย่างของระบบเทอร์โมไดนามิกส์ที่ตีพิมพ์โดยN. Metropolisและคณะในปี 1953 ^{[ 11 ]}

สถานะs ของระบบทางกายภาพ บางระบบ และฟังก์ชันE ( s ) ที่ต้องการลดค่าให้เหลือน้อยที่สุดนั้น เปรียบได้กับพลังงานภายในของระบบในสถานะนั้น เป้าหมายคือการนำระบบจากสถานะเริ่ม ต้นใด ๆไปสู่สถานะที่มีพลังงานต่ำที่สุดเท่าที่จะเป็นไปได้

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

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

วิธีการฮิวริสติกแบบง่ายๆเช่นการปีนเขา (hill climbing ) ซึ่งเคลื่อนที่โดยการค้นหาเพื่อนบ้านที่ดีกว่าไปเรื่อยๆ และหยุดเมื่อพบคำตอบที่ไม่มีเพื่อนบ้านที่ดีกว่านั้น ไม่ได้รับประกันว่าจะนำไปสู่คำตอบที่ดีที่สุดที่มีอยู่เสมอไป ผลลัพธ์อาจเป็นเพียงจุด เหมาะสมที่สุดเฉพาะที่ (local optimum ) ในขณะที่คำตอบที่ดีที่สุดที่แท้จริงอาจเป็นจุด เหมาะสมที่สุดโดยรวม (global optimum)ซึ่งอาจแตกต่างออกไปส่วนเมตาฮิวริสติก (metaheuristics)ใช้เพื่อนบ้านของคำตอบเป็นวิธีในการสำรวจพื้นที่ของคำตอบ และถึงแม้ว่าจะชอบเพื่อนบ้านที่ดีกว่า แต่ในเชิงความน่าจะเป็นก็ยอมรับเพื่อนบ้านที่แย่กว่าเพื่อหลีกเลี่ยงการติดอยู่ในจุดเหมาะสมที่สุดเฉพาะที่ และสามารถค้นหาจุดเหมาะสมที่สุดโดยรวมได้หากมีเวลามากพอ

ความน่าจะเป็นของการเปลี่ยนสถานะจากสถานะปัจจุบันไปยังสถานะใหม่ที่เป็นไปได้นั้น ถูกกำหนดโดยฟังก์ชันความน่าจะเป็นในการยอมรับซึ่งขึ้นอยู่กับพลังงานของทั้งสองสถานะ และพารามิเตอร์ที่เปลี่ยนแปลงตามเวลาโดยรวมที่เรียกว่าอุณหภูมิสถานะที่มีพลังงานน้อยกว่าจะดีกว่าสถานะที่มีพลังงานมากกว่า ฟังก์ชันความน่าจะเป็นจะต้องมีค่าเป็นบวกแม้ว่าจะมากกว่า ก็ตามคุณสมบัตินี้ช่วยป้องกันไม่ให้วิธีการติดอยู่ที่จุดต่ำสุดเฉพาะที่ซึ่งแย่กว่าจุดต่ำสุดโดยรวม ${\displaystyle s}$${\displaystyle s_{\mathrm {new} }}$${\displaystyle P(e,e_{\mathrm {new} },T)}$${\displaystyle e=E(s)}$${\displaystyle e_{\mathrm {new} }=E(s_{\mathrm {new} })}$${\displaystyle T}$${\displaystyle P}$${\displaystyle e_{\mathrm {new} }}$${\displaystyle e}$

เมื่อค่า เข้าใกล้ศูนย์ ความน่าจะเป็นจะต้องเข้าใกล้ศูนย์หากและเข้าใกล้ค่าบวกในกรณีอื่น ๆ สำหรับค่า ที่เล็กพอระบบจะเลือกการเคลื่อนที่ที่ลงเนิน (เช่น ไปยังค่าพลังงานที่ต่ำกว่า) มากขึ้น และหลีกเลี่ยงการเคลื่อนที่ขึ้นเนินด้วยขั้นตอนดังกล่าว ขั้นตอนนี้จะลดลงเหลือ อัลก อริทึมแบบโลภ (greedy algorithm ) ซึ่งจะทำการเปลี่ยนผ่านเฉพาะที่ลงเนินเท่านั้น ${\displaystyle T}$${\displaystyle P(e,e_{\mathrm {new} },T)}$${\displaystyle e_{\mathrm {ใหม่} }>e}$${\displaystyle T}$${\displaystyle T=0}$

ในคำอธิบายดั้งเดิมของการจำลองการอบอ่อน (simulated annealing) ความน่าจะเป็นจะเท่ากับ 1 เมื่อ—นั่นคือ กระบวนการจะเคลื่อนลงเนินเสมอเมื่อพบวิธีที่จะทำเช่นนั้น โดยไม่ขึ้นอยู่กับอุณหภูมิ คำอธิบายและการใช้งานการจำลองการอบอ่อนจำนวนมากยังคงใช้เงื่อนไขนี้เป็นส่วนหนึ่งของคำจำกัดความของวิธีการ อย่างไรก็ตาม เงื่อนไขนี้ไม่จำเป็นสำหรับการทำงานของวิธีการ ${\displaystyle P(e,e_{\mathrm {new} },T)}$${\displaystyle e_{\mathrm {ใหม่} }<e}$

โดยปกติแล้ว ฟังก์ชันจะถูกเลือกเพื่อให้ความน่าจะเป็นในการยอมรับการเคลื่อนไหวลดลงเมื่อความแตกต่างเพิ่มขึ้น กล่าวคือ การเคลื่อนไหวขึ้นเนินเล็กๆ มีโอกาสเกิดขึ้นมากกว่าการเคลื่อนไหวขึ้นเนินใหญ่ๆ อย่างไรก็ตาม ข้อกำหนดนี้ไม่จำเป็นอย่างเคร่งครัด หากตรงตามข้อกำหนดข้างต้นแล้ว ${\displaystyle P}$${\displaystyle e_{\mathrm {ใหม่} }-e}$

ด้วยคุณสมบัติเหล่านี้ อุณหภูมิมีบทบาทสำคัญในการควบคุมวิวัฒนาการของสถานะของระบบ โดยเฉพาะอย่างยิ่งความไวต่อการเปลี่ยนแปลงของพลังงานในระบบ กล่าวคือ สำหรับค่า ที่มีขนาดใหญ่วิวัฒนาการของ จะมีความไวต่อการเปลี่ยนแปลงของพลังงานในระดับหยาบ ในขณะที่เมื่อ ค่า มีขนาดเล็ก วิวัฒนาการของ จะมีความไวต่อการเปลี่ยนแปลงของพลังงานในระดับละเอียด${\displaystyle T}$${\displaystyle s}$${\displaystyle T}$${\displaystyle s}$${\displaystyle T}$

เร็ว

ช้า

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

ชื่อและแรงบันดาลใจของอัลกอริทึมนี้ต้องการการควบคุมการเปลี่ยนแปลงอุณหภูมิ ซึ่งจำเป็นต้องลดอุณหภูมิลงอย่างค่อยเป็นค่อยไปในระหว่างการจำลอง อัลกอริทึมเริ่มต้นด้วยการตั้งค่าอุณหภูมิไว้สูง จากนั้นจะค่อยๆ ลดลงในแต่ละขั้นตอนตามตารางการอบอ่อน (annealing schedule ) ซึ่งผู้ใช้สามารถกำหนดได้ แต่ต้องสิ้นสุดใกล้กับช่วงเวลาที่กำหนดไว้ ด้วยวิธีนี้ ระบบคาดว่าจะเคลื่อนที่ไปยังบริเวณกว้างๆ ของพื้นที่การค้นหาที่มีคำตอบที่ดีในตอนแรก โดยไม่สนใจคุณลักษณะเล็กๆ ของฟังก์ชันพลังงาน จากนั้นจะเคลื่อนไปยังบริเวณที่มีพลังงานต่ำซึ่งจะแคบลง และสุดท้ายจะเคลื่อนลงตามหลักการลดลงที่ชันที่สุด (steepest descent heuristic) ${\displaystyle T}$${\displaystyle T=0}$

สำหรับปัญหาจำกัดใดๆ ที่กำหนด ความน่าจะเป็นที่อัลกอริทึมการอบชุบแบบจำลองจะสิ้นสุดลงด้วย โซลูชัน ที่เหมาะสมที่สุดทั่วโลกจะเข้าใกล้ 1 เมื่อตารางการอบชุบขยายออกไป^{[ 12 ]}อย่างไรก็ตาม ผลลัพธ์ทางทฤษฎีนี้ไม่ได้มีประโยชน์มากนัก เนื่องจากเวลาที่ต้องใช้เพื่อให้แน่ใจว่ามีความน่าจะเป็นของความสำเร็จอย่างมีนัยสำคัญมักจะเกินเวลาที่ต้องใช้สำหรับการ ค้นหา พื้นที่โซลูชันทั้งหมด^{[ 13 ]}

รหัสเทียมต่อไปนี้แสดงฮิวริสติกการจำลองการอบชุบ (simulated annealing) ตามที่อธิบายไว้ข้างต้น โดยเริ่มต้นจากสถานะs = ₀ และดำเนินต่อไปจนกว่า จะดำเนินการครบจำนวนขั้นตอนสูงสุดk _max ขั้นตอน ในกระบวนการนี้ ฟังก์ชันเรียก neighbour( s )ควรสร้างเพื่อนบ้านที่เลือกแบบสุ่มของสถานะs ที่กำหนดให้ ฟังก์ชันเรียกrandom(0, 1)ควรเลือกและส่งคืนค่าในช่วง[0, 1]แบบสุ่มอย่างสม่ำเสมอตารางการอบชุบถูกกำหนดโดยฟังก์ชันเรียกtemperature( r )ซึ่งควรให้ค่าอุณหภูมิที่จะใช้ โดยพิจารณาจากเศษส่วนrของงบประมาณเวลาที่ใช้ไปแล้ว

ในการนำวิธีการจำลองการอบอ่อน (simulated annealing) ไปใช้กับปัญหาเฉพาะเจาะจง จำเป็นต้องระบุพารามิเตอร์ต่อไปนี้: พื้นที่สถานะ (state space), ฟังก์ชันพลังงาน (เป้าหมาย) E() , ขั้นตอนการสร้างตัวเลือกเพื่อนบ้าน (neighbour()) , ฟังก์ชันความน่าจะเป็นในการยอมรับP()และตารางการอบอ่อนtemperature()รวมถึงอุณหภูมิเริ่มต้นinit_tempการเลือกพารามิเตอร์เหล่านี้มีผลกระทบอย่างมากต่อประสิทธิภาพของวิธีการ น่าเสียดายที่ไม่มีการเลือกพารามิเตอร์ใดที่จะดีสำหรับทุกปัญหา และไม่มีวิธีทั่วไปที่จะหาตัวเลือกที่ดีที่สุดสำหรับปัญหาที่กำหนด ส่วนต่อไปนี้จะให้แนวทางทั่วไปบางประการ

การจำลองการอบอ่อน (Simulated annealing) สามารถจำลองได้เป็นการเดินแบบสุ่มบนกราฟการค้นหา ซึ่งจุดยอดของกราฟคือสถานะที่เป็นไปได้ทั้งหมด และขอบที่เชื่อมต่อจุดยอดคือการเคลื่อนที่ที่เป็นไปได้ ข้อกำหนดที่สำคัญสำหรับ ฟังก์ชัน neighbour()คือ ฟังก์ชันนี้ต้องให้เส้นทางที่สั้นเพียงพอในกราฟนี้จากสถานะเริ่มต้นไปยังสถานะใดๆ ก็ตามที่อาจเป็นค่าเหมาะสมที่สุดทั่วโลก – เส้นผ่านศูนย์กลางของกราฟการค้นหาต้องมีขนาดเล็ก ตัวอย่างเช่น ในตัวอย่างพนักงานขายเดินทางข้างต้น พื้นที่การค้นหาสำหรับ n = 20 เมืองมี n! = 2,432,902,008,176,640,000 (2.4 ควินทิลเลียน) สถานะ แต่จำนวนเพื่อนบ้านของแต่ละจุดยอดมีเพียงขอบ (มาจาก) และเส้นผ่านศูนย์กลางของกราฟก็คือ ${\displaystyle \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190}$${\displaystyle n \choose 2}$${\displaystyle n-1}$

เพื่อตรวจสอบพฤติกรรมของการจำลองการอบอ่อน (simulated annealing) ในปัญหาเฉพาะเจาะจง อาจเป็นประโยชน์ที่จะพิจารณาความน่าจะเป็นของการเปลี่ยนสถานะที่เกิดจากตัวเลือกการออกแบบต่างๆ ที่ใช้ในการใช้งานอัลกอริทึม สำหรับแต่ละขอบของกราฟการค้นหา ความน่าจะเป็นของการเปลี่ยนสถานะถูกกำหนดให้เป็นความน่าจะเป็นที่อัลกอริทึมการจำลองการอบอ่อนจะเปลี่ยนไปสู่สถานะ เมื่อสถานะปัจจุบันคือความน่าจะเป็นนี้ขึ้นอยู่กับอุณหภูมิปัจจุบันที่ระบุโดยฟังก์ชัน temperature()ลำดับที่การเคลื่อนที่ที่เป็นไปได้ถูกสร้างขึ้นโดย ฟังก์ชัน neighbour()และฟังก์ชันความน่าจะเป็นในการยอมรับP()โปรดทราบว่าความน่าจะเป็นของการเปลี่ยนสถานะไม่ใช่เพียงแค่เพราะการเคลื่อนที่ที่เป็นไปได้จะถูกทดสอบแบบอนุกรม ${\displaystyle (s,s')}$${\displaystyle s'}$${\displaystyle s}$${\displaystyle P(e,e',T)}$

การระบุฟังก์ชันneighbour() , P()และtemperature()นั้นซ้ำซ้อนบางส่วน ในทางปฏิบัติ มักใช้ฟังก์ชันการยอมรับP() เดียวกัน สำหรับปัญหาหลายๆ ปัญหา และปรับฟังก์ชันอีกสองฟังก์ชันตามปัญหาเฉพาะนั้นๆ

ในการกำหนดวิธีการโดย Kirkpatrick และคณะ ฟังก์ชันความน่าจะเป็นในการยอมรับถูกกำหนดให้เป็น 1 ถ้าและเป็น0 ในกรณีอื่น ๆ สูตรนี้ได้รับการพิสูจน์อย่างผิวเผินโดยการเปรียบเทียบกับการเปลี่ยนสถานะของระบบทางกายภาพ มันสอดคล้องกับอัลกอริทึม Metropolis–Hastingsในกรณีที่ T=1 และการกระจายข้อเสนอของ Metropolis–Hastings เป็นแบบสมมาตร อย่างไรก็ตาม ความน่าจะเป็นในการยอมรับนี้มักถูกใช้สำหรับการจำลองการอบอ่อนแม้ว่า ฟังก์ชัน neighbour()ซึ่งคล้ายคลึงกับการกระจายข้อเสนอใน Metropolis–Hastings จะไม่สมมาตรหรือไม่เป็นความน่าจะเป็นเลยก็ตาม ผลก็คือ ความน่าจะเป็นในการเปลี่ยนสถานะของอัลกอริทึมการจำลองการอบอ่อนจึงไม่สอดคล้องกับการเปลี่ยนสถานะของระบบทางกายภาพที่คล้ายคลึงกัน และการกระจายสถานะในระยะยาวที่อุณหภูมิคงที่อาจไม่จำเป็นต้องมีความคล้ายคลึงกับการกระจายสมดุลทางเทอร์โมไดนามิกของสถานะของระบบทางกายภาพนั้นที่อุณหภูมิใด ๆ อย่างไรก็ตาม คำอธิบายส่วนใหญ่เกี่ยวกับการจำลองการอบชุบด้วยความร้อน (simulated annealing) มักจะถือว่าฟังก์ชันการยอมรับดั้งเดิมยังคงเหมือนเดิม ซึ่งอาจถูกกำหนดไว้ตายตัวในหลายๆ การใช้งานของ SA ${\displaystyle P(e,e',T)}$${\displaystyle e'<e}$${\displaystyle \exp(-(e'-e)/T)}$${\displaystyle T}$

ในปี พ.ศ. 2533 Moscato และ Fontanari ^{[ 14 ]}และ Dueck และ Scheuer ^{[ 15 ]}ได้เสนอว่าการอัปเดตแบบกำหนด (เช่น การอัปเดตที่ไม่ขึ้นอยู่กับกฎการยอมรับแบบความน่าจะเป็น) สามารถเร่งกระบวนการเพิ่มประสิทธิภาพได้โดยไม่ส่งผลกระทบต่อคุณภาพขั้นสุดท้าย Moscato และ Fontanari สรุปจากการสังเกตเส้นโค้ง "ความร้อนจำเพาะ" ของการอบอ่อนแบบ "การอัปเดตเกณฑ์" ที่มาจากการศึกษาของพวกเขาว่า "ความสุ่มของการอัปเดต Metropolis ในอัลกอริทึมการอบอ่อนแบบจำลองไม่ได้มีบทบาทสำคัญในการค้นหาค่าต่ำสุดที่ใกล้เคียงค่าที่เหมาะสมที่สุด" ในทางกลับกัน พวกเขาเสนอว่า "การทำให้พื้นผิวของฟังก์ชันต้นทุนเรียบขึ้นที่อุณหภูมิสูงและการกำหนดค่าต่ำสุดอย่างค่อยเป็นค่อยไปในระหว่างกระบวนการทำความเย็นเป็นส่วนประกอบพื้นฐานสำหรับความสำเร็จของการอบอ่อนแบบจำลอง" วิธีนี้ได้รับความนิยมในเวลาต่อมาภายใต้ชื่อ "การยอมรับเกณฑ์" ตามชื่อของ Dueck และ Scheuer ในปี พ.ศ. 2544 Franz, Hoffmann และ Salamon ได้แสดงให้เห็นว่ากลยุทธ์การอัปเดตแบบกำหนดได้นั้นเป็นกลยุทธ์ที่เหมาะสมที่สุดในบรรดาอัลกอริทึมจำนวนมากที่จำลองการเดินแบบสุ่มบนภูมิทัศน์ต้นทุน/พลังงาน^{[ 16 ]}

ในการเลือกตัวสร้างตัวเลือก (candidate generator neighbour()) ต้องคำนึงว่าหลังจากวนซ้ำอัลกอริทึมการจำลองการอบอ่อน (simulated annealing algorithm) ไปไม่กี่รอบ พลังงานของสถานะปัจจุบันจะต่ำกว่าสถานะสุ่มมาก ดังนั้น โดยทั่วไปแล้ว ควรปรับตัวสร้างตัวเลือกไปทางตัวเลือกที่มีพลังงานของสถานะปลายทางใกล้เคียงกับพลังงานของสถานะปัจจุบันหลักการ นี้ (ซึ่งเป็นหลักการสำคัญของอัลกอริทึม Metropolis–Hastings ) มีแนวโน้มที่จะตัด ตัวเลือก ที่ดีมาก ๆและ ตัวเลือก ที่แย่ มาก ๆ ออกไป อย่างไรก็ตาม ตัวเลือกที่ดีมาก ๆ มักพบได้น้อยกว่าตัวเลือกที่แย่มาก ๆ ดังนั้น หลักการนี้จึงค่อนข้างมีประสิทธิภาพโดยทั่วไป ${\displaystyle s'}$

ในปัญหาพนักงานขายเดินทางข้างต้น ตัวอย่างเช่น การสลับเมืองสอง เมือง ที่อยู่ติดกันในการเดินทางที่ใช้พลังงานต่ำ คาดว่าจะส่งผลกระทบต่อพลังงาน (ความยาว) เพียงเล็กน้อย ในขณะที่การสลับเมืองสอง เมือง ใดๆ ก็ตามมีแนวโน้มที่จะเพิ่มความยาวมากกว่าที่จะลดลง ดังนั้น ตัวสร้างเพื่อนบ้านแบบสลับเมืองที่อยู่ติดกันจึงคาดว่าจะทำงานได้ดีกว่าตัวสร้างเพื่อนบ้านแบบสลับเมืองใดๆ แม้ว่าตัวหลังอาจให้เส้นทางที่สั้นกว่าเล็กน้อยไปยังจุดที่เหมาะสมที่สุด (ด้วยการสลับเมือง แทนที่จะเป็น) ${\displaystyle n-1}$${\displaystyle n(n-1)/2}$

คำอธิบายที่แม่นยำยิ่งขึ้นของฮิวริสติกคือ ควรลองสถานะผู้สมัครแรกๆที่มีค่ามาก สำหรับฟังก์ชันการยอมรับ "มาตรฐาน" ข้างต้น หมายความว่ามีค่าอยู่ในลำดับของหรือน้อยกว่า ดังนั้น ในตัวอย่างพนักงานขายเดินทางข้างต้น เราสามารถใช้ฟังก์ชันที่สลับเมืองสองเมืองแบบสุ่ม โดยที่ความน่าจะเป็นในการเลือกคู่เมืองจะลดลงจนเป็นศูนย์เมื่อระยะห่างระหว่างเมืองเพิ่มขึ้นเกินกว่า ${\displaystyle s'}$${\displaystyle P(E(s),E(s'),T)}$${\displaystyle P}$${\displaystyle E(s')-E(s)}$${\displaystyle T}$neighbour()${\displaystyle T}$

ในการเลือกตัวสร้างพลังงานที่เหมาะสมneighbour()นั้น จำเป็นต้องพยายามลดจำนวนจุดต่ำสุดเฉพาะที่ "ลึก" ลงด้วย ซึ่งก็คือสถานะ (หรือกลุ่มสถานะที่เชื่อมต่อกัน) ที่มีพลังงานต่ำกว่าสถานะข้างเคียงทั้งหมดอย่างมาก "แอ่ง กัก เก็บพลังงานแบบปิด" เหล่านี้ อาจดักจับอัลกอริทึมการจำลองการอบชุบ (simulated annealing algorithm) ได้ด้วยความน่าจะเป็นสูง (โดยประมาณเป็นสัดส่วนกับจำนวนสถานะในแอ่ง) และเป็นเวลานานมาก (โดยประมาณเป็นแบบเลขชี้กำลังตามความแตกต่างของพลังงานระหว่างสถานะโดยรอบกับด้านล่างของแอ่ง)

โดยทั่วไปแล้ว เป็นไปไม่ได้ที่จะออกแบบตัวสร้างตัวเลือกที่สามารถบรรลุเป้าหมายนี้และจัดลำดับความสำคัญของตัวเลือกที่มีพลังงานใกล้เคียงกันได้ ในทางกลับกัน มักจะสามารถปรับปรุงประสิทธิภาพของการจำลองการอบอ่อนได้อย่างมากโดยการเปลี่ยนแปลงตัวสร้างแบบง่ายๆ ตัวอย่างเช่น ในปัญหาพนักงานขายเดินทาง ไม่ยากที่จะแสดงเส้นทางสองเส้นทาง, , ที่มีความยาวเกือบเท่ากัน โดยที่ (1) เป็นเส้นทางที่เหมาะสมที่สุด (2) ทุกลำดับของการสลับคู่เมืองที่แปลงเป็นจะผ่านเส้นทางที่ยาวกว่าทั้งสองเส้นทางมาก และ (3) สามารถแปลงเป็น ได้โดยการสลับ (กลับลำดับของ) ชุดของเมืองที่ต่อเนื่องกัน ในตัวอย่างนี้และอยู่ใน "แอ่งลึก" ที่แตกต่างกัน หากตัวสร้างทำการสลับคู่แบบสุ่มเท่านั้น แต่จะอยู่ในแอ่งเดียวกันหากตัวสร้างทำการสลับส่วนแบบสุ่ม ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$

การเปรียบเทียบทางกายภาพที่ใช้ในการให้เหตุผลของการอบอ่อนแบบจำลองนั้นถือว่าอัตราการเย็นตัวต่ำพอที่จะทำให้การกระจายความน่าจะเป็นของสถานะปัจจุบันอยู่ใกล้สมดุลทางอุณหพลศาสตร์ตลอดเวลา น่าเสียดายที่เวลาผ่อนคลาย —เวลาที่ต้องรอให้สมดุลกลับคืนมาหลังจากการเปลี่ยนแปลงอุณหภูมิ—ขึ้นอยู่กับ "ลักษณะทางภูมิศาสตร์" ของฟังก์ชันพลังงานและอุณหภูมิปัจจุบันอย่างมาก ในอัลกอริทึมการอบอ่อนแบบจำลอง เวลาผ่อนคลายยังขึ้นอยู่กับตัวสร้างผู้สมัครด้วยวิธีที่ซับซ้อนมาก โปรดทราบว่าพารามิเตอร์ทั้งหมดเหล่านี้มักจะถูกจัดเตรียมเป็นฟังก์ชันกล่องดำให้กับอัลกอริทึมการอบอ่อนแบบจำลอง ดังนั้นอัตราการเย็นตัวที่เหมาะสมจึงไม่สามารถกำหนดล่วงหน้าได้และควรปรับตามประสบการณ์สำหรับแต่ละปัญหา อัลกอริทึม การอบอ่อนแบบจำลองแบบปรับตัวได้จะแก้ไขปัญหานี้โดยการเชื่อมโยงตารางการเย็นตัวเข้ากับความคืบหน้าของการค้นหา วิธีการปรับตัวอื่นๆ เช่น การอบอ่อนแบบจำลองทางอุณหพลศาสตร์^{[ 17 ]}จะปรับอุณหภูมิโดยอัตโนมัติในแต่ละขั้นตอนตามความแตกต่างของพลังงานระหว่างสองสถานะตามกฎของอุณหพลศาสตร์

บางครั้ง การย้อนกลับไปยังวิธีแก้ปัญหาที่ดีกว่าอย่างเห็นได้ชัด อาจดีกว่าการเปลี่ยนจากสถานะปัจจุบันไปเรื่อยๆ กระบวนการนี้เรียกว่าการเริ่มต้นใหม่ของการจำลองการอบชุบ (Simulated Annealing) ในการทำเช่นนี้ เราจะตั้งค่าและและอาจเริ่มต้นตารางการอบชุบใหม่ การตัดสินใจที่จะเริ่มต้นใหม่นั้นอาจขึ้นอยู่กับเกณฑ์หลายประการ ที่สำคัญได้แก่ การเริ่มต้นใหม่โดยอิงจากจำนวนขั้นตอนที่กำหนดไว้ การเริ่มต้นใหม่โดยอิงจากว่าพลังงานปัจจุบันสูงเกินไปเมื่อเทียบกับพลังงานที่ดีที่สุดที่ได้รับมาแล้วหรือไม่ การเริ่มต้นใหม่แบบสุ่ม เป็นต้น ${\displaystyle s}$${\displaystyle e}$${\displaystyle {\text{sbest}}}$${\displaystyle {\text{ebest}}}$

• อัลกอริทึม Metropolis–Hasting ที่มีปฏิสัมพันธ์ (หรือที่เรียกว่าMonte Carlo แบบลำดับ^{[ 18 ]} ) ผสมผสานการเคลื่อนไหวการอบอ่อนจำลองเข้ากับการยอมรับ-การปฏิเสธบุคคลที่เหมาะสมที่สุดซึ่งมีกลไกการรีไซเคิลแบบมีปฏิสัมพันธ์
• การอบชุบควอนตัมใช้ "ความผันผวนควอนตัม" แทนความผันผวนทางความร้อนเพื่อทะลุผ่านกำแพงสูงแต่บางในฟังก์ชันเป้าหมาย
• การอุโมงค์แบบสุ่ม (Stochastic tunneling)พยายามเอาชนะความยากลำบากที่เพิ่มขึ้นในการจำลองการอบอ่อน (simulated annealing) ในการหลุดพ้นจากจุดต่ำสุดเฉพาะที่ (local minima) เมื่ออุณหภูมิลดลง โดยการ "อุโมงค์" ผ่านสิ่งกีดขวาง
• การค้นหาแบบ Tabuโดยปกติจะเคลื่อนไปยังสถานะใกล้เคียงที่มีพลังงานต่ำกว่า แต่จะเคลื่อนขึ้นเนินเมื่อพบว่าตัวเองติดอยู่ในจุดต่ำสุดเฉพาะที่ และหลีกเลี่ยงวงจรโดยการเก็บ "รายการต้องห้าม" ของโซลูชันที่เคยเห็นแล้ว
• วิวัฒนาการแบบสองเฟสเป็นกลุ่มของอัลกอริธึมและกระบวนการ (ซึ่งรวมถึงการจำลองการอบอ่อน) ที่เป็นตัวกลางระหว่างการค้นหาแบบเฉพาะที่และการค้นหาแบบโดยรวม โดยใช้ประโยชน์จากการเปลี่ยนแปลงเฟสในพื้นที่การค้นหา
• การเพิ่มประสิทธิภาพการค้นหาแบบตอบสนอง (Reactive Search Optimization)มุ่งเน้นไปที่การผสมผสานการเรียนรู้ของเครื่องเข้ากับการเพิ่มประสิทธิภาพ โดยการเพิ่มวงจรป้อนกลับภายในเพื่อปรับพารามิเตอร์อิสระของอัลกอริทึมให้เข้ากับลักษณะเฉพาะของปัญหา ของอินสแตนซ์ และของสถานการณ์โดยรอบโซลูชันปัจจุบัน
• อัลกอริทึมทางพันธุกรรมจะเก็บรักษาชุดคำตอบไว้หลายชุด แทนที่จะมีเพียงชุดเดียว คำตอบใหม่ๆ จะถูกสร้างขึ้นไม่เพียงแต่โดย "การกลายพันธุ์" (เช่นเดียวกับใน SA) แต่ยังโดย "การผสมผสาน" ของคำตอบสองคำตอบจากชุดคำตอบที่มีอยู่ด้วย เกณฑ์ความน่าจะเป็นที่คล้ายกับที่ใช้ใน SA จะถูกนำมาใช้เพื่อเลือกผู้สมัครสำหรับการกลายพันธุ์หรือการผสมผสาน และเพื่อกำจัดคำตอบส่วนเกินออกจากชุดคำตอบ
• อัลกอริทึมแบบเมเมติกค้นหาวิธีแก้ปัญหาโดยใช้ชุดของเอเจนต์ที่ทั้งร่วมมือและแข่งขันกันในกระบวนการ บางครั้งกลยุทธ์ของเอเจนต์เกี่ยวข้องกับขั้นตอนการจำลองการอบอ่อนเพื่อให้ได้วิธีแก้ปัญหาที่มีคุณภาพสูงก่อนที่จะรวมเข้าด้วยกัน^{[ 19 ]}การอบอ่อนยังได้รับการเสนอแนะให้เป็นกลไกในการเพิ่มความหลากหลายของการค้นหาอีกด้วย^{[ 20 ]}
• การปรับให้เหมาะสมแบบค่อยเป็นค่อยไปจะ "ปรับให้เรียบ" ฟังก์ชันเป้าหมายไปพร้อมๆ กับการปรับให้เหมาะสม
• การเพิ่มประสิทธิภาพโดยใช้แบบจำลองอาณานิคมมด (ACO) ใช้มดจำนวนมาก (หรือตัวแทน) ในการสำรวจพื้นที่คำตอบและค้นหาพื้นที่ที่มีผลผลิตสูงในระดับท้องถิ่น
• วิธีการครอสเอนโทรปี (CE) สร้างโซลูชันที่เป็นไปได้ผ่านการแจกแจงความน่าจะเป็นแบบมีพารามิเตอร์ พารามิเตอร์จะได้รับการปรับปรุงผ่านการลดค่าครอสเอนโทรปีให้เหลือน้อยที่สุด เพื่อสร้างตัวอย่างที่ดีขึ้นในรอบถัดไป
• การค้นหาความกลมกลืนของเสียงเลียนแบบการเล่นดนตรีแบบด้นสดของนักดนตรีแต่ละคน โดยที่นักดนตรีแต่ละคนจะเล่นโน้ตหนึ่งตัวเพื่อหาเสียงประสานที่ดีที่สุดร่วมกัน
• การปรับให้เหมาะสมแบบสุ่ม (Stochastic optimization)เป็นชุดวิธีการที่ครอบคลุม ซึ่งรวมถึงการจำลองการอบอ่อน (simulated annealing) และวิธีการอื่นๆ อีกมากมาย
• การเพิ่มประสิทธิภาพด้วยฝูงอนุภาค (Particle Swarm Optimization)เป็นอัลกอริทึมที่จำลองมาจากปัญญาของฝูง (Swarm Intelligence) ซึ่งค้นหาคำตอบสำหรับปัญหาการเพิ่มประสิทธิภาพในพื้นที่การค้นหา หรือสร้างแบบจำลองและทำนายพฤติกรรมทางสังคมโดยมีเป้าหมายกำกับอยู่
• อัลกอริทึมรากและลำต้นเลื้อย (RRA) เป็น อัลกอริทึมการเพิ่มประสิทธิภาพ แบบเมตาฮิวริสติกสำหรับการแก้ปัญหาแบบโมดอลเดียวและหลายโมดอล ซึ่งได้รับแรงบันดาลใจจากลำต้นเลื้อยและรากของพืชในธรรมชาติ
• อัลกอริทึมหยดน้ำอัจฉริยะ (IWD) ซึ่งเลียนแบบพฤติกรรมของหยดน้ำตามธรรมชาติเพื่อแก้ปัญหาการหาค่าเหมาะสมที่สุด
• การปรับอุณหภูมิแบบขนาน (Parallel tempering)คือการจำลองสำเนาของแบบจำลองที่อุณหภูมิ (หรือแฮมิลโทเนียน ) ต่างกัน เพื่อเอาชนะอุปสรรคทางศักยภาพ
• อัลกอริทึมการจำลองการอบอ่อนแบบหลายวัตถุประสงค์ถูกนำมาใช้ในการเพิ่มประสิทธิภาพแบบหลายวัตถุประสงค์^{[ 21 ]}

• A. Das และ BK Chakrabarti (บรรณาธิการ), Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)
• Weinberger, E. (1990). "ภูมิทัศน์ความเหมาะสมที่สัมพันธ์กันและไม่สัมพันธ์กัน และวิธีแยกแยะความแตกต่าง" Biological Cybernetics . 63 (5): 325– 336. doi : 10.1007/BF00202749 . S2CID  851736 .
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "ส่วนที่ 10.12 วิธีการจำลองการอบอ่อน" สูตรการคำนวณเชิงตัวเลข : ศิลปะแห่งการคำนวณทางวิทยาศาสตร์ (ฉบับที่ 3). นิวยอร์ก: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 978-0-521-88068-8เก็บถาวรจากต้นฉบับเมื่อวันที่ 11 สิงหาคม 2554 เรียกดูเมื่อวันที่ 13 สิงหาคม 2554
• Strobl, MAR; Barker, D. (2016). "เกี่ยวกับการเปลี่ยนเฟสของการจำลองการอบอ่อนในการสร้างวิวัฒนาการ" . Molecular Phylogenetics and Evolution . 101 : 46– 55. Bibcode : 2016MolPE.101...46S . doi : 10.1016/j.ympev.2016.05.001 . PMC  4912009 . PMID  27150349 .
• V.Vassilev, A.Prahova: "การใช้การจำลองการอบอ่อนในการควบคุมระบบการผลิตแบบยืดหยุ่น" วารสารนานาชาติทฤษฎีสารสนเทศและการประยุกต์ใช้เล่มที่ 6/1999
• D. Thiel, "การจำลองการอบอ่อน: จากอุณหพลศาสตร์เชิงสถิติสู่การแก้ปัญหาเชิงการจัดเรียง", สารานุกรมระบบสนับสนุนชีวิต UNESCO – EOLSS, บทที่ วิทยาศาสตร์ระบบและไซเบอร์เนติกส์ – เล่ม III [1]

• การจำลองการอบชุบ (Simulated Annealing)แอปพลิเคชัน JavaScript ที่ช่วยให้คุณทดลองใช้งานการจำลองการอบชุบ มีซอร์สโค้ดให้ด้วย
• "อัลกอริทึมการจำลองการอบชุบทั่วไป" เก็บถาวรเมื่อ 23 กันยายน 2008 ที่Wayback Machineโปรแกรม MATLAB แบบโอเพนซอร์สสำหรับแบบฝึกหัดการจำลองการอบชุบทั่วไป
• บทเรียนแบบเรียนรู้ด้วยตนเองเกี่ยวกับการจำลองการอบอ่อน (Simulated Annealing)โครงการจาก Wikiversity
• Google อยู่ในสภาวะซ้อนทับกันระหว่างการใช้และการไม่ใช้คอมพิวเตอร์ควอนตัม Ars Technica อภิปรายถึงความเป็นไปได้ที่คอมพิวเตอร์ D-Wave ที่ Google ใช้ อาจเป็นตัวประมวลผลร่วมแบบ Simulated Annealing ที่มีประสิทธิภาพ
• [2]อัลกอริทึมการเพิ่มประสิทธิภาพหลายวัตถุประสงค์แบบจำลองการอบอ่อน: AMOSA