เมตาฮิวริสติกแบบขนาน

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

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

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

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

สำหรับการอภิปรายอย่างละเอียดเกี่ยวกับวิธีการผสมผสานความขนานกับเมตาฮิวริสติก โปรดดูที่[2 ]

เมตาฮิวริสติกส์สำหรับการแก้ปัญหาการหาค่าเหมาะสมที่สุด อาจมองได้ว่าเป็นการเดินสำรวจไปตามละแวกใกล้เคียง โดยติดตามเส้นทางการค้นหาผ่านขอบเขตคำตอบของปัญหาที่กำลังพิจารณาอยู่:

อัลกอริทึม: รหัสเทียมทั่วไปแบบลำดับตามวิถีการเคลื่อนที่ Generate( s (0)); // วิธีแก้ปัญหาเริ่มต้น t  := 0; // ขั้นตอนเชิงตัวเลข while not Termination Criterion(s(t)) do s′( t ) := SelectMove(s( t )); // การสำรวจบริเวณใกล้เคียง if AcceptMove(s′( t )) then s( t ) := ApplyMove(s′( t )); t  := t + 1; endwhile

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

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

• แบบจำลองการเริ่มต้นหลายจุดแบบขนาน : ประกอบด้วยการเรียกใช้หลายวิธีตามวิถีการเคลื่อนที่พร้อมกัน เพื่อคำนวณหาคำตอบที่ดีและเสถียรยิ่งขึ้น วิธีเหล่านี้อาจแตกต่างกันหรือเหมือนกัน เป็นอิสระต่อกันหรือร่วมมือกัน เริ่มต้นจากคำตอบเดียวกันหรือต่างกัน และกำหนดค่าด้วยพารามิเตอร์เดียวกันหรือต่างกันก็ได้
• โมเดลการเคลื่อนที่แบบขนาน : เป็นโมเดลหลัก-รองระดับต่ำที่ไม่เปลี่ยนแปลงพฤติกรรมของฮิวริสติก การค้นหาแบบลำดับจะคำนวณผลลัพธ์เดียวกันแต่ช้ากว่า ในตอนเริ่มต้นของการวนซ้ำแต่ละครั้ง มาสเตอร์จะคัดลอกโซลูชันปัจจุบันไปยังโหนดที่กระจายอยู่ โหนดแต่ละโหนดจะจัดการผู้สมัคร/โซลูชันของตนเองแยกกัน และผลลัพธ์จะถูกส่งกลับไปยังมาสเตอร์
• โมเดลเร่งความเร็วการเคลื่อนไหว : คุณภาพของการเคลื่อนไหวแต่ละครั้งจะถูกประเมินในลักษณะขนานแบบรวมศูนย์ โมเดลนี้มีความน่าสนใจเป็นพิเศษเมื่อฟังก์ชันการประเมินสามารถทำงานแบบขนานได้ เนื่องจากใช้เวลาในการประมวลผลของ CPU และ/หรือใช้ทรัพยากร I/O มาก ในกรณีนั้น ฟังก์ชันดังกล่าวสามารถมองได้ว่าเป็นผลรวมของฟังก์ชันย่อยจำนวนหนึ่งที่สามารถทำงานแบบขนานได้

เมตาฮิวริสติกแบบใช้ประชากรเป็นเทคนิคการค้นหาแบบสุ่มที่ได้รับการประยุกต์ใช้สำเร็จในแอปพลิเคชันจริงและซับซ้อนมากมาย (ปัญหาแบบเอพิสแตติก หลายโหมด หลายวัตถุประสงค์ และปัญหาที่มีข้อจำกัดสูง) อัลกอริทึมแบบใช้ประชากรเป็นเทคนิคแบบวนซ้ำที่ใช้ตัวดำเนินการแบบสุ่มกับกลุ่มของแต่ละบุคคล: ประชากร (ดูอัลกอริทึมด้านล่าง) แต่ละบุคคลในประชากรเป็นเวอร์ชันที่เข้ารหัสของโซลูชันชั่วคราว ฟังก์ชันการประเมินจะเชื่อมโยงค่าความเหมาะสมกับแต่ละบุคคลเพื่อบ่งชี้ความเหมาะสมกับปัญหา การประยุกต์ใช้ตัวดำเนินการแปรผันแบบสุ่มกับบุคคลที่เลือกจะนำทางประชากรไปยังโซลูชันชั่วคราวที่มีคุณภาพสูงขึ้นอย่างต่อเนื่อง ตระกูลเมตาฮิวริสติกที่เป็นที่รู้จักมากที่สุดซึ่งอิงกับการจัดการประชากรของโซลูชัน ได้แก่อัลกอริทึมวิวัฒนาการ (EA) การเพิ่มประสิทธิภาพด้วยฝูงมด (ACO) การเพิ่มประสิทธิภาพด้วยฝูงอนุภาค (PSO) การค้นหาแบบกระจาย (SS) วิวัฒนาการเชิงอนุพันธ์ (DE) และอัลกอริทึมการกระจายการประมาณค่า (EDA)

อัลกอริทึม: รหัสเทียมเมตาฮิวริสติกแบบลำดับตามประชากร สร้าง (P(0)); // ประชากรเริ่มต้น t  := 0; // ขั้นตอนเชิงตัวเลข ในขณะที่ยังไม่ถึงเกณฑ์การยุติ (P( t )) ให้ ประเมิน (P( t )); // ประเมินค่าประชากร P′′( t ) := ใช้ตัวดำเนินการแปรผัน (P′( t )); // การสร้างโซลูชันใหม่ P( t + 1) := Replace(P( t ), P′′( t )); // สร้างประชากรชุดถัดไป t  := t + 1; endwhile

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

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

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

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

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

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

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

นอกจากนี้ ยังมีการเสนอโมเดลแบบไฮบริดซึ่งใช้แนวทางการประมวลผลแบบขนานสองระดับ โดยทั่วไปแล้ว ระดับที่สูงกว่าสำหรับการประมวลผลแบบขนานจะเป็นการใช้งานแบบหยาบ และส่วนพื้นฐานจะดำเนินการในรูปแบบเซลลูลาร์ รูปแบบมาสเตอร์-สเลฟ หรือแม้แต่รูปแบบกระจายอื่นๆ

• อัลกอริทึมวิวัฒนาการของเซลล์
• เอ็นริเก้ อัลบา