En este artículo, para una red de satélites en órbita baja (LEO) con enlaces entre satélites, se desarrolla un método de optimización de enrutamiento en el caso de fallos de enlace estocásticos. Primero, se utiliza una estrategia de tiempo discreto para que la red de satélites adquiera varios gráficos topológicos estáticos durante un ciclo. Basado en los gráficos topológicos estáticos respecto al fallo de enlace estocástico, se establece un modelo de restricciones que construye los ingresos de la tarea, los tiempos de conmutación y el costo de enrutamiento como indicadores. Luego, se propone un Algoritmo Genético mejorado basado en A* para optimizar la topología bajo el modelo de restricciones. En particular, para reducir el costo de computación, se presenta una nueva estrategia de generación para la solución inicial que combina el operador de ruleta y el algoritmo A*. Finalmente, se ilustra la efectividad del método propuesto mediante un grupo de simulaciones numéricas para la red con fallo de enlace estocástico.