This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

A genetic algorithm for the partial binary constraint satisfaction problem: an application to a frequency assignment problem

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
Kolen, Antoon (METEOR)

Additional information is available for the following registered author(s):

Abstract

We describe a genetic algorithm for the partial constraint satisfaction problem. The typical elements of a genetic algorithm, selection, mutation and cross-over, are filled in with combinatorial ideas. For instance, cross-over of two solutions is performed by taking the one or two domain elements in the solutions of each of the variables as the complete domain of the variable. Then a branch-and-bound method is used for solving this small instance. When tested on a class of frequency assignment problems this genetic algorithm produced the best known solutions for all test problems. This feeds the idea that combinatorial ideas may well be useful in genetic algorithms.

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

File URL: http://edocs.ub.unimaas.nl/loader/file.asp?id=1196
File Format: application/pdf
File Function:
Download Restriction: no

Publisher Info
Paper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number 045.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length:
Date of creation: 2006
Date of revision:
Handle: RePEc:dgr:umamet:2006045

Contact details of provider:
Web page: http://edocs.ub.unimaas.nl/

For technical questions regarding this item, or to correct its listing, contact: (Willy Villevoye).

Related research
Keywords: Economics ;

Other versions of this item:

This paper has been announced in the following NEP Reports: References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
  1. McKelvey, Richard D. & McLennan, Andrew, 1996. "Computation of equilibria in finite games," Handbook of Computational Economics, in: H. M. Amman & D. A. Kendrick & J. Rust (ed.), Handbook of Computational Economics, edition 1, volume 1, chapter 2, pages 87-142 Elsevier. [Downloadable!] (restricted)
  2. Wilson, Robert, 1992. "Computing Simply Stable Equilibria," Econometrica, Econometric Society, vol. 60(5), pages 1039-70, September. [Downloadable!] (restricted)
  3. John C. Harsanyi & Reinhard Selten, 1988. "A General Theory of Equilibrium Selection in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262582384, January.
  4. Rosenthal, Robert W, 1989. "A Bounded-Rationality Approach to the Study of Noncooperative Games," International Journal of Game Theory, Springer, vol. 18(3), pages 273-91.
  5. Herings,Jean-Jacques & Peeters,Ronald, 2002. "A Globally Convergent Algorithm to Compute All Nash Equilibria of n-Person Games," Research Memoranda 084, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization. [Downloadable!]
  6. Herings, P. Jean-Jacques & van den Elzen, Antoon, 2002. "Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games," Games and Economic Behavior, Elsevier, vol. 38(1), pages 89-117, January. [Downloadable!] (restricted)
    Other versions:
  7. Govindan, Srihari & Wilson, Robert, 2004. "Computing Nash equilibria by iterated polymatrix approximation," Journal of Economic Dynamics and Control, Elsevier, vol. 28(7), pages 1229-1241, April. [Downloadable!] (restricted)
  8. Mark Voorneveld, 2006. "Probabilistic Choice in Games: Properties of Rosenthal’s t-Solutions," International Journal of Game Theory, Springer, vol. 34(1), pages 105-121, April. [Downloadable!] (restricted)
    Other versions:
  9. Richard Mckelvey & Thomas Palfrey, 1998. "Quantal Response Equilibria for Extensive Form Games," Experimental Economics, Springer, vol. 1(1), pages 9-41, June. [Downloadable!] (restricted)
  10. McKelvey Richard D. & Palfrey Thomas R., 1995. "Quantal Response Equilibria for Normal Form Games," Games and Economic Behavior, Elsevier, vol. 10(1), pages 6-38, July. [Downloadable!] (restricted)
  11. Herings, P. Jean-Jacques & Peeters, Ronald J. A. P., 2004. "Stationary equilibria in stochastic games: structure, selection, and computation," Journal of Economic Theory, Elsevier, vol. 118(1), pages 32-60, September. [Downloadable!] (restricted)
    Other versions:
  12. Govindan, Srihari & Wilson, Robert, 2003. "A global Newton method to compute Nash equilibria," Journal of Economic Theory, Elsevier, vol. 110(1), pages 65-86, May. [Downloadable!] (restricted)
  13. Yamamoto, Yoshitsugu, 1993. "A Path-Following Procedure to Find a Proper Equilibrium of Finite Games," International Journal of Game Theory, Springer, vol. 22(3), pages 249-59.
  14. Kenneth L. Judd, 1997. "Computational Economics and Economic Theory: Substitutes or Complements," NBER Technical Working Papers 0208, National Bureau of Economic Research, Inc. [Downloadable!] (restricted)
    Other versions:
  15. Jean-Jacques Herings, P., 1997. "A globally and universally stable price adjustment process," Journal of Mathematical Economics, Elsevier, vol. 27(2), pages 163-193, March. [Downloadable!] (restricted)
  16. Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, vol. 73(1), pages 141-174, 01. [Downloadable!] (restricted)
    Other versions:
  17. Herings,P. Jean-Jacques & Peeters,R., 1999. "A Differentiable Homotopy to Compute Nash Equilibria of n-Person Games," Research Memoranda 038, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization. [Downloadable!]
  18. Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, number comp1, March. [Downloadable!]
  19. Bernhard von Stengel & Antoon van den Elzen & Dolf Talman, 2002. "Computing Normal Form Perfect Equilibria for Extensive Two-Person Games," Econometrica, Econometric Society, vol. 70(2), pages 693-715, March. [Downloadable!] (restricted)
  20. Kohlberg, Elon & Mertens, Jean-Francois, 1986. "On the Strategic Stability of Equilibria," Econometrica, Econometric Society, vol. 54(5), pages 1003-37, September. [Downloadable!] (restricted)
  21. Jean-Jacques Herings, P., 2002. "Universally converging adjustment processes--a unifying approach," Journal of Mathematical Economics, Elsevier, vol. 38(3), pages 341-370, November. [Downloadable!] (restricted)
  22. Koller, Daphne & Megiddo, Nimrod & von Stengel, Bernhard, 1996. "Efficient Computation of Equilibria for Extensive Two-Person Games," Games and Economic Behavior, Elsevier, vol. 14(2), pages 247-259, June. [Downloadable!] (restricted)
  23. von Stengel, Bernhard, 1996. "Efficient Computation of Behavior Strategies," Games and Economic Behavior, Elsevier, vol. 14(2), pages 220-246, June. [Downloadable!] (restricted)
  24. Eaves, B. Curtis & Schmedders, Karl, 1999. "General equilibrium models and homotopy methods," Journal of Economic Dynamics and Control, Elsevier, vol. 23(9-10), pages 1249-1279, September. [Downloadable!] (restricted)
  25. Von Stengel, Bernhard, 2002. "Computing equilibria for two-person games," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 3, chapter 45, pages 1723-1759 Elsevier. [Downloadable!] (restricted)
Full references

Statistics
Access and download statistics

Did you know? Springer Verlag was the first commercial publisher to be listed on RePEc.

This page was last updated on 2009-11-4.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.