Colloidal-based surface-enhanced Raman scattering (SERS) is a complex technique, where interaction between multiple parameters, such as colloid type, its concentration, and aggregating agent, is poorly understood. As a result SERS has so far achieved limited reproducibility. Therefore the aim of this study was to improve enhancement and reproducibility in SERS, and to achieve this, we have developed a multiobjective evolutionary algorithm (MOEA) based on Pareto optimality. In this MOEA approach, we tested a combination of five different colloids with six different aggregating agents, and a wide range of concentrations for both were explored; in addition we included in the optimization process three laser excitation wavelengths. For this optimization of experimental conditions for SERS, we chose the β-adrenergic blocker drug propranolol as the target analyte. The objective functions chosen suitable for this multiobjective problem were the ratio between the full width at half-maximum and the half-maximum intensity for enhancement and correlation coefficient for reproducibility. To analyze a full search of all the experimental conditions, 7785 experiments would have to be performed empirically; however, we demonstrated the search for acceptable experimental conditions of SERS can be achieved using only 4% of these possible experiments. The MOEA identified several experimental conditions for each objective which allowed a limit of detection of 2.36 ng/mL (7.97 nM) propranolol, and this is significantly lower (>25 times) than previous SERS studies aimed at detecting this β-blocker.