A dataset may have many irrelevant and unnecessary features, which not only increase computational space but also lead to a very critical phenomenon called curse of dimensionality. Feature selection process aims at selecting some relevant features for further processing on behalf of the entire dataset. However, to extract such information is non-trivial task, especially for large datasets. In literature many feature selection approaches have been proposed but recently rough set based heuristic approaches have become prominent ones. However, these approaches do not ensure the optimum solution. In this paper, a hybrid approach for feature selection has been proposed, based on heuristic algorithm and exhaustive search. Heuristic algorithm finds initial feature subset which is then further optimized by exhaustive search. We have used genetic algorithm and particle swarm optimization as preprocessor and relative dependency for optimization. Experiments have shown that our proposed approach is more effective and efficient as compared to the conventional relative dependency based approach.