?? sga.cpp
字號:
//////////////////////////////////
//
// 實驗三： 基本sga遺傳算法
// 解安徽省17市TSP問題
// 姓名：饒玉佳 學號：E200602075
//
//
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<conio.h>
#define LENGTH 17 //染色體長度17,代表17個城市
#define POPSIZE 500
double distance[LENGTH][LENGTH];//城市之間的距離矩陣
double cityposition[LENGTH][2]={//城市的相對坐標
{1089.66, 541.02},//淮北0
{538.48, 594.36},//亳州1
{1191.26, 774.70},//宿州2
{1409.70, 1257.30},//蚌埠3
{558.80, 1259.84},//阜陽4
{1209.04, 1465.58},//淮南5
{1358.90, 1973.58},//合肥6
{929.64 , 2059.94},//六安7
{1965.96, 2319.02},//蕪湖8
{2166.62, 2580.64},//宣城9
{1473.20, 2776.22},//池州10
{1226.82, 2865.12}, //安慶11
{1661.16, 2603.50},//銅陵12
{1971.04, 3403.60},//黃山13
{1673.86, 2156.46},//巢湖14
{2006.60, 2075.18},//馬鞍山15
{1920.24, 1681.48}//滁州16
};
int popsize ; //種群大小
int maxgeneration; //最大世代數
double pcross = 0.0; //交叉率
double pmutation = 0.0; //變異率
double sumfitness; //種群個體適應值累計
struct individual //定義染色體個體結構體
{
int chrom[LENGTH]; //定義染色體二進制表達形式
double fitness; //染色體的適應值
};
int generation; //當前執行的世代數
int best_index; //本世代最好的染色體索引序號
struct individual bestindividual; //最佳染色體個體
struct individual currentbest; //當前最好的染色體個體 currentbest
int bestgeneration; //當前最好染色體個體產生的代數
struct individual oldpop[POPSIZE];//種群數組
struct individual newpop[POPSIZE];//新種群數組
/* 隨機數發生器使用的靜態變量 */
static double oldrand[55];
static int jrand;
static double rndx2;
static int rndcalcflag;
//函數聲明
void printline(FILE *);
void caldistancematrix(FILE *ffp);//設定城市距離矩陣
void initialoldpop(FILE *ffp); //ok-初始化當代種群
void generatenextpop(FILE *ffp); //產生下一代種群
void evaluateoldpop(); //評價種群
void calculateobjectfitness(); //計算種群適應度
void findbestindividual(); //尋找最好的染色體個體
int select(); //選擇操作
//將p中移除掉q中位置在j1，j2之間的元素，其余元素前移，返回剩下元素的數量
int searchanddelete(int *p,int* q,int j1,int j2);
void crossover(int *,int *,int *,int *,FILE *ffp); //交叉操作
void mutation(int *); //變異操作
void input(); //輸入接口
void outputtextreport(FILE *ffp); //每代輸出文字報告
void report(FILE *ffp);//輸出最終結果報告
//以下為一些隨機數相關函數
void advance_random();
int flip(double);int rnd(int, int);
void randomize();
double randomnormaldeviate();
float randomperc();float rndreal(float,float);
void warmup_random(float);
void main() //主函數
{
int i;
FILE *fp;
//打開文本文件
if((fp= fopen("test1.txt","w+"))==NULL)
{
printf("Can not open file!\n");
}
fprintf(fp,"本程序為使用基本SGA求解tsp問題\n");
generation=0; //初始化generation當前執行的代
input(); //初始化種群大小、交叉率、變異率
randomize(); // 初始化隨機數發生器
caldistancematrix(fp);//設定城市距離矩陣
initialoldpop(fp); //產生初始化種群
evaluateoldpop();
while(generation<maxgeneration) //小于最大世代數,執行循環體
{
generation++;
generatenextpop(fp); //生成子代種群(A.選擇; B.交叉; C.變異)
for(i = 0 ; i < popsize ; i++)
{
oldpop[i]=newpop[i];
}
evaluateoldpop(); //評價新生子代種群
outputtextreport(fp); //輸出當前子代種群統計報告
}
report(fp);//輸出最終報告
fclose(fp);
printf("計算結果已經輸出到test1.txt文件中。");
getch();
}
void printline(FILE *ffp)
{
fprintf(ffp,"\n*************************************************************\n");
}
void caldistancematrix(FILE *ffp)//設定城市距離矩陣
{
int i,j;
for(i=0;i<LENGTH;i++)
for(j=0;j<LENGTH;j++)
//求城市i,j之間的距離存放在distance[i][j]
{
distance[i][j]=sqrt( pow( cityposition[i][0]-cityposition[j][0] ,2) +
pow( cityposition[i][1]-cityposition[j][1] ,2) );
}
}
void initialoldpop(FILE *ffp) //種群初始化,對種群中每條染色體,生成0-16的不重復序列
{
int i,j,k,m;
srand( (unsigned)time( NULL ) );
for (i=0;i<popsize; i++)
{
//對oldpop[i]染色體生成隨機序列
int a[LENGTH] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
j =LENGTH;
m=0;
while(j > 0)
{
k =rand();
k%=j;
oldpop[i].chrom[m]=a[k];
a[k]=a[j-1]; // 把最后一個拷貝到剛生成的位置
m++;
j--;
}
}
}
void generatenextpop(FILE *ffp) //生成下一代
{
do{
//挑選交叉配對
mate1=select();
mate2=select();
crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[j].chrom,newpop[j+1].chrom,ffp);
mutation(newpop[j].chrom);
mutation(newpop[j+1].chrom);
j=j+2;
}
while(j<(popsize-1));
}
void evaluateoldpop() //評價種群
{
calculateobjectfitness(); //計算種群個體的適應度
findbestindividual(); //找到最好和最差的染色體個體
}
void calculateobjectfitness() //計算染色體個體適應值
{
int i,j;
for(i=0;i<popsize;i++)
{
oldpop[i].fitness=0.0;
for(j=0;(j+1)<LENGTH;j++)
oldpop[i].fitness+=distance[oldpop[i].chrom[j]][oldpop[i].chrom[j+1]];
oldpop[i].fitness+=distance[oldpop[i].chrom[LENGTH-1]][0];
}
}
void findbestindividual( ) //求最佳個體
{
int i;
sumfitness=0.0;
bestindividual=oldpop[0];
best_index=0;
sumfitness=+oldpop[0].fitness;
for (i=1;i<popsize; i++)
{
if (oldpop[i].fitness<bestindividual.fitness) //依次比較,找出最佳個體
{
bestindividual=oldpop[i];
best_index=i;
}
sumfitness+=oldpop[i].fitness; // 存放種群總體適應值
}//for
if (generation==0)
{
currentbest=bestindividual; //第一代最好的暫時存放在currentbest
bestgeneration=0;
}
if(bestindividual.fitness<currentbest.fitness)//第n代最好的，通過比較小于以往最好個體的話，暫時存放在currentbest
{
currentbest=bestindividual;
bestgeneration=generation;
}
}
//將p[]中移除掉q[]中位置在j1，j2之間的元素，其余元素前移，返回剩下元素的數量
int searchanddelete(int *p,int* q,int j1,int j2)
{
int num=LENGTH;
int i,j;
for(j=j1;j<j2;j++)
for(i=0;i<num;i++)
{ if(q[j]==p[i])
{
while((i+1)<num)
{
p[i]=p[i+1];
i++;
}
num--;//刪除一個元素，計數器減一
}
}
num=LENGTH-(j2-j1);//計算剩下元素的數目
return num;
}
int select() //輪盤賭選擇
{
float randomperc();
double sum,pick;
int i;
pick=randomperc(); //產生[0，1]上隨機數
sum=0.0;
if(sumfitness!=0)
{
for(i=0;(sum<pick)&&(i<popsize);i++)
sum+=oldpop[i].fitness/sumfitness;
}
else
i=rnd(1,popsize);
return(i-1);
}
void crossover(int *parent1,int *parent2,int *child1,int *child2,FILE *ffp) //ox交叉算法
{
int i,j;
int jcross1,jcross2;//交叉位置
int temp;
int num1,num2;
int temp1[LENGTH],temp2[LENGTH];//分別作為暫存parent1,parent2的數組
for(i=0;i<LENGTH;i++)
{
temp1[i]=parent1[i];
temp2[i]=parent2[i];
}
if(flip(pcross))
{
//在1和LENGTH-1之間隨機產生兩個交叉位置值
jcross1=-1;
jcross2=-1;
while(jcross1==jcross2)
{
jcross1=rand()%(LENGTH-1)+1;
jcross2=rand()%(LENGTH-1)+1;
}
if(jcross1>jcross2)
{
temp=jcross1;
jcross1=jcross2;
jcross2=temp;
}
//將切割點之間的元素復制到后代的切割點之間
j=jcross1;
while(j<jcross2)
{
child1[j]=temp1[j];
child2[j]=temp2[j];
j++;
}
//將parent2中,除掉child1中位置在jcross1，jcross2之間的元素，其余元素前移，返回剩下元素的數量
num1=searchanddelete(temp2,child1,jcross1,jcross2);
//將parent1中,除掉child2中位置在jcross1，jcross2之間的元素，其余元素前移，返回剩下元素的數量
num2=searchanddelete(temp1,child2,jcross1,jcross2);
//將去掉多余元素的parent2中值復制到child1中，避開jcross1，jcross2之間的元素
j=0;i=0;
while(j<jcross1)
{
child1[j]=temp2[i];
i++;
j++;
}
j=jcross2;//數組下標避開jcross1，jcross2之間的元素
while(i<num1)
{
child1[j]=temp2[i];
i++;
j++;
}
//將去掉多余元素的parent1中值復制到child2中，避開jcross1，jcross2之間的元素
j=0;i=0;
while(j<jcross1)
{
child2[j]=temp1[i];
i++;
j++;
}
j=jcross2;//數組下標避開jcross1，jcross2之間的元素
while(i<num2)
{
child2[j]=temp1[i];
i++;
j++;
}
}//if
else
{
for(i=0;i<LENGTH;i++)
{
child1[i]=temp1[i];
child2[i]=temp2[i];
}
}
}
void mutation(int *child) //變異是在染色體上隨機地選擇兩點，交換其編碼
{
int i;
int j1,j2,temp;
for(i=0;i<LENGTH;i++)
{
if (flip(pmutation))
{
j1=rand()%(LENGTH-1)+1;
j2=rand()%(LENGTH-1)+1;
temp=child[j1];
child[j1]=child[j2];
child[j2]=temp;
}
}
}
void input() //數據輸入
{
printf("初始化全局變量:\n");
printf(" 種群大小(50-500偶數)：");
scanf("%d", &popsize); //輸入種群大小，必須為偶數
if((popsize%2) != 0)
{
printf( " 種群大小已設置為偶數\n");
popsize++;
}
printf(" 最大世代數(100-300)："); //輸入最大世代數
scanf("%d", &maxgeneration);
printf(" 交叉率(0.2-0.99)："); //輸入交叉率
scanf("%lf", &pcross);
printf(" 變異率(0.001-0.1)："); //輸入變異率
scanf("%lf", &pmutation);
}
void outputtextreport(FILE *ffp)//數據輸出
{
int i;
printline(ffp);
fprintf(ffp,"\n\t當前世代=%d\n",generation);
fprintf(ffp,"本世代最好的染色體為:\n");
for(i=0;i<LENGTH;i++)
fprintf(ffp," %d-",bestindividual.chrom[i]);
fprintf(ffp,"\n總長度（相對長度）為%6.1f",currentbest.fitness);
}
void report(FILE *ffp)
{
int i;
fprintf(ffp,"\n");
fprintf(ffp," 統計結果: ");
fprintf(ffp,"\n");
fprintf(ffp,"\n種群數：%d", popsize);
fprintf(ffp,"\n最大世代數：%d", maxgeneration);
fprintf(ffp,"\n交叉率：%5.1f", pcross);
fprintf(ffp,"\n變異率：%5.1f", pmutation);
fprintf(ffp,"\n最終求得tsp問題的最短路徑解");
fprintf(ffp,"產生于%d代",bestgeneration);
fprintf(ffp,"\n其染色體編碼為：");
for( i = 0 ; i < LENGTH ; i++ )
fprintf(ffp," %d-",currentbest.chrom[i]);
fprintf(ffp,"\n總長度（相對長度）為%6.1f",currentbest.fitness);
fprintf(ffp,"\n");
}
void advance_random() // 產生55個隨機數
{
int j1;
double new_random;
for(j1 = 0; j1 < 24; j1++)
{
new_random = oldrand[j1] - oldrand[j1+31];
if(new_random < 0.0) new_random = new_random + 1.0;
oldrand[j1] = new_random;
}
for(j1 = 24; j1 < 55; j1++)
{
new_random = oldrand [j1] - oldrand [j1-24];
if(new_random < 0.0) new_random = new_random + 1.0;
oldrand[j1] = new_random;
}
}
int flip(double prob) //以一定概率產生0或1
{
if(randomperc() <= prob)
return(1);
else
return(0);
}
void randomize() /* 設定隨機數種子并初始化隨機數發生器 */
{
float randomseed;
int j1;
for(j1=0; j1<=54; j1++)
oldrand[j1] = 0.0;
jrand=0;
do
{
printf("請輸入隨機數種子[0-1]:\n");
scanf("%f",&randomseed);
}
while((randomseed < 0.0) || (randomseed > 1.0));
warmup_random(randomseed);
}
double randomnormaldeviate() // 產生隨機標準差
{
double t, rndx1;
if(rndcalcflag)
{ rndx1 = sqrt(- 2.0*log((double) randomperc()));
t = 6.2831853072 * (double) randomperc();
rndx2 = rndx1 * sin(t);
rndcalcflag = 0;
return(rndx1 * cos(t));
}
else
{
rndcalcflag = 1;
return(rndx2);
}
}
float randomperc() //與庫函數random()作用相同, 產生[0,1]之間一個隨機數
{
jrand++;
if(jrand >= 55)
{
jrand = 1;
advance_random();
}
return((float) oldrand[jrand]);
}
int rnd(int low,int high) //在整數low和high之間產生一個隨機整數
{
int i;
if(low >= high)
i = low;
else
{
i = ((int)randomperc() * (high - low + 1)) + low;
if(i > high) i = high;
}
return(i);
}
void warmup_random(float random_seed) //初始化隨機數發生器
{
int j1, ii;
double new_random, prev_random;
oldrand[54] = random_seed;
new_random = 0.000000001;
prev_random = random_seed;
for(j1 = 1 ; j1 <= 54; j1++)
{
ii = (21*j1)%54;
oldrand[ii] = new_random;
new_random = prev_random-new_random;
if(new_random<0.0) new_random = new_random + 1.0;
prev_random = oldrand[ii];
}
advance_random();
advance_random();
advance_random();
jrand = 0;
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -