資料整理，僅作記錄。
【OpenCV C++】基于遺傳算法解決旅行商問題的疊代過程可視化原型系統
功能
- 實作了遺傳算法解決旅行商問題
- 實作了可視化旅行地點标記
- 實作了疊代過程可視化
【OpenCV C++】基于遺傳算法解決旅行商問題的疊代過程可視化原型系統
代碼
Github
main.cpp
#include"GA_TSP.h"
#include<stdlib.h>
#define BUFSIZE 256
using namespace std;
void main()
{
double t =(double) cv::getTickCount();
system("cls");
generation = 0;
GetPoint();
//fileRead();
//fileWrite();
CITYCOUNT = CHROMLENGTH = pointcount;//城市節點不限制，可以随意改，pointcount為輸入的城市節點的個數
CalculatorDistance();
//第一代
GenerateInitialPopulation();
CalculateFitness();
FindBestIndividual();
OutputTextReport();
//然而，不斷進化
while (generation<MaxGeneration)
{
generation++;
GenerateNextPopulation();
CalculateFitness();
FindBestIndividual();
ShowResult();
}
//最後一代輸出
OutputTextReport();
//結果展示，繪制出了路徑
ShowResult();
//fileWrite();
t = cv::getTickCount() - t;
cout << "程式運作時間：" << t / ((double)cv::getTickFrequency()*1000.) <<"ms"<< endl;
//cvWaitKey(0);
}
GA_TSP.cpp
#include "GA_TSP.h"
GA_TSP::GA_TSP()
{
}
GA_TSP::~GA_TSP()
{
}
int PopSize =500; //種群規模
int MaxGeneration = 10000;//進化代數
double Pc = 0.2;//交叉機率
double Pm = 0.005;//變異機率
int CITYCOUNT = 3; //城市個數
int CHROMLENGTH = 3;
int CitySet[500];//城市集合
int WorkSet[100];//染色體解碼時的臨時工作數組，存放還未通路的城市序列
int TempCitySet[100];//存放染色體解碼完成後所經過的城市序列
FILE *f= fopen("city.txt", "rb+");
//int disaster_control = 0;
//double disaster_Pc = 0.3;
//double disaster_Pm = 0.01;
//double m = Pm;//緩存不變
//double c = Pc;
cv::Scalar line = cv::Scalar(255, 0,0);
typedef struct individual{
int chrom[100];//染色體編碼
double value; //value值表示路徑長度
double fitness; //适應度
}individual;
int generation;
individual bestindividual;//某一代群體中最優個體
individual currentbest;//目前最優個體
individual population[POPSIZE];//
cv::Mat tsp_image = cv::Mat::zeros(cv::Size(800, 600),CV_8UC3);
int CityDistance[100][100] = {};//城市之間的距離矩陣,來回相等
//選擇算子
void Select(int start, int stop, individual *newpopulation){
int i, index;
double p, sum = 0.0;
double cfitness[POPSIZE];//個體适應度
//求總适應度sum
//#pragma omp parallel for
for (i = start; i < stop; i++){
sum += population[i].fitness;
}
//求每個個體的适應度所占的百分比cfitness[i]
#pragma omp parallel for
for (i = start; i < stop; i++){
cfitness[i] = population[i].fitness / sum;
}
//适應度求和，類似機率分布：0 1 2 3 4 -> 0 1 3 4 10
for (i = start + 1; i < stop; i++){
cfitness[i] = cfitness[i - 1] + cfitness[i];
}
//選擇個體，
//#pragma omp parallel for
for (i = start; i < stop; i++){
p = rand() % 1000 / 1000.0;//0到1之間
index = 0;
while (p>cfitness[index]){
index++;
}
newpopulation[i] = population[index];
}
for (i = start; i < stop; i++){
population[i] = newpopulation[i];
}
}
void SelectionOperator(void){
individual newpopulation[POPSIZE];
int start = 0;
int stop = (int)PopSize / 3;
Select(start, stop, newpopulation);
start = stop + 1;
stop = (int)(2 * PopSize / 3);
Select(start, stop, newpopulation);
start = stop + 1;
stop = PopSize;
Select(start, stop, newpopulation);
}
//随機數生成
int random(int randmax){
return rand() % randmax;
}
//交叉算子
void CrossoverOperator(void){
//TODO:變量命名不規範，需要重新設計
int i, j;
int index[POPSIZE];
int point, temp;
double p;
int CityNo; //定義為染色體編碼交換的 暫存BUFF
for (i = 0; i < PopSize; i++){
index[i] = i;//TODO:編号
}
//交換i 和 point+i 的編号
for (i = 0; i < PopSize; i++){
point = random(PopSize - i); //生成的随機數小于PopSize - i
temp = index[i];
index[i] = index[point + i];
index[point + i] = temp;
}
//交換 point 至 CHROMLENGTH 長度的 染色體編碼
#pragma omp parallel for
for (i = 0; i < PopSize - 1; i += 2)
{
p = rand() % 1000 / 1000.0;
if (p < Pc){
point = random(CHROMLENGTH - 1) + 1;
for (j = point; j < CHROMLENGTH; j++){
CityNo = population[index[i]].chrom[j];
population[index[i]].chrom[j] = population[index[i + 1]].chrom[j];
population[index[i + 1]].chrom[j] = CityNo;
}
}
}
}
//變異算子
void MutationOperator(){
int i, j;
double p;
for (i = 0; i < PopSize; i++){
for (j = 1; j < CHROMLENGTH; j++){// 染色體第一個元素為1，不能變異
p = rand() % 1000 / 1000.0;
//随機修改基因
if (p < Pm){
population[i].chrom[j] = random(CITYCOUNT - j) + 1;
}
}
}
}
//生成初始群體
void GenerateInitialPopulation(){
int i, j;
for (i = 0; i < PopSize; i++){
CitySet[i] = i + 1;
}
srand((unsigned)time(NULL));
for (i = 0; i < PopSize; i++){
//出發城市固定為第一個城市
population[i].chrom[0] = 1;
for (j = 1; j < CITYCOUNT; j++){
population[i].chrom[j] = random(CITYCOUNT - j) + 1;
//std::cout << population[i].chrom[j];
}
}
}
//生成下一代群體
void GenerateNextPopulation(){
SelectionOperator();
CrossoverOperator();
MutationOperator();
}
//從城市序列中删去一個體,删除i個體
void DeleteOneCity(int *workset, int position, int n){
for (int i = position - 1; i < n - 1; i++){
workset[i] = workset[i + 1];
}
}
//對染色體Chrom解碼，結果在Result中
void DecodeChromosome(int *chrom, int *Result){
int *p; //指向将要通路的城市
int i = 0;
int n = CITYCOUNT;
p = chrom;//出發城市
//初始工作城市數組
for (i = 0; i < CITYCOUNT; i++){
WorkSet[i] = CitySet[i];
}
//TODO:
for (i = 0; i < CITYCOUNT; i++){
Result[i] = WorkSet[*p - 1];//工作數組中第*p個元素是即将通路的城市
DeleteOneCity(WorkSet, *p, n);//從未通路的n個城市中删去剛通路的第*p個
n--;//未通路城市個數減1
p++;//即将通路城市指向下一個
}
}
//輸出結果
void OutputTextReport(){
int i = 0;
DecodeChromosome(currentbest.chrom, TempCitySet);
printf("群體代數：%d , 最短路徑： %f \n", generation, currentbest.value);
printf("個體編碼：[");
for (i = 0; i < CHROMLENGTH; i++){
printf(" %d", currentbest.chrom[i]);
}
printf("]\n");
printf("通路順序：[");
for (i = 0; i < CHROMLENGTH; i++){
printf(" %d", TempCitySet[i]);
}
printf("]\n\n");
}
//計算适應度
void CalculateFitness(){
int i, j;
double TotalDistance = 0.0;
//對每個個體，求其路徑總長度
for (i = 0; i < PopSize; i++){
DecodeChromosome(population[i].chrom, TempCitySet);
for (j = 1; j < CITYCOUNT; j++){
TotalDistance = TotalDistance + CityDistance[TempCitySet[j - 1] - 1][TempCitySet[j] - 1];
}
TotalDistance = TotalDistance + CityDistance[TempCitySet[CITYCOUNT - 1] - 1][0];
population[i].value = TotalDistance;
TotalDistance = 0.0;
}
//城市數目 除以 個體路徑總長度 = 個體适應度
//路徑越短，适應度越高
for (i = 0; i < PopSize; i++){
population[i].fitness = CITYCOUNT / population[i].value;
}
}
//尋找最優個體
void FindBestIndividual(void)
{
int i;
bestindividual = population[0];
//通過比較适應度來篩選，越大越好
for (i = 1; i<PopSize; i++)
{
if (population[i].fitness>bestindividual.fitness)
bestindividual = population[i];
}
//對第一代
if (generation == 0)
{
currentbest = bestindividual;
}
else
{
if (bestindividual.fitness>currentbest.fitness)
{
currentbest = bestindividual;
OutputTextReport(); /* 每更新一次目前最優值，輸出結果 */
//災變控制清零
//disaster_control = 0;
//Pc = c ;
//Pm = m ;
}
//else{
// disaster_control++;
// if (disaster_control > 50){
// Pc = disaster_Pc;
// Pm = disaster_Pm;
// }
//}
}
}
//距離計算公式
int CalculatorEuler(int *src1, int *src2){
return sqrt(pow((src1[X] - src2[X]), 2) + pow((src1[Y] - src2[Y]), 2));
}
//計算兩兩城市之間的距離
void CalculatorDistance(){
int i, j;
for (i = 0; i<CITYCOUNT; i++){
for (j = 0; j<CITYCOUNT; j++){
CityDistance[i][j] = CalculatorEuler(city[i], city[j]);
//CityDistance[i][j] = 100;
//printf(" %d", CityDistance[i][j]);
}
//printf("\n");
}
}
//結果圖形化顯示：出發城市-綠色 路線-紅色 城市-藍色
void ShowResult(){
//cvZero(tsp_image);
tsp_image = cv::imread("china.jpg");
cv::rectangle(
tsp_image,
cv::Point(city[0][X] - 5, city[0][Y] - 5),
//cvPoint(box.x+box.width,box.y+box.height),
cv::Point(city[0][X] + 5, city[0][Y] + 5),
cv::Scalar(0, 0,255), //綠色
2
);
#pragma omp parallel for
for (int i = 1; i < CITYCOUNT; i++){
cv::rectangle(
tsp_image,
cv::Point(city[i][X] - 5, city[i][Y] - 5),
//cvPoint(box.x+box.width,box.y+box.height),
cv::Point(city[i][X] + 5, city[i][Y] + 5),
cv::Scalar(0, 0, 255),
2
);//
}
#pragma omp parallel for
for (int i = 0; i < CITYCOUNT - 1; i++){
cv::line(tsp_image, cv::Point(city[TempCitySet[i] - 1][X], city[TempCitySet[i] - 1][Y]), cv::Point(city[TempCitySet[i + 1] - 1][X], city[TempCitySet[i + 1] - 1][Y]), line, 2);
if ((i + 1) == (CITYCOUNT - 1)){
cv::line(tsp_image, cv::Point(city[TempCitySet[i + 1] - 1][X], city[TempCitySet[i + 1] - 1][Y]), cv::Point(city[0][X], city[0][Y]), line, 2);
}
}
cv::imshow("遺傳算法解決旅行商問題仿真", tsp_image);
cv::waitKey(33);
}
int fileWrite()
{
int icount = pointcount;
fprintf(f, "pointcount:%d ", pointcount);
while (icount--)
fprintf(f, "{%d,%d},", city[icount][0], city[icount][1]);
fclose(f);
return 1;
}
int fileRead(){
int icount = 0;
char buff=',';
while (!feof(f)){
fscanf(f, "%f%d%f%d%f ", buff, city[icount][0], buff, city[icount][1],buff);
icount++;
}
fclose(f);
pointcount = icount;
return 1;
}
![K-近鄰算法以及圖像分類應用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)