5.2 Віконні форми
Роздивимось покрокове виконання програми з представленням вікон. Після запуску програмі відкриється наступне вікно.
Для спрощення зовнішнього настроювання, користувачу можна змінити лише кількість індивідів у популяції і ймовірність мутації.
Після виставлення необхідних параметрів, визначимо на робочій області точками вершини графу (клік лівою кнопкою миші), за якими буде проводитись обхід.
Натиснемо кнопку Start, після якого буде побудовано початковий обхід вершин
Для наступного кроку натиснемо кнопку Next.
Постійно натискаючи кнопку Next, ми вийдемо на граф, який вже не буде змінюватись, цей граф відповідає оптимальному обходу вершин.
5.3 Лістинги реалізації кроків генетичного алгоритму
Для реалізації схрещування використовується функція GenChild(), яку розміщено в файлі main.h.
void RebList::GenChild()
{
if (lst)
{
chld=new int*[pop];
mtx *mt= new mtx[cnt];
int a,b,err=0;
for (int i=0;i<pop;i++)
{
a=b=rand()%pop;
while (b==a) b=rand()%pop;
int *f=lst[a],*s=lst[b];
for(int j=0;j<cnt;j++)
{
mt[j].elem=f[j];
mt[j].link[0]=f[(j+1)%cnt];
mt[j].link[1]=f[(j-1+cnt)%cnt];
mt[j].len=2;
int k=0;
while (s[k]!=f[j]) k++;
if ((mt[j].link[0]!=s[(k+1)%cnt])&&(mt[j].link[1]!=s[(k+1)%cnt]))
{
mt[j].len++;
mt[j].link[2]=s[(k+1)%cnt];
}
else mt[j].link[2]=-1;
if ((mt[j].link[0]!=s[(k-1+cnt)%cnt])&&(mt[j].link[1]!=s[(k-1+cnt)%cnt]) &&(mt[j].link[2]!=s[(k-1+cnt)%cnt]))
{
mt[j].len++;
mt[j].link[3]=s[(k-1+cnt)%cnt];
}
else mt[j].link[3]=-1;
}
qsort(mt,cnt,sizeof(mtx),mtx_cmp);
fprintf(df,"First:\n");
for (int n=0;n<cnt;n++)
fprintf(df,"%i ",f[n]);
fprintf(df,"\n");
fprintf(df,"Second:\n");
for (int n=0;n<cnt;n++)
fprintf(df,"%i ",s[n]);
fprintf(df,"\n");
fprintf(df,"Matrix:\n");
for (int n=0;n<cnt;n++)
{
fprintf(df,"%i | %i %i %i %i | %i\n",mt[n].elem,mt[n].link[0],mt[n].link[1],mt[n].link[2],mt[n].link[3],mt[n].len);
}
int *ch=new int[cnt];
int indx=0,chl=5;
for(int j=0;j<cnt;j++)
if (chl>mt[j].len)
{
indx=j;
chl=mt[j].len;
}
chl=0;
fprintf(df,"New index: %i\n",indx);
while (chl<cnt)
{
ch[chl]=mt[indx].elem;
mt[indx].len=5;
int minl=5,nindx=-1;
for (int k=0;k<4;k++)
if (mt[indx].link[k]!=-1)
{
int j=mt[indx].link[k];
mt[j].len--;
if ((mt[j].len<minl)||((mt[j].len==minl)&&(nindx>j)))
{
nindx=j;
minl=mt[j].len;
}
if (mt[j].link[0]==ch[chl]) mt[j].link[0]=-1;
else if (mt[j].link[1]==ch[chl]) mt[j].link[1]=-1;
else if (mt[j].link[2]==ch[chl]) mt[j].link[2]=-1;
else mt[j].link[3]=-1;
}
fprintf(df,"Matrix:\n");
for (int n=0;n<cnt;n++)
{
fprintf(df,"%i | %i %i %i %i | %i\n",mt[n].elem,mt[n].link[0],mt[n].link[1],mt[n].link[2],mt[n].link[3],mt[n].len);
}
fprintf(df,"New index: %i\n",nindx);
if (nindx==-1)
{
nindx=5;
for(int j=0;j<cnt;j++)
if (nindx>mt[j].len)
{
indx=j;
nindx=mt[j].len;
}
fprintf(df,"New index: %i\n",indx);
}
else indx=nindx;
chl++;
}
fprintf(df,"Child:\n");
for (int n=0;n<cnt;n++)
fprintf(df,"%i ",ch[n]);
fprintf(df,"\n");
chld[i]=ch;
}
delete[] mt;
Childr();
}
}
Мутація на кожному кроці алгоритму реалізується за допомогою функції Mutations():
void RebList::Mutations()
{
if (lst)
for(int i=0;i<pop;i++)
if ((rand()%101)<mut)
{
int a,b=rand()%cnt;
a=b;
while (b==a) b=rand()%cnt;
int t=lst[i][a];
lst[i][a]=lst[i][b];
lst[i][b]=t;
}
if (chld)
for(int i=0;i<pop;i++)
if ((rand()%101)<mut)
{
int a,b=rand()%cnt;
a=b;
while (b==a) b=rand()%cnt;
int t=chld[i][a];
chld[i][a]=chld[i][b];
chld[i][b]=t;
}
List();
Childr();
}
Відбір найбільш пристосованих індивідів популяції виконується за допомогою функції Selection():
void RebList::Selection()
{
int ln=0;
if (lst) ln+=pop;
if (chld) ln+=pop;
if (ln)
{
len_ind *lens=new len_ind[ln];
int i=0;
if (lst)
for (int j=0;j<pop;j++)
{
lens[i].len=Len(lst[j]);
lens[i].ind=i;
i++;
}
if (chld)
for (int j=0;j<pop;j++)
{
lens[i].len=Len(chld[j]);
lens[i].ind=i;
i++;
}
qsort((void*)lens,i,sizeof(len_ind),len_cmp);
int **nlst=new int*[pop];
for (int j=0;j<pop;j++)
{
nlst[j]= new int[cnt];
if (lens[j].ind<pop)
memcpy(&nlst[j],&lst[lens[j].ind],cnt);
// nlst[j]=lst[lens[j].ind];
else
memcpy(&nlst[j],&chld[lens[j].ind -pop],cnt);
//nlst[j]=chld[lens[j].ind -pop];
}
for (int j=0;j<pop;j++)
{
// delete[] lst[j];
// delete[] chld[j];
delete[] lst;
delete[] chld;
lst=NULL;
chld=NULL;
}
lst=nlst;
delete[] lens;
}
else return;
}