亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        多Agent系統(tǒng)協(xié)作求解的粒子模型方法

        2012-07-02 03:25:44趙旭寶李靜董靚瑜
        大連交通大學(xué)學(xué)報 2012年2期
        關(guān)鍵詞:分配資源方法

        趙旭寶,李靜,董靚瑜

        (大連交通大學(xué) 軟件學(xué)院,遼寧 大連 116021)*

        0 引言

        在分布式人工智能中,基于Agent結(jié)構(gòu)提供了柔性和魯棒性,適合解決動態(tài)、不確定和分布式的問題.系統(tǒng)中各Agent個體都是具有自主性的智能體,存在自己的信念、愿望、目標(biāo)等認(rèn)知屬性和承諾、義務(wù)、協(xié)作、競爭等社會屬性[1-2].系統(tǒng)中各Agent個體通過對自身知識的表示和對問題域的描述,構(gòu)成分布的、異構(gòu)的、面向特定問題的Agent求解子系統(tǒng),完成指定任務(wù)的求解.但在多Agent分布式系統(tǒng)中由于每個Agent個體所具有的知識資源和執(zhí)行能力是有限的,當(dāng)單個Agent難以獨立完成指定任務(wù),或多個Agent一起完成會產(chǎn)生更大的效益時,多個A-gent個體之間就傾向于利用協(xié)作機(jī)制進(jìn)行信息的交流、知識的共享來完成任務(wù)的協(xié)作求解.為了保證多Agent系統(tǒng)協(xié)作求解的性能,很多學(xué)者在關(guān)于多Agent系統(tǒng)協(xié)作求解模型建立和協(xié)作求解方法方面做了大量研究.文獻(xiàn)[3]提出面向共同目標(biāo)的合作求解策略,重點在于尋求系統(tǒng)的最大效益;文獻(xiàn)[4-5]提出基于彈簧網(wǎng)絡(luò)的多Agent系統(tǒng)協(xié)作求解方法,通過自組織動力學(xué)策略來實現(xiàn)Agent之間的協(xié)調(diào);文獻(xiàn)[6-7]提出基于合同網(wǎng)協(xié)議的合作求解方法,先協(xié)商結(jié)盟再規(guī)劃求解,并通過協(xié)商的方式解決沖突.

        目前多Agent分布式系統(tǒng)協(xié)作求解方法的研究基本上有兩種類型:一種類型是Agent個體各自尋求自身最大利益的方法;另一種是Agent個體共同尋求整個系統(tǒng)最大效益的方法.但前者協(xié)作求解中沒有全局的優(yōu)化目標(biāo),缺乏統(tǒng)一的全局控制策略;后者又難以描述Agent個體自變與自組織現(xiàn)象.同時,這兩種類型雖然都涉及到Agent間的協(xié)作和交互,但協(xié)作交互也僅僅是一些簡單的社會交互行為,在問題求解過程中不能及時處理環(huán)境和Agent本身的動態(tài)變化以及社會交互行為的隨機(jī)性和并發(fā)性的問題.

        為此,本文提出了一種多Agent系統(tǒng)協(xié)作求解的粒子模型方法.將系統(tǒng)協(xié)作求解轉(zhuǎn)換為多粒子共同尋優(yōu)過程,克服了Agent本身認(rèn)知屬性和社會屬性動態(tài)變化及隨機(jī)性和并發(fā)性的問題,使得Agent個體在協(xié)作求解中既獲取自身的最大利益,又促進(jìn)系統(tǒng)的總體效益.最后,引入了協(xié)作程度變化參數(shù),給出了Agent協(xié)作求解的需求強(qiáng)度計算公式和系統(tǒng)效益目標(biāo)函數(shù)及優(yōu)化算法,經(jīng)過算法迭代計算求得了協(xié)作求解的資源分配優(yōu)化解.仿真結(jié)果表明該方法具有很好的收斂性和實用性.

        1 求解粒子模型

        1.1 求解問題描述

        不失一般性,本文以多Agent分布式環(huán)境下對問題實施任務(wù)資源規(guī)劃分配的協(xié)作求解為背景,討論多Agent系統(tǒng)協(xié)作求解方法與優(yōu)化算法.設(shè)待解決的任務(wù)Agent集合和知識與執(zhí)行能力構(gòu)成的資源Agent集合分別為 Task={AgentT1,AgentT2,…, AgentTn} 和 Res = {AgentR1,AgentR2,…,AgentRm},且每個子資源AgentRi個體擁有的資源容量為mi.子資源AgentRi個體分配給子任務(wù)AgentTk個體的資源量為rik(rik≤mik),供其完成規(guī)劃的任務(wù).同時子任務(wù)AgentTk個體付給子資源AgentRi個體單位資源報酬為pik.設(shè)第k個子任務(wù)AgentTk對各種子資源Agent需求資源總量為Sk和第k個子任務(wù)AgentTk所能支付總的資源報酬代價為Pk.子任務(wù)AgentTk在執(zhí)行任務(wù)時使用何種子資源Agent取決于子任務(wù)AgentTk對子資源AgentRi的需求強(qiáng)度xik(1≤i≤m,1≤k≤n).xik表示第k個任務(wù)需要第i個資源.因此,在多Agent分布協(xié)作求解中,任務(wù)資源規(guī)劃目標(biāo)則為尋找一個優(yōu)化的任務(wù)資源規(guī)劃分配方案,在各資源用量最下的前提下,取得系統(tǒng)整體收益最大值.

        1.2 求解粒子模型

        由上述問題分析可知,單個子任務(wù)AgentTk對各子資源AgentRi的需求是關(guān)于rik,pik,xik的函數(shù),函數(shù)表示為Aik=F(rik,pik,xik).所有任務(wù)對資源需求可以表示成如下的分配矩陣T_R=[Aik]m×n(1 ≤ i≤ m,1≤ k≤ n).矩陣如下:

        在上述分配矩陣中,每個子任務(wù)AgentTk(1≤k≤n)在完成任務(wù)時,可能對每個資源Agent Ri(1≤i≤m)個體存在需求.也就是說,每個子資源AgentRi個體可能分配給不同的子任務(wù)(rikxik≤ mi(?i=1,2,…,m)).這樣當(dāng)多個子任務(wù)同時需要某資源時,就可能產(chǎn)生資源使用的沖突.為此,本文提出了資源協(xié)作求解的粒子模型.將每個子資源AgentRi個體視為不可再分的個體,稱為粒子,每個子資源粒子每次僅能分配給一個子任務(wù)粒子.這樣,當(dāng)多個子任務(wù)需要同時使用某子資源時,Agent粒子就會傾向于進(jìn)行協(xié)作求解共同完成多個子任務(wù).或當(dāng)多個子資源Agent粒子一起完成所規(guī)劃任務(wù)會更有效時,也會傾向協(xié)作求解.多Agent粒子之間是否進(jìn)行協(xié)作,取決于協(xié)作求解強(qiáng)度xik的值.

        1.3 需求強(qiáng)度的計算

        在實際應(yīng)用中,對于任務(wù)對資源需求強(qiáng)度的取值,不但要考慮Agent意愿、目標(biāo)等自身認(rèn)知屬性的變化,更要考慮復(fù)雜社會交互行為對協(xié)作求解中需求強(qiáng)度的影響.對于群體Agent協(xié)作求解過程中所涉及的社會交互行為類型大致可分為兩類:

        (1)對于子任務(wù) AgentTk,子資源 AgentRi粒子與子資源AgentRj粒子的協(xié)作交互行為ρijk;

        (2)對于子資源AgentRi,子任務(wù)AgentTk粒子與子任務(wù)AgentTj粒子之間的協(xié)作交互行為ρ'kji.

        其中,ρijk的含義為:對于子任務(wù)AgentTk,如果資源AgentRi與資源AgentRj具有相同的意愿和目標(biāo),且產(chǎn)生交互行為能加速對任務(wù)的執(zhí)行,或產(chǎn)生更多的效益,則將加強(qiáng)任務(wù) AgentTk對資源AgentRi粒子與AgentRj粒子的需求,加強(qiáng)的強(qiáng)度為ρijk.相反則消弱.

        同理,ρ'kji的含義為:對于子資源 AgentRi,如果任務(wù)AgentTk與任務(wù)AgentTj之間產(chǎn)生交互合作行為,能簡化任務(wù)執(zhí)行的復(fù)雜度,并能節(jié)約資源的消耗,則將加強(qiáng)資源AgentRi對任務(wù)AgentTk粒子與AgentTj粒子的分配.加強(qiáng)的強(qiáng)度為ρ'kji.相反則消弱.

        假定不同類型的交互行為產(chǎn)生的效果具有疊加性.因此,根據(jù)上述社會交互行為的分類,在協(xié)作求解交互過程中,任務(wù)對資源的需求強(qiáng)度可通過式(2)計算取得.

        其中,wij為關(guān)聯(lián)權(quán)值,在[0,1]之間取值.它表示協(xié)作求解中各Agent粒子間關(guān)聯(lián)程度.它隨Agent粒子的動態(tài)變化而改變.如新陳代謝、隨機(jī)故障以及協(xié)作交互的競爭、利用、欺騙等.在Agent粒子生命周期結(jié)束時wij=0.為了簡化問題求解的復(fù)雜度,本文假定交互行為對需求強(qiáng)度的加強(qiáng)與消弱程度相同,即ρijk和ρ'kji取相同的小數(shù)值.

        在式(3)中,當(dāng)計算所得需求強(qiáng)度值超過給定的某閾值μ后,使得xik=1,否則為0.構(gòu)造后,某次任務(wù)資源規(guī)劃協(xié)作求解狀態(tài)可用圖1表示.圖1中圓點表示子資源粒子對子任務(wù)粒子的分配.有向邊表示各粒子之間的協(xié)作求解過程.如有向邊 <x12,x24>表示子任務(wù)粒子T2在使用資源粒子R1時,還需要使用資源粒子R2,但R2已被T4使用.因此資源粒子R1和R2建立協(xié)作關(guān)系.在圖1中有向邊越多表明系統(tǒng)內(nèi)部協(xié)作求解規(guī)模越大.另外,如果從資源分配角度描述群體Agent粒子間的協(xié)作求解交互過程,還可以表示成有向圖,如圖2.圖2中每條邊上的權(quán)值代表系統(tǒng)消費代價.在協(xié)作求解中由于Agent粒子自身的動態(tài)變化和社會交互行為隨機(jī)性、并發(fā)性等因素的影響,使得這種協(xié)作求解是以通信開銷和資源耗費為代價.本文將第i個Agent粒子和第j個Agent粒子協(xié)作求解產(chǎn)生的資源消費代價定義為cij.在圖2中有向邊的多少也體現(xiàn)了系統(tǒng)協(xié)作求解交互程度.用變量e∈[0,1]表示系統(tǒng)協(xié)作交互程度.

        圖1 Agent協(xié)作求解模型

        圖2 資源Agent協(xié)作求解過程

        2 求解數(shù)學(xué)模型

        λ1,λ2為(0,1)的隨機(jī)數(shù)

        3 協(xié)作求解的粒子群算法

        在多Agent系統(tǒng)分布式協(xié)作求解的粒子模型中,每個規(guī)劃解xik都是一個0或1值(1≤i≤m,1≤k≤n).顯然任務(wù)資源協(xié)作求解問題屬于組合優(yōu)化問題.因此,本文構(gòu)造了適合求解的改進(jìn)粒子群優(yōu)化算法[8].在每次求解中把子資源數(shù)粒子數(shù)m定義為算法中每次迭代求解的空間維數(shù).即每一維空間代表一個資源粒子對任務(wù)粒子的分配情況,用一個整數(shù)來表示.如果某資源粒子在求解中沒有被任何子任務(wù)所使用,則表示為0.如Pkm代表算法中第k次求解的第m維空間;Pkm=n-1表示算法中第k次求解中第m個資源粒子分配給第n-1個子任務(wù)使用.

        在此粒子群優(yōu)化算法中,采用了懲罰函數(shù)法[9]來處理了具有約束的優(yōu)化問題,即只要是非可行解就直接丟棄.轉(zhuǎn)化后的目標(biāo)適應(yīng)值計算公式可表示為式(8).

        采用這種適應(yīng)值計算方法,對式(4)經(jīng)過多次優(yōu)化迭代計算,即可求得其系統(tǒng)消費代價最小優(yōu)化解.

        協(xié)作求解的粒子群算法如下:

        (1)隨機(jī)初始化粒子種群:粒子群位置X、速度V、種群規(guī)模N、學(xué)習(xí)因子C1和C2、慣性因子w和最大迭代次數(shù)Max_Len以及系統(tǒng)參數(shù)變量pik,rik,cij值.

        (2)利用給定的初始位置值,初始化個體最優(yōu)位置Pi解和全局最優(yōu)位置Pg解.并根據(jù)各個Agent自治性和社會交互性,利用式(2)(3)計算需求強(qiáng)度參數(shù)xik.

        (3)While(k< =Max_Len&& φ <0.0001)//φ為優(yōu)化達(dá)到的精度;

        For i=1∶N

        For j=1∶m

        Change(X,V)//修改每個解的位置X和速度V.End For

        (4)calculation(i);//通過式(8),計算第i次迭代適應(yīng)值.

        localbest(i);//將第i次計算解與所經(jīng)歷過的當(dāng)前最好位置解Pi進(jìn)行比較,若較好,則將其作為當(dāng)前解的最好位置解;

        End For

        globalbest();//對每次求解,將其Pi與全局所經(jīng)歷的最好位置解進(jìn)行比較,求出全局極值Pg.

        EndWhile

        4 仿真實例

        4.1 仿真實例參數(shù)設(shè)置

        在仿真實驗中,考慮到每個子資源Agent和子任務(wù)Agent有不同的優(yōu)先級、自治度、交互性等復(fù)雜的行為,在仿真實驗中隨機(jī)生成了相關(guān)系統(tǒng)參數(shù).仿真程序中各個參數(shù)和變量分別設(shè)置如下:每次迭代中搜索空間的維數(shù)為資源數(shù)m;加速因子c1和c2設(shè)置為2.慣性權(quán)w根據(jù)經(jīng)驗值設(shè)為w=0.9 -count*0.5/(Max_Len -1),count代表當(dāng)前第count個粒子.種群位置的變化范圍根據(jù)所要研究的問題設(shè)置為[1,N],粒子速度的變化范圍設(shè)定為[1,N];最大迭代次數(shù)Max_Len取值為500;其他參數(shù)設(shè)置為如下隨機(jī)值:wij=[0,1];λ1= [0.01,0.1];λ2= [0.1,0.2];mi= [50,100];pik= [2,10];rik= [1,5];cij= [5,10];Sk= [100,200];Pk= [100,200].

        4.2 仿真結(jié)果與收斂性分析

        算法中的全局最優(yōu)適應(yīng)值變化反應(yīng)了協(xié)作求解的尋優(yōu)過程.種群根據(jù)自身經(jīng)驗和全局經(jīng)驗,不斷調(diào)整單個解的位置,最后通過迭代搜索到全局最優(yōu)解.由于本文把每個解的搜索空間定義為資源數(shù).所以每個全局最優(yōu)適應(yīng)值就代表了任務(wù)資源的一次規(guī)劃分配方案.在系統(tǒng)協(xié)作求解中,由于子任務(wù)數(shù)和子資源數(shù)是不固定的,并且協(xié)作求解的程度e也處于動態(tài)變化之中.因此,為了全面考察算法的有效性.本文針對不同的子任務(wù)、子資源和不同e值組合進(jìn)行實驗分析.如圖3,4所示.

        圖3 給出了在 (m,n)=(12,10),e=0.3,0.5,0.8條件下全局最優(yōu)適應(yīng)值Pg的變化過程.從圖3可以看出,當(dāng)資源粒子數(shù)和任務(wù)粒子數(shù)相同,協(xié)作求解程度e不同時,全局最優(yōu)適應(yīng)值差別很大,由17.1變化到41.2,而收斂速度基本相同.這是因為隨著e的增加,系統(tǒng)協(xié)作求解的資源消費不斷增加,導(dǎo)致系統(tǒng)總消費不斷增大.但由于資源數(shù)和任務(wù)數(shù)相同,每個粒子的搜索空間維數(shù)相同.因此算法的收斂速度基本相同.這也說明了該算法的收斂速度與協(xié)作求解程度e無關(guān).當(dāng)資源數(shù)和任務(wù)數(shù)不同,協(xié)作求解程度相同時.全局最優(yōu)適應(yīng)值雖變化很大,但收斂速度隨資源粒子數(shù)的增加明顯變慢.這是由于資源數(shù)的增加導(dǎo)致粒子搜索的空間變大,迭代速度就會變慢時間變長.如圖4所示.在圖4雖然全局最優(yōu)適應(yīng)值變化速度不同,但最終都趨于平穩(wěn)狀態(tài).表明該方法具有良好的收斂性.同時,仿真結(jié)果也驗證了該方法適合不同協(xié)作條件下各種任務(wù)資源規(guī)劃分配求解.

        圖3 全局最優(yōu)適應(yīng)值變化((m,n)=(12,10))

        圖4 全局最優(yōu)適應(yīng)值變化(e=0.2)

        仿真計算過程中,對于不同的資源粒子數(shù)、任務(wù)粒子數(shù)和不同的e值.在run_time=30條件下,求得的全局最優(yōu)適應(yīng)平均值和標(biāo)準(zhǔn)方差值如附表所示.

        在附表中全局最優(yōu)適應(yīng)值的標(biāo)準(zhǔn)均方差的變化范圍為0.22~0.42.說明了該算法具有良好的收斂性和有效性.仿真結(jié)果也驗證了該方法適合不同協(xié)作條件下各種任務(wù)資源規(guī)劃分配求解,該方法具有一定的通用性和有效性.

        附表 任務(wù)資源規(guī)劃分配結(jié)果表

        5 結(jié)論

        多Agent分布式系統(tǒng)協(xié)作求解比較復(fù)雜,需要考慮Agent本身的自治與交互行為動態(tài)性和隨機(jī)性、復(fù)雜性等問題.本文針對分布式環(huán)境下任務(wù)資源協(xié)作規(guī)劃分配問題,提出了一種多Agent分布式系統(tǒng)協(xié)作求解粒子模型方法,通過討論多A-gent系統(tǒng)分布協(xié)作求解和粒子協(xié)作之間的關(guān)系,將協(xié)作求解問題轉(zhuǎn)化為多個粒子共同尋優(yōu)的過程,并構(gòu)造了適合求解該方法的粒子群算法.在算法迭代過程中,盡管全局最優(yōu)適應(yīng)值收斂的速度不同,但都收斂達(dá)到平穩(wěn)狀態(tài),表明該算法是收斂的.仿真實驗結(jié)果表明在該方法中資源數(shù)的多少決定了算法的搜索空間,影響了收斂速度的快慢,但收斂速率與協(xié)作求解程度無關(guān).仿真實驗結(jié)果也驗證了該模型方法即能克服了環(huán)境和Agent本身的動態(tài)變化,又能處理社會交互行為變化對系統(tǒng)協(xié)作求解的影響,能夠很好地解決各種復(fù)雜的任務(wù)資源規(guī)劃問題,具有很好的有效性和通用性.

        [1]張新良,石純一.多Agent合作求解[J].計算機(jī)科學(xué),2003,30(8):100-103.

        [2]李英.多Agent系統(tǒng)及其在預(yù)測與智能交通系統(tǒng)的應(yīng)用[M].上海:華東理工大學(xué)出版社,2004.

        [3]WOOLDRIDGE M,JENNINGS NR.The cooperative problem-solving process[J].Journal of Logic Computation,1999,9(4):563-592.

        [4]SHUAI Dianxun,F(xiàn)ENG Xiang.Distributed problem solving in multi-agent system:A spring net approach[J].IEEE Intelligent System,2005,20(4):66-74.

        [5]帥典勛,王亮.一種新的基于復(fù)合彈簧網(wǎng)絡(luò)的多A-gent系統(tǒng)分布式問題求解方法[J].計算機(jī)學(xué)報,2002,25(8):853-859.

        [6]陶海軍,王亞東,郭茂祖,等.基于熟人聯(lián)盟及擴(kuò)充合同網(wǎng)協(xié)議的多智能體協(xié)商模型[J].計算機(jī)研究與發(fā)展,2006,43(7):1155-1160.

        [7]陳宇,陳新,陳新度,等.基于設(shè)備整體效能和多Agent的預(yù)測-反應(yīng)式調(diào)度[J].計算機(jī)集成制造系統(tǒng),2009,15(8):1599-1605.

        [8]謝曉鋒,張文俊,楊之廉.微粒群算法綜述[J].控制與決策,2003,18(2):129-134.

        [9]徐剛,于泳波.基于改進(jìn)的微粒子算法求解0/1背包問題[J].齊齊哈爾大學(xué)學(xué)報,2007,23(1):71-74.

        猜你喜歡
        分配資源方法
        基礎(chǔ)教育資源展示
        一樣的資源,不一樣的收獲
        應(yīng)答器THR和TFFR分配及SIL等級探討
        遺產(chǎn)的分配
        一種分配十分不均的財富
        資源回收
        績效考核分配的實踐與思考
        資源再生 歡迎訂閱
        資源再生(2017年3期)2017-06-01 12:20:59
        可能是方法不對
        用對方法才能瘦
        Coco薇(2016年2期)2016-03-22 02:42:52
        人人人妻人人人妻人人人| 亚洲男人在线无码视频| 一区二区三区视频免费观看在线| 久久久精品人妻一区二区三区妖精| 亚洲欧美乱综合图片区小说区| 亚洲精品久久久久高潮| 级毛片无码av| 内射爆草少妇精品视频| 永久免费人禽av在线观看| 人禽无码视频在线观看| 亚欧免费无码AⅤ在线观看| 91九色播放在线观看| 亚洲av无码专区在线观看成人| 久久精品夜夜夜夜夜久久| 最新永久免费AV网站| 手机在线播放av网址| 手机看片久久国产免费| 欧美在线专区| 91蜜桃精品一区二区三区毛片| 国产自拍精品一区在线观看| 久久久久女人精品毛片| 亚洲国产成人久久综合一区77| 麻豆三级视频网站在线观看| 国产精品国产亚洲精品看不卡| 国自产偷精品不卡在线| 国产精品18久久久久久首页| 永久中文字幕av在线免费| 四川丰满妇女毛片四川话| 亚洲图区欧美| 亚洲综合网中文字幕在线| 狠狠cao日日橹夜夜十橹| 中文字幕无码不卡一区二区三区| 久久久亚洲精品蜜桃臀| 成人做爰黄片视频蘑菇视频| 亚洲国产精品无码久久98| 国产乱淫视频| 精品女同一区二区三区亚洲| 在线观看特色大片免费视频| 学生妹亚洲一区二区| 亚洲视频一区二区久久久| 午夜视频在线观看视频在线播放 |