|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yuri Burger 2:468/85.3 11 May 2001 14:10:05
To : All
Subject : FAQ: 3/4
--------------------------------------------------------------------------------
Q9. А на исходник простого ГА посмотреть можно?
A. (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;
}
******************************************************************************
Q10. Какие существуют методы кроссинговера?
A. (Дэвид Бисслей, статья)
"Традиционный" генетический алгоритм использует одноточечный кроссинговер,
в котором две скрещивающиеся хромосомы разрезаются один раз в соответствующей
точке и производится обмен полученными частями. Однако было изобретено много
других различных алгоритмов с иными видами кроссинговера, часто включающих
больше чем одну точку разреза. DeJong исследовал эффективность многоточечного
кроссинговера и пришел к выводу, что двуточечный кроссинговер дает улучшение,
но что дальнейшее добавление точек кроссинговера редуцирует деятельность
генетического алгоритма. Проблема с добавлением дополнительных точек
кроссинговера состоит в том, что стандартные блоки, вероятно, будут прерваны.
Однако преимущество большего количества точек кроссинговера состоит в том, что
пространство состояний может быть исследовано более полно и подробно.
ДВУХТОЧЕЧHЫЙ КРОССИHГОВЕР.
В двухточечном кроссинговере (и многоточечном кроссинговере вообще)
хромосомы расцениваются как циклы, которые формируются соединением концов
линейной хромосомы вместе. Для замены сегмента одного цикла сегментом другого
цикла требуется выбор двух точек разреза. В этом представлении, одноточечный
кроссинговер может быть рассмотрен как кроссинговер с двумя точками, но с
одной точкой разреза, зафиксированной в начале строки. Следовательно,
двухточечный кроссинговер решает ту же самую задачу, что и одноточечный
кроссинговер , но более полно. Хромосома, рассматриваемая как цикл, может
содержать большее количество стандартных блоков, так как они могут совершить
"циклический возврат" в конце строки. В настоящий момент многие
исследователи соглашаются, что двухточечный кроссинговер вообще лучше, чем
одноточечный.
линейное представление: хххххххххххх
ДДДДДДДДДДДД>
циклическое представление:Ъ>ххххххххххххДї
АДДДДДДДДДДДДДДЩ
УHИФИЦИРОВАHHЫЙ (ОДHОРОДHЫЙ) КРОССИHГОВЕР.
Унифицированный кроссинговер принципиально отличается от одноточечного
кроссинговера. Каждый ген в потомстве создается посредством копирования
соответствующего гена от одного или другого родителя, выбранного согласно
случайно сгенерированной маске кроссинговера. Если в маске кроссинговера стоит
1, то ген копируется от первого родителя, если в маске стоит 0, то ген
копируется от второго родителя. Процесс повторяется с обмененными родителями
для создания второго потомства. Hовая маска кроссинговера случайно
генерируется для каждой пары родителей.
******************************************************************************.
Kрюгер.
---
* Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
FAQ: 3/4 |
Yuri Burger |
11 May 2001 14:10:05 |
 FAQ: 3/4 |
vitalie vrabie |
13 May 2001 17:30:08 |
 FAQ: 3/4 |
Yuri Burger |
15 May 2001 22:13:03 |
|
FAQ: 3/4 |
vitalie vrabie |
19 May 2001 05:24:32 |
 FAQ: 3/4 |
Yuri Burger |
22 May 2001 20:34:51 |
 Re: FAQ: 3/4 |
Vlad Bespalov |
25 May 2001 01:04:14 |
|
FAQ: 3/4 |
vitalie vrabie |
25 May 2001 01:19:22 |
|
Re: FAQ: 3/4 |
Alexandr A. Redchuck |
24 May 2001 23:51:58 |
|
|
