Artikel
02/01/2017

November 2016

Band 31, Nummer 11

Testlauf: Lösen von Sudokus mithilfe kombinatorischer Evolution

James McCaffrey Bei einem kombinatorischen Optimierungsproblem ist es das Ziel, eine Menge diskreter Elemente in einer bestimmten Reihenfolge anzuordnen. Ein Sudoku-Puzzle ist ein Beispiel eines kombinatorischen Optimierungsproblems. In diesem Artikel zeige ich Ihnen, wie ein Programm geschrieben wird, mit dem schwierige Sudoku-Probleme mithilfe einer Technik gelöst werden, die ich kombinatorische Evolution nenne.

Mithilfe der Demo wird ein „nicht einfaches“ Sudoku-Problem eingerichtet (ich erkläre in Kürze, was ich mit „nicht einfach“ meine). Beim Sudoku gibt es mehrere Vorgaben. Jede Zeile des 9×9-Lösungsgitters muss die Ziffern 1 bis 9 ohne Duplikate enthalten. Jede Spalte muss die Ziffern 1 bis 9 enthalten. Jedes 3×3-Unterquadrat muss die Ziffern 1 bis 9 enthalten. Und im Lösungsgitter können keine der Anfangswerte im Problemgitter geändert werden.

Abbildung 1 zeigt das Demoproblem. Einige Sudokus lassen sich mit einem Brute-Force-Algorithmus (dt. „rohe Gewalt“) lösen, bei dem Sie jede leere Zelle im Gitter untersuchen und prüfen, welche Werte erlaubterweise dort platziert werden können, indem die Vorgaben für Zeilen, Spalten und Unterquadraten geprüft werden. Ist nur ein Wert möglich, wird dieser Wert in der leeren Zelle platziert. Der Prozess wird fortgesetzt, bis allen leeren Zellen ein Wert zugeordnet ist. Dieser nicht einfache Typ von Sudoku-Problemen findet sich meist in Zeitungen und Zeitschriften.

Abbildung 1: Ein nicht einfaches Sudoku-Problem

Das Demoproblem ist nicht einfach, da der Brute-Force-Algorithmus nicht funktioniert. Angenommen, Sie untersuchen das Problemgitter von links nach rechts und dann von oben nach unten. Die leere Zelle bei (0, 0) kann einen der folgenden Werte enthalten: 1, 3, 5, 9. Die leere Zelle bei (0, 1) kann einen der folgenden Werte enthalten: 1, 3, 9. Die nächste leere Zelle bei (0, 4) kann nur 3 enthalten, weshalb Sie dort eine 3 platzieren und fortfahren. Doch bei diesem Ansatz bleiben Sie nach dem Platzieren von neun Werten stecken, da in allen verbleibenden Zellen zwei oder mehr Werte möglich sind.

Um zu verstehen, was kombinatorische Evolutionsoptimierung ist, lassen Sie uns einen Blick auf Abbildung 2 werfen. Für die kombinatorische Evolutionsoptimierung werden Ideen aus verschiedenen bioinspirierten Algorithmen genutzt. Der Algorithmus arbeitet mit einer Sammlung virtueller Organismen. Jeder Organismus repräsentiert eine mögliche Lösung des Problems. Kombinatorische Evolution ist ein iterativer Prozess. Jede Iteration wird als „Epoche“ bezeichnet. In jeder Epoche versucht jeder Organismus, eine bessere Lösung zu finden, indem eine neue mögliche Lösung untersucht wird.

Abbildung 2: Lösen eines Sudokus mithilfe kombinatorischer Evolution

Nachdem alle Organismen eine Chance zur Verbesserung hatten, werden zwei gute Organismuslösungen ausgewählt, um einen neuen Organismus zu gebären, der eine schwache Lösung ersetzt. Auf diese Weise entwickelt sich die Population von Organismen mit der Zeit weiter. Wenn nach dem Zeitraum „maxEpochs“ keine optimale Lösung gefunden wurde, wird der Algorithmus neu gestartet, wobei alle Organismen getötet und eine neue Population erzeugt wird.

In der Demo werden 200 virtuelle Organismen bei einem Zeitlimit von 5.000 Epochen eingerichtet. Diese Werte wurden durch Ausprobieren gefunden. Kombinatorische Evolution garantiert nicht, dass eine optimale Lösung gefunden wird, weshalb ein Grenzwert von 20 Neustarts festgestellt wurde, um eine mögliche Endlosschleife zu vermeiden.

Das Demoprogramm fand eine optimale Lösung nach drei Neustarts, was auf meinem Desktopcomputer ca. 8 Sekunden gedauert hat. Während der Ausführung der Demo zeigte das Programm ein Fehlermaß des besten Organismus. Ich erläutere, wie das Fehlermaß definiert und berechnet wird, wenn ich den entsprechenden Code vorstelle. Sie können jedoch sehen, dass der Algorithmus dazu neigt, sehr schnell zu einer sehr guten Lösung zu gelangen (Fehler = 2), dann aber stecken bleibt. Der Neustartprozess ist eine der Methoden zum Bekämpfen dieses Merkmals und in vielen Optimierungsalgorithmen üblich.

Das Demoprogramm

Um das Demoprogramm zu erstellen, habe ich Visual Studio gestartet, auf „Datei“ > „Neu“ > „Projekt“ geklickt und dann die Option „C#-Konsolenanwendung“ ausgewählt. Ich habe das Projekt „SudokuEvo“ genannt. Das Demoprogramm hat keine nennenswerten .NET-Abhängigkeiten, sodass jede Version von Visual Studio funktionieren sollte. Nach dem Laden des Vorlagencodes habe ich im Fenster des Projektmappen-Explorers mit der rechten Maustaste auf „Program.cs“ geklickt, die Datei in „SudokuEvoProgram.cs“ umbenannt und Visual Studio die automatische Umbenennung der Klasse „Program“ gestattet.

Oben im Editor-Fenster habe alle überflüssigen „using“-Anweisungen außer den Verweisen auf die Namespaces „System“ und „Collections.Generic“ gelöscht. Die Gesamtstruktur des Demoprogramms (mit ein paar kleinen Änderungen) ist in Abbildung 3 zu sehen. Das Demoprogramm ist zu lang, um es in diesem Artikel im Ganzen darzustellen. Der vollständige Quellcode der Demo ist jedoch im begleitenden Download enthalten.

Abbildung 3: Struktur des Demoprogramms

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

Das Demoprogramm ist nicht so kompliziert, wie es ggf. zunächst den Anschein hat, da viele der Methoden kurze Hilfsmethoden sind. Die Demo hat zwei Klassen. In die „Main“-Klasse ist die gesamte Codelogik als statische Methoden implementiert. Die „Organism“-Klasse definiert eine mögliche Lösung des Sudoku-Zielproblems.

Jedes „Organism“-Objekt hat einen Typ, der 0 für einen „worker“-Organismus oder 1 für einen „explorer“-Organismus sein kann. Das Feld namens „matrix“ ist eine Zeichenfolgenmatrix mit ganzen Zahlen in der Art eines Arrays von Arrays, das die mögliche Lösung darstellt. Jede mögliche Lösung hat einen Fehler. Dabei bedeutet der Fehlerwert 0, dass gegen keine Vorgaben verstoßen wurde, weshalb das Feld „matrix“ eine optimale Lösung enthält. Jedes „Organism“-Objekt hat ein Feld „age“ zum Steuern, ob der Organismus in jeder Epoche stirbt.

Im Demoprogramm wird das Sudoku-Problem mithilfe dieser Anweisungen eingerichtet und angezeigt:

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);

Der Wert 0 dient zum Angeben einer leeren Zelle. Dieser manuelle, hartcodierte Ansatz ist ziemlich mühsam, und bei den meisten realistischen kombinatorischen Optimierungsproblemen werden Problemdaten aus einer Textdatei gelesen.

Das Sudoku-Problem wird mithilfe dieser Anweisungen in Angriff genommen:

int numOrganisms = 200;
int maxEpochs = 5000;
int maxRestarts = 20;
int[][] soln = Solve(problem, numOrganisms, maxEpochs, maxRestarts);
Console.WriteLine("Best solution found: ");
DisplayMatrix(soln);

Die Methode „Solve“ ist hauptsächlich ein Wrapper um die Methode „SolveEvo“, die die meiste Arbeit leistet. Dies ist ein gängiges Entwurfsmuster bei der kombinatorischen Optimierung. Eine Solvermethode auf niedriger Ebene versucht, eine optimale Lösung zu finden. Diese Methode wird von einer Solvermethode auf höherer Ebene umschlossen, die Neustarts ausführt.

Der kombinatorische Evolutionsalgorithmus findet nicht garantiert eine optimale Lösung (d. h. eine Lösung ohne Verstöße gegen Vorgaben). Deshalb prüft das Demoprogramm, ob die beste gefundene Lösung optimal ist:

int err = Error(soln);
if (err == 0)
  Console.WriteLine("Success");
else
  Console.WriteLine("Did not find optimal solution");

Matrixinitialisierung und Fehler

Meiner Meinung nach ist die beste Möglichkeit, die kombinatorische Evolutionsoptimierung zu verstehen, mit der Untersuchung der Hilfsmethoden anzufangen. Sobald diese verstanden wurden, ist die „solve“-Methode relativ einfach zu begreifen. Lassen Sie mich mit der Erläuterung der Methode „RandomMatrix“ beginnen, die das Feld „matrix“ eines „Organism“-Objekts mit einer wahllosen möglichen Lösung initialisiert. Einigermaßen überraschend ist, dass die Methode „RandomMatrix“ der kniffligste Teil des gesamten Algorithmus ist.

Abbildung 4 zeigt die Definition der Methode „RandomMatrix“.

Abbildung 4: Definition der Methode „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;
}

Der Algorithmus ist so konzipiert, dass jedes der neun 3x3-Unterquadrate jederzeit in dem Sinne in Ordnung ist, dass jede Zelle die Ziffern 1 bis 9 ohne doppelte Werte enthält. Eine Bedingung, die stets wahr ist, wird mitunter als „Invariante“ bezeichnet. Diese Invariante beeinflusst alle anderen Methoden des Algorithmus. Theoretisch hätte die Zeilen- oder Spaltenvorgabe als Invariante verwendet werden können, doch in der Praxis ist das Verwenden der Unterquadratvorgabe effektiver.

Konzeptuell geht das Durchlaufen jedes 3x3-Unterquadrats in einer 9x9-Matrix nicht tief, doch die Implementierung ist milde gesagt knifflig. Meine Vorgehensweise bestand darin, zwei Hilfsmethoden zu definieren: „Block“ und „Corner“. Die Methode „Block“ akzeptiert den Zeilenindex „r“ und den Spaltenindex „c“ und gibt eine Blocknummer (0-8) zurück, die die Zelle bei (r, c) enthält. Blocknummern werden von links nach rechts und dann von oben nach unten zugewiesen. Beispiel: wenn (r, c) = (3, 8), dann gibt die Methode “Block” 5 zurück.

Die Methode „Corner“akzeptiert eine Block-ID (0-8) und gibt die Indizes der linken oberen Ecke des Blocks zurück. Beispiel: wenn block = 8, gibt die Methode „Corner“ (6, 6) zurück.

Sobald bekannt ist, dass alle neun 3x3-Unterquadrate einer Matrix in Ordnung sind, ist es möglich, eine relativ einfache Methode zu bestimmen, die Fehler wie folgt definiert:

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;
}

Die Gesamtanzahl der Fehler für eine mögliche Lösung ist die Summe der Anzahl fehlender Werte in den Zeilen plus die Anzahl fehlender Werte in den Spalten. Aufgrund der Algorithmusinvariante fehlen in allen 3x3-Unterquadraten keine Werte, sodass sie nicht zum Fehler beitragen. Beachten Sie, dass das Zählen der Anzahl doppelter Werte in jeder Zeile und Spalte dem Zählen der Anzahl fehlender Werte entspricht.

Generieren einer benachbarten Matrix

Bei der kombinatorischen Evolution gibt es zwei Typen von „Organism“-Objekten. Diejenigen mit dem Typ „explorer“ suchen mithilfe der Methode „RandomMatrix“ wahllos nach möglichen Lösungen. „Organism“-Objekte mit dem Typ „worker“ versuchen wiederholt, eine bessere Lösung als diejenige zu finden, die in ihrem Feld „matrix“ gespeichert ist. Dazu wird eine „benachbarte“ mögliche Lösung untersucht.

Aufgrund der Invariante der 3x3-Unterquadrate muss sich eine benachbarte Lösung auf eine Permutation eines Unterquadrats beschränken. Das heißt konkret, dass der Algorithmus zum Bestimmen einer benachbarten Matrix einen Block wahllos auswählt, dann zwei Zellen im Block auswählt (wobei keine Zelle einen festen Wert aus der Problemdefinition enthält) und die Werte in den beiden Zellen austauscht.

Die Methode „NeighborMatrix“ ist so definiert:

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;
}

Das Demoprogramm setzt das Vorhandensein eines „Random“-Objekts auf Klassenebene namens „rnd“ voraus. Dieses Konzept ist bei vielen Optimierungsalgorithmen üblich. Die Idee der Generierung einer benachbarten Lösung findet sich in verschiedenen kombinatorischen Optimierungsalgorithmen, z. B. bei der simulierten Abkühlung oder der simulierten Bienenvolkoptimierung.

Zusammenführen zweier Matrizen

Der Algorithmus für die kombinatorische Evolutionsoptimierung implementiert eine Form virtueller Evolution durch Auswahl zweier guter „Organism“-Objekte (deren Feld „matrix“ eine kleine Fehleranzahl aufweist) und das anschließende Nutzen dieser guten Objekte zum Erzeugen eines neuen Kindobjekts. Dieser neue, mutmaßlich sehr gute Kindorganismus ersetzt einen schwachen Organismus.

Die Methode „MergeMatrices“ akzeptiert zwei 9x9-Matrizen von zwei „Organism“-Objekten. Diese Methode durchsucht die Blöcke 0 bis 8. Für jeden Block wird ein Zufallswert im Bereich 0,0 bis 1,0 generiert. Wenn der Zufallswert kleiner als 0,50 ist (also ca. in der Hälfte der Fälle), werden die Werte in den beiden Blöcken ausgetauscht. Der Code ist wie folgt:

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;
}

Der Evolutionsmechanismus ist ungefähr vergleichbar mit dem Mechanismus zur Rekombination von Chromosomen, der bei genetischen Algorithmen zum Einsatz kommt.

Die „SolveEvo“-Methode

Der primäre Algorithmus wird mit der Methode „SolveEvo“ implementiert. Die Methode lässt sich am besten mithilfe einer Kombination aus Code und allgemeinem Pseudocode beschreiben (siehe Abbildung 5).

Abbildung 5: In die „SolveEvo“-Methode implementierter primärer Algorithmus

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;
}

Die Methode beginnt mit dem Bestimmen der Anzahl von „Organism“-Objekten des Typs „worker“ (90 % der Gesamtanzahl werden verwendet). Dieser Wert wurde durch systematisches Ausprobieren ermittelt. Die „Organism“-Objekte werden in einem Array namens „hive“ gespeichert.

Der Pseudocode für die Verarbeitung eines „Organism“-Objekts des Typs „worker“ ist wie folgt:

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

Der Algorithmus weist gelegentlich (Wahrscheinlichkeit = 0,001) ein „Organism“-Objekt an, eine benachbarte Lösung zu akzeptieren, die schlechter als die aktuelle Lösung des Objekts ist. Dies ist eine gängige Optimierungsstrategie, um einem Algorithmus zu helfen, sich von einer nicht optimalen Lösung zu befreien.

In jeder Epoche in der Iterationsschleife generiert jedes „Organism“-Objekt des Typs „explorer“ ein zufälliges Lösungsgitter. Nachdem alle „Organism“-Objekte verarbeitet wurden, wird ein neues „Organism“-Objekt erzeugt. In Pseudocode sieht das folgendermaßen aus:

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

Wie sich herausstellt, ist dieser evolutionäre Mechanismus entscheidend für den Erfolg des Algorithmus. Ohne Evolution hat der Algorithmus mitunter keinen Erfolg. Doch mit Evolution hat der Algorithmus alle schwierigen Sudoku-Probleme gelöst, die ich ihm vorgelegt haben, darunter einige verdammt schwierige Probleme, die ich im Internet gefunden habe. Die kombinatorische Optimierung wurde jedoch noch keiner Forschungsanalyse unterzogen, weshalb die Tatsache, dass kombinatorische Evolution sich zum Lösen von Sudokus eignet, keine Garantie ist, dass mit ihrer Hilfe kombinatorische Optimierungsprobleme gelöst werden können.

Zusammenfassung

Der kombinatorische Evolutionsalgorithmus, den ich in diesem Artikel vorgestellt habe, ist nicht tatsächlich ein Algorithmus. Denn kombinatorische Evolution ist eine Metaheuristik. Damit meine ich, dass kombinatorische Evolution nur allgemeine Leitlinien vorsieht, die zum Entwerfen eines konkreten Algorithmus zum Lösen eines bestimmten Optimierungsproblems befolgt werden können.

Es ist unwahrscheinlich, dass Sie in Ihrem normalen Arbeitsumfeld Sudoku-Probleme lösen müssen. Doch die kombinatorische Optimierung kann auch zum Lösen realer Probleme genutzt werden. Die Hauptideen für die kombinatorische Optimierung sind das Definieren einer Datenstruktur, die das Zielproblem beschreibt, was mit einer Zufallslösung gemeint ist, was eine benachbarte Lösung ist und was ein Fehlermaß ist. Sind diese Teile des Puzzles an der richtigen Stelle, können viele Probleme, die mit herkömmlichen Algorithmen nicht gelöst werden können, schnell und effizient mithilfe kombinatorischer Evolution gelöst werden.

Dr. James McCaffreyist in Redmond (Washington) für Microsoft Research tätig. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und Bing. Dr. McCaffrey erreichen Sie unter jammc@microsoft.com.

Unser Dank gilt den folgenden technischen Experten von Microsoft für die Durchsicht dieses Artikels: Chris Lee und Kirk Olynyk