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

Abstract

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.

Keywords

differential evolution / global optimum / ecommerce / agent / multi-lateral multi-issue negotiation

References

[1] Kleindorfer P R, Kunreuther H C, Schoemaker P J H. Decision Sciences: An Integrative Perspective. Cambridge: Cambridge University Press, 1993

[2] 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

[3] 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

[4] 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

[5] 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

[6] 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

[7] Wang Y, Lin K J. Reputation-oriented trustworthy computing in ecommerce environments. IEEE Internet Computing, 2008, 12(4): 55-59

[8] Von-Neumann J, Morgenstern O. The Theory of Games and Economic Behavior. Princeton: Princeton University Press, 1994

[9] 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

[10] 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

[11] Fatima S S,Wooldridge M, Jennings N R. An agenda based framework for multi-issues negotiation. Artificial Intelligence, 2004, 152(1): 1-45

[12] He M, Jennings N R, Leung H. On agent-mediated electronic commerce. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(4): 985-1003

[13] 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

[14] 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

[15] 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

[16] 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

[17] Luke S, Spector L. Evolving teamwork and coordination with genetic programming. In: Proceedings of the 1st Annual Conference on Genetic Programming. 1996, 150-156

[18] 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

[19] 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

[20] 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

[21] 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

[22] 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)

[23] 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

[24] Price K V. An Introduction to Differential Evolution. Maidenhead: McGraw-Hill, 1999, 79-108

[25] Ilonen J, Kamarainen J K, Lampinen J. Differential evolution training algorithm for feed-forward neural networks. Neural Process Letters, 2003, 17(1): 93-105

[26] Storn R. Designing nonstandard filters with differential evolution. IEEE Signal Processing Magazine, 2005, 22(1): 103-106

[27] 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

[28] 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

[29] 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

[30] 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

[31] Bui L T, Shan Y, Qi F. Comparing two versions of differential evolution in real parameter optimization. Technical Report TR-ALAR-200504009, 2005

[32] 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

[33] 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

[34] 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

[35] Kennedy J, Eberhart R. Particle swarm optimization. In: Proceedings of 1995 IEEE International Conference on Neural Networks. 1995, 1942-1948

[36] 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

[37] Eiben A E, Smith J E. Introduction to Evolutionary Computing. Berlin: Springer, 2003

[38] Eiben A E, Hinterding R, Michalewicz Z. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 124-141

[39] 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

[40] Teo J. Exploring dynamic self-adaptive populations in differential evolution. Soft Computation, 2006, 10(8): 637-686

[41] Brest J, Greiner S, Boškovisć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

[42] Brest J, Bošković Greiner S, Žumer V, Maučcec M S. Performance comparison of self-adaptive and adaptive differential evolution algorithms. Soft Computation, 2007, 11(7): 617-629

[43] Liu J, Lampinen J. Adaptive parameter control of differential evolution. In: Proceedings of the 8th International Mendel Conference on Soft Computing. 2002, 19-26

[44] Liu M. Differential evolution algorithms and modification. Systems Engineering, 2005, 23(2): 108-111 (in Chinese)

[45] Das S, Abraham A. Differential evolution using a neighborhood-based mutation operator. IEEE Transactions on Evolutionary Computation, 2009, 13(3): 526-553

[46] 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

[47] 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

[48] 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

[49] Park S, Yang S B. An efficient multilateral negotiation system for pervasive computing environments. Engineering Applications of Artificial Intelligence, 2008, 21(4): 633-643

[50] 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

[51] Lau R Y K. Towards genetically optimized multi-agent multi-issue negotiations. In: Proceedings of the 38th Hawaii International Conference on System Sciences. 2005

[52] 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

[53] 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

[54] 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

[55] 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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg