Created
August 1, 2015 19:20
-
-
Save Randl/6a04760abb9994f28b29 to your computer and use it in GitHub Desktop.
Dices genetic
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
#include <array> | |
#include <vector> | |
#include <iostream> | |
#include <random> | |
#include <string> | |
#include <sstream> | |
using namespace std; | |
const int sides = 6; | |
const int pop_size = 25; | |
const int min_v = -10, max_v = 100, sum_v = 60; | |
random_device rd; | |
mt19937 gen(rd()); | |
uniform_int_distribution<int> dist(0,sides-1); | |
int from_string(string &s) { | |
stringstream ss(s); | |
int result; | |
ss >> result; | |
return result; | |
} | |
struct dice { | |
array<short, sides> values; | |
double f; | |
dice() { | |
values = {0, 0, 0, 0, 0, 0}; | |
f = 0.0; | |
} | |
dice(array<short, sides> v): values(v), f(0) {} | |
dice(const dice& d): values(d.values), f(d.f) {} | |
dice(string s) { | |
int i = 0, c = 0; | |
while(i < s.size() && c < sides) { | |
if (s[i]=='[') { | |
++i; | |
string tmp = ""; | |
while (s[i] != ']') { | |
tmp += s[i]; | |
++i; | |
} | |
values[c] = from_string(tmp); | |
values[c] = values[c] > min_v ? (values[c] < max_v ? values[c] : max_v) : min_v; | |
++c; | |
} | |
++i; | |
} | |
if (accumulate(values.begin(), values.end(), 0) != sum_v) { | |
values.fill(0); | |
for(int i = 0; i < sides-1; ++i) | |
values[i] = sum_v/sides; | |
values[sides-1] = sum_v - accumulate(values.begin(), values.end(), 0); | |
} | |
f = 0.0; | |
} | |
dice& operator=(const dice& d) { | |
values=d.values; | |
f = d.f; | |
return *this; | |
} | |
}; | |
std::ostream &operator<<(std::ostream &os, dice const &d) { | |
for (int i = 0; i < sides; ++i) | |
os << "[" << d.values[i] << "]"; | |
return os; | |
} | |
bool operator>(const dice& d1, const dice& d2) { | |
return d1.f > d2.f; | |
} | |
bool operator<(const dice& d1, const dice& d2) { | |
return d1.f < d2.f; | |
} | |
bool operator==(const dice& d1, const dice& d2) { | |
return d1.values == d2.values; | |
} | |
vector<dice> testing_pop; | |
double winning_prob(const dice d1, const dice d2) { | |
const int win_score = 100, run_n = 1000; | |
int sc1=0, sc = 0; | |
for (int i = 0; i < run_n; ++i) { | |
int score1 = 0, score2 = 0; | |
while(score1 < win_score && score2 < win_score) { | |
int a1 = dist(gen), a2 = dist(gen); | |
int res = d1.values[a1] - d2.values[a2]; | |
if (res > 0) | |
score1 += res; | |
else | |
score2 -= res; | |
} | |
++sc; | |
if (score1 > win_score) | |
++sc1; | |
} | |
return (double)sc1/sc; | |
} | |
double fitness(dice d, vector<dice> test) { | |
double score = 0; | |
for (auto it = test.begin(); it != test.end(); ++it) | |
score += winning_prob(d, *it); | |
score /= test.size(); | |
return score; | |
} | |
void fill_tp(vector<dice>& test) { | |
test.push_back(dice("[-10][-10][-10][-10][0][100]")); | |
test.push_back(dice("[-9][-9][-9][-9][-4][100]")); | |
test.push_back(dice("[0][0][0][15][15][30]")); | |
test.push_back(dice("[10][10][10][10][10][10]")); | |
test.push_back(dice("[3][5][9][11][15][17]")); | |
test.push_back(dice("[1][5][11][11][11][21]")); | |
test.push_back(dice("[-10][-10][20][20][20][20]")); | |
test.push_back(dice("[8][8][10][11][11][12]")); | |
test.push_back(dice("[-7][1][1][6][27][32]")); | |
test.push_back(dice("[0][0][0][0][60][0]")); | |
test.push_back(dice("[11][11][11][11][11][5]")); | |
test.push_back(dice("[5][5][-10][-10][20][50]")); | |
test.push_back(dice("[25][20][15][10][0][-10]")); | |
test.push_back(dice("[-10][-10][-10][-10][50][50]")); | |
test.push_back(dice("[20][30][20][10][-10][-10]")); | |
test.push_back(dice("[-10][14][14][14][14][14]")); | |
test.push_back(dice("[50][50][-10][-10][-10][-10]")); | |
test.push_back(dice("[1][1][1][1][1][55]")); | |
test.push_back(dice("[61][-1][-10][-10][18][2]")); | |
test.push_back(dice("[13][13][13][13][13][-5]")); | |
test.push_back(dice("[25][10][10][10][5][-10]")); | |
test.push_back(dice("[30][-10][30][-10][30][-10]")); | |
test.push_back(dice("[2][2][2][2][2][50]")); | |
test.push_back(dice("[-10][0][17][17][18][18]")); | |
test.push_back(dice("[-6][-6][-6][-6][53][31]")); | |
test.push_back(dice("[30][30][30][-10][-10][-10]")); | |
test.push_back(dice("[20][15][10][5][5][5]")); | |
test.push_back(dice("[-10][8][14][15][16][17]")); | |
test.push_back(dice("[-10][2][26][14][16][12]")); | |
test.push_back(dice("[-10][-9][-8][47][29][11]")); | |
test.push_back(dice("[10][10][10][10][11][9]")); | |
test.push_back(dice("[9][11][9][11][9][11]")); | |
test.push_back(dice("[39][33][-3][-3][-3][-3]")); | |
test.push_back(dice("[4][8][15][16][23][-6]")); | |
test.push_back(dice("[90][10][-10][-10][-10][-10]")); | |
test.push_back(dice("[27][27][27][-7][-7][-7]")); | |
test.push_back(dice("[-9][-9][15][21][21][21]")); | |
test.push_back(dice("[7][8][9][11][12][13]")); | |
test.push_back(dice("[44][11][4][1][0][0]")); | |
test.push_back(dice("[-10][12][12][12][12][12]")); | |
test.push_back(dice("[-5][5][0][20][20][20]")); | |
test.push_back(dice("[-1][-1][-1][-1][0][64]")); | |
test.push_back(dice("[12][12][12][12][6][6]")); | |
test.push_back(dice("[-8][-8][10][22][22][22]")); | |
test.push_back(dice("[-8][-8][-8][-8][-8][100]")); | |
test.push_back(dice("[100][-8][-8][-8][-9][-7]")); | |
test.push_back(dice("[7][13][11][9][5][15]")); | |
test.push_back(dice("[-10][14][14][14][8][20]")); | |
test.push_back(dice("[-10][-10][21][19][19][21]")); | |
test.push_back(dice("[9][10][11][9][10][11]")); | |
test.push_back(dice("[0][1][2][5][13][38]")); | |
test.push_back(dice("[-9][1][11][13][21][23]")); | |
test.push_back(dice("[-10][10][45][-10][20][5]")); | |
test.push_back(dice("[11][11][11][11][11][5]")); | |
test.push_back(dice("[6][9][4][20][21]")); | |
test.push_back(dice("[25][25][5][5][5][-5]")); | |
test.push_back(dice("[3][5][7][11][17][17]")); | |
test.push_back(dice("[0][20][20][0][20][0]")); | |
test.push_back(dice("[8][12][10][10][10][10]")); | |
test.push_back(dice("[10][-10][20][-20][30][30]")); | |
test.push_back(dice("[28][38][14][0][-10][-10]")); | |
test.push_back(dice("[16][6][20][-5][32][-9]")); | |
test.push_back(dice("[27][27][27][-7][-7][-7]")); | |
test.push_back(dice("[-9][5][15][16][16][17]")); | |
test.push_back(dice("[40][40][-10][-10][0][0]")); | |
test.push_back(dice("[5][27][3][11][7][7]")); | |
test.push_back(dice("[-9][-9][20][20][20][18]")); | |
test.push_back(dice("[-9][-4][-2][5][8][62]")); | |
test.push_back(dice("[4][6][10][11][14][15]")); | |
test.push_back(dice("[25][15][15][15][0][-10]")); | |
test.push_back(dice("[10][-5][20][-10][30][15]")); | |
test.push_back(dice("[-10][-10][-10][-9][1][98]")); | |
test.push_back(dice("[0][0][10][13][17][20]")); | |
test.push_back(dice("[9][10][15][9][5][12]")); | |
test.push_back(dice("[3][5][7][11][13][21]")); | |
test.push_back(dice("[-10][-9][-8][30][29][28]")); | |
test.push_back(dice("[-10][-10][20][20][20][20]")); | |
test.push_back(dice("[-10][6][16][16][16][16]")); | |
test.push_back(dice("[-9][10][14][14][14][17]")); | |
test.push_back(dice("[14][14][14][19][9][-10]")); | |
} | |
dice generate_dice() { | |
int mx = max_v, mn = min_v; | |
dice d; | |
int sum = 0; | |
for (int i = 0; i < sides - 1; ++i) { | |
uniform_int_distribution<int> val(mn, mx); | |
d.values[i] = val(gen); | |
if (d.values[i] < min_v || d.values[i] > max_v) { | |
cout << "s: " << sum << ", m: " << mn << "," << mx << "v: " << d.values[i] << endl; | |
int x; | |
cin >>x; | |
} | |
sum += d.values[i]; | |
mn = max((sum_v - sum) - max_v * (sides - i - 2), min_v); | |
mx = min((sum_v - sum) - min_v * (sides - i - 2), max_v); | |
} | |
d.values[sides-1] = sum_v - accumulate(d.values.begin(), d.values.end(), 0); | |
return d; | |
} | |
void generate_population(array<dice, pop_size>& pop) { | |
for (int i = 0; i < pop_size; ++i) | |
pop[i] = generate_dice(); | |
} | |
array<dice, pop_size> mutate(array<dice, pop_size> old_pop) { | |
geometric_distribution<int> ch(1.0/(pop_size)); | |
array<dice, pop_size> mutants; | |
for (int i = 0; i < pop_size; ++i) { | |
int m = ch(gen); | |
m = m > pop_size - 1 ? pop_size - 1 : m; | |
uniform_int_distribution<int> genes(0, sides-1); | |
int g1 = genes(gen), g2 = genes(gen); | |
while (g2==g1) | |
g2 = genes(gen); | |
int sum = old_pop[m].values[g1] + old_pop[m].values[g2]; | |
int mn = max(min_v, sum - max_v); | |
int mx = min(max_v, sum - min_v); | |
uniform_int_distribution<int> val(mn, mx); | |
int new_gene = val(gen); | |
mutants[i]=old_pop[m]; | |
mutants[i].values[g1] = new_gene; | |
mutants[i].values[g2] = sum - new_gene; | |
} | |
return mutants; | |
} | |
array<dice, pop_size> gen_children(array<dice, pop_size> old_pop) { | |
geometric_distribution<int> ch(1.0/(pop_size)); | |
array<dice, pop_size> children; | |
for (int i = 0; i < pop_size; ++i) { | |
int p1, p2; | |
p1 = ch(gen); | |
p1 = p1 > pop_size - 1 ? pop_size - 1 : p1; | |
p2 = ch(gen); | |
p2 = p2 > pop_size - 1 ? pop_size - 1 : p2; | |
while (p2==p1) { | |
p2 = ch(gen); | |
p2 = p2 > pop_size - 1 ? pop_size - 1 : p2; | |
} | |
uniform_real_distribution<double> parts(0.3, 0.7); | |
double fath_p = parts(gen); | |
array<short, sides> *father = &old_pop[p1].values, *mother = &old_pop[p2].values; | |
int sum = 0, mn = min_v, mx = max_v; | |
for(int j = 0; j < sides - 1; ++j) { | |
int gene = (int)((double)(*father)[j] * fath_p + (double)(*mother)[j] * (1-fath_p)); | |
gene = gene < mn ? mn : gene > mx ? mx : gene; | |
children[i].values[j]=gene; | |
sum += gene; | |
mn = max((sum_v - sum) - max_v * (sides - j - 2), min_v); | |
mx = min((sum_v - sum) - min_v * (sides - j - 2), max_v); | |
} | |
children[i].values[sides-1] = 0; | |
children[i].values[sides-1] = sum_v - accumulate(children[i].values.begin(), children[i].values.end(), 0); | |
} | |
return children; | |
} | |
array<dice, pop_size> next_g(array<dice, pop_size> old_pop) { | |
array<dice, pop_size> mutants, children, new_pop; | |
mutants = mutate(old_pop); | |
children = gen_children(old_pop); | |
double chance = 1.0 / pop_size; | |
uniform_real_distribution<double> ch(0, 1); | |
int m_num = pop_size / 6, ch_num = pop_size / 6, top_num = pop_size / 7, else_num = pop_size - m_num - ch_num - top_num; | |
int count = 0; | |
for (int i = 0; i < m_num; ++i) { | |
bool chosen = false; | |
vector<int> inside; | |
int j = 0; | |
while (!chosen) | |
if (ch(gen) < chance && find(inside.begin(), inside.end(), j) == inside.end()) { | |
new_pop[count] = mutants[j]; | |
inside.push_back(j); | |
chosen = true; | |
++count; | |
} else if (j < pop_size - 1) | |
++j; | |
else | |
j = 0; | |
} | |
for (int i = 0; i < ch_num; ++i) { | |
bool chosen = false; | |
vector<int> inside; | |
int j = 0; | |
while (!chosen) | |
if (ch(gen) < chance && find(inside.begin(), inside.end(), j) == inside.end()) { | |
new_pop[count] = children[j]; | |
inside.push_back(j); | |
chosen = true; | |
++count; | |
} else if (j < pop_size - 1) | |
++j; | |
else | |
j = 0; | |
} | |
for (int i = 0; i < top_num; ++i) { | |
new_pop[count] = old_pop[i]; | |
++count; | |
} | |
for (int i = 0; i < else_num; ++i) { | |
new_pop[count] = generate_dice(); | |
++count; | |
} | |
for (int i = 0; i < pop_size; ++i) | |
for (int j = i + 1; j < pop_size; ++j) | |
if (new_pop[i] == new_pop[j]) { | |
new_pop[j] = generate_dice(); | |
i = 0; | |
break; | |
} | |
return new_pop; | |
} | |
int main() { | |
const int num_g = 20000; | |
array<dice, pop_size> population; | |
generate_population(population); | |
// population[0] = dice("[10][10][10][10][10][10]"); | |
fill_tp(testing_pop); | |
for (int i = 0; i < num_g; ++i) { | |
for (int i = 0; i < pop_size; ++i) | |
population[i].f = fitness(population[i], testing_pop); | |
sort(population.begin(), population.end()); | |
reverse(population.begin(), population.end()); | |
cout << "-----------------\nPopulation " << i << endl; | |
for (int i = 0; i < pop_size; ++i) { | |
cout << population[i] << ": " << population[i].f << endl; | |
} | |
population = next_g(population); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment