游戏编程中的人工智能技术-遗传算法实现寻路

标签: 游戏开发  人工智能  算法  AI

前言

学习游戏中的AI,《游戏编程中的人工智能技术》一书可作为参考学习
在阅读本文章前,强烈建议先看附录中的一些术语,并自行查阅相关资料了解
这里我把附录提前

附录

在进行学习以下内容之前,先了解一些专业术语:
生物知识

  • 染色体 Chromosome
  • 基因 gene
  • 等位基因 allele
  • 基因座位 locus
  • 基因组 genome
  • 遗传类型 genotype
  • 表现型 phentype
  • 重组 recombination
  • 杂交 crossover
  • 突变(变异) mutation

遗传算法中的一些英文

  • 赌轮选择法 roulette wheel selection
  • 世代 generation
  • 时代 epoch
  • 变异率 mutation rate
  • 杂交率 crossover rate

效果预览

这里写图片描述

实现

  1. defines.h 定义本GA算法演示要用到的一些常量
#ifndef DEFINES_H
#define DEFINES_H
#define WINDOW_WIDTH 450
#define WINDOW_HEIGHT 300

#define MAP_WIDTH 15
#define MAP_HEIGHT 10

#define CROSSOVER_RATE 0.7
#define MUTATION_RATE 0.001

#define POP_SIZE 140
#define CHROMO_LENGTH 70
#define GENE_LENGTH 2

#endif

分析

CROSSOVER_RATE 杂交率
MUTATION_RATE 变异率
POP_SIZE 初始人口数量
CHROMO_LENGTH 染色体长度
GENE_LENGTH 基因长度

2. utils.h 工具类
#ifndef UTILS_H
#define UTILS_H

#include <stdlib.h>
#include <math.h>
#include <sstream>
#include <string>

using namespace std;

//-----------------------------------------------------------------------
//  一些随机数函数
//-----------------------------------------------------------------------
inline int    RandInt(int x, int y) { return rand() % (y - x + 1) + x; }
inline double RandFloat() { return (rand()) / (RAND_MAX + 1.0); }
inline bool   RandBool()
{
    if (RandInt(0, 1)) return true;
    else return false;
}
//返回一个随机数范围是 -1 < n < 1
inline double RandomClamped() { return RandFloat() - RandFloat(); }
//-----------------------------------------------------------------------
// 有用的字符串函数
//-----------------------------------------------------------------------
//整型转为字符串函数
string itos(int arg);
#endif

分析

上面的代码是一些工具类函数的定义
randInt 返回的整型范围为 x < = n < = x+y
randFloat 返回的浮点型范围是 0 <= n <1

3. utils.cpp 工具类实现
#include "utils.h"

//--------------------------itos------------------------------------
//  整型转为字符串
//------------------------------------------------------------------        
string itos(int arg)
{
    ostringstream buffer;
    buffer << arg;
    return buffer.str();
}
4. CBobMap.h 地图类
#ifndef CBOBMAP_H
#define CBOBMAP_H
///////////////////////////////////////////////////////////////////////
//Bob地图类
///////////////////////////////////////////////////////////////////////
#include "stdlib.h"
#include "windows.h"
#include <vector>

#include "defines.h"

using namespace std;
class CBobMap
{
private:
    //存储地图
    static const int    map[MAP_HEIGHT][MAP_WIDTH];
    //地图的宽高
    static const int    m_iMapWidth;
    static const int    m_iMapHeight;
    //起始点在数组中的坐标
    static const int    m_iStartX;
    static const int    m_iStartY;
    //终点的数组下标
    static const int    m_iEndX;
    static const int    m_iEndY;
public:
    //如果需要,可以利用这一数组作为Bob走过的路程的存储器
    int memory[MAP_HEIGHT][MAP_WIDTH];
    CBobMap()
    {
        ResetMemory();
    }
    //利用一个字符串来记录Bob行进的方向,其中每一个字符串代表Bob所走的一步
    //检查Bob离开出口还有多远,返回一个到达出口距离成正比的适应性分数
    double TestRoute(const vector<int> &vecPath, CBobMap &memory);

    //Render函数利用GDI在一个给定的作图表面上显示地图
    void Render(const int cxClient, const int cyClient, HDC surface);
    //画出能够存放与存储器中的任意路径
    void MemoryRender(const int cxClient, const int cyClient, HDC surface);
    void ResetMemory();
};

#endif
5. CBobMap.cpp 地图类实现
#include "CBobMap.h"
//地图数据
const int CBobMap::map[MAP_HEIGHT][MAP_WIDTH] =
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1,
8, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1,
1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1,
1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1,
1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1,
1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1,
1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 5,
1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };


const int CBobMap::m_iMapHeight = MAP_HEIGHT;
const int CBobMap::m_iMapWidth = MAP_WIDTH;

//右下角为0,0

const int CBobMap::m_iStartX = 14;
const int CBobMap::m_iStartY = 7;

const int CBobMap::m_iEndX = 0;
const int CBobMap::m_iEndY = 2;


//-------------------------------Render -----------------------------

void CBobMap::Render(const int cxClient,
    const int cyClient,
    HDC surface)
{
    const int border = 20;

    int BlockSizeX = (cxClient - 2 * border) / m_iMapWidth;
    int BlockSizeY = (cyClient - 2 * border) / m_iMapHeight;

    HBRUSH  BlackBrush, RedBrush, OldBrush;
    HPEN    NullPen, OldPen;

    NullPen = (HPEN)GetStockObject(NULL_PEN);
    BlackBrush = (HBRUSH)GetStockObject(BLACK_BRUSH);

    RedBrush = CreateSolidBrush(RGB(255, 0, 0));

    OldBrush = (HBRUSH)SelectObject(surface, BlackBrush);
    OldPen = (HPEN)SelectObject(surface, NullPen);

    for (int y = 0; y<m_iMapHeight; ++y)
    {
        for (int x = 0; x<m_iMapWidth; ++x)
        {
            //计算出每个格子的边角坐标
            int left = border + (BlockSizeX * x);
            int right = left + BlockSizeX;

            int top = border + (BlockSizeY * y);
            int bottom = top + BlockSizeY;

            //如果是墙,画黑矩形
            if (map[y][x] == 1)
            {
                SelectObject(surface, BlackBrush);
                Rectangle(surface, left, top, right, bottom);
            }

            //如果是出入口,画红矩形
            if ((map[y][x] == 5) || (map[y][x] == 8))
            {
                SelectObject(surface, RedBrush);
                Rectangle(surface, left, top, right, bottom);
            }
        }
    }

    SelectObject(surface, OldBrush);
    SelectObject(surface, OldPen);
}

//-------------------------------MemoryRender ------------------------

void CBobMap::MemoryRender(const int cxClient,
    const int cyClient,
    HDC surface)
{
    const int border = 20;

    int BlockSizeX = (cxClient - 2 * border) / m_iMapWidth;
    int BlockSizeY = (cyClient - 2 * border) / m_iMapHeight;

    HBRUSH  GreyBrush, OldBrush;
    HPEN    NullPen, OldPen;

    GreyBrush = (HBRUSH)GetStockObject(LTGRAY_BRUSH);

    NullPen = (HPEN)GetStockObject(NULL_PEN);

    OldBrush = (HBRUSH)SelectObject(surface, GreyBrush);
    OldPen = (HPEN)SelectObject(surface, NullPen);

    for (int y = 0; y<m_iMapHeight; ++y)
    {
        for (int x = 0; x<m_iMapWidth; ++x)
        {
            int left = border + (BlockSizeX * x);
            int right = left + BlockSizeX;

            int top = border + (BlockSizeY * y);
            int bottom = top + BlockSizeY;

            //绘制灰色矩形
            if (memory[y][x] == 1)
            {
                Rectangle(surface, left, top, right, bottom);
            }
        }
    }

    SelectObject(surface, OldBrush);

    SelectObject(surface, OldPen);

}

//---------------------------- TestRoute ---------------------------
//根据距离返回适应性分数
//-------------------------------------------------------------------
double CBobMap::TestRoute(const vector<int> &vecPath, CBobMap &Bobs)
{
    int posX = m_iStartX;
    int posY = m_iStartY;

    for (int dir = 0; dir<vecPath.size(); ++dir)
    {
        int NextDir = vecPath[dir];

        switch (vecPath[dir])
        {
        case 0: //North

                //检查边界
            if (((posY - 1) < 0) || (map[posY - 1][posX] == 1))
            {
                break;
            }

            else
            {
                posY -= 1;
            }

            break;

        case 1: //South

            if (((posY + 1) >= m_iMapHeight) || (map[posY + 1][posX] == 1))
            {
                break;
            }

            else
            {
                posY += 1;
            }

            break;

        case 2: //East

            if (((posX + 1) >= m_iMapWidth) || (map[posY][posX + 1] == 1))
            {
                break;
            }

            else
            {
                posX += 1;
            }

            break;

        case 3: //West

            if (((posX - 1) < 0) || (map[posY][posX - 1] == 1))
            {
                break;
            }

            else
            {
                posX -= 1;
            }

            break;

        }//end switch

         //将这个路径设为1
        Bobs.memory[posY][posX] = 1;

    }//next direction

    //计算距离
    int DiffX = abs(posX - m_iEndX);
    int DiffY = abs(posY - m_iEndY);

    //返回适应性分数
    return 1 / (double)(DiffX + DiffY + 1);
}

//--------------------- ResetMemory --------------------------
//------------------------------------------------------------
void CBobMap::ResetMemory()
{
    for (int y = 0; y<m_iMapHeight; ++y)
    {
        for (int x = 0; x<m_iMapWidth; ++x)
        {
            memory[y][x] = 0;
        }
    }
}
6. CgaBob.h 遗传算法类
#ifndef CGABOB_H
#define CGABOB_H

/////////////////////////////////////////////////////////////////////////
//SGenome基因结构和遗传算法类
/////////////////////////////////////////////////////////////////////////

#include <vector>
#include <sstream>

#include "defines.h"
#include "CBobMap.h"
#include "utils.h"

using namespace std;

struct SGenome
{
    vector<int> vecBits;
    double      dFitness;

    SGenome() :dFitness(0) {}

    SGenome(const int num_bits) :dFitness(0)
    {
        //创造随机二进制位串
        for (int i = 0; i<num_bits; ++i)
        {
            vecBits.push_back(RandInt(0, 1));
        }
    }
};

//--------------------------------------------------------------
//  定义遗传算法类
//---------------------------------------------------------------
class CgaBob
{
private:

    //基因组群体
    vector<SGenome> m_vecGenomes;

    //群体大小
    int             m_iPopSize;
    double          m_dCrossoverRate;
    double          m_dMutationRate;

    //每个染色体有多少bits
    int             m_iChromoLength;

    //每个基因有多少bits
    int             m_iGeneLength;

    int             m_iFittestGenome;

    double          m_dBestFitnessScore;

    double          m_dTotalFitnessScore;

    int             m_iGeneration;

    //为map类创建一个实例
    CBobMap        m_BobsMap;

    //另一个CBobMap对象,用来保存每一代的最佳路径的一个记录
    //这是被访问小格的一个数组,它仅为了显示目的而使用
    CBobMap     m_BobsBrain;

    //检测运行是否仍在进行中
    bool            m_bBusy;

    void        Mutate(vector<int> &vecBits);

    void        Crossover(const vector<int> &mum,
        const vector<int> &dad,
        vector<int>       &baby1,
        vector<int>       &baby2);

    SGenome&        RouletteWheelSelection();

    //用新的适应性分数来更新基因组原有的适应性分数
    //并计算群体的最高适应性分数和适应性分数最高的那个成员
    void              UpdateFitnessScores();

    //把一个位向量译成为一个方向的(整数)向量
    vector<int> Decode(const vector<int> &bits);

    //把一个位向量译成为十进制数。用于译码
    int               BinToInt(const vector<int> &v);

    //创建一个随机的二进制位串的初始群体
    void              CreateStartPopulation();

public:

    CgaBob(double cross_rat,
        double mut_rat,
        int    pop_size,
        int    num_bits,
        int    gene_len) :m_dCrossoverRate(cross_rat),
        m_dMutationRate(mut_rat),
        m_iPopSize(pop_size),
        m_iChromoLength(num_bits),
        m_dTotalFitnessScore(0.0),
        m_iGeneration(0),
        m_iGeneLength(gene_len),
        m_bBusy(false)

    {
        CreateStartPopulation();
    }

    void            Run(HWND hwnd);

    void            Render(int cxClient, int cyClient, HDC surface);

    void            Epoch();

    //访问用的方法
    int             Generation() { return m_iGeneration; }
    int             GetFittest() { return m_iFittestGenome; }
    bool      Started() { return m_bBusy; }
    void            Stop() { m_bBusy = false; }
};
#endif
7. CgaBob.cpp 遗传算法实现
#include "CgaBob.h"

//--------------------------RouletteWheelSelection-----------------
//  赌轮选择法
//------------------------------------------------------------------
SGenome& CgaBob::RouletteWheelSelection()
{
    double fSlice = RandFloat() * m_dTotalFitnessScore;

    double cfTotal = 0.0;

    int SelectedGenome = 0;

    for (int i = 0; i<m_iPopSize; ++i)
    {

        cfTotal += m_vecGenomes[i].dFitness;

        if (cfTotal > fSlice)
        {
            SelectedGenome = i;
            break;
        }
    }

    return m_vecGenomes[SelectedGenome];
}

//----------------------------Mutate---------------------------------
//沿着一个染色体的长度,一位一位地进行考察,并按m_MutationRate给定的
//几率,将其中某些位进行翻转
//--------------------------------------------------------------------
void CgaBob::Mutate(vector<int> &vecBits)
{
    for (int curBit = 0; curBit<vecBits.size(); curBit++)
    {
        //是否需要翻转此位
        if (RandFloat() < m_dMutationRate)
        {
            //是,翻转此位
            vecBits[curBit] = !vecBits[curBit];
        }
    }//下一位
}

//----------------------------Crossover--------------------------------
//杂交算子
//两个染色体在同一随机位置上断裂开来,然后将它们在
//断开点以后的部分进行互换,以形成两个新的染色体(子代)
//---------------------------------------------------------------------
void CgaBob::Crossover(const vector<int> &mum,
    const vector<int> &dad,
    vector<int>       &baby1,
    vector<int>       &baby2)
{
    //确定是否需要杂交
    //不需要杂交的情况
    //大于杂交率不进行杂交
    //父母让色体相同
    if ((RandFloat() > m_dCrossoverRate) || (mum == dad))
    {
        baby1 = mum;
        baby2 = dad;

        return;
    }

    //确定一个杂交点
    int cp = RandInt(0, m_iChromoLength - 1);

    //交换位
    for (int i = 0; i<cp; ++i)
    {
        baby1.push_back(mum[i]);
        baby2.push_back(dad[i]);
    }

    for (int i = cp; i<mum.size(); ++i)
    {
        baby1.push_back(dad[i]);
        baby2.push_back(mum[i]);
    }
}
//-----------------------------------Run----------------------------------
//------------------------------------------------------------------------
void CgaBob::Run(HWND hwnd)
{
    //创建一个随机的基因群体
    CreateStartPopulation();

    m_bBusy = true;

}
//----------------------CreateStartPopulation---------------------------
//
//-----------------------------------------------------------------------
void CgaBob::CreateStartPopulation()
{
    //清理存在的群体
    m_vecGenomes.clear();

    for (int i = 0; i<m_iPopSize; i++)
    {
        m_vecGenomes.push_back(SGenome(m_iChromoLength));
    }

    //重置所有变量
    m_iGeneration = 0;
    m_iFittestGenome = 0;
    m_dBestFitnessScore = 0;
    m_dTotalFitnessScore = 0;
}
//--------------------------------Epoch---------------------------------
//时代方法
//遗传算法的循环,它是这个类中执行工作的部门,
//这以方法与所有工作或多或少都联系在一起
//----------------------------------------------------------------------
void CgaBob::Epoch()
{

    UpdateFitnessScores();

    //创建一个新的群体
    int NewBabies = 0;

    //创建婴儿的存储
    vector<SGenome> vecBabyGenomes;

    while (NewBabies < m_iPopSize)
    {
        //赌轮选取两个上辈
        SGenome mum = RouletteWheelSelection();
        SGenome dad = RouletteWheelSelection();

        //杂交操作
        SGenome baby1, baby2;
        Crossover(mum.vecBits, dad.vecBits, baby1.vecBits, baby2.vecBits);

        //变异操作
        Mutate(baby1.vecBits);
        Mutate(baby2.vecBits);

        //加入新群体
        vecBabyGenomes.push_back(baby1);
        vecBabyGenomes.push_back(baby2);

        NewBabies += 2;
    }

    //所有婴儿负值到初始群体
    m_vecGenomes = vecBabyGenomes;

    //代的数量加1
    ++m_iGeneration;
}

//---------------------------UpdateFitnessScores------------------------
//  用新的适应度得分更新基因组适应度,并计算群体的最高适应度和最适成员。
//  如果找到一个解决方案(在这个例子中健身=1),
//  则通过设置m_bBusy为false来停止运行。
//-----------------------------------------------------------------------
void CgaBob::UpdateFitnessScores()
{
    m_iFittestGenome = 0;
    m_dBestFitnessScore = 0;
    m_dTotalFitnessScore = 0;

    CBobMap TempMemory;

    //更新适应性并对最适成员进行检查
    for (int i = 0; i<m_iPopSize; ++i)
    {
        //解析染色体基因到方向
        vector<int> vecDirections = Decode(m_vecGenomes[i].vecBits);

        //计算它的适应性分数
        m_vecGenomes[i].dFitness = m_BobsMap.TestRoute(vecDirections, TempMemory);

        //更新全部分数
        m_dTotalFitnessScore += m_vecGenomes[i].dFitness;

        //如果这是迄今为止发现的最合适的基因组,储存结果
        if (m_vecGenomes[i].dFitness > m_dBestFitnessScore)
        {
            m_dBestFitnessScore = m_vecGenomes[i].dFitness;

            m_iFittestGenome = i;

            m_BobsBrain = TempMemory;

            //Bob找到了出口?
            if (m_vecGenomes[i].dFitness == 1)
            {
                //如果是这样,停止运行
                m_bBusy = false;
            }
        }

        TempMemory.ResetMemory();

    }//next genome
}

//---------------------------Decode-------------------------------------
//
//  解析一个位为方向
//
//  0=North, 1=South, 2=East, 3=West
//-----------------------------------------------------------------------
vector<int> CgaBob::Decode(const vector<int> &bits)
{
    vector<int> directions;

    //step through the chromosome a gene at a time
    for (int gene = 0; gene < bits.size(); gene += m_iGeneLength)
    {
        //get the gene at this position
        vector<int> ThisGene;

        for (int bit = 0; bit < m_iGeneLength; ++bit)
        {
            ThisGene.push_back(bits[gene + bit]);
        }

        //convert to decimal and add to list of directions
        directions.push_back(BinToInt(ThisGene));
    }

    return directions;
}

//-------------------------------BinToInt-------------------------------
//  二进制位转为整数
//----------------------------------------------------------------------
int CgaBob::BinToInt(const vector<int> &vec)
{
    int val = 0;
    int multiplier = 1;

    for (int cBit = vec.size(); cBit>0; cBit--)
    {
        val += vec[cBit - 1] * multiplier;

        multiplier *= 2;
    }

    return val;
}



//------------------------- Render -------------------------------
//界面渲染
//----------------------------------------------------------------
void CgaBob::Render(int cxClient, int cyClient, HDC surface)
{
    m_BobsMap.Render(cxClient, cyClient, surface);

    //渲染最好的路径
    m_BobsBrain.MemoryRender(cxClient, cyClient, surface);

    //渲染额外的信息
    string s = "Generation: " + itos(m_iGeneration);
    TextOut(surface, 5, 0, s.c_str(), s.size());

    if (!m_bBusy)
    {
        string Start = "Press Return to start a new run";

        TextOut(surface, cxClient / 2 - (Start.size() * 3), cyClient - 20, Start.c_str(), Start.size());
    }

    else

    {
        string Start = "Space to stop";

        TextOut(surface, cxClient / 2 - (Start.size() * 3), cyClient - 20, Start.c_str(), Start.size());
    }

}
8. main.cpp 程序入口


#include <windows.h>   
#include <stdlib.h>
#include <time.h>

#include "CgaBob.h"
#include "defines.h"

using namespace std;

///////////////////////GLOBALS ////////////////////////////////////

const char*         szApplicationName = "Chapter3 - Pathfinder";
const char*         szWindowClassName = "PFclass";

//pointer to the GA object
CgaBob* g_pGABob;


//-----------------------------------WinProc------------------------------------------
//
//------------------------------------------------------------------------------------
LRESULT CALLBACK WindowProc(HWND hwnd,
    UINT msg,
    WPARAM wparam,
    LPARAM lparam)
{
    //窗口设备环境
    HDC             hdc;
    PAINTSTRUCT     ps;

    //窗口大小区域
    static int cxClient, cyClient;

    //用于创建后备缓冲
    static HDC      hdcBackBuffer;
    static HBITMAP  hBitmap;
    static HBITMAP  hOldBitmap;


    switch (msg)
    {
    case WM_CREATE:
    {
        //随机数种子
        srand((unsigned)time(NULL));

        //创建GA类
        g_pGABob = new CgaBob(CROSSOVER_RATE,
            MUTATION_RATE,
            POP_SIZE,
            CHROMO_LENGTH,
            GENE_LENGTH);

        //获取客户端区大小
        RECT rect;
        GetClientRect(hwnd, &rect);

        cxClient = rect.right;
        cyClient = rect.bottom;

        //后备缓冲区
        hdcBackBuffer = CreateCompatibleDC(NULL);

        HDC hdc = GetDC(hwnd);

        hBitmap = CreateCompatibleBitmap(hdc,
            cxClient,
            cyClient);

        ReleaseDC(hwnd, hdc);

        hOldBitmap = (HBITMAP)SelectObject(hdcBackBuffer, hBitmap);


    }

    break;
    //check key press messages
    case WM_KEYUP:
    {
        switch (wparam)
        {
        case VK_RETURN:
        {
            g_pGABob->Run(hwnd);

        }

        break;

        case VK_ESCAPE:
        {
            PostQuitMessage(0);
        }

        break;

        case VK_SPACE:
        {
            g_pGABob->Stop();
        }

        break;


        }//end switch
    }

    break;

    //改变了客户端大小
    case WM_SIZE:
    {
        cxClient = LOWORD(lparam);
        cyClient = HIWORD(lparam);

        //重新调整大小
        SelectObject(hdcBackBuffer, hOldBitmap);

        HDC hdc = GetDC(hwnd);

        hBitmap = CreateCompatibleBitmap(hdc,
            cxClient,
            cyClient);

        ReleaseDC(hwnd, hdc);

        hOldBitmap = (HBITMAP)SelectObject(hdcBackBuffer, hBitmap);
    }

    break;

    case WM_PAINT:
    {

        hdc = BeginPaint(hwnd, &ps);

        //后备缓冲填充为白色
        BitBlt(hdcBackBuffer, 0, 0, cxClient, cyClient, NULL, NULL, NULL, WHITENESS);

        //渲染地图和最好的路径
        g_pGABob->Render(cxClient, cyClient, hdcBackBuffer);

        //后备缓冲渲染出来
        BitBlt(hdc, 0, 0, cxClient, cyClient, hdcBackBuffer, 0, 0, SRCCOPY);

        ReleaseDC(hwnd, hdc);

        EndPaint(hwnd, &ps);
    }

    break;

    case WM_DESTROY:
    {

        SelectObject(hdcBackBuffer, hOldBitmap);

        //清除后备缓冲区
        DeleteDC(hdcBackBuffer);
        DeleteObject(hBitmap);

        //销毁GA对象
        delete g_pGABob;

        // kill the application, this sends a WM_QUIT message 
        PostQuitMessage(0);

    }

    break;

    default:break;

    }//end switch

     // 默认的消息句柄
    return (DefWindowProc(hwnd, msg, wparam, lparam));

}//end WinProc


 //-----------------------------------WinMain-----------------------------------------
 // windows程序入口点
 //-----------------------------------------------------------------------------------
int WINAPI WinMain(HINSTANCE hinstance,
    HINSTANCE hprevinstance,
    LPSTR lpcmdline,
    int ncmdshow)
{

    WNDCLASSEX winclass;
    HWND       hwnd;
    MSG        msg;


    winclass.cbSize = sizeof(WNDCLASSEX);
    winclass.style = CS_HREDRAW | CS_VREDRAW;
    winclass.lpfnWndProc = WindowProc;
    winclass.cbClsExtra = 0;
    winclass.cbWndExtra = 0;
    winclass.hInstance = hinstance;
    winclass.hIcon = LoadIcon(NULL, IDI_APPLICATION);
    winclass.hCursor = LoadCursor(NULL, IDC_ARROW);
    winclass.hbrBackground = NULL;
    winclass.lpszMenuName = NULL;
    winclass.lpszClassName = szWindowClassName;
    winclass.hIconSm = LoadIcon(NULL, IDI_APPLICATION);



    if (!RegisterClassEx(&winclass))
        return 0;


    if (!(hwnd = CreateWindowEx(NULL,
        szWindowClassName,
        szApplicationName,
        WS_OVERLAPPEDWINDOW | WS_VISIBLE,
        0, 0,
        WINDOW_WIDTH, WINDOW_HEIGHT,
        NULL,
        NULL,
        hinstance,
        NULL)))
        return 0;

    ShowWindow(hwnd, ncmdshow);
    UpdateWindow(hwnd);

    //开始消息循环
    bool bDone = false;

    while (!bDone)
    {

        while (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE))
        {
            if (msg.message == WM_QUIT)
            {
                // 如果有退出消息,退出循环
                bDone = true;
            }

            else
            {
                TranslateMessage(&msg);
                DispatchMessage(&msg);
            }
        }

        //启动GA
        if (g_pGABob->Started())
        {
            //开启时代
            g_pGABob->Epoch();

            //this will call WM_PAINT 
            InvalidateRect(hwnd, NULL, TRUE);
            UpdateWindow(hwnd);
        }


    }//end while


    UnregisterClass(szWindowClassName, winclass.hInstance);


    return 0;


} // end WinMain

到此我们的代码都写完了,现在可以运行一下,查看效果。
当然,仅靠这一个例子是不够的,还需要多实践,多运用。
可以尝试将杂交率,变异率,群体尺寸,染色体长度等参数设置各种不同的值来进行试验,加深对遗传算法的理解。

总结

常量对GA算法的影响

  • 群体尺寸
    一般情况,当群体大小减少时, 每一代的求解速度快,总体求解速度很慢,迭代的代数增大。
    一般情况,当群体大小增加时,每一代求解速度很慢,总体求解速度会加快,迭代数减少。当群体设置为3000时,整体的求解速度却下降了。当到了9000的时候,程序就奔溃了。

    群体大小设置需要考虑整体的求解速度,群体大小太大速度反而会下降。

    下面的这张图效果是在群体大小为400时
    群体大小400
    下面的这张图效果是在群体大小为1000时
    群体大小1000

  • 杂交率
    一般情况下,杂交率过于小时,杂交的几率就变小了,生物群体的进化就减慢了,整体的求解速度会下降。
版权声明:本文为cre2017原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/cre2017/article/details/82557464