{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T06:21:28Z","timestamp":1774160488074,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540594796","type":"print"},{"value":"9783540492818","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59479-5_30","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:17:52Z","timestamp":1330276672000},"page":"267-283","source":"Crossref","is-referenced-by-count":17,"title":["GA-easy and GA-hard constraint satisfaction problems"],"prefix":"10.1007","author":[{"given":"\u00c1goston","family":"Eiben","sequence":"first","affiliation":[]},{"given":"Paul-Erik","family":"Rau\u00e9","sequence":"additional","affiliation":[]},{"given":"Zs\u00f3fia","family":"Ruttkay","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Adorf, H. M. and Johnston, M. D., A discrete stochastic neural network algorithm for constraint satisfaction problems, In Proc. of the International Joint Conference on Neural Networks, San Diego, CA 1990.","DOI":"10.1109\/IJCNN.1990.137951"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Back, T., Khuri, A., An evolutionary heuristic for the maximum independent set problem, In Proc. of the First IEEE Conference on Evolutionary Computation, Orlando, Fl. 1994, pp 531\u2013535.","DOI":"10.1109\/ICEC.1994.350004"},{"key":"15_CR3","volume-title":"Algorithmics \u2014 Theory and Practice","author":"G. Brassard","year":"1988","unstructured":"Brassard, G. and Bratley, P., Algorithmics \u2014 Theory and Practice, Prentice Hall, Englewood Cliffs, NJ, 1988."},{"key":"15_CR4","unstructured":"Cheeseman, P., Kenefsky, B. and Taylor, W. M., Where the really hard problems are, In Proc. of IJCAI-91, 1991, pp 331\u2013337."},{"key":"15_CR5","unstructured":"Corcoran, A. L. and Wainwright, R. L., LibGA: A User Friendly Workbench for Order-Based Genetic Algorithm Research, In Proc. of Applied Computing: Sates of the Art and Practice-1993, 1993, pp 111\u2013117."},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Crawford, K.D., Solving the n-queens problem using genetic algorithms, In Proc. ACM\/SIGAPP Symposium on Applied Computing, Kansas City, Missouri, 1992, pp 1039\u20131047.","DOI":"10.1145\/130069.130128"},{"key":"15_CR7","unstructured":"Davenport, A., Tsang, E., Wang, C. J. and Zhu, K., GENET: A connnectionist architecture for solving constraint satisfaction problems by iterative improvement, In Proc. of AAAI'94."},{"key":"15_CR8","volume-title":"Handbook of Genetic Algorithms","author":"L. Davis","year":"1991","unstructured":"Davis, L., Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991."},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","volume":"41","author":"R. Dechter","year":"1990","unstructured":"Dechter, R., Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition, Artificial Intelligence 41 1990, pp 273\u2013312.","journal-title":"Artificial Intelligence"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Dozier, G., Bowen, J., Bahler, D., Solving small and large scale constraint satisfaction problems using a heuristic-based microgenetic agorithm, In Proc. of the First IEEE Conference on Evolutionary Computation, Orlando, Fl. 1994, pp 306\u2013311.","DOI":"10.1109\/ICEC.1994.349934"},{"key":"15_CR11","unstructured":"Dozier, G., Bowen, J., Bahler, D., Constraint processing using heuristic microgenetic algorithms, In Proc. of the ECAI'94 Workshop on Applied Genetic and Other Evolutionary Algorithms, Amsterdam, 1994."},{"key":"15_CR12","unstructured":"Eiben, A. E., Rau\u00e9, P-E. and Ruttkay, Zs., Heuristic Genetic Algorithms for Constrained Problems, Part I: Principles, Technical Report IR-337, Dep. of Maths. and Comp. Sci., Free University Amsterdam, 1993."},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Eiben, A. E., Rau\u00e9, P-E. and Ruttkay, Zs., Solving constraint satisfaction problems using genetic algorithms, In Proc. of the IEEE World Conf. on Comp. Intelligence, Orlando, 1994, pp 542\u2013547.","DOI":"10.1109\/ICEC.1994.350002"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Eiben, A. E., Rau\u00e9, P-E. and Ruttkay, Zs., Genetic algorithms with multi-parent reproduction, To appear in Proc. of the 3rd Parallel Problem Solving from Nature, LNCS Series, Springer-Verlag, 1994.","DOI":"10.1007\/3-540-58484-6_252"},{"key":"15_CR15","unstructured":"Eiben, A. E., Rau\u00e9, P-E. and Ruttkay, Zs., Repairing, adding constraints and learning as a means of improving GA performance on CSPs, In Proc. of the BENELEARN-94, Rotterdam, 1994."},{"key":"15_CR16","unstructured":"Forrest, S. and Mitchell, M., What makes a problem hard for a GA?, to appear in Machine Learning 1994."},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Fox, B. R. and McMahon, M.B., Genetic operators for sequencing problems, In Proc. of Foundations of Genetic Algorithms-90, Morgan Kaufman, 1991, pp 284\u2013300.","DOI":"10.1016\/B978-0-08-050684-5.50021-5"},{"issue":"1","key":"15_CR18","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"E. C. Freuder","year":"1982","unstructured":"Freuder, E. C., A sufficient condition for backtrack-free search, Journal of the ACM 29, 1 1982. pp 24\u201332.","journal-title":"Journal of the ACM"},{"issue":"4","key":"15_CR19","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1145\/4221.4225","volume":"32","author":"E. C. Freuder","year":"1985","unstructured":"Freuder, E. C., A sufficient condition for backtrack-bounded search, Journal of the ACM 32, 4 1985. pp 775\u2013761.","journal-title":"Journal of the ACM"},{"key":"15_CR20","unstructured":"Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989."},{"key":"15_CR21","unstructured":"Hao, J., Dorne, R., A new population-based method for satisfiability problems, In Proc. of ECAI'94, Amsterdam 1994, pp 135\u2013139."},{"key":"15_CR22","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0004-3702(80)90051-X","volume":"14","author":"R. M. Haralick","year":"1980","unstructured":"Haralick, R. M., and Elliot, G. L., Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence 14 1980, pp 263\u2013313.","journal-title":"Artificial Intelligence"},{"key":"15_CR23","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1090.001.0001","volume-title":"Adaptation in Natural and Artificial Systems","author":"J.H. Holland","year":"1992","unstructured":"Holland, J.H., Adaptation in Natural and Artificial Systems, Ann Arbor: Univ. of Michingan Press, 1992."},{"key":"15_CR24","unstructured":"Hower, W. and Jaboci, S., Parallel distributed constraint satisfaction, In Proc. of the Second International Workshop on Parallel Processing for Artificial Intelligence, IJCAI-93, Chambery, 1993, pp 65\u201368."},{"key":"15_CR25","unstructured":"Huang, W., Kao, C., Horng, J., A genetic algorithm approach for set covering problems, In Proc. of the First IEEE Conference on Evolutionary Computation, Orlando, Fl. 1994, pp 569\u2013574."},{"issue":"3","key":"15_CR26","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1287\/opre.39.3.378","volume":"39","author":"D. S. Johnson","year":"1991","unstructured":"Johnson, D. S., Aragon, C. R., McGeoch, L. A. and Schevon, C., Optimization by simulated annealing: an experimental evaluation, Part II, Journal of Operations Research 39, 3 1991, pp 378\u2013406.","journal-title":"Journal of Operations Research"},{"key":"15_CR27","volume-title":"Proceedings of CSC'94","author":"S. Khuri","year":"1994","unstructured":"Khuri, S., B\u00e4ck, T. and Heitk\u00f6tter, J., An evolutionary approach to combinatorial optimization problems, In Proceedings of CSC'94, Phoenix Arizona, 1994, ACM Press."},{"key":"15_CR28","doi-asserted-by":"crossref","unstructured":"Manderick, B. and Inayoshi, H., The weighted graph bi-partitioning problem: an analysis of GA performance, To appear in Proc. of the 3rd Parallel Problem Solving from Nature, Springer-Verlag, 1994.","DOI":"10.1007\/3-540-58484-6_304"},{"key":"15_CR29","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A.K. Mackworth","year":"1977","unstructured":"Mackworth, A.K., Concistency in networks of relations, Artificial Intelligence 8. 1977 pp 99\u2013118.","journal-title":"Artificial Intelligence"},{"issue":"no.1","key":"15_CR30","doi-asserted-by":"crossref","first-page":"3","DOI":"10.3233\/AIC-1989-2101","volume":"2","author":"P. Meseguer","year":"1989","unstructured":"Meseguer, P., Constraint satisfactionproblems: an overview, AICOM, Vol. 2. no. 1 1989, pp 3\u201317.","journal-title":"AICOM"},{"key":"15_CR31","unstructured":"Michalewicz, Z. and Janikow, C. Z., Handling constraints in genetic algorithms, In Proc. of Int. Conference on Genetic Algorithms-91, Morgan Kaufman, 1991."},{"key":"15_CR32","doi-asserted-by":"crossref","unstructured":"Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, 1994.","DOI":"10.1007\/978-3-662-07418-3"},{"key":"15_CR33","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0004-3702(92)90007-K","volume":"58","author":"S. Minton","year":"1992","unstructured":"Minton, S., Johnston, M. D., Philips, A. and Laird, P., Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence 58. 1992. pp 161\u2013205.","journal-title":"Artificial Intelligence"},{"key":"15_CR34","volume-title":"The royal road for genetic algorithms: fitness landscapes and GA performance","author":"M. Mitchell","year":"1991","unstructured":"Mitchell, M., Forrest, S., and Holland, J., The royal road for genetic algorithms: fitness landscapes and GA performance, In Proc. of the First European Conference on Artificial Life, Cambridge, MA, MIT Press, 1991."},{"key":"15_CR35","unstructured":"Morris, P., On the density of solutions in equilibrium points for the n-queens problem, In Proc. AAAI-92, San Jose, CA 1992, pp 428\u2013433."},{"key":"15_CR36","doi-asserted-by":"crossref","unstructured":"Paechter, B., Cumming, S., Luchian, H. and Petriuc, M., Two solutions for the general timetable problem using evolutionary methods, In Proc. of the First IEEE Conference on Evolutionary Computation, Orlando, Fl. 1994, pp 300\u2013305.","DOI":"10.1109\/ICEC.1994.349935"},{"key":"15_CR37","unstructured":"Paredis, J., Exploiting constraints as background knowledge for a case-study for scheduling, In Proc. Parallel Problem Solving from Nature, 1992, Elsevier."},{"issue":"3","key":"15_CR38","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/101340.101343","volume":"1","author":"R. Sosic","year":"1990","unstructured":"Sosic, R., Gu, J., A polynomial time algorithm for the n-queens problem, SIGART 1 (3), 1990, pp 7\u201311.","journal-title":"SIGART"},{"key":"15_CR39","unstructured":"Starkweather, T., Mc Daniel, S., Mathias, K., Whitley, D. and Whitley, C., A comparison of genetic sequenceing operators, In Proc. of Int. Conference on Genetic Algorithms-91, 1991, pp 69\u201376."},{"key":"15_CR40","unstructured":"Tsang, E. P. K. and Warwick, T., Applying genetic algorithms to constraint satisfaction optimization problems, In Proc. of ECAI-90, 1990, pp 649\u2013654."},{"key":"15_CR41","unstructured":"Yamada, T. and Nakano, R., A genetic algorithm applicable to large-scale job-shop problems, In Proc. Parallel Problem Solving from Nature, 1992, Elsevier, pp 281\u2013290."}],"container-title":["Lecture Notes in Computer Science","Constraint Processing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59479-5_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:46:58Z","timestamp":1742597218000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59479-5_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540594796","9783540492818"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/3-540-59479-5_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}