Dado un grafo con vértices y aristas, la distribución de carga de una coloración: {rojo, azul} se define como = (, ), en donde es el número de aristas con al menos un vértice extremo coloreado de rojo y es el número de aristas con al menos un vértice extremo coloreado de azul. El problema de coloración de carga mínima (MLCP) consiste en encontrar una coloración tal que la carga máxima, = 1/ x máx{, }, se minimice. Se ha demostrado que este problema es NP-completo. Este artículo propone un algoritmo memético para MLCP basado en una búsqueda local K-OPT mejorada y una operación evolutiva. Además, se ejecuta una operación de división de datos para ampliar la cantidad de datos de la búsqueda global, y se emplea una operación de perturbación para mejorar la capacidad de búsqueda del algoritmo. Se realizan experimentos en el conjunto de datos de referencia DIMACS para comparar los resultados de búsqueda del algoritmo memético y los algoritmos propuestos. Los resultados experimentales muestran que un mayor número de mejores resultados para los grafos pueden encontrarse mediante el algoritmo memético, lo que puede mejorar los mejores resultados conocidos de MLCP.