社群網路上之專案團隊籌組問題

Abstract

近來，有許多研究探討如何透過社群網路(social network)中的成員關係找出特定領域的專家群，並推薦於專案團隊之籌組作業。傳統的專案團隊籌組問題主要研究如何在給定專案任務下，於一群具有多項技能的群體以及由群體所組成的社群網路中篩選滿足專案任務的需求和符合限制的個體群。一群具有多項技能的群體以及由群體所組成的社群關係網路，其群體之間的關係可為彼此間的溝通成本和擁有相同的嗜好等建立。當社群網路的規模尚小時(n=50以內)，可透過簡單的直覺式經驗法則(Heuristic)來找到符合專案任務需求的個體；當社群網路規模擴增時(n=100以上)，則利用巨集式啟發法(meta-heuristic)能在短時間內能找到近似於最佳解的答案。 因此，如何在滿足短時間和高品質解為前提下，希望找出來的各體群達成總通訊成本(communication cost)最小化將是本論文探討的主題。本論文提出一個改良式的群蟻最佳化演算法(Ants Colony Optimization)，導入探索(exploration)和開發(exploitation)兩大策略並修改群蟻最佳化演算法內的狀態轉移機率和費洛蒙更新法則來求解。此外，本論文亦提出五個效能較好的直覺式經驗法則探討，並分析採用不同經驗法則所求出的初始解對最小總通訊成本的影響程度。透過計算實驗，我們比較群蟻最佳化演算法和一般的直覺式經驗法則的決策品質和相對改善幅度。實驗數據顯示，於網路規模大時巨集式啟發法的演算法找到解的品質明顯優於一般直覺式經驗法。

Since the past few years, the issue concerning how to identify experts in special fields through the process of team formation on social networks has been drawing considerable attention. Traditional studies on team formation mainly focus on satisfaction of the task requirement. This thesis considers a new setting. Given the skills required by a task and a social network, in which each individual (expert) is equipped with various skills, we want to identify a subset of the experts whose skills fulfill the task’s requirement and the overall communication cost among the selected experts is minimized. The problem is NP-hard in the aspect of computational complexity. When the scale of social network is small, simple heuristics can solve the problem to optimality. However, when the scale becomes large, say over one hundred people, the running time required to produce optimal solutions will be exceedingly high. Therefore, we instead design simple heuristics and a meta-heuristic to find approximate solutions in an acceptable time. We design five heuristics that can produce solutions in a timely manner. An Ant Colony Optimization (ACO) algorithm equipped with specific features, including a mixed strategy of exploitation and exploration, state transition rule, and pheromone updating rule, is designed to solve the team formation problem. Computational experiments show that the tailor-designed ACO algorithm can deliver solutions of good qualities.