Users search the On-The-Fly-Market for services that satisfy their specifications. For these specifications we develop a user-friendly approach to forumalte one's requirements. On the one hand, natural-language specifications provided by the end users are processed. On the other hand, domain experts model their requirements in the form of examples, which are then synthesized into a comprehensive specification. This synthesis task is translated into an optimization problem that we solve with evolutionary algorithms.