2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Генетический алгоритм (помогите довести до ума)
Сообщение31.05.2013, 11:14 
Проблема заключается в следующем:
Имеется работающий генетический алгоритм, требуется дополнить его, чтобы он выполнял:
1)метод наискорейшего спуска
2) Переход по первому улучшению, т. е. к примеру в процессе работы алгоритма было выбрано некоторое колличество особей:
0100000000
0010000000
1000000000
0001000000
Путём инвертирования сначало первой особи находим первое более лучшшее решение и сразу начинаем просмотр окркстности из новой точки. Можно переходить только в допустимые точки.
Помогите пожалуйста.
меню:
Код:
#include <iostream.h>
#include "GA.h"

void main() {

   GA dp(5,6,7,40);

   int ans;
   ans = dp.Solve();
   if (ans == -1) {
      cout << "Решений не найдено." << endl;
   } else {
      gene gn = dp.GetGene(ans);

      cout << "Решение уравнения 5*x1+6*x2+7*x3=40:\n";
      cout << "x1 = " << gn.alleles[0] << "." << endl;
      cout << "x2 = " << gn.alleles[1] << "." << endl;
      cout << "x3 = " << gn.alleles[2] << "." << endl;
   
   }
}

Сам GA.h
Код:
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <string.h> 
using std::string;

#define MAXPOP 10   

struct gene {
   int alleles[3];
   int fitness;
   float likelihood;

   
   operator==(gene gn) {
      for (int i=0;i<3;i++) {
         if (gn.alleles[i] != alleles[i]) return false;
      }

      return true;
   }
};

class GA {
   public:
      GA(int, int, int, int);      // Конструктор для коэффициентов x1,x2,x3.
      int Solve();                        // Решаем уравнение.
      
      // Возвращение этого гена.
      gene GetGene(int i) { return population[i];}

   protected:
      int ca,cb,cc;                     // Коэффициенты
      int result;
      gene population[MAXPOP];               // Популяция

      int Fitness(gene &);                  // Функция приспосабливаемости
      void GenerateLikelihoods();               // Вычисляет вероятность выбора гена в качестве родительского
      float MultInv();                     
      int CreateFitnesses();
      void CreateNewPopulation();
      int GetIndex(float val);
      int   BinToDec(string bin);
      string DecToBin(int val);




      gene Breed(int p1, int p2);

};

GA::GA(int a, int b, int c, int res) : ca(a), cb(b), cc(c), result(res) {}

int GA::Solve() {                       //итеративно вызывает вышеописанные функции
   int fitness = -1;

   // Создание начальной популяции.
   srand((unsigned)time(NULL));

   for(int i=0;i<MAXPOP;i++) {                     // Заполняем популяцию числами от 0 до результата
      for (int j=0;j<3;j++) {                  
         population[i].alleles[j] = rand() % (result + 1);
      }
   }

   if (fitness = CreateFitnesses()) {
      return fitness;
   }

   int iterations = 0;                        
   while (fitness != 0 || iterations < 50) {      
      GenerateLikelihoods();                  
      CreateNewPopulation();
      if (fitness = CreateFitnesses()) {
         return fitness;
      }
      
      iterations++;
   }

   return -1;
}

int GA::Fitness(gene &gn) {              //вычисляет коэффициент выживаемости ( приспособленности - fitness) каждого гена.
   int total = ca * gn.alleles[0] + cb * gn.alleles[1] + cc * gn.alleles[2];

   return gn.fitness = abs(total - result);
}

int GA::CreateFitnesses() {
   float avgfit = 0;
   int fitness = 0;
   for(int i=0;i<MAXPOP;i++) {
      fitness = Fitness(population[i]);
      avgfit += fitness;
      if (fitness == 0) {
         return i;
      }
   }
   
   return 0;
}

float GA::MultInv() {
   float sum = 0;

   for(int i=0;i<MAXPOP;i++) {
      sum += 1/((float)population[i].fitness);
   }

   return sum;
}

void GA::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);
   }
}

int GA::GetIndex(float val) {               //GetIndex использует идею кумулятивности вероятностей (likelihoods), она просто делает итерации по всем генам, пока не найден ген, содержащий число
   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 GA::Breed(int p1, int p2) {          //возвращает ген, который помещается во временную популяцию
   int crossover = rand() % 3+1;               // Создание кросовера
   int first = rand() % 100;                  // Какой родитель идёт в первую очередь

   gene child = population[p1];               // Ребенок у которого все родители первые

   int initial = 0, final = 3;                  // Границы кросовера
   if (first < 50) initial = crossover;         // Если первые родители в первую очередь, то начать с кроссовера.
   else final = crossover+1;                  

   for(int i=initial;i<final;i++) {            // Кроссовер
      child.alleles[i] = population[p2].alleles[i];
      if (rand() % 101 < 5) child.alleles[i] = rand() % (result + 1);
   }

   return child;                           // Возврвщает ребенка
}

void GA::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 > 25) break;
      }
      
      temppop[i] = Breed(parent1, parent2);      
   }

   for(i=0;i<MAXPOP;i++) population[i] = temppop[i];
}
int   GA::BinToDec(string bin)//переводит из двоичных в десятичную
{
   int val          = 0;
   int value_to_add = 1;

   for (int i = bin.length(); i > 0; i--)
   {
     

      if (bin.at(i-1) == '1')

         val += value_to_add;

      value_to_add *= 2;
   
   }

   return val;
}

string GA::DecToBin(int val)//переводит из десятичной в двоичную
{
   string bin,Temp;
   while (val != 0)
   {
      Temp += ((val%2)+0x30);
      val /= 2;
   }
   for (int i=0;i<Temp.size();i++)
   bin += Temp[Temp.size()-(i+1)];
   return bin;
}      


 
 
 
 Re: Генетический алгоритм (помогите довести до ума)
Сообщение31.05.2013, 20:44 
Аватара пользователя
MANrycT в сообщении #730718 писал(а):
1)метод наискорейшего спуска
Позвольте, но ГА и метод наискорейшего спуска - это две большие разницы!

Что-то маленькая у вас популяция. Всего 10 штук.

Вообще большой код - уверен никому не доставит удовольствие его за вас модифицировать.

 
 
 
 Re: Генетический алгоритм (помогите довести до ума)
Сообщение01.06.2013, 05:22 
Я понимаю, что это разные вещи. Есть вероятность, что при переходе по первому улучшения(при популяции даже в 10 особей) алгоритм будет сходиться к оптимуму практически мгновенно. Помогите кто чем сможет :-)

 
 
 
 Re: Генетический алгоритм (помогите довести до ума)
Сообщение01.06.2013, 08:34 
Аватара пользователя
MANrycT в сообщении #731135 писал(а):
Помогите кто чем сможет
Ну я могу дать ссылку на похожую тему, вдруг что полезное topic42705.html Там же рекомендации по выбору количества особей.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group