Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования "Кузбасский государственный технический университет" |
|
Кафедра информационных и автоматизированных производственных систем |
|
Исследование влияния начальных параметров генетических алгоритмов на скорость и точность нахождения оптимального решения задачи коммивояжера |
|
Выполнил: Турапин К.А. Проверил: Сыркин И.С. |
|
Кемерово 2006 |
Цель работы: обретение навыков оптимальной настройки параметров генетических алгоритмов при решении задачи коммивояжёра; сравнение точности нахождения результата ГА с аналитическими методами решения.
Задание: Исследовать влияние вида кроссовера и вероятности «жадной мутации» на скорость нахождения результата и его точность при количестве городов равным 30. Города расположить по кругу. Размер поля принять равным 1500х1500. Сравнить точность нахождения результата генетическими алгоритмами и методом кратчайшего незамкнутого пути.
Листинг программы
//---------------------------------------------------------------------------- #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; } //---------------------------------------------------------------------------- |
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.