java - 模拟退火 N Queens 概率公式

Question

我在使用模拟退火算法来解决 n 皇后问题时遇到了一些麻烦。基本上，我让它寻找更好的更多，效果很好，但然后我运行一个公式来检查它是否应该采取“坏” Action 。据我了解，公式为e^(板状态计算变化)/CurrentTemperature。这个数字应该与随机的 double 或 float 进行比较，如果随机数大于方程，算法应该采取“坏”的举动。我遇到的问题是该公式总是非常接近 1 或超过 1。这里是我的一些代码(让我知道是否应该提供更多代码):

temperature = n*100; //initializes starting temperature 
    currentTemp = n*100;
    int cooldown = n*2; //initializes cool down temperature 
    float examine = 0; //this is the change in board calculation
int cost = 1;
    boolean betterMove = false;
    queen = new int[n];
    int[][] board = graph; // generates a board of n size
    float ran = 0; //random float to compare to 
    double compareAgainst = 0; //formula variable 
cost = calculate(board, n); //calculates the cost 
while (cost > 0 && currentTemp > 0) 
    {


        // chooses a random queen to move that has a heuristic higher than zero
        int Q = rand.nextInt(n);
        while (queen[Q] == 0)
            Q = rand.nextInt(n);

        betterMove = false;

        for (int i = 0; i < n; i++) 
        {
            for (int j = 0; j < n; j++) 
            {
                if (board[i][j] == 1 && j == Q) 
                {
                    while (!betterMove)
                    {
                        int move = i;
                        while (move == i)

                        move = rand.nextInt(n); //pick a random move
                        tempBoard[i][j] = 0; //erase old position 
                        tempBoard[move][j] = 1; //set new position 

examine =  calculate(tempBoard, n) - calculate(board, n); //calculates the difference between the change in boards
                        ran = rand.nextFloat(); //generates random number to compare against 
                        compareAgainst = Math.pow(Math.E, (-examine / currentTemp)); //formula out of the book, basically is e^(change in board state divided by currentTemp)


                        if (calculate(tempBoard, n) < calculate(board, n))  //if this is a better move
                        {
                            for (int a = 0; a < n; a++)
                                for (int b = 0; b < n; b++)
                                    board[a][b] = tempBoard[a][b]; //set it to the board 

                            cost = calculate(board, n);
                            currentTemp -= cooldown; //cool down the temperature 

    betterMove = true;
                        }

else if(calculate(tempBoard,n) >= calculate(board,n)) //if this is a worse move
                        {

                          if(verbose == 1) //outputs whether or not this is a bad move and outputs function value and random float for simulated annealing purposes
                            {
                                System.out.println("This is a worse move");
                                System.out.println("The numbers for Simulated Annealing:");
                                System.out.println("Random number = " + ran);
                                System.out.println("Formula = " + compareAgainst);
                                System.out.println("Examine = " + examine);

                            }

                            if(ran > compareAgainst) //if the random float is greater than compare against, take the bad move

                            {

                                for (int a = 0; a < n; a++)
                                    for (int b = 0; b < n; b++)
                                        board[a][b] = tempBoard[a][b]; //take the move

                                cost = calculate(board, n);

                                currentTemp-= cooldown;



                                betterMove = true;
                            }

                            else //if not, do not take the move 
                            {

                                for (int a = 0; a < n; a++)
                                    for (int b = 0; b < n; b++)
                                        tempBoard[a][b] = board[a][b];



                                }

                            currentTemp-= cooldown;
                            betterMove = true;
                            }
                        }


                    }

                    i = n;
                    j = n;
                }
            }
        }

    }

我尝试了很多方法，例如将检查变量设置为负值或取棋盘状态之间差异的绝对值。此外，正在调用的计算函数基本上会扫描棋盘并返回有多少个皇后发生冲突，这是一个 int。如果需要更多说明，请告诉我。谢谢

Answer 1

也许这张图片中的公式和示例来自 OptaPlanner的文档也有帮助: