citymap.cpp

旅行商问题

#include "StdAfx.h"
#include ".\citymap.h"

CCityMap::CCityMap(void)
    : m_pDPCitySites(NULL)
    , m_iRoomSize(0)
    , m_iCityNum(0)
    , m_bCompute(false)
    , m_bKillMsg(false)
    , m_ppdDistanceM(NULL)
    , m_iDMSize(0)
    , m_piBestIndex(NULL)
    , m_piCurrBestIndex(NULL)
    , m_i64GenNum(1)
    , m_i64BestGen(1)
    , m_dBestMark(1.0)
    , m_iJumpCountdown(CM_JUMP_COUNTDOWN_INIT)
    , m_iJumpCount(0)
    , m_dAVGMark(1.0)
    , m_pAVGTrendLine(NULL)
    , m_pMaxTrendLine(NULL)
    , m_tsTimeUsed(0)
{
    // 取得程序路径
    this->m_sProPath = "";
    char fileName[1024];
    ::GetModuleFileName(GetModuleHandle(NULL), fileName, 1024);
    for(size_t i = strlen(fileName); i > 0; i--)
    {
        if(fileName[i] == '.')
        {
            fileName[i] = 0;
        }
        if(fileName[i] == '\\')
        {
            fileName[i + 1] = 0;
            m_sProPath = fileName;
            break;
        }
    }
    ReadSetting();
}

CCityMap::~CCityMap(void)
{
    if(this->m_pDPCitySites)
    {
        delete [] m_pDPCitySites;
        m_pDPCitySites = NULL;
    }
    if(this->m_piBestIndex)
    {
        delete [] m_piBestIndex;
        m_piBestIndex = NULL;
    }
    if(this->m_piCurrBestIndex)
    {
        delete [] m_piCurrBestIndex;
        m_piCurrBestIndex = NULL;
    }
    this->m_iCityNum = 0;
    this->m_iRoomSize = 0;
}


// 全局参数
// 种子数量
int CCityMap::CM_SEED_NUM = 12;
// 子女数量
int CCityMap::CM_CHILDREN_NUM = 36;
// 最大转移数
int CCityMap::CM_MAX_TRANS_NUM = 10;
// 灾变初始值
int CCityMap::CM_JUMP_COUNTDOWN_INIT = 800;
// 灾变倍增值
double CCityMap::CM_JUMP_COUNTDOWN_INC = 3.6;
// 图片日志
bool CCityMap::CM_IMG_LOG = true;

// 读取参数设置
void CCityMap::ReadSetting()
{
    FILE * fp = fopen(this->m_sProPath + "setting.cfg", "r");
    if(fp)
    {
        char buffer[1024];
        size_t read;
        CString s = "";
        while(!feof(fp))
        {
            read = fread(buffer, 1, 1023, fp);
            buffer[read] = 0;
            s += buffer;
        }

        s += "\n";
        int start, end;
        int len = s.GetLength();
        CString t;
        start = s.Find("种子数量");
        if(start >= 0)
        {
            start = s.Find("=", start);
            end = s.Find("\n", start);
            if(end > start + 1)
            {
                t = s.Mid(start + 1, end - start - 1).Trim(" ");
                sscanf(t, "%d", &this->CM_SEED_NUM);
            }
        }
        start = s.Find("子女数量");
        if(start >= 0)
        {
            start = s.Find("=", start);
            end = s.Find("\n", start);
            if(end > start + 1)
            {
                t = s.Mid(start + 1, end - start - 1).Trim(" ");
                sscanf(t, "%d", &this->CM_CHILDREN_NUM);
            }
        }
        start = s.Find("最大转移数");
        if(start >= 0)
        {
            start = s.Find("=", start);
            end = s.Find("\n", start);
            if(end > start + 1)
            {
                t = s.Mid(start + 1, end - start - 1).Trim(" ");
                sscanf(t, "%d", &this->CM_MAX_TRANS_NUM);
            }
        }
        start = s.Find("灾变初始值");
        if(start >= 0)
        {
            start = s.Find("=", start);
            end = s.Find("\n", start);
            if(end > start + 1)
            {
                t = s.Mid(start + 1, end - start - 1).Trim(" ");
                sscanf(t, "%d", &this->CM_JUMP_COUNTDOWN_INIT);
            }
        }
        start = s.Find("灾变倍增值");
        if(start >= 0)
        {
            start = s.Find("=", start);
            end = s.Find("\n", start);
            if(end > start + 1)
            {
                t = s.Mid(start + 1, end - start - 1).Trim(" ");
                sscanf(t, "%lf", &this->CM_JUMP_COUNTDOWN_INC);
            }
        }
        start = s.Find("图片日志");
        if(start >= 0)
        {
            start = s.Find("=", start);
            end = s.Find("\n", start);
            if(end > start + 1)
            {
                t = s.Mid(start + 1, end - start - 1).Trim(" ");
                this->CM_IMG_LOG = (t.MakeUpper() == "TRUE");
            }
        }

        fclose(fp);
    }
}

// 保存参数设置
void CCityMap::SaveSetting()
{
    FILE * fp = fopen(this->m_sProPath + "setting.cfg", "w");
    if(fp)
    {
        fprintf(fp, "种子数量 = %d\n", this->CM_SEED_NUM);
        fprintf(fp, "子女数量 = %d\n", this->CM_CHILDREN_NUM);
        fprintf(fp, "最大转移数 = %d\n", this->CM_MAX_TRANS_NUM);
        fprintf(fp, "灾变初始值 = %d\n", this->CM_JUMP_COUNTDOWN_INIT);
        fprintf(fp, "灾变倍增值 = %lf\n", this->CM_JUMP_COUNTDOWN_INC);
        fprintf(fp, "图片日志 = %s\n", this->CM_IMG_LOG ? "TRUE" : "FALSE");

        fclose(fp);
    }
}

// 保存为图像文件
void CCityMap::SaveAsImage(CString fileName)
{
	CDC dc;
	if(!dc.Attach(::GetWindowDC(NULL)))
	{
		return;
	}

    CRect rect(0, 0, 880, 660);
    CDC tdc;
    CBitmap tbmp;
    tdc.CreateCompatibleDC(&dc);
    tbmp.CreateCompatibleBitmap(&dc, rect.Width(), rect.Height());
    tdc.SelectObject(&tbmp);
    
    CFont font;
    VERIFY(font.CreateFont(
        12,                        // nHeight
        0,                         // nWidth
        0,                         // nEscapement
        0,                         // nOrientation
        FW_NORMAL,                 // nWeight
        FALSE,                     // bItalic
        FALSE,                     // bUnderline
        0,                         // cStrikeOut
        ANSI_CHARSET,              // nCharSet
        OUT_DEFAULT_PRECIS,        // nOutPrecision
        CLIP_DEFAULT_PRECIS,       // nClipPrecision
        DEFAULT_QUALITY,           // nQuality
        DEFAULT_PITCH | FF_SWISS,  // nPitchAndFamily
        "宋体"));                 // lpszFacename

    CFont* def_font = tdc.SelectObject(&font);

    tdc.FillSolidRect(0, 0, rect.Width(), rect.Height(), RGB(255, 255, 255));
    rect.bottom -= 20;
    this->Draw(&tdc, rect, -1, -1);

    tdc.FillSolidRect(0, rect.bottom, rect.Width(), 20, RGB(255, 255, 255));
    tdc.MoveTo(0, rect.bottom + 1);
    tdc.LineTo(rect.Width(), rect.bottom + 1);
    tdc.TextOut(10, rect.bottom + 5, this->GetStateDescription());

    rect.bottom += 20;
    {
        CString prefixion = "路径";
        CImage img;
        img.Attach(HBITMAP(tbmp));
        img.Save(prefixion + fileName);
    }

    rect = CRect(0, 0, 880, 660);
    tdc.FillSolidRect(&rect, RGB(255, 255, 255));
    tdc.SetTextColor(RGB(0, 0, 0));
    static CPen penFleetAVG(PS_SOLID, 1, RGB(200, 200, 200));
    static CPen penDeepAVG(PS_SOLID, 1, RGB(0, 0, 0));
    this->m_pAVGTrendLine->Draw(&tdc, rect, penFleetAVG, penDeepAVG, true);
    {
        CString prefixion = "平均分";
        CImage img;
        img.Attach(HBITMAP(tbmp));
        img.Save(prefixion + fileName);
    }

    tdc.FillSolidRect(&rect, RGB(255, 255, 255));
    tdc.SetTextColor(RGB(0, 0, 255));
    static CPen penFleetMax(PS_SOLID, 1, RGB(200, 200, 255));
    static CPen penDeepMax(PS_SOLID, 1, RGB(0, 0, 255));
    this->m_pMaxTrendLine->Draw(&tdc, rect, penFleetMax, penDeepMax, false);
    {
        CString prefixion = "最优分";
        CImage img;
        img.Attach(HBITMAP(tbmp));
        img.Save(prefixion + fileName);
    }

    tdc.SelectObject(def_font);

}


// 变异函数
void CCityMap::Variant(GENE & gsource, GENE & gdest, int * ptemp, int size, int varate)
{
    static int i;
    static int j, k, l, n, m;
    static int tmp;
    memcpy(gdest.index, gsource.index, sizeof(int) * size);
    for(i = 0; i < varate; i++)
    {
        switch(rand() % 2)
        {
        case 0:
            // 逆序变异
            {
                j = rand() % size;
                k = rand() % size;
                if(j == k)
                {
                    k = (k + 1) % size;
                }
                if(j > k)
                {
                    k += size;
                    for(l = j; l < j + k - l; l++)
                    {
                        n = (j + k - l) % size;
                        m = l % size;
                        tmp = gdest.index[m];
                        gdest.index[m] = gdest.index[n];
                        gdest.index[n] = tmp;
                    }
                }
                else
                {
                    for(l = j; l < j + k - l; l++)
                    {
                        tmp = gdest.index[l];
                        gdest.index[l] = gdest.index[j + k - l];
                        gdest.index[j + k - l] = tmp;
                    }
                }
            }
            break;
        case 1:
            // 转移变异
            {
                j = rand() % size;
                k = rand() % CM_MAX_TRANS_NUM;
                if(k == 0)
                {
                    k = 1;
                }
                l = rand() % (size - k) + 1;
                n = (j + k) % size + l > size ? size - (j + k) % size : l;
                memcpy(ptemp, gdest.index + (j + k) % size, n * sizeof(int));
                if(n < l)
                {
                    memcpy(ptemp + n, gdest.index, (l - n) * sizeof(int));
                }
                n = j + k > size ? size - j : k;
                memcpy(ptemp + l, gdest.index + j, n * sizeof(int));
                if(n < k)
                {
                    memcpy(ptemp + l + n, gdest.index, (k - n) * sizeof(int));