Algorithms for separation of heart sounds from background lung sound noises are vital for accurate diagnosis of heart diseases. In this paper, an improved adaptive noise cancellation technique based on the Least Mean Square (LMS) algorithm is used to separate heart sounds from lung sounds. The step size parameter in the LMS algorithm is optimally chosen using a hybrid Nelder-Mead (H-NM) optimization algorithm. The NM algorithm is initialized with a good initial solution by using computationally cheap random search to compute a rough estimate of the global minimum. Initialization of the NM algorithm with a good initial guess avoided convergence to shallow local minima and improved the quality of the final solution. The effects of using two state-of-the-arts biologically inspired heuristic optimization algorithms instead of the H-NM algorithm and three variants of the standard LMS algorithm are investigated. The correlation coefficient between the ideal and filtered heart sound signal and running time-complexity of different algorithms are taken as the metric for comparison of different heart sound separation approaches. Simulation results indicate that the approach presented in this paper performs significantly better than a variety of alternate approaches on heart sound separation problems.