citymap.cpp

旅行商问题

                }
                m = k + l;
                n = j + m > size ? size - j :m;
                memcpy(gdest.index + j, ptemp, n * sizeof(int));
                if(n < m)
                {
                    memcpy(gdest.index, ptemp + n, (m - n) * sizeof(int));
                }
            }
            break;
        default:
            break;
        }
    }
}

// 辅助线程
UINT CCityMap::ThreadProc( LPVOID pParam )
{
    CCityMap * pClass = (CCityMap *)pParam;
    if(pClass->m_iCityNum <= 1)
    {
        return 0;
    }
    srand((UINT)time(NULL));
    pClass->m_bCompute = true;
    // 读取参数设置
    pClass->ReadSetting();
    static int i, j;
    static GENE tgene;
    static int bullet;
    static int totalBullet;
    static int maxCountdown = CM_JUMP_COUNTDOWN_INIT;
    // 分配空间
    int num = pClass->m_iCityNum;
    int * ptmp = new int[num];
    int commSize = CM_SEED_NUM * (1 + CM_CHILDREN_NUM);
    GENE * comm = new GENE[commSize];
    for(i = 0; i < commSize; i++)
    {
        comm[i].index = new int [num];
        comm[i].mark  = 0.0;
    }
    // 计算距离矩阵
    pClass->ComputeDistanceMatrix();
    // 生成初始群落
    CTime tstart = CTime::GetCurrentTime();
    CTime tnow;
    pClass->m_i64GenNum = 1;
    pClass->m_iJumpCount = 0;
    memcpy(comm[0].index, pClass->m_piBestIndex, sizeof(int) * num);
    pClass->Mark(comm[0]);
    pClass->QuadrangleOptimise(comm[0]);
    pClass->m_dBestMark = comm[0].mark;
    pClass->m_i64BestGen = pClass->m_i64GenNum;
    double maxMark = comm[0].mark;
    int maxIndex = 0;
    double totalMark = maxMark;
    pClass->m_iJumpCountdown = CM_JUMP_COUNTDOWN_INIT;
    for(i = 1; i < CM_SEED_NUM; i++)
    {
        Variant(comm[0], comm[i], ptmp, num, pClass->m_iJumpCountdown);
        pClass->Mark(comm[i]);
        totalMark += comm[i].mark;
        if(maxMark < comm[i].mark)
        {
            maxMark = comm[i].mark;
            maxIndex = i;
        }
    }
    // 移动最优基因
    if(maxIndex != 0)
    {
        tgene.index = comm[0].index;
        tgene.mark = comm[0].mark;
        comm[0].index = comm[maxIndex].index;
        comm[0].mark = comm[maxIndex].mark;
        comm[maxIndex].index = tgene.index;
        comm[maxIndex].mark = tgene.mark;
        maxIndex = 0;
        pClass->QuadrangleOptimise(comm[0]);
        maxMark = comm[0].mark;
        memcpy(pClass->m_piCurrBestIndex, pClass->m_piBestIndex, sizeof(int) * num);
        memcpy(pClass->m_piBestIndex, pClass->m_piCurrBestIndex, sizeof(int) * num);
        pClass->m_dBestMark = maxMark;
        pClass->m_i64BestGen = pClass->m_i64GenNum;
    }
    int indNum = CM_SEED_NUM;
    pClass->m_dAVGMark = (totalMark) / indNum;
    pClass->m_pMaxTrendLine->Clear();
    pClass->m_pAVGTrendLine->Clear();
    pClass->m_pMaxTrendLine->AddValue(maxMark);
    pClass->m_pAVGTrendLine->AddValue(pClass->m_dAVGMark);
    // 开始进化
    while(!pClass->m_bKillMsg)
    {
        totalMark = 0.0;
        // 变异
        for(i = 0; i < CM_SEED_NUM; i++)
        {
            totalMark += comm[i].mark;
            for(j = 0; j < CM_CHILDREN_NUM; j++)
            {
                Variant(comm[i], comm[indNum], ptmp, num, 1);
                pClass->Mark(comm[indNum]);
                totalMark += comm[indNum].mark;
                if(maxMark < comm[indNum].mark)
                {
                    maxMark = comm[indNum].mark;
                    maxIndex = indNum;
                }
                indNum++;
            }
        }
        pClass->m_dAVGMark = (totalMark) / indNum;
        pClass->m_pAVGTrendLine->AddValue(pClass->m_dAVGMark);
        pClass->m_pMaxTrendLine->AddValue(maxMark);
        // 移动最优基因
        if(maxIndex != 0)
        {
            tgene.index = comm[0].index;
            tgene.mark = comm[0].mark;
            comm[0].index = comm[maxIndex].index;
            comm[0].mark = comm[maxIndex].mark;
            comm[maxIndex].index = tgene.index;
            comm[maxIndex].mark = tgene.mark;
            maxIndex = 0;
            memcpy(pClass->m_piCurrBestIndex, comm[0].index, sizeof(int) * num);
            if(maxMark > pClass->m_dBestMark)
            {
                memcpy(pClass->m_piBestIndex, pClass->m_piCurrBestIndex, sizeof(int) * num);
                pClass->m_dBestMark = maxMark;
                pClass->m_i64BestGen = pClass->m_i64GenNum;
            }
            int forcastCountdown = int((maxCountdown - pClass->m_iJumpCountdown) * CM_JUMP_COUNTDOWN_INC);
            if(forcastCountdown > maxCountdown)
            {
                maxCountdown = forcastCountdown;
            }
            pClass->m_iJumpCountdown = maxCountdown;
        }
        else
        {
            pClass->m_iJumpCountdown--;
            if(pClass->m_iJumpCountdown <= 0)
            {
                pClass->QuadrangleOptimise(comm[0]);
                if(maxMark < comm[0].mark)
                {
                    pClass->m_iJumpCountdown = maxCountdown;
                    maxMark = comm[0].mark;
                    memcpy(pClass->m_piCurrBestIndex, comm[0].index, sizeof(int) * num);
                    if(maxMark > pClass->m_dBestMark)
                    {
                        memcpy(pClass->m_piBestIndex, pClass->m_piCurrBestIndex, sizeof(int) * num);
                        pClass->m_dBestMark = maxMark;
                        pClass->m_i64BestGen = pClass->m_i64GenNum;
                    }
                }
                else
                {
                    if(CM_IMG_LOG)
                    {
                        // 保存当前屏幕图像为文件,作为日志
                        pClass->m_iJumpCountdown = maxCountdown;
                        static CString fileName;
                        fileName.Format("%03d.bmp", pClass->m_iJumpCount);
                        pClass->SaveAsImage(fileName);
                    }
                    srand((UINT)time(NULL));
                    maxCountdown = CM_JUMP_COUNTDOWN_INIT;
                    pClass->m_iJumpCountdown = maxCountdown;
                    // 已经陷入局部最优，灾变
                    pClass->m_iJumpCount++;
                    Variant(comm[0], comm[0], ptmp, num, 20);
                    pClass->Mark(comm[0]);
                    maxMark = comm[0].mark;
                    for(i = 1; i < CM_SEED_NUM; i++)
                    {
                        Variant(comm[0], comm[i], ptmp, num, 20);
                        pClass->Mark(comm[i]);
                        totalMark += comm[i].mark;
                        if(maxMark < comm[i].mark)
                        {
                            maxMark = comm[i].mark;
                            maxIndex = i;
                        }
                    }
                    // 移动最优基因
                    if(maxIndex != 0)
                    {
                        tgene.index = comm[0].index;
                        tgene.mark = comm[0].mark;
                        comm[0].index = comm[maxIndex].index;
                        comm[0].mark = comm[maxIndex].mark;
                        comm[maxIndex].index = tgene.index;
                        comm[maxIndex].mark = tgene.mark;
                        maxIndex = 0;
                    }
                    indNum = CM_SEED_NUM;
                }
            }
        }
        // 轮盘赌
        totalMark -= comm[0].mark;
        totalBullet = 0;
        for(i = 1; i < indNum; i++)
        {
            comm[i].killRate = int(10000.0 * comm[i].mark / totalMark);
            totalBullet += comm[i].killRate;
        }
        while(indNum > CM_SEED_NUM)
        {
            bullet = rand() % totalBullet;
            for(i = 1; i < indNum; i++)
            {
                if(bullet <= comm[i].killRate)
                {
                    // 命中
                    totalBullet -= comm[i].killRate;
                    tgene.index = comm[indNum - 1].index;
                    tgene.mark = comm[indNum - 1].mark;
                    tgene.killRate = comm[indNum - 1].killRate;
                    comm[indNum - 1].index = comm[i].index;
                    comm[indNum - 1].mark = comm[i].mark;
                    comm[indNum - 1].killRate = comm[i].killRate;
                    comm[i].index = tgene.index;
                    comm[i].mark = tgene.mark;
                    comm[i].killRate = tgene.killRate;
                    indNum--;
                    break;
                }
                else
                {
                    bullet -= comm[i].killRate;
                }
            }
        }
        pClass->m_i64GenNum++;
        tnow = CTime::GetCurrentTime();
        pClass->m_tsTimeUsed = tnow - tstart;
    }
    // 释放空间
    for(i = 0; i < commSize; i++)
    {
        delete [] comm[i].index;
        comm[i].index = NULL;
    }
    delete [] comm;
    comm = NULL;

    // 销毁距离矩阵
    pClass->DestroyDistanceMatrix();

    tgene.index = NULL;
    pClass->m_bCompute = false;

    // 保存参数设置
    pClass->SaveSetting();

    return 0;   // thread completed successfully
}

// 销毁距离矩阵
void CCityMap::DestroyDistanceMatrix()
{
    if(this->m_ppdDistanceM)
    {
        for(int i = 1; i < this->m_iDMSize; i++)
        {
            delete [] this->m_ppdDistanceM[i];
            this->m_ppdDistanceM[i] = NULL;
        }
        delete [] this->m_ppdDistanceM;
        this->m_ppdDistanceM = NULL;
    }
}

// 计算距离矩阵
void CCityMap::ComputeDistanceMatrix()
{
    int i, j;
    this->DestroyDistanceMatrix();
    // 创建存储空间
    this->m_iDMSize = this->m_iCityNum;
    this->m_ppdDistanceM = new double * [m_iDMSize];
    m_ppdDistanceM[0] = NULL;
    for(i = 1; i < this->m_iDMSize; i++)
    {
        this->m_ppdDistanceM[i] = new double[i];
    }
    // 计算距离
    for(i = 1; i < m_iDMSize; i++)
    {
        for(j = 0; j < i; j++)
        {
            m_ppdDistanceM[i][j] = m_pDPCitySites[i].Distance(this->m_pDPCitySites[j]);
        }
    }
}

// 打分
void CCityMap::Mark(GENE & gene)
{
    static int i;
    gene.mark = this->m_pDPCitySites[gene.index[0]].Distance(this->m_pDPCitySites[gene.index[m_iCityNum - 1]]);
    for(i = 1; i < this->m_iCityNum; i++)
    {
        // gene.mark += this->m_pDPCitySites[gene.index[i]].Distance(this->m_pDPCitySites[gene.index[i - 1]]);
        if(gene.index[i] > gene.index[i - 1])
        {
            gene.mark += m_ppdDistanceM[gene.index[i]][gene.index[i - 1]];
        }
        else
        {
            gene.mark += m_ppdDistanceM[gene.index[i - 1]][gene.index[i]];
        }
    }
    if(gene.mark < 0.00001)
    {
        gene.mark = 100000.0;
    }
    else
    {
        gene.mark = 1.0 / gene.mark;
    }
}

// 四边形优化
void CCityMap::QuadrangleOptimise(GENE & gene)
{
    if(this->m_iCityNum < 3)
    {