1

遺伝的アルゴリズムを構築しましたが、コードの選択/突然変異部分に何か問題があるように感じます。これは私が話しているコードの一部です：

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <random>
#include <string>
#include <iomanip>
#include <math.h>

// The random number generator I am using.
std::random_device rd;
std::mt19937 rng(rd());

for (int k = 1; k < population_size; k++)                       // Loop until new population is filled up. K = 1 because first individual has the best genes from last generation.
{
// Calculate total fitness.

double totalfitness = 0;

for (int i = 0; i < population_size; i++)
{
    totalfitness += individuals[i].fitness;
}

// Calculate  relative fitness.

for (int i = 0; i < population_size; i++)
{
    individuals[i].probability = individuals[i].fitness / totalfitness;
}

std::uniform_real_distribution<double> dist2(0.0, 1.0);     // Initiate random number generator to generate a double between 0 and 1.

double rndNumber = dist2(rng);                              // Generate first double
double rndNumber2 = dist2(rng);                             // Generate second double
double offset = 0.0;                                        // Set offset (starting point from which it'll add up probabilities) at 0.
int father = 0;                                             // father is the individual that is picked, initialize at 0.
int mother = 0;

// Pick first parent. Once picked, set the fitness for that individual at 0 so that it can not be picked again.

for (int i = 0; i < population_size; i++)
{
    offset += individuals[i].probability;
    if (rndNumber < offset)
    {
        father = i;
        individuals[i].fitness = 0.0;
        break;
    }
}

offset = 0.0;       // Reset offset to zero because we'll start again for the second parent.
totalfitness = 0;   // Recalculate total fitness using only the remaining individuals and reset total fitness to 0

// Here we recalculate total fitness using only the fitness of the individuals remaining.

for (int i = 0; i < population_size; i++)
{
    totalfitness += individuals[i].fitness;
}

// Then we recalculate probability for the individuals based on the new totalfitness.

for (int i = 0; i < population_size; i++)
{
    individuals[i].probability = individuals[i].fitness / totalfitness;
}

// Then we give back the old fitness to the father/mother

individuals[father].fitness = 1 / (individuals[father].evaluation*individuals[father].evaluation);

// Then pick parent 2.

for (int i = 0; i < population_size; i++)
{
    offset += individuals[i].probability;
    if (rndNumber2 < offset)
    {
        mother = i;
        break;
    }
}

// Having picked father and mother, now the idea is to run a random number generator between 0 and 1 for each gene.
// So if:   father  {5, 8, 9, 3}
//          mother  {1, 5, 2, 6)
//          rndnum  {0, 0, 1, 1}
// then     child   {5, 8, 2, 6}

std::uniform_int_distribution<int> gene_selection(0, 1);        // Initiate random number generator to generate an integer between 0 and 1.

for (int i = 0; i < number_of_variables; i++)
{
    int gene1 = gene_selection(rng);
    if (gene1 == 0)
    {
        new_individuals[k].chromosomes[0].push_back(individuals[father].chromosomes[0].at(i));
    }
    else if (gene1 == 1)
    {
        new_individuals[k].chromosomes[0].push_back(individuals[mother].chromosomes[0].at(i));
    }
}

for (int j = 0; j < number_of_variables; j++)
{
    for (int l = 0; l < 32; l++)
    {
        std::uniform_int_distribution<int> mutation(0, 50);
        int mutation_outcome = mutation(rng);
        if (mutation_outcome == 1)
        {
            new_individuals[k].chromosomes[0].at(j) ^= (1 << l);
            if (new_individuals[k].chromosomes[0].at(j) == 0)
            {
                int new_var = uni(rng);
                new_individuals[k].chromosomes[0].at(j) = new_var;
            }
        }
    }
}
}

// When all new individuals have values, give individuals values of new_individuals and start next round of evaluation.

for (int i = 0; i < population_size; i++)
{
individuals[i] = new_individuals[i];
}

私のコードはほとんど問題なく動作しているようです。私が理解できないように見えるのは、なぜパフォーマンスが次第に悪化するのかということです. 最初の数世代は、新しいより良い解決策を頻繁に見つけているようです。数世代が経過すると、新しい最適解が見つからなくなります。

これはもちろん、より良い解決策がないためである可能性がありますが、私は同時に Excel で計算を行っており、「染色体」の 1 つを 1 つ増やすだけで、個人のフィットネスが向上することがよくあります。 1 ビットの変更です。私は通常、このコードを 10000 人の個人で実行するので、プログラムはこの変異を持つ個人を作成するようにバインドされていると言えます。

現在、デバッガーを使用してコードを何度もステップ実行し、途中のすべてのステップで値を表示していますが、どこで問題が発生しているのかがわからないため、コードをここに投稿して、誰かが私がめちゃくちゃになっている場所を見つけられるかどうかを確認してください。

記録のために、このアルゴリズムは単なる数式ソルバーです。たとえば、a = 1、b = 6、ターゲット = 50、a*gene1 + b *gene2 を入力すると、(理論的には) 個人がこの結果に近づくほど、より高い適合度が割り当てられます。

また、私が台無しにした場所を推測する必要がある場合、それはコードのミューテーション部分にあると言えます。

for (int j = 0; j < number_of_variables; j++)
{
    for (int l = 0; l < 32; l++)
    {
        std::uniform_int_distribution<int> mutation(0, 50);
        int mutation_outcome = mutation(rng);
        if (mutation_outcome == 1)
        {
            new_individuals[k].chromosomes[0].at(j) ^= (1 << l);
            if (new_individuals[k].chromosomes[0].at(j) == 0)
            {
                int new_var = uni(rng);
                new_individuals[k].chromosomes[0].at(j) = new_var;
            }
        }
    }
}

私がこれを言うのは、これが私自身が最も理解していない部分であり、そこで「目に見えない」エラーを犯したと非常に想像できたからです.

とにかく、どんな助けでも大歓迎です。

4

1 に答える 1

0

まあ、これはあなたのコードをより良く、より効率的にする方法にすぎません。シードなしで使用してstd::uniform_int_distributionおり、ほぼ 5 回連続して呼び出しているため、おそらく your random number is not really random after allです。

簡単な方法の 1 つは です。これにより、長期的にはより良い乱数の作成がto get things better可能になります (10000 人、なんとなく大きい!)。seeding the random engine with time

これについてのより良い説明へのリンクと、テストするための簡単なコード スニペットは次のとおりです。

#include <iostream>
#include <random> 

std::default_random_engine generator((unsigned int)time(0));
int random(int n) {
  std::uniform_int_distribution<int> distribution(0, n);
  return distribution(generator);
}
int main() {
        for(int i = 0; i < 15; ++i)
                std::cout << random(5) << " " << random(5)<< std::endl;
        return 0;
}

それが役立つことを願っています! 乾杯、

于 2016-05-15T11:39:16.243 に答える