魔方遗传算法求解器？
Rubik's cube genetic algorithm solver?
魔方是否可以通过遗传算法高效求解？
应该使用什么样的染色体编码？应该如何进行交叉和变异？
我正在使用这个模型的立方体：
#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] = ⊤
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 += '[=10=]';
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
免责声明：到目前为止，我不是魔方方面的专家，我什至没有解过一个
通过 GA 解决给定的魔方
您有一个给定的配置，并且您想要使用 GA 生成解决此特定配置的步骤序列。
代表
对于每个轴，都有三个可能的旋转方向，每个方向都有两个方向。这给出了以下动作：
X1+, X1-, X2+, X2-, X3+, X3-,
Y1+, Y1-, Y2+, Y2-, Y3+, Y3-,
Z1+, Z1-, Z2+, Z2-, Z3+, Z3-
基因型就是这些动作的序列。
基因型
有两种可能：
- variable-length 基因型
- fixed-length 基因型
Variable-length genotype 遵循我们事先不知道特定配置需要多少步才能解决的想法。我稍后会回到这个变体。
Fixed-length 基因型也可以使用。即使我们不知道特定配置需要多少步才能解决，我们 知道 任何 配置都可以在 [=11] 中解决=].由于 20 意味着对于某些位置，算法将被迫找到最佳解决方案（这可能非常困难），我们可以将基因型长度设置为 50 以赋予算法一些灵活性。
健身
您需要找到一个好的适应度度量来判断解决方案的质量。目前我想不出一个很好的质量衡量标准，因为我不是魔方方面的专家。但是，您可能应该将移动次数纳入您的健身措施。稍后我会回来讨论它。
您还应该决定您是在寻找任何 解决方案还是一个好的解决方案。如果您正在寻找任何解决方案，您可以在找到的第一个解决方案处停止。如果您正在寻找一个好的解决方案，您不会在找到第一个解决方案时停下来，而是优化它的长度。然后在您决定停止时停止（即在搜索所需时间后）。
运算符
交叉和变异这两个基本算子与经典 GA 基本相同。唯一的区别是 "bit" 没有两个状态，而是 18 个状态。即使使用 variable-length 基因型，交叉也可以保持不变——你只需将两种基因型切成两半，然后交换尾巴。与 fixed-length 情况的唯一区别是切割不会在相同的位置，而是彼此独立。
膨胀
使用variable-length基因型会带来一个不愉快的现象，即解的大小过度增长，而对适应度没有太大影响。在遗传编程（这是一个完全不同的主题）中，这被称为 bloat。这可以通过两种机制来控制。
我已经提到的第一个机制——将解决方案的长度纳入适应度。如果您寻找一个好的解决方案（即您不会在找到第一个时停下来），长度当然只是有效部分的长度（即从开始到结束的移动次数立方体），不计算其余部分。
我从语法进化（一种也使用线性 variable-length 基因型的遗传编程算法）借用的另一种机制是 修剪 。修剪运算符采用解决方案并删除基因型的 non-effective 部分。
其他可能性
您还可以发展类似 "policy" 或策略的东西 - 一个通用规则，给定一个立方体，决定下一步要做什么。这是一项艰巨得多的任务，但绝对是可进化的（这意味着您可以使用进化来尝试找到它，而不是您最终会找到它）。您可能会使用例如神经网络作为策略的表示，并使用一些 neuro-evolution 概念和框架来完成此任务。
或者您可以为给定的搜索算法进化启发式算法（使用遗传编程），例如一种*。 A* 算法需要启发式来估计状态到最终状态的距离。这种启发式算法越准确，A* 算法找到解决方案的速度就越快。
最后的评论
根据我的经验，如果您对问题有所了解（对于 Rubik 魔方，您确实知道这一点），最好使用专门的或至少是知情的算法来解决问题，而不是使用几乎像GA这样的盲人。在我看来，魔方不是适合 GA 的问题，或者说 GA 不是解决魔方的好算法。
我做了很多实验，我发现这样的染色体表示已经足够好了，但是遗传算法会陷入局部最优。魔方的解决方案是高度组合的，遗传算法不足以解决此类问题。
我大学的一位 post 博士写了关于这个主题的论文并基本上解决了它。
据我所知，他使用了一些组合动作作为运算符。
https://link.springer.com/chapter/10.1007/978-3-642-12239-2_9
钉子 El-Sourani、萨沙·豪克、马库斯·博施巴赫
Solutions calculated by Evolutionary Algorithms have come to surpass
exact methods for solving various problems. The Rubik’s Cube
multiobjective optimization problem is one such area. In this work we
present an evolutionary approach to solve the Rubik’s Cube with a low
number of moves by building upon the classic Thistlethwaite’s
approach. We provide a group theoretic analysis of the subproblem
complexity induced by Thistlethwaite’s group transitions and design an
Evolutionary Algorithm from the ground up including detailed
derivation of our custom fitness functions. The implementation
resulting from these observations is thoroughly tested for integrity
and random scrambles, revealing performance that is competitive with
exact methods without the need for pre-calculated lookup-tables.
魔方是否可以通过遗传算法高效求解？
应该使用什么样的染色体编码？应该如何进行交叉和变异？
我正在使用这个模型的立方体：
#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] = ⊤
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 += '[=10=]';
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
免责声明：到目前为止，我不是魔方方面的专家，我什至没有解过一个
通过 GA 解决给定的魔方
您有一个给定的配置，并且您想要使用 GA 生成解决此特定配置的步骤序列。
代表
对于每个轴，都有三个可能的旋转方向，每个方向都有两个方向。这给出了以下动作：
X1+, X1-, X2+, X2-, X3+, X3-,
Y1+, Y1-, Y2+, Y2-, Y3+, Y3-,
Z1+, Z1-, Z2+, Z2-, Z3+, Z3-
基因型就是这些动作的序列。
基因型
有两种可能：
- variable-length 基因型
- fixed-length 基因型
Variable-length genotype 遵循我们事先不知道特定配置需要多少步才能解决的想法。我稍后会回到这个变体。
Fixed-length 基因型也可以使用。即使我们不知道特定配置需要多少步才能解决，我们 知道 任何 配置都可以在 [=11] 中解决=].由于 20 意味着对于某些位置，算法将被迫找到最佳解决方案（这可能非常困难），我们可以将基因型长度设置为 50 以赋予算法一些灵活性。
健身
您需要找到一个好的适应度度量来判断解决方案的质量。目前我想不出一个很好的质量衡量标准，因为我不是魔方方面的专家。但是，您可能应该将移动次数纳入您的健身措施。稍后我会回来讨论它。
您还应该决定您是在寻找任何 解决方案还是一个好的解决方案。如果您正在寻找任何解决方案，您可以在找到的第一个解决方案处停止。如果您正在寻找一个好的解决方案，您不会在找到第一个解决方案时停下来，而是优化它的长度。然后在您决定停止时停止（即在搜索所需时间后）。
运算符
交叉和变异这两个基本算子与经典 GA 基本相同。唯一的区别是 "bit" 没有两个状态，而是 18 个状态。即使使用 variable-length 基因型，交叉也可以保持不变——你只需将两种基因型切成两半，然后交换尾巴。与 fixed-length 情况的唯一区别是切割不会在相同的位置，而是彼此独立。
膨胀
使用variable-length基因型会带来一个不愉快的现象，即解的大小过度增长，而对适应度没有太大影响。在遗传编程（这是一个完全不同的主题）中，这被称为 bloat。这可以通过两种机制来控制。
我已经提到的第一个机制——将解决方案的长度纳入适应度。如果您寻找一个好的解决方案（即您不会在找到第一个时停下来），长度当然只是有效部分的长度（即从开始到结束的移动次数立方体），不计算其余部分。
我从语法进化（一种也使用线性 variable-length 基因型的遗传编程算法）借用的另一种机制是 修剪 。修剪运算符采用解决方案并删除基因型的 non-effective 部分。
其他可能性
您还可以发展类似 "policy" 或策略的东西 - 一个通用规则，给定一个立方体，决定下一步要做什么。这是一项艰巨得多的任务，但绝对是可进化的（这意味着您可以使用进化来尝试找到它，而不是您最终会找到它）。您可能会使用例如神经网络作为策略的表示，并使用一些 neuro-evolution 概念和框架来完成此任务。
或者您可以为给定的搜索算法进化启发式算法（使用遗传编程），例如一种*。 A* 算法需要启发式来估计状态到最终状态的距离。这种启发式算法越准确，A* 算法找到解决方案的速度就越快。
最后的评论
根据我的经验，如果您对问题有所了解（对于 Rubik 魔方，您确实知道这一点），最好使用专门的或至少是知情的算法来解决问题，而不是使用几乎像GA这样的盲人。在我看来，魔方不是适合 GA 的问题，或者说 GA 不是解决魔方的好算法。
我做了很多实验，我发现这样的染色体表示已经足够好了，但是遗传算法会陷入局部最优。魔方的解决方案是高度组合的，遗传算法不足以解决此类问题。
我大学的一位 post 博士写了关于这个主题的论文并基本上解决了它。 据我所知，他使用了一些组合动作作为运算符。
https://link.springer.com/chapter/10.1007/978-3-642-12239-2_9
钉子 El-Sourani、萨沙·豪克、马库斯·博施巴赫
Solutions calculated by Evolutionary Algorithms have come to surpass exact methods for solving various problems. The Rubik’s Cube multiobjective optimization problem is one such area. In this work we present an evolutionary approach to solve the Rubik’s Cube with a low number of moves by building upon the classic Thistlethwaite’s approach. We provide a group theoretic analysis of the subproblem complexity induced by Thistlethwaite’s group transitions and design an Evolutionary Algorithm from the ground up including detailed derivation of our custom fitness functions. The implementation resulting from these observations is thoroughly tested for integrity and random scrambles, revealing performance that is competitive with exact methods without the need for pre-calculated lookup-tables.