Domino effects are high-impact low-probability events that can have catastrophic consequences. To prevent and to reduce risks related to such events, safety barriers (SBs) are crucial. However, the initiation, propagation, and stopping processes of domino effects are characterized with complexity and uncertainties and hence they are unpredictable. This makes it challenging to allocate SBs based on predicted probabilities. In this study, a multi-objective optimization model which integrates graph theory with Non-dominated Sorting Genetic Algorithm II (NSGA-II) was proposed to allocate add-on SBs effectively. Graph metrics were used to quantify the escalation risks related to storage tanks and to optimize the allocation of add-on SBs, thereby minimizing the consequences of a domino effect under a budget constraint. The results of the case study demonstrate great efficiency in finding globally optimal strategies with a largest reduction of 94.3% in the out-closeness score due to the implementation of add-on SBs, allowing decision-makers to choose the most preferable investment strategy in face of domino effect risk. Our study therefore provides a novel approach to achieve an optimal allocation of add-on SBs globally and can be useful in preventing domino effects in large-scale chemical clusters equipped with a large number of storage tanks.