Article
11/17/2016

Novembre 2016

Volume 31, numéro 11

Cet article a fait l'objet d'une traduction automatique.

Série de tests : résoudre un Sudoku en utilisant l’évolution combinatoire

James McCaffrey Un problème d’optimisation combinatoire est un dans lequel l’objectif est de disposer d’un ensemble d’éléments discrets dans un ordre particulier. Un puzzle Sudoku est un exemple d’un problème d’optimisation combinatoire. Dans cet article, je vous montrer comment écrire un programme pour résoudre des problèmes difficiles Sudoku, en utilisant une technique que j’appelle COMBINATOIRE évolution.

La démonstration définit un problème de Sudoku non facile (j’expliquerai ce que j’entends par non facile sous peu). Dans Sudoku, il existe plusieurs contraintes. Chaque ligne de la grille 9 x 9 solution doit contenir les chiffres 1 à 9, sans doublon. Chaque colonne doit contenir les chiffres 1 à 9. Chaque grille secondaire 3 x 3 doit contenir les chiffres 1 à 9. Et la grille de la solution ne peut pas modifier les valeurs de départ dans la grille de problème.

Le problème de démonstration est indiqué dans Figure 1. Certains problèmes de Sudoku peuvent être résolus à l’aide d’un algorithme de force brute où vous examinez chaque cellule vide dans la grille et vérifiez les valeurs qui peuvent être légalement placés là par la vérification de la ligne, les contraintes de colonne et de la grille secondaire. Si une seule valeur est possible, cette valeur est placée dans la cellule vide. Le processus se poursuit jusqu'à ce que toutes les cellules vides ont été attribués. Ces problèmes de Sudoku non simple sont celles généralement de journaux et magazines.

Un problème de Sudoku Non simple
Figure 1-facilité Sudoku problème

Le problème de démonstration est non facile car l’algorithme force brute ne fonctionne pas. Supposons que votre analyse de la grille de problème de gauche à droite, puis de haut en bas. La cellule vide à (0, 0) peut être (1, 3, 5, 9). La cellule vide à (0, 1) peut être (1, 3, 9). La cellule vide suivante à (0, 4) peut uniquement être un 3, vous pouvez placer un 3 là et continuer. Toutefois, à l’aide de cette approche, après avoir ajouté les neuf valeurs, vous serez coincé, car toutes les cellules restantes peut être de deux ou plusieurs valeurs.

Pour obtenir une idée de quelles optimisation combinatoire évolution, observez la capture d’écran de Figure 2. Optimisation de l’évolution COMBINATOIRE utilise des idées à partir de plusieurs algorithmes inspiré de bio. L’algorithme gère une collection d’organismes virtuels. Chaque organisme représente une solution possible au problème. Évolution COMBINATOIRE est un processus itératif. Chaque itération est appelée une époque. Dans chaque version, chaque organisme tente de trouver une meilleure solution en examinant une solution possible.

Figure 2 résolution de Sudoku à l’aide d’évolution COMBINATOIRE

Une fois que tous les organismes ont eu l’occasion d’améliorer, deux solutions d’organisme bonne sont sélectionnées et utilisées pour donner naissance à un nouvel organisme, qui remplace une solution médiocre. Par conséquent, la population d’organismes évolue au fil du temps. Si une solution optimale est introuvable après un certain temps maxEpochs, l’algorithme est redémarré à l’arrêt de tous les organismes et la création d’un nouveau remplissage.

La démonstration définit des 200 organismes virtuels et un délai de 5 000 époques. Ces valeurs ont été trouvées à l’aide d’un peu de tâtonnement. Évolution COMBINATOIRE ne garantit pas qu'une solution optimale, se trouvent donc la définition d’une limite de 20 redémarrages afin d’éviter une boucle infinie possible.

Le programme de démonstration de trouver une solution optimale après le redémarrage de trois, qui a pris environ 8 secondes en cours d’exécution sur mon ordinateur de bureau. Pendant l’exécution de la démonstration, le programme affiche une mesure d’erreur de l’organisme meilleures. Je vais expliquer comment erreur définie et calculée lorsque je présente le code approprié. Toutefois, notez que l’algorithme a tendance à obtenir une très bonne solution (erreur = 2) très rapidement, mais ensuite reste bloqué. Le processus de redémarrage est un mécanisme de lutte contre cette caractéristique et est une technique courante dans de nombreux algorithmes d’optimisation.

Le programme de démonstration

Pour créer le programme de démonstration, j’ai lancé Visual Studio, cliqué sur fichier | Nouveau | Projet et sélectionné l’option d’Application Console c#. J’ai nommé le projet SudokuEvo. Le programme de démonstration n’a aucune dépendance significative de .NET pour n’importe quelle version de Visual Studio fonctionne. Après que le code du modèle chargé, dans la fenêtre Explorateur de solutions, j’ai cliqué sur le fichier Program.cs et renommé SudokuEvoProgram.cs et autorisé Visual Studio renommer automatiquement la classe Program pour moi.

En haut de la fenêtre de l’éditeur, j’ai supprimé tout inutiles à l’aide d’instructions, en laissant seulement les références aux espaces de noms System et Collections.Generic. La structure générale du programme, avec quelques modifications mineures, est illustrée dans Figure 3. Le programme de démonstration est trop long pour être présenté dans son intégralité dans cet article, mais le code source complet de démonstration est disponible dans le téléchargement qui accompagne cet article.

Figure 3 Structure de programme de démonstration

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

Le programme de démonstration n’est pas aussi compliqué qu’il vous semble tout d’abord, étant donné que de nombreuses méthodes sont des méthodes d’assistance courte. La démonstration dispose de deux classes. La classe principale a toute la logique de code implémentée en tant que méthodes statiques. La classe organisme définit une solution possible au problème cible Sudoku.

Chaque objet de l’organisme a un type qui peut être 0 pour un organisme de « travail » ou 1 pour un organisme de « explorer ». Le champ de matrice est une matrice de tableau de tableaux de type entier qui représente une solution possible. Chaque solution possible comporte une erreur, où une valeur d’erreur de 0 signifie qu’aucune des contraintes ne sont violées et, par conséquent, le champ de matrice conserve une solution optimale. Chaque objet de l’organisme a un champ d’âge pour contrôler si l’organisme de puces dans chaque version.

Le programme de démonstration configure et affiche le problème de Sudoku à l’aide de ces instructions :

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

Notez que les valeurs 0 sont utilisées pour indiquer une cellule vide. Ce manuel, codé en dur approche est assez fastidieux et des problèmes d’optimisation combinatoire plus réalistes de vous lirez les données du problème à partir d’un fichier texte.

Le problème de Sudoku est abordé à l’aide de ces instructions :

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

Méthode résoudre est essentiellement un wrapper autour de la méthode SolveEvo, qui effectue l’essentiel du travail. Il s’agit d’un modèle de conception courant dans l’optimisation combinatoire : une méthode de bas niveau solver tente de trouver une solution optimale, et cette méthode est encapsulée par une méthode de solveur de haut niveau qui effectue le redémarrage.

L’algorithme d’évolution COMBINATOIRE n’est pas assuré de trouver une solution optimale (autrement dit, une solution qui ne comporte aucune erreur de contrainte), le programme de démonstration vérifie pour déterminer si la meilleure solution trouvée est optimale :

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

Erreur et l’initialisation de matrice

À mon avis, la meilleure façon de comprendre l’optimisation combinatoire évolution consiste à commencer par examiner les méthodes d’assistance. Une fois les programmes d’assistance sont compris, la méthode solve est relativement facile à comprendre. Je vais commencer par expliquer la méthode RandomMatrix, qui initialise le champ de matrice d’un objet de l’organisme pour une solution aléatoire. Quelque peu surprenant, méthode RandomMatrix est la partie la plus délicate de l’algorithme entière.

Figure 4 illustre la définition de méthode RandomMatrix.

Figure 4 définition de la méthode 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;
}

L’algorithme est conçu pour qu’à tout moment, chacune des grilles secondaire 3 x 3 est OK en ce sens que chaque cellule contient les chiffres 1 à 9, et aucune valeur en double. Une condition est toujours true est parfois appelée un invariant. Cet invariant influence toutes les autres méthodes de l’algorithme. En théorie, la contrainte de ligne ou de la contrainte de colonne peut ont été utilisée en tant que l’invariant, mais dans la pratique, à l’aide de la grille sous contrainte est plus efficace.

Conceptuellement, parcourant chaque 3 x 3 secondaire grille 9 x 9 matrice n’est pas complète, mais mise en œuvre est un peu délicat. L’approche que j’ai consistait à définir les deux méthodes d’assistance, le bloc et angle. Un bloc de méthode accepte un index de ligne r et un index de colonne c et retourne un numéro de bloc (0-8) qui contient la cellule à (r, c). Les numéros du bloc sont affectés de gauche à droite, puis de haut en bas. Par exemple, si (r, c) = (3, 8) méthode bloc retourne 5.

Angle de la méthode accepte un ID de bloc (0-8) et retourne l’index de l’angle supérieur gauche du bloc. Par exemple, si bloc = 8, la méthode renvoie la coin (6, 6).

Une fois que vous savez que chacune des grilles secondaires d’une matrice 3 x 3 sont OK, il est possible de définir une méthode relativement simple qui définit l’erreur :

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 mots, l’erreur total pour une solution possible est la somme du nombre de valeurs manquantes dans les lignes, plus le nombre de valeurs manquantes dans les colonnes. En raison de l’algorithme invariant, toutes les grilles secondaires 3 x 3 n’ont aucune valeur manquante, afin qu’ils ne contribuent à l’erreur. Notez que le comptage du nombre de valeurs dans chaque ligne et de colonne en double est équivalente à compter le nombre de valeurs manquantes.

Génération d’une matrice de voisin

Dans l’évolution COMBINATOIRE, il existe deux types d’objets de l’organisme. Ceux qui sont type recherche de l’Explorateur de solutions possibles au hasard, à l’aide de la méthode RandomMatrix. Essayez de trouver une meilleure solution à celle stockée dans leur champ de matrice, en examinant une fermeture, solution possible » voisin » organisme objets travail de type à plusieurs reprises.

En raison de l’invariant grille secondaire 3 x 3, une solution voisine doit se limiter est une permutation d’une grille secondaire. Plus concrètement, afin de déterminer une matrice voisine, l’algorithme sélectionne de manière aléatoire un bloc, puis sélectionne les deux cellules dans le bloc (où aucune cellule contient une valeur fixe à partir de la définition du problème) et échange les valeurs dans les deux cellules.

Méthode NeighborMatrix est défini comme suit :

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

Le programme de démonstration suppose l’existence d’un objet de Random à étendue de classe nommé rnd. Cette conception est courante dans de nombreux algorithmes d’optimisation. L’idée de générer une solution voisine est trouvée dans plusieurs algorithmes d’optimisation combinatoire, par exemple, l’optimisation de recuit simulée et optimisation de colonies d’abeilles simulée.

Fusion de deux Matrices

L’algorithme d’optimisation combinatoire évolution implémente une forme d’évolution virtuelle en sélectionnant les deux objets organisme bonne (c'est-à-dire si qu'elles ont un champ de matrice avec une petite erreur), puis à l’aide de ces objets bonne pour créer un nouvel objet enfant. La nouvelle, sans doute très bonne, enfant organisme remplace un organisme médiocre.

Méthode MergeMatrices accepte deux 9 x 9 matrices de deux objets organisme. La méthode d’analyse par blocs de 0 à 8. Pour chaque bloc, une valeur aléatoire comprise entre 0,0 et 1,0 est générée. Si la valeur aléatoire est inférieur à 0,50 (c'est-à-dire environ la moitié du temps), puis les valeurs dans les deux blocs sont échangés. Le code est :

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

Ce mécanisme évolutionnaire est quelque peu semblable au mécanisme de croisement de chromosomes utilisé dans les algorithmes génétiques.

La méthode SolveEvo

L’algorithme principal est implémenté dans la méthode SolveEvo. La méthode est la meilleure description avec une combinaison de code et pseudo-code, comme indiqué dans Figure 5.

Algorithme de la figure 5 principal implémenté dans la méthode 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;
}

La méthode commence par déterminer le nombre d’objets organisme de travail comme 90 % du nombre total utilisé. Cette valeur a été déterminée par essais et erreurs. Les objets de l’organisme sont stockés dans un tableau nommé hive.

Le pseudo-code de traitement d’un organisme de type de travail est la suivante :

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

Il peut arriver que l’algorithme (probabilité = 0,001) demande à un objet de l’organisme d’accepter une solution voisine moins bonne que la solution actuelle de l’objet. Il s’agit d’une stratégie d’optimisation courants conçue pour aider un algorithme réglés à partir d’une solution non optimal.

À chaque version de la boucle d’itération, chaque organisme de type Explorateur génère une grille de solution aléatoire. Une fois que chaque objet organisme a été traité, un nouvel organisme est alors créé. En voici le pseudo-code :

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

En fait, ce mécanisme évolutionnaire est critique au succès de l’algorithme. Évolution, l’algorithme échoue parfois mais l’évolution, l’algorithme a résolu tous les problèmes Sudoku difficile que j’ai présentée il avec, y compris certains problèmes difficiles heinously, que j’ai trouvé sur Internet. Toutefois, l’optimisation combinatoire n’a pas été soumise pour effectuer des recherches sur analysis, donc le fait que COMBINATOIRE évolution peut résoudre les puzzles Sudoku n’est pas garanti qu’il peut résoudre les problèmes d’optimisation combinatoire arbitraire.

Pour résumer

L’algorithme d’évolution COMBINATOIRE que j’ai présentée dans cet article n’est pas vraiment un algorithme. Évolution COMBINATOIRE est une métaheuristique. J’entends par qui COMBINATOIRE évolution est simplement un ensemble d’instructions générales qui peut être utilisé pour concevoir un algorithme concret pour résoudre un problème d’optimisation spécifiques.

Il est peu probable que vous aurez besoin résoudre un problème de Sudoku dans votre environnement de travail normal, mais optimisation combinatoire peut être utilisée pour résoudre des problèmes concrets, trop. Les idées clés optimisation combinatoire sont à définir une structure de données qui décrit le problème cible ; définir la signification d’une solution aléatoire. définir une solution voisine est ; et définissez une métrique d’erreur. Avec ces pièces du puzzle étant en place, de nombreux problèmes qui ne peut pas être résolus par les algorithmes traditionnelles peuvent être résolus rapidement et efficacement à l’aide d’évolution combinatoire.

Récupération d’urgence. James McCaffrey travaille pour Microsoft Research à Redmond, Wash. Il a travaillé sur plusieurs produits Microsoft, y compris Internet Explorer et Bing. Dr. James McCaffrey peut être atteint à jammc@microsoft.com.

Je remercie les experts techniques Microsoft suivants qui cet article : Chris Lee et Kirk Olynyk