經濟調度問題的混合蟻群算法及序列二次規劃法解
2007-01-01 00:00:00羅中良
計算機應用研究 2007年6期
摘 要：為了獲得整體近似最優解，提出采用蟻群算法，搜索發電機可運行狀態的最優組合，并對蟻群算法的數學模型進行分析，以參數的形式給出具有普遍意義的收斂性定理。在此求解過程中，以每只人工螞蟻來表示符合限制條件的某個可運轉狀態的發電機組合并以序列二次規劃法來求解傳統的經濟調度問題。以三部機組的數值模擬，驗證該方法正確有效。
關鍵詞：經濟調度； 閥點效應； 螞蟻算法； 序列二次規劃法
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2007)06-0112-03
0 引言
發電機組的經濟調度問題是在各運轉機組電力輸出上、下限不等式約束及機組電力輸出總和與負載需求相等(本文未考慮傳輸損失)的等式約束前提下，最小化發電成本的最優化問題。而傳統的經濟調度(Economic Dispatch，ED)問題，其發電成本函數僅考慮為凸集函數，使其最小化問題可以有梯度搜索、線性規劃法、非線性規劃法、動態規劃法、拉格朗日乘數法、序列二次規劃法等。它們或難以得到最優解，或到高維問題很容易陷入維數災［1，2］。不過，發電機組實際運行時，其發電成本曲線將出現含漣波形狀的閥點效應。這并非凸集的發電成本函數曲線，其特征為不連續、不可微分，且以傳統方法求解很容易陷入局部最優解［3－6］。近年來，新的優化算法相繼出現并應用于ED問題，如遺傳算法、神經網絡算法、模擬退火算法、混沌優化算法［1］、蟻群算法［7］等。這些新算法在處理帶閥點效應非凸集非線性問題方面，取得了比較滿意的成果。這些新的方法各有優缺點，特別是存在計算復雜、收斂速度低、易陷入局部最優點、只適合離散組合優化而不適合連續變量的優化等問題，使其應用于實際工程領域受到限制。
本文根據這些算法的優勢和不足，利用蟻群算法全局優化能力，特別是對離散組合優化問題的良好能力［7－10］，利用序列二次規劃法（Sequential Quadratic Programming，SQP）的整體收斂性同時保持局部超一次收斂性［11－14］，提出混合蟻群算法及序列二次規劃法來求解帶閥點效應的經濟調度問題。目的是通過模擬真實螞蟻的覓食行為的蟻群算法根據信息素軌跡的強度及概率選擇技巧，找到發電機組可運轉狀態的最優組合。求解過程中以每只人工螞蟻來表示符合約束條件的某個可運轉狀態的發電機組合，再以二次規劃法來求解傳統特性的經濟調度問題。最后以三部機組的數值模擬來驗證上述算法的正確和有效性。
1 帶閥點效應的經濟調度問題描述
帶閥點效應的電力系統經濟調度問題是求解發電成本的最優化問題。通常以如下模型表示［4，15］：
本文以文獻[3]的研究對象為研究對象，圖1為文獻[3]中三部機組中第一部機組的發電成本曲線。本文求解開始時先找到整條曲線在不連續處的分界點，而每個分界點之間即為該機組的一個狀態。經分析后，圖1有七個分界點（精確到小數點后四位），所以有六個狀態。左邊分界點即該狀態電力輸出的下限值；右邊分界點有該狀態電力輸出的上限值。三部機組分界點所對應狀態的電力輸出上、下限值如表1所示。
根據表1，以兩只螞蟻為例來說明機組1－3可能的狀態選擇過程，如圖2所示。其中螞蟻1對應于機組1、2、3的可能運轉狀態組合{S2，S4，S3}；而螞蟻2的狀態組合則為{S6，S2，S1}。本文每個狀態的組合須先篩選以確認是否滿足約束條件。若滿足才可能成為可運轉狀態，也才可由SQP求得一組調度解。
2 帶閥點效應的經濟調度問題求解方法
本文提出以混合蟻群算法及序列二次規劃法（SQP）來求解帶閥點效應的經濟調度問題。在求解過程中，以每只人工螞蟻來表示符合約束條件的某個可運轉狀態的發電機組合并以序列二次規劃法來求解傳統特性的經濟調度問題。
2.1蟻群算法
蟻群算法源自昆蟲群體智慧的模擬智能理論，是由意大利學者M. Dorigo等人提出，并成功地應用在TSP、二次分配等問題上。同時也獲得專家、學者的青睞，紛紛將其應用于各自的領域上［7－10］。蟻群算法是模仿螞蟻覓食，尋找最短路徑的行為，而發展出來的啟發式方法。動物行為專家發現幾乎全盲的螞蟻，透過一種稱為Pheromone的分泌物作為信息素來進行群體間接通信，具有正反饋的信息素軌跡的增強使得所有螞蟻最后都能選擇最短路徑。蟻群算法能夠成功搜索整體近似最優解，主要在于概率選擇技巧、局部與整體信息素更新機制三部分。
2.1.1 概率選擇技巧
本文參考文獻[6，9，10]提出在第t次迭代時，人工螞蟻k在機組x的第i個運轉狀態，其選擇下一個機組的第j個運轉狀態的概率為
信息素更新機制本文采用局部和整體更新機制，一方面在路徑上蒸發掉部分的信息素（局部更新機制）；另一方面則要在較短的路徑上積累較高的信息素（整體更新機制）。
2.1.2 局部信息素更新機制
本文中，當某只螞蟻在每次迭代建立一個完整解之后，其走過的路徑上（機組運轉的狀態組合）的信息量，依據局部信息素更新機制進行更新。其數學式如下：
其中，ρ∈(0，1]為信息素軌跡持久系數；1-ρ為信息素揮發系數；τx→yi→j(0)為初始信息素，一般為一個小正數。本更新機制目的是為了使隨后的眾多螞蟻能找到更多不同的解，搜索到更多不同機組可運轉狀態的組合，以此找到更優解。
2.1.3 整體信息素更新機制
本文中，當所有螞蟻在每次迭代分別建立一個完整解之后，則對于其中最優解的那只螞蟻所走過的路徑（即某個可運轉狀態的發電機組合），再一次更新信息素，其公式為
其中，q為一正系數；m為螞蟻數量；Fk為螞蟻k在第t次迭代時的可運行狀態發電機組合，經SQP求解其傳統經濟調度的發電成本。
2.1.4 蟻群算法的收斂性
目前，蟻群算法是眾多學者的研究熱點，但算法的效果一般以應用實例來驗證。本文為了分析蟻群算法的收斂性，先分析算法是非齊次的馬氏鏈，然后給出其收斂性定理；根據收斂性定理很容易選擇蟻群算法的參數。這為算法的設計提供了一定的理論依據。
由于限于篇幅，本文不加證明地根據X(t)是非齊次馬氏鏈，直接給出算法的收斂性定理。定理表明只要在滿足給定約束條件的信息素揮發系數情況下，算法能以概率1逼近最優狀態（最優路徑），即找到最優解，且各路徑上的信息素分布呈現最優路徑上的信息素達到最大值，其他路徑趨于零。
定理中采用蟻群算法參數的形式給出收斂性條件。其中信息素揮發系數1-ρt可以根據算法需要在全局優化和收斂速度之間折中進行變化。于是定理可適應蟻群算法的各種信息素揮發系數的情況，即上述定理對蟻群算法的收斂性具有普遍意義。
2.2 序列二次規劃法
在每次迭代后，對于所有螞蟻（每只螞蟻表示找到符合約束條件的某個可運轉狀態的發電機組合），分別用SQP求解傳統的經濟調度問題。SQP在解決具有整體收斂性的同時具有保持局部超一次收斂性，在解決非線性規劃問題具有優越的性能，因而得到廣泛應用。具體可參考文獻[5，14]。
2.3 混合算法步驟
根據上面的分析，本文提出的混合算法可用下列步驟進行描述和求解。
(1)系統初始化：讀取系統資料及設定相關算法參數。
(2)找到所有符合等式及不等式約束條件的可運轉狀態的發電機組合，開始讓每只螞蟻隨機選擇各發電機某一狀態組合，并通過SQP建立完整的初始解。
(3)對每只螞蟻隨機任選首部機組的某一狀態，然后依概率選擇技巧，讓每只螞蟻選擇下一機組Y的第j個運轉狀態，直到所有發電機均選擇完畢。
(4)重復步驟(3)，直到所有螞蟻完成各機組狀態的選擇。
(5)以SQP分別對每只螞蟻求解傳統的經濟調度問題。
(6)執行局部信息素更新機制。
(7)執行整體信息素更新機制。
(8)判斷是否符合終止條件；否則返回步驟(3)。
3 算法有效性驗證
4 結束語
本文提出以混合螞蟻算法及序列二次規劃法求解帶閥點效應的經濟調度問題。通過蟻群算法找到發電機組可運轉的最優組合，并以序列二次規劃法求解傳統的經濟調度問題。對其中的蟻群算法進行了數學模型描述，并給出了對蟻群算法具有普遍意義的收斂性定理。最后以三部機組的數值模擬，算法能100%找到文獻[3]研究對象的最優解，成功驗證了算法的正確和有效性。同時筆者改變算法參數也能搜索到最優解，說明算法具有一定的魯棒性。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
