Исследование структуры стандартного генетического алгоритма. Разработка структуры генетического алгоритма для решения задач оптимизации

Голомаздин С.М.

Лабораторная работа №3

Исследование структуры стандартного генетического алгоритма

Цель - исследовать структуру стандартного генетического алгоритма; разработать структуру генетического алгоритма для решения задач оптимизации

Целевая функция: . Исследовать влияние  вероятности мутации (от 0 до 1) и размера хромосомы (от 20 до 50) на скорость нахождения результата.

Вероятность мутации

вероятности мутации	Скорость
0	19
0,001	24
0,003	42
0,005	48
0,007	51
0,009	56
0,01	57

Размер хромосомы

Размер	Скорость
20	20
25	14
30	10
32	14

график зависимости TotalFitness от PopulationNumber

Площади прямоугольника равна S=a*b, Периметр определяется как P=(a+b)*2

a=S/b, P(b)=(S/b+b)*2

Код программы:

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <iostream.h>

#include <conio.h>

#include "math.h"

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

int razmPopul; // Размер популяции

int pokolNumber; // Количество поколений

int chromLen; // Длина хромосомы

int mutProb; // Вероятность мутации, 1=0,01%

int totalMut; // Всего мутаций

int S;

float result;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

        : TForm(Owner)

{

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{

razmPopul=StrToInt(Edit2->Text);

pokolNumber=StrToInt(Edit3->Text);

chromLen=StrToInt(Edit4->Text);

mutProb=StrToInt(Edit5->Text);

totalMut=StrToInt(Edit6->Text);

S=StrToInt(Edit1->Text);

ListBox1->Items->Clear();

float *curPolez;

curPolez=new float [razmPopul]; // Приспособленность текущего поколения

float *nextPolez;

nextPolez=new float [razmPopul]; // Приспособленность следующего

int chromLenInUse;

short unsigned int mutBit; // Мутирующий ген.

int breakPoint; // Точка разрыва хромосом.

int *curGen;

curGen=new int [razmPopul]; // Текущее поколение.

int *nextGen;

nextGen=new int [razmPopul]; // Следующее поколение.

float sumPolez; // Общая приспособленность поколения.

int newPokol[2];

int ch11,ch12,ch21,ch22, turnir1, turnir2, cutSuppL, cutSuppR;

short unsigned int cutL=0, cutR=0;

chromLenInUse=pow(2,chromLen-1);

randomize();

for (int i=0; i<razmPopul; i++)

        {

a1:     curGen[i]=random(chromLenInUse); // Заполнение начальной популяции

        if (curGen[i]==0) goto a1;

        if (curGen[i]>S) goto a1;

        curPolez[i]=(2*(S/(pow(curGen[i],2))+curGen[i])); // Оценка полезности

        }

for (int f=0; f<pokolNumber; f++) // Смена поколений

{

 for (int a=0; a<razmPopul/2; a++) // Скрещивание

 {

a2:for (int x=0; x<2; x++) // Отбор экземпляров для скрещивания

     {

        turnir1=random(razmPopul);

        turnir2=random(razmPopul);

        if (curPolez[turnir1]>curPolez[turnir2])

        newPokol[x]=turnir1;

        else newPokol[x]=turnir2;

     }

curGen[newPokol[0]]=curGen[newPokol[0]]^(curGen[newPokol[0]]>>1); // в код Грея

curGen[newPokol[1]]=curGen[newPokol[1]]^(curGen[newPokol[1]]>>1); //

breakPoint=random(chromLen-2); // Устанока точки разрыва

for (int i=0; i<(chromLen-breakPoint-1); i++)

        {

        cutSuppL=pow(2,chromLen-i-1);

        cutL=cutL|cutSuppL; // напр. cutL=111000

        }

for (int i=0; i<(breakPoint+1); i++)

        {

        cutSuppR=pow(2,i);

        cutR=cutR|cutSuppR; // напр. cutR=000111

        }

ch11=curGen[newPokol[0]]&cutR; // разбиение хромосом на части

ch12=curGen[newPokol[0]]&cutL; //

ch21=curGen[newPokol[1]]&cutR; //

ch22=curGen[newPokol[1]]&cutL; //

cutSuppL=0; cutSuppR=0; cutL=0; cutR=0;

nextGen[2*a]=ch11|ch22; // обмен частями хромосом

nextGen[2*a+1]=ch12|ch21; //

if (mutProb>random(10000))

        {

        mutBit=1;

        mutBit=mutBit<<random(chromLen);

        nextGen[2*a+random(2)]^=mutBit;

        totalMut++;

        }

for (unsigned i=1; i<32; i<<=1) nextGen[2*a]^=(nextGen[2*a]>>i); // из кода Грея

for (unsigned i=1; i<32; i<<=1) nextGen[razmPopul-a]^=(nextGen[razmPopul-a]>>i); //

if (nextGen[2*a]==0) goto a2;

if (nextGen[2*a+1]==0) goto a2;

if (nextGen[2*a]>S) goto a2;

if (nextGen[2*a+1]>S) goto a2;

nextPolez[2*a]=(2*(S/(pow(nextGen[2*a],2))+nextGen[2*a])); // оценка присполобленности

nextPolez[2*a+1]=(2*(S/(pow(nextGen[2*a+1],2))+nextGen[2*a+1])); //

 } // смена поколения завершилась

 sumPolez=0;

 for (int i=0; i<razmPopul; i++)

        {

        curGen[i]=nextGen[i];

        curPolez[i]=nextPolez[i];

        sumPolez+=curPolez[i];

        }

ListBox1->Items->Add(sumPolez);

result=curPolez[random(razmPopul)];

}

Edit9->Text=totalMut;

Edit8->Text=result;

delete curPolez;

delete nextPolez;

delete curGen;

delete nextGen;

}

//---------------------------------------------------------------------------