背包問題的案例
模擬退火算法優(yōu)化指派問題
1、引言
之前二狗已經(jīng)分別介紹過了，如何用模擬退火算法和遺傳算法，進(jìn)行背包問題的求解。其實背包問題是可以看成是一個可以看成是一個比較特殊的，有線性約束的，0-1規(guī)劃問題。在數(shù)學(xué)中還有很多其他特殊的問題，比如指派問題。指派問題可以看成是更特殊的多個背包問題（很多個背包求優(yōu)，每個背包只能裝一樣物品）。基本指派問題一般可以描述為有n個任務(wù)n個人。要求為n個任務(wù)分配給指定的人來完成。并且在這種基本情況下，人和任務(wù)需要是一一對應(yīng)的關(guān)系。不能有重復(fù)，不能出現(xiàn)兩個人做同一個任務(wù)，或者一個人同時做兩個任務(wù)的情況。（這些情況也屬于指派問題的范疇，但屬于更加復(fù)雜的情況，今天就不做講解）。指派問題已經(jīng)有了明確可解的算法，也就是我們大家都知道的匈牙利算法。同樣的，這個問題也可以使用模擬退火來解決。今天我們就使用模擬退火算法來為大家演示，如何在指派問題進(jìn)行優(yōu)化？
2、 數(shù)據(jù)結(jié)構(gòu)及重點講解
指派矩陣如圖
每行代表每個人單獨做每個工作的時間或費(fèi)用（cost），每列代表每個工作分別由每個人完成時的cost。矩陣中位于(i,j)的元素是第i個人做第j個工作的cost。將這四個元素相加即為整個問題的最優(yōu)解。由于是cost，當(dāng)然越小越好。
模擬退火算法這個名稱的來源大家已經(jīng)知道了，我們就不再贅述。這里要提的是退火算法中的馬爾可夫鏈。如果將每個特定時間序列上的解空間狀態(tài)看成離散的，并將這些離散狀態(tài)連成一條鏈的話。那么整個求解過程就是一條馬爾可夫鏈，這一個時刻的狀態(tài)，只和上一個相鄰的時間點上的狀態(tài)相關(guān)，而與之前的時間點狀態(tài)都無關(guān)。這聽起來有點像還錢。我不管誰欠你的錢，但是我只知道你欠我錢，我只管你要。SA中馬爾可夫鏈的長度就是模擬退火中溫度的變化。
展開 