6

魔方能否通过遗传算法有效求解？

应该使用什么样的染色体编码？应该如何进行交叉和变异？

我正在使用这个立方体模型：

#ifndef RUBIKSCUBE_H_INCLUDED
#define RUBIKSCUBE_H_INCLUDED

#include "Common.h"
#include "RubiksSide.h"
#include "RubiksColor.h"
#include "RotationDirection.h"

class RubiksCube {
private:
    int top[3][3];
    int left[3][3];
    int right[3][3];
    int front[3][3];
    int back[3][3];
    int down[3][3];

    int (*sides[6])[3][3];

    std::string result;

    void spinSide(RubiksSide side) {
        static int buffer[ 3 ];

        if (side == TOP) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = left[i][2];
            }
            for (int i = 0; i < 3; i++) {
                left[i][2] = front[0][i];
            }
            for (int i = 0; i < 3; i++) {
                front[0][i] = right[3 - i - 1][0];
            }
            for (int i = 0; i < 3; i++) {
                right[i][0] = back[2][i];
            }
            for (int i = 0; i < 3; i++) {
                back[2][3 - i - 1] = buffer[i];
            }
        } else if (side == LEFT) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = down[i][2];
            }
            for (int i = 0; i < 3; i++) {
                down[3 - i - 1][2] = front[i][0];
            }
            for (int i = 0; i < 3; i++) {
                front[i][0] = top[i][0];
            }
            for (int i = 0; i < 3; i++) {
                top[i][0] = back[i][0];
            }
            for (int i = 0; i < 3; i++) {
                back[3 - i - 1][0] = buffer[i];
            }
        } else if (side == BACK) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = down[0][i];
            }
            for (int i = 0; i < 3; i++) {
                down[0][i] = left[0][i];
            }
            for (int i = 0; i < 3; i++) {
                left[0][i] = top[0][i];
            }
            for (int i = 0; i < 3; i++) {
                top[0][i] = right[0][i];
            }
            for (int i = 0; i < 3; i++) {
                right[0][i] = buffer[i];
            }
        } else if (side == RIGHT) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = down[i][0];
            }
            for (int i = 0; i < 3; i++) {
                down[i][0] = back[3 - i - 1][2];
            }
            for (int i = 0; i < 3; i++) {
                back[i][2] = top[i][2];
            }
            for (int i = 0; i < 3; i++) {
                top[i][2] = front[i][2];
            }
            for (int i = 0; i < 3; i++) {
                front[3 - i - 1][2] = buffer[i];
            }
        } else if (side == FRONT) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = down[2][i];
            }
            for (int i = 0; i < 3; i++) {
                down[2][i] = right[2][i];
            }
            for (int i = 0; i < 3; i++) {
                right[2][i] = top[2][i];
            }
            for (int i = 0; i < 3; i++) {
                top[2][i] = left[2][i];
            }
            for (int i = 0; i < 3; i++)
                left[2][i] = buffer[i];
        } else if (side == DOWN) {
            for (int i = 0; i < 3; i++) {
                buffer[i] = front[2][i];
            }
            for (int i = 0; i < 3; i++) {
                front[2][i] = left[i][0];
            }
            for (int i = 0; i < 3; i++) {
                left[i][0] = back[0][3 - i - 1];
            }
            for (int i = 0; i < 3; i++) {
                back[0][i] = right[i][2];
            }
            for (int i = 0; i < 3; i++) {
                right[3 - i - 1][2] = buffer[i];
            }
        }
    }

    void spinClockwise(int side[3][3], int times, RubiksSide index) {
        static int buffer[3][3];
        static int newarray[3][3];

        if (times == 0) {
            return;
        }

        /*
         * Transponse.
         */
        for (int j = 0; j < 3; j++) {
            for (int i = 0; i < 3; i++) {
                newarray[j][i] = side[i][j];
            }
        }
        /*
         * Rearrange.
         */
        for (int i = 0; i < 3; i++) {
            static int cache = 0;
            cache = newarray[i][0];
            newarray[i][0] = newarray[i][2];
            newarray[i][2] = cache;
        }

        spinSide(index);
        memcpy(buffer, newarray, sizeof(int)*3*3);

        for (int t = 1; t < times; t++) {
            for (int j = 0; j < 3; j++) {
                for (int i = 0; i < 3; i++) {
                    newarray[j][i] = buffer[i][j];
                }
            }
            for (int i = 0; i < 3; i++) {
                static int cache = 0;
                cache = newarray[i][0];
                newarray[i][0] = newarray[i][2];
                newarray[i][2] = cache;
            }

            spinSide(index);

            memcpy(buffer, newarray, sizeof(int)*3*3);
        }

        memcpy(side, buffer, sizeof(int)*3*3);
    }

    double euclidean(const RubiksCube &cube) const {
        double difference = 0.0;

        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                difference += abs(top[i][j]-cube.top[i][j]);
                difference += abs(left[i][j]-cube.left[i][j]);
                difference += abs(right[i][j]-cube.right[i][j]);
                difference += abs(front[i][j]-cube.front[i][j]);
                difference += abs(back[i][j]-cube.back[i][j]);
                difference += abs(down[i][j]-cube.down[i][j]);
            }
        }

        return difference;
    }

    double colors(const RubiksCube &cube) const {
        //TODO Change array with STL maps.
        static const double coefficients[7][7] = {
            {0, 0, 0, 0, 0, 0, 0},
            {0, 1, 2, 2, 2, 2, 4},
            {0, 2, 1, 2, 4, 2, 2},
            {0, 2, 2, 1, 2, 4, 2},
            {0, 2, 4, 2, 1, 2, 2},
            {0, 2, 2, 4, 2, 1, 2},
            {0, 4, 2, 2, 2, 2, 1},
        };

        double difference = 0.0;

        /*
         * Count matches for all sides.
         */
        for(int s=0; s<6; s++) {
            for(int i=0; i<3; i++) {
                for(int j=0; j<3; j++) {
                    /*
                     * If colors are equal calculate distance.
                     */
                    difference += coefficients[(*sides[s])[1][1]][(*sides[s])[i][j]];
                }
            }
        }

        return difference;
    }

    double hausdorff(const RubiksCube &cube) const {
        long ha = 0;
        long hb = 0;
        long result = 0;

        for(int m=0; m<3; m++) {
            for(int n=0; n<3; n++) {
                int distances[] = {0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

                for(int i=0, d=0; i<3; i++) {
                    for(int j=0; j<3; j++) {
                        distances[d++] = abs(top[m][n]-cube.top[i][j]);
                        distances[d++] = abs(left[m][n]-cube.left[i][j]);
                        distances[d++] = abs(right[m][n]-cube.right[i][j]);
                        distances[d++] = abs(front[m][n]-cube.front[i][j]);
                        distances[d++] = abs(back[m][n]-cube.back[i][j]);
                        distances[d++] = abs(down[m][n]-cube.down[i][j]);
                    }
                }

                int min = distances[0];
                for(int d=0; d<54; d++) {
                    if(distances[d] < min) {
                        min = distances[d];
                    }
                }

                if(min > ha) {
                    ha = min;
                }
            }
        }

        for(int m=0; m<3; m++) {
            for(int n=0; n<3; n++) {
                int distances[] = {0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

                for(int i=0, d=0; i<3; i++) {
                    for(int j=0; j<3; j++) {
                        distances[d++] = abs(top[i][j]-cube.top[m][n]);
                        distances[d++] = abs(left[i][j]-cube.left[m][n]);
                        distances[d++] = abs(right[i][j]-cube.right[m][n]);
                        distances[d++] = abs(front[i][j]-cube.front[m][n]);
                        distances[d++] = abs(back[i][j]-cube.back[m][n]);
                        distances[d++] = abs(down[i][j]-cube.down[m][n]);
                    }
                }

                int min = distances[0];
                for(int d=0; d<54; d++) {
                    if(distances[d] < min) {
                        min = distances[d];
                    }
                }

                if(min > hb) {
                    hb = min;
                }
            }
        }

        result = std::max(ha, hb);

        return(result);
    }

    friend std::ostream& operator<< (std::ostream &out, const RubiksCube &cube);

public:
    RubiksCube() {
        reset();

        sides[0] = &top;
        sides[1] = &left;
        sides[2] = &right;
        sides[3] = &front;
        sides[4] = &back;
        sides[5] = &down;
    }

    void reset() {
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                top[i][j] = GREEN;
                left[i][j] = PURPLE;
                right[i][j] = RED;
                front[i][j] = WHITE;
                back[i][j] = YELLOW;
                down[i][j] = BLUE;
            }
        }
    }

    double compare(const RubiksCube &cube) const {
        return euclidean(cube);
    }

    void callSpin(RubiksSide side, RotationDirection direction, int numberOfTimes) {
        if (numberOfTimes < 0) {
            numberOfTimes = -numberOfTimes;
            if(direction == CLOCKWISE) {
                direction = COUNTERCLOCKWISE;
            } else if(direction == COUNTERCLOCKWISE) {
                direction = CLOCKWISE;
            }
        }

        numberOfTimes %= 4;

        if (direction == CLOCKWISE) {
            if (side == NONE) {
                /*
                * Do nothing.
                */
            }
            if (side == TOP) {
                spinClockwise(top, numberOfTimes, TOP);
            }
            if (side == LEFT) {
                spinClockwise(left, numberOfTimes, LEFT);
            }
            if (side == RIGHT) {
                spinClockwise(right, numberOfTimes, RIGHT);
            }
            if (side == FRONT) {
                spinClockwise(front, numberOfTimes, FRONT);
            }
            if (side == BACK) {
                spinClockwise(back, numberOfTimes, BACK);
            }
            if (side == DOWN) {
                spinClockwise(down, numberOfTimes, DOWN);
            }
        }
    }

    void execute(std::string commands) {
        for(int i=0; i<commands.length(); i++) {
            callSpin((RubiksSide)commands[i], CLOCKWISE, 1);
        }
    }

    std::string shuffle(int numberOfMoves=0) {
        std::string commands = "";

        for(int i=0; i<numberOfMoves; i++) {
            switch(rand()%6) {
            case 0:
                commands+=(char)TOP;
                break;
            case 1:
                commands+=(char)LEFT;
                break;
            case 2:
                commands+=(char)RIGHT;
                break;
            case 3:
                commands+=(char)FRONT;
                break;
            case 4:
                commands+=(char)BACK;
                break;
            case 5:
                commands+=(char)DOWN;
                break;
            }
        }

        execute(commands);

        return commands;
    }

    const std::string& toString() {
        result = "";

        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(top[i][j]) + " ";
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(left[i][j]) + " ";
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(right[i][j]) + " ";
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(front[i][j]) + " ";
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(back[i][j]) + " ";
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                result += std::to_string(down[i][j]) + " ";
            }
        }

        /*
         * Trim spaces.
         */
        result.erase(result.size()-1, 1);
        result += '\0';

        return result;
    }

    void fromString(const char text[]) {
        std::string buffer(text);
        std::istringstream in(buffer);

        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> top[i][j];
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> left[i][j];
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> right[i][j];
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> front[i][j];
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> back[i][j];
            }
        }
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                in >> down[i][j];
            }
        }
    }
};

std::ostream& operator<< (std::ostream &out, const RubiksCube &cube) {
    for(int i=0; i<3; i++) {
        out << "      ";
        for(int j=0; j<3; j++) {
            out << cube.back[i][j] << " ";
        }
        out << std::endl;
    }

    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            out << cube.left[i][j] << " ";
        }
        for(int j=0; j<3; j++) {
            out << cube.top[i][j] << " ";
        }
        for(int j=0; j<3; j++) {
            out << cube.right[i][j] << " ";
        }
        for(int j=0; j<3; j++) {
            out << cube.down[i][j] << " ";
        }
        out << std::endl;
    }

    for(int i=0; i<3; i++) {
        out << "      ";
        for(int j=0; j<3; j++) {
            out << cube.front[i][j] << " ";
        }
        out << std::endl;
    }

    return out;
}

#endif
4

3 回答 3

6

免责声明：到目前为止，我还不是魔方专家，我什至从来没有解决过一个

通过 GA 求解给定的魔方

您有一个给定的配置，并且您想使用 GA 生成解决此特定配置的步骤序列。

表示

对于每个轴，存在三个可能的旋转，每个旋转在两个方向上。这给出了以下动作：

X1+, X1-, X2+, X2-, X3+, X3-,
Y1+, Y1-, Y2+, Y2-, Y3+, Y3-,
Z1+, Z1-, Z2+, Z2-, Z3+, Z3-

然后，基因型是这些移动的序列。

基因型

有两种可能：

  • 可变长度基因型
  • 固定长度基因型

可变长度基因型遵循我们事先不知道特定配置将采取多少移动来解决的想法。我稍后会回到这个变体。

也可以使用固定长度的基因型。尽管我们不知道特定配置需要多少步才能解决，但我们知道任何配置都可以在20步或更少的时间内解决。由于 20 意味着对于某些位置算法将被迫找到最佳解决方案（这可能非常困难），我们可以将基因型长度设置为 50 以赋予算法一些灵活性。

健康

您需要找到一个好的适应度度量来判断解决方案的质量。目前我想不出一个好的质量衡量标准，因为我不是魔方专家。但是，您可能应该将移动次数纳入您的健身测量中。稍后我会回到它。

此外，您应该决定您是在寻找任何解决方案还是一个好的解决方案。如果您正在寻找任何解决方案，您可以在找到的第一个解决方案处停下来。如果您正在寻找一个好的解决方案，您不会在找到第一个解决方案时停下来，而是会优化它的长度。然后，当您决定停止时（即在搜索所需的时间后），您就停止了。

运营商

两个基本算子 - 交叉和变异 - 可以与经典 GA 基本相同。唯一的区别是“位”没有两个状态，而是 18。即使使用可变长度的基因型，交叉也可以保持不变 - 您只需将两个基因型切成两部分并交换尾巴。与固定长度情况的唯一区别是切割不会在相同的位置，而是彼此独立。

膨胀

使用可变长度的基因型会带来一个令人不快的现象，即解的大小过度增长，而对适应度没有太大影响。在遗传编程（这是一个完全不同的主题）中，这被称为膨胀。这可以通过两种机制来控制。

我已经提到的第一个机制 - 将解决方案的长度纳入适应度。如果您寻找一个好的解决方案（即您不会停止寻找第一个解决方案），那么长度当然只是有效部分的长度（即从开始到结束的移动次数立方体），不计算其余部分。

我从语法进化（一种遗传编程算法，也使用线性可变长度基因型）中借用的另一种机制是pruning。修剪操作员采取解决方案并删除基因型的无效部分。

其他可能性

您还可以发展类似“策略”或策略的东西——一个一般规则，给定一个立方体，决定下一步要做什么。这是一项艰巨得多的任务，但绝对是可以进化的（意味着你可以使用进化来尝试找到它，而不是你最终会找到它）。您可以使用例如神经网络作为策略的表示，并使用一些神经进化概念和框架来完成此任务。

或者，您可以为给定的搜索算法（例如 A*）演化启发式算法（使用遗传编程）。A* 算法需要启发式方法来估计状态到最终状态的距离。这种启发式方法越准确，A* 算法找到解决方案的速度就越快。

最后的评论

根据我的经验，如果您对问题有所了解（在魔方的情况下您确实知道），那么使用专用的或至少是知情的算法来解决问题要好得多，而不是使用像 GA 这样几乎盲目的算法. 在我看来，魔方对 GA 来说不是一个好问题，或者说 GA 不是解决魔方的好算法。

于 2016-04-07T07:14:16.820 回答
2

我做了很多实验，我发现这样的染色体表示已经足够好了，但是遗传算法陷入了局部最优。魔方的解决方案是高度组合的，遗传算法不足以解决此类问题。

于 2017-10-08T13:36:49.217 回答
2

我大学的一个博士后写了他关于这个主题的论文并基本解决了它。据我记得，他使用了一些组合动作作为操作员。

https://link.springer.com/chapter/10.1007/978-3-642-12239-2_9

Nail El-Sourani、萨沙·豪克、马库斯·博尔施巴赫

进化算法计算的解决方案已经超越了解决各种问题的精确方法。魔方多目标优化问题就是这样一个领域。在这项工作中，我们提出了一种进化方法，通过建立在经典的 Thistlethwaite 方法的基础上，以较少的步数解决魔方。我们对 Thistlethwaite 的群转换引起的子问题复杂性进行群论分析，并从头开始设计进化算法，包括我们自定义适应度函数的详细推导。从这些观察中得到的实现经过了彻底的完整性和随机加扰测试，揭示了与精确方法相比具有竞争力的性能，而无需预先计算的查找表。

于 2019-07-04T13:45:50.467 回答