Tuning the hyperparameters of a model is still more of an art than a science.
Both R (caRet) and Python (sklearn) have frameworks for performing grid searches of hyperparameters using cross validation. You can define custom cost functions in these frameworks, which will allow you to directly assess your cross-validation results using your cost matrix. See the scikit-learn documentation for Python, or the caRet documentation for R. You will get much better results using your cost matrix directly to evaluate your models, instead of using F-1, precision, recall, accuracy, or any other metric.
It is important to understand what the different hyperparameters actually mean in the context of each learning algorithm to help guide the parameter search, as computational limitations usually strictly limit the number of different models you can build total, limiting the size of the grid you can realistically search.
With such a low percentage of negative examples in your set, you will want to ensure that you use stratified sampling for your cross-validation. This will ensure that each fold has the same percentage of negative examples as the base set. Otherwise, your cross-validation results will likely be biased by the non-uniform negative class distribution.