L'expression et le traitement de préférences ou d'incertitudes dans les problèmes de satisfaction de contraintes a fait l'objet de diverses extensions du cadre CSP : CSP possibilistes, CSP probabilistes, CSP additifs... D'un point de vue purement algorithmique, de nombreux problèmes s'exprimant dans ces différents formalismes semblent de meme nature et l'on souhaiterait pouvoir définir des algorithmes génétiques dans un cadre englobant. Nous proposons une généralisation de ces formalismes qui découle d'un compromis entre la généralité (suffisante pour recouvrir l'essentiel des propositions existantes) et la spécificité (suffisante pour que l'étude d'algorithmes ait un sens). Plus finement, on note que certains formalismes semblent bien se preter à l'extension des propriétés et algorithmes traditionnels des CSP alors que d'autres sont plus récalcitrants. Le cadre général proposé permet d'identifier les sources de ces différences et de montrer que certains formalismes définissent des problèmes plus difficiles, tant du point de vue théorique que pratique.