Tod*_*nov 6 optimization solver rubiks-cube genetic-algorithm
是否有可能通过遗传算法有效地解决魔方？
应该使用什么样的染色体编码？应该如何进行交叉和变异？
我正在使用这个立方体模型：
#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 += '\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
免责声明：到目前为止，我不是魔方方面的专家，我什至从未解决过
您有一个给定的配置，并且希望使用 GA 来生成解决此特定配置的步骤序列。
对于每个轴，都有三个可能的旋转，每个旋转方向都在两个方向上。这给出了以下动作：
X1+, X1-, X2+, X2-, X3+, X3-,
Y1+, Y1-, Y2+, Y2-, Y3+, Y3-,
Z1+, Z1-, Z2+, Z2-, Z3+, Z3-
那么基因型就是这些动作的序列。
有两种可能：
可变长度基因型遵循的想法是我们事先不知道特定配置需要多少移动才能解决。稍后我会回到这个变体。
也可以使用固定长度的基因型。尽管我们不知道有多少移动将在特定的配置拿地解决，我们知道的是任何配置中可以解决以下20个移动。由于 20 意味着对于某些位置，算法将被迫找到最佳解决方案（这可能非常困难），因此我们可以将基因型长度设置为 50，以便为算法提供一些灵活性。
您需要找到一个良好的适应度度量来判断解决方案的质量。目前我想不出一个好的质量衡量标准，因为我不是魔方方面的专家。但是，您可能应该在您的健身测量中加入移动次数。稍后我会回到这个话题。
此外，您应该决定是在寻找任何解决方案还是一个好的解决方案。如果您正在寻找任何解决方案，您可以在找到的第一个解决方案处停下来。如果您正在寻找一个好的解决方案，您不会在找到第一个解决方案时停下来，而是优化其长度。然后，当您决定停止时（即在搜索所需的时间后），您将停止。
两个基本算子——交叉和变异——可以与经典遗传算法基本相同。唯一的区别是“位”没有两种状态，而是 18。即使使用可变长度基因型，交叉也可以保持不变——您只需将两种基因型切成两部分并交换尾部。与固定长度情况的唯一区别是切口不会在相同的位置，而是相互独立。
使用变长基因型带来了一个令人不快的现象，即解决方案的大小过度增长，而对适应度没有太大影响。在遗传编程（这是完全不同的主题）中，这称为bloat。这可以通过两种机制来控制。
我已经提到的第一个机制 - 将解决方案的长度合并到适应度中。如果你寻找一个好的解决方案（即你不停止寻找第一个），长度当然只是有效部分的长度（即从开始移动到完成移动的次数立方体），不计算其余部分。
我从 Grammatical Evolution（一种也使用线性可变长度基因型的遗传编程算法）借用的另一种机制是pruning。修剪算子采用解决方案并删除基因型的无效部分。
您还可以演化出诸如“策略”或策略之类的东西 - 一个通用规则，可以根据给定的立方体来决定下一步要做什么。这是一项艰巨的任务，但绝对可以进化（意味着您可以使用进化来尝试找到它，而不是您最终会找到它）。您可以使用例如神经网络作为策略的表示，并使用一些神经进化概念和框架来完成此任务。
或者，您可以为给定的搜索算法（例如 A*）演化出启发式算法（使用遗传编程）。A* 算法需要一个启发式来估计一个状态到最终状态的距离。这种启发式算法越准确，A* 算法找到解决方案的速度就越快。
根据我的经验，如果您对问题有所了解（在魔方的情况下您确实知道），最好使用专门的或至少是明智的算法来解决问题，而不是使用像 GA 这样几乎盲目的算法. 在我看来，魔方对 GA来说不是一个好问题，或者说 GA 不是解决魔方的好算法。