[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

An augmented EDA with dynamic diversity control and local neighborhood search for coevolution of optimal negotiation strategies

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

In this paper, we present an estimation of distribution algorithm (EDA) augmented with enhanced dynamic diversity controlling and local improvement methods to solve competitive coevolution problems for agent-based automated negotiations. Since optimal negotiation strategies ensure that interacting agents negotiate optimally, finding such strategies—particularly, for the agents having incomplete information about their opponents—is an important and challenging issue to support agent-based automated negotiation systems. To address this issue, we consider the problem of finding optimal negotiation strategies for a bilateral negotiation between self-interested agents with incomplete information through an EDA-based coevolution mechanism. Due to the competitive nature of the agents, EDAs should be able to deal with competitive coevolution based on two asymmetric populations each consisting of self-interested agents. However, finding optimal negotiation solutions via coevolutionary learning using conventional EDAs is difficult because the EDAs suffer from premature convergence and their search capability deteriorates during coevolution. To solve these problems, even though we have previously devised the dynamic diversity controlling EDA (D2C-EDA), which is mainly characterized by a diversification and refinement (DR) procedure, D2C-EDA suffers from the population reinitialization problem that leads to a computational overhead. To reduce the computational overhead and to achieve further improvements in terms of solution accuracy, we have devised an improved D2C-EDA (ID2C-EDA) by adopting an enhanced DR procedure and a local neighborhood search (LNS) method. Favorable empirical results support the effectiveness of the proposed ID2C-EDA compared to conventional and the other proposed EDAs. Furthermore, ID2C-EDA finds solutions very close to the optimum.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Bengoetxea E, Larrañaga P, Bloch I, Perchant A (2001) Estimation of distribution algorithms: a new evolutionary computation approach for graph matching problems. In: Lect Notes Comput Sc, vol 2134. Springer, Berlin, pp 454–468

    Google Scholar 

  2. Brazier FMT, Cornelissen F, Gustavsson R, Jonker CM, Lindeberg O, Polak B, Treur J (2004) Compositional verification of a multi-agent system for one-to-many negotiation. Appl Intell 20(2):95–117

    Article  MATH  Google Scholar 

  3. Chao K-M, Chen J-H, Gatward R (2002) Negotiating agents in a market-oriented grid. In: Proceedings of the 2nd IEEE/ACM international symposium on cluster computing and the grid, p 436

    Chapter  Google Scholar 

  4. Deb K, Sindhya K, Okabe T (2007) Self-adaptive simulated binary crossover for real-parameter optimization. In: Proceedings of the 9th annual conference on genetic and evolutionary computation, pp 1187–1194

    Chapter  Google Scholar 

  5. Erus G, Polat F (2007) A layered approach to learning coordination knowledge in multiagent environments. Appl Intell 27(3):249–267

    Article  Google Scholar 

  6. Faratin P, Sierra C, Jennings NR (1998) Negotiation decision functions for autonomous agents. Robot Auton Syst 24(3–4):59–182

    Google Scholar 

  7. Fatima S, Wooldridge MJ, Jennings NR (2002) Optimal negotiation strategies for agents with incomplete information. In: Lect Notes Artif Int, vol 2333. Springer, Berlin, pp 377–392

    Google Scholar 

  8. Fogel DB (1994) An introduction to simulated evolutionary optimization. IEEE Trans Neural Netw 5(1):3–14

    Article  Google Scholar 

  9. Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading

    MATH  Google Scholar 

  10. Gwak J, Sim KM (2010) Novel dynamic diversity controlling EDA and its application to automated bilateral negotiation. In: Proceedings of the 5th IEEE international conference on bio-inspired computing: theories and applications, pp 536–544

    Google Scholar 

  11. Gwak J, Sim KM (2010) Co-evolving best response strategies for P-S-Optimizing negotiation using evolutionary algorithms. In: Proceedings of the 2010 international multiconference of engineers and comput scientists. Lecture notes in engineering and computer science. Springer, Berlin, pp 13–18

    Google Scholar 

  12. Gwak J, Sim KM (2011) Coevolving negotiation strategies for p-s-optimizing agents. In: Ao S-I, Castillo O, Huang X (eds) Intelligent control and computer engineering. Springer, Berlin, pp 119–135

    Chapter  Google Scholar 

  13. Gwak J, Sim KM, Zhang M (2010) Finding near-optimal strategies for negotiation with incomplete information using a diversity controlling EDA. In: Proceedings of the 8th international conference on supply chain management and information systems, pp 571–577

    Google Scholar 

  14. Isern D, Moreno A, Sánchez D, Hajnal Á, Pedone G, Varga LZ (2011) Agent-based execution of personalised home care treatments. Appl Intell 34(2):155–180

    Article  Google Scholar 

  15. Jennings NR, Faratin P, Lomuscio AR, Parsons S, Wooldridge MJ, Sierra C (2001) Automated negotiation: prospects, methods and challenges. Group Decis Negot 10:199–215

    Article  Google Scholar 

  16. Kolomvatsos K, Hadjiefthymiades S (2012) Buyer behavior adaptation based on a fuzzy logic controller and prediction techniques. Fuzzy Sets Syst 189:30–52

    Article  MathSciNet  Google Scholar 

  17. Kowalczyk R (2002) Fuzzy e-negotiation agents. Soft Comput 6(5):337–347

    Article  MathSciNet  MATH  Google Scholar 

  18. Lai KR, Lin MW, Yu TJ (2009) Learning opponent’s beliefs via fuzzy constraint-directed approach to make effective agent negotiation. Appl Intell 33(2):232–246

    Article  Google Scholar 

  19. Larrañaga P, Lozano ZA (2002) Estimation of distribution algorithms: a new tool for evolutionary computation. Kluwer, Norwell

    Book  MATH  Google Scholar 

  20. Larrañaga P, Etxeberria R, Lozano JA, Peña JM (1999) Optimization by learning and simulation of Bayesian and Gaussian networks. Technical Report. EHU-KZAA-IK-4/99, University of the Basque Country

  21. Leung Y, Gao Y, Xu Z-B (1997) Degree of population diversity—a perspective on premature convergence in genetic algorithms and its Markov chain analysis. IEEE Trans Neural Netw 8:1165–1176

    Article  Google Scholar 

  22. Matos N, Sierra C, Jennings NR (1998) Determining successful negotiation strategies: an evolutionary approach. In: Proceedings of the 3rd international conference on multi-agent systems, pp 182–189

    Google Scholar 

  23. Miconi T (2009) Why coevolution doesn’t “work”: superiority and progress in coevolution. In: Proceedings of the 12th European conference on genetic programming, pp 49–60

    Chapter  Google Scholar 

  24. Mittal S, Deb K (2009) Optimal strategies of the iterated prisoner’s dilemma problem for multiple conflicting objectives. IEEE Trans Evol Comput 13(3):554–565

    Article  Google Scholar 

  25. Nolfi S, Floreano D (1998) Coevolving predator and prey robots: do “arms races” arise in artificial evolution? Artif Life 4:311–335

    Article  Google Scholar 

  26. Oliver JR (1996) A machine-learning approach to automated negotiation and prospects for electronic commerce. J Manag Inf Syst 13:83–112

    Article  MathSciNet  Google Scholar 

  27. Pelikan M, Goldberg DE, Lobo FG (2002) A survey of optimization by building and using probabilistic models. Comput Optim Appl 21:5–20

    Article  MathSciNet  MATH  Google Scholar 

  28. Pollack JB, Blair AD (1998) Co-evolution in the successful learning of backgammon strategy. Mach Learn 32(3):225–240

    Article  MATH  Google Scholar 

  29. Rosenschein JS, Zlotkin G (1994) Rules of encounter: designing conventions for automated negotiation among computers. MIT Press, Cambridge

    Google Scholar 

  30. Rubinstein A (1985) A bargaining model with incomplete information about time preferences. Econometrica 53(5):1151–1172

    Article  MathSciNet  MATH  Google Scholar 

  31. Sim KM (2002) A market driven model for designing negotiation agents. Comput Intell 18(4):618–637

    Article  MathSciNet  Google Scholar 

  32. Sim KM (2005) Equilibria, prudent compromises,and the “waiting” game. IEEE Trans Syst Man Cybern, Part B, Cybern 35(4):712–724

    Article  MathSciNet  Google Scholar 

  33. Sim KM (2008) An evolutionary approach for p-s-optimizing negotiation. In: Proceedings of the 2008 IEEE congress on evolutionary computation, pp 1364–1371

    Google Scholar 

  34. Sim KM, An B (2009) Evolving best-response strategies for market-driven agents using aggregative fitness GA. IEEE Trans Syst Man Cybern, Part C, Appl Rev 39(3):284–298

    Article  Google Scholar 

  35. Sim KM, Choi CY (2003) Agents that react to changing market situations. IEEE Trans Syst Man Cybern, Part B, Cybern 33(2):188–201

    Article  Google Scholar 

  36. Sim KM, Guo Y, Shi B (2007) Adaptive bargaining agents that negotiate optimally and rapidly. In: Proceedings of the 2007 IEEE congress on evolutionary computation, pp 1007–1014

    Google Scholar 

  37. Sim KM, Guo Y, Shi B (2009) BLGAN: Bayesian learning and genetic algorithm for supporting negotiation with incomplete information. IEEE Trans Syst Man Cybern, Part B, Cybern 39(1):198–211

    Article  Google Scholar 

  38. Tutkun N (2009) Optimization of multimodal continuous functions using a new crossover for the real-coded genetic algorithms. Expert Syst Appl 36(4):8172–8177

    Article  Google Scholar 

  39. Ursem RK (2002) Diversity-guided evolutionary algorithms. In: Proceedings of the 7th international conference on parallel problem solving from nature, pp 462–474

    Google Scholar 

  40. Ursem RK (2003) Model for evolutionary algorithms and their applications in system identification and control optimization. PhD dissertation, University of Aarhus

  41. Wang X, Shen X, Georganas ND (2006) A fuzzy logic based intelligent negotiation agent (FINA) in ecommerce. In: Proceedings of the 2006 IEEE Canadian conference on electrical and computer engineering, pp 276–279

    Chapter  Google Scholar 

Download references

Acknowledgements

This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MEST) (KRF-2009-220-D00092) and the DASAN International Faculty Fund (project code: 140316). The authors would like to thank the Editor-in-Chief and the anonymous referees for their comments and suggestions.

Author information

Authors and Affiliations

  1. School of Information and Mechatronics, Gwangju Institute of Science and Technology, 261 Cheomdan-gwagiro (Oryong-dong), Buk-gu, Gwangju, 500-712, Republic of Korea

    Jeonghwan Gwak

  2. School of Computing, University of Kent, Chatham Maritime, Chatham, Kent, ME4 4AG, UK

    Kwang Mong Sim

Authors
  1. Jeonghwan Gwak
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kwang Mong Sim
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jeonghwan Gwak.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gwak, J., Sim, K.M. An augmented EDA with dynamic diversity control and local neighborhood search for coevolution of optimal negotiation strategies. Appl Intell 38, 600–619 (2013). https://doi.org/10.1007/s10489-012-0384-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-012-0384-6

Keywords

Search

Navigation