分布式約束優(yōu)化算法若干問(wèn)題研究.pdf

1、在實(shí)際生活中，許多問(wèn)題都可以抽象成為多agent模型進(jìn)行解決，而分布式約束優(yōu)化(DCOP)算法是近年解決多agent問(wèn)題的主要算法。多agent問(wèn)題的求解具有NP難度，如何能夠快速的獲得最優(yōu)、完備的解決方案，對(duì)提高生產(chǎn)率，促進(jìn)社會(huì)的發(fā)展具有重要意義。雖然目前有很多DCOP算法，但由于大部分算法是針對(duì)問(wèn)題的特殊求解目標(biāo)提出的，而且算法的執(zhí)行策略各異，求解質(zhì)量也不盡相同，因此當(dāng)有新的實(shí)際問(wèn)題抽象成為多agent模型時(shí)，算法在選擇上就出現(xiàn)了制

2、約。其次，雖然當(dāng)前有相關(guān)研究，將主要DCOP算法進(jìn)行整合，建立了分布式約束優(yōu)化問(wèn)題解決框架(FRODO)，但該框架主要用于算法性能分析，在實(shí)際問(wèn)題應(yīng)用中的算法選擇方面存在不足，同時(shí)，由于該框架的提出時(shí)間較早，因此算法的時(shí)效性和性能兩個(gè)方面也亟待提高。
　　針對(duì)這些問(wèn)題，本文分析了FRODO框架在解決實(shí)際問(wèn)題時(shí)存在的不足。并根據(jù)分析結(jié)果，從算法的擴(kuò)展性、策略自適應(yīng)性兩方面完善了算法框架。在此基礎(chǔ)上，本文根據(jù)約束圖特征對(duì)典型算法進(jìn)行分

3、類(lèi)并給出了策略自適應(yīng)匹配算法，最后，本文設(shè)計(jì)并實(shí)現(xiàn)了支持策略自適應(yīng)的DCOP算法平臺(tái)APLODO，針對(duì)平臺(tái)測(cè)試過(guò)程中發(fā)現(xiàn)的MULBS算法的不足，對(duì)其進(jìn)行了改進(jìn)。
　　在具體實(shí)現(xiàn)中，本文首先對(duì)實(shí)際問(wèn)題在FRODO框架中的解決過(guò)程進(jìn)行了分析，分析表明，一個(gè)支持策略自適應(yīng)的DCOP算法框架，應(yīng)具備良好的算法可擴(kuò)展性以及策略自適應(yīng)性，針對(duì)這兩個(gè)特性，一方面，本文對(duì)DCOP算法的執(zhí)行過(guò)程進(jìn)行模塊劃分，并以MULBS算法為例闡述了該模式下的算

4、法實(shí)現(xiàn)方式。另一方面，本文根據(jù)算法搜索策略、解的完整度、異步性、時(shí)效性選取了5種典型算法，在完善的評(píng)價(jià)指標(biāo)體系下，從約束圖密度、節(jié)點(diǎn)數(shù)量和取值空間大小三個(gè)特征入手，對(duì)算法進(jìn)行性能的分析、分類(lèi)。然后，本文結(jié)合實(shí)際問(wèn)題求解目標(biāo)以及算法分類(lèi)結(jié)果，提出策略自適應(yīng)匹配算法，該算法的核心是算法的打分機(jī)制，其次，本文在FRODO框架基礎(chǔ)上設(shè)計(jì)并實(shí)現(xiàn)了APLODO平臺(tái)，最后通過(guò)對(duì)平臺(tái)的算法測(cè)試，發(fā)現(xiàn)MULBS算法在沖突解決機(jī)制和算法并行性方面存在缺陷，