Инспекция кода: генетический поиск

259

13 октября 2017, 16:15

Здравствуйте! Сейчас пытаюсь искать алгоритмы Маркова с помощью генетических алгоритмов. Есть такой вот код:

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::pair;
using std::vector;
using std::string;
typedef pair<string, string> rule;
typedef vector<rule> algorithm;
typedef pair<string, string> test;

void print_rule(rule r)
{
    cout<<r.first<<" -> "<<r.second<<endl;
}
void print_algorithm(algorithm algo)
{
    cout<<endl;
    for(int i=0; i<algo.size(); i++)
        print_rule(algo[i]);
    cout<<endl;
}

string apply_algorithm(string str, const algorithm& algo, bool verbose=false)
{
    vector<string> prevs;
    int step = 0;
    bool loop=false;

    bool found = false;
    for(int i=0; i<algo.size(); i++)
    {
        if(str.find(algo[i].first)!=-1)
        {
            found = true;
            break;
        }
    }
    if(!found)
        return str;
    while(step<10000 && !loop)
    {
        step++;
        if(str.length()>100)
            break;
        for(int i=0; i<algo.size(); i++)
        {
            if(str.find(algo[i].first) != -1)
            {
                int first = str.find(algo[i].first);
                int len   = (algo[i].first).length();
                str.replace(first, len, algo[i].second);
                if(verbose)
                {
                    cout<<"found '"<<algo[i].first<<"' -> '"<<algo[i].second<<"'"<<endl;
                    cout<<str<<endl;
                }
                break;
            }
        }
        for(int i=0; i<prevs.size(); i++)
        {
            if(prevs[i] == str)
            {
                loop = true;
                break;
            }
        }
        prevs.push_back(str);
    }
    return str;
}
string mutate_string(string str)
{
    int chance = rand()%100;
    if(chance<25)
    {
        char n = (char)(rand()%94+32);
        str.push_back(n);
        return str;
    }
    else if(chance<50 && str.length()>0)
    {
        str.erase(rand()%str.length(), 1);
        return str;
    }
    else if(chance<75 && str.length()>0)
    {
        auto index = str.begin()+rand()%str.length();
        str.insert(index, 1, (char)(rand()%94+32));
        return str;
    }
    return str;
}
rule mutate_rule(rule r)
{
    string left = r.first;
    string right = r.second;
    int chance = rand()%100;
    if(chance<33)
    {
        left = mutate_string(left);
    }
    else if(chance<66)
    {
        right = mutate_string(right);
    }
    else
    {
        left = mutate_string(left);
        // cout<<left<<endl;
        right = mutate_string(right);
        // cout<<right<<endl;
    }
    rule result(left, right);
    return result;
}
string random_string(const int length)
{
    string ret = "";
    for(int i=0; i<length; i++)
        ret.push_back((char)(rand()%94+32));
    return ret;
}
rule random_rule()
{
    return make_pair(random_string(rand()%5+1),
                     random_string(rand()%5+1));
}
algorithm mutate_algoritm(algorithm algo)
{
    int chance = rand()%100;
    if(chance<33)
    {
        algo.push_back(random_rule());
        return algo;
    }
    else if(chance<66 && algo.size() > 1)
    {
        auto index = algo.begin()+rand()%algo.size();
        algo.erase(index);
        return algo;
    }
    else 
    {
        int index = rand()%algo.size();
        rule new_rule = mutate_rule(algo[index]);
        algo[index] = new_rule;
        return algo;
    }
}
algorithm random_algoritm()
{
    int length = rand()%10+1;
    algorithm ret;
    for(int i=0; i<length; i++)
        ret.push_back(random_rule());
    return ret;
}
int max_fitness(const vector<test>& tests)
{
    int length = 0;
    for(int i=0; i<tests.size(); i++)
        length+=tests[i].second.length();
    return length;
}
int difference(const string& a, const string& b)
{
    if(a.length()!=b.length())
        return -abs(a.length()-b.length());
    int ret=0;
    for(int i=0; i<a.length(); i++)
        if(a[i] == b[i])
            ret++;
    return ret;
}
int fitness(const algorithm& algo, const vector<test>& tests)
{
    int ret = 0;
    for(int i=0; i<tests.size(); i++)
    {
        string result = apply_algorithm(tests[i].first, algo);
        ret+=difference(result, tests[i].second);
    }
    return ret;
}                      
int fitness_opt(const algorithm& algo, const vector<test>& tests)
{
    int ret = 0;
    for(int i=0; i<tests.size(); i++)
    {
        string result = apply_algorithm(tests[i].first, algo);
        if(result!=tests[i].second)
            ret-=algo.size();
    }
    ret-=algo.size();
    return ret;
}
algorithm find_algorithm(const vector<test>& tests)
{
    const int goal = max_fitness(tests);
    int best = -10000;
    vector<algorithm> population;
    for(int i=0; i<100; i++)
        population.push_back(random_algoritm());

    int generation = 0;
    int last_print = 0;
    int start = time(NULL);
    pair<algorithm, int> pop[100];
    while(best != goal)
    {
        generation++;
        for(int i=0; i<100; i++)
            pop[i]=make_pair(population[i], fitness(population[i], tests));
        sort(pop, pop+100, 
            [](const pair<algorithm, int>& a, const pair<algorithm, int>& b)
            {return a.second > b.second;});
        population[0] = pop[0].first;
        for(int i=1; i<100; i++)
        {
            int chance=rand()%100;
            if(chance>i)
            {
                population[i] = mutate_algoritm(pop[0].first);
            }
            else 
                population[i] = pop[0].first;
        }
        const int first = fitness(population[0], tests);
        if(first>best)
        {
            best=first;
        }
    }
    return population[0];
}
algorithm optimize_algorithm(const vector<test> tests, algorithm algo)
{
    vector<algorithm> population;
    for(int i=0; i<100; i++)
        population.push_back(algo);

    int generation = 0;
    int last_print = 0;

    int best = -algo.size();
    pair<algorithm, int> pop[100];
    while(generation<10000)
    {
        generation++;
        for(int i=0; i<100; i++)
            pop[i]=make_pair(population[i], fitness_opt(population[i], tests));
        sort(pop, pop+100, 
            [](const pair<algorithm, int>& a, const pair<algorithm, int>& b)
            {return a.second > b.second;});
        population[0] = pop[0].first;
        for(int i=1; i<100; i++)
        {
            int chance=rand()%100;
            if(chance>i)
            {
                population[i] = mutate_algoritm(pop[0].first);
            }
            else 
                population[i] = pop[0].first;
        }
        const int first = fitness_opt(population[0], tests);
        if(first>best)
            best=first;
    }
    return population[0];
}
int main()
{
    // const vector<test> tests = {{"||*||", "||||"},
    //                             {"||*|||", "||||||"},
    //                             {"||||*||", "||||||||"},
    //                             {"||||*||||", "||||||||||||||||"}};
    // const vector<test> tests = {{"||+||", "||||"},
    //                          {"|+||", "|||"},
    //                          {"|||+|", "||||"}};

    // const vector<test> tests = {{"||-||", ""},
    //                          {"|||-|", "||"},
    //                          {"||-|", "|"}}; 

    const vector<test> tests = {{"||+||", "||||"},
                                {"|||+|", "||||"},
                                {"|+|", "||"}}; 

    int start = time(NULL);
    algorithm un_add = find_algorithm(tests);
    cout<<"Found in "<<time(NULL)-start<<'s'<<endl;
    print_algorithm(un_add);

    un_add = optimize_algorithm(tests, un_add);
    cout<<"Optimized in "<<time(NULL)-start<<'s'<<endl;
    print_algorithm(un_add);
    return 0;
}

Он работает правильно, но медленно. Вернее для простого случая (который раскомментирован) он работает быстро (около семи секунд), а для более сложных (трех закомментированных) очень долго.

Главный вопрос такой: можно ли сделать его быстрее?

Хочется также услышать критику самого кода, возможно предложений, как сделать его лучше (уверен, он далек от идеала).

Мне не нравятся сортировки около 290-ой и 344-ой строк и функция apply_algorithm - наверняка есть способы не считать ее в некоторых случаях.

Я, наверное, чего-то не понимаю, но замена всех функций типа

T mutate_T(const T& t)
{
    ...
    return new_t;
}

на

void mutate_T(T& t)
{
    ...
    t = new_t;
}

Увеличила время исполнения в десять(!) раз.

Получившийся код:

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::pair;
using std::vector;
using std::string;
typedef pair<string, string> rule;
typedef vector<rule> algorithm;
typedef pair<string, string> test;

void print_rule(rule r)
{
    cout<<r.first<<" -> "<<r.second<<endl;
}
void print_algorithm(algorithm algo)
{
    cout<<endl;
    for(int i=0; i<algo.size(); i++)
        print_rule(algo[i]);
    cout<<endl;
}

string apply_algorithm(string str, const algorithm& algo, bool verbose=false)
{
    vector<string> prevs;
    int step = 0;
    bool loop=false;

    bool found = false;
    for(int i=0; i<algo.size(); i++)
    {
        if(str.find(algo[i].first)!=-1)
        {
            found = true;
            break;
        }
    }
    if(!found)
        return str;
    while(step<10000 && !loop)
    {
        step++;
        if(str.length()>100)
            break;
        for(int i=0; i<algo.size(); i++)
        {
            if(str.find(algo[i].first) != -1)
            {
                int first = str.find(algo[i].first);
                int len   = (algo[i].first).length();
                str.replace(first, len, algo[i].second);
                if(verbose)
                {
                    cout<<"found '"<<algo[i].first<<"' -> '"<<algo[i].second<<"'"<<endl;
                    cout<<str<<endl;
                }
                break;
            }
        }
        for(int i=0; i<prevs.size(); i++)
        {
            if(prevs[i] == str)
            {
                loop = true;
                break;
            }
        }
        prevs.push_back(str);
    }
    return str;
}
void mutate_string(string& str)
{
    int chance = rand()%100;
    if(chance<25)
    {
        char n = (char)(rand()%94+32);
        str.push_back(n);
    }
    else if(chance<50 && str.length()>0)
    {
        str.erase(rand()%str.length(), 1);
    }
    else if(chance<75 && str.length()>0)
    {
        auto index = str.begin()+rand()%str.length();
        str.insert(index, 1, (char)(rand()%94+32));
    }
}
void mutate_rule(rule& r)
{
    int chance = rand()%100;
    if(chance<33)
    {
        mutate_string(r.first);
    }
    else if(chance<66)
    {
        mutate_string(r.second);
    }
    else
    {
        mutate_string(r.first);
        // cout<<left<<endl;
        mutate_string(r.second);
        // cout<<right<<endl;
    }
}
string random_string(const int length)
{
    string ret = "";
    for(int i=0; i<length; i++)
        ret.push_back((char)(rand()%94+32));
    return ret;
}
rule random_rule()
{
    return make_pair(random_string(rand()%5+1),
                     random_string(rand()%5+1));
}
void mutate_algoritm(algorithm& algo)
{
    int chance = rand()%100;
    if(chance<33)
    {
        algo.push_back(random_rule());
        // return algo;
    }
    else if(chance<66 && algo.size() > 1)
    {
        auto index = algo.begin()+rand()%algo.size();
        algo.erase(index);
        // return algo;
    }
    else 
    {
        int index = rand()%algo.size();
        mutate_rule(algo[index]);
        // return algo;
    }
}
algorithm random_algoritm()
{
    int length = rand()%10+1;
    algorithm ret;
    for(int i=0; i<length; i++)
        ret.push_back(random_rule());
    return ret;
}
int max_fitness(const vector<test>& tests)
{
    int length = 0;
    for(int i=0; i<tests.size(); i++)
        length+=tests[i].second.length();
    return length;
}
int difference(const string& a, const string& b)
{
    if(a.length()!=b.length())
        return -abs(a.length()-b.length());
    int ret=0;
    for(int i=0; i<a.length(); i++)
        if(a[i] == b[i])
            ret++;
    return ret;
}
int fitness(const algorithm& algo, const vector<test>& tests)
{
    int ret = 0;
    for(int i=0; i<tests.size(); i++)
    {
        string result = apply_algorithm(tests[i].first, algo);
        ret+=difference(result, tests[i].second);
    }
    return ret;
}                      
int fitness_opt(const algorithm& algo, const vector<test>& tests)
{
    int ret = 0;
    for(int i=0; i<tests.size(); i++)
    {
        string result = apply_algorithm(tests[i].first, algo);
        if(result!=tests[i].second)
            ret-=algo.size();
    }
    ret-=algo.size();
    return ret;
}
algorithm find_algorithm(const vector<test>& tests)
{
    const int goal = max_fitness(tests);
    int best = -10000;
    vector<algorithm> population;
    for(int i=0; i<100; i++)
        population.push_back(random_algoritm());

    int generation = 0;
    int last_print = 0;
    int start = time(NULL);
    pair<algorithm, int> pop[100];
    while(best != goal)
    {
        generation++;
        for(int i=0; i<100; i++)
            pop[i]=make_pair(population[i], fitness(population[i], tests));
        sort(pop, pop+100, 
            [](const pair<algorithm, int>& a, const pair<algorithm, int>& b)
            {return a.second > b.second;});
        population[0] = pop[0].first;
        for(int i=1; i<100; i++)
        {
            int chance=rand()%100;
            if(chance>i)
            {
                mutate_algoritm(pop[0].first);
                population[i] = pop[0].first;
            }
            else 
                population[i] = pop[0].first;
        }
        const int first = fitness(population[0], tests);
        if(first>best)
        {
            best=first;
        }
    }
    return population[0];
}
algorithm optimize_algorithm(const vector<test> tests, algorithm algo)
{
    vector<algorithm> population;
    for(int i=0; i<100; i++)
        population.push_back(algo);

    int generation = 0;
    int last_print = 0;

    int best = -algo.size();
    pair<algorithm, int> pop[100];
    while(generation<10000)
    {
        generation++;
        for(int i=0; i<100; i++)
            pop[i]=make_pair(population[i], fitness_opt(population[i], tests));
        sort(pop, pop+100, 
            [](const pair<algorithm, int>& a, const pair<algorithm, int>& b)
            {return a.second > b.second;});
        population[0] = pop[0].first;
        for(int i=1; i<100; i++)
        {
            int chance=rand()%100;
            if(chance>i)
            {
                mutate_algoritm(pop[0].first);
                population[i] = pop[0].first;
            }
            else 
                population[i] = pop[0].first;
        }
        const int first = fitness_opt(population[0], tests);
        if(first>best)
            best=first;
    }
    return population[0];
}
int main()
{
    // const vector<test> tests = {{"||*||", "||||"},
    //                             {"||*|||", "||||||"},
    //                             {"||||*||", "||||||||"},
    //                             {"||||*||||", "||||||||||||||||"}};
    // const vector<test> tests = {{"||+||", "||||"},
    //                          {"|+||", "|||"},
    //                          {"|||+|", "||||"}};

    // const vector<test> tests = {{"||-||", ""},
    //                          {"|||-|", "||"},
    //                          {"||-|", "|"}}; 

    const vector<test> tests = {{"||+||", "||||"},
                                {"|||+|", "||||"},
                                {"|+|", "||"}}; 

    int start = time(NULL);
    algorithm un_add = find_algorithm(tests);
    cout<<"Found in "<<time(NULL)-start<<'s'<<endl;
    print_algorithm(un_add);

    un_add = optimize_algorithm(tests, un_add);
    cout<<"Optimized in "<<time(NULL)-start<<'s'<<endl;
    print_algorithm(un_add);
    return 0;
}

Для @Voidificator: Если я правильно понимаю собственный код:

    // Суем пары типа 
    // <Алгоритм, фитнес-функция>
    // в массив pop
    for(int i=0; i<100; i++)
        pop[i]=make_pair(population[i], fitness(population[i], tests));
    // Сортируем массив pop по второму значению
    sort(pop, pop+100, 
        [](const pair<algorithm, int>& a, const pair<algorithm, int>& b)
        {return a.second > b.second;});
    population[0] = pop[0].first;
    for(int i=1; i<100; i++)
    {
        int chance=rand()%100;
        if(chance>i)
        {
            // Алгоритм попадает в population
            // либо после мутации
            mutate_algoritm(pop[0].first);
            population[i] = pop[0].first; //
        }
        else 
            population[i] = pop[0].first; // Либо без
    }

Answer 1

Навскидку предлагаю такую оптимизацию:

Код вида

for(int i=0; i<100; i++)
    pop[i]=make_pair(population[i], fitness(population[i], tests));
sort(pop, pop+100,
    [](const pair<algorithm, int>& a, const pair<algorithm, int>& b)
    {return a.second > b.second;});
population[0] = pop[0].first;
...

заменить на:

pair<algorithm*, int> pop = make_pair(&population[0], fitness(population[0], tests));
for(int i=1; i<100; i++)
{
    int ft = fitness(population[i], tests);
    if(ft > pop.second)
        pop = make_pair(&population[i], ft);
}
algorithm popalg = *pop.first;
population[0] = popalg;
...

Ибо, как я понял по коду, вам надо найти алгоритм с максимальным соответствием тестам. Для этого достаточно простого поиска максимума, а полноценная сортировка ни к чему. Кроме того я заменил вектора указателями на них.

А вообще в таких случаях желательно пользоваться профилировщиком. Ибо бывает сложно без измерений оценить, какую выгоду даст то или иное изменение кода.

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Глобальная переменная своего типа - c++

Завожу глобальную переменную собственноручно написанного класса в файле maincpp следующим образом:

243

c++

Работа с частью вектора как с вектором

Есть стандартный вектор, допустим типа std::vector<int>Есть функция void plusOne(std::vector<int>::iterator it1, std::vector<int>::iterator it2), прибавляющая всем элементам...

306

c++

Как ссылаться на DLL в решении в VS?

В VS2013 есть решение с проектами на С++Один главный, а остальные планируется оформить в виде динамических библиотек

321

c++

Базовый класс Фигура

Базовый класс Фигура с полем «название фигуры» и методом «Печать названия»Производный класс Шар с полем Радиус

270