Генетический алгоритм оптимизации в C++

Я ищу эффективные способы добавления или исключения кода, чтобы моя программа генетического алгоритма быстрее возвращала результаты. Цель программы состоит в том, чтобы принять строку и создать другие строки, максимально соответствующие ей. Какие бы вновь созданные строки ни соответствовали ближайшему (пятерке лучших) сочетанию с другими и производят потомство (некоторые из которых имеют мутации, которые помещают новое случайное число в строку, не влияя на длину). Все это прекрасно работает, но требуется непостижимое количество поколений, чтобы некоторые из более длинных строк (4 и выше) идеально совпадали. Извините за длину tl; dr, но вот мой текущий код. Критиковать прочь!

    #include "stdio.h"
    #include "fstream"
    #include "ctime"
    #include "iostream"
    #include "string"
    #include "windows.h"

    #define CHARACTERS 16
    #define STRINGS 100
    /*
    Enter String(max 16 chars)
    Generate 100 words of the same length
    Check for Fitness(how close each word is to the string)
    Every generation: display top 5
    Clone the top 5
    Top 20 reproduce(mix each other's chars)
    1/1000 chance the children might mutate(each newly mixed string or char might have a completely random number)

    */

    typedef struct _stringHolder
    {
        char randString[CHARACTERS];
        int fitness;
    }StringHolder;


//Randomly generate 100 words
void generate(char *myString, StringHolder *SH)
{
    unsigned seed = time(0);
    srand(seed);
        //int i = 0;
    int j = 0;
    char randChar;
        //char showString[CHARACTERS];
    for(int i=0; i<STRINGS; i++)
    {
        for(int j=0; j<strlen(myString); j++)
        {
            randChar = ('a' + (rand() %26));
            SH[i].randString[j] = randChar;
        }
        //limiter so that it doesn't crash
        SH[i].randString[strlen(myString)] = 0;
    }
}

//Check the similarity of the random strings to the original string.
void getFitness(char *myString, StringHolder *SH)
{
    for(int i=0; i<STRINGS; i++)
    {
        for(int j=0; j<strlen(myString); j++)
        {
            if(SH[i].randString[j] == myString[j])
            { SH[i].fitness++; }
        }
    }
}

//Sort the strings
void sortByFitness(char *myString, StringHolder *SH)
{

        bool swapped = 1;
        while(swapped)
        {
            swapped = 0;
            for(int a=0; a<STRINGS-1; a++)
            {
                if(SH[a].fitness < SH[a+1].fitness)
                {
                    swapped = 1;


                        StringHolder temp[STRINGS]; 
                        temp[a] = SH[a+1]/*.randString[i]*/;
                        SH[a+1]/*.randString[i]*/ = SH[a]/*.randString[i]*/;
                        SH[a]/*.randString[i]*/ = temp[a];

                    /*if(SH[a].fitness < SH[a+1].fitness)
                    { swapped = 0; }*/
                }
            }
        }//while
}

//Clone the Top 5 strings
void cloneTopFive(char *myString, StringHolder *SH, StringHolder *cloneString)
{
    for(int i=0; i<5; i++)
    {       
            cloneString[i]/*.randString[j]*/ = SH[i]/*.randString[j]*/;
            //printf("cloneString[%d] now holds %s.\n", i, SH[i].randString);

    }
}
//Reproduce the Top 20 strings by mixing and matching elements between strings
void reproduceTopTwenty(char *myString, StringHolder *SH /*char *cloneString*/)
{
    /*for(int h=5; h<95; h++)
    {*/
        for(int i=0; i<20; i++)
        {
            for(int j=0; j<strlen(myString)-1; j++)
            {
                //char temp[16];
                //temp[i] = 
                SH[i].randString[j] = SH[1 + (rand() %20)].randString[1 + (rand() %strlen(myString)-1)];
                int randomNumber;
                randomNumber = (1 +(rand() %100));
                if(randomNumber == 7)
                {
                    SH[i].randString[1 + (rand() %strlen(myString)-1)] = ('a' + (rand() %26));
                }
            }
        }

}
//Randomize the other 75 numbers and place the cloned Top 5 at the end of the String Holder(SH)
void randomizeOther75(char *myString, StringHolder *SH, StringHolder *cloneString)
{
    for(int i=20; i<STRINGS; i++)
    {
        for(int j=0; j<strlen(myString); j++)
        {
            SH[i].randString[j] = ('a' + (rand() %26));
        }
    }

    for(int i=0; i<5; i++)
    {
        for(int j=0; j<strlen(myString); j++)
        {
            int v = i + 94;
            SH[v].randString[j] = cloneString[i].randString[j];
        }
    }

}
void printGen(char *myString, StringHolder *SH)
{
    for(int i=0; i<5; i++)
        {       
            if(SH[i].fitness == strlen(myString))
             { printf("%s has %d fitness. Perfection!\n", SH[i].randString, SH[i].fitness); }
            else
             printf("%s has %d fitness.\n", SH[i].randString, SH[i].fitness);
        }
}
void main()
{
    char myString[CHARACTERS];
    StringHolder cloneString[5];
    StringHolder SH[STRINGS];
    for(int i=0; i<STRINGS; i++)
    { SH[i].fitness = 0; }

    printf("Enter your name(no whitespaces): ");
    scanf("%s", myString);
    /*while(strlen(myString) >= CHARACTERS)
    {
        printf("Please type a string with less than 16 characters\n");
        scanf("%s", myString);
    }*/
    //printf("%s\n", myString);

    //first generation
    generate(myString, SH);
    int gen = 0;
    while(1)
    {   
        char x = ' ';
    /*  printf("Insert something. Anything!");
        scanf(&x);*/


        /*char newString[CHARACTERS];
        for(int i=0; i<5; i++)
        {
            for( int j=0; j< strlen(myString); j++)
            {           
                newString[j] = SH[i].randString[j]; 
            }
            newString[strlen(myString)] = 0;
            printf("%s has %d fitness.\n", newString, SH[i].fitness);
        }*/

        printf("\n");
        while(x==' ')
        {
            printf("Generation %d: \n", gen);
            getFitness(myString, SH);
            sortByFitness(myString, SH);

            printGen(myString, SH);

            for(int i=0; i<STRINGS; i++)
            { SH[i].fitness = 0; }

            cloneTopFive(myString, SH, cloneString);
            reproduceTopTwenty(myString, SH);
            randomizeOther75(myString, SH, cloneString);
            /*getFitness(myString, SH);
            sortByFitness(myString, SH);

            for(int i=0; i<5; i++)
            {
                printf("%s has %d fitness.\n", SH[i].randString, SH[i].fitness);
            }
            printf("\n");*/

            //printf("\nInsert ' ' to continue!\n");

            //scanf("%c",&x);
            gen++;
        }   
}

person Mr. Czar    schedule 12.12.2010    source источник


Ответы (4)


Одной из основных причин плохой сходимости ГА является ваша фитнес-функция. Не обращая внимания на возможные ошибки кодирования в других частях программы, вы вознаграждаете только идеально совпадающие буквы. Ландшафт фитнеса выглядит так (бойтесь моего ASCII-искусства!):

___________   ___________
           | |
           |_|
a b c d e f G h i j k l m

Где Г - искомая буква. Алгоритм понятия не имеет, как найти G, кроме как по счастливой случайности. По сути, вы реализовали рандомизированный поиск методом грубой силы по буквам.

Сделайте так, чтобы фитнес-функция вознаграждала «близость» к правильному решению, и сходимость будет намного быстрее. Также настройте параметры популяции, мутацию, кроссовер и т. д.

person LumpN    schedule 13.12.2010
comment
Сделайте так, чтобы фитнес-функция вознаграждала близость к правильному решению, и сходимость будет намного быстрее: не обязательно... это зависит от того, имеют ли ваши операторы такое же понятие расстояния или нет. Судя по коду, я не уверен, что они это делают. Если оператор мутации изменен, чтобы добавить или вычесть единицу из значения символа, тогда да, этот ответ правильный. Если мутация выбирает новое случайное значение, то этот ответ неверен. ГА хитрые! - person Cameron Skinner; 14.12.2010
comment
При более внимательном чтении кода я все больше убеждаюсь, что это не сработает. Кроссовер выбирает из случайных родительских аллелей, и мутации практически не существует (скорее, 75 нижних особей генерируются случайным образом). Не существует механизма, позволяющего выполнять какой-либо градиентный спуск на одном аллеле, поэтому изменение функции пригодности таким образом практически ничего не даст. Я не буду минусовать, потому что идея хороша, но в этом случае также требуется модификация генетических операторов. - person Cameron Skinner; 14.12.2010
comment
Я должен согласиться как с ответом, так и с комментарием. Может помочь настройка вашей фитнес-функции для вознаграждения в зависимости от расстояния от оригинала, в отличие от простого измерения расстояния Хэмминга, хотя это будет означать изменение вашей функции мутации для увеличения или уменьшения символа на небольшую величину, а не просто случайный выбор другого символа. - person Raskolnikov; 14.12.2010

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

person Ljdawson    schedule 12.12.2010
comment
Хотел бы я знать больше, чтобы иметь возможность делать что-то вроде CUDA. Я все же больше начинающий программист. - person Mr. Czar; 13.12.2010

К сожалению, природа генетических алгоритмов такова, что иногда вам просто нужно настроить параметры и посмотреть, сможете ли вы ускорить поиск решения. Попробуйте клонировать 10 лучших особей, или 7 лучших, или 3 лучших. Измените ваши 20 лучших на, например, 50. Увеличьте или уменьшите частоту мутаций.

К сожалению, мы еще недостаточно понимаем ГА, чтобы определить «правильные» параметры без такой настройки.

Оптимизация кода — это отдельный вопрос, который может заставить каждое поколение работать быстрее, но я подозреваю, что проблема в том, что она занимает слишком много поколений, поэтому я не буду говорить об этом.

person Cameron Skinner    schedule 12.12.2010
comment
Точно. Я хотел уменьшить количество поколений, необходимых для получения идеального ответа. - person Mr. Czar; 13.12.2010
comment
Если вы считаете, что ответ неверный, объясните, пожалуйста. Это поможет всем! - person Cameron Skinner; 14.12.2010

Нужно смотреть параметры вашего ГА. Ваша популяция слишком мала для таких простых вычислений. У вас не должно возникнуть проблем с увеличением его как минимум до 1000, если не до 10 или 100К. У вас просто недостаточно решений в пуле, чтобы быстро прийти к хорошему результату.

Кроме того, ваша элитарность (количество кандидатов, которых вы клонируете для следующего поколения) довольно высока. Как правило, вы не хотите превышать 2% для элитарности.

Вы также можете посмотреть, как вы выполняете функцию кроссовера. Как правило, вы хотите выполнить кроссовер для всего населения, а не только для верхних 20%. Передайте все 95 ваших неклонированных значений в функцию кроссовера, и вы увидите больше разнообразия в своей популяции.

Как сказал Кэмерон, ваши проблемы, скорее всего, связаны с вашими параметрами, а не с вашим кодом, и это совершенно другая проблема, но это должно помочь вам на вашем пути. Удачи!

person Raskolnikov    schedule 12.12.2010
comment
Дело в том, что мне специально поручили попасть в топ-20. - person Mr. Czar; 13.12.2010
comment
Большая популяция может помочь, но также стоит изучить огромное количество литературы по эволюционным алгоритмам для малых популяций. Можете ли вы привести ссылку на 2% вещь? Это еще один параметр, который необходимо настроить. Иногда будет работать 2%, в других случаях будут работать 0,2% или 20%. Я согласен с крестом все немного. В качестве откровенной рекламы: взгляните на Skinner et al в отношении использования мутаций для поиска нового генетического материала :) - person Cameron Skinner; 14.12.2010
comment
Ссылка взята из работы докторов М. Петерсона и Ф. Мура, оба родом из штата Райт, а также из личного опыта моего собственного исследования ЭК. Это, вероятно, немного многословно, но стоит прочитать ИМО. И, как вы заметили, это не жесткое и быстрое правило, это точно так же, как настройка любого другого контроллера, но я не могу вспомнить GA, который я использовал, где я получил положительную производительность, увеличив элитарность выше этого. - person Raskolnikov; 14.12.2010
comment
Хм. Я не знаком с их работой, но я не делал много вещей в устойчивом состоянии. Конечно, в генетических алгоритмах поколений выбор параметра элитарности очень проблематичен и зависит от представления (как и все другие параметры). Я буду читать. - person Cameron Skinner; 14.12.2010