📄 ga.cpp
字号:
free(dSiteWeight);
free(dCarCapacity);
return OK;
}
/******************************************************************/
/* 函数名： Randomize(low,high) */
/* 参 数： low--随机数的下限 */
/* high--随机数的上限 */
/* 返回值： 生成的随机数（类型为整数） */
/* 功 能： 随机产生随机产生指定范围内整数 */
/******************************************************************/
int Randomize(int low, int high)
{
return low+rand()%(high-low+1);
}
/******************************************************************/
/* 函数名： CalculateFitnessValue(stIndividual) */
/* 参 数： stIndividual--个体，计算后改变其适应度值 */
/* 返回值： OK-1; NO-0 */
/* 功 能： 对stIndividual计算其适应度值 */
/******************************************************************/
int CalculateFitnessValue(struct individual *stIndividual)
{
double dSumTime=0.0,dSumWeight=0.0;
double dBeta;
int ret;
dBeta=100.0-dAlpha;//dAlpha+dBeta=100
ret=DecodeChromosome(stIndividual);
if(ret==NO) return ret;
for(int i=0; i<stIndividual->iCarNum; i++){
dSumTime+=stIndividual->dCarFactTime[i];
if(dCarCapacity[i]!=0.0){
dSumWeight+=(stIndividual->dCarFactWeight[i]/dCarCapacity[i]);
}
else return NO;
}
if(dTimeLimit!=0&&stIndividual->iCarNum!=0){
stIndividual->dFitness = 100.0 -
(dAlpha*dSumTime/dTimeLimit+dBeta*dSumWeight)/stIndividual->iCarNum;
}
else return NO;
return OK;
}
/******************************************************************/
/* 函数名： DecodeChromosome(stIndividual) */
/* 参 数： stIndividual--个体 */
/* 返回值： OK-1; NO-0 */
/* 功 能： stIndividual解码， */
/* 计算出线路数、车辆的工作量、实际容量 */
/* iCarNum,dCarFactTime,dCarFactWeight,iLineStartPos */
/******************************************************************/
int DecodeChromosome(struct individual *stIndividual)
{
int pos1,pos2=0;
double dTotalTime=0.0,dTotalWeight=0.0;
stIndividual->iCarNum=1;
stIndividual->iLineStartPos[0]=stIndividual->iChrom[0];
for(int k=0; k<iChromLong; k++)
{
stIndividual->dCarFactWeight[stIndividual->iCarNum-1]=dTotalWeight;
stIndividual->dCarFactTime[stIndividual->iCarNum-1]=dTotalTime;
pos1=pos2;
pos2=stIndividual->iChrom[k];
dTotalWeight+=dSiteWeight[pos2-1];
dTotalTime+=dRunTime[pos1][pos2]+dWorkTime[pos2-1];
if(dTotalWeight>dCarCapacity[stIndividual->iCarNum-1] || dTotalTime>dTimeLimit){
stIndividual->iLineStartPos[stIndividual->iCarNum]=pos2;
stIndividual->iCarNum++;
dTotalWeight=dSiteWeight[pos2-1];
dTotalTime=dRunTime[0][pos2]+dWorkTime[pos2-1];
}
}
stIndividual->dCarFactWeight[stIndividual->iCarNum-1]=dTotalWeight;
stIndividual->dCarFactTime[stIndividual->iCarNum-1]=dTotalTime;
stIndividual->iLineStartPos[stIndividual->iCarNum]='\0';
stIndividual->dCarFactWeight[stIndividual->iCarNum]='\0';
stIndividual->dCarFactTime[stIndividual->iCarNum]='\0';
return OK;
}
/******************************************************************/
/* 函数名： SimulatedAnnealing(stOldIdividual) */
/* 参 数： stOldIndividual--旧个体，调用完成之后为新个体 */
/* 返回值： OK-1; NO-0 */
/* 功 能： 用模拟退火算法产生局部最优个体 */
/******************************************************************/
int SimulatedAnnealing(struct individual *stOldIndividual)
{
int iTemp,ret;
struct individual stTempChrom;
double dDeltaFitness;
double T;
int iFirstPosition,iSecondPosition;
if((stTempChrom.iChrom=(int*)calloc(iChromLong+1,sizeof(int)))==NULL){
return NO;
}
if((stTempChrom.dCarFactTime=(double*)calloc(iChromLong+1,sizeof(double)))==NULL){
return NO;
}
if((stTempChrom.dCarFactWeight=(double*)calloc(iChromLong+1,sizeof(double)))==NULL){
return NO;
}
if((stTempChrom.iLineStartPos=(int*)calloc(iChromLong+1,sizeof(int)))==NULL){
return NO;
}
T=dMaxTemperature;
while(T>dMinTemperature){
for(int j=0; j<iChromLong; j++){
stTempChrom.iChrom[j]=stOldIndividual->iChrom[j];
}
stTempChrom.iChrom[j]='\0';
for(int i=0; i<iNumCycle; i++){
iFirstPosition=Randomize(0,iChromLong-1);
iSecondPosition=Randomize(0,iChromLong-1);
iTemp=stTempChrom.iChrom[iFirstPosition];
stTempChrom.iChrom[iFirstPosition]=stTempChrom.iChrom[iSecondPosition];
stTempChrom.iChrom[iSecondPosition]=iTemp;
ret=CalculateFitnessValue(&stTempChrom);
if(ret==NO)return ret;
dDeltaFitness=stTempChrom.dFitness-stOldIndividual->dFitness;
if(dDeltaFitness<0||exp(-dDeltaFitness/T)>Randomize(1,10000)/10000.0){
CopyStruct(&stTempChrom,stOldIndividual);
}
}
T=T*dDownRate;
}
free(stTempChrom.iChrom);
free(stTempChrom.dCarFactTime);
free(stTempChrom.dCarFactWeight);
free(stTempChrom.iLineStartPos);
return OK;
}
/******************************************************************/
/* 函数名： InverseMutation(stMutationPop) */
/* 参 数： stMutationPop */
/* 返回值： OK-1,NO-0 */
/* 功 能： 倒位交换变异产生新个体 */
/******************************************************************/
int InverseMutation(struct individual *stMutationPop)
{
int pos1,pos2,i;
double p;
int iTempChrom;
pos1=Randomize(0,iChromLong-1);
pos2=Randomize(0,iChromLong-1);
p=Randomize(0,10000)/10000.0;
if(pos2<pos1){
i=pos2;
pos2=pos1;
pos1=i;
}
if(p<=dPMutation && pos1!=pos2){
for(i=0; i<((pos2-pos1)/2); i++){
iTempChrom=stMutationPop->iChrom[pos2-i];
stMutationPop->iChrom[pos2-i]=stMutationPop->iChrom[pos1+1+i];
stMutationPop->iChrom[pos1+1+i]=iTempChrom;
}
}
return OK;
}
/******************************************************************/
/* 函数名： TwoPointSwopMutation(stMutationPop) */
/* 参 数： stMutationPop */
/* 返回值： OK-1,NO-0 */
/* 功 能： 两点交换变异产生新个体 */
/******************************************************************/
int TwoPointSwopMutation(struct individual *stMutationPop)
{
int pos1,pos2;
double p;
int iTempChrom;
pos1=Randomize(0,iChromLong-1);
pos2=Randomize(0,iChromLong-1);
p=Randomize(0,10000)/10000.0;
if(p<=dPMutation && pos1!=pos2){
iTempChrom=stMutationPop->iChrom[pos2];
stMutationPop->iChrom[pos2]=stMutationPop->iChrom[pos1];
stMutationPop->iChrom[pos1]=iTempChrom;
}
return OK;
}
/******************************************************************/
/* 函数名： InsertMutation(stMutationPop) */
/* 参 数： stMutationPop */
/* 返回值： OK-1,NO-0 */
/* 功 能： 插入变异产生新个体 */
/******************************************************************/
int InsertMutation(struct individual *stMutationPop)
{
int pos1,pos2,i;
double p;
int iTempChrom;
pos1=Randomize(0,iChromLong-1);
pos2=Randomize(0,iChromLong-1);
p=Randomize(0,10000)/10000.0;
if(pos2<pos1){
i=pos2;
pos2=pos1;
pos1=i;
}
if(p<=dPMutation && pos1!=pos2){
iTempChrom=stMutationPop->iChrom[pos2];
for(i=pos2; i>pos1+1; i--){
stMutationPop->iChrom[i]=stMutationPop->iChrom[i-1];
}
stMutationPop->iChrom[i]=iTempChrom;
}
return OK;
}
/******************************************************************/
/* 函数名： InsertMutation(stMutationPop,iFlag) */
/* 参 数： stMutationPop,iFlag */
/* iFlag=1,调用InverseMutation */
/* iFlag=2,调用TwoPointSwopMutation */
/* iFlag=3,调用InsertMutation */
/* 返回值： OK-1,NO-0 */
/* 功 能： 变异操作 */
/******************************************************************/
int MutationOperator(struct individual *stMutationPop,int iFlag)
{
switch(iFlag){
case 1:
InverseMutation(stMutationPop);
break;
case 2:
TwoPointSwopMutation(stMutationPop);
break;
case 3:
InsertMutation(stMutationPop);
break;
default:
return NO;
}
return OK;
}
/******************************************************************/
/* 函数名： SelectionOperator() */
/* 参 数： 无 */
/* 返回值： 返回个体编号 */
/* 功 能： 用赌盘方法选择个体 */
/******************************************************************/
int SelectionOperator()
{
double dRnd=0,dSum=0;
int i;
dRnd=Randomize(0,10000)/10000.0;
if((iPopSize*dMaxFitness-dSumOfFitness)!=0.0){
for(i=0; dSum<=dRnd && i<iPopSize; i++)
dSum+=(dMaxFitness-stOldPopulation[i].dFitness)/(iPopSize*dMaxFitness-dSumOfFitness);
// fprintf(outfp,"\n\t*****[%f]*****[%d]\n",iPopSize*dMaxFitness-dSumOfFitness,i-1);
}
else i=Randomize(1,iPopSize);
return i-1;
}
/******************************************************************/
/* 函数名： Statistics() */
/* 参 数： 无 */
/* 返回值： Ok-1,NO-0 */
/* 功 能： 统计最大、最小、平均适应度，求最佳个体 */
/******************************************************************/
int Statistics()
{
int i=0,k=0;
dMaxFitness=-1.0;
dMinFitness=100000.0;
dSumOfFitness=0;
/* 找出最佳个体的位置，汇总适应度值，找出最大、最小适应度值 */
for(i=0; i<iPopSize; i++){
dSumOfFitness+=stOldPopulation[i].dFitness;
dMaxFitness=dMaxFitness<stOldPopulation[i].dFitness?stOldPopulation[i].dFitness:dMaxFitness;
if(dMinFitness>stOldPopulation[i].dFitness){
k=i;
dMinFitness=stOldPopulation[i].dFitness;
}
}
/* 求平均适应度值 */
if(iPopSize!=0)
dAvgFitness=dSumOfFitness/iPopSize;
else dAvgFitness=0.0;
/* 记录最佳个体 */
for(i=0; i<iChromLong; i++)
stBestFit.iChrom[i]=stOldPopulation[k].iChrom[i];
stBestFit.iChrom[i]='\0';
stBestFit.dFitness=stOldPopulation[k].dFitness;
stBestFit.iCarNum=stOldPopulation[k].iCarNum;
stBestFit.iGeneration=stOldPopulation[k].iGeneration;
for(i=0; i<iChromLong && stOldPopulation[k].iLineStartPos[i]!=0x00; i++){
stBestFit.dCarFactTime[i]=stOldPopulation[k].dCarFactTime[i];
stBestFit.dCarFactWeight[i]=stOldPopulation[k].dCarFactWeight[i];
stBestFit.iLineStartPos[i]=stOldPopulation[k].iLineStartPos[i];
}
stBestFit.dCarFactTime[i]='\0';
stBestFit.iLineStartPos[i]='\0';
stBestFit.dCarFactWeight[i]='\0';
return OK;
}
/*******************************************************************/
/* 函数名： CopyStruct(stOld,stNew) */
/* 参 数： stOld:被复制个体,stNew:复制后的新个体 */
/* 返回值： Ok-1,NO-0 */
/* 功 能： 复制个体 */
/*******************************************************************/
int CopyStruct(struct individual *stOld, struct individual *stNew)
{
int i=0;
stNew->dFitness=stOld->dFitness;
stNew->iCarNum=stOld->iCarNum;
stNew->iGeneration=stOld->iGeneration;
for(i=0; i<stOld->iCarNum; i++){
stNew->dCarFactTime[i]=stOld->dCarFactTime[i];
stNew->dCarFactWeight[i]=stOld->dCarFactWeight[i];
stNew->iLineStartPos[i]=stOld->iLineStartPos[i];
}
stNew->dCarFactTime[i]='\0';
stNew->dCarFactWeight[i]='\0';
stNew->iLineStartPos[i]='\0';
for(i=0; i<iChromLong; i++)
stNew->iChrom[i]=stOld->iChrom[i];
stNew->iChrom[i]='\0';
stNew->iXSite1=stOld->iXSite1;
stNew->iXSite2=stOld->iXSite2;
stNew->iParent[0]=stOld->iParent[0];
stNew->iParent[1]=stOld->iParent[1];
return OK;
}
/*******************************************************************/
/* 函数名： PartiallyMatchedCrossover(stOld1,stOld2,stNew1,stNew2)*/
/* 参 数： stOld1,stOld2:参加交叉的旧个体 */
/* stNew1,stNew2:运算之后的旧个体 */
/* 返回值： Ok-1,NO-0 */
/* 功 能： 部分匹配交叉产生新个体 */
/*******************************************************************/
int PartiallyMatchedCrossover(struct individual *stOld1,struct individual *stOld2,
struct individual *stNew1,struct individual *stNew2)
{
int i=0,j=0,k;
int pos1,pos2;
double p;
CopyStruct(stOld1,stNew1);
CopyStruct(stOld2,stNew2);
p=Randomize(0,10000)/10000.0;
if(p<dPCross){//小于交叉概率时，才进行交叉
pos1=Randomize(0,iChromLong-1);
pos2=Randomize(0,iChromLong-1);
while(pos1==pos2){
pos2=Randomize(0,iChromLong-1);
}
if(pos2<pos1){
k=pos2;
pos2=pos1;
pos1=k;
}
for(i=pos1+1; i<=pos2; i++){
for(j=0; j<iChromLong; j++){
if(stNew1->iChrom[j]==stOld2->iChrom[i])break;
}
k=stNew1->iChrom[i];
stNew1->iChrom[i]=stNew1->iChrom[j];
stNew1->iChrom[j]=k;
}
for(i=pos1+1; i<=pos2; i++){
for(j=0; j<iChromLong; j++){
if(stNew2->iChrom[j]==stOld1->iChrom[i])break;
}
k=stNew2->iChrom[i];
stNew2->iChrom[i]=stNew2->iChrom[j];
stNew2->iChrom[j]=k;
}
stNew1->iXSite1=pos1;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -