?? opticalnetworkdlg.cpp
字號(hào):
// 搜索最小C值
double COpticalNetworkDlg::FindMiniC(double *data, int len)
{
double mini=data[0];
int mininum=0;
for(int n=0;n<len;n++)
{
if(data[n]<mini)
{
mini=data[n];
mininum=n;
}
}
return mini;
}
// 基因算法的具體實(shí)現(xiàn)
void COpticalNetworkDlg::OnButtonGa()
{
// 取得基因算法所需參數(shù)
UpdateData(TRUE);
// 分配內(nèi)存
OBD_OLT=(double *)malloc(sizeof(double)*m_nOBDNum);
ONU_OBD=(double *)malloc(sizeof(double)*m_nONUNum*m_nOBDNum);
// 根據(jù)群體規(guī)模和交叉概率計(jì)算出交叉?zhèn)€體個(gè)數(shù)
nGACrossNum = m_nGroupSize*m_GACrossProb/2;
// 根據(jù)群體規(guī)模和變異概率計(jì)算出變異個(gè)體個(gè)數(shù)
nGAVariNum = m_nGroupSize*m_GAVariProb;
// 設(shè)置已進(jìn)行過(guò)基因算法標(biāo)志
m_bIsGa=TRUE;
// 為當(dāng)前一代個(gè)體分配內(nèi)存
for(int k=0;k<m_nGroupSize;k++)
GeneSerial[k]=(int *) malloc(sizeof(int)*m_nONUNum);
// 為當(dāng)前一代個(gè)體交叉和變異后的新產(chǎn)生的個(gè)體分配內(nèi)存
for(int u=0;u<nGACrossNum*2+nGAVariNum;u++)
NextGeneSerial[u]=(int *)malloc(sizeof(int)*m_nONUNum);
// 參數(shù)有效性檢查
if(m_nONUNum>=m_nOBDLimit*m_nOBDNum)
{
AfxMessageBox("ONU數(shù)目過(guò)多，或者OBD數(shù)目過(guò)少，或OBD最大連接數(shù)目過(guò)小!",MB_OK|MB_ICONINFORMATION,NULL);
return;
}
if(m_nGroupSize<nGACrossNum*2+nGAVariNum)
{
AfxMessageBox("群體規(guī)模過(guò)小，或者交叉概率過(guò)大，或者變異概率過(guò)大!",MB_OK|MB_ICONINFORMATION,NULL);
return;
}
for(int n1=0;n1<m_nOBDNum;n1++)
{
OBD_OLT[n1]=sqrt((m_OBDX[n1]-m_OLTX)*(m_OBDX[n1]-m_OLTX)+(m_OBDY[n1]-m_OLTY)*(m_OBDY[n1]-m_OLTY));
nOBDLimit[n1]=m_nOBDLimit;
}
int LimitTotal=0;
int CurGroupSize=1;
for(int p=0;p<m_nOBDNum;p++)
LimitTotal+=nOBDLimit[p];
for(int q=0;q<m_nONUNum;q++)
{
if(CurGroupSize>MAX_GROUPSIZE*10)
break;
else
{
CurGroupSize=LimitTotal*CurGroupSize;
LimitTotal--;
}
}
if(m_nGroupSize>CurGroupSize||m_nGroupSize>MAX_GROUPSIZE*10)
return;
// 計(jì)算ONU和OBD之間距離
for(int i=0;i<m_nONUNum;i++)
for(int j=0;j<m_nOBDNum;j++)
*(ONU_OBD+i*m_nOBDNum+j)=sqrt((m_ONUX[i]-m_OBDX[j])*(m_ONUX[i]-m_OBDX[j])+(m_ONUY[i]-m_OBDY[j])*(m_ONUY[i]-m_OBDY[j]));
// 產(chǎn)生初始基因序列
for(int i1=0;i1<m_nGroupSize;i1++)
{
for(int k=0;k<m_nOBDNum;k++)
nCurOBDLimit[i1][k]=0;
for(int j1=0;j1<m_nONUNum;j1++)
{
int RandInt;
Random:RandInt=RandomInt(0,m_nOBDNum-1);
if(nCurOBDLimit[i1][RandInt]<=nOBDLimit[RandInt]-1)
{
*(GeneSerial[i1]+j1)=RandInt;
nCurOBDLimit[i1][RandInt]++;
}
else
goto Random; // 不滿足約束條件2時(shí)，重新產(chǎn)生基因序列
}
}
// 基因算法具體實(shí)現(xiàn)
for( nCurGANum=0;nCurGANum<m_GANum;nCurGANum++)
{
// 計(jì)算當(dāng)前一代群體中每個(gè)個(gè)體的適應(yīng)度數(shù)值F
for(int i=0;i<m_nGroupSize;i++)
{
Cost[i]=0;
for(int j=0;j<m_nONUNum;j++)
{
Cost[i]=Cost[i]+*(ONU_OBD+j*m_nOBDNum+*(GeneSerial[i]+j))+*(OBD_OLT+*(GeneSerial[i]+j));
temp[i][j]=*(ONU_OBD+j*m_nOBDNum+*(GeneSerial[i]+j));
}
F[i]=1/Cost[i];
TotalF=F[i]+TotalF;
}
// 歸一化F值
for(int a=0;a<m_nGroupSize;a++)
Pm[a]=F[a]/TotalF*100;
// 將當(dāng)前一代群體中的個(gè)體按F值從大到小排序
for(int b=0;b<m_nGroupSize-1;b++)
{
FindMiniF(Pm,m_nGroupSize-b);
}
m_CurGANum=nCurGANum;
// 查找當(dāng)前一代中的最小費(fèi)用個(gè)體
m_MiniCost=FindMiniC(Cost,m_nGroupSize);
// 繪制圖形
DrawNetwork();
// 交叉操作
for(int c=0;c<nGACrossNum;c++)
{
int nExchangePos,temp=0;
int nNextOBD1;
int nNextOBD2;
int LimitLoop=0;
int new1=0; // 發(fā)生交叉?zhèn)€體1在當(dāng)前一代群體中位置
int new2=0; // 發(fā)生交叉?zhèn)€體2在當(dāng)前一代群體中位置
//int temp=0;
Limit1:new1=RandomInt(0,m_nGroupSize-1);
temp=RandomInt(0,m_nGroupSize-1);
// 由于當(dāng)前一代群體中個(gè)體已經(jīng)按照F從大到小排序
// 如果new1>temp,則位置new1處個(gè)體F值小于temp處個(gè)體F值
// 所以選定new1=temp處個(gè)體進(jìn)行交叉，體現(xiàn)了F值較大的個(gè)體有較多機(jī)會(huì)進(jìn)行交叉
if(new1>temp)
new1=temp;
new2=RandomInt(0,m_nGroupSize-1);
temp=RandomInt(0,m_nGroupSize-1);
if(new2>temp)
new2=temp;
for(int g=0;g<m_nOBDNum;g++)
{
nNextOBDLimit[2*c][g]=nCurOBDLimit[new1][g];
nNextOBDLimit[2*c+1][g]=nCurOBDLimit[new2][g];
}
Limit2:nExchangePos=RandomInt(0,m_nONUNum-1); // 被選中交叉?zhèn)€體的基因序列中用于交叉的基因位
nNextOBD1=nNextOBDLimit[2*c][*(GeneSerial[new2]+nExchangePos)]+1;
nNextOBD2=nNextOBDLimit[2*c+1][*(GeneSerial[new1]+nExchangePos)]+1;
LimitLoop++;
if((nNextOBD1>nOBDLimit[*(GeneSerial[new2]+nExchangePos)])||(nNextOBD2>nOBDLimit[*(GeneSerial[new1]+nExchangePos)]))
if(LimitLoop>50) // 跳轉(zhuǎn)到Limit2重新產(chǎn)生交叉位滿50次，仍未滿足約束條件2，
goto Limit1; // 則跳轉(zhuǎn)到Limit1，重新產(chǎn)生交叉?zhèn)€體在當(dāng)前一代群體中位置
else
goto Limit2; // 交叉后，不滿足約束條件2，跳轉(zhuǎn)到Limit2重新產(chǎn)生交叉位
// 交叉成功，產(chǎn)生新的個(gè)體
for(int m=0;m<m_nONUNum;m++)
{
if(m==nExchangePos)
{
*(NextGeneSerial[2*c]+nExchangePos)=*(GeneSerial[new2]+nExchangePos);
*(NextGeneSerial[2*c+1]+nExchangePos)=*(GeneSerial[new1]+nExchangePos);
nNextOBDLimit[2*c][*(GeneSerial[new2]+nExchangePos)]++;
nNextOBDLimit[2*c][*(GeneSerial[new1]+nExchangePos)]--;
nNextOBDLimit[2*c+1][*(GeneSerial[new2]+nExchangePos)]--;
nNextOBDLimit[2*c+1][*(GeneSerial[new1]+nExchangePos)]++;
}
else
{
*(NextGeneSerial[2*c]+m)=*(GeneSerial[new1]+m);
*(NextGeneSerial[2*c+1]+m)=*(GeneSerial[new2]+m);
}
}
}
// 變異操作
for(int d=0;d<nGAVariNum;d++)
{
int nVariIndividual=0;
int nVariPos=0;
int VariLoop=0;
Vari1:VariLoop=0;
nVariIndividual=RandomInt(0,m_nGroupSize-1); // 發(fā)生變異個(gè)體在當(dāng)前一代群體中位置
nVariPos=RandomInt(0,m_nONUNum-1); // 發(fā)生變異個(gè)體的基因序列中變異的基因位
for(int z=0;z<m_nOBDNum;z++)
nNextOBDLimit[2*nGACrossNum+d][z]=nCurOBDLimit[nVariIndividual][z];
for(int h=0;h<m_nONUNum;h++)
{
if(h==nVariPos)
{
int nVariValue;
int nNextVari;
Vari2: nVariValue=RandomInt(0,m_nOBDNum-1); // 產(chǎn)生變異位變異后的值
if(nVariValue==*(GeneSerial[nVariIndividual]+nVariPos))
{
VariLoop++;
if(VariLoop==100) // 跳轉(zhuǎn)到Vari2滿50次，隨機(jī)產(chǎn)生的變異位的值仍等于待變異位的當(dāng)前值
goto Vari1; // 則跳轉(zhuǎn)到Vair1，重新產(chǎn)生變異個(gè)體在當(dāng)前一代群體中位置
else
goto Vari2; // 變異位的值等于待變異位的當(dāng)前值，跳轉(zhuǎn)到Vari2，重新產(chǎn)生變異位變異后的值
}
nNextVari=nNextOBDLimit[2*nGACrossNum+d][nVariValue]+1;
if(nNextVari>nOBDLimit[nVariValue])
{
VariLoop++;
if(VariLoop==100)// 跳轉(zhuǎn)到Vari2重新產(chǎn)生變異位滿50次，仍未滿足約束條件2，
goto Vari1; // 則跳轉(zhuǎn)到Vair1，重新產(chǎn)生變異個(gè)體在當(dāng)前一代群體中位置
else
goto Vari2; // 變異后，不滿足約束條件2，跳轉(zhuǎn)到Vari2重新產(chǎn)生變異位
}
// 變異成功
*(NextGeneSerial[2*nGACrossNum+d]+h)=nVariValue;
nNextOBDLimit[2*nGACrossNum+d][nVariValue]++;
nNextOBDLimit[2*nGACrossNum+d][*(GeneSerial[nVariIndividual]+nVariPos)]--;
}
else
*(NextGeneSerial[2*nGACrossNum+d]+h)=*(GeneSerial[nVariIndividual]+h);
}
}
// 產(chǎn)生下一代群體
for(int e=0;e<2*nGACrossNum+nGAVariNum;e++)
{
for(int f=0;f<m_nONUNum;f++)
*(GeneSerial[m_nGroupSize-e-1]+f)=*(NextGeneSerial[e]+f);
for(int x=0;x<m_nOBDNum;x++)
nCurOBDLimit[m_nGroupSize-e-1][x]=nNextOBDLimit[e][x];
}
Sleep(m_SleepTime);
}
}
// 產(chǎn)生1～100之間的隨機(jī)整數(shù)
int COpticalNetworkDlg::RandomInt(int low,int high)
{
int result;
result=rand();
return result%(high+1);
}
// 搜索最小F值
void COpticalNetworkDlg::FindMiniF(double *data,int len)
{
double mini=data[0];
int mininum=0;
int CurOBDTemp;
int *GeneSerTemp;
double datatemp;
for(int n=0;n<len;n++)
if(mini>data[n])
{
mini=data[n];
mininum=n;
}
if(mininum!=len-1)
{
datatemp=*(data+len-1);
*(data+len-1)=*(data+mininum);
*(data+mininum)=datatemp;
GeneSerTemp=GeneSerial[len-1];
GeneSerial[len-1]=GeneSerial[mininum];
GeneSerial[mininum]=GeneSerTemp;
for(int n2=0;n2<m_nOBDNum;n2++)
{
CurOBDTemp=nCurOBDLimit[mininum][n2];
nCurOBDLimit[mininum][n2]=nCurOBDLimit[len-1][n2];
nCurOBDLimit[len-1][n2]=CurOBDTemp;
}
}
}
void COpticalNetworkDlg::DrawNetwork()
{
int NetLeft,NetBottom;
int x_coordinate=0,y_coordinate=0;
char txt[4];
CString info;
CDC* pDC=GetDC();
CRect RectClient,Workarea;
GetClientRect(RectClient);
Workarea.left=RectClient.left+RectClient.right/3-15;
Workarea.right=RectClient.right;
Workarea.top=RectClient.top;
Workarea.bottom=RectClient.bottom;
pDC->Rectangle(Workarea);
pDC->SetBkColor(0x00FFFFFF);
NetLeft=Workarea.left+25;
NetBottom=Workarea.bottom-20;
pDC->MoveTo(NetLeft,NetBottom);
pDC->LineTo(NetLeft+500,NetBottom);
pDC->MoveTo(NetLeft,NetBottom);
pDC->LineTo(NetLeft,NetBottom-500);
pDC->TextOut(NetLeft+500,NetBottom-12,"X");
pDC->TextOut(NetLeft+5,NetBottom-505,"Y");
pDC->SetTextColor(0x000000FF);
info.Format("已進(jìn)化代數(shù) %d",m_CurGANum+1);
pDC->TextOut(NetLeft+100,NetBottom-520,info);
info.Format("最小費(fèi)用 %5.5f",m_MiniCost);
pDC->TextOut(NetLeft+250,NetBottom-520,info);
pDC->SetTextColor(GetSysColor(COLOR_WINDOWTEXT));
for(x_coordinate=0;x_coordinate<=10;x_coordinate++)
{
char xn[4];
wsprintf(xn,"%d",x_coordinate*10);
pDC->TextOut(NetLeft+x_coordinate*50-8,NetBottom+2,xn);
}
for(y_coordinate=1;y_coordinate<=10;y_coordinate++)
{
char yn[4];
wsprintf(yn,"%d",y_coordinate*10);
if(y_coordinate==10)
pDC->TextOut(NetLeft-24,NetBottom-y_coordinate*50,yn);
else
pDC->TextOut(NetLeft-22,NetBottom-y_coordinate*50,yn);
}
PtrOldPen=pDC->SelectObject(&PenOBD);
for(int b1=0;b1<m_nOBDNum;b1++)
{
pDC->MoveTo(NetLeft+m_OBDX[b1]*5,NetBottom-m_OBDY[b1]*5);
pDC->LineTo(NetLeft+m_OLTX*5,NetBottom-m_OLTY*5);
}
for(int b2=0;b2<m_nONUNum;b2++)
{
pDC->SelectObject(&PenONU[colornum]);
pDC->MoveTo(NetLeft+m_ONUX[b2]*5,NetBottom-m_ONUY[b2]*5);
pDC->LineTo(NetLeft+m_OBDX[*(GeneSerial[0]+b2)]*5,NetBottom-m_OBDY[*(GeneSerial[0]+b2)]*5);
colornum++;
if(colornum==16)
colornum=0;
}
pDC->SelectObject(PtrOldPen);
pDC->SetTextColor(0x000000FF);
pDC->TextOut(NetLeft+m_OLTX*5-7,NetBottom-m_OLTY*5-7,"★");
pDC->SetTextColor(0x00FF0000);
for(int a1=0;a1<m_nOBDNum;a1++)
{
wsprintf(txt,"%d",a1+1);
pDC->TextOut(NetLeft+m_OBDX[a1]*5-3,NetBottom-m_OBDY[a1]*5-9,txt);
}
pDC->SetTextColor(0x0000FF00);
for(int a2=0;a2<m_nONUNum;a2++)
{
wsprintf(txt,"%d",a2+1);
pDC->TextOut(NetLeft+m_ONUX[a2]*5-3,NetBottom-m_ONUY[a2]*5-9,txt);
}
pDC->SetTextColor(0x00FFFFFF);
pDC->TextOut(NetLeft+507,NetBottom-508,"c");
pDC->SetTextColor(GetSysColor(COLOR_WINDOWTEXT));
pDC->SetBkColor(GetSysColor(COLOR_WINDOW));
}
void COpticalNetworkDlg::OnAbout()
{
CAboutDlg dlg;
dlg.DoModal();
}
void COpticalNetworkDlg::OnOK()
{
CDialog::OnOK();
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -