El problema del conjunto dominante mínimo conectado (MCDS) es un problema de optimización combinatoria muy significativo y NP-duro, y se ha utilizado en muchos campos como las redes de sensores inalámbricos y las redes ad hoc. En este documento, proponemos un nuevo algoritmo de búsqueda local de múltiples arranques (MSLS) para abordar el problema del conjunto dominante mínimo conectado. En primer lugar, presentamos el mecanismo de aptitud para diseñar el mecanismo de puntuación de vértices para que nuestro algoritmo pueda salir del óptimo local. En segundo lugar, utilizamos el mecanismo de verificación de configuración (CC) para evitar el problema de ciclado. Luego, proponemos el mecanismo de volteo de vértices para cambiar el estado del vértice combinando el mecanismo CC con el mecanismo de puntuación de vértices. Finalmente, proponemos un marco de búsqueda local de múltiples arranques basado en estos mecanismos. Comparamos el algoritmo MSLS con otros algoritmos comparativos en extensas instancias. Los resultados del experimento muestran que MSLS es superior a otros algoritmos en calidad de solución y eficiencia temporal en la mayoría de las instancias.