999精品在线视频,手机成人午夜在线视频,久久不卡国产精品无码,中日无码在线观看,成人av手机在线观看,日韩精品亚洲一区中文字幕,亚洲av无码人妻,四虎国产在线观看 ?

用離散粒子群優化算法求解WTA問題

2011-03-12 09:06:36曲在濱劉彥君徐曉飛
哈爾濱工業大學學報 2011年3期
關鍵詞:分配優化

曲在濱,劉彥君,徐曉飛

(1.哈爾濱工業大學計算機科學與技術學院,150001哈爾濱,zbqu@hotmail.com; 2.哈爾濱理工大學計算機科學與技術學院,150080哈爾濱)

武器-目標分配(Weapon-target Assignment,WTA)問題是現代戰爭中一個十分重要的問題,其解空間隨武器種類數和目標總數的增加而呈指數級的增加,使其成為一個多參數、多約束NP完全問題[1-2].對于WTA問題,國內外主流的求解方法多采用諸如神經網絡、遺傳算法、模擬退火算法和蟻群優化等求次優解方法,但它們的求解效率都還不是十分令人滿意,所以探索有效的求解方法解決WTA問題仍然十分重要.

目前,關于單一兵器火力分配問題的文獻已比較多,然而由于在現代作戰中,經常是多種類型的兵器聯合作戰,故需對多種不同類型的兵器的武器-目標分配問題進行探討.文獻[3-6]雖然解決的是多種武器類型的火力分配問題,但所建立模型還是一種簡化模型,在實際使用中一般需添加額外約束條件,如對各目標分配的武器數目限制等.本文針對多類型兵器的火力分配問題給出更實用的數學模型,并將粒子群算法求解問題的思路應用于此問題,用實例驗證了方法的可行性及有效性.

1 問題的描述

具體問題可描述為:設有n個目標;m種類型武器;Vj為目標j的威脅度;Wi為可分配給目標的i類型武器數量;pij為i類型的一個武器對目標j的殺傷概率;xij為給目標j分配i類型武器的數量,目標j最多可分配武器數量為Nj.WTA問題是要確定分配給各目標的各類武器數量以使所有目標的總期望生存值最小,這個問題可形式化為

xij≥0且為整數,i=1,2,…,m,j=1,2,…,n.式中qij=1-pij,即目標j受到一發i類型武器打擊的生存概率.

2 粒子群優化算法

粒子群優化Particle Swarm Optimization(PSO)算法是由Kennedy等[7]在1995年提出的,此算法受鳥群覓食行為的啟發,并用于解決優化問題.同遺傳算法相比,PSO算法不但具有遺傳算法的全局尋優能力,還具有較強的局部尋優能力.

算法將每個個體看作是在n維搜索空間中的一個沒有重量和體積的粒子,并在搜索空間中以一定的速度飛行.每個粒子的飛行速度根據其本身的飛行經驗和群體的飛行經驗不斷調整.每個粒子代表解空間的一個候選解,解的優劣程度由適應函數決定,而適應函數根據優化目標定義. PSO隨機初始化一群粒子,其中第i個粒子在n維解空間的位置為xi=(xi1,xi2,…,xin).粒子通過在每一次迭代中動態跟蹤2個極值來更新其速度和位置為:

1)粒子本身從初始到當前迭代搜索產生的最優解:個體極值pi=(pi1,pi2,…,pin);

2)整個粒子種群目前的最優解:全局極值pg=(pg1,pg2,…,pgn).

如果第i個粒子的速度表示為vi=(vi1,vi2,…,vin),粒子根據式(1),式(2)來動態調節自己的“飛行”,得到搜索問題的最優解為

式中:t為迭代次數;c1,c2分別為正常數,稱為學習因子,一般有c1=c2=2;r1,r2分別為(0,1)之間的隨機數;ω為慣性因子.

3 離散PSO算法求解WTA問題

3.1 約束處理方法

WTA問題的解可表示為一個矩陣 X= (xij)m×n,其中xij為第i類武器分配給第j個目標的數目.在這里,每個粒子的位置便對應著武器的一種分配方案.對粒子群迭代中產生的不可行解采用修正結果值方案的方法進行修正,使其在可行解空間范圍內搜索.具體實現時利用一個可行性函數檢查新產生的解是否滿足所有約束.當不滿足時,采用啟發式策略進行調節.調節策略為:

1)如果分配方案中某一目標的武器分配總數超過約束限制,則取消對此目標殺傷概率最小的超出數目的武器分配;如果此種武器分配數少于超出數目,則需取消此種武器的全部分配.重復步驟1),直到各目標滿足各自的武器分配總數約束.

2)如果分配方案中某種武器的分配不滿足約束,則在已分配這種武器的目標中選擇“威脅度與此種武器對此目標殺傷概率之和”最小的目標,取消超出單位數的武器分配;如果超出單位數大于分給此目標的武器數,則余下部分再從占用此種武器且滿足選擇準則的目標中取消分配.重復步驟2),直到各種武器分配滿足約束為止.

本啟發式策略運用了貪心思想,盡可能使所做調節有利于提高武器對目標打擊的有效性,從而加速找到最優或次優的分配方案.

3.2 離散PSO算法實現

本文對粒子群算法中的速度和位置進行了重新定義.對速度進行的重新定義為

式中:r1[Plbest(t)-Xi(t)]為第i個粒子的位置Xi的任一列以概率r1與其個體極值Plbest(t)的對應列做減法運算,未做減法運算的列一律清零; r2[Pgbest(t)-Xi(t)]為第i個粒子的位置Xi的任一列以概率r2與全局極值Pgbest(t)的對應列做減法運算,未做減法運算的列一律清零;⊕為對作為操作數的2個矩陣產生1個新的矩陣,當2個操作數矩陣的對應列所有元素均為0,則結果矩陣的相應列也為全0;如果只有一列不全為0,則此列為結果矩陣的對應列;否則任選其中一列為結果矩陣的對應列.

上述定義解決了速度難于表示問題,而進行位置的更新為

式中:Xi'(t)為將Xi(t)隨機選擇一行根據相應類型武器數目對各目標產生隨機分配而其余各行保持不變的結果,而“+”運算則為2個矩陣對應元素相加.

求解WTA問題的離散PSO算法(DPSOWTA)描述為:

1)初始化粒子群,即隨機設定各粒子的初始位置X和速度V;

2)計算每個粒子的個體適應度值(即目標函數值);

3)將每個粒子的適應度值與個體極值Plbest比較,若更好,則更新Plbest;

4)將每個粒子的適應度值與全局極值Pgbest比較,若更好,則更新Pgbest;

5)根據式(3)和式(4)更新粒子的速度和位置,并使用啟發式策略調整新位置;

6)如未達到最大的迭代次數,則返回步驟2);否則結束.

算法在對每一粒子初始化時根據各類武器的數目隨機產生分配方案,且使其滿足各約束條件.

4 算法測試

假設有6個目標,T1,T2,…,T6,各目標的威脅度如表1所示.5種武器:W1,W2,W3,W4,W5的數目為{4,3,3,2,2},對各目標最多可使用武器數目為{1,1,2,1,1,2},各類武器對各目標的單發殺傷概率如表2所示.

表1 各目標的威脅性系數

表2 武器對目標的殺傷概率表

算法具體實現時,為避免陷入局部最優,若全局極值在進化一定代數后保持不變,則只保留最優粒子,其他粒子全部重新生成.本例中的粒子數取為30,最大迭代數為100.在P4 1.7 G/512 M微機上重復執行算法50次得出的最優方案的適應度值情況如表3所示,最優分配方案的適應度函數值為0.634,與枚舉算法所得分配方案的適應度函數值相同.

表3 最優方案的適應值情況

進化過程中的適應度函數值(平均值)變化情況如圖1所示,圖1中同時也給出與遺傳算法(GA)的對比.對于此例,采用枚舉算法求解大約需1 142 s,而提出的離散粒子群算法迭代100代所需平均時間為156.9 ms,所得最佳方案的適應度平均值為0.732,與最優值相差0.098;對遺傳算法進行同樣次數獨立實驗,每次迭代100代所需平均時間為217.3 ms,所得最佳方案的適應度平均值為1.061,與最優值相差0.427,可明顯看出離散PSO算法大大優于遺傳算法,求解精度也明顯高于文獻[8]提出的粒子群優化算法.

圖1 適應度函數值(平均值)變化情況

經過對大量實例的計算發現,隨著武器和目標數的增加,所提出離散粒子群算法對遺傳算法的優勢也越發明顯.圖2給出當目標數為15,武器種類數為5,且每類武器數為(4,6,5,5,4)時2種算法執行時的最佳適應度值隨時間變化情況,

此例分配方案的適應度最優值為1.404.總而言之,使用本文提出的離散粒子群優化算法能快速給出武器-目標分配問題的最優或近優解,驗證了算法的有效性.

圖2 適應度函數值(平均值)隨時間變化情況

5 結論

1)采用啟發式策略對粒子群迭代過程產生的不可行解進行調節,使算法在可行解空間范圍內搜索.調節利用了貪心思想,使其有利于提高武器對目標打擊的有效性.

2)對粒子群算法中的速度和位置進行了重新定義,使粒子群算法這一主要用于連續函數優化的算法可以解決武器-目標分配問題這樣的約束組合優化問題,明顯提高了問題求解的速度和精度,拓展了粒子群優化算法在離散空間的應用.

3)提出的算法能快速給出武器-目標分配問題的最優或近優分配方案,為解決這一NP難點問題提出了新的解決途徑.

[1]AHUJA R K,KUMAR A,JHA K,et al.Exact and heuristic methods for the weapon target assignment problem[EB/OL].(2003-06-20)[2004-04-20]http://ssrn.com/abstract=489802.

[2]ROSENBERGER J M,HWANG H S,PALLERLA R P, et al.The generalized weapon target assignment problem[C]//Proceddings of 10thInternational Command and Control Research and Technology Symposium on The Future of C2.McLean,VA:Lockheed Martin Corporation,2005:1-13.

[3]陳紹順,王穎龍,王君.多武器系統的火力分配模型[J].火力與指揮控制,2005,30(2):45-47.

[4]鄭澤席.使用多種防空武器時目標分配的數學模型[J].系統工程與電子技術,2000,22(5):15-16.

[5]解春明,楊傳春,李德勝.地地導彈突擊目標火力分配模型[J].火力與指揮控制,2004,29(6):41-44.

[6]王瑋,程樹昌,張玉芝.基于遺傳算法的一類武器目標分配方法研究[J].系統工程與電子技術,2008,30(9):1708-1711.

[7]KENNEDY J,EBERHART R C.Particle swarm optimization[C]//Proceedings of IEEE International conference on Neural Networks.Piscataway,NJ:IEEE Service Center,1995:1942-1948.

[8]高尚,楊靜宇.武器-目標分配問題的粒子群優化算法[J].系統工程與電子技術,2005,27(7):1250-1252.

猜你喜歡
分配優化
基于可行方向法的水下機器人推力分配
超限高層建筑結構設計與優化思考
房地產導刊(2022年5期)2022-06-01 06:20:14
民用建筑防煙排煙設計優化探討
關于優化消防安全告知承諾的一些思考
一道優化題的幾何解法
由“形”啟“數”優化運算——以2021年解析幾何高考題為例
應答器THR和TFFR分配及SIL等級探討
遺產的分配
一種分配十分不均的財富
績效考核分配的實踐與思考
主站蜘蛛池模板: 中文字幕久久亚洲一区| 欧美激情福利| 国产欧美日韩另类| 国产精品九九视频| 一级片一区| 麻豆国产精品一二三在线观看| 亚洲色欲色欲www在线观看| 久久精品人人做人人爽| 欧美日韩在线成人| 制服丝袜亚洲| 无码人中文字幕| 国产成人精品免费视频大全五级| 亚洲最大情网站在线观看| 日韩久草视频| 婷婷丁香在线观看| 国产综合在线观看视频| 久久99精品国产麻豆宅宅| 99九九成人免费视频精品| 另类重口100页在线播放| 日本一区二区不卡视频| 男女猛烈无遮挡午夜视频| 97视频精品全国在线观看| 亚洲国产日韩一区| 国产va视频| 2022国产无码在线| 99久久免费精品特色大片| 国产香蕉97碰碰视频VA碰碰看| 国产精品尹人在线观看| 片在线无码观看| 天堂av综合网| 99久久免费精品特色大片| 免费不卡视频| 亚洲成人在线免费| 亚洲午夜综合网| 婷婷六月在线| 在线观看国产一区二区三区99| 91免费国产高清观看| 99re热精品视频中文字幕不卡| 91原创视频在线| 伊人蕉久影院| 在线播放91| 四虎永久在线精品国产免费| 91成人在线观看| 国产成人精品男人的天堂| 中文字幕av无码不卡免费 | 啊嗯不日本网站| 91国内视频在线观看| a免费毛片在线播放| 99性视频| 久久久亚洲色| 99在线视频网站| 亚洲第一视频免费在线| 97久久人人超碰国产精品| 中文字幕 91| 国产手机在线小视频免费观看 | 国产精品女主播| 亚洲一区二区日韩欧美gif| 91无码国产视频| 91毛片网| 日本高清成本人视频一区| 国产SUV精品一区二区6| 欧美激情伊人| 片在线无码观看| 中文字幕中文字字幕码一二区| 精品一区二区三区自慰喷水| 欧美无遮挡国产欧美另类| 第九色区aⅴ天堂久久香| 久久综合伊人77777| 国产系列在线| 成人一区专区在线观看| 无遮挡国产高潮视频免费观看| 国产精品视频a| 中美日韩在线网免费毛片视频| 亚洲91精品视频| 日本欧美一二三区色视频| 熟妇丰满人妻| 夜夜爽免费视频| 亚洲欧美在线综合一区二区三区| 99激情网| 国产精品永久免费嫩草研究院| 99999久久久久久亚洲| 香蕉久人久人青草青草|