資源分配是計算科學領域研究的熱點問題之一,其應用場景包括計算資源共享、工業(yè)生產(chǎn)、邊界爭端處理等等。在已有的資源分配研究中,研究者通常會根據(jù)應用場景的不同而設定不同的資源分配目標,并設計針對性的資源分配方法。例如,在計算資源分配中,研究者會關注如何分配計算資源以高效的完成待處理的計算任務;在邊界爭端處理中,研究者通常關注如何分配資源以保證分配的公平性。隨著民主政治的發(fā)展,社會選舉已成為現(xiàn)代社會的重要組成部分。與此同時,社會選舉也逐漸成為多Agent系統(tǒng)研究領域關注的重要應用場景之一,其中Agent通常用來建模參與選舉的選民或候選人。在社會選舉中,選舉組織者(例如國家政府)通常需要建立多個投票站來方便不同選區(qū)的選民進行選舉投票。而且,選舉組織者還需要部署保護資源(如安保資源),提供選民服務資源(例如用于電子投票服務的計算資源與用于選民服務的工人資源)來保證選舉過程的高效有序進行。因為社會選舉過程與選舉結(jié)果具有廣泛的關注性與影響性,這使得社會選舉中的資源分配擁有更多元化的要求,并為資源分配研究提出了新的挑戰(zhàn)。第一,選舉組織者需要考慮如何分配保護資源來保證選舉過程的安全進行,保證選舉結(jié)果不被操...

【文章頁數(shù)】：118 頁

【學位級別】：博士

【部分圖文】：

圖2.1：選民組或候選人數(shù)

第二章基于最少資源消耗的選舉保護21二個，貪心法（Greedy），即從未被選擇的選民組中不斷貪心的選擇持有最大vi(w)的選民組添加到分配策略直到該策略能夠保證選舉結(jié)果不被操控。在本章中，整數(shù)線性規(guī)劃采用CPLEX12.5求解。在實驗中，本章隨機的生成每個候選人在每個選民組中的得....

圖2.2：候選人選票分布區(qū)間對于資源消耗的影響

東南大學博士學位論文22人在每個選民組內(nèi)的得票數(shù)的分布方差越校從圖2.2中，我們可以發(fā)現(xiàn)隨著分布區(qū)間長度B的增加，本章所提出的優(yōu)化近似算法始終擁有僅次于精確（最優(yōu)）算法的性能。而且，在資源消耗上其與精確算法之間的差距保持穩(wěn)定。這說明當候選人在每個選民組中選票分布方差增加時，本章所....

圖2.3:基于真實數(shù)據(jù)的算法性能對比

東南大學博士學位論文22人在每個選民組內(nèi)的得票數(shù)的分布方差越校從圖2.2中，我們可以發(fā)現(xiàn)隨著分布區(qū)間長度B的增加，本章所提出的優(yōu)化近似算法始終擁有僅次于精確（最優(yōu)）算法的性能。而且，在資源消耗上其與精確算法之間的差距保持穩(wěn)定。這說明當候選人在每個選民組中選票分布方差增加時，本章所....

圖3.2：不可分割資源數(shù)

洹?基于匹配的算法（MBA）：在該算法中，我們首先將可分割資源均分成n個等效用的虛擬資源。然后，我們將每個虛擬資源視為不可分并采用Bezakova和Dani[3]提出的基于匹配的方法來公平分配所有資源。最后，我們采用線性規(guī)劃的方法來優(yōu)化可分割資源的分配。我們在一個擁有IntelE....

本文編號：3948009