歐洲電力市場 宋永華

1、宋永華宋永華英國利物浦大學(xué)英國利物浦大學(xué)歐盟電力市場歐盟電力市場最新進(jìn)展及對我國的啟發(fā)最新進(jìn)展及對我國的啟發(fā)提 綱可持續(xù)電力可持續(xù)電力的三大要素可持續(xù)電力的三大要素可持續(xù)電力可持續(xù)電力安全安全經(jīng)濟(jì)經(jīng)濟(jì)環(huán)保環(huán)保1. 依賴于新型能源技術(shù)實(shí)現(xiàn)可持續(xù)發(fā)展2. 依賴于市場化和放松管制提高電力工業(yè)的運(yùn)營效率21世紀(jì)的電網(wǎng)和電網(wǎng)技術(shù)1.統(tǒng)一或協(xié)調(diào)規(guī)劃建設(shè)，統(tǒng)一調(diào)度和運(yùn)行的統(tǒng)一或聯(lián)合特高壓電網(wǎng) 中國2.分布發(fā)電與交互式供電的分散智能電網(wǎng) - 歐洲統(tǒng)一或聯(lián)合特高壓電網(wǎng) - 中國電網(wǎng)的發(fā)展趨勢電力高速發(fā)展；資源分布不均衡；經(jīng)濟(jì)發(fā)展不平衡；電力市場發(fā)展提高電網(wǎng)輸送能力：遠(yuǎn)距離大容量輸電的需求。1. 特高壓輸電：特高

2、壓交流：1000KV; 特高壓直流: 800KV2. 半波輸電方式3. 緊湊型輸電方式 4. 多相交流輸電5. 超高壓干式電纜6. 氣體絕緣線路GIL（Gas Insulated Line）7. 高溫超導(dǎo)輸電線路8. 分頻輸電9. 提高現(xiàn)有線路的輸送能力 - 靈活交流輸電系統(tǒng)10.輸電控制新技術(shù)未來的大電網(wǎng)技術(shù) - 將在中國發(fā)展分布發(fā)電與交互式供電的分散智能電網(wǎng) - 歐洲電網(wǎng)的發(fā)展趨勢 歐洲的能源政策更加強(qiáng)調(diào)對環(huán)境的保護(hù)和可再生能源發(fā)電的發(fā)展。 可再生能源，特別是風(fēng)能、水電、太陽能和生物質(zhì)能的發(fā)展，是歐盟委員會能源政策的中心目標(biāo)。 這種能源政策的引導(dǎo)下，歐洲以分散式電源作為發(fā)展的一個(gè)必然方向，

3、而不強(qiáng)調(diào)電網(wǎng)規(guī)模的擴(kuò)大。分布發(fā)電與交互式供電的分散智能電網(wǎng) - 歐洲電網(wǎng)的發(fā)展趨勢 在歐洲，電網(wǎng)的發(fā)展有沒有未來？在歐洲，電網(wǎng)的發(fā)展有沒有未來？ 與電網(wǎng)的大容量和超高壓發(fā)展方向相反，歐洲更多的是關(guān)心智能電網(wǎng)技術(shù)。 未來的電網(wǎng)必須建立電網(wǎng)信息化管理系統(tǒng)之上，特別是低壓供電電網(wǎng)的信息化控制，流量平衡控制、網(wǎng)內(nèi)分布式能源智能管制系統(tǒng)、智能保護(hù)系統(tǒng)等。其電網(wǎng)的發(fā)展目標(biāo)是可靠、高效和靈活。當(dāng)前的電網(wǎng)當(dāng)前的電網(wǎng)歐洲未來電網(wǎng)歐洲未來電網(wǎng):智能智能/分散分散/自主自主 發(fā)發(fā)電電 和高度集成的網(wǎng)絡(luò)管理和高度集成的網(wǎng)絡(luò)管理StoragePhotovoltaics power plantWindpowerplant

4、House with domestic CHPPowerqualitydeviceStorageCentral power stationHouseFactoryCommercialbuildingLocal CHP plantStorageStoragePowerqualitydeviceFlowControlTransmission NetworkDistribution Network歐洲未來電網(wǎng)歐洲未來電網(wǎng)transmission380 kVinterconnectionsub-transmission110 kVdistribution10 . 30 kVdistribution40

5、0 VCHPGGchanging load flowstoragestorageCHPG未來供電結(jié)構(gòu)未來供電結(jié)構(gòu): :分布發(fā)電與交互式供電分布發(fā)電與交互式供電分布發(fā)電與交互式供電的分散智能電網(wǎng) -歐洲電網(wǎng)的發(fā)展趨勢 短期與中期研究計(jì)劃清潔能源, 尤其是可再生能源節(jié)能和能源使用效率: 需求側(cè)管理新型汽車燃料中期與長期研究計(jì)劃儲能技術(shù)(燃料電池)新型能源載體(液態(tài)氫) 再生能源新技術(shù)CO2分離能源策略對社會經(jīng)濟(jì)的影響歐洲歐洲能源能源技術(shù)的發(fā)展趨勢技術(shù)的發(fā)展趨勢 無論單獨(dú)的，聯(lián)網(wǎng)的再生能源發(fā)電都需要各種高效的儲能技術(shù)發(fā)電曲線負(fù)荷曲線歐洲歐洲能源能源技術(shù)的發(fā)展趨勢技術(shù)的發(fā)展趨勢儲能問題：尋找新的能量載

6、體，研制高密度、低成本、長壽命、無污染的儲能系統(tǒng)可能的儲能系統(tǒng)蓄電池蓄電池超導(dǎo)磁能超導(dǎo)磁能超級電容器，超級電容器，儲能是普通電容器的儲能是普通電容器的20-1000倍倍飛輪儲能飛輪儲能壓縮空氣儲能壓縮空氣儲能熱儲能熱儲能抽水蓄能抽水蓄能 新能源發(fā)電發(fā)展的挑戰(zhàn)高效、低成本地解決不連續(xù)、不穩(wěn)定、低密度、隨時(shí)間季節(jié)以及氣候變化的新能源的聚集與轉(zhuǎn)化問題；并網(wǎng)的新能源發(fā)電，如何減少系統(tǒng)對自然條件的依賴性，提高發(fā)電系統(tǒng)的穩(wěn)定性、可靠性；供電質(zhì)量及其控制問題；保護(hù)方案；獨(dú)立電力系統(tǒng)的穩(wěn)定性分析方法含新能源發(fā)電的配電網(wǎng)絡(luò)設(shè)計(jì)和運(yùn)行；含新能源發(fā)電的電力系統(tǒng)可靠性評價(jià)；經(jīng)濟(jì)分析；不同新能源發(fā)電系統(tǒng)聯(lián)合運(yùn)行；電力變

7、換器設(shè)計(jì)及其控制和運(yùn)行（風(fēng)電、光伏、微燃?xì)廨啓C(jī)）風(fēng)電、太陽能轉(zhuǎn)換最大化（風(fēng)速、太陽光跟蹤控制）設(shè)備制造技術(shù) 新能源發(fā)電的挑戰(zhàn)明確開展電力市場的目的增強(qiáng)競爭力提高效率激勵投資 增大投入競爭： 發(fā)供電選擇：用戶電力市場改革面臨的問題電力市場改革面臨的問題工業(yè)結(jié)構(gòu)、監(jiān)管和所有權(quán)市場結(jié)構(gòu)交易方式電力市場運(yùn)行的技術(shù)支持系統(tǒng)電力市場的運(yùn)行與控制當(dāng)前歐盟成當(dāng)前歐盟成員國員國2007 加盟國加盟國歐盟的基本特點(diǎn)歐盟的基本特點(diǎn)歐盟的基本特點(diǎn)歐盟的基本特點(diǎn)成員國：25人數(shù)：459百萬（Millions）發(fā)電容量：696,146MW歐盟的歐盟的基本基本特點(diǎn)特點(diǎn)歐盟的基本特點(diǎn)歐盟的基本特點(diǎn)當(dāng)前當(dāng)前未來歐洲電網(wǎng)的設(shè)想未

8、來歐洲電網(wǎng)的設(shè)想儲能光伏電站光伏電站風(fēng)電站風(fēng)電站具有戶用具有戶用 CHP的家庭的家庭電能質(zhì)量設(shè)備儲能電電 廠廠家庭家庭工廠工廠商業(yè)建筑物商業(yè)建筑物本地本地 CHP 站站儲能儲能電能質(zhì)量設(shè)備潮流控制器輸輸 電電 網(wǎng)網(wǎng)配配 電電 網(wǎng)網(wǎng)總體目標(biāo)統(tǒng)一的單個(gè)電力市場歐洲電力市場用戶可以在歐洲的任何地方從供電者購電，無論任一方地理位置在哪里或越境與否，最終都可送到用戶端至至 2015?加上新加盟的國家國家的相同框架結(jié)構(gòu)發(fā)電側(cè)競價(jià)發(fā)輸配電分離輸電網(wǎng)對第三方的開放開發(fā)市場建立統(tǒng)一的歐盟電力市場挑戰(zhàn)建立統(tǒng)一的歐盟電力市場挑戰(zhàn)建立統(tǒng)一的歐盟電力市場挑戰(zhàn)：當(dāng)前狀況建立統(tǒng)一的歐盟電力市場挑戰(zhàn)：當(dāng)前狀況北歐北歐歐洲中東

9、部歐洲中東部43.2526.7033.9033.8531.2038.5050-554 TWh9 TWh41 TWh18 TWh2 TWh36.0043.0024.4030.9525.2018.4625.14市場價(jià)格市場價(jià)格 基于基于 2004年數(shù)據(jù)年數(shù)據(jù)單位：歐元單位：歐元/MWh(數(shù)據(jù)數(shù)據(jù): Platts 22/03/2003)市場價(jià)格市場價(jià)格 基于基于 2006年數(shù)據(jù)年數(shù)據(jù)單位：歐元單位：歐元/MWh (數(shù)據(jù)數(shù)據(jù): Platts 16/02/2005)電力交易電力交易 2004 （買入（買入/賣出）交易平衡賣出）交易平衡 單位：單位：TWh (數(shù)據(jù)數(shù)據(jù): UCTE 16/02/2005)建

10、立統(tǒng)一的歐盟電力市場挑戰(zhàn)：當(dāng)前狀況建立統(tǒng)一的歐盟電力市場挑戰(zhàn)：當(dāng)前狀況建立統(tǒng)一的歐盟電力市場挑戰(zhàn)：當(dāng)前狀況物理流量和物理流量和交易流量的交易流量的不同：不同：比利時(shí)和意大利直接輸送100MW電能UKNSFIFDB NLLCH AISIEPDKCZNL時(shí)間表：改版多次歐洲法規(guī)電力導(dǎo)則電力導(dǎo)則（ Electricity directive ） 2003/55/EC 是歐洲電力市場的核心法規(guī)。在2004年7月份歐盟各成員國必須實(shí)施。電能和燃?xì)鈱?dǎo)則的實(shí)施指南（ Notes for implementation） 詳細(xì)說明導(dǎo)則實(shí)施的方法。電能越境交易規(guī)章電能越境交易規(guī)章（ Regulation on c

11、ross-border trade in electricity ） 1228/2003/EEC制定了各成員國之間電能輸送的條規(guī)。這個(gè)規(guī)章在 2004年7月號實(shí)施。是一個(gè)實(shí)用法律。歐洲國會和參議會在2006年1月18日制定的導(dǎo)則導(dǎo)則 （ Directive ）2005/89/EC重點(diǎn)關(guān)注保障電能供應(yīng)安全的措施和基礎(chǔ)投入等問題。這個(gè)導(dǎo)則必須在2008年2月24日實(shí)施。越境交易的電能導(dǎo)則和規(guī)章都是根據(jù)2001年三月的提議提議（ proposal ）對1996年舊電舊電力力導(dǎo)則導(dǎo)則（ old Electricity Directive ） 96/92/EC修訂而制定的。- 19971997年年2 2

12、月月1919日實(shí)施日實(shí)施主要規(guī)定：主要規(guī)定： 到到20052005年最小市場運(yùn)營量達(dá)年最小市場運(yùn)營量達(dá)30%30% 發(fā)輸配電分離（財(cái)務(wù)）發(fā)輸配電分離（財(cái)務(wù)） 輸電系統(tǒng)運(yùn)營者的提名輸電系統(tǒng)運(yùn)營者的提名 TPATPA（regTPA regTPA 或或 nTPAnTPA）或者單一購買方之間的）或者單一購買方之間的選擇選擇 新發(fā)電的授權(quán)和提議新發(fā)電的授權(quán)和提議歐洲法規(guī)歐洲電力導(dǎo)則 -2002年1月：一致通過修訂的導(dǎo)則 歐盟能源市場（電能和燃?xì)猓┑男聦?dǎo)則 必須設(shè)立監(jiān)管機(jī)構(gòu) 加強(qiáng)越境交易的監(jiān)管 僅基于授權(quán)的新發(fā)電直至200年7月100%的開放輸、配電系統(tǒng)運(yùn)營機(jī)構(gòu) （TSOs和DSOs）的分離2004年三月

13、： European Commission strategy paper 電力市場的中期展望（Medium term vision for the internal electricity market） 中期計(jì)劃=發(fā)展可越境的區(qū)域電力市場（REMs）歐洲電力導(dǎo)則 REMs創(chuàng)建的阻礙因素 發(fā)電廠的高市場能力和低平衡市場流量 輸電定價(jià)高 輸電定價(jià)的不確定性 輸電網(wǎng)運(yùn)營者之間入網(wǎng)費(fèi)的不一致 不完全分離 不同市場開放程度 不夠強(qiáng)的網(wǎng)絡(luò)聯(lián)絡(luò)不同組織結(jié)構(gòu)的職責(zé)歐盟國家政府國家監(jiān)管機(jī)構(gòu)輸電系統(tǒng)運(yùn)營機(jī)構(gòu)歐洲電能和燃?xì)獗O(jiān)管協(xié)調(diào)組（ The European Regulators Group for Elect

14、ricity and Gas，ERGEG）歐洲輸電系統(tǒng)運(yùn)營機(jī)構(gòu)（ETSO）例如： NationaGrid (UK), TenneT (Netherlands), Fingrid (Finland), Svenska Kraftnt (Sweden), Statnett (Norway), REE (Spain), CEPS (Czech Republic), REN (Portugal), Elia (Belgium)系統(tǒng)運(yùn)營輸電所有者市場運(yùn)營輸電系統(tǒng)運(yùn)營機(jī)構(gòu) （TSO） 1999年非正式地以TSOs俱樂部（club）命名 2001年6月以TSOs協(xié)會名義重建，具有明確的章程和決策權(quán)以及在Br

15、ussels設(shè)立永久秘書處 具有18個(gè)國家的33個(gè)TSO成員和4個(gè)中央TSO（Centrel-TSOs）協(xié)調(diào)成員 TSOI，愛爾蘭（Ireland）的TSOs協(xié)會 UKTSOA，英國TSO協(xié)會 NORDEL, 北歐TSOs UCTE，輸電協(xié)調(diào)聯(lián)盟，CENTREL協(xié)會，中西歐大陸國家的TSOs歐洲輸電系統(tǒng)運(yùn)營機(jī)構(gòu) （ETSO）阻塞管理Inter TSO compensation TSO間補(bǔ)償輸電費(fèi)用協(xié)調(diào)和位置信號運(yùn)營標(biāo)準(zhǔn)市場平衡ETSO的主要職責(zé) Nordpool/Scandinavia (1991) OMEL/Spain (1994) APX/Netherlands (1999) EEX (L

16、PX)/Germany (2000) PolPX/Poland (2000) 大多數(shù)歐洲國家決定采用雙邊市場結(jié)構(gòu) 許多國家中，雙邊交易（OTC）由自愿電能交易（PX）來補(bǔ)充 幾個(gè)TSOs運(yùn)營一個(gè)平衡市場以保障電力市場實(shí)時(shí)供求平衡歐洲電能交易 Borzen/ Slovenia (2001) OPCOM/Romania (2001) Powernext / France (2002) IPEX / ITALY (2001) UK PX (2002)北歐電力市場Norway（1993），）， Sweden（1996），），F(xiàn)inland（1998），），Denmark（1999，2000）影響當(dāng)前聯(lián)

17、合北歐電力市場的整合過程的關(guān)鍵因素為：影響當(dāng)前聯(lián)合北歐電力市場的整合過程的關(guān)鍵因素為： 個(gè)別國家的混合發(fā)電方式的不便性 由四個(gè)政府和能源管理部對此整合過程的支持 輸電系統(tǒng)運(yùn)營機(jī)構(gòu)較好的合作和支持 北歐電力庫（Nord Pool）電力交易是這個(gè)整合過程的源動力北歐電力庫（北歐電力庫（Nord Pool）在）在Elspot中央市場模型（中央市場模型（Elspot Centralized Market Splitting Model）上的應(yīng)用）上的應(yīng)用北歐電力市場北歐電力市場北歐電力市場躉售市場：躉售市場： 北歐電能交易實(shí)時(shí)市場的比額大約是全部北歐全年用電量北歐電能交易實(shí)時(shí)市場的比額大約是全部北歐全

18、年用電量的的32%。全年總交易量中金融交易是。全年總交易量中金融交易是3,800TWh（大約北（大約北歐年用電量的歐年用電量的10倍）。倍）。零售市場：零售市場： 大規(guī)模終端用戶，通常與零售商協(xié)商和簽合同 小規(guī)模終端用戶，能選擇零售供應(yīng)商和合同類型北歐電力市場北歐電力庫（北歐電力庫（Nord Pool）市場和出清服務(wù)）市場和出清服務(wù) 物質(zhì)交易的實(shí)時(shí)市場（北歐電力庫AS）金融市場期貨、預(yù)定和可選擇合同 金融電力合同的出清服務(wù)（北歐電力庫出清ASA）北歐電力市場北歐電力市場北歐電力市場第三部分第三部分啟發(fā)式優(yōu)化算法啟發(fā)式優(yōu)化算法電力市場面臨的不少問題都是運(yùn)籌優(yōu)化問題這類問題的求解算法，其實(shí)就是一種

19、搜索過程，它基于某種思想和機(jī)制，通過一定的途徑或規(guī)則來得到滿足用戶要求的解 科學(xué)的定量方法優(yōu)化問題的求解優(yōu)化問題的求解面臨的挑戰(zhàn)：多目標(biāo)；面臨的挑戰(zhàn)：多目標(biāo)； 復(fù)雜約束；復(fù)雜約束； 不確定性；隨機(jī)因素；不確定性；隨機(jī)因素； 技技術(shù)經(jīng)濟(jì)社會指標(biāo)術(shù)經(jīng)濟(jì)社會指標(biāo)優(yōu)化問題優(yōu)化問題Min c(x) (4a) xs.t.xl x x u (4b) fl f (x ) f u (4c) 其中，c目標(biāo)值x獨(dú)立變量向量 xl約束下限向量 xu約束上限向量 f 約束函數(shù)向量 fl約束函數(shù)下限向量 fu約束函數(shù)上限向量 詳細(xì)信息參見：SONG, Y.H. (eds.): Modern optimisation te

20、chniques in power systems (Kluwer Academic Publishers, 1999, ISBN 0-7923-5697-7)Ch1: Introduction Ch2: Simulated annealing applications Ch3: Tabu search appliaction in fault section estimation and state identification of unobserved protective relays in power system Ch4: Genetic algorithms for schedu

21、ling generation and maintenance in power systems Ch5: Transmission network planning using genetic algorithms Ch6: Artificial neural networks for generation scheduling Ch7: Decision making in a deregulated power environment based on fuzzy sets Ch8: Lagrangian relaxation applications to electric power

22、 operations and planning problems Ch9: Inter point models and applications in power systems Ch10: Ant colony search, advanced engineered-conditioning genetic algorithms and fuzzy logic controlled genetic algorithms: economic dispatch problems Ch11: Industry applications of artificial intelligence te

23、chniques ContentKwang Y. Lee, Mohamed A. El-Sharkawi (eds.) Modern Heuristic Optimization Techniques: Theory and Applications to Power Systems，Publisher: Wiley-IEEE Press Publication Date: 2008-02-08；ISBN-10 / ASIN: 0471457116 U.S. Department of Energy the National Science Foundation 線性和二次規(guī)劃線性和二次規(guī)劃M

24、in cTx (5a) x (5b) (5c)s.t.xl x x u l Ax u 其中，c目標(biāo)因子向量 (cT 表示c的轉(zhuǎn)置) x獨(dú)立變量向量 xl約束下限向量 xu約束上限向量 A 約束因子矩陣Min (5d)cTx + xT H x x其中，H二次項(xiàng)目標(biāo)因子矩陣線性和二次規(guī)劃線性和二次規(guī)劃簡單兩機(jī)調(diào)度問題G1G2L1G1 發(fā)電機(jī)1，功率極限100MW，燃料費(fèi)用40單位/MW.hrG2L1120MW的負(fù)荷發(fā)電機(jī)2，功率極限200MW，燃料費(fèi)用50單位/MW.hrMin40 x1 + 50 x2s.t.0 x1 1000 x2 200120 x1 + x2 120其中， x1表示發(fā)電機(jī)1的

25、輸出x2表示發(fā)電機(jī)2的輸出簡單兩機(jī)調(diào)度問題簡單兩機(jī)調(diào)度問題簡單方法x1 x2內(nèi)點(diǎn)法單純形法最優(yōu)可行區(qū)域不可行不可行不可行不可行迭代 0:( x1 = 0 , x2 = 0 )迭代 1:( x1 = 100 , x2 = 0 )迭代 2:( x1 = 100 , x2 = 20 )簡單兩機(jī)調(diào)度問題簡單兩機(jī)調(diào)度問題非線性規(guī)劃非線性規(guī)劃上坡算法的典型迭代過程上坡算法的典型迭代過程 x2 x1費(fèi)用等高線凸函數(shù)和凸集凸函數(shù)和凸集凸集非凸集凸函數(shù)非凸函數(shù)非線性規(guī)劃非線性規(guī)劃數(shù)學(xué)優(yōu)化方法數(shù)學(xué)優(yōu)化方法拉格朗日乘子理論拉格朗日乘子理論內(nèi)點(diǎn)法內(nèi)點(diǎn)法整數(shù)和混合整數(shù)法整數(shù)和混合整數(shù)法分枝定界法分枝定界法 動態(tài)規(guī)劃動態(tài)

26、規(guī)劃.數(shù)學(xué)優(yōu)化方法數(shù)學(xué)優(yōu)化方法2.A 2.A 數(shù)學(xué)最優(yōu)化方法的缺點(diǎn)：數(shù)學(xué)最優(yōu)化方法的缺點(diǎn)：p僅產(chǎn)生一個(gè)解；局部解p問題的公式化描述必須滿足數(shù)學(xué)約束條件p需要先進(jìn)的計(jì)算算法p可能遇到數(shù)值問題1.A 1.A 數(shù)學(xué)最優(yōu)化方法的優(yōu)點(diǎn)：數(shù)學(xué)最優(yōu)化方法的優(yōu)點(diǎn)：能保證收斂性基于數(shù)學(xué)分析好的終止規(guī)則解的附加信息能有效計(jì)算啟發(fā)式優(yōu)化方法啟發(fā)式優(yōu)化方法啟發(fā)式是一種在合理計(jì)算費(fèi)用下的尋找好的（即接近最優(yōu)）解技術(shù)，啟發(fā)式是一種在合理計(jì)算費(fèi)用下的尋找好的（即接近最優(yōu)）解技術(shù)，但不能保障可行性或最優(yōu)性，或甚至在許多情況下不能說明如何最優(yōu)但不能保障可行性或最優(yōu)性，或甚至在許多情況下不能說明如何最優(yōu)接近一個(gè)特殊可行解。大多數(shù)

27、現(xiàn)代啟發(fā)式搜索策略都是基于生物模擬接近一個(gè)特殊可行解。大多數(shù)現(xiàn)代啟發(fā)式搜索策略都是基于生物模擬的。的。主要包括：a.基于遺傳和演化的進(jìn)化算法；基于遺傳和演化的進(jìn)化算法；b.基于熱力學(xué)的模擬退火法；基于熱力學(xué)的模擬退火法；c.基于記憶反應(yīng)的基于記憶反應(yīng)的Tabu搜索；搜索；d.模擬螞蟻解決問題方式的蟻群搜索法；模擬螞蟻解決問題方式的蟻群搜索法；e.模擬鳥群捕食行為的粒子群算法模擬鳥群捕食行為的粒子群算法f. 基于大腦工作方式的人工神經(jīng)網(wǎng)絡(luò)；基于大腦工作方式的人工神經(jīng)網(wǎng)絡(luò)；g.基于人類語言分類和推理的模糊規(guī)劃法基于人類語言分類和推理的模糊規(guī)劃法 P,Q,R: (multi-)set of solu

28、tions S initialise (P); while not finish (P) do begin Q:= select(P) R:= create(Q) P:= merge(P,Q,R) end endP 是解庫(=1)。在某些情況下，例如簡單遺傳算法，S可 包含一個(gè)解的多復(fù)制（一個(gè)多集合）或者在其他情況下，S僅保護(hù)單個(gè)復(fù)制（集）。Q是所選擇的子庫并且用于創(chuàng)建解的新集合。R是新解集。啟發(fā)式優(yōu)化方法啟發(fā)式優(yōu)化方法2變量的單個(gè)和多集的等高線圖X1X2LLLGLG單集搜索局部優(yōu)化全局優(yōu)化多集搜索的第一次遺傳結(jié)果多集搜索的第二次遺傳結(jié)果多集搜索的第三次遺傳結(jié)果啟發(fā)式優(yōu)化方法啟發(fā)式優(yōu)化方法進(jìn)化

29、算法進(jìn)化算法遺傳算法遺傳算法遺傳規(guī)劃遺傳規(guī)劃進(jìn)化策略進(jìn)化策略進(jìn)化規(guī)劃進(jìn)化規(guī)劃雖然以上三種不同方法，然而，它們都受相同的自然進(jìn)化原理啟發(fā)而得。雖然以上三種不同方法，然而，它們都受相同的自然進(jìn)化原理啟發(fā)而得。在自然界，每一物種均需適應(yīng)一個(gè)復(fù)雜和變化環(huán)境以來增大其生存的可在自然界，每一物種均需適應(yīng)一個(gè)復(fù)雜和變化環(huán)境以來增大其生存的可能性。每一物種的特性都體現(xiàn)在單個(gè)染色體中，這些染色體在繁殖時(shí)會能性。每一物種的特性都體現(xiàn)在單個(gè)染色體中，這些染色體在繁殖時(shí)會發(fā)生變化。經(jīng)過一段時(shí)期后，這些染色體突變產(chǎn)生更適于生存的物種，發(fā)生變化。經(jīng)過一段時(shí)期后，這些染色體突變產(chǎn)生更適于生存的物種，并且具有更大機(jī)會將它們改

30、進(jìn)特性傳給后代。并且具有更大機(jī)會將它們改進(jìn)特性傳給后代。適者生存適者生存“Survival of the fittest”包括：包括：染色體表現(xiàn)形式染色體表現(xiàn)形式每一染色體（由一串基因組成）表示問題的一個(gè)可行解。二進(jìn)制數(shù)字（0，1）通常用于表示這些基因但有時(shí)根據(jù)其應(yīng)用實(shí)際情況而用整數(shù)或?qū)崝?shù)來表示。實(shí)際上，幾乎任何表示方式都能得到一個(gè)由有限長度字符串表示的解。例如，在經(jīng)濟(jì)調(diào)度問題中，可使用二進(jìn)制字符串10011來表示一臺發(fā)電機(jī)的19MW的輸出。初始種群初始種群一旦選定了合適的染色體表現(xiàn)方式，就需要創(chuàng)建一個(gè)初始種群來作為遺傳算法的起點(diǎn)。這個(gè)初始種群可隨機(jī)產(chǎn)生或者使用特殊方法、具體問題以及信息產(chǎn)生。

31、由經(jīng)驗(yàn)知，對于具有廣泛取值范圍的函數(shù)優(yōu)化問題，通常推薦30和100之間的種群大小。適應(yīng)度評價(jià)適應(yīng)度評價(jià)適應(yīng)度評價(jià)涉及定義一個(gè)目標(biāo)或者適應(yīng)度函數(shù)，以此來測試每一染色體的環(huán)境適應(yīng)性。隨著算法的進(jìn)行，期望得到“最好”染色體的單個(gè)適應(yīng)度與種群的整個(gè)適應(yīng)度一樣不斷增強(qiáng)。進(jìn)化算法進(jìn)化算法選擇選擇需要從當(dāng)前繁殖的種群中選擇染色體。如果有一個(gè)大小為10的種群，選擇程序篩選處兩個(gè)父染色體，基于它們的適應(yīng)度值，然后利用交叉和變異算子產(chǎn)生新種群的兩個(gè)子代。適應(yīng)度值越高的染色體被選擇來繁殖的可能性越大。交叉交叉一旦選擇了一對染色體，利用交叉可以生成子代。下面說明一個(gè)典型單點(diǎn)交叉過程：考慮如下兩個(gè)體，每一個(gè)體由11個(gè)二

32、進(jìn)制變量表示：個(gè)體1：0 1 1 1 0 0 1 1 0 1 0個(gè)體2：1 0 1 0 1 1 0 0 1 0 1選定交叉位置是：交叉位置：5交叉后產(chǎn)生的新個(gè)體為：子代1：0 1 1 1 0| 1 0 0 1 0 1 子代2：1 0 1 0 1| 0 1 1 0 1 0進(jìn)化算法進(jìn)化算法變異變異如果僅使用交叉操作來產(chǎn)生子代，便出現(xiàn)一個(gè)問題是：如果在某種特殊位置上初始種群中的所有染色體都具有相同值，于是所有未來子代將在此位置具有相同的值。例如，如果在位置2所有染色體均是0，于是所有未來子代將在位置2上的值為0.為了解決這種不希望情況發(fā)生使用進(jìn)行變異操作。以此來試圖對基因引入某些隨機(jī)變化，比如：0變

33、成1或反之。通常，這個(gè)變異發(fā)生的幾率是千分之幾。通過產(chǎn)生隨機(jī)數(shù)來檢驗(yàn)染色體每位值變異可能性，這個(gè)隨機(jī)數(shù)在0和1之間，并且如果這個(gè)數(shù)小于或等于給定變異概率（如0.001），于是位值就變化。進(jìn)化算法進(jìn)化算法I: I: 一個(gè)簡單遺傳算法包括如下步驟：一個(gè)簡單遺傳算法包括如下步驟：1.問題編碼2.隨機(jī)產(chǎn)生初始種群字符串3.每一字符串的適應(yīng)度評價(jià)4.選擇高適應(yīng)度字符串作為父代并根據(jù)它們的適應(yīng)度產(chǎn)生子代5.對當(dāng)前子代配對來產(chǎn)生新字符串，利用交叉和變異操作來引入變化并形成新字符串6.最后，新字符串替代現(xiàn)有字符串。重復(fù)此順序直到滿足終止條件遺傳算法（遺傳算法（GasGas）與傳統(tǒng)最優(yōu)化算法不同：）與傳統(tǒng)最優(yōu)化

34、算法不同：（1）針對控制變量的編碼而不是變量本身；（2）從解的一個(gè)種群到其他種群的搜索方法，而不是從個(gè)體到個(gè)體（3）僅使用目標(biāo)函數(shù)信息，不涉及導(dǎo)數(shù)。必須指出，標(biāo)準(zhǔn)Gas通常出現(xiàn)收斂困難問題。在某些應(yīng)用中，Gas能有效地搜索到全局最優(yōu)的鄰域，而難于收斂到最優(yōu)點(diǎn)。另一個(gè)困難是：標(biāo)準(zhǔn)GAs計(jì)算效率問題和早熟收斂。進(jìn)化算法進(jìn)化算法模擬退火技術(shù)最初提出是模擬冷卻時(shí)固體中結(jié)晶過程。此方法本身與熱力學(xué)相類似，特別地模擬液體冷卻和結(jié)晶方式，或者金屬冷卻退火方式。高溫時(shí)，液體分子自由移動。如果液體慢慢冷卻，熱動性受限。通常原子排列有序并形成一個(gè)規(guī)則純晶體。這個(gè)晶體具有最小能量的狀態(tài)，這對應(yīng)于數(shù)學(xué)優(yōu)化問題中的最優(yōu)

35、解。模擬退火法的搜索特性X1X2XC(X)模擬退火算法模擬退火算法一個(gè)模擬退火算法的基本部分：一個(gè)模擬退火算法的基本部分：1、系統(tǒng)形態(tài)的描述，即，問題最小化（最大化）對應(yīng)的解的一些展現(xiàn)方式，通常涉及表示一個(gè)解的參數(shù)的一些形態(tài)。2、一個(gè)形態(tài)中的隨機(jī)變化的產(chǎn)生器，這些變化通常是當(dāng)前形態(tài)的鄰域解（neighourhood），例如，參數(shù)之一的變化。3、目標(biāo)或者代價(jià)函數(shù)（模擬能量），其最小化是全局搜索過程。4、控制參數(shù)T（模擬溫度和用于確定可接受“uphill上坡”的概率）和一個(gè)退火計(jì)劃，使T值如何由大變?。?，形態(tài)經(jīng)過多少次隨機(jī)變化使T減少？以及減少多少？模擬退火算法（模擬退火算法（SASA）的優(yōu)

36、點(diǎn)）的優(yōu)點(diǎn)： （1）適用于處理任意系統(tǒng)和費(fèi)用函數(shù)；（2）能保證尋求最優(yōu)解；（3）算法實(shí)現(xiàn)的簡單性（即使是復(fù)雜問題）。這使SA算法可處理特殊問題或者沒有特殊方法可解決的問題。缺點(diǎn)缺點(diǎn)：重復(fù)退火速度慢。重復(fù)退火速度慢。對于具有平滑的能量面的問題，最好采用更簡單和更快速的局部優(yōu)化方法。這個(gè)方法不能表明是否已經(jīng)尋找到最優(yōu)解。需要利用一些其他方法（如分枝邊界法）來完成。因此，SA通常用做一個(gè)逼近算法。模擬退火算法模擬退火算法機(jī)組啟停機(jī)計(jì)劃問題機(jī)組啟停機(jī)計(jì)劃問題此例中，最優(yōu)化的每一步都考慮單個(gè)試探解（trial solution）。11011111模擬退火的每一步都考慮“局部移動”（local move）

37、，這個(gè)局部移動能改變單個(gè)隨機(jī)選擇位的值。然而，當(dāng)前試探解也許與最優(yōu)解有“兩步”遠(yuǎn)。這個(gè)兩步需要為：11011011 和11111111實(shí)際上，這些步中的任何一步都可以自己增加費(fèi)用。（簡單局部搜索方法則將在此點(diǎn)終止）。然而，模擬退火的溫度參數(shù)T可允許進(jìn)行這些步某一步操作，甚至它是一個(gè)“上坡（uphill）”移動。需要進(jìn)行第二步完成一個(gè)“簡單”下坡移動。模擬退火算法模擬退火算法Tabu搜索（搜索（TS）是一種迭代改進(jìn)程序，它從某些初始可行解開始，然后試圖以“鄰域最大下降”搜索算法來確定更較優(yōu)解。利用短期當(dāng)前解記憶功能和長期記憶過程的策略，它通過采取限制來避開局部最優(yōu)，并指導(dǎo)搜索過程。TS算法中，鄰

38、域用于產(chǎn)生用于選擇下一解/移動的鄰域子集，它可通過對某些移動進(jìn)行分類為Tabu（禁忌）和其他所需規(guī)定來修正。這是TS法的關(guān)鍵步驟，稱為Tabu列表管理。換而言之，Tabu列表管理關(guān)注Tabu列表的更新，即決定在搜索迭代中多少移動和哪些移動必須設(shè)成Tabu。有幾種基本方式來實(shí)現(xiàn)這個(gè)管理，通常涉及新記錄來分別維持不同屬性或不同類屬性。TS法的最基本組成部分基本組成部分包括：移動（Move）、Tabu列表（Tabu list）和激勵水平（標(biāo)準(zhǔn)）。Tabu搜索因此是一種基于多層記憶管理和響應(yīng)探究的元啟發(fā)式算式來求解全局最優(yōu)問題。它需要鄰域概念來得到一個(gè)試探解（也許是部分的）的。Tabu 搜索法搜索法T

39、abuTabu搜索采取如下步驟：搜索采取如下步驟：1. 初始化。隨機(jī)產(chǎn)生或利用給定問題的現(xiàn)有方法來給出初始解。2. 選擇移動。定義適用于當(dāng)前解的移動集來產(chǎn)生一組試探解。例如，移動具有形式：Xtrial=XcurrentX, X具有與X相同維數(shù)的向量。在所有產(chǎn)生的試探解中，TS尋找目標(biāo)函數(shù)改進(jìn)最多的一個(gè)解。3. 更新。從鄰域（希望的或者非禁忌的并且目標(biāo)函數(shù)值是最小的）中選擇下一個(gè)解。如果滿足停止條件則停止。否則更新T（根據(jù)某些Tabu更新規(guī)則）并返回選擇移動。TSTS的特點(diǎn)是：的特點(diǎn)是：以記憶自適應(yīng)形式的搜索方式來解決通常其他方法無法處理的復(fù)雜性問題。Tabu搜索是一種工程方法，必須根據(jù)所需解決

40、問題實(shí)際情況來進(jìn)行特別處理。麻煩的是，很少有理論知識來指導(dǎo)這個(gè)處理過程，必須對實(shí)踐經(jīng)驗(yàn)進(jìn)行分類。Tabu 搜索法搜索法蟻群搜索（蟻群搜索（ACSACS）的思想來源于真正蟻群行為，可用于求解函數(shù)或者組合最優(yōu)問題。蟻群搜索算法在某種程度上模擬螞蟻的行為。真正螞蟻能利用視覺提示尋找食物源與巢之間最短的路徑。它們也能根據(jù)環(huán)境的變化而改變路徑， 例如，若發(fā)現(xiàn)了一個(gè)新最短路徑將不再走舊的路徑。行為學(xué)家研究揭示這個(gè)能力本質(zhì)上也是由所謂的“荷爾蒙 跟蹤”。利用荷爾蒙螞蟻之間進(jìn)行交換信息來決定路徑和去的地方。螞蟻在行走時(shí)留下一定量的荷爾蒙，并且每個(gè)螞蟻更樂于朝荷爾蒙相對較多的方向走。蟻群搜索法蟻群搜索法一個(gè)簡單

41、蟻群算法包括如下步驟：1. 初始化。問題參數(shù)用一實(shí)數(shù)來編碼。每一步搜索前，蟻群的初始種群（巢）在可行域內(nèi)隨機(jī)產(chǎn)生，并且將在半徑不大于R的不同方向上爬行。2. 評價(jià)。所有螞蟻的適應(yīng)度利用目標(biāo)函數(shù)來評價(jià)。3. 增加蹤跡。按正比于螞蟻適應(yīng)度而在某一特定方向上增添蹤跡數(shù)量。4. 派遣螞蟻。根據(jù)目標(biāo)函數(shù)，螞蟻的工作由適應(yīng)度來衡量，而這個(gè)適應(yīng)度直接影響螞蟻已選擇特定方向上增加的蹤跡數(shù)量水平。每一螞蟻選擇移動到下一節(jié)點(diǎn)必須考慮兩個(gè)參數(shù)：節(jié)點(diǎn)的可見性和由其他螞蟻留下的蹤跡密度。派遣過程基于蹤跡密度和可視性利用競爭選擇在選定方向上派遣螞蟻。5. 揮發(fā)。最后，由一個(gè)螞蟻留下的荷爾蒙蹤跡最終將揮發(fā)，并且始發(fā)點(diǎn)（巢）也隨著最優(yōu)路徑的發(fā)現(xiàn)而更新。蟻群搜索法（ACS）的主要特點(diǎn)：正反饋、分布式計(jì)算以及貪婪式啟發(fā)搜索。正反饋可快速尋找好的解，分布式計(jì)算避免早熟收斂，并且貪婪式啟發(fā)搜索有助于在搜索過程早期就尋求到可行解。還有很多有益工作要做，尤其是提高計(jì)算效率。蟻群搜索法蟻群搜索法粒子群算法112 2( 1 )()()( ()()()( ()()ijijjijijjgjijv tw v t cr t p t x tcr t p t x t ( 1)()( 1)ijijijx tx tv