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

#cpp #алгоритм #оптимизация #инспекция_кода #быстродействие

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

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::pair;
using std::vector;
using std::string;

typedef pair rule;
typedef vector algorithm;
typedef pair test;


void print_rule(rule r)
{
    cout< "< prevs;
    int step = 0;

    bool loop=false;


    bool found = false;
    for(int i=0; i100)
            break;

        for(int i=0; i '"<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< 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& tests)
{
    int length = 0;

    for(int i=0; i& tests)
{
    int ret = 0;

    for(int i=0; i& tests)
{
    int ret = 0;

    for(int i=0; i& tests)
{
    const int goal = max_fitness(tests);

    int best = -10000;

    vector 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 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& a, const pair& 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 tests, algorithm algo)
{
    vector population;

    for(int i=0; i<100; i++)
        population.push_back(algo);


    int generation = 0;

    int last_print = 0;


    int best = -algo.size();

    pair 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& a, const pair& 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 tests = {{"||*||", "||||"},
    //                             {"||*|||", "||||||"},
    //                             {"||||*||", "||||||||"},
    //                             {"||||*||||", "||||||||||||||||"}};

    // const vector tests = {{"||+||", "||||"},
    //                          {"|+||", "|||"},
    //                          {"|||+|", "||||"}};


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


    const vector tests = {{"||+||", "||||"},
                                {"|||+|", "||||"},
                                {"|+|", "||"}}; 


    int start = time(NULL);

    algorithm un_add = find_algorithm(tests);

    cout<<"Found in "<
#include 
#include 
#include 
#include 
#include 
#include 

using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::pair;
using std::vector;
using std::string;

typedef pair rule;
typedef vector algorithm;
typedef pair test;


void print_rule(rule r)
{
    cout< "< prevs;
    int step = 0;

    bool loop=false;


    bool found = false;
    for(int i=0; i100)
            break;

        for(int i=0; i '"<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< 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& tests)
{
    int length = 0;

    for(int i=0; i& tests)
{
    int ret = 0;

    for(int i=0; i& tests)
{
    int ret = 0;

    for(int i=0; i& tests)
{
    const int goal = max_fitness(tests);

    int best = -10000;

    vector 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 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& a, const pair& 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 tests, algorithm algo)
{
    vector population;

    for(int i=0; i<100; i++)
        population.push_back(algo);


    int generation = 0;

    int last_print = 0;


    int best = -algo.size();

    pair 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& a, const pair& 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 tests = {{"||*||", "||||"},
    //                             {"||*|||", "||||||"},
    //                             {"||||*||", "||||||||"},
    //                             {"||||*||||", "||||||||||||||||"}};

    // const vector tests = {{"||+||", "||||"},
    //                          {"|+||", "|||"},
    //                          {"|||+|", "||||"}};


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


    const vector tests = {{"||+||", "||||"},
                                {"|||+|", "||||"},
                                {"|+|", "||"}}; 


    int start = time(NULL);

    algorithm un_add = find_algorithm(tests);

    cout<<"Found in "<
    // в массив 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& a, const pair& 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; // Либо без
    }

    

Ответы

Ответ 1

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

Код вида 

for(int i=0; i<100; i++)
    pop[i]=make_pair(population[i], fitness(population[i], tests));

sort(pop, pop+100,
    [](const pair& a, const pair& b)
    {return a.second > b.second;});

population[0] = pop[0].first;
...


заменить на:

pair 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;
...


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

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