化驗室資源調度優化的改進型克隆選擇算法

顧偉偉, 張棟良

(上海電力大學 自動化工程學院, 上海 200090)

化驗室調度的目的是將待化驗的化驗單及樣品分配到合適的設備,以此來提高共享資源的利用率,使得整個流程更加高效?；炇屹Y源調度問題本質上是一個組合優化[1]問題,針對原先的動態規劃法[2],其處理大規模復雜優化問題時存在不足,建模較為復雜,計算速度也較慢。目前智能算法如神經網絡[3]、遺傳算法[4]、模擬退火[5]等在調度問題上的應用越來越廣泛。近年來,研究人員提出了各種優化算法[6-14]以解決調度問題。高陽陽等人[15]在克隆選擇算法中設計了新的移民算子進行多種群交流,提高了搜索效率;宋丹等人[16]將克隆選擇算法與模糊非基因信息搜索策略相結合,改善了算法搜索能力及算法精度;周炳海和顧佳穎[17]在免疫克隆選擇算法中引入了新的鄰域搜索算子和種群更新算子,提高了算法的搜索效率。

傳統的克隆選擇算法與其他智能算法一樣,容易陷入局部最優、早熟收斂等問題。本文在克隆選擇算法的基礎上,引入了多種群協同進化的思想,以提高種群的多樣性;設計了新的克隆選擇算子,增加了個體的多樣性;提出了自適應變異算子,能加快局部搜索速度,提升全局搜索能力。

1 化驗室調度數學模型

化驗室處理化驗單的問題可表述為:有j個化驗單(一個化驗單可含多種樣品)在某一臺設備上化驗檢測,已知各類樣品的化驗時間和各樣品在各設備上化驗檢測的次序約束,合理地安排樣品所使用的設備以及化驗單檢測順序,可使化驗檢測流程效率達到最優。……