logo标签列表

魔方遗传算法求解器？

optimizationgenetic-algorithmsolverrubiks-cube
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
2
我不想说这是不可能的，但实现起来很可能非常困难。染色体必须定义魔方解决的行为。在更抽象的层面上，遗传算法将进化出解决魔方的算法。另一个选择可能是定义一个可以解决魔方的算法，然后遗传算法将进化出该算法的参数，但这使问题几乎变得微不足道。 - KDecker
1
此问题对于StackOverflow来说太过宽泛。我可能错了，但CS StackExchange可能是更好的选择？ - KDecker
2
那可能行得通，但只有在每次适应度评估中都使用魔方的初始排列时才有效。此外，您的遗传算法只能解决该魔方排列问题，而不能解决所有可能的排列问题。这有点像作弊.. // 如果使用不同的排列，则（我认为，但可能是错误的）您只是用遗传算法模拟随机性。对于每个单独的运行，使用给定染色体解决魔方问题的机会与在范围“0-可能的魔方排列”内生成相同随机数的机会相同。没有办法使染色体变得更加适合。 - KDecker
1
为什么不直接使用正确移动的百分比呢？无论“截止点”如何，其中最多正确移动的染色体似乎更适合解决魔方，或者至少在未来几代中会更好。 - KDecker
1
到目前为止，情况中可能存在局部最小值。染色体要么在解决特定排列问题方面得到明显改善（其适应度基于对该排列问题的选择解决方案），要么会消亡。 - KDecker
显示剩余4条评论
3个回答
6

免责声明：我并不是魔方专家，甚至从未解过一个魔方

使用遗传算法解决给定的魔方

你有一个给定的魔方配置，希望使用遗传算法生成一系列步骤来解决这个特定的配置。

表示方法

对于每个轴，有三种可能的旋转方式，每种方式又有两个方向。这样就得到了以下的移动：

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

基因型是这些移动的一个序列。

基因型

有两种可能性:

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

可变长度基因型遵循的思想是我们事先不知道特定配置需要多少步才能解决。稍后我会回到这个变体。

固定长度基因型也可以使用。即使我们不知道特定配置需要多少步才能解决，我们知道任何配置都可以在20步或更少内解决。由于20意味着对于某些位置，算法将被迫找到最优解（这可能相当困难），我们可以将基因型长度设置为50，以给算法一些灵活性。

适应度

您需要找到一个好的适应度度量来判断解决方案的质量。目前我无法想到一个好的质量度量，因为我不是魔方专家。然而，您可能应该将步数纳入适应度度量中。稍后我会再谈到它。

您应该决定是寻找任何解决方案还是好的解决方案。如果您正在寻找任何解决方案，可以停留在找到的第一个解决方案上。如果您正在寻找好的解决方案，则不会停留在找到的第一个解决方案上，而是优化其长度。当您决定停止搜索时（即经过所需的一定时间后），您就可以停止了。
运算符
两个基本运算符——交叉和变异——基本上与经典遗传算法相同。唯一的区别是“位”的状态不是两个，而是18个。即使使用可变长度的基因型，交叉也可以保持不变——您只需将两个基因型分成两个部分并交换尾部。与固定长度情况的唯一区别是切割位置不同，而是彼此独立。
膨胀
使用可变长度的基因型会带来一个令人不快的现象，即解决方案的大小过度增长，但对适应度影响不大。在遗传编程中（这是一个完全不同的话题），这称为膨胀。这可以通过两种机制来控制。
第一个机制我已经提到了 - 将解决方案的长度纳入适应度。如果您寻找一个好的解决方案（即您不止于找到第一个解决方案），那么长度当然只是有效部分的长度（即从开始到完成魔方的移动数，不包括其余部分）。
我从Grammatical Evolution（一种遗传编程算法，也使用线性、可变长度的基因型）中借鉴了另一个机制，即“修剪”。修剪运算符接受一个解决方案并删除基因型的非有效部分。
其他可能性
您也可以演变出像“策略”或者“战略”这样的东西 - 一般规则，可以在给定一个魔方的情况下决定下一步要移动哪个面。这是一个更加困难的任务，但绝对是可演化的（意味着您可以使用进化来尝试找到它，而不是最终会找到它）。您可以将神经网络用作策略的表示，并使用一些神经进化的概念和框架来完成此任务。

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

最后的话

根据我的经验，如果你对问题有所了解（在魔方的情况下是这样），最好使用专门的或至少知情的算法来解决问题，而不是使用类似 GA 这样几乎是盲目的算法。在我看来，魔方并不适合使用 GAs，或者说 GAs 不是解决魔方的好算法。

是的，没错。我想在遗传算法优化后获得一组旋转指令。我不太清楚人工神经网络如何用于这种组合问题。根据我对A*算法的了解，它最适合用于路径规划。 - Todor Balabanov
1
@TodorBalabanov 关于A*算法 - 你正在尝试找到一条路径 - 从初始位置，通过旋转，到达解决状态。关于ANN - 那只是一个想法...基本上，人工神经网络将代表一个函数，将魔方的配置映射到要采取的移动，但它可能不起作用。关于遗传求解 - 我会在一段时间内更新我的答案。 - zegkljan
我喜欢魔方问题，因为它是一个组合问题，我可以衡量遗传算法的效率。 - Todor Balabanov
2
一位我大学的博士后写了他的论文来解决这个问题。据我记得，他使用了一些组合移动作为运算符。通过进化算法计算出的解决方案已经超越了解决各种问题的精确方法。魔方多目标优化问题就是其中之一。在这项工作中，我们提出了一种进化方法来通过基于经典的Thistlethwaite方法来用较少的步骤解决魔方。我们对Thistlethwaite的群转换引起的子问题复杂性进行了群论分析，并从头开始设计了一个进化算法，包括我们自定义适应度函数的详细推导。由这些观察结果产生的实现经过了完整性和随机混淆的彻底测试，表现出了与无需预先计算查找表的精确方法相竞争的性能。原始回答：https://link.springer.com/chapter/10.1007/978-3-642-12239-2_9
2

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接