//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;
}
}
Проблемы с памятью в генетическом алгоритме
Я написал программу максимизирующую функцию Profit(x(0),x(1)), приведенную в первых строках программы в комментариях, с помощью генетического алгоритма. Проблема заключается в том, что программа при попытке выполнения деструктора ~Generation выдает ошибку Assertion Failure (_BLOCK_TYPE_IS_VALID(pHead->nBlockUse). Судя по тому, что я почел про эту ошибку в гугле, она вызывается неправильной работой с памятью, посему прошу посмотреть корректность ее выделения/освобождения и помочь с решением проблемы. Заранее спасибо.
Во-вторых - смотрите, что у вас получается:
[QUOTE=Salein]
Код:
Generation::~Generation()
{
for (int i=0; i<iNum; i++)
{
Gen->~Individual();
}
}
{
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;
}
{
delete[] Gen;
}
[/QUOTE]
На этом участке кода происходит попытка освободить элементы Gen, и нулевого в том числе. Но для него уже был вызыван деструктор! Обращаемся к Individual::~Individual():
[QUOTE=Salein]
Код:
Individual::~Individual()
{
delete[] uiX;
}
{
delete[] uiX;
}
[/QUOTE]
Как легко видеть, повторный вызов этого деструктора приводит к попытке освободить недействительный блок памяти, о чем недвусмысленно и говорит Assertion Failure.
С учетом первого пункта, вам достаточно написать следующее:
Код:
Generation::~Generation()
{
for (int i = 0; i < iNum; i++)
delete[] Gen;
delete[] Gen;
}
{
for (int i = 0; i < iNum; i++)
delete[] Gen;
delete[] Gen;
}
Я согласен с вышеприведенным и внес правки в код, но т.к. Gen - массив указателей на объекты класса Individual, по-моему не нужно ставить квадратные скобки после delete в 4 строке вашей версии деструктора ~Generation() иначе мы попытаемся освободить массив элементов, когда имеем указатель на один (и Assertion Failure не исчезает).Если же не ставить скобок, то этого на второй итерации цикла for выпадает ошибка 0xC0000005: Access violation reading location 0xfeeefee2. Подскажите, пожалуйста, где я не прав.
Код:
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;
}
{
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[]. И обратите внимание на конструктор копирования, он может вызывать проблемы.
Конструктор копирования я подправил, но проблема все та же (Assertion Failure, строка 52), посему не могли бы вы предложить какое-нибудь средство тестирования (чтобы посмотреть на то, какие ячейки памяти когда выделяются, что-то в этом роде), если есть на примете? Если такие есть в Visual Studio 2010, то буду вдвойне благодарен.
P.S. А что такое строка 52?
Брейкпоинтами я и так пользуюсь, окно Locals не замечал до сих пор, спасибо.