CDiophantine(int, int, int, int, int); // Конструкторскоэффициентамиприа,b,c,d
int Solve(); // Вычисляетрешениеуравнения
gene GetGene(int i)
{ return population[i];}
protected:
int ca,cb,cc,cd; // Коэффициенты при а,b,c,d
int result;
gene population[MAXPOP]; // Массив из генов - популяция
intFitness(gene&); // Функция приспособленности
voidGenerateLikelihoods(); // Вычисляет вероятности воспроизведения
float MultInv();
int CreateFitnesses();
void CreateNewPopulation();
int GetIndex(float val);
gene Breed(int p1, int p2);
};
CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {}
int CDiophantine::Solve()
{
int fitness = -1;
// Создаемначальнуюпопуляцию
srand((unsigned)time(NULL));
for(int i=0;i<MAXPOP;i++)
{ // Аллели хромосом заполняем
// произвольными числами от 0 до result
for (int j=0;j<4;j++)
{
population[i].alleles[j] = rand() % (result + 1);
}
}
if (fitness = CreateFitnesses())
{
return fitness;
}
int iterations = 0;
while (fitness != 0 || iterations < 50)
{ // Считаем до тех пор пока решение
// не будет найдено или к-во итераций более 50
GenerateLikelihoods();
CreateNewPopulation();
if (fitness = CreateFitnesses())
{
printf("iterations %d \n",iterations);
return fitness;
}
iterations++;
}
return -1;
}
int CDiophantine::Fitness(gene &gn) // Вычисляеткоэффициет
// приспособленностидляданногогена
{
int total = ca * gn.alleles[0] + cb * gn.alleles[1] + cc * gn.alleles[2] + cd * gn.alleles[3];
return gn.fitness = abs(total - result);
}
int CDiophantine::CreateFitnesses() // Возвращает номер гена в популяции ,
{ // кот. явл. решением данного ур-я
float avgfit = 0;
int fitness = 0;
for(int i=0;i<MAXPOP;i++)
{
fitness = Fitness(population[i]);
// avgfit += fitness;
if(fitness== 0)
{
returni;
}
}
return0; //Возвращает 0 ,если среди генов данной
// популяции не нашлось решения
}
floatCDiophantine::MultInv()
{
float sum = 0;
for(int i=0;i<MAXPOP;i++)
{
sum += 1/((float)population[i].fitness);
}
returnsum; //Сумма обратных коэффициентов
// приспособленности всех генов в популяции
}
voidCDiophantine::GenerateLikelihoods() //Генерирует вероятности воспроизведения
{
float multinv = MultInv();
float last = 0;
for(int i=0;i<MAXPOP;i++)
{
population[i].likelihood = last = last + ((1/((float)population[i].fitness) / multinv) * 100);
}
}
intCDiophantine::GetIndex(floatval) // По данному числу от 0 до 100 возвращает
{ // номер необходимого гена в популяции
float last = 0;
for(int i=0;i<MAXPOP;i++)
{
if (last <= val && val <= population[i].likelihood) return i;
else last = population[i].likelihood;
}
return 4;
}
gene CDiophantine::Breed(int p1, int p2)
{
intcrossover= rand() % 3+1; // Число от 1 до 3 - генерируем точку кроссовера.
intfirst= rand() % 100; // Какой родитель будет первым ?
genechild= population[p1]; // Инициализировать ребенка первым родителем
int initial = 0, final = 4;
if (first < 50) initial = crossover; // Еслипервыйродительр1(вероятностьэтого50%) -
// начинаем с точки кроссовера
elsefinal= crossover; // Иначе - заканчиваем на точке кроссовера
for(int i=initial;i<final;i++)
{ // Кроссовер
child.alleles[i] = population[p2].alleles[i];
if (rand() % 101 < 5) child.alleles[i] = rand() % (result + 1);// 5% - мутация
}
return child; // Возвращаем ребенка
}
void CDiophantine::CreateNewPopulation() {
gene temppop[MAXPOP];
for(int i=0;i<MAXPOP;i++)
{
int parent1 = 0,parent2 = 0, iterations = 0;
while(parent1 == parent2 || population[parent1] == population[parent2])
{
parent1 = GetIndex((float)(rand() % 101));
parent2 = GetIndex((float)(rand() % 101));
if (++iterations > MAXPOP) break; // Вэтомслучае
// родителей выбираем случайно
}
temppop[i] = Breed(parent1, parent2); // Процесс размножения
}
for(i=0;i<MAXPOP;i++)
population[i] = temppop[i];
}