Randomness as a constraint
21st International Conference on the Principles and Practice of Constraint Programming, CP 2015, Cork, İrlanda, 31 Ağustos - 04 Eylül 2015, cilt.9255, ss.351-366, (Tam Metin Bildiri)
- Yayın Türü: Bildiri / Tam Metin Bildiri
- Cilt numarası: 9255
- Doi Numarası: 10.1007/978-3-319-23219-5_25
- Basıldığı Şehir: Cork
- Basıldığı Ülke: İrlanda
- Sayfa Sayıları: ss.351-366
- Hacettepe Üniversitesi Adresli: Evet
Özet
Some optimisation problems require a random-looking solution with no apparent patterns, for reasons of fairness, anonymity, undetectability or unpredictability. Randomised search is not a good general approach because problem constraints and objective functions may lead to solutions that are far from random.We propose a constraintbased approach to finding pseudo-random solutions, inspired by the Kolmogorov complexity definition of randomness and by data compression methods. Our “entropy constraints” can be implemented in constraint programming systems using well-known global constraints. We apply them to a problem from experimental psychology and to a factory inspection problem.