Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Проблемы с памятью в генетическом алгоритме

66K
12 марта 2011 года
Salein
9 / / 12.03.2011
Я написал программу максимизирующую функцию Profit(x(0),x(1)), приведенную в первых строках программы в комментариях, с помощью генетического алгоритма. Проблема заключается в том, что программа при попытке выполнения деструктора ~Generation выдает ошибку Assertion Failure (_BLOCK_TYPE_IS_VALID(pHead->nBlockUse). Судя по тому, что я почел про эту ошибку в гугле, она вызывается неправильной работой с памятью, посему прошу посмотреть корректность ее выделения/освобождения и помочь с решением проблемы. Заранее спасибо.
Код:
//genetic v3
//Fitness function is Profit(x(0),x(1))
//Profit(x(0),x(1))=((ln(x(0))+alpha*x(1))*Spr-(x(0)^2+10)^(1/2))/x(1)*st
//Function shows the profit received from selling parts in given time
//x(0) - quality of material, ranges from 1 to 128
//x(1) - time, needed to produce one part, ranges from 1 to 256

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define alpha 0.7
#define Spr 10
#define st 512

void wait();
int myxor(int, int); //logical xor
void delaysec(); //delays for 1 sec
void mydelay (int secs); //delays for <secs>, using delaysec
int Bits (int bit); //returns int with all bits lower than <bit> filled with 1 (example, for bit=3 it returns 00000111)

class Individual
{
private:
    unsigned int* uiX;  //solution (vector of iN components)
    int iN;  //number of variables in optimised function
public:
    Individual();
    Individual(int n);  //creates Individual with a vector with <n> randomly filled components
    Individual(const Individual& rhsI);
    ~Individual();
    float GetFitness() const; //gets fitness of the individual, based on the profit function
    int Get(int var) const; //get the value of <var> variable
    int GetN() const; //gets number of values in an individual
    void Set(int var, int val); //sets <var> variable to <val> value
    int* Crossover(Individual& I1, Individual& I2, int var, int bit); //creates 2 children out of <I1> & <I2> parents
    void IndAss(const Individual& rhsI);
    Individual operator=(Individual&);
};

class Generation
{
private:
    Individual** Gen;  //array of pointers to individual solutions
    int iNgen;  //number of the generation in order
    int iNum;  //number of individuals in generation
    void Roulette(Generation&) const;  //selects <iNum> parents for breeding
public:
    Generation(int Num, int var); //<Num> = number of individual, <var> = number of variables in each
    Generation (Generation& G);
    ~Generation();
    float GetMaxFit() const; //gets max fitness of the generation
    void DispMaxFit() const; //displays max fitness of the generation
    void NextGen(int var); //creates new generation of solutions, changing <var> variable
    void Evolution(int disp=1); //disp = 1, shows maxfit on every generation
};
int main()
{
    srand((unsigned)time(NULL));
    Generation genTest(6, 2);
    genTest.Evolution(1);
    wait();
    return 0;
}

void wait()
{
    if (!_getch()) _getch();
}

int myxor(int x, int y)
{
    if ((!x&&y)||(x&&!y))
        return 1;
    else
        return 0;
}

void delaysec()
{
    time_t time1=time(NULL), time2;
    while ((time2=time(NULL))==time1)
    {}
}

void mydelay (int secs)
{
    for (int i=0; i<secs; i++)
    {
        delaysec();
    }
}

int Bits (int bit)
{
    int result=0;
    for (int i=0; i<bit; i++)
    {
        result+=(int) pow((double) 2,i);
    }
    return result;
}


Individual::Individual()
{
}

Individual::Individual(int n)
{
    uiX=new unsigned int[n];
    iN=n;
    for (int i=0; i<iN; i++)
    {
        if (i==0)
        {
            uiX=rand()%127+1;
            continue;
        }
        if (i==1)
        {
            uiX=rand()%255+1;
            continue;
        }
        uiX=rand()%255+1;
    }
}

Individual::Individual(const Individual& rhsI)
{
    iN=rhsI.iN;
    uiX=new unsigned int[iN];
    for (int i=0; i<iN; i++)
    {
        uiX=rhsI.uiX;
    }
}

Individual::~Individual()
{
    delete[] uiX;
}

float Individual::GetFitness() const
{
    return ((log((double) uiX[0])+alpha*uiX[1])*Spr-pow((pow((double) uiX[0],2)+10),0.5))/st*uiX[1];
}

void Individual::Set(int var, int val)
{
    uiX[var]=val;
}

int Individual::Get(int var) const
{
    return uiX[var];
}

int Individual::GetN() const
{
    return iN;
}

int* Individual::Crossover(Individual& I1, Individual& I2, int var, int bit)
{
    int* Result = new int[I1.GetN()];
    int bit1=0, bit2=0;
    if (bit==0)
    {
        bit1=I1.Get(var)&Bits(bit+1);
        bit2=I2.Get(var)&Bits(bit+1);
    }
    else
    {
        bit1=(I1.Get(var)&Bits(bit+1)) - (I1.Get(var)&Bits(bit));
        bit2=(I2.Get(var)&Bits(bit+1)) - (I2.Get(var)&Bits(bit));
    }
    if (!myxor(bit1, bit2))
    {
        Result[0]=I1.Get(var);
        Result[1]=I2.Get(var);
    }
    else
    {
        Result[0]=I1.Get(var)^((int)pow((double) 2,bit));
        Result[1]=I2.Get(var)^((int)pow((double) 2,bit));
    }
    return Result;
}

void Individual::IndAss(const Individual& rhsI)
{
    iN=rhsI.iN;
    for (int i=0; i<iN; i++)
    {
        uiX=rhsI.uiX;
    }
}

Individual Individual::operator=(Individual& rhsI)
{
    iN=rhsI.iN;
    for (int i=0; i<iN; i++)
    {
        uiX=rhsI.uiX;
    }
    return (*this);
}

Generation::Generation(int Num, int var)
{
    iNum=Num;
    Gen = new Individual*[iNum];
    for (int i=0; i<iNum; i++)
    {
        Gen = new Individual(var);
    }
    iNgen=0;
}

Generation::Generation(Generation& rhsG)
{
    iNum=rhsG.iNum;
    Gen = new Individual*[iNum];
    int var=rhsG.Gen[0]->GetN();
    for (int i=0; i<iNum; i++)
    {
        Gen=&Individual(*rhsG.Gen);
    }
    iNgen=rhsG.iNgen;
}

Generation::~Generation()
{
    for (int i=0; i<iNum; i++)
    {
        Gen->~Individual();
    }
    for (int i=0; i<iNum; i++)
    {
        delete[] Gen;
    }
    delete Gen;
}

float Generation::GetMaxFit() const
{
    Individual* Best=0;
    float BestFit=0;
    for (int i=0; i<iNum; i++)
    {
        if (Gen->GetFitness()>BestFit)
        {
            BestFit=Gen->GetFitness();
            Best=Gen;
        }
    }
    return BestFit;
}

void Generation::DispMaxFit() const
{
    Individual* Best=0;
    float BestFit=0;
    for (int i=0; i<iNum; i++)
    {
        if (Gen->GetFitness()>BestFit)
        {
            BestFit=Gen->GetFitness();
            Best=Gen;
        }
    }
    printf("Best fitness in generation #%d is %f\n", iNgen, BestFit);
    printf("Best ind. param. are");
    for (int i=0; i<(Best->GetN()); i++)
    {
        printf(" %d:%d", i, Best->Get(i));
    }
    printf("\n");
}

void Generation::Roulette(Generation& genInd) const
{
    float *Fitness = new float[iNum];
    Fitness[0]=Gen[1]->GetFitness();
    for (int i=1; i<iNum; i++)
    {
        Fitness=Fitness[i-1]+Gen->GetFitness();
    }
    for (int i=0; i<iNum; i++)
    {
        float F=rand()% (unsigned long) Fitness[iNum-1];
        if (F<Fitness[0])
        {
            genInd.Gen=Gen[0];
            continue;
        }
        for (int j=1; j<iNum; j++)
        {
            if ((F>Fitness[j-1])&&(F<Fitness[j]))
            {
                genInd.Gen=Gen[j];
                break;
            }
        }
    }
    delete[] Fitness;
}

void Generation::NextGen(int var)
{
    Generation genInd = Generation(*this);
    Roulette(genInd);
    for (int i=0; i<iNum; i+=2)
    {
        int *Result = 0;
        int bit=0;
        if (var==0)
            bit=rand()%7;
        if (var==1)
            bit=rand()%8;
        Result=genInd.Gen->Crossover(*genInd.Gen, *genInd.Gen[i+1], var, bit);
        (Gen)->Set(var, Result[0]);
        (Gen[i+1])->Set(var, Result[1]);
        delete[] Result;
    }
    iNgen++;
}

void Generation::Evolution(int disp)
{
    float PrevMaxFit=0, MaxFit=GetMaxFit();
    int flag=0;
    for (int i=0; i<(Gen[0])->GetN(); i++)
    {
        if (disp)
            printf("Evolving %d variable\n", i);
        while (fabs(MaxFit-PrevMaxFit)>10)
        {
            if (disp)
            {
                DispMaxFit();
                mydelay(2);
                if (_kbhit())
                {
                    flag=1;
                    break;
                }
            }
            NextGen(i);
            PrevMaxFit=MaxFit;
            MaxFit=GetMaxFit();
        }
        if (flag)
            break;
    }
}
278
12 марта 2011 года
Alexander92
1.1K / / 04.08.2008
Во-первых, учтите, что вызов delete автоматически вызывает деструктор.

Во-вторых - смотрите, что у вас получается:

[QUOTE=Salein]
 
Код:
Generation::~Generation()
{
    for (int i=0; i<iNum; i++)
    {
        Gen->~Individual();
    }
}

[/QUOTE]
Строка
 
Код:
Gen->~Individual();
эквивалентна строке
 
Код:
(*(Gen)).~Individual();

, что, в свою очередь, эквивалентно строке
 
Код:
Gen[0].~Individual();

, т.е. происходит удаление только нулевого элемента Gen. Разбираем далее:

[QUOTE=Salein]
 
Код:
for (int i=0; i<iNum; i++)
    {
        delete[] Gen;
    }

[/QUOTE]
На этом участке кода происходит попытка освободить элементы Gen, и нулевого в том числе. Но для него уже был вызыван деструктор! Обращаемся к Individual::~Individual():
[QUOTE=Salein]
 
Код:
Individual::~Individual()
{
    delete[] uiX;
}

[/QUOTE]
Как легко видеть, повторный вызов этого деструктора приводит к попытке освободить недействительный блок памяти, о чем недвусмысленно и говорит Assertion Failure.


С учетом первого пункта, вам достаточно написать следующее:

 
Код:
Generation::~Generation()
{
  for (int i = 0; i < iNum; i++)
    delete[] Gen;
  delete[] Gen;
}
66K
13 марта 2011 года
Salein
9 / / 12.03.2011
Я согласен с вышеприведенным и внес правки в код, но т.к. Gen - массив указателей на объекты класса Individual, по-моему не нужно ставить квадратные скобки после delete в 4 строке вашей версии деструктора ~Generation() иначе мы попытаемся освободить массив элементов, когда имеем указатель на один (и Assertion Failure не исчезает).Если же не ставить скобок, то этого на второй итерации цикла for выпадает ошибка 0xC0000005: Access violation reading location 0xfeeefee2. Подскажите, пожалуйста, где я не прав.
278
13 марта 2011 года
Alexander92
1.1K / / 04.08.2008
Только что обратил внимание еще на одну вещь... Скажите, у вас где-то используется конструктор копирования? Просто его тоже было бы хорошо подправить. Если я правильно понял, вы имели в виду следующее:

Код:
Generation::Generation(Generation& rhsG)
{
    iNum=rhsG.iNum;
    Gen = new Individual*[iNum];
    int var=rhsG.Gen[0]->GetN();
    for (int i=0; i < iNum; i++)
    {
        Gen= new Individual(rhsG.Gen);
    }
    iNgen=rhsG.iNgen;
}



[QUOTE=Salein]
Gen - массив указателей на объекты класса Individual
...
Подскажите, пожалуйста, где я не прав.
[/QUOTE]
Вот как раз здесь. Исходя из вашего определения, Gen есть указатель на МАССИВ объектов класса Individual, поэтому для корректного удаления как раз и пишется delete[]. И обратите внимание на конструктор копирования, он может вызывать проблемы.
66K
14 марта 2011 года
Salein
9 / / 12.03.2011
Конструктор копирования я подправил, но проблема все та же (Assertion Failure, строка 52), посему не могли бы вы предложить какое-нибудь средство тестирования (чтобы посмотреть на то, какие ячейки памяти когда выделяются, что-то в этом роде), если есть на примете? Если такие есть в Visual Studio 2010, то буду вдвойне благодарен.
278
14 марта 2011 года
Alexander92
1.1K / / 04.08.2008
Поставьте в VS брейкпойнты и запускайте в режиме отладки. VS в этом случае выводит окно локальных переменных с полным описанием.

P.S. А что такое строка 52?
66K
15 марта 2011 года
Salein
9 / / 12.03.2011
52 строка это пототип деструктора ~Generation().
Брейкпоинтами я и так пользуюсь, окно Locals не замечал до сих пор, спасибо.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог