ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:468/85.3     18 Jul 2001  22:32:21
 To : All
 Subject : Mild.Faq: 3/9
 -------------------------------------------------------------------------------- 
 

 
 
 [ю]ДДДДДДДД Begin 3 ДДДДДДД
 
 >1.7 Совсем запутал. А проще можно?
 >Yuri Burger [2:468/85.3]
 
     Допустим  нам нужно оптимизировать некоторую функцию F(X1,X2,..,Xn). Пусть
 мы  ищем её глобальный максимум. Тогда, для реализации ГА нам нужно придумать,
 как   мы   будем  хранить  решения.  По  сути, нам нужно поместить все X1-Xn в
 некоторый   вектор,  который  будет  играть  роль  хромосомы. Один из наиболее
 распространенных  способов - кодировать значения переменных в битовом векторе.
 Hапример,  выделим каждому иксу по 8 бит. Тогда наш  вектор будет длины L=8*n.
 Для  простоты будем считать, что биты лежат в массиве X[0..L-1].
     Пусть  каждая  особь  состоит  из  массива  X  и  значения  функции  F  на
 переменных, извлеченных из этого массива.
     Тогда ГА будет состоять из следующих шагов:
     1. Генерация начальной популяции - заполнение популяции особями, в которых
 элементы массива X (биты) заполнены случайным образом.
     2.  Выбор  родительской  пары  -  я всегда использую элитный отбор, тоесть
 берем  K  особей  с  максимальными значениями функции F и составляю из них все
 возможные пары (K*(K-1)/2).
     3.  Кроссинговер  - берем случайную точку t на массиве X (0..L-1). Теперь,
 все   элементы  массива  с  индексами  0-t  новой  особи  (потомка)  заполняем
 элементами  с  теми-же  индексами,  но из массива X первой родительской особи.
 Остальные  элементы  заполняются  из  массива  второй  родительской особи. Для
 второго  потомка  делается наоборот - элементы 0-t берут от второго потомка, а
 остальные - от первого.
     4. Hовые особи с некоторой вероятностью мутируют - инвертируется случайный
 бит массива X этой особи. Вероятность мутации обычно полагают порядка 1%.
     5.  Полученные  особи-потомки  добавляются  в  популяцию после переоценки.
 Обычно новую особь добавляют взамен самой плохой старой особи, при условии что
 значение функции на новой особи выше значения функции на старой-плохой особи.
     6.  Если самое лучшее решение в популяции нас не удовлетворяет, то переход
 на  шаг  2.  Хотя,  чаще  всего  этого  условия нет, а итерации ГА выполняются
 бесконечно.
     Вообще,  если  строго  придерживаться правилам, то ГА должен содержать еще
 такие  шаги  как  отбор  особей  для размножения и генерация пар из отобранных
 особей. При этом каждая особь может быть задействована в одной и более паре, в
 зависимости от используемого алгоритма.
     Однако я предпочитаю эти два шага совмещать, используя построение пар "все
 на все" в элитной выборке. Имхо, так проще.
 ******************************************************************************
 
 >1.8 А на исходник простого ГА посмотреть можно?
 >Yuri Burger [2:468/85.3]
 
     Вот.   Собирал  на  Watcom  C.  Расчитано  на  2  переменные.  Кроссовер -
 классический, отбор - элитарный.
 
 // (c) BSM Group, Burger Y.A. (Kruger)
 // x = 0..XMaxValue
 // y = 0..YMaxValue
 #include <stdio.h>
 #include <stdlib.h>
 #include "math.h"
 #define PI 3.14159265358979323846
 #define MaxGenNum 256
 #define MaxPopulationLeng 65536
 
 long XMaxValue=1024;
 long YMaxValue=1024;
 
 double  LastX,LastY,LastZ;
 char    BestIsIn=0;
 double  BestX,BestY,BestZ;
 double  NumOfHromosoms;
 long    PBestLeng=16;    // длина лучшей выборки
 long    PMaxLeng=128;    // максимальная длина популяции
 long    PLeng=0;                 // текущая длина популяции
 long    HLeng=32;                // количество ген в хромосоме
 double  MutateHPercent=8;// процент мутаций в популяции
 double  MutateGPercent=8;// процент мутаций в хромосоме
 
 typedef struct
 {
         char   G[MaxGenNum];    // набор ген
         double V;       // значение оценки
 }HROMOSOM;
 
 HROMOSOM  *P[MaxPopulationLeng];        // популяция
 HROMOSOM  *B[MaxPopulationLeng];        // для селекции
 
 void PrintInfo(void)
 {
         printf("X=%g ",BestX);
         printf("Y=%g ",BestY);
         printf("Z(X,Y)=%g\n",BestZ);
 }
 double CalcZ(double X,double Y)
 {
         double z;
         double sx=X*PI/XMaxValue;
         double sy=Y*PI/YMaxValue;
         z=fabs(127+200*(cos(sx*sx+sy*sy)*cos(sy*sx))*sqrt(sin(sx)*sin(sy)));
         return z;
 }
 void SortPopulation(long l,long r)
 {
   long i=l,j=r;
   double x=P[(r+l)/2]->V;
   HROMOSOM *y;
   do
    {
     while (P[i]->V > x) i++;
     while (x > P[j]->V) j--;
     if (i<=j)
      {
       y=P[i];P[i]=P[j];P[j]=y;
       i++;j--;
      };
    }while(i<j);
   if (l<j) SortPopulation(l,j);
   if (i<r) SortPopulation(i,r);
 }
 double GetX(HROMOSOM *h)
 {
     long t;
     double d=0;
     for(t=0;t<HLeng;t++)
     {
         d+=(double)h->G[t]*pow(2,t-0);
     }
     d=XMaxValue*d/(pow(2,HLeng)-1);
     return d;
 }
 double GetY(HROMOSOM *h)
 {
     long t;
     double d=0;
     for(t=HLeng;t<HLeng*2;t++)
     {
        d+=(double)h->G[t]*pow(2,t-HLeng);
     }
     d=XMaxValue*d/(pow(2,HLeng)-1);
     return d;
 }
 double MiFunction(HROMOSOM *h)
 {
         double X,Y,Z;
         X=GetX(h);
         Y=GetY(h);
         Z=CalcZ(X,Y);
         LastX=X;
         LastY=Y;
         LastZ=Z;
         return Z;
 }
 HROMOSOM *NewHromosom(void)
 {
     HROMOSOM *t;
     t=(HROMOSOM *)calloc(1,sizeof(HROMOSOM));
     NumOfHromosoms++;
     return t;
 }
 void KillHromosom(HROMOSOM *h)
 {
     free(h);
 }
 int AddHromosom(HROMOSOM *h)
 {
         long mh=0;
     long t;
     if(PLeng<PMaxLeng)
     {
                 P[PLeng]=h;
         PLeng++;
         return 0;
     }
     else
     {
                 for(t=0;t<PLeng;t++)
                         if(P[t]->V < P[mh]->V)mh=t;
         if(h->V > P[mh]->V)// >= ?
         {
                         KillHromosom(P[mh]);
             P[mh]=h;
         }
         else return -1;
         return 0;
     }
 }
 void RandomFillHromosom(HROMOSOM *h)
 {
   long t;
         for(t=0;t<HLeng*2;t++)
     {
                 if(rand()<RAND_MAX/2) h->G[t]=0;
         else                  h->G[t]=1;
     }
 
     h->V=MiFunction(h);
 
 }
 void GenerateHromosom(HROMOSOM *h1,HROMOSOM *h2,HROMOSOM *s1,HROMOSOM *s2)
 {
         long t;
     long l=rand()*HLeng*2/RAND_MAX;
     for(t=0;t<l;t++)
     {
                 h1->G[t]=s1->G[t];
         h2->G[t]=s2->G[t];
     }
     for(t=l;t<HLeng*2;t++)
     {
         h1->G[t]=s2->G[t];
         h2->G[t]=s1->G[t];
     }
     h1->V=MiFunction(h1);
     h2->V=MiFunction(h2);
 }
 void MutateHromosom(HROMOSOM *h)
 {
         double l1,l2;
         long g;
         l1=MutateHPercent*RAND_MAX/100;
         l2=MutateGPercent*RAND_MAX/100;
         if(rand()<l1)
         {
                 for(g=0;g<HLeng*2;g++)
                 {
                         if(rand()<l2)
                         {
                                 h->G[g]^=1;
                         }
                 }
         }
         h->V=MiFunction(h);
 }
 void GA()
 {
         HROMOSOM *h,*h1,*h2;
         long x,y,z,mx,my;
         long c=0;
         long t;
     for(t=0;t<PMaxLeng;t++)
         {
                 h=NewHromosom();
         RandomFillHromosom(h);
         if(AddHromosom(h)==-1)KillHromosom(h);
         }
         if(PLeng>0)SortPopulation(0,PLeng-1);
 Loop:
         if(kbhit()){getch();goto Exit;}
         for(t=0;t<PBestLeng;t++)B[t]=P[t];
         for(my=0;my<PBestLeng;my++)
         {
                 for(mx=my+1;mx<PBestLeng;mx++)
                 {
                         c++;
                         h1=NewHromosom();
                         h2=NewHromosom();
                         GenerateHromosom(h1,h2,B[my],B[mx]);
                         MutateHromosom(h1);
                         if(AddHromosom(h1)==-1)KillHromosom(h1);
                         MutateHromosom(h2);
                         if(AddHromosom(h2)==-1)KillHromosom(h2);
                 }
         }
         if(PLeng>0)SortPopulation(0,PLeng-1);
         if(BestIsIn==0||P[0]->V>BestZ)
         {
                 BestIsIn=1;
                 BestX=GetX(P[0]);
                 BestY=GetY(P[0]);
                 BestZ=P[0]->V;
                 PrintInfo();
         }
         goto Loop;
 Exit:
         for(x=0;x<PLeng;x++)KillHromosom(P[x]);
         return;
 }
 int main(void)
 {
   GA();
   return 0;
 }
 ******************************************************************************.
 [ю]ДДДДДДДД End 3   ДДДДДДД
                                                  Kрюгер.
 ---
  * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор