statview.cpp

求解静态TSP 的IGT算法

// STATView.cpp : implementation of the CSTATView class
//22

#include "stdafx.h"
#include "STAT.h"
#include "DlgPara.h"
#include "STATDoc.h"
#include "STATView.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
//-------------------------------------------------------//

#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<stdio.h>

//#define FILE_PATH  "CHN144.TSP","r"
#define N_COLONY 1000
#define CITY     5000
//-------------------------------------------------------//
int flagRun=0;
int flagOpen=0;
struct ppp
{
	int x;
	int y;
};
struct ppp disDraw[N_COLONY];

//-------------------------------------------------------//
CString strFilePath="";
int once=0;
int show=0;



int     xColony=80;
int     xCity=144;
double  edgeSpeed=5000;
double  probab1=0.02, probab2=0.05;    //0.04(80) 0.03(50) 0.015(80)  0.05(50);
long    NOCHANGE=20000,maxGen=80000;

int     colony[N_COLONY][CITY];
double  cityXY[CITY][2];
double  city_dis[CITY][CITY];
double  dis_p[N_COLONY];
double  sumbest,sumTemp;
double  speed;
int     temp[CITY],ibest;
clock_t timeStart,timeNow,timeTemp,ltimepast;
long    GenNum,Ni;
//-------------------------------------------------------//
void    initialize();
int     position(int *tmp,int C);
void    invert(int pos_start,int pos_end);
void    printBest(long GenNum);
int     tempTest(int i);
void    mapped();
void    LastCP();
void    Main();
double  path(int tmp[],int k1,int k2);
//_______________________________________________________________________________________



/////////////////////////////////////////////////////////////////////////////
// CSTATView

IMPLEMENT_DYNCREATE(CSTATView, CView)

BEGIN_MESSAGE_MAP(CSTATView, CView)
	//{{AFX_MSG_MAP(CSTATView)
	ON_COMMAND(ID_MENU_RUN, OnMenuRun)
	ON_COMMAND(ID_MENU_PARA, OnMenuPara)
	ON_COMMAND(ID_FILE_OPEN, OnFileOpen)
	ON_COMMAND(ID_MENU_SHOW, OnMenuShow)
	ON_COMMAND(ID_MENU_PAUSE, OnMenuPause)
	ON_COMMAND(ID_MENU_STOP, OnMenuStop)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CSTATView construction/destruction

CSTATView::CSTATView()
{
	// TODO: add construction code here

}

CSTATView::~CSTATView()
{
}

BOOL CSTATView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs
	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CSTATView drawing

void CSTATView::OnDraw(CDC* pDC)
{
//	CSTATDoc* pDoc = GetDocument();
//	ASSERT_VALID(pDoc);
if(flagRun==1)
	{
	  if(show==0)
	  { Draw(pDC);
	    Invalidate(TRUE);once=1;
	  }
      else 
	  { Main();
	    Invalidate(TRUE);once=1;
        
		CString str1,str2,str3;//写最短距离
        str1.Format("%f",sumbest);
        pDC->TextOut(10,5,str1);
        str2.Format("%f",(double)(timeNow-timeStart)/CLOCKS_PER_SEC);
        pDC->TextOut(10,25,str2);

        if(once==1){once=0;ltimepast=clock();}
        str3.Format("%f",(double)(ltimepast-timeStart)/CLOCKS_PER_SEC  );
        pDC->TextOut(10,-20,"   ");//"Total time:"+str3+" second");

	  }
	}
if(flagRun==2) Draw(pDC);
	// TODO: add draw code for native data here
}

/////////////////////////////////////////////////////////////////////////////
// CSTATView printing

BOOL CSTATView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CSTATView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initializeialization before printing
}

void CSTATView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CSTATView diagnostics

#ifdef _DEBUG
void CSTATView::AssertValid() const
{
	CView::AssertValid();
}

void CSTATView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CSTATDoc* CSTATView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CSTATDoc)));
	return (CSTATDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CSTATView message handlers

void Main()
{ int C1,j,k,pos_C,pos_C1; int k1,k2,l1,l2,pos_flag;
  double disChange;
  static int i=0;
 
  for(;;)
  { for(j=0;j<xCity;j++)temp[j]=colony[i][j];
    disChange=0;pos_flag=0;
    pos_C=rand()%xCity;
   	for(;;)
    { 
      if((rand()/32768.0)<probab1)     //内变异算子
      { do pos_C1=rand()%xCity;while (pos_C1==pos_C);
        C1=colony[i][pos_C1];
      }
      else
	  { do j=rand()%xColony;while(j==i);
        k=position(colony[j],temp[pos_C]);
        C1=colony[j][(k+1)%xCity];
        pos_C1=position(temp,C1);
      }
	  if(speed>edgeSpeed && pos_C1<pos_C+2)break;         ///////////////////////	  
	  if((pos_C+1)%xCity==pos_C1 || (pos_C-1+xCity)%xCity==pos_C1 )break;

	  k1=temp[pos_C]; k2=temp[(pos_C+1)%xCity]; l1=temp[pos_C1]; l2=temp[(pos_C1+1)%xCity];
	  disChange+=city_dis[k1][l1]+city_dis[k2][l2]-city_dis[k1][k2]-city_dis[l1][l2];

	  invert(pos_C,pos_C1);  pos_flag++;if(pos_flag>xCity-1)break;  ////////////
      pos_C++; if(pos_C>=xCity)pos_C=0;                 /**********************/
      if(speed<edgeSpeed && disChange<0) {dis_p[i]+=disChange; disChange=0; if(tempTest(i)==1)return;}     //每有改变就计算
	}   //sumbest<31000 sumbest>=31000
	if( speed>=edgeSpeed && disChange<0 )	{dis_p[i]+=disChange; if(tempTest(i)==1)return;}  /////speed>=1500 &&
    i++;
    if(i>=xColony)
	{ 	Ni++; GenNum++;i=0;
 		probab1=probab1*(1-GenNum*0.001/maxGen);        //内逆转概率逐渐减小
		if( speed<edgeSpeed && (rand()/32767.0<probab2) )   //sumbest<32000
		{   mapped();  	
		    //probab2=PROB2*(GenNum*2.0/maxGen+1);    //部分交换概率逐渐增大
		}  
        if(NOCHANGE-Ni<1) LastCP();   //5可改
		if(GenNum>=maxGen || Ni>=NOCHANGE )
		{ flagRun=2; return; } // GenNum=0;Ni=0;strFilePath=""
	}
  }
}


void initialize()
{ int i,j,t,sign,mod=xCity,array[CITY];
  double d;
  timeStart=timeNow=timeTemp=clock();  
  
  srand( (unsigned)time( NULL ) );

  ///////////////////////////
  for(i=0;i<xCity;i++)    /*  initialize city_dis[] */
  for(j=0;j<xCity;j++)
  { if(j>i)
    { d=(cityXY[i][0]-cityXY[j][0])*(cityXY[i][0]-cityXY[j][0])*1.0+
        (cityXY[i][1]-cityXY[j][1])*(cityXY[i][1]-cityXY[j][1])*1.0;
      city_dis[i][j]=(float)sqrt(d);
      continue;
    }
    if(j==i) {city_dis[i][j]=0;continue;}
    if(j<i)  city_dis[i][j]=city_dis[j][i];
  }

  for(i=0;i<xCity;i++)array[i]=i;     //    initialize colony[][]     
  for(i=0;i<xColony;i++,mod=xCity)
  for(j=0;j<xCity;j++)
  { sign=rand()%mod;
    colony[i][j]=array[sign];
    t=array[mod-1];
    array[mod-1]=array[sign];
    array[sign]=t;
    mod--;
    if(mod==1) colony[i][++j]=array[0];
   }

   for(i=0;i<xColony;i++)		    /*    initialize dis_p[]       */
   { dis_p[i]=0;
     for(j=0;j<xCity-1;j++)
       dis_p[i]=dis_p[i]+city_dis[*(*(colony+i)+j)][*(*(colony+i)+j+1)];
     dis_p[i]=dis_p[i]+city_dis[**(colony+i)][*(*(colony+i)+xCity-1)];
   }

   ibest=0;             sumbest=dis_p[0];	    /*  initialize ibest & sumbest */
   sumTemp=sumbest*5;   speed=100000000;
   GenNum=0;        	Ni=0;                   /*   initialize GunNum & Ni    */
   strFilePath="";
}

void invert(int pos_start,int pos_end)
{ int j,k,t;
  if(pos_start<pos_end)
  {  j=pos_start+1; k=pos_end;
     for(;j<=k;j++,k--)
	 { t=temp[j]; temp[j]=temp[k]; temp[k]=t;  }
  }
  else
  {  
	if(xCity-1-pos_start<=pos_end+1)
	{  j=pos_end;k=pos_start+1; 
	   for(;k<xCity;j--,k++)
	   { t=temp[j];temp[j]=temp[k];temp[k]=t;   }
	   k=0;
	   for(;k<=j;k++,j--)
	   {  t=temp[j]; temp[j]=temp[k];temp[k]=t; }
    }
	else
	{  j=pos_end;k=pos_start+1;
	   for(;j>=0;j--,k++)
	   {  t=temp[j];temp[j]=temp[k];temp[k]=t;  }
       j=xCity-1;
	   for(;k<=j;k++,j--)
	   {  t=temp[j];temp[j]=temp[k]; temp[k]=t; }
    }
  }

}


int position(int *tmp,int C)
{ int j;
  for(j=0;j<xCity;j++)
  if(*(tmp+j)==C)break;
  return(j);
}

int tempTest(int i)
{  int j; double dt;
   for(j=0;j<xCity;j++)colony[i][j]=temp[j];
   if((int)sumbest>(int)dis_p[i])
   { sumbest=dis_p[i];ibest=i;Ni=0;
     timeNow=clock();
	 dt=(double)(timeNow-timeTemp)/CLOCKS_PER_SEC;;
     if(dt>0.1)
	 {  speed=(sumTemp-sumbest)/dt;
		sumTemp=sumbest;
		timeTemp=timeNow;
     }
	 return 1;
   }