The growing field of machine learning and optimization gives us various promising methods to enhance risk assessment and detection of various disease. Using a combination of an evolutionary algorithm with a local solver, a memetic algorithm for hyper parameter tuning on a deep neural network, this study aims to enhance performance of heart disease prediction models. We used a comprehensive dataset from Kaggle with clinical features and applied Deep Neural Network and a Memetic algorithm with Evolutionary algorithm for global search for Hyperparameter Tuning and Naive Bayes for local solver and increased the accuracy of the Deep Neural network by 9.86% to an impressive 91.82%. The memetic optimization also achieved a higher F1 score, Precision and Recall. By placing our results, we show the potential of memetic algorithms in combination with deep neural network in advancing the predictive analytics in Cardio Vascular Diseases (CVD). The proposed Memetic model can be used to detect other diseases too and its performance can be tested on other datasets.