Cycle Crossover (CX)<\/em><\/strong>\u7b97\u5b50 \u5bfb\u627e\u7236\u4ee3\u57fa\u56e0\u7684\u73af\uff0c\u73af\u5916\u57fa\u56e0\u7684\u5168\u5c40\u4e92\u6362\u5e76\u4e0d\u4f1a\u5f71\u54cd\u57fa\u56e0\u7ed3\u6784 ![\"image-20200605181908899\"](\"http:\/\/kodo.cyasylum.top\/2020\/06\/05\/be8b14329eb34.png\")
<\/li><\/ol>\n\n\n\n\u7ed3\u679c\u8fd9\u4e48\u770b\u4e0b\u6765\uff0c\u4ea4\u53c9\u672a\u5fc5\u6709\u6211\u4eec\u60f3\u8c61\u5f97\u90a3\u4e48\u590d\u6742\uff1f<\/p>\n\n\n\n
\u4ee3\u7801\u6784\u5efa<\/h2>\n\n\n\n
\u90a3\u4e48\u8ba9\u6211\u4eec\u6765\u8003\u8651\u4e00\u4e0b\uff0c\u8981\u5982\u4f55\u901a\u8fc7\u4ee3\u7801\u7684\u5f62\u5f0f\u6784\u5efa\u9057\u4f20\u7b97\u6cd5<\/p>\n\n\n\n
\u4e2a\u4f53\u6784\u5efa<\/h3>\n\n\n\n
\u9996\u5148\u662f\u8003\u8651\u6784\u5efa\u4e2a\u4f53\uff0c\u53ca\u57fa\u56e0\u7ec4\uff0c\u4ece\u6700\u539f\u59cb\u7684\u4e16\u4ee3\u800c\u8a00\uff0c\u901a\u5e38\u90fd\u662f\u968f\u673a\u751f\u6210\u7684\u5e8f\u5217\u3002\u540c\u65f6\u6211\u4eec\u4e5f\u4e0d\u8003\u8651\u8f83\u4e3a\u590d\u6742\u7684\u57fa\u56e0\u7ed3\u6784\uff0c\u521b\u5efa\u4e00\u4e2a\u539f\u59cb\u7684\u57fa\u56e0\u7c7b<\/p>\n\n\n\n
class Unit {\n public:\n vector<int> Gene;\n size_t Gene_length;\n};<\/code><\/pre>\n\n\n\n\u57fa\u7840\u6784\u9020<\/h4>\n\n\n\n
\u540c\u65f6\uff0c\u7ed9\u51fa\u6700\u7b80\u5355\u7684\u968f\u673a\u6784\u9020\u7b97\u6cd5<\/p>\n\n\n\n
Unit(const size_t L, const bool init_ = true) : Gene_length(L) {\n if (init_) randperm();\n}\n\/\/\u751f\u6210\u968f\u673a\u57fa\u56e0\nvoid randperm() {\n vector<int> serial_num;\n \/\/\u751f\u6210\u5e8f\u5217\uff0c\u6b64\u5904\u4ece1\u5f00\u59cb\uff0c\u89c6\u540e\u7eed\u60c5\u51b5\u53ef\u6539\u4e3a\u4ece0\u5f00\u59cb\n for (int i = 1; i <= Gene_length; ++i) serial_num.push_back(i);\n \/\/\u6fc0\u60c5\u6253\u4e71\n for (int i = Gene_length; i > 0; i--) {\n int index = u(gen) % i;\n Gene.push_back(serial_num[index]);\n serial_num.erase(serial_num.begin() + index);\n }\n}<\/code><\/pre>\n\n\n\n\u7e41\u6b96\u4ea4\u53c9<\/h4>\n\n\n\n\/\/ Cycle Crossover \u4ea4\u53c9\nUnit& CX_SIMPLE(const Unit& b) {\n Unit* result = new Unit(Gene_length, false);\n int nb = u(gen); \/\/\u9501\u5b9a\u968f\u673a\u78b1\u57fa\uff08\u4f4d\u4e8e\u57fa\u56e01\u4e0a\n vector<int> temp;\n while (count(temp.begin(), temp.end(), nb) == 0) {\n \/\/\u67e5\u627e\u78b1\u57fa\u5728\u57fa\u56e01\u4e0a\u7684\u4f4d\u7f6e\n int iter = findPosVector(Gene, nb);\n \/\/\u50a8\u5b58\u5f53\u524d\u78b1\u57fa\n temp.push_back(nb);\n \/\/\u6307\u5411\u4e0b\u4e00\u78b1\u57fa\n nb = b.Gene[iter];\n }\n \/\/\u5bf9\u4e0d\u5728\u73af\u5185\u7684\u57fa\u56e0\u8fdb\u884c\u4ea4\u53c9\u64cd\u4f5c\n for (size_t i = 0; i < Gene_length; i++)\n if (count(temp.begin(), temp.end(), Gene[i]) == 0)\n result->Gene.push_back(Gene[i]);\n else\n result->Gene.push_back(b.Gene[i]);\n return *result;\n}\n\n\/\/ \u7528\u4e8e\u67e5\u627e\u5143\u7d20\u4f4d\u7f6e\u7684\u51fd\u6570\nint findPosVector(vector<int> input, const int number) {\n vector<int>::iterator iter = std::find(\n input.begin(), input.end(), number); \/\/\u8fd4\u56de\u7684\u662f\u4e00\u4e2a\u8fed\u4ee3\u5668\u6307\u9488\n if (iter == input.end()) {\n return -1;\n } else {\n return std::distance(input.begin(), iter);\n }\n}<\/code><\/pre>\n\n\n\n\u9057\u4f20\u53d8\u5f02<\/h4>\n\n\n\n\/\/ \u5077\u61d2\u7528\u7684\u53d8\u5f02\nUnit& VG_SIMPLE_BACK() {\n int index = u(gen);\n Gene.push_back(Gene[index]);\n Gene.erase(Gene.begin() + index);\n return *this;\n}<\/code><\/pre>\n\n\n\n\u79cd\u7fa4\u6784\u5efa<\/h3>\n\n\n\n
\u6211\u4eec\u9996\u5148\u8003\u8651\u79cd\u7fa4\u9700\u8981\u6709\u4ec0\u4e48\u5c5e\u6027<\/p>\n\n\n\n
\u9996\u5148\uff0c\u79cd\u7fa4\u662f\u4e2a\u4f53\u7684\u96c6\u5408\uff0c\u4e5f\u5c31\u662f\u521b\u5efa\u4e00\u4e2a\u6570\u7ec4\u5b58\u653e\u79cd\u7fa4\u4e2d\u6240\u6709\u7684\u4e2a\u4f53\uff0c\u5176\u6b21\u4fbf\u662f\u79cd\u7fa4\u5bb9\u91cf\uff0c\u5373\u786e\u5b9a\u79cd\u7fa4\u4e2d\u7684\u4e2a\u4f53\u6570\u76ee\uff0c\u5373\u79cd\u7fa4\u5bb9\u91cf\uff0c\u5176\u6b21\u662f\u4ea4\u53c9\u4e0e\u53d8\u5f02\u7684\u6982\u7387\uff0c\u4ece\u8d44\u6599\u770b\u6765\u901a\u5e38\u88ab\u8bbe\u7f6e\u4e3a1\u548c0.1\u3002<\/p>\n\n\n\n
\u540c\u65f6\uff0c\u4e2a\u4f53\u7684\u4ef7\u503c\u4e5f\u662f\u7531\u79cd\u7fa4\u9700\u8981\u6765\u5b9a\u4e49\u7684\uff0c\u6211\u4eec\u5728\u79cd\u7fa4\u4e2d\u9700\u8981\u5efa\u7acb\u4ef7\u503c\u5224\u5b9a\u51fd\u6570\uff0c\u4ee5\u53ca\u8fed\u4ee3\u8fdb\u5316\u51fd\u6570<\/p>\n\n\n\n
\u8fd9\u662f\u6211\u6784\u60f3\u7684\u6846\u67b6<\/p>\n\n\n\n
class Group {\n private:\n \/\/\u5185\u90e8\u53c2\u6570\n \/\/\u4e2a\u4f53\u96c6\u5408\n vector<Unit> Indiv;\n \/\/\u4ef7\u503c\u8bc4\u65ad\n vector<float> Values;\n \/\/\u521b\u5efa\u4ef7\u503c\u5bf9\uff0c\u65b9\u4fbf\u6392\u5e8f\n vector<pair<Unit, float>> unit_value;\n\n \/\/\u4f18\u79c0\u5b50\u4ee3\n Unit* best_u;\n float best_v;\n\n \/\/\u5916\u90e8\u53c2\u6570\n \/\/\u57fa\u56e0\u957f\u5ea6(\u5f53\u524d\u95ee\u9898\u4e3a\u57ce\u5e02\u6570)\n size_t Gene_length;\n \/\/\u79cd\u7fa4\u5bb9\u91cf\n size_t Group_size;\n \/\/\u8fed\u4ee3\u6b21\u6570\n size_t Iter_times;\n \/\/\u4ea4\u53c9\u6982\u7387\n float Cross_rate;\n \/\/\u53d8\u5f02\u6982\u7387\n float Vg_rate;\n\n \/\/\u95ee\u9898\u53c2\u6570\n vector<vector<int>> param;\n\n public:\n Group(size_t Gene_l, size_t Group_s, size_t Iter_t,\n vector<vector<int>> param_t, float Vg_r = 0.1, float Cross_r = 1)\n : Gene_length(Gene_l),\n Group_size(Group_s),\n Iter_times(Iter_t),\n Cross_rate(Cross_r),\n Vg_rate(Vg_r) {\n best_u = new Unit(Gene_length);\n \/\/\u586b\u5145\u79cd\u7fa4\u5bb9\u91cf\u4e2a\u957f\u5ea6\u4e3a\u6307\u5b9a\u7684\u4e2a\u4f53\n for (size_t i = 0; i < Group_size; i++) {\n Unit unit(Gene_length);\n Indiv.push_back(unit);\n }\n param = param_t;\n Compute_Values();\n for (size_t i = 0; i < Indiv.size(); i++) {\n pair<Unit, float> temp = make_pair(Indiv[i], Values[i]);\n unit_value.push_back(temp);\n }\n sort(unit_value.begin(), unit_value.end(), value_cmp);\n best_u = new Unit(unit_value[0].first);\n best_v = unit_value[0].second;\n }\n void Compute_Values() {}\n void Evolution() {}\n void Run() {}\n};<\/code><\/pre>\n\n\n\n\u4ef7\u503c\u8ba1\u7b97<\/h4>\n\n\n\n
\u5bf9\u79cd\u7fa4\u5185\u4e2a\u4f53\u4ef7\u503c\u7684\u8ba1\u7b97\u662f\u76f8\u5bf9\u7b80\u5355\u7684\uff0c\u76f4\u63a5\u4e22\u51fd\u6570\u5566<\/p>\n\n\n\n
void Compute_Values() {\n for (size_t i = 0; i < Indiv.size(); i++) {\n float Value = 0; \/\/\u5f53\u524d\u4e2a\u4f53\u4ef7\u503c\n \/\/\u68c0\u7d22\u53c2\u6570\u8868\u4e2d\u4e24\u57ce\u5e02\u7684\u8ddd\u79bb\uff0c\u5e76\u7d2f\u8ba1\u52a0\u5728\u4e2a\u4f53\u4ef7\u503c\u4e0a\uff08\u4ef7\u503c\u8d8a\u4f4e\u7684\u4e2a\u4f53\u8d8a\u597d\uff08\uff1f\n for (size_t j = 0; j < Gene_length - 1; j++)\n Value += param[Indiv[i].Gene[j] - 1][Indiv[i].Gene[j + 1] - 1];\n Value +=\n param[Indiv[i].Gene[Gene_length - 1] - 1][Indiv[i].Gene[0] - 1];\n\n Values.push_back(Value);\n }\n }<\/code><\/pre>\n\n\n\n\u79cd\u7fa4\u8fdb\u5316<\/h4>\n\n\n\n
\u90a3\u4e48\u63a5\u4e0b\u6765\uff0c\u6211\u4eec\u8003\u8651\u79cd\u7fa4\u7684\u8fdb\u5316<\/p>\n\n\n\n
\u4e00\u4e2a\u79cd\u7fa4\u7684\u8fdb\u5316\u62e5\u6709\u54ea\u4e9b\u6307\u6807\u5462\uff0c\u8fd9\u662f\u4e2a\u597d\u95ee\u9898<\/p>\n\n\n\n
\u5148\u4e0d\u8003\u8651\u57fa\u56e0\u7684\u5bff\u547d\uff0c\u4ec5\u4ec5\u8003\u8651\u79cd\u7fa4\u7684\u9694\u4ee3\u9057\u4f20<\/p>\n\n\n\n
\u9996\u5148\u6211\u4eec\u9700\u8981\u7684\u662f\u5bf9\u79cd\u7fa4\u8fdb\u884c\u4e00\u4ee3\u7e41\u6b96\uff0c\u5728\u8fd9\u91cc\u6211\u4eec\u53ef\u80fd\u4f1a\u8003\u8651\u4ef7\u503c\u8f83\u9ad8\uff08\u5373values\u8f83\u4f4e\uff09\u7684\u4e2a\u4f53\u66f4\u9ad8\u4f18\u5148\u7ea7\u540c\u76f8\u4f3c\u7684\u4e2a\u4f53\u8fdb\u884c\u7e41\u6b96\uff0c\u4f46\u662f\u8fd9\u4e5f\u51b3\u5b9a\u4e86\u79cd\u7fa4\u662f\u5426\u9700\u8981\u7ecf\u8fc7\u4e24\u8f6e\u6392\u5e8f\u3002\u7531\u6b64\u7ecf\u8fc7\u4ea4\u53c9\u53ca\u53d8\u5f02\uff0c\u6211\u4eec\u4fbf\u80fd\u83b7\u5f97\u7b2c\u4e00\u4ee3\u5b50\u4ee3\u3002\u5e76\u5c06\u5b50\u4ee3\u96c6\u5408\u4e0e\u7236\u4ee3\u96c6\u5408\u8fdb\u884c\u5e76\u96c6\u5904\u7406\uff0c\u5e76\u6dd8\u6c70\u4ef7\u503c\u8f83\u4f4e\uff0c\u4e14\u8d85\u51fa\u4e86\u79cd\u7fa4\u5bb9\u91cf\u7684\u4e2a\u4f53\u3002<\/p>\n\n\n\n
\u7ed9\u51fa\u6211\u7684\u5b9e\u73b0\uff1f<\/p>\n\n\n\n
static bool value_cmp(const pair<Unit, float>& a,\n const pair<Unit, float>& b) {\n return a.second < b.second; \/\/\u6839\u636esecond\u7684\u503c\u5347\u5e8f\u6392\u5e8f\n }\n void Evolution() {\n \/\/\u8003\u8651\u5a5a\u5ac1\u548c\u7e41\u6b96\n bool married[Group_size] = {0};\n\n \/\/\u53ea\u6709\u524d\u4e00\u534a\u7684\u4eba\u80fd\u4e3b\u52a8\u5a5a\u5ac1\uff0c\u5047\u8bbe\u53ea\u80fd\u627e\u4f4e\u4e8e\u81ea\u5df1\u7684\uff08x\n \/\/\u7b49\u4f1a\u513f\u6539\u6210\u6b63\u6001\u5206\u5e03\u7684\u6570\u636e\n for (size_t i = 0; i < Group_size \/ 2; i++) {\n \/\/\u8ba8\u8001\u5a46\uff08\uff1f\n \/\/ int wife = (i + rand() % (Group_size \/ 2)) % Group_size;\n \/\/\u5929\u547d\n \/\/ int wife = rand() % Group_size;\n int wife = abs(int(dis(gen) * Group_size \/ 2)) % Group_size;\n \/\/\u5982\u679c\u5df2\u5a5a\n if (married[wife] || married[i]) continue;\n\n \/\/\u7ed3\u5a5a\u767b\u8bb0\uff08\u632a\u5230\u524d\u9762\u6765\uff0c\u907f\u514d\u4e86\u672a\u5a5a\u5148\u5b55\n married[i] = true;\n married[wife] = true;\n\n \/\/\u7e41\u6b96\uff0c\u4ee5\u53ca\u662f\u5426\u53d8\u5f02\n if (rand() % 100 > Vg_rate * 100)\n Indiv.push_back(Indiv[i].CX_SIMPLE(Indiv[wife]));\n else {\n Indiv.push_back(Indiv[i].CX_SIMPLE(Indiv[wife]));\n Indiv[i].VG_SIMPLE_BACK();\n }\n }\n\n \/\/\u5efa\u7acb\u4ef7\u503c\u7b49\u7ea7\u8868\u5355\n Values.clear();\n unit_value.clear();\n Compute_Values();\n for (size_t i = 0; i < Indiv.size(); i++) {\n pair<Unit, float> temp = make_pair(Indiv[i], Values[i]);\n unit_value.push_back(temp);\n }\n sort(unit_value.begin(), unit_value.end(), value_cmp);\n \/\/\u5efa\u7acb\u65b0\u751f\u4ee3\u6570\u636e\u5e93\uff0c\u843d\u540e\u4e8e\u65f6\u4ee3\u7684\u52c7\u58eb\u4eec\u4f9d\u65e7\u671b\u7740\u4f60\n Values.clear();\n Indiv.clear();\n for (size_t i = 0; i < Group_size; i++) {\n Values.push_back(unit_value[i].second);\n Indiv.push_back(unit_value[i].first);\n }\n if (best_v > unit_value[0].second) {\n best_u = new Unit(unit_value[0].first);\n best_v = unit_value[0].second;\n }\n }<\/code><\/pre>\n\n\n\n\u8fd0\u884c\/\u8bad\u7ec3<\/h4>\n\n\n\n void Run() {\n int t = Iter_times;\n while (t--) Evolution();\n best_u->print();\n cout << \"best has value:\" << best_v << endl;\n }<\/code><\/pre>\n\n\n\n\u8fd0\u884c\u6d4b\u8bd5<\/h3>\n\n\n\n
\u8ddd\u79bb\u77e9\u9635\u662fcsdn\u4e0a\u6252\u6765\u7684hhhh\uff0c\u4e4b\u540e\u51c6\u5907\u5728\u66f4\u68d2\u7684\u6570\u636e\u4e0a\u8dd1\u4e2a\u723d<\/p>\n\n\n\n
int main() {\n int test_times = 10;\n\n const int city_num = 10; \/\/\u57ce\u5e02\u6570\u91cf\n const int unit_num = 300; \/\/\u7fa4\u4f53\u89c4\u6a21\n const float vg_pro = 0.1; \/\/\u53d8\u5f02\u6982\u7387\n const int gen_maxn = 500; \/\/\u6700\u5927\u8fed\u4ee3\u6570\n \/\/\u57ce\u5e02\u8ddd\u79bb\u8868\uff0c\u4f5c\u4e3a\u5168\u5c40\u53c2\u6570\n int length_table[10][10] = {\n\n {0, 1, 1272, 2567, 1653, 2097, 1425, 1177, 3947, 1},\n\n {1, 0, 1, 2511, 1633, 2077, 1369, 1157, 3961, 1518},\n\n {1272, 1, 0, 1, 380, 1490, 821, 856, 3660, 385},\n\n {2567, 2511, 1, 0, 1, 2335, 1562, 2165, 3995, 933},\n\n {1653, 1633, 380, 1, 0, 1, 1041, 1135, 3870, 456},\n\n {2097, 2077, 1490, 2335, 1, 0, 1, 920, 2170, 1920},\n\n {1425, 1369, 821, 1562, 1041, 1, 0, 1, 4290, 626},\n\n {1177, 1157, 856, 2165, 1135, 920, 1, 0, 1, 1290},\n\n {3947, 3961, 3660, 3995, 3870, 2170, 4290, 1, 0, 1},\n\n {1, 1518, 385, 993, 456, 1920, 626, 1290, 1, 0}};\n\n vector<vector<int>> vt;\n int row = city_num;\n int column = city_num;\n\n \/\/\u628a\u57ce\u5e02\u8ddd\u79bb\u90bb\u63a5\u77e9\u9635\u5199\u5165vector\n for (int i = 0; i < row; i++) {\n vector<int> tmp;\n for (int j = 0; j < column; j++) tmp.push_back(length_table[i][j]);\n vt.push_back(tmp);\n }\n\n \/\/\u6d4b\u8bd5\u6a21\u578b\n vector<Group> rua;\n int t = test_times;\n\n while (t--) rua.push_back(Group(city_num, unit_num, gen_maxn, vt, vg_pro));\n\n for (size_t i = 0; i < test_times; i++) rua[i].Run();\n\n system(\"pause\");\n return 0;\n}<\/code><\/pre>\n\n\n\n\u6211\u5f97\u53bb\u4ea4\u4f5c\u4e1a\u4e86\uff08\uff1f<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4eba\u5de5\u667a\u80fd\u5bfc\u8bba\u6740\u6211 \u6562\u4fe1\uff1f\u8001\u5e08\u5728\u8ddf\u6211\u4eec\u8bb2\u4e86\u9057\u4f20\u4e4b\u540e\uff0c\u5e03\u7f6e\u4e86\u9057\u4f20\u7b97\u6cd5\u7684\u5927\u4f5c\u4e1a\u3002 \u53ea\u8bb2\u9057\u4f20\u6ca1\u8bb2\u7b97\u6cd5\uff0c\u4f60\u4eec\u6562\u4fe1\uff1f\uff1f\u4f60\u4eec\u6562\u4fe1\uff1f\uff1f \u786c\u7740\u5934\u76ae\u51b2 …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"emotion":"","emotion_color":"","title_style":"","license":"","footnotes":""},"categories":[10,19],"tags":[37,38,35,36],"class_list":["post-236","post","type-post","status-publish","format-standard","hentry","category-10","category-19","tag-ga","tag-tsp","tag-35","tag-36"],"_links":{"self":[{"href":"http:\/\/blog.cyasylum.top\/index.php\/wp-json\/wp\/v2\/posts\/236","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.cyasylum.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.cyasylum.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.cyasylum.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.cyasylum.top\/index.php\/wp-json\/wp\/v2\/comments?post=236"}],"version-history":[{"count":4,"href":"http:\/\/blog.cyasylum.top\/index.php\/wp-json\/wp\/v2\/posts\/236\/revisions"}],"predecessor-version":[{"id":268,"href":"http:\/\/blog.cyasylum.top\/index.php\/wp-json\/wp\/v2\/posts\/236\/revisions\/268"}],"wp:attachment":[{"href":"http:\/\/blog.cyasylum.top\/index.php\/wp-json\/wp\/v2\/media?parent=236"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.cyasylum.top\/index.php\/wp-json\/wp\/v2\/categories?post=236"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.cyasylum.top\/index.php\/wp-json\/wp\/v2\/tags?post=236"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"img\"\/](\"http:\/\/kodo.cyasylum.top\/2020\/06\/05\/a6882e496be60.jpg\")
<\/figure>\n\n\n\n![\"TSP\"\/](\"http:\/\/kodo.cyasylum.top\/2020\/06\/05\/f1f0605b542cd.png\")
<\/figure>\n\n\n\n![\"image-20200605181826213\"](\"http:\/\/kodo.cyasylum.top\/2020\/06\/05\/0c4fef8f6c261.png\")
<\/li>![\"image-20200605181843152\"](\"http:\/\/kodo.cyasylum.top\/2020\/06\/05\/9ae168b9200f4.png\")
<\/li>