《基於知識型蟻群算法的時間依賴型成像調度方法研究》是依託中國人民解放軍國防科技大學，由邢立寧擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於知識型蟻群算法的時間依賴型成像調度方法研究
- 項目類別：青年科學基金項目
- 項目負責人：邢立寧
- 依託單位：中國人民解放軍國防科技大學
中文摘要,結題摘要,
中文摘要
本項目針對時間依賴型成像調度問題進行一些預先研究。將時間依賴型成像調度問題分解為多星多任務分配、單星多任務觀測調度和多任務多資源數傳任務調度三個子問題；研究時間依賴型成像調度問題的求解框架，構建總問題求解和子問題求解之間的循環疊代關係；設計並實現求解多星多任務分配問題、單星多任務觀測調度問題和多任務多資源數傳任務調度問題的知識型蟻群算法：根據具體問題定義不同類型的知識，構建能有效管理各種知識的知識模型，基於蟻群最佳化思想設計可行方案構建機制，建立蟻群最佳化模型和知識模型之間的互動機制，設計能有效評價可行方案的指標集，最終實現對不同問題的高效求解；以高解析度對地觀測系統為背景，設計一個比較完善的能反映出時間依賴型成像調度問題本質特徵的套用實例。力爭該項目在理論、方法和結合國情方面達到國內先進水平。
結題摘要
本項目的主要研究成果可總結如下： （1）在現有智慧型最佳化方法的基礎上，論文建立了知識型蟻群算法的基本框架。該框架採用蟻群最佳化模型和知識模型相結合的集成建模思路：蟻群算法按照“鄰域搜尋”策略對待最佳化問題的可行空間進行搜尋；知識模型從前期的最佳化過程中挖掘出一些有用的知識，然後採用得到的知識來指導蟻群算法的後續最佳化過程。知識型蟻群算法的基本框架為現有最佳化方法改進提供了一種有益的借鑑。提出了精英個體知識、構件知識、運算元知識和參數知識等四種典型的知識形式，可輔助知識型智慧型最佳化方法高效地求解複雜最佳化問題。 （2）提出了考慮提早-延期懲罰調度問題的求解算法。機器加工一個工件引起的懲罰項不是一個固定值，而是依賴於工件的完工時間。考慮每個工件具有不等的釋放時間、交貨期、提早和延期懲罰係數，為並行機環境下的調度問題建立了數學模型。並行機環境下，一是將求解單機問題的模因演化算法進行了擴展使之套用於並行機環境，二是在給定工件加工序列的情況下提出了一種改進的構造啟發式算法確定工件的加工機器及開工時間，通過實驗分析給出了這兩種算法各自的適用場景。 （3）提出了訂單受理與調度問題的求解算法。為最大化完工訂單的收益，需要將選擇和調度這兩個決策過程集成考慮，從所有訂單中選擇出一部分加工並為各訂單安排加工時間，加工訂單獲得的收益依賴於訂單的完工時間。建立了該問題的數學模型，提出了求解該問題的差異化控制遺傳算法。算法中針對該問題的特點提出了一種衡量個體之間差異大小的準則，使用差異化控制策略使算法在搜尋過程中始終保持一個差異化種群，引入基於析構與構造策略的疊代貪婪啟發式算法作為局部搜尋算法。 （4）提出了具有多時間依賴特點調度問題的求解算法。該問題是在訂單受理與調度問題的基礎上，引入時間依賴轉換時間以及提早-延期懲罰，非常複雜、難以求解。採用位於0和1之間的實數作為編碼方式，每個實數表示工件的實際完工時間占整個時間視窗長度的比率。當給定一個實值向量時，根據向量中的各實數預先確定對應工件的開工時間和完工時間，並且根據工件的開工和完工時間計算不同工件之間需要的轉換時間。在此基礎上建立一個有向無環圖，圖中最長路徑上的節點即為被安排加工的工件，路徑的長度即為該實值向量對應的目標函式。提出一種基於該有向圖適應度評價的混合差分進化算法，通過和其他三種算法在測試算例上的實驗分析驗證了算法的有效性。
