/
ga.cpp
109 lines (101 loc) · 2.81 KB
/
ga.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <random>
#include <map>
using namespace std;
const int GEN = 10;
int N;
vector<vector<int>> init(vector<vector<int>>);
vector<vector<int>> shuffle(vector<vector<int>>);
void select();
void cross();
void mutation();
double eval(vector<int>, double**);
bool second_cmp(const pair<vector<int>, double>& a, const pair<vector<int>, double>& b);
int main() {
FILE *fp;
char fname[] = "../test.txt";
int a, b;
double dist;
if((fp = fopen(fname,"r"))==NULL){
printf("errer\n");
return -1;
}else{
printf("%s file opened\n",fname);
}
fscanf(fp,"%d",&N);
double **net;
net = (double**)malloc(sizeof(double*)*N);
for(int i = 0; i < N; i++) net[i] = (double*)malloc(sizeof(double)*N);
vector<vector<int>> gen(GEN, vector<int>(N));
while(fscanf(fp,"%d %d %lf",&a, &b, &dist)!=EOF) {
net[a][b] = net[b][a] = dist;
}
fclose(fp);
gen = init(gen);
vector<pair<vector<int>, double>> vp;
for(int i = 0; i < GEN; i++) {
vp.push_back(make_pair(gen.at(i), eval(gen.at(i), net)));
}
sort(vp.begin(), vp.end(), second_cmp);
for(int i = 0; i < GEN; i++) {
gen.at(i) = vp.at(i).first;
}
for(int i = 0; i < GEN; i++) {
for(int j = 0; j < N; j++) {
if(j == 0) cout << "gen: ";
if(j != 0) cout << " ";
cout << gen.at(i).at(j);
}
cout << ", dist: " << vp.at(i).second << endl;
}
cout << endl;
/*
while(true) {
vector<pair<vector<int>, double>> vp;
for(int i = 0; i < GEN; i++) {
vp.push_back(make_pair(gen.at(i), eval(gen.at(i), net)));
}
sort(vp.begin(), vp.end(), second_cmp);
vector<vector<int>> next_gen;
while(next_gen.size() < GEN) {
select();
cross();
}
gen = next_gen;
}
*/
return 0;
}
vector<vector<int>> init(vector<vector<int>> gen) {
for(int i = 0; i < GEN; i++) {
for(int j = 0; j < N; j++) {
gen.at(i).at(j) = j;
}
}
gen = shuffle(gen);
return gen;
}
vector<vector<int>> shuffle(vector<vector<int>> gen) {
random_device rnd;
mt19937 mt(rnd());
for(int i = 0; i < GEN; i++) {
for(int j = 0; j < N; j++) {
int tmp = mt()%N;
int t = gen.at(i).at(j);
gen.at(i).at(j) = gen.at(i).at(tmp);
gen.at(i).at(tmp) = t;
}
}
return gen;
}
double eval(vector<int> gen, double** net) {
double dist = net[gen.at(0)][gen.at(gen.size()-1)];
for(int i = 0; i < N-1; i++) dist += net[gen.at(i)][gen.at(i+1)];
return dist;
}
bool second_cmp(const pair<vector<int>, double>& a, const pair<vector<int>, double>& b) {
return a.second < b.second;
}