StringGenetic.cpp

#include <vector>
#include <iostream>
#include <string>
#include <functional>
#include <random>
#include <algorithm>
#include <chrono>
using namespace std;

random_device device;
mt19937 generator(device());
uniform_int<char> letters('a', 'z');
uniform_int_distribution<int> percent(0, 100);

auto letter_g = bind(letters, ref(generator));
auto percent_g = bind(percent, ref(generator));

const int children = 30;
const int mutation_rate = 50;
const int mutation_chance = 10;

class GeneticString {
    const int len;
    function<int(const string&)> dist_fn;
    vector<string> generation;
    uniform_int_distribution<int> picker;

public:
    GeneticString(int len, function<int(const string&)> fn)
        : len(len), dist_fn(fn), generation(generate(children)),
        picker(0, children - 1)    
    {}

    void go() {
        int gen = 0;
        while (dist_fn(generation[0])) {
            evolve();
            if (gen % 1000 == 0) {
                cout << dist_fn(generation[0]) << ' ';
            }
        }
        cout << endl;
    }

    string check() {
        return generation[0];
    }

    void evolve() {
        vector<string> new_gen = generate(children);

        for (int c = 0; c < children; ++c) {
            if (percent_g() < mutation_chance) {
                mutate(generation[c]);
            }

            if (c >= children / 10) {
                generation[c] = cross(new_gen[picker(generator)], generation[picker(generator)]);
            }
        }
        sort(generation);
    }


private:
    string cross(string left, const string & right) {
        string tester(left);
        for (int c = 0; c < len; ++c) {
            tester[c] = right[c];

            if (this->dist_fn(tester) < this->dist_fn(left)) {
                left[c] = right[c];
            } else {
                tester[c] = left[c];
            }
        }
        return left;
    }

    void mutate(string & target) {
        for (int c = 0; c < len;  ++c) {
            if (percent_g() < mutation_chance) {
                target[c] = letter_g();
            }
        }
    }

    vector<string> & sort(vector<string> & target) {
        std::sort(target.begin(), target.end(), [this](const string & l, const string & r) {
            return this->dist_fn(l) < this->dist_fn(r);
        });
        return target;
    }

    vector<string> generate(int size) {
        vector<string> result(size);
        for_each(result.begin(), result.end(), [this](string & str) {
            str.resize(this->len);
            std::generate(str.begin(), str.end(), letter_g);
        });
        return sort(result);
    }
};

void test(int sz, function<int(const string&)> fn, const char * name) {
    auto start = chrono::high_resolution_clock::now();
    GeneticString(sz, fn).go();
    auto end = chrono::high_resolution_clock::now();
    std::cout << name << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
}

int main() {
    string inp("loremipsumdolorsitametconsecteturadipisicingelitseddoeiusmodtemporincididuntutlaboreetdoloremagnaaliquautenimadminimveniamquisnostrudexercitationullamcolaborisnisiutaliquipexeacommodoconsequatduisauteiruredolorinreprehenderitinvoluptatevelitessecillumdoloreeufugiatnullapariaturexcepteursintoccaecatcupidatatnonproidentsuntinculpaquiofficiadeseruntmollitanimidestlaborum");
    
    auto dist = [&inp](const string & check) {
        int dist = 0, len = check.length();
        for (int c = 0; c < len; ++c) {
            dist += abs(inp[c] - check[c]);
        }
        return dist;
    };
    
    auto diff = [&inp](const string & check) {
        int dist = 0, len = check.length();
        for (int c = 0; c < len; ++c) {
            dist += inp[c] != check[c];
        }
        return dist;
    };

    test(inp.size(), dist, "DIST: ");
    test(inp.size(), diff, "DIFF: ");

    cin.get();
    return 0;
}