用于数独求解的模拟退火

Question

我正试图使用模拟退火来解决一个9x9数独难题，但我的实现似乎无法正常工作。它甚至没有接近更低成本的解决方案，而是一直围绕着成本在60到80之间的结果。

我的成本函数返回三项的总和：每个行、列和块中的重复位数(3x3(。

我实现的后继(邻居(函数用随机值改变9x9网格中随机选择的两个数字。

这是我的SA函数，它没有按预期工作：

public static void simulatedAnnealing() {
Sudoku neighbour; // candidate successor object
final Double temperature = 2.0; // initial temperature
final Double coolingFactor = 0.999; // cooling constant
final int maxIterations = 1000; // number of iterations
for(Double t = temperature; t>1; t*=coolingFactor) {
for(int i = 0; i < maxIterations; i++) {
neighbour = sudoku.generateSuccessor(); // set random neighbour
int delta = neighbour.cost() - sudoku.cost(); // calculate delta
if (delta <= 0) {
sudoku = neighbour; // always accept good step.
} else {
if (Math.exp(-delta / temperature) > Math.random()) { // Simulated annealing
sudoku = neighbour;
} 
} 
}
System.out.println(sudoku.cost());
if(sudoku.cost() == 0) { break; } // if puzzle is solved
} }

生成继任者的功能：

public Sudoku generateSuccessor() {
int[][] newGrid = new int[9][9];
for(int o = 0; o < 9; o ++) { // cloning current grid array
for(int g = 0; g < 9; g ++) {
newGrid[o][g] = grid[o][g];
}
}
Sudoku rndm = new Sudoku(newGrid); // random Sudoku object.
for (int i = 0; i < 2; i++) { // will randomize 2 cells in 9x9 grid.
int rndmCell = rndmValue(); // random digit for randomizing.
int randomRow = rndm(); // random row that will be randomized
int randomCol = rndm(); // random column that will be randomized
// prevent randomizing given cells in sudoku (in problem definition)
boolean shouldContinue = false;
for (Coordinate c : SudokuSolver.concreteCoordinates) {
if (c.row == randomRow && c.col == randomCol) { 
shouldContinue = true;
break;
}
}
if (shouldContinue) {
i--;
continue;
}
// prevention end.
rndm.grid[randomRow][randomCol] = rndmCell;
}
return rndm;
}

成本函数：

public int cost() {
if(hasZeros()) { // if grid is not totally filled with numbers don't calculate its cost.
return -1;
}
int cost = 0;
for(int i = 0; i< 9; i++) { // find total collusions in rows&columns.
cost += findNumberOfCollusions(grid[i]); // find collustions at row 'i'.
cost += findNumberOfCollusions(getColumn(grid,i)); // find collustions at column 'i'.
}
for(int r = 0; r < 9; r += 3) { //find total colusions in blocks (3x3).
for(int c = 0; c < 9; c += 3) {
int[] block = new int[9];
int ctr = 0;
for (int i = r; i < r + 3; i++) {
for (int y = c; y < c+ 3; y++) {
block[ctr] = grid[i][y];
ctr++;
}
}
cost += findNumberOfCollusions(block);
}
}
return cost;
}

当我运行程序时，输出的成本在60到80之间。之后，温度低于极限，程序输出的解决方案的成本约为该时间间隔。有人能告诉我我做错了什么吗？提前谢谢。

Answer 1

我也遇到了与您描述的问题类似的问题，我的适应度仍然很高(实际上，我的问题是没有在Python中复制列表(。我真的不能确定为什么你的代码会被卡住，但如果必须猜测的话：邻居一代(int rndmCell = rndmValue(); int randomRow = rndm(); int randomCol = rndm();(实际上可能弊大于利。想象一下，您有一个几乎完全的数独，但突然有两个正确的单元格将其值更改为完全相反的值，这不仅对单元格本身是错误的，而且对行、列和/或3x3正方形也是错误的。我不是数学家，但逻辑告诉我，数独越适合(也就是说，它的适合度越接近0(，通过随机改变单元格来打乱数独的机会就越多。这种方法可能会让你很容易陷入局部最小值。

更多的"；"知情"；这个问题的解决方案是通过例如生成值[1..9]的排列行、交换随机行的两个单元格(因此仍然满足限制(以及仅计算列和3x3平方上的适合度来固定数独谜题的三个基本限制之一。这种邻居代的选择通常更有效。如果你感兴趣，这个想法来自于Metaheuristics可以解决数独难题的论文。我可以说，这个想法对我帮助很大，现在算法完成了我提供的数独：(