Noviembre de 2016
Volumen 31, número 11
Serie de pruebas: resolver sudokus con la evolución combinatoria
Por James McCaffrey
.jpg "James McCaffrey")
Un problema de optimización combinatoria es aquel cuyo objetivo consiste en organizar un conjunto de elementos discretos en un orden concreto. Un rompecabezas sudoku es un ejemplo de problema de optimización combinatoria. En este artículo, mostraré cómo escribir un programa para resolver problemas de sudoku complejos, mediante una técnica que yo denomino evolución combinatoria.
La demo expone un problema de sudoku que no es fácil (explicaré a qué me refiero con "no es fácil" en breve). En sudoku, existen varias restricciones. Cada fila del cuadrado latino 9 x 9 debe contener los números del 1 al 9, sin ningún duplicado. Cada columna debe contener los números del 1 al 9. Cada subcuadrícula de 3 x 3 debe contener los números del 1 al 9. El cuadrado latino no puede cambiar ninguno de los valores iniciales de la cuadrícula del problema.
El problema de demostración se muestra en la Figura 1. Algunos problemas de sudoku pueden resolverse con un algoritmo de fuerza bruta, donde debe examinar cada celda vacía de la cuadrícula y comprobar qué valores se pueden colocar legalmente allí, para lo cual deberá comprobar las restricciones de fila, columna y subcuadrícula. Si solo un valor es posible, dicho valor se colocará en la celda vacía. El proceso continúa hasta que todas las celdas vacías están asignadas. Estos problemas de sudoku que no son de tipo fácil son aquellos que suelen encontrarse en periódicos y revistas.
.png "Un problema de sudoku que no es fácil")
Figura 1 Un problema de sudoku que no es fácil
El problema de la demostración no es fácil porque el algoritmo de fuerza bruta no funciona. Supongamos que examina la cuadrícula del problema de izquierda a derecha y, después, de arriba abajo. La celda vacía en (0, 0) puede ser un valor de (1, 3, 5, 9). La celda vacía en (0, 1) puede ser un valor de (1, 3, 9). La siguiente celda vacía en (0, 4) solo puede ser un 3, de modo que puede colocar un 3 allí y continuar. No obstante, con este enfoque, después de colocar nueve valores, se quedará bloqueado, ya que todas las celdas restantes pueden ser dos o más valores.
Para hacerse una idea de lo que es la optimización de evolución combinatoria, eche un vistazo a la captura de pantalla de la Figura 2. La optimización de evolución combinatoria usa ideas de varios algoritmos de inspiración biológica. El algoritmo mantiene una colección de organismos virtuales. Cada organismo representa una posible solución al problema. La evolución combinatoria es un proceso iterativo. Cada iteración se denomina una época. En cada época, cada organismo examina una nueva solución posible para intentar encontrar una solución mejor.
.png "Resolver sudokus con la evolución combinatoria")
Figura 2 Resolver sudokus con la evolución combinatoria
Una vez que todos los organismos hayan tenido la oportunidad de mejorar, se seleccionan y se usan dos buenas soluciones de organismos para crear un nuevo organismo, que reemplaza a una solución mediocre. Así, la población de organismos evoluciona con el tiempo. Si no se encuentra una solución óptima transcurrido algo de tiempo de maxEpochs, el algoritmo se reinicia mediante la destrucción de todos los organismos y la creación de una nueva población.
La demo configura 200 organismos virtuales y un límite de tiempo de 5000 épocas. Estos valores se encontraron con algo de pruebas y errores. La evolución combinatoria no garantiza que se encuentre una solución óptima, por lo que se estableció un límite de 20 reinicios para evitar un posible bucle infinito.
El programa de demostración encontró una solución óptima después de tres reinicios, que tardó unos 8 segundos en ejecutarse en mi máquina de escritorio. Durante la ejecución de la demo, el programa mostró una medida de error del mejor organismo. Explicaré cómo se define y calcula el error cuando presente el código pertinente. No obstante, observe que el algoritmo tiende a obtener una solución muy buena (error = 2) muy rápidamente, pero se bloquea a continuación. El proceso de reinicio es un mecanismo para combatir esta característica, así como una técnica común en muchos algoritmos de optimización.
El programa de demostración
Para crear el programa de demostración, inicié Visual Studio, hice clic en Archivo | Nuevo | Proyecto y seleccioné la opción Aplicación de consola de C#. El nombre del proyecto fue SudokuEvo. El programa de demostración no tiene ninguna dependencia significativa de .NET, por lo que funcionará con cualquier versión de Visual Studio. Después de cargar el código de plantilla en la ventana Explorador de soluciones, hice clic con el botón derecho en el archivo Program.cs, le cambié el nombre a SudokuEvoProgram.cs y permití que Visual Studio cambiase automáticamente el nombre de la clase Program.
En la parte superior de la ventana del Editor, eliminé todos los elementos innecesarios mediante instrucciones, excepto las referencias a los espacios de nombres System y Collections.Generic. La estructura general del programa, con algunos cambios menores, se muestra en la Figura 3. El programa de demostración es demasiado largo para presentarlo entero en este artículo, pero el código fuente completo de la demostración está disponible en la descarga que acompaña este artículo.
Figura 3 Estructura del programa de demostración
using System;
using System.Collections.Generic;
namespace SudokuEvo
{
class SudokuEvoProgram
{
static Random rnd = new Random(0);
static void Main(string[] args)
{
Console.WriteLine("Begin solving Sudoku");
Console.WriteLine("The problem is: ");
int[][] problem = new int[9][];
problem[0] = new int[] { 0, 0, 6, 2, 0, 0, 0, 8, 0 };
problem[1] = new int[] { 0, 0, 8, 9, 7, 0, 0, 0, 0 };
problem[2] = new int[] { 0, 0, 4, 8, 1, 0, 5, 0, 0 };
problem[3] = new int[] { 0, 0, 0, 0, 6, 0, 0, 0, 2 };
problem[4] = new int[] { 0, 7, 0, 0, 0, 0, 0, 3, 0 };
problem[5] = new int[] { 6, 0, 0, 0, 5, 0, 0, 0, 0 };
problem[6] = new int[] { 0, 0, 2, 0, 4, 7, 1, 0, 0 };
problem[7] = new int[] { 0, 0, 3, 0, 2, 8, 4, 0, 0 };
problem[8] = new int[] { 0, 5, 0, 0, 0, 1, 2, 0, 0 };
DisplayMatrix(problem);
int numOrganisms = 200;
int maxEpochs = 5000;
int maxRestarts = 20;
int[][] soln = Solve(problem, numOrganisms,
maxEpochs, maxRestarts);
Console.WriteLine("Best solution found: ");
DisplayMatrix(soln);
int err = Error(soln);
if (err == 0)
Console.WriteLine("Success \n");
else
Console.WriteLine("Did not find optimal solution \n");
Console.WriteLine("End Sudoku demo");
Console.ReadLine();
} // Main()
public static int[][] Solve(int[][] problem,
int numOrganisms, int maxEpochs, int maxRestarts) { . . }
public static void DisplayMatrix(int[][] matrix) { . . }
public static int[][] SolveEvo(int[][] problem,
int numOrganisms, int maxEpochs) { . . }
public static int[][] RandomMatrix(int[][] problem) { . . }
public static int[] Corner(int block) { . . }
public static int Block(int r, int c) { . . }
public static int[][] NeighborMatrix(int[][] problem,
int[][] matrix)
public static int[][] MergeMatrices(int[][] m1,
int[][] m2) { . . }
public static int Error(int[][] matrix) { . . }
public static int[][] DuplicateMatrix(int[][] matrix) { . . }
public static int[][] CreateMatrix(int n) { . . }
} // Program
public class Organism
{
public int type; // 0 = worker, 1 = explorer
public int[][] matrix;
public int error;
public int age;
public Organism(int type, int[][] m, int error, int age)
{
this.type = type;
this.matrix = SudokuEvoProgram.DuplicateMatrix(m);
this.error = error;
this.age = age;
}
}
} // ns
El programa de demostración no es tan complicado como puede parecer inicialmente, ya que muchos de los métodos son métodos auxiliares breves. La demo tiene dos clases. La clase principal tiene toda la lógica de código implementada como métodos estáticos. La clase Organism define una posible solución para el problema de sudoku de destino.
Cada objeto Organism tiene un tipo, que puede ser 0 para un organismo "worker" o 1 para un organismo "explorer". El campo denominado matrix es una matriz de enteros de estilo matriz de matrices que representa una solución posible. Cada solución posible tiene un error, donde un valor de error de 0 significa que no se infringe ninguna restricción y, por tanto, el campo matrix contiene una solución óptima. Cada objeto Organism tiene un campo age para controlar si el organismo muere en cada época.
El programa de demostración configura y muestra el problema de sudoku mediante estas instrucciones:
int[][] problem = new int[9][];
problem[0] = new int[] { 0, 0, 6, 2, 0, 0, 0, 8, 0 };
...
problem[8] = new int[] { 0, 5, 0, 0, 0, 1, 2, 0, 0 };
DisplayMatrix(problem);
Observe que se usan valores de 0 para indicar una celda vacía. Este enfoque manual codificado de forma rígida es bastante tedioso y, en problemas de optimización combinatoria más realistas, los datos del problema se leerían de un archivo de texto.
El problema de sudoku se aborda con estas instrucciones:
int numOrganisms = 200;
int maxEpochs = 5000;
int maxRestarts = 20;
int[][] soln = Solve(problem, numOrganisms, maxEpochs, maxRestarts);
Console.WriteLine("Best solution found: ");
DisplayMatrix(soln);
El método Solve es principalmente un contenedor alrededor del método SolveEvo, que realiza la mayor parte del trabajo. Este es un patrón de diseño común en la optimización combinatoria: un método Solver de bajo nivel intenta encontrar una solución óptima y un método Solver de alto nivel, que ejecuta el reinicio, encapsula ese método.
No se garantiza que el algoritmo de evolución combinatoria encuentre una solución óptima (es decir, una solución que no tenga errores de restricción), por lo que el programa de demostración realiza comprobaciones para determinar si la mejor solución encontrada resulta óptima:
int err = Error(soln);
if (err == 0)
Console.WriteLine("Success");
else
Console.WriteLine("Did not find optimal solution");
Inicialización y error de la matriz
En mi opinión, la mejor manera de comprender la optimización de evolución combinatoria es comenzar examinando los métodos auxiliares. Una vez que se comprenden las aplicaciones auxiliares, el método Solve es relativamente fácil de captar. Permítame comenzar explicando el método RandomMatrix, que inicializa el campo de matriz de un objeto Organism en una posible solución alternativa. De manera un poco sorprendente, el método RandomMatrix es la parte más complicada de todo el algoritmo.
En la Figura 4 se muestra la definición del método RandomMatrix.
Figura 4 Definición del método RandomMatrix
public static int[][] RandomMatrix(int[][] problem)
{
int[][] result = DuplicateMatrix(problem);
for (int block = 0; block < 9; ++block) {
// Create a List with values 1-9
// Shuffle the values in List
// Walk through each cell in current block
// If a cell is occupied, remove that value from List
// Walk through each cell in current block
// If cell is empty, add value from List
}
return result;
}
El algoritmo está diseñado para que, en cualquier momento, cada una de las nueve subcuadrículas de 3 x 3 sea correcta en el sentido de que cada celda contenga un número de 1 al 9 y no existan valores duplicados. Una condición que se da siempre se denomina, en ocasiones, invariante. Esta invariante influye en todos los demás métodos del algoritmo. En teoría, la restricción de fila o la restricción de columna se podría usar como invariante, pero en la práctica resulta más eficaz usar la restricción de subcuadrícula.
Conceptualmente, revisar cada subcuadrícula de 3 x 3 en una matriz de 9 x 9 no es una tarea compleja, pero la implementación es un poco difícil. El enfoque que seguí fue definir dos métodos auxiliares, Block y Corner. El método Block acepta un índice de fila r y un índice de columna c, y devuelve un número de bloque (0-8) que contiene la celda en (r, c). Los números de bloque se asignan de izquierda a derecha y, luego, de arriba abajo. Por ejemplo, si (r, c) = (3, 8), el método Block devuelve 5.
El método Corner acepta un id. de bloque (0-8) y devuelve los índices de la esquina superior izquierda del bloque. Por ejemplo, si block = 8, el método Corner devuelve (6, 6).
Una vez se sepa que cada una de las nueve subcuadrículas de 3 x 3 de una matriz es correcta, es posible definir un método relativamente simple que define el error:
public static int Error(int[][] matrix)
{
int err = 0;
for (int i = 0; i < 9; ++i) { // Each row
// Determine missing values in row
// Add 1 to err for each missing value
}
for (int j = 0; j < 9; ++j) { // each column
// Determine missing values in column
// Add 1 to err for each missing value
}
return err;
}
En palabras, el error total de una posible solución es la suma del número de valores que faltan en las filas, más el número de valores que faltan en las columnas. Debido a la invariante del algoritmo, no faltan valores en ninguna de las subcuadrículas de 3 x 3, por lo que no contribuyen a generar un error. Tenga en cuenta que el recuento de números duplicados de cada fila y columna equivale al recuento del número de valores que faltan.
Generar una matriz adyacente
En la evolución combinatoria, existen dos tipos de objetos Organism. Los que son de tipo explorador buscan posibles soluciones de manera aleatoria usando el método RandomMatrix. Los objetos Organism que son de tipo trabajo intentan repetidamente buscar una solución mejor para la almacenada en su campo de matriz. Para ello, examinan una posible solución "adyacente" más próxima.
Debido a la invariante de la subcuadrícula de 3 x 3, una solución adyacente debe confinarse para ser una permutación de una subcuadrícula. De manera más concreta, para determinar una matriz adyacente, el algoritmo selecciona un bloque al azar, luego selecciona dos celdas del bloque (donde ninguna celda contiene un valor fijo de la definición del problema) e intercambia los valores de las dos celdas.
El método NeighborMatrix se define de la siguiente manera:
public static int[][] NeighborMatrix(int[][] problem, int[][] matrix)
{
int[][] result = DuplicateMatrix(matrix);
int block = rnd.Next(0, 9); // pick a random block
// Determine which cells have values that can be swapped
// Pick two of those cells: (r1,c1) and (r2,c2)
int tmp = result[r1][c1];
result[r1][c1] = result[r2][c2];
result[r2][c2] = tmp;
return result;
}
El programa de demostración presupone la existencia de un objeto Random de ámbito de clase denominado rnd. Este diseño es común en muchos algoritmos de optimización. La idea de generar una solución adyacente se encuentra en varios algoritmos de optimización combinatoria como, por ejemplo, la optimización de recocido simulado y la optimización de colonia de abejas simulada.
Fusión de dos matrices
El algoritmo de optimización de evolución combinatoria implementa una forma de evolución virtual mediante la selección de dos buenos objetos Organism (lo que significa que tienen un campo de matriz con un pequeño error) y, luego usa estos buenos objetos para crear un nuevo objeto secundario. El nuevo objeto secundario Organism, presuntamente muy bueno, reemplaza a un objeto Organism mediocre.
El método MergeMatrices acepta dos matrices de 9 x 9 de dos objetos Organism. El método examina los bloques de 0 a 8. Para cada bloque, se genera un valor aleatorio entre 0.0 y 1.0. Si el valor aleatorio es inferior a 0.50 (es decir, la mitad del tiempo), los valores de los dos bloques se intercambian. El código es:
public static int[][] MergeMatrices(int[][] m1, int[][] m2)
{
int[][] result = DuplicateMatrix(m1);
for (int block = 0; block < 9; ++block) {
double pr = rnd.NextDouble();
if (pr < 0.50) {
// Replace values in block of m1 with those in m2
}
}
return result;
}
Este mecanismo evolutivo es, en cierto modo, similar al mecanismo de intercambio genético de cromosomas que se usa en los algoritmos genéticos.
Método SolveEvo
El algoritmo principal se implementa en el método SolveEvo. El método se describe mejor con una combinación de código y seudocódigo de alto nivel, como se muestra en la Figura 5.
Figura 5 Algoritmo principal implementado en el método SolveEvo
public static int[][] SolveEvo(int[][] problem,
int numOrganisms, int maxEpochs)
{
int numWorker = (int)(numOrganisms * 0.90);
int numExplorer = numOrganisms - numWorker;
Organism[] hive = new Organism[numOrganisms];
// Initialize each Organism
int epoch = 0;
while (epoch < maxEpochs) {
for (int i = 0; i < numOrganisms; ++i) {
// Process each Organism
}
// Merge best worker with best explorer, increment epoch
}
return bestMatrix;
}
El método se inicia determinando el número de objetos Organism de trabajo como el 90 % del número total usado. Este valor se determinó a partir de pruebas y errores. Los objetos Organism se almacenan en una matriz denominada hive.
El seudocódigo para procesar un objeto Organism de tipo trabajo es:
generate a neighbor matrix
if neighbor is better (or Organism makes mistake)
update matrix with neighbor
reset age to 0
else
don't update matrix
increment age
end-if
Ocasionalmente, el algoritmo (probabilidad = 0.001) indica a un objeto Organism que acepte la solución adyacente, que es peor que la solución actual del objeto. Esta es una estrategia de optimización común diseñada para ayudar a un algoritmo a desbloquearse de una solución que no es óptima.
En cada época del bucle de iteración, cada objeto Organism de tipo explorador genera una cuadrícula de solución aleatoria. Luego, después de procesar cada uno de los objetos Organism, se crea un nuevo objeto Organism. En seudocódigo:
determine index of best worker Organism
determine index of best explorer Organism
create new Organism using best worker and best explorer
determine index of worst worker Organism
replace worst worker with new child Organism
Resulta que este mecanismo evolutivo es crítico para el éxito del algoritmo. Sin evolución, el algoritmo falla en ocasiones, pero con esta, el algoritmo ha resuelto correctamente todos los problemas de sudoku complejos que le he presentado, incluidos algunos problemas de dificultad abominable que he encontrado en Internet. No obstante, la optimización combinatoria no se ha sometido a análisis de investigación, por lo que el hecho de que la evolución combinatoria pueda resolver rompecabezas de sudoku no garantiza que pueda resolver problemas de optimización combinatoria arbitrarios.
Resumen
El algoritmo de evolución combinatoria que he presentado en este artículo no es realmente un algoritmo. La evolución combinatoria es metaheurística. Con esto quiero decir que la evolución combinatoria es solo un conjunto de directrices generales que pueden usarse para diseñar un algoritmo concreto destinado a resolver un problema de optimización específico.
Es poco probable que necesite resolver un problema de sudoku en su entorno de trabajo habitual, pero la optimización combinatoria también se puede usar para resolver problemas de la vida real. Las principales ideas de la optimización combinatoria son definir una estructura de datos que describa el problema planteado, definir qué significa una solución aleatoria, definir que es una solución adyacente y definir una métrica de error. Con estas piezas del rompecabezas en su lugar, muchos problemas que no se pueden resolver con algoritmos tradicionales pueden resolverse de manera rápida y eficaz mediante la evolución combinatoria.
El Dr. James McCaffrey trabaja para Microsoft Research en Redmond, Washington. Ha colaborado en el desarrollo de varios productos de Microsoft como, por ejemplo, Internet Explorer y Bing. Puede ponerse en contacto con James en jammc@microsoft.com.
Gracias a los siguientes expertos técnicos de Microsoft por revisar este artículo: Chris Lee y Kirk Olynyk