Classification-based self-adaptive differential evolution and its application in multi-lateral multi-issue negotiation

Frontiers of Computer Science in China - Tập 6 - Trang 442-461 - 2012
Xiaojun Bi1, Jing Xiao1,2
1School of Information and Communication Engineering, Harbin Engineering University, Harbin, China
2School of Information Engineering, Liaoning Provincial College of Communications, Shenyang, China

Tóm tắt

Multi-lateral multi-issue negotiations are the most complex realistic negotiation problems. Automated approaches have proven particularly promising for complex negotiations and previous research indicates evolutionary computation could be useful for such complex systems. To improve the efficiency of realistic multi-lateral multi-issue negotiations and avoid the requirement of complete information about negotiators, a novel negotiation model based on an improved evolutionary algorithm p-ADE is proposed. The new model includes a new multi-agent negotiation protocol and strategy which utilize p-ADE to improve the negotiation efficiency by generating more acceptable solutions with stronger suitability for all the participants. Where p-ADE is improved based on the well-known differential evolution (DE), in which a new classification-based mutation strategy DE/rand-to-best/pbest as well as a dynamic self-adaptive parameter setting strategy are proposed. Experimental results confirm the superiority of p-ADE over several state-of-the-art evolutionary optimizers. In addition, the p-ADE based multiagent negotiation model shows good performance in solving realistic multi-lateral multi-issue negotiations.

Tài liệu tham khảo

Kleindorfer P R, Kunreuther H C, Schoemaker P J H. Decision Sciences: An Integrative Perspective. Cambridge: Cambridge University Press, 1993 Krovi R, Graesser A, Pracht W. Agent behaviors in virtual negotiation environments. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 1999, 29(1): 15–25 Lomuscio A R, Wooldridge M, Jennings N R. A classification scheme for negotiation in electronic commerce. Journal of Group Decision and Negotiation, 2003, 12(1): 31–56 Rubenstein-Montano B, Malaga R. A co-evolutionary approach to strategy design for decision makers in complex negotiation situations. In: Proceedings of the 33rd Hawaii International Conference on System Sciences. 2000 Jennings N R, Faratin P, Lomuscio A R, Parsons S, Sierra C, Wooldridge M. Automated negotiation: prospects, methods and challenges. Journal of Group Decision and Negotiation, 2001, 10(2): 199–215 Lin R, Kraus S, Wilkenfeld J, Barry J. Negotiating with bounded rational agents in environments with incomplete information using an automated agent. Artificial Intelligence, 2008, 172(6): 823–851 Wang Y, Lin K J. Reputation-oriented trustworthy computing in ecommerce environments. IEEE Internet Computing, 2008, 12(4): 55–59 Von-Neumann J, Morgenstern O. The Theory of Games and Economic Behavior. Princeton: Princeton University Press, 1994 Fatima S, Wooldridge M, Jennings N R. Comparing equilibria for game theoretic and evolutionary bargaining models. In: Proceedings of the 5th International Workshop on Agent-Mediated Electronic Commerce. 2003, 70–77 Ehtamo H, Ketteunen E, Hämäläinen R P. Searching for joint gains in multi-party negotiations. European Journal of Operational Research, 2001, 130(1): 54–69 Fatima S S, Wooldridge M, Jennings N R. An agenda based framework for multi-issues negotiation. Artificial Intelligence, 2004, 152(1): 1–45 He M, Jennings N R, Leung H. On agent-mediated electronic commerce. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(4): 985–1003 Gerding E, Van B D, Poutré H L. Multi-issue negotiation processes by evolutionary simulation, validation and social extensions. Computational Economics, 2003, 22(1): 39–63 Cooper S, Taleb-Bendiab A. Concensus: multi-party negotiation support for conflict resolution in concurrent engineering design. Journal of Intelligent Manufacturing, 1998, 9(2): 155–159 Matwin S, Szapiro T, Haigh K. Genetic algorithms approach to a negotiation support system. IEEE Transactions on Systems, Man and Cybernetics, 1991, 21(1): 102–114 Dworman G, Kimbrough S O, Laing J D. On automated discovery of models using genetic programming in game-theoretic contexts. In: Proceedings of the 28th Hawaii International Conference on System Sciences. 1995, 428–438 Luke S, Spector L. Evolving teamwork and coordination with genetic programming. In: Proceedings of the 1st Annual Conference on Genetic Programming. 1996, 150–156 Rubenstein-Montano B, Malaga R A. A weighted sum genetic algorithm to support multiple-party multi-objective negotiations. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 366–377 Rubenstein-Montano B, Yoonb V, Drummeyc K, Liebowitz J. Agent learning in the multi-agent contracting system. Decision Support Systems, 2008, 45(1): 140–149 Li J, Deng D M. An agent negotiation system based on adaptive genetic algorithm. In: Proceedings of the 5th International Conference on Wireless Communications, Networking and Mobile Computing. 2009, 1–4 Li J, Wang L C, Jing B. An agent bilateral multi-issue simultaneous bidding negotiation protocol based on genetic algorithm and its application in e-commerce. In: Proceedings of 2008 Congress on Image and Signal Processing. 2009, 395–398 Li J, Jing B, Yang Y X. Multi-lateral multi-issue negotiation based on hybrid genetic algorithm and its application in e-commerce. Transactions of Beijing Institute of Technology, 2008, 28(10): 890–893 (in Chinese) Storn R, Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11(4): 341–359 Price K V. An Introduction to Differential Evolution. Maidenhead: McGraw-Hill, 1999, 79–108 Ilonen J, Kamarainen J K, Lampinen J. Differential evolution training algorithm for feed-forward neural networks. Neural Process Letters, 2003, 17(1): 93–105 Storn R. Designing nonstandard filters with differential evolution. IEEE Signal Processing Magazine, 2005, 22(1): 103–106 Rogalsky T, Derksen R W, Kocabiyik S. Differential evolution in aerodynamic optimization. In: Proceedings of the 46th Annual Conference of Canadian Aeronautics and Space Institute. 1999, 29–36 Joshi R, Sanderson A C. Minimal representation multisensory fusion using differential evolution. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 1999, 29(1): 63–76 Qin A K, Suganthan P N. Self-adaptive differential evolution algorithm for numerical optimization. In: Proceedings of 2005 IEEE Congress on Evolutionary Computation. 2005, 1785–1791 Noman N, Iba H. Enhancing differential evolution performance with local search for high dimensional function optimization. In: Proceedings of 2005 Genetic and Evolutionary Computation Conference. 2005, 967–974 Bui L T, Shan Y, Qi F. Comparing two versions of differential evolution in real parameter optimization. Technical Report TR-ALAR-200504009, 2005 Das S, Konar A, Chakraborty U K. Two improved differential evolution schemes for faster global search. In: Proceedings of 2005 Genetic Evolutionary Computation. 2005, 991–998 Vesterstrom J, Thomson R. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems. In: Proceedings of 2004 IEEE Congress on Evolutionary Computation. 2004, 1980–1987 Mezura-Montes E, Velázquez-Reyes J, Coello C A C. A comparative study of differential evolution variants for global optimization. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. 2006, 485–492 Kennedy J, Eberhart R. Particle swarm optimization. In: Proceedings of 1995 IEEE International Conference on Neural Networks. 1995, 1942–1948 Jeyakumar G, Velayutham C S. A comparative performance analysis of differential evolution and dynamic differential evolution variants. In: Proceedings of 2009 World Congress on Nature & Biologically Inspired Computing. 2009, 463–468 Eiben A E, Smith J E. Introduction to Evolutionary Computing. Berlin: Springer, 2003 Eiben A E, Hinterding R, Michalewicz Z. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 124–141 Qin A K, Huang V L, Suganthan P N. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 398–417 Teo J. Exploring dynamic self-adaptive populations in differential evolution. Soft Computation, 2006, 10(8): 637–686 Brest J, Greiner S, Bošković B, Mernik M, Žumer V. Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems. IEEE Transactions on Evolutionary Computation, 2006, 10(6): 646–657 Brest J, Bošković, Greiner S, Žumer V, Maučec M S. Performance comparison of self-adaptive and adaptive differential evolution algorithms. Soft Computation, 2007, 11(7): 617–629 Liu J, Lampinen J. Adaptive parameter control of differential evolution. In: Proceedings of the 8th International Mendel Conference on Soft Computing. 2002, 19–26 Liu M. Differential evolution algorithms and modification. Systems Engineering, 2005, 23(2): 108–111 (in Chinese) Das S, Abraham A. Differential evolution using a neighborhood-based mutation operator. IEEE Transactions on Evolutionary Computation, 2009, 13(3): 526–553 Zhang J Q, Sanderson A C. JADE: self-adaptive differential evolution with fast and reliable convergence performance. In: Proceedings of 2007 IEEE Congress on Evolution Computation. 2007, 2251–2258 Liang L L, Qin A K, Suganthan P N. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281–295 Beheshti R, Rahmani A T. A multi-objective genetic algorithm method to support multi-agent negotiations. In: Proceedings of the 2nd International Conference on Future Information Technology and Management Engineering. 2009, 596–599 Park S, Yang S B. An efficient multilateral negotiation system for pervasive computing environments. Engineering Applications of Artificial Intelligence, 2008, 21(4): 633–643 Lau R Y K. Towards a web services and intelligent agents-based negotiation system for B2B e-commerce. Electronic Commerce Research and Applications, 2007, 6(3): 260–273 Lau R Y K. Towards genetically optimized multi-agent multi-issue negotiations. In: Proceedings of the 38th Hawaii International Conference on System Sciences. 2005 Kebriaei H, Majd V H, Rahimi-Kian A. A new agent matching scheme using an ordered fuzzy similarity measure and game theory. Computational Intelligence, 2008, 24(2): 108–121 Du T C, Chen H L. Building a multiple-criteria negotiation support system. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(6): 804–817 Kraus S, Hoz-Weiss P, Wilkenfeld J, Andersen D R, Pate A. Resolving crises through automated bilateral negotiations. Artificial Intelligence, 2008, 172(1): 1–18 Suganthan P N, Hansen N, Liang J J, Deb K, Chen Y P, Auger A, Tiwari S. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Nanyang Technological University Technical Report. 2005