Personalized medicine (PM) aims to identify the best treatment for a subject using subject-specific covariates. Current methods for designing a parametric-based PM systems rely on a regression model with interaction terms involving the pre-selected treatments and the covariates. Trial design issues for estimating this model are less discussed and invariably focus on two-arm trials only. This paper thus proposes a genetic algorithm to construct multi-arm trials that optimize the model’s estimation efficiency across quantitative and two-level categorical covariates. To this end, the algorithm uses a novel optimality criterion that resembles the I-optimality criterion commonly used in the optimal design literature. Using numerical experiments and four other state-of-art algorithms, we show that our algorithm matches the performance of dedicated design methods for two-arm trials, and out-performs the only other available design method for multi-arm trials. We also demonstrate its applicability by redesigning a real three-arm Weight Maintenance Diet trial.