การเพิ่มประสิทธิภาพโดยใช้ Hopfield Network
การเพิ่มประสิทธิภาพเป็นการดำเนินการเพื่อให้บางสิ่งบางอย่างเช่นการออกแบบสถานการณ์ทรัพยากรและระบบมีประสิทธิภาพมากที่สุด การใช้ความคล้ายคลึงกันระหว่างฟังก์ชันต้นทุนและฟังก์ชันพลังงานเราสามารถใช้เซลล์ประสาทที่เชื่อมต่อกันอย่างมากเพื่อแก้ปัญหาการเพิ่มประสิทธิภาพ เครือข่ายประสาทชนิดดังกล่าวคือเครือข่าย Hopfield ซึ่งประกอบด้วยชั้นเดียวที่มีเซลล์ประสาทที่เกิดซ้ำที่เชื่อมต่อกันอย่างสมบูรณ์อย่างน้อยหนึ่งเซลล์ สามารถใช้เพื่อเพิ่มประสิทธิภาพ
สิ่งที่ต้องจำขณะใช้เครือข่าย Hopfield เพื่อการเพิ่มประสิทธิภาพ -
ฟังก์ชันพลังงานต้องต่ำสุดของเครือข่าย
จะพบวิธีแก้ปัญหาที่น่าพอใจแทนที่จะเลือกรูปแบบที่จัดเก็บไว้
คุณภาพของโซลูชันที่พบโดยเครือข่าย Hopfield นั้นขึ้นอยู่กับสถานะเริ่มต้นของเครือข่ายอย่างมีนัยสำคัญ
ปัญหาพนักงานขายในการเดินทาง
การค้นหาเส้นทางที่สั้นที่สุดที่พนักงานขายเดินทางเป็นหนึ่งในปัญหาด้านการคำนวณซึ่งสามารถปรับให้เหมาะสมได้โดยใช้เครือข่ายประสาทเทียม Hopfield
แนวคิดพื้นฐานของ TSP
Travelling Salesman Problem (TSP) เป็นปัญหาการเพิ่มประสิทธิภาพแบบคลาสสิกที่พนักงานขายต้องเดินทาง nเมืองที่เชื่อมต่อกันโดยรักษาค่าใช้จ่ายตลอดจนระยะทางที่เดินทางต่ำสุด ตัวอย่างเช่นพนักงานขายต้องเดินทาง 4 เมือง A, B, C, D และเป้าหมายคือค้นหาทัวร์วงกลมที่สั้นที่สุด ABC – D เพื่อลดค่าใช้จ่ายให้น้อยที่สุดซึ่งรวมถึงค่าใช้จ่ายในการเดินทางจาก เมืองสุดท้าย D ไปยังเมืองแรก A
การเป็นตัวแทนเมทริกซ์
จริงๆแล้ว TSP แต่ละครั้งของ n-city สามารถแสดงเป็นไฟล์ n × n เมทริกซ์ที่มี ith แถวอธิบายไฟล์ ithที่ตั้งของเมือง. เมทริกซ์นี้Mสำหรับ 4 เมือง A, B, C, D สามารถแสดงได้ดังนี้ -
$$ M = \ begin {bmatrix} A: & 1 & 0 & 0 & 0 \\ B: & 0 & 1 & 0 & 0 \\ C: & 0 & 0 & 1 & 0 \\ D: & 0 & 0 & 0 & 1 \ end {bmatrix} $$
โซลูชันโดย Hopfield Network
ในขณะที่พิจารณาโซลูชันของ TSP โดยเครือข่าย Hopfield นี้ทุกโหนดในเครือข่ายจะสอดคล้องกับองค์ประกอบหนึ่งในเมทริกซ์
การคำนวณฟังก์ชันพลังงาน
เพื่อให้เป็นโซลูชันที่เหมาะสมที่สุดฟังก์ชันพลังงานจะต้องมีค่าต่ำสุด บนพื้นฐานของข้อ จำกัด ต่อไปนี้เราสามารถคำนวณฟังก์ชันพลังงานได้ดังนี้ -
ข้อ จำกัด - I
ข้อ จำกัด ประการแรกบนพื้นฐานที่เราจะคำนวณฟังก์ชันพลังงานคือองค์ประกอบหนึ่งจะต้องเท่ากับ 1 ในแต่ละแถวของเมทริกซ์ M และองค์ประกอบอื่น ๆ ในแต่ละแถวต้องเท่ากับ 0เนื่องจากแต่ละเมืองสามารถเกิดขึ้นได้เพียงตำแหน่งเดียวใน TSP tour ข้อ จำกัด นี้สามารถเขียนทางคณิตศาสตร์ได้ดังนี้ -
$$ \ displaystyle \ sum \ LIMIT_ {j = 1} ^ n M_ {x, j} \: = \: 1 \: สำหรับ \: x \: \ in \: \ lbrace1, ... , n \ rbrace $ $
ตอนนี้ฟังก์ชันพลังงานที่จะย่อเล็กสุดตามข้อ จำกัด ข้างต้นจะมีคำที่เป็นสัดส่วนกับ -
$$ \ displaystyle \ sum \ LIMIT_ {x = 1} ^ n \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ LIMIT_ {j = 1} ^ n M_ {x, j } \ end {array} \ right) ^ 2 $$
ข้อ จำกัด -II
ดังที่เราทราบใน TSP หนึ่งเมืองสามารถเกิดขึ้นได้ในตำแหน่งใดก็ได้ในทัวร์ด้วยเหตุนี้ในแต่ละคอลัมน์ของเมทริกซ์ Mองค์ประกอบหนึ่งต้องเท่ากับ 1 และองค์ประกอบอื่น ๆ ต้องเท่ากับ 0 ข้อ จำกัด นี้สามารถเขียนทางคณิตศาสตร์ได้ดังนี้ -
$$ \ displaystyle \ sum \ LIMIT_ {x = 1} ^ n M_ {x, j} \: = \: 1 \: สำหรับ \: j \: \ in \: \ lbrace1, ... , n \ rbrace $ $
ตอนนี้ฟังก์ชันพลังงานที่จะย่อเล็กสุดตามข้อ จำกัด ข้างต้นจะมีคำที่เป็นสัดส่วนกับ -
$$ \ displaystyle \ sum \ LIMIT_ {j = 1} ^ n \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ LIMIT_ {x = 1} ^ n M_ {x, j } \ end {array} \ right) ^ 2 $$
การคำนวณฟังก์ชันต้นทุน
สมมติว่าเมทริกซ์กำลังสองของ (n × n) แสดงโดย C หมายถึงเมทริกซ์ต้นทุนของ TSP สำหรับ n เมืองที่ n > 0. ต่อไปนี้เป็นพารามิเตอร์บางส่วนในขณะคำนวณฟังก์ชันต้นทุน -
Cx, y - องค์ประกอบของเมทริกซ์ต้นทุนแสดงถึงต้นทุนการเดินทางจากเมือง x ถึง y.
ความคลาดเคลื่อนขององค์ประกอบของ A และ B สามารถแสดงได้ด้วยความสัมพันธ์ต่อไปนี้ -
$$ M_ {x, i} \: = \: 1 \: \: and \: \: M_ {y, i \ pm 1} \: = \: 1 $$
ดังที่เราทราบใน Matrix ค่าเอาต์พุตของแต่ละโหนดอาจเป็น 0 หรือ 1 ดังนั้นสำหรับทุกคู่ของเมือง A, B เราสามารถเพิ่มเงื่อนไขต่อไปนี้ในฟังก์ชันพลังงาน -
$$ \ displaystyle \ sum \ LIMIT_ {i = 1} ^ n C_ {x, y} M_ {x, i} (M_ {y, i + 1} \: + \: M_ {y, i-1}) $$
บนพื้นฐานของฟังก์ชันต้นทุนและค่าข้อ จำกัด ข้างต้นฟังก์ชันพลังงานขั้นสุดท้าย E ได้ดังนี้ -
$$ E \: = \: \ frac {1} {2} \ displaystyle \ sum \ LIMIT_ {i = 1} ^ n \ displaystyle \ sum \ LIMIT_ {x} \ displaystyle \ sum \ LIMIT_ {y \ neq x} C_ {x, y} M_ {x, i} (M_ {y, i + 1} \: + \: M_ {y, i-1}) \: + $$
$$ \: \ begin {bmatrix} \ gamma_ {1} \ displaystyle \ sum \ LIMIT_ {x} \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ LIMIT_ {i} M_ {x, i} \ end {array} \ right) ^ 2 \: + \: \ gamma_ {2} \ displaystyle \ sum \ LIMIT_ {i} \ left (\ begin {array} {c} 1 \: - \ : \ displaystyle \ sum \ LIMIT_ {x} M_ {x, i} \ end {array} \ right) ^ 2 \ end {bmatrix} $$
ที่นี่ γ1 และ γ2 คือค่าคงที่ในการชั่งน้ำหนักสองค่า