The requirements imposed on information retrieval systems are increasing steadily. The vast number of documents in today?s large databases and especially on World Wide Web causes notable problems when searching for concrete information. It is difficult to find satisfactory information that accurately matches user information needs even if it is present in the database. One of the key elements when searching the web is proper formulation of user queries. Search effectiveness can be seen as the accuracy of matching user information needs against the retrieved information. Personalized search applications can notably contribute to the improvement of web search effectiveness. It has been shown, that genetic programming can evolve search queries towards users interests captured by the means of relevance. In this paper, we propose user modelling technique based on relevance estimation and provide experimental results in web search framework with evolutionary query optimization.