china45dlg.cpp

遗传算法解中国旅行商问题

// China45Dlg.cpp : implementation file
//

#include "stdafx.h"
#include "stdlib.h"
#include "math.h"

#include "China45.h"
#include "China45Dlg.h"
#include "GASetDlg.h"
#include "ResultDlg.h"
#include "PopNode.h"
#include "China45Recordset.h"

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

//自定义全局变量

//用于绘制连线的颜色
COLORREF COLOR[16]={0x008080F0,0x0000D080,0x00800080,0x008080E0,  
                    0x0080E000,0x00E08000,0x0000E080,0x003020D0,
					0x0080F080,0x00F08080,0x008080F0,0x00F0F080,
					0x0080F020,0x00208080,0x008020F0,0x00A02080,};

static double m_distance[MAXCHROM*MAXCHROM]={
0,268,3526,587,1533,1217,1232,997,2145,1524,1683,1170,1147,1490,2665,1385,2536,1895,1608,2275,1925,1855,2011,1934,2970,2308,2091,4085,2103,2895,2447,2648,2358,3196,2636,3121,3624,2873,3223,3506,3247,3309,3617,3582,3725,
268,0,3460,320,1355,992,991,729,1964,1291,1461,901,879,1233,2487,1116,2345,1645,1340,2045,1656,1588,1743,1669,2743,2044,1824,3904,1840,2653,2178,2384,2093,2945,2369,2858,3381,2606,2955,3245,2978,3040,3353,3316,3458,
3526,3460,0,3355,2300,2777,2887,3307,1918,2691,2520,3356,3427,2998,1658,3339,1863,2814,3324,2433,3465,3655,3344,3766,2367,3184,3725,1806,3878,2655,3479,3273,3944,2964,3992,3347,2876,4037,3784,3463,3895,3885,3660,3774,3899,
587,320,3355,0,1144,725,700,410,1737,1006,1188,585,570,919,2256,799,2099,1337,1021,1757,1341,1284,1424,1372,2455,1724,1519,3664,1545,2351,1860,2064,1794,2633,2065,2539,3077,2298,2636,2926,2661,2722,3033,2996,3138,
1533,1355,2300,1144,0,478,587,1012,611,455,388,1057,1127,755,1133,1063,1006,804,1104,887,1345,1476,1288,1597,1523,1343,1621,2552,1746,1539,1621,1625,1899,1904,2061,2000,2240,2212,2280,2337,2352,2387,2498,2521,2675,
1217,992,2777,725,478,0,130,533,1025,310,468,587,654,423,1538,635,1375,720,741,1057,1043,1117,1040,1236,1753,1221,1303,2939,1402,1684,1446,1550,1596,2004,1805,1992,2412,1995,2186,2364,2237,2286,2498,2491,2642,
1232,991,2887,700,587,130,0,442,1096,307,496,470,539,316,1600,505,1425,668,616,1057,924,990,933,1108,1755,1140,1181,2986,1276,1663,1348,1474,1474,1967,1690,1928,2391,1886,2100,2305,2147,2198,2433,2418,2568,
997,729,3307,410,1012,533,442,0,1538,726,924,181,192,550,2037,389,1857,977,611,1439,932,891,1014,987,2127,1321,1122,3410,1163,1993,1449,1660,1405,2254,1668,2137,2712,1896,2226,2525,2251,2312,2627,2588,2729,
2145,1964,1918,1737,611,1025,1096,1538,0,829,636,1533,1608,1116,522,1467,406,897,1419,604,1548,1738,1431,1848,1028,1319,1810,1941,1961,1143,1623,1496,2042,1529,2124,1747,1767,2213,2115,2020,2208,2224,2203,2262,2412,
1524,1291,2691,1006,455,310,307,726,829,0,198,704,779,311,1314,649,1131,428,655,753,892,1023,845,1143,1451,957,1167,2685,1291,1374,1210,1272,1447,1694,1621,1699,2102,1787,1920,2065,1979,2023,2205,2206,2358,
1683,1461,2520,1188,388,468,496,924,636,198,0,901,975,482,1115,831,933,415,805,596,996,1154,919,1272,1288,954,1271,2490,1407,1240,1234,1241,1537,1582,1683,1634,1964,1826,1896,1985,1966,2002,2137,2151,2305,
1170,901,3356,585,1057,587,470,181,1533,704,901,0,74,462,2014,216,1824,877,441,1363,755,709,847,807,2037,1169,941,3359,984,1882,1279,1504,1224,2124,1486,1984,2592,1715,2056,2373,2077,2140,2468,2423,2563,
1147,879,3427,570,1127,654,539,192,1608,779,975,74,0,534,2089,258,1898,944,480,1434,781,713,883,804,2105,1216,948,3432,979,1945,1312,1548,1225,2180,1494,2029,2651,1728,2086,2418,2104,2168,2509,2460,2598,
1490,1233,2998,919,755,423,316,550,1116,311,482,462,534,0,1571,351,1374,426,349,901,623,724,617,844,1580,834,890,2898,1001,1443,1032,1173,1179,1714,1382,1636,2164,1572,1789,2019,1833,1885,2138,2116,2264,
2665,2487,1658,2256,1133,1538,1600,2037,522,1314,1115,2014,2089,1571,0,1920,216,1263,1834,805,1895,2107,1754,2207,796,1543,2132,1419,2291,1037,1831,1615,2322,1393,2344,1724,1483,2379,2146,1908,2254,2252,2103,2195,2334,
1385,1116,3339,799,1063,635,505,389,1467,649,831,216,258,351,1920,0,1720,717,225,1220,542,524,630,633,1872,957,745,3228,808,1699,1063,1290,1035,1924,1287,1771,2399,1510,1839,2160,1862,1924,2253,2207,2347,
2536,2345,1863,2099,1006,1375,1425,1857,406,1131,933,1824,1898,1374,216,1720,0,1050,1626,588,1679,1892,1537,1991,689,1329,1915,1564,2074,885,1620,1414,2106,1258,2132,1556,1415,2174,1967,1769,2072,2074,1962,2044,2187,
1895,1645,2814,1337,804,720,668,977,897,428,415,877,944,426,1263,717,1050,0,582,506,651,849,538,956,1160,541,913,2515,1064,1017,818,845,1157,1300,1277,1272,1740,1412,1496,1643,1560,1600,1779,1777,1929,
1608,1340,3324,1021,1104,741,616,611,1419,655,805,441,480,349,1834,225,1626,582,0,1087,330,378,405,498,1706,738,567,3092,661,1512,838,1068,860,1717,1093,1548,2199,1306,1615,1937,1640,1701,2028,1982,2122,
2275,2045,2433,1757,887,1057,1057,1439,604,753,596,1363,1434,901,805,1220,588,506,1087,0,1099,1317,952,1411,698,750,1328,2009,1488,654,1048,893,1519,1017,1560,1163,1369,1625,1512,1469,1605,1622,1641,1684,1837,
1925,1656,3465,1341,1345,1043,924,932,1548,892,996,755,781,623,1895,542,1679,651,330,1099,0,226,166,312,1621,529,276,3049,414,1382,537,817,557,1522,767,1291,2018,976,1306,1676,1323,1387,1748,1688,1823,
1855,1588,3655,1284,1476,1117,990,891,1738,1023,1154,709,713,724,2107,524,1892,849,378,1317,226,0,391,120,1848,746,236,3275,286,1605,697,1009,514,1730,781,1470,2229,1018,1432,1848,1432,1501,1904,1831,1957,
2011,1743,3344,1424,1288,1040,933,1014,1431,845,919,847,883,617,1754,630,1537,538,405,952,166,391,0,466,1456,368,381,2885,538,1216,436,675,621,1363,776,1154,1858,955,1212,1542,1241,1300,1626,1577,1716,
1934,1669,3766,1372,1597,1236,1108,987,1848,1143,1272,807,804,844,2207,633,1991,956,498,1411,312,120,466,0,1916,797,188,3349,176,1662,701,1031,423,1762,705,1476,2262,949,1401,1847,1392,1464,1890,1808,1929,
2970,2743,2367,2455,1523,1753,1755,2127,1028,1451,1288,2037,2105,1580,796,1872,689,1160,1706,698,1621,1848,1456,1916,0,1127,1783,1438,1941,312,1342,1036,1885,604,1817,986,738,1783,1429,1117,1543,1526,1314,1415,1548,
2308,2044,3184,1724,1343,1221,1140,1321,1319,957,954,1169,1216,834,1543,957,1329,541,738,750,529,746,368,797,1127,0,656,2565,814,864,303,340,786,995,810,815,1490,898,965,1204,1022,1066,1309,1281,1429,
2091,1824,3725,1519,1621,1303,1181,1122,1810,1167,1271,941,948,890,2132,745,1915,913,567,1328,276,236,381,188,1783,656,0,3222,160,1517,521,858,293,1593,546,1293,2093,782,1214,1661,1207,1278,1702,1620,1741,
4085,3904,1806,3664,2552,2939,2986,3410,1941,2685,2490,3359,3432,2898,1419,3228,1564,2515,3092,2009,3049,3275,2885,3349,1438,2565,3222,0,3379,1724,2774,2452,3319,1816,3226,2259,1466,3155,2686,2179,2801,2759,2347,2496,2573,
2103,1840,3878,1545,1746,1402,1276,1163,1961,1291,1407,984,979,1001,2291,808,2074,1064,661,1488,414,286,538,176,1941,814,160,3379,0,1670,653,995,258,1731,549,1411,2230,798,1288,1767,1267,1341,1794,1702,1814,
2895,2653,2655,2351,1539,1684,1663,1993,1143,1374,1240,1882,1945,1443,1037,1699,885,1017,1512,654,1382,1605,1216,1662,312,864,1517,1724,1670,0,1050,731,1595,385,1511,692,728,1471,1129,887,1241,1229,1078,1160,1302,
2447,2178,3479,1860,1621,1446,1348,1449,1623,1210,1234,1279,1312,1032,1831,1063,1620,818,838,1048,537,697,436,701,1342,303,521,2774,653,1050,0,343,544,1078,512,775,1577,598,776,1151,806,864,1213,1151,1286,
2648,2384,3273,2064,1625,1550,1474,1660,1496,1272,1241,1504,1548,1173,1615,1290,1414,845,1068,893,817,1009,675,1031,1036,340,858,2452,995,731,343,0,878,736,780,480,1236,768,655,869,730,762,968,943,1093,
2358,2093,3944,1794,1899,1596,1474,1405,2042,1447,1537,1224,1225,1179,2322,1035,2106,1157,860,1519,557,514,621,423,1885,786,293,3319,258,1595,544,878,0,1601,292,1240,2092,542,1062,1574,1030,1106,1583,1479,1584,
3196,2945,2964,2633,1904,2004,1967,2254,1529,1694,1582,2124,2180,1714,1393,1924,1258,1300,1717,1017,1522,1730,1363,1762,604,995,1593,1816,1731,385,1078,736,1601,0,1450,443,500,1347,881,515,997,966,711,812,944,
2636,2369,3992,2065,2061,1805,1690,1668,2124,1621,1683,1486,1494,1382,2344,1287,2132,1277,1093,1560,767,781,776,705,1817,810,546,3226,549,1511,512,780,292,1450,0,1048,1923,250,802,1347,756,833,1333,1218,1312,
3121,2858,3347,2539,2000,1992,1928,2137,1747,1699,1634,1984,2029,1636,1724,1771,1556,1272,1548,1163,1291,1470,1154,1476,986,815,1293,2259,1411,692,775,480,1240,443,1048,0,878,917,445,388,561,540,506,522,676,
3624,3381,2876,3077,2240,2412,2391,2712,1767,2102,1964,2592,2651,2164,1483,2399,1415,1740,2199,1369,2018,2229,1858,2262,738,1490,2093,1466,2230,728,1577,1236,2092,500,1923,878,0,1793,1257,715,1367,1316,880,1029,1109,
2873,2606,4037,2298,2212,1995,1886,1896,2213,1787,1826,1715,1728,1572,2379,1510,2174,1412,1306,1625,976,1018,955,949,1783,898,782,3155,798,1471,598,768,542,1347,250,917,1793,0,595,1167,530,607,1128,1001,1083,
3223,2955,3784,2636,2280,2186,2100,2226,2115,1920,1896,2056,2086,1789,2146,1839,1967,1496,1615,1512,1306,1432,1212,1401,1429,965,1214,2686,1288,1129,776,655,1062,881,802,445,1257,595,0,582,116,109,533,417,527,
3506,3245,3463,2926,2337,2364,2305,2525,2020,2065,1985,2373,2418,2019,1908,2160,1769,1643,1937,1469,1676,1848,1542,1847,1117,1204,1661,2179,1767,887,1151,869,1574,515,1347,388,715,1167,582,0,680,619,197,322,435,
3247,2978,3895,2661,2352,2237,2147,2251,2208,1979,1966,2077,2104,1833,2254,1862,2072,1560,1640,1605,1323,1432,1241,1392,1543,1022,1207,2801,1267,1241,806,730,1030,997,756,561,1367,530,116,680,0,77,606,472,556,
3309,3040,3885,2722,2387,2286,2198,2312,2224,2023,2002,2140,2168,1885,2252,1924,2074,1600,1701,1622,1387,1501,1300,1464,1526,1066,1278,2759,1341,1229,864,762,1106,966,833,540,1316,607,109,619,77,0,534,397,479,
3617,3353,3660,3033,2498,2498,2433,2627,2203,2205,2137,2468,2509,2138,2103,2253,1962,1779,2028,1641,1748,1904,1626,1890,1314,1309,1702,2347,1794,1078,1213,968,1583,711,1333,506,880,1128,533,197,606,534,0,156,239,
3582,3316,3774,2996,2521,2491,2418,2588,2262,2206,2151,2423,2460,2116,2195,2207,2044,1777,1982,1684,1688,1831,1577,1808,1415,1281,1620,2496,1702,1160,1151,943,1479,812,1218,522,1029,1001,417,322,472,397,156,0,154,
3725,3458,3899,3138,2675,2642,2568,2729,2412,2358,2305,2563,2598,2264,2334,2347,2187,1929,2122,1837,1823,1957,1716,1929,1548,1429,1741,2573,1814,1302,1286,1093,1584,944,1312,676,1109,1083,527,435,556,479,239,154,0};

static double position[MAXCHROM*2]={
24,1,23.8,2,5,1.5,22.8,4,21.5,1,18.8,5.2,19.5,6,22,5.8,13.3,5.8,17.8,6.8,16.8,6.8,22,7,22.2,7.1,
20,7.4,10.2,7.4,22,7.5,11.2,8,17,8.8,21,9,15,9,20.6,10,21.5,9.8,19.8,10.2,21.8,11,12,11,17.2,11.2,
21.5,11.4,7,11.2,22,11.6,13.2,11.5,18.8,12,16.8,13,22,13,13.2,13.2,21.2,14.4,15,14.6,11.5,15,
20,15.5,17,15.8,14.8,16,17.2,16.4,17.4,16,14.4,16.6,15.8,17,15.8,17.5};

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CChina45Dlg dialog

CChina45Dlg::CChina45Dlg(CWnd* pParent /*=NULL*/)
	: CDialog(CChina45Dlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CChina45Dlg)
	m_GALen = 45;
	m_nGroupSize = 100;
	m_GACrossProb = 0.6;
	m_GAVariProb = 0.03;
	m_GANum = 100;
	m_CurGANum = 0;
	m_MiniCost = 0.0;
	m_CrossNum = 0;
	m_VariNum = 0;
	m_GAFitness = 0.0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	
	m_bIsGA=false;

	for(int i=0;i<MAXCHROM;i++)
	{
		m_point[i].x=(int)(position[i*2]*9.25);
		m_point[i].y=(int)(250-position[i*2+1]*9.25);
	}
	
	//AfxMessageBox("成功");

	//m_recordset=new CChina45Recordset;

	//m_recordset.Move(1);

	  //以下代码专用于断点检查
  //char xn[20]; wsprintf(xn,"%d",(int)m_recordset.m_C12);
  //AfxMessageBox(xn);


	//m_distance=new double[MAXCHROM*MAXCHROM];

	// 计算城市之间距离
    //for(i=0;i<MAXCHROM;i++) for(int j=0;j<MAXCHROM;j++)   
	//{
		//int x1=m_point[i].x;
		//int y1=m_point[i].y;
		//int x2=m_point[j].x;
		//int y2=m_point[j].y;
		//m_distance[i*MAXCHROM+j]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    //}

}

void CChina45Dlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CChina45Dlg)
	DDX_Text(pDX, IDC_EDIT1, m_GALen);
	DDX_Text(pDX, IDC_EDIT2, m_nGroupSize);
	DDX_Text(pDX, IDC_EDIT3, m_GACrossProb);
	DDX_Text(pDX, IDC_EDIT4, m_GAVariProb);
	DDX_Text(pDX, IDC_EDIT5, m_GANum);
	DDX_Text(pDX, IDC_EDIT6, m_CurGANum);
	DDX_Text(pDX, IDC_EDIT7, m_MiniCost);
	DDX_Text(pDX, IDC_EDIT8, m_CrossNum);
	DDX_Text(pDX, IDC_EDIT9, m_VariNum);
	DDX_Text(pDX, IDC_EDIT10, m_GAFitness);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CChina45Dlg, CDialog)
	//{{AFX_MSG_MAP(CChina45Dlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_COMMAND(ID_MENU_GASET, OnMenuGaset)
	ON_COMMAND(ID_MENU_SOFT, OnMenuSoft)
	ON_COMMAND(ID_MENU_EXIT, OnMenuExit)
	ON_BN_CLICKED(IDC_BUTTON_GA, OnButtonGa)
	ON_COMMAND(ID_MENU_RESULT, OnMenuResult)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CChina45Dlg message handlers

BOOL CChina45Dlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CChina45Dlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CChina45Dlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		if(!m_bIsGA)
		{
	       CPen Pen;
	       CDC* pDC=GetDC();
		   CRect RectClient,Workarea;

           GetClientRect(RectClient);
           Workarea.left=RectClient.left+140;
           Workarea.bottom=RectClient.bottom-30;
		   Workarea.right=Workarea.left+290;
           Workarea.top=Workarea.bottom-270;
           pDC->Rectangle(Workarea);
           pDC->SetBkColor(0x00FFFFFF);

		   int px=Workarea.left;
			int py=Workarea.bottom+20;
			
		   pDC->SetTextColor(0x00F08080);
		   for(int i=0;i<MAXCHROM;i++)
		   {
			   CRect city;
			   city.left=px+m_point[i].x-2;
			   city.right=px+m_point[i].x+2;
			   city.top=py-m_point[i].y-2;
			   city.bottom=py-m_point[i].y+2;
			   pDC->Ellipse(city);
		   }
		
		}

		else DrawNetwork();