系統識別號 | U0002-0607202118445600 |
---|---|
DOI | 10.6846/TKU.2021.00158 |
論文名稱(中文) | 以量子遺傳演算法與深度學習為基礎之自動化協商對手喜好預測 |
論文名稱(英文) | Opponent Preference Prediction In Automated Negotiation Based On Quantum-Inspired Genetic Algorithms And Deep Learning |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 資訊管理學系碩士班 |
系所名稱(英文) | Department of Information Management |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 109 |
學期 | 2 |
出版年 | 110 |
研究生(中文) | 徐得芳 |
研究生(英文) | Te-Fang Hsu |
學號 | 609630305 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2021-05-29 |
論文頁數 | 48頁 |
口試委員 |
指導教授
-
張昭憲
委員 - 壽大衛 委員 - 魏世杰 委員 - 張昭憲 |
關鍵字(中) |
協商對手喜好預測 量子遺傳演算法 基因演算法 粒子群演算法 LSTM 電子化協商 電子商務 |
關鍵字(英) |
preference prediction in negotiation quantum-inspired genetic algorithms genetic algorithms particle swarm optimization lstm electronic negotiation e-commerce |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
電子化協商(e-Negotation)可透過網路讓協商者免除空間及時間的限制,大幅節省協商成本。此外,透過協商支援系統,可協助協商者以更理性的態度快速做出決策,大幅降低過程中的誤判。然而,面對日益複雜的交易環境,協商者仍需親自參與許多流程,使其便利性大打折扣。有鑑於此,學者便開始發展各種有效的自動化協商機制。前人研究雖已提出許多可行的做法,但在機器學習領域日新月異的年代,實有必要重新評估現有架構,發展更準確、更符合實際需求之協商預測方法。為此,本研究以Faratin等人(1998)提出之協商模型為基礎,透過量子遺傳演算法與深度學習方法,發展有效的協商對手喜好預測方法。首先,我們針對協商中各種參數進行基因編碼,以表示雙方的喜好。接下來,運用量子遺傳演算法找尋對手喜好可能對應之基因組合,並透過量子旋轉閘角度的調整,產生更合適的預測結果。其次,我們也以雙方之出價序列為輸入,設計與時序相關之LSTM無模型對手喜好預測方法,並與前述方法進行比較。為驗證提出方法之有效性,本研究透過模擬協商進行效能評估。實驗結果顯示,與傳統的基因演算法與粒子群演算法比較,無論在整合式或分配式協商中,本研究使用之預測方法均可獲得較佳之總效用。然而,在使用LSTM進行無模型的預測時,並無法獲得合理的預測結果。綜合上述結果,我們發現以喜好模型為基礎之量子遺傳預測方法,確實有助於進一步提升雙方總效用,產生雙贏的協商結果。 |
英文摘要 |
Electronic negotiation (e-negotiation) allows traders to conduct negotiations through the Internet without considering the time-zone and physical location, that will greatly reduce the negotiation costs. In addition, the negotiation support system can help negotiators make quick decisions with a more rational attitude that would reduce misjudgments in negotiation. However, to face an increasingly complex trading environment, negotiators still need full participation that could degrade the convenience of e-negotiation seriously. In the light of this, scholars have begun to develop effective automated negotiation mechanisms. Although previous studies have proposed many feasible methods, with the quick development of machine learning, it is still necessary to re-evaluate the existing architecture and develop more suitable negotiate support methods. For this reason, this research is based on the negotiation model proposed by Faratin et al. (1998), developing an effective method for predicting the preferences of negotiating opponent through Quantum-Inspired Genetic Algorithms and Deep Learning. First, each gene is encoded by various parameters in the negotiation to express the preferences of both parties. Secondly, the quantum-inspired genetic algorithms is used to find the genetic combination corresponding to the opponent's preferences, through the adjustment of the angle of the quantum rotation gate. Also, to compare with the aforementioned methods, we take the bid sequences of both parties as input and design a time-related of LSTM for model-free opponent preference prediction. To verify the effectiveness of the proposed method, this study conducts simulated negotiation to compare the obtained results. Comparing with traditional genetic algorithm and particle swarm optimization, the proposed method can achieve better overall utility no matter in integrated or distributed negotiation. However, when LSTM is used for model-free prediction, reasonable prediction results cannot be obtained. In summary, we found that the preference prediction methods based on quantum-inspired genetic algorithm does help to further enhance the total utility of both parties and reach a win-win negotiation result. |
第三語言摘要 | |
論文目次 |
目錄 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機 2 1.3 研究目的 3 1.4 論文架構 4 第二章 相關理論與技術 5 2.1協商效用模型 5 2.2協商戰術 (Negotiation Tactics) 8 2.3協商類型 10 2.4基因演算法 10 2.5粒子群演算法 12 2.6量子遺傳演算法 13 2.7長短期記憶模型(Long Short-term Memory, LSTM) 14 第三章 自動化協商之對手喜好預測 16 3.1協商對手喜好預測之重要性 16 3.2以喜好模型為基礎: 有模型預測 17 3.2.1 基因編碼 17 3.2.2 以量子遺傳演算法進行對手喜好預測 18 3.3以LSTM進行對手喜好預測: 無模型預測 21 第四章 實驗結果與分析 24 4.1實驗設計 24 4.1.1 協商實驗之各項參數設定 24 4.1.2 基因編碼 25 4.1.3 協商結果之評量指標 26 4.1.4 系統運作流程 26 4.2 使用不同量子旋轉閘之旋轉角度預測對手喜好 28 4.3 以粒子群演算法、基因演算法與量子遺傳演算法預測對手喜好 32 4.4 各種預測方法最佳解基因編碼之比較 36 4.5 不同議題數在無預測及有預測協商之執行速度比較 38 4.6 使用LSTM進行無模型之喜好預測 40 五 結論與未來工作 42 參考文獻 44 附錄A: 雙議題協商預測結果 47 圖目錄 圖 1: 效用函數圖 6 圖 2: 基因演算法流程圖(蘇木春,2004) 12 圖 3: LSTM之隱藏層元件(圖片來源: GREFF 等人, 2016) 15 圖 4: 協商動線圖 17 圖 5: 以量子概念產生基因池之物種示意圖 19 圖 6: 量子基因通過量子旋轉閘示意圖 21 圖 7: 協商者出價資料訓練示意圖 22 圖 8: 模型架構設計圖 23 圖 9: 模型架構圖(以三議題協商為例) 23 圖 10: 系統流程圖-有模型預測(黃淳韋,2010) 27 圖 11: 系統流程圖-無模型預測 28 圖 12: 分配式協商中不同旋轉角度對應雙方平均效用和(不考慮破局) 29 圖 13: 整合式協商中不同旋轉角度對應雙方平均效用和(不考慮破局) 30 圖 14: 分配式協商中不同旋轉角度對應雙方平均效用和(考慮破局) 31 圖 15: 整合式協商中不同旋轉角度對應雙方平均效用和(考慮破局) 32 圖 16: 不同喜好預測方法之協商每回合執行時間折線圖 39 表目錄 表 1: 效用函數類型,資料來源: MUMPOWER (1991) 6 表 2: 協商範例表(協商者A與B在各回合的提案) 7 表 3: 本研究之基因編碼表 18 表 4: 量子旋轉閘旋轉角度調整表 (資料來源: HAN AND KIM 2002) 20 表 5: 協商實驗之各項參數設定 25 表 6: 預測對手喜好時,需編碼之變數(喜好模型中之參數) 25 表 7: 根據表6中的變數,實際編碼後之基因長度(格式: BIT數(種類)) 26 表 8: 應用不同量子旋轉閘旋轉角度預測對手喜好之比較表(不考量破局) 29 表 9: 應用不同量子旋轉閘旋轉角度預測對手喜好之比較表(考量破局) 31 表 10: 應用粒子群演算法(PSO)、基因演算法(GA)與量子遺傳演算法(QGA)預測對手喜好之比較表(不考量破局情形) 35 表 11: 應用粒子群演算法(PSO)、基因演算法(GA)與量子遺傳演算法(QGA)預測對手喜好之比較表(考量破局情形) 36 表 12: 最佳解基因編碼 37 表 13: 最佳解基因編碼相似度比較 37 表 14: 不同喜好預測方法之協商每回合執行時間 39 表 15: 模型訓練資料集 40 表 16: 應用LSTM預測對手出價之協商結果比較表(不考量破局情形) 41 表 17: 應用LSTM預測對手出價之協商結果比較表(考量破局情形) 41 |
參考文獻 |
參考文獻 [1] 蘇木春,機器學習:類神經網路.模糊系統以及基因演算法則。全華科技圖 書公司,民國九十三年。 [2] 楊雅卿 (2006)。電子商務架構下之協商對手喜好預測。淡江大學資訊管理學系碩士論文。 [3] 杨淑媛, 焦李成, and 刘芳. "量子进化算法." 工程數學學報 23.2 (2006): 235-246. [4] 黃淳韋(2010)。電子化協商架構下的對手喜好預測與策略運用方法。淡江大學資訊管理學系碩士論文。 [5] Baek, J. and Kim, C. (2007), “Learning single-issue negotiation strategies using hierarchical clustering method” Expert Systems with Applications, VOL 32, Iss 2, pp. 606-615. [6] Barbuceanu, M., & Lo, W.-K. (2000). “A Multi-Attribute Utility Theoretic Negotiation Architecture for Electronic Commerce,” Proceedings of the Fourth International Conference on Autonomous Agents, 239-246. [7] Blecherman, B. (1999). “Adopting Automated Negotiation,” Technology in Society 21, 167-174. [8] Carbonneau, R., Kersten, G., and Vahidov, R. (2008), “Predicting opponent’s moves in electronic negotiations using neural networks” Expert Systems with Applications, VOL 34, Iss 2, pp. 1266-1273. [9] Faratin, P., Sierra, C.,& Jennings, N. R. (1998). “Negotiation Decision Functions for Autonomous Agents,” Robotics and Autonomous Systems 24, 159-182. [10] Faratin, P., Sierra, C., & Jennings, N. R. (2002). “Using Similarity Criteria to Make Issue Trade-Offs in Automated Negotiation,” Artificial Intelligence 142, 205-237. [11] Greff, Klaus, et al. "LSTM: A search space odyssey." IEEE transactions on neural networks and learning systems 28.10 (2016): 2222-2232. [12] Han, Kuk-Hyun, and Jong-Hwan Kim. "Genetic quantum algorithm and its application to combinatorial optimization problem." Proceedings of the 2000 congress on evolutionary computation. CEC00 (Cat. No. 00TH8512). Vol. 2. IEEE, 2000. [13] Han, Kuk-Hyun, and Jong-Hwan Kim. "Quantum-inspired evolutionary algorithm for a class of combinatorial optimization." IEEE transactions on evolutionary computation 6.6 (2002): 580-593. [14] Hochreiter, Sepp, and Jürgen Schmidhuber. "Long short-term memory." Neural computation 9.8 (1997): 1735-1780. [15] Hou, Chongming. "Predicting agents tactics in automated negotiation." Proceedings. IEEE/WIC/ACM International Conference on Intelligent Agent Technology, 2004.(IAT 2004).. IEEE, 2004. [16] Holland, John Henry. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992. [17] Kennedy, James, and Russell Eberhart. "Particle swarm optimization." Proceedings of ICNN'95-international conference on neural networks. Vol. 4. IEEE, 1995. [18] Kennedy, James, and Russell C. Eberhart. "A discrete binary version of the particle swarm algorithm." 1997 IEEE International conference on systems, man, and cybernetics. Computational cybernetics and simulation. Vol. 5. IEEE, 1997. [19] Lim, John Lai Huat. "Multi-stage negotiation support: a conceptual framework." Information and Software Technology 41.5 (1999): 249-255. [20] Mumpower, J. L. (1991). “The Judgment Policies of Negotiators and the Structure of Negotiation Problems,” Management Science 37 (10), 1304-1324. [21] Narayanan, Ajit, and Mark Moore. "Quantum-inspired genetic algorithms." Proceedings of IEEE international conference on evolutionary computation. IEEE, 1996. [22] Rau, H., Tsai, M., Chen, C., and Shiang, W. (2006), “Learning-based automated negotiation between shipper and forwarder” Computers & Industrial Engineering, VOL 51, Iss 3, pp. 464-481. [23] Shi, Yuhui. "Particle swarm optimization." IEEE connections 2.1 (2004): 8-13. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信