魔
方是否有可能通过遗传算法有效地解决？
应该使用什么样的染色体编码？交叉和突变应该如何完成？
我正在使用这个立方体模型：
#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 += ' ';
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-
然后基因型是这些移动的序列。
基因型
有两种可能性：
- 可变长度基因型
- 固定长度基因型
可变长度基因型遵循这样一种想法，即我们事先不知道特定配置需要多少步才能解决。我稍后会回到这个变体。
也可以使用固定长度的基因型。尽管我们不知道特定配置需要多少步才能解决，但我们知道任何配置都可以在 20 步或更短的时间内解决。由于 20 意味着对于某些位置，算法将被迫找到最佳解决方案（这可能非常困难），我们可以将基因型长度设置为 50，以便为算法提供一定的灵活性。
健康
您需要找到一个好的适应度措施来判断解决方案的质量。目前我想不出一个好的质量衡量标准，因为我不是魔方的专家。但是，您可能应该将移动次数纳入您的体能测量中。我稍后再谈。
此外，您还应该决定您是在寻找任何解决方案还是寻找一个好的解决方案。如果您正在寻找任何解决方案，则可以停在找到的第一个解决方案上。如果您正在寻找一个好的解决方案，您不会停留在找到第一个解决方案时，而是优化其长度。然后，当您决定停止时（即在花费搜索所需时间后），您就会停止。
运营商
两个基本运算符 - 交叉和突变 - 可以与经典GA基本相同。唯一的区别是，一个"位"不是两个状态，而是 18 个。即使使用可变长度的基因型，交叉也可以保持不变 - 您只需将两种基因型切成两部分并交换尾巴即可。与固定长度情况的唯一区别是切割不会位于相同的位置，而是彼此独立。
膨胀
使用可变长度基因型带来了令人不快的现象，即溶液大小的过度增长，对适应性没有很大影响。在遗传编程（这是一个完全不同的主题）中，这被称为膨胀。这可以通过两种机制进行控制。
我已经提到的第一种机制 - 将解决方案的长度纳入健身。如果你寻找一个好的解决方案（即你不会止步于找到第一个），长度当然只是有效部分的长度（即从开始到完成立方体的移动次数），不包括其余部分。
我从语法进化（一种遗传编程算法，也使用线性的、可变长度的基因型）中借用的另一种机制是修剪。修剪操作员采用解决方案并删除基因型的非有效部分。
其他可能性
你也可以发展一些类似"政策"或策略的东西——一个一般规则，给定一个立方体，决定下一步要做什么。这是一项困难得多的任务，但绝对是可以进化的（这意味着你可以用进化来尝试找到它，而不是你最终会找到它）。例如，您可以使用神经网络作为策略的表示，并使用一些神经进化概念和框架来完成此任务。
或者，您可以为给定的搜索算法（例如 A*）进化启发式（使用遗传编程）。A* 算法需要启发式算法来估计状态到最终状态的距离。这种启发式方法越准确，A* 算法找到解决方案的速度就越快。
结语
根据我的经验，如果您对问题有所了解（在魔方的情况下，您确实知道），那么最好使用专用或至少是知情的算法来解决问题，而不是使用像 GA 这样的几乎盲目的算法。在我看来，魔方对于 GA 来说不是一个好问题，或者更确切地说，GA 不是解决魔方的好算法。
我做了很多实验，我发现这样的染色体表示已经足够好了，但遗传算法被困在局部最优中。魔方的解是高度组合的，遗传算法不够强大，无法用于此类问题。
我大学的一位博士后写了关于这个主题的论文，并基本上解决了它。据我所知，他使用了一些组合动作作为操作员。
https://link.springer.com/chapter/10.1007/978-3-642-12239-2_9
钉子埃尔-苏拉尼， 萨沙·豪克， 马库斯·博尔施巴赫
进化算法计算的解决方案已经超越 解决各种问题的确切方法。魔方 多目标优化问题就是这样一个领域。在这项工作中，我们 提出一种进化方法来解决低 建立在经典蓟斯韦特的基础上的移动次数 方法。我们提供子问题的组理论分析 由Thistlethwaite的群转换引起的复杂性并设计一个 从头开始的进化算法，包括详细的 派生我们的自定义健身函数。实施 根据这些观察结果进行彻底的完整性测试 和随机加扰，揭示具有竞争力的性能 精确的方法，无需预先计算的查找表。