Исследование влияния вида кроссовера и вероятности «жадной мутации» на скорость нахождения результата и его точность

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

#include <vcl.h>

#include <conio.h>

#include <iostream.h>

#include "math.h"

#include <stdio.h>

#pragma hdrstop

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

#pragma argsused

const unsigned short int razmPopul = 300;

const unsigned short int townNumber = 30;//количество городов

const unsigned short int square = 1500; // площадь на которой находятся города

unsigned short int crossType = 3;                  // вид кроссовера: 1 - частично отображаемый

                                                   //                 2 - упорядоченный (не работает)

                                                   //                 3 - изменённый

unsigned short int checkMode = 2;       // способ проверки решения на правильность

unsigned short int pokolNumber = 300;     // Количество поколений.

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

unsigned short int totalMut = 0;          // счётчик мутаций.

unsigned short int towns[townNumber];     // "Список" городов

unsigned short int bestOne;                        // лучший в своём поколении

unsigned short int checkSumValue; // контрольная сумма

unsigned short int curGen[razmPopul][townNumber];

unsigned short int nextGen[razmPopul][townNumber];

float curFitness[razmPopul];  // полезность

float nextFitness[razmPopul]; //

float totalFitness;

float bestFitness; // Лучшая приспособленность

int newPokol[2]; // Особи,  отбираемые для скрещивания.

unsigned short int chosenOne1[townNumber]; // Особи для скрещивания

unsigned short int chosenOne2[townNumber]; //

unsigned short int newOne1[townNumber]; // Потомки

unsigned short int newOne2[townNumber]; //

unsigned short int newTown, checkNewTown, turnir1, turnir2, breakPoint, breakPoint2;

// функция находит расстояние между городами расположенными по кругу

//                                        (номер города1, номер города2, площадь, кол-во городов)

float townDistance       (int town1, int town2, int square, int townNumber)

  {

  float x1, y1, x2, y2, rez;

  x1 = square/2*cos(town1*(360/townNumber)*M_PI/180);

  y1 = square/2*sin(town1*(360/townNumber)*M_PI/180);

  x2 = square/2*cos(town2*(360/townNumber)*M_PI/180);

  y2 = square/2*sin(town2*(360/townNumber)*M_PI/180);

  rez = pow(pow(x2-x1,2) + pow(y2-y1,2), 0.5);

  return rez;

}

float polza=0;

int main(int argc, char* argv[])

{

randomize();

for (unsigned int x = 0; x < razmPopul; x++) // Заполнение начальной популяции

  {

  for (unsigned int y = 0; y < townNumber; y++)

  towns[y] = y+1;

  for (unsigned int i = 0; i < townNumber; i++)

    {

    do

      {

      newTown = random (townNumber);

          checkNewTown = towns[newTown];

      curGen[x][i] = towns[newTown];

      towns[newTown] = 0;

      }

    while (checkNewTown == 0);

        }

  } // конец заполнения популяции

for (unsigned int i = 0; i < razmPopul; i++) // Оценка приспособленности

  {

  for (unsigned int x = 0; x < townNumber-1; x++)

    curFitness[i] += townDistance(curGen[i][x], curGen[i][x+1], square, townNumber);

  }

cout << endl;

//-----эволюция началась------------------------------------------------------

int next;

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

{

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

        {

        next = 0;

        while (next < 2) // Отбор экземпляров для скрещивания

          {

          turnir1 = random(razmPopul);

          turnir2 = random(razmPopul);

         // if (curFitness[turnir1] < curFitness[turnir2] && curFitness[turnir1] != (pow(10,6)))

          if (curFitness[turnir1] < curFitness[turnir2])

                 {

                 newPokol[next] = turnir1;

                 next++;

                 }

          else

                 if (curFitness[turnir2] != (pow(10,6)))

                         {

                         newPokol[next] = turnir2;

                         next++;

                         }

          }

for (unsigned int i2 = 0; i2 < townNumber; i2++)

  {

  chosenOne1[i2] = curGen[newPokol[0]][i2];

  chosenOne2[i2] = curGen[newPokol[1]][i2];

  }

// Экземпляров для скрещивания отобраны, занесены в переменные chosenOne_

        switch (crossType) // выбор типа кроссовера

        {

case 1: //---Частично отображаемый кроссовер начался--------------------------

{

  breakPoint = random(townNumber-1)+1;  // breakPoint = 1;

  for (unsigned int i2 = 0; i2 < breakPoint; i2++)

    {

        newOne1[i2] = chosenOne2[i2];

        newOne2[i2] = chosenOne1[i2];

    }

  for (unsigned int i2 = breakPoint; i2 < townNumber; i2++)

        {

        newOne1[i2] = chosenOne1[i2];

    newOne2[i2] = chosenOne2[i2];

    }

  for (unsigned int i2 = breakPoint; i2 < townNumber; i2++)

    {

      for (unsigned int j = 0; j < breakPoint; j++)

        {

                 if (newOne1[i2] == newOne1[j]) newOne1[i2] = newOne2[j];

                 if (newOne2[i2] == newOne2[j]) newOne2[i2] = newOne1[j];

                 }

        }

break;

} //---Частично отображаемый кроссовер закончился------------------------------

case 2: //---Упорядоченный кроссовер начался-----------------------------------

{

do

        {

        breakPoint = random(townNumber-1)+1;

        breakPoint2 = random(townNumber-1)+1;

        }

while ((breakPoint2 - breakPoint) < 1);

//cout << endl << breakPoint << "-" << breakPoint2 << endl;

for (unsigned int i2 = 0 ; i2 < townNumber; i2++)

        {

        newOne1[i2] = 0;

        newOne2[i2] = 0;

        }

for (unsigned int i2 = breakPoint ; i2 < breakPoint2; i2++)

        {

        newOne1[i2] = chosenOne1[i2];

        newOne2[i2] = chosenOne2[i2];

        //cout << newOne2[i2] << "|";

        }  //  cout << endl ;

        unsigned int j = 0;

        unsigned short int chosenOne11[townNumber];

        unsigned short int chosenOne22[townNumber];

for (unsigned int i2 = 0 ; i2 < townNumber; i2++)

        {

        chosenOne11[i2] = 0;

        chosenOne22[i2] = 0;

        }

for (unsigned int i2 = breakPoint2 ; i2 < townNumber; i2++)

        {

        chosenOne11[j] = chosenOne1[i2];

        chosenOne22[j] = chosenOne2[i2];

        j++;

        }

for (unsigned int i2 = 0 ; i2 < breakPoint2; i2++)

        {

        chosenOne11[j] = chosenOne1[i2];

        chosenOne22[j] = chosenOne2[i2];

        j++;

        }

for (unsigned int i2 = 0 ; i2 < townNumber; i2++)

        {

        chosenOne1[i2] = chosenOne11[i2];

        chosenOne2[i2] = chosenOne22[i2];

        }

for (unsigned int i2 = 0 ; i2 < townNumber; i2++)

        {

        for (unsigned int i3 = breakPoint ; i3 < breakPoint2; i3++)

          {

          if (chosenOne2[i2] == newOne1[i3])

                  chosenOne2[i2] = 0;

          if (chosenOne1[i2] == newOne2[i3])

                  chosenOne1[i2] = 0;

          }

        }

        j = 0;

for (unsigned int i2 = breakPoint2 ; i2 < townNumber; i2++)

        {

        chosenOne11[j] = chosenOne1[i2];

        chosenOne22[j] = chosenOne2[i2];

        j++;

        }

for (unsigned int i2 = 0 ; i2 < breakPoint2; i2++)

        {

        chosenOne11[j] = chosenOne1[i2];

        chosenOne22[j] = chosenOne2[i2];

        j++;

        }

for (unsigned int i2 = 0 ; i2 < townNumber; i2++)

        {

        chosenOne1[i2] = chosenOne11[i2];

        chosenOne2[i2] = chosenOne22[i2];

        }

for (unsigned int i2 = 0 ; i2 < townNumber; i2++)

  for (unsigned int i3 = 0 ; i3 < townNumber; i3++)

        {

        if (newOne1[i2] == 0 && chosenOne2[i3] != 0)

          {

          newOne1[i2] = chosenOne2[i3];

          chosenOne2[i3] = 0;

          }

        if (newOne2[i2] == 0 && chosenOne1[i3] != 0)

          {

          newOne2[i2] = chosenOne1[i3];

          chosenOne1[i3] = 0;

          }

        }

break;

  } //---Упорядоченный кроссовер закончился-----------------------------------

case 3:

{

breakPoint = random(townNumber-1)+1;

for (int i2 = 0 ; i2 < breakPoint; i2++)

        {

        newOne1[i2] = chosenOne1[i2];

        newOne2[i2] = chosenOne2[i2];

        }

bool ok1, ok2;

for (unsigned int i2 = breakPoint ; i2 < townNumber; i2++)

        {

        ok1 = true; ok2 = true;

        for (int i3 = 0 ; i3 < townNumber; i3++)

                 {

                 if (chosenOne2[i2] == newOne1[i3])

                         ok1 = false;

                 if (chosenOne1[i2] == newOne2[i3])

                         ok2 = false;

                 }

        if (ok1) newOne1[i2] = chosenOne2[i2];

        else             newOne1[i2] = 0;

        if (ok2) newOne2[i2] = chosenOne1[i2];

        else             newOne2[i2] = 0;

        }

bool stop;

for (unsigned int i2 = breakPoint ; i2 < townNumber; i2++)

        {

        if (newOne1[i2] == 0)

                 {

                 stop = false;

                 for (unsigned int i3 = 0 ; i3 < townNumber; i3++)

                         {

                         if (stop == false)

                                  {

                                  ok1 = true;

                                  for (unsigned int i4 = 0 ; i4 < townNumber; i4++)

                                          if (chosenOne1[i3] == newOne1[i4])

                                                   {

                                                   ok1 = false;

                                                   }

                                  if (ok1 == true)

                                          {

                                          newOne1[i2] = chosenOne1[i3];

                                          stop = true;

                                          }

                                  }

                         }

                 }

        }

for (unsigned int i2 = breakPoint ; i2 < townNumber; i2++)

        {

        if (newOne2[i2] == 0)

                 {

                 stop = false;

                 for (unsigned int i3 = 0 ; i3 < townNumber; i3++)

                         {

                         if (stop == false)

                                  {

                                  ok1 = true;

                                  for (unsigned int i4 = 0 ; i4 < townNumber; i4++)

                                          if (chosenOne2[i3] == newOne2[i4])

                                                   {

                                                   ok1 = false;

                                                   }

                                  if (ok1 == true)

                                          {

                                          newOne2[i2] = chosenOne2[i3];

                                          stop = true;

                                          }

                                  }

                         }

                 }

        }

break;

        }

} // конец всем кроссоверам

//---жадная мутация началась--------------------------------------------------

//mutProb = 20000;

if (mutProb > random(10000)) // мутация

  {

  do

        {

        breakPoint = random(townNumber-1)+1;

        breakPoint2 = random(townNumber-1)+1; // breakPoint2 = 3;

        //cout << breakPoint2 << " " << breakPoint << endl;

        }

  while ((breakPoint2 - breakPoint) < 2);

  float dist1, dist2;

  int j = 0, buf;

  for (unsigned int i2 = breakPoint; i2 < breakPoint2; i2++)

        {

        dist1 = townDistance(newOne1[breakPoint + j - 1], newOne1[breakPoint + j + 1], square, townNumber);

        //cout << newOne1[breakPoint + j - 1]  << " " << newOne1[breakPoint + j + 1] << " " << dist1 << endl;

        dist2 = townDistance(newOne1[breakPoint + j - 1], newOne1[breakPoint + j + 0], square, townNumber);

        //cout << newOne1[breakPoint + j - 1]  << " " << newOne1[breakPoint + j + 0] << " " << dist2 << endl << endl;

        if (dist1 < dist2)

          {

          buf = newOne1[breakPoint + j + 1];

          newOne1[breakPoint + j + 1] = newOne1[breakPoint + j];

          newOne1[breakPoint + j] = buf;

          }

        j++;

        }

  totalMut++;

  }

//---жадная мутация закончилась-----------------------------------------------

//--потомки заносятся в новое поколение---------------------------------------

for (unsigned int i1 = 0; i1 < townNumber; i1++)

  {

  nextGen[2*a][i1] = newOne1[i1];

  nextGen[2*a+1][i1] = newOne2[i1];

  }

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

switch (checkMode)

{

case 1: //---Проверка решения на правильность началась 1-----------------------

        {

        bool wrong = false;

        for (unsigned int i1 = 0; i1 < townNumber; i1++)

                 {

                 for (unsigned int i2 = i1 + 1; i2 < townNumber; i2++)

                         if (nextGen[2*a][i1] == nextGen[2*a][i2])

                                  wrong = true;

                 }

        if (wrong == true) nextFitness[2*a] = pow(10,6);

        wrong = false;

        for (unsigned int i1 = 0; i1 < townNumber; i1++)

                 {

                 for (unsigned int i2 = i1 + 1; i2 < townNumber; i2++)

                         if (nextGen[2*a+1][i1] == nextGen[2*a+1][i2])

                                  wrong = true;

                 }

        if (wrong == true) nextFitness[2*a+1] = pow(10,6);

        break;

        }

//---Проверка решения на правильность закончилась 1---------------------------

case 2: //---Проверка решения на правильность началась 2----------------------

        {

        for (unsigned int i1 = 0; i1 < townNumber; i1++)

           {

                 for (unsigned int i2 = i1 + 1; i2 < townNumber; i2++)

                         if (nextGen[2*a][i1] == nextGen[2*a][i2])

                                  nextGen[2*a][i2] = 0; // Если в хромосоме есть одинаковые города,

           }                              // то дубли удаляются

        for (unsigned int y = 0; y < townNumber; y++)

                 {

                 towns[y] = y + 1;

                 for (unsigned int i2 = 0; i2 < townNumber; i2++)

                         {

                         if (towns[y] == nextGen[2*a][i2])

                                  {

                                  towns[y] = 0;

                                  }

                         }

                 }

        for (unsigned int i1 = 0; i1 < townNumber; i1++)

                 {

                 if (nextGen[2*a][i1] == 0)

                         {

                         do

                                  {

                                  newTown = random (townNumber);

                                  checkNewTown = towns[newTown];

                                  nextGen[2*a][i1] = towns[newTown];

                                  towns[newTown] = 0;

                                  }

                         while (checkNewTown == 0);

                         }

                 }

        // второй пошёл

        for (unsigned int i1 = 0; i1 < townNumber; i1++)

           {

                 for (unsigned int i2 = i1 + 1; i2 < townNumber; i2++)

                         if (nextGen[2*a+1][i1] == nextGen[2*a+1][i2])

                                  nextGen[2*a+1][i2] = 0; // Если в хромосоме есть одинаковые города,

           }                              // то дубли удаляются

        for (unsigned int y = 0; y < townNumber; y++)

                 {

                 towns[y] = y + 1;

                 for (unsigned int i2 = 0; i2 < townNumber; i2++)

                         {

                         if (towns[y] == nextGen[2*a+1][i2])

                                  {

                                  towns[y] = 0;

                                  }

                         }

                 }

        for (unsigned int i1 = 0; i1 < townNumber; i1++)

                 {

                 if (nextGen[2*a+1][i1] == 0)

                         {

                         do

                                  {

                                  newTown = random (townNumber);

                                  checkNewTown = towns[newTown];

                                  nextGen[2*a+1][i1] = towns[newTown];

                                  towns[newTown] = 0;

                                  }

                         while (checkNewTown == 0);

                         }

                 }

        break;

        }

//---Проверка решения на правильность закончилась 2---------------------------

}

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

 nextFitness[2*a+1]= 0; nextFitness[2*a] = 0;

for (unsigned int i1 = 0; i1 < townNumber-1; i1++) // Оценка приспособленности особей нового поколения

  {

  nextFitness[2*a] += townDistance(nextGen[2*a][i1], nextGen[2*a][i1+1], square, townNumber);

  nextFitness[2*a+1] += townDistance(nextGen[2*a+1][i1], nextGen[2*a+1][i1+1], square, townNumber);

  }

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

 //cout << "-------Next generation--------" << endl;

for (unsigned int s = 0; s < razmPopul; s++) // Следующее поколение становится текущим

  {

  for (unsigned int d = 0; d < townNumber; d++)

        curGen[s][d] = nextGen[s][d];

  curFitness[s] = nextFitness[s];

  }

bestFitness = pow(10,10) ;

for (unsigned int s = 0; s < razmPopul; s++)

        {

        if (curFitness[s] < bestFitness)

                 {

                 bestFitness = curFitness[s];

                 bestOne = s;   // самая приспособленная особь

                 }

        }

totalFitness = 0;

for (unsigned int s = 0; s < razmPopul; s++)

  {

  totalFitness += curFitness[s]; // Общая приспособленность популяции

  }

cout << curFitness[bestOne] << " / ";

cout << totalFitness/razmPopul << endl;

getch();

        return 0;

}

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