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

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

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

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

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