精华内容
下载资源
问答
  • 本课题中的染色体交叉使用的是启发式交叉,启发式交叉的步骤如下(最近邻点法): 步骤1:从一对双亲中随机地选取一个城市最为开始城市, 步骤2:由当前城市出发,选择一条不构成循环的最短边(由双亲表达的

    旅行商问题

    一 染色体表达方式

    染色体的表达方式采用换位表达,它是TSP巡回的最自然的表达,如下图:
    在这里插入图片描述

    它的访问顺序为 3-2-5-4-7-1-6-9-8,染色体中基因的值表示城市,基因的顺序表示访问城市的顺序,这种表达的搜索空间是城市顺序“换位”的集合,采用传统的单点交叉时,可能导致非法的巡回。

    二 染色体交叉

    本课题中的染色体交叉使用的是启发式交叉,启发式交叉的步骤如下(最近邻点法):
    步骤1:从一对双亲中随机地选取一个城市最为开始城市,
    步骤2:由当前城市出发,选择一条不构成循环的最短边(由双亲表达的)。若两边都构成循环,则随机选取一个能使巡回继续的城市;
    步骤3:如巡回完成,停机;否则转第2步。
    在这里插入图片描述

    启发式交叉法明显优于其他方法

    三 染色体变异

    本课题中的染色体变异使用的是启发式变异,采用邻域技术,以获得后代的改进。启发式变异过程如下:
    步骤1:随机地选出λ个基因;
    步骤2:按所有选出基因的可能的换位产生邻域;
    步骤3:评估所有邻域点,选出最好的作为变异产生的后代。
    在这里插入图片描述

    四 种群的适值函数

    本课题中的适值函数为一个染色体中相邻两个基因的距离的加和,以及首尾两个城市的距离。

    五 种群的选择策略

    本课题中的选择策略是从交叉后代,变异后代,和原来的父代中选择最好的前n(n表示种群数量)个。

    六 种群的初始化方法

    本种群的初始化方法是从源文件读取城市信息,确定城市数量,通过城市数量产生m(表示城市数量)个不同的随机数,通过客户的输入的种群大小k,随机产生k个染色体。

    七 程序设计说明

    1、遗传算法结构图
    在这里插入图片描述

    2、种群初始化流程图
    在这里插入图片描述

    3、染色体交叉流程图
    在这里插入图片描述

    4、染色体变异流程图

    在这里插入图片描述
    在这里插入图片描述

    5、种群更新
    在这里插入图片描述

    八、程序

    //  东北大学信息科学与工程学院2020级硕士荆黎明
    //  染色体的编码方式:换位表达
    //  染色体的交叉方式:启发式交叉
    //  染色体的变异方式:启发式变异
    // Created by jlm on 2020/10/19.
    //
    #include <iostream>
    #include "class.h"
    #include <ctime>	// 产生随机数种子
    
    using namespace std;
    
    int main()
    {
        PrintMessage();
    
        srand(time(NULL));	// 设置随机数种子
    
        TSP tsp;
    
        tsp.InitiPopul();
        cout << "/*************************************种群开始迭代*************************************" << endl;
        for (int i = 0; i != tsp.GetPopulationAlgebra(); i++)
        {
            cout << i+1 << "代" << endl << endl;;
            tsp.Crossover();
            tsp.HeuristicMutation();
            tsp.Update();
            tsp.Print();
            cout << "/*************************************"<<i+1 << "代交叉变异结束" <<
                 "*************************************/" << endl;
        }
    
        return 0;
    }
    
    
    
    //
    // Created by jlm on 2020/10/19.
    //
    
    #ifndef TSP_CLASS_H
    #define TSP_CLASS_H
    
    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    struct Data {
        int PopulationAlgebra;	// 种群代数
        double NumPopulation;	// 种群数量
        double CrossoverRate;	// 交叉率
        double MutationRate;	// 突变率
    };
    
    typedef struct city{
        std::string name;
        double x;
        double y;
    }p;
    
    typedef struct DistTable{
        double distance;
        int table;
    } DT;
    
    // 输出文件信息
    void PrintMessage(void) ;
    
    class BaseTsp{
    public:
        BaseTsp();
        // 显示路径
        void ShowRoute(vector<int> &vi) const;
    
        // 获得两个城市的距离
        double GetTwoCityDist(int firstCity, int secondCity) const;
    
        // 获得n个城市的路径
        void GetCityDist(const vector<int> &vi, double &distance) const;
    
        // 生成随机数
        void GeneratorRand(vector<int> &vi) const;
    
        // 获得nCity数据
        int GetnCity(void) const;
    
        // 打印染色体
        void printFunc(const vector<int> &vi) const;
    
    private:
        void ReadCityData();
        vector<p> vCity;
        int nCity;
    };
    
    class TSP: public BaseTsp
    {
    public:
        TSP(int Size, double CrossoverRate, double MutationRate, int PopulationAlgebra);
        TSP(struct Data data);
        TSP();
        void InitiPopul(void);
        void Crossover(void);
        void HeuristicMutation(void);
        void Update(void);
        void Print(void);
    
    public:
        // 获得种群代数
        int GetPopulationAlgebra(void) const;
    
    private:
        // 两个父代产生一个子代
        void GeneratorOffspring( const vector<int> &va, const vector<int> &vb, vector<int> &offspring) const;
    
        // 确定定位点
        int DeterminePoint(const vector<int> &vi, const int &value) const;
    
        // 为种群生成一个随机数列,该数列作为种群中各个染色体的交叉率 、变异率
        void ForPopulRand(vector<double> &vd) const;
    
        // 根据适值选择变异的子代
        void SelectOffspring(const vector<vector<int> > &mutoffspring, vector<int> &bestMuOffspring) const;
    
        // 基因换位,传入一个父代基因,输出全排列后的所有基因
        void GeneTransposition(const vector<int> &vpa, vector<vector<int> > &vvGene) const;
    
        // 全排列算法 传入一个数组,产生一个全排列数组
        void Permutation(vector<int> &vi, vector<int>::iterator begin,
                         vector<int>::iterator end, vector<vector<int> > &vvi) const;
    
        // 生成n个不同的随机数,范围0~n;
        void GeneratorRand(int n, int start, int end, vector<int> & vi) const;
    
        // 对基因进行插值
        void Interpolation(const vector<int> &position, const vector<int> &vGene, vector<vector<int> > &vvGene) const;
    
        // 根据适值选择子代,子代的个数为种群的数量
        void SelectOffspring(vector<vector<int> > &vparent);
    
        // 寻找最后一个元素是否前面出现过
        bool findFun(vector<int> &vi) const;
    
        int DeleteFun(vector<int> & vtParent, vector<int> & voffspring) const;
    
        void InputData(struct Data & data) const;
    
    private:
        int Size;	//种群数量
        double CrossoverRate;	//交叉率
        double MutationRate; 	// 突变率
        int PopulationAlgebra;  // 种群迭代次数
    
        vector<vector<int> > vParent;   // 父代染色体
        vector<vector<int> > vOffspring;    // 交叉产生的染色体
        vector<vector<int> > vMutOffspring; // 变异产生的染色体
    };
    
    #endif //TSP_CLASS_H
    
    
    //
    // Created by jlm on 2020/10/19.
    //
    #include "class.h"
    #include <iostream>
    #include <fstream>
    #include <cstdlib>	// support for exit()	//随机数
    #include <cmath>
    #include <ctime>	// 产生随机数种子
    #include <vector>
    #include <algorithm> 	//  for sort() 排序函数
    
    using namespace std;
    
    /*
     * @BaseTsp()构造函数
     */
    BaseTsp::BaseTsp()
    {
        ReadCityData();
    }
    /*
     @ ReadCityDate() :实现文件数据读取
     */
    void BaseTsp::ReadCityData()
    {
    
        cout << "Enter name of data file: ";
        string filename;
        cin >> filename;
    
    
        ifstream file(filename);
        if(!file.is_open())
        {
            cerr << "文件未能打开:" << filename << endl;
            cerr << "程序终止\n";
            exit(EXIT_FAILURE);		// should include <cstdlib>
        }
    
        p City;	// 城市的结构体
        nCity = 0;
        file >> City.name >> City.x >> City.y ;
        while(file.good())
        {
            vCity.push_back(City);
            nCity++;
            file >> City.name >> City.x >> City.y ;
        }
    
        if(file.eof())
        {
            cout <<" 文件数据信息读取完成.\n";
        }
        else if (file.fail())
        {
            cout << " 文件数据信息不匹配.\n";
        }
        else
        {
            cout << " 由未知原因导致程序输入异常终止.\n";
        }
        file.close();
    
        cout << "数据读取完成..." << endl;
    }
    /*
     * @ShowRoute:该函数实现输出巡回路径
     * @ vi : 染色体
     */
    void BaseTsp::ShowRoute(vector<int> &vi) const
    {
        cout << "最优路径:  " ;
        //向屏幕输出结果
        int num = 0;
        for (auto a:vi)
        {
            cout << vCity[a - 1].name << "->" ;
            num++;
            if(num % 20 == 0)   // 20个城市换行
                cout << endl;
        }
        cout << vCity[vi[0] - 1].name << endl;
    }
    /*
     * @GetTwoCityDist():该函数实现两个城市距离计算
     * @返回值:两个城市间的距离
     * @firstCity: 第一个城市的序号
     * @secondCity: 第二个城市的序号
     */
    double BaseTsp::GetTwoCityDist(int firstCity, int secondCity) const
    {
        double distance;
        distance = sqrt((vCity[firstCity - 1].x - vCity[secondCity - 1].x)*(vCity[firstCity - 1].x - vCity[secondCity - 1].x)
                        +(vCity[firstCity - 1].y - vCity[secondCity - 1].y)*(vCity[firstCity - 1].y - vCity[secondCity - 1].y));
        return distance;
    }
    
    void BaseTsp::GetCityDist(const vector<int> &vi, double &distance) const
    {
        distance = 0;
        int n = vi.size();
        for (int i = 0; i < n - 1; i++)
        {
            distance += GetTwoCityDist(vi[i], vi[i+1]);
        }
        // 最后回到原点
        distance += GetTwoCityDist(vi[n - 1], vi[0]);
    }
    /*
     *@GetnCity:获得城市的数量
     */
    int BaseTsp::GetnCity(void) const
    {
        return nCity;
    }
    /*
     * @GeneratorRand:为染色体产生随机数,随机数范围位【1,城市的数量】
     * @vi: 染色体
     */
    void BaseTsp::GeneratorRand(vector<int> &vi) const	// for chromosome(染色体)
    {
        int numCity = GetnCity();
        int randNum;
        int j;
        for (int i = 0; i < numCity; i++)
        {
            while(1)
            {
                randNum = rand() % numCity + 1;	// 获取固定区间[m,n]的随机数的公式 rand % (n - m + 1) + m
                for (j = 0; j < i; j++)
                    if(vi[j] == randNum)	break;	// 检查重复
                if (j == i)	// 没有重复,保存到vi中
                {
                    vi.push_back(randNum);
                    break;
                }
            }
        }
    }
    
    /*
     * @printFunc(): 打印染色体
     */
    void BaseTsp::printFunc(const vector<int> &vi) const
    {
        for (auto a:vi)
        {
            cout << a << "  ";
        }
        cout << endl;
    }
    
    /*
     * @TSP: TSP() 的构造函数
     * @ Size: 种群的数量
     * @ CrossoverRate: 种群的交叉率
     * @ MutationRate: 种群的变异率
     */
    TSP::TSP(int Size, double CrossoverRate, double MutationRate, int PopulationAlgebra):BaseTsp()
    {
        this -> Size = Size;
        this -> CrossoverRate = CrossoverRate;
        this -> MutationRate = MutationRate;
        this -> PopulationAlgebra = PopulationAlgebra;
    }
    /*
     * @TSP():构造函数
     * @data: 结构体
     */
    TSP::TSP( struct Data data):BaseTsp()
    {
       this -> Size = data.NumPopulation;
       this -> CrossoverRate = data.CrossoverRate;
       this -> MutationRate = data.MutationRate;
       this -> PopulationAlgebra = data.PopulationAlgebra;
    }
    
    TSP::TSP() :BaseTsp()
    {
        struct Data data;
        InputData(data);
        this -> Size = data.NumPopulation;
        this -> CrossoverRate = data.CrossoverRate;
        this -> MutationRate = data.MutationRate;
        this -> PopulationAlgebra = data.PopulationAlgebra;
    }
    /*
     * @InitiPopul(): tsp的初始化函数,并打印产生的初始种群
     */
    void TSP::InitiPopul(void)
    {
        for (int i = 0; i < Size; i++)
        {
            vector<int> vi;
            BaseTsp::GeneratorRand(vi);
            vParent.push_back(vi);
        }
    
        // 打印出初始种群
        cout << "初始种群" <<endl;
        int i = 0;
        for (auto a:vParent)
        {
            cout << ++i << "#         ";
            printFunc(a);
        }
    }
    
    /*
     * @Crossover():种群交叉,并打印种群交叉产生的子代
     */
    void TSP::Crossover(void)
    {
        vector<double> vd;	// 存储各个染色体的交叉率
        ForPopulRand(vd);
    
        // 寻找小于交叉率的染色体
        vector<int> vc;	// 存储染色体小于交叉率的序号
        for (int i = 0; i != vd.size(); i++)
        {
            if (vd[i] <= CrossoverRate)
            {
                vc.push_back(i);
            }
        }
    
        if (vc.size()%2)	// 删除一个数,使得产生偶数个父代
        {
            int t = rand() % vc.size();		// 随机产生一个数
            vc.erase(vc.begin() + t);
        }
    
        // 随机选择两个染色体进行交叉
    
        int nNum = vc.size()/2;	// 进行交叉的次数
        for (int i = 0; i != nNum; i++)
        {
            int vaPoint = rand() % vc.size();
            int vaValue = vc[vaPoint];	// 父代1号索引值
            vc.erase(vc.cbegin() + vaPoint);
    
            int vbPoint = rand() % vc.size();
            int vbValue = vc[vbPoint];	// 父代2号索引值
            vc.erase(vc.cbegin() + vbPoint);
    
            vector<int> offspring;	// 存储交叉的子代
    
            GeneratorOffspring(vParent[vaValue],vParent[vbValue],offspring);
            vOffspring.push_back(offspring);
        }
    }
    /*
     * @GeneratorOffspring():两个染色体进行交叉,产生子代染色体
     * @va: 父代染色体
     * @vb: 父代染色体
     * @offspring: 交叉产生的子代染色体
     */
    void TSP::GeneratorOffspring( const vector<int> &va, const vector<int> &vb,
                                  vector<int> &offspring) const
    {
        int nCity = GetnCity();
    
        int firstCity = rand() % nCity + 1;	// 随机选择一个城市作为开始,随机数的产生范围为[1, ncity]
        offspring.push_back(firstCity);	// 第一个基因
    
        int vaPoint, vbPoint;
        int count = 0;
    
        vaPoint = DeterminePoint(va, firstCity);
        vbPoint = DeterminePoint(vb, firstCity);
    
        vector<int> vtParent(va.begin(),va.end());
    
        while (offspring.size() != nCity)
        {
            if (vaPoint == nCity - 1)
            {
                vaPoint = -1;
            }
            if (vbPoint == nCity - 1)
            {
                vbPoint = -1;
            }
    
            double distanceOne = GetTwoCityDist(offspring[offspring.size() - 1],va[vaPoint + 1]);
            double distanceTwo = GetTwoCityDist(offspring[offspring.size() - 1], vb[vbPoint + 1]);
    
            if (distanceOne >= distanceTwo)
            {
                offspring.push_back(vb[vbPoint + 1]);
    
                if (findFun(offspring)) //最后一个元素和前面的基因(元素)重复
                {
                    offspring.push_back(va[vaPoint + 1]);
                    if(findFun(offspring))
                    {
                        //随机选择一个城市
                        int city = DeleteFun(vtParent, offspring);
                        offspring.push_back(city);
                        vaPoint = DeterminePoint(va, city);
                        vbPoint = DeterminePoint(vb, city);
                    }
                    else
                    {
                        vaPoint = vaPoint + 1;
                        vbPoint = DeterminePoint(vb, va[vaPoint]);
                    }
                }
                else
                {
                    vaPoint = DeterminePoint(va, vb[vbPoint + 1]);
                    vbPoint = vbPoint + 1;
                }
            }
            else
            {
                offspring.push_back(va[vaPoint + 1]);
                if (findFun(offspring))
                {
                    offspring.push_back(vb[vbPoint + 1]);
                    if (findFun(offspring))
                    {
                        // 随机选择一个城市
                        int city = DeleteFun(vtParent, offspring);
                        offspring.push_back(city);
                        vaPoint = DeterminePoint(va, city);
                        vbPoint = DeterminePoint(vb, city);
                    }
                    else
                    {
                        vaPoint = DeterminePoint(va, vb[vbPoint + 1]);
                        vbPoint = vbPoint + 1;
                    }
                }
                else
                {
                    vaPoint = vaPoint + 1;
                    vbPoint = DeterminePoint(vb, va[vaPoint]);
                }
            }
        }
    }
    /*
     * @DeleteFun():删除添加的重复城市,并随机选择一个城市
     * @vtParent: 父代
     * @voffspring: 子代
     */
    int TSP::DeleteFun(vector<int> & vtParent, vector<int> &voffspring) const
    {
        for (int i = 0; i != voffspring.size(); i++)
        {
            for (int j = 0; j != vtParent.size(); j++)
            {
                if (voffspring[i] == vtParent[j])
                {
                    vtParent.erase(vtParent.begin() + j);
                    j = j - 1;
                }
            }
        }
    
        int cityPoint = rand() % vtParent.size()  + 1;
        return vtParent[cityPoint - 1];
    }
    
    /*
     *@ findFun : 查找染色体中前面已经出现的城市,若出现则删除
     */
    
    bool TSP::findFun( vector<int> &vi) const
    {
        for (int i = 0; i != vi.size()- 1; i++)	// 减去2的原因是value
        {
            if (vi[i] == vi[vi.size() - 1])
            {
                vi.erase(vi.cbegin() + vi.size() - 1);
                return true;
            }
        }
        return false;
    }
    
    /*
     * @DeterminePoint():该函数的功能是确定value值在染色体的vi的位置
     * @ vi: 染色体
     * @ value: 染色体的某个值
     */
    int TSP::DeterminePoint(const vector<int> &vi, const int &value) const
    {
        for (int i = 0; i != vi.size(); i++)
        {
            if (value == vi[i])
            {
                return i;
            }
        }
    }
    /*
    @function :函数功能为为种群生成一个随机数列,该随机数列可作为交叉率和突变率
    @ vd : vd存储的是生成的随机数列
    */
    void TSP::ForPopulRand(vector<double> &vd) const
    {
        srand(time(NULL));
        double randNum;
        const int N = 99;		// 两位小数
        for (int i = 0; i < Size; i++)
        {
            randNum = rand() %(N + 1)/(double) (N + 1);	// 生成0-1间的随机数
            vd.push_back(randNum);
        }
    }
    
    /*
     * @ HeuristicMutation(): 该函数的动能是对染色体进行变异
     */
    void TSP::HeuristicMutation(void)
    {
        // 第一步:根据突变率选择变异的父代
        vector<double>  vd;	// 存储的是各个染色体的突变率
        ForPopulRand(vd);
    
        vector<int> vmu;	// 存储需要突变的染色体序号
    
        for (int i = 0; i != vd.size(); i++)
        {
            if (vd[i] <= MutationRate)
            {
                vmu.push_back(i);
            }
        }
    
        for (int i = 0; i != vmu.size(); i++)
        {
            vector<vector<int> > vvGene;	// 存储全排列后的所有染色体
            GeneTransposition(vParent[vmu[i]], vvGene);
    
            // 对于每个染色体选择最优的子代
            vector<int> bestMuOffspring;
            SelectOffspring(vvGene, bestMuOffspring);
            vMutOffspring.push_back(bestMuOffspring);
        }
    }
    
    /*
    @function:基因换位,传入一个父代基因,输出全排列后的所有染色体
    @vpa: 表示父代基因
    @vvGene: 表示生成的变异基因(已经除去了和父代相同的基因)
    */
    void TSP::GeneTransposition(const vector<int> &vpa, vector<vector<int> > &vvGene) const
    {
    
        int numGene = rand() % (vpa.size() - 2) + 2;	// 选择numGene 个基因,范围在[2~vpa.size()-1]
    
        // 对n个基因位置进行插值
        vector<int> vi;	// vi 存储变异基因的位置
        GeneratorRand(numGene, 0, vpa.size() - 1, vi);
        Interpolation(vi, vpa, vvGene);
    }
    
    // 对基因进行插值,生成基因全排列
    /*
    @ position : 存储的是随机选择的基因位置
    @ vGene : 传入的父代基因
    @ vvGene : 生成基因全排列
    */
    void TSP::Interpolation(const vector<int> &position, const vector<int> &vGene, vector<vector<int> > &vvGene) const
    {
        vector<int> vTemp;	// 装载随机选择的基因
        for (auto a:position)
        {
            vTemp.push_back(vGene[a]);
        }
    
        vector<int> vtemp(vTemp.begin(),vTemp.end());
    
        // 对选择的基因进行全排列
        vector<vector<int> > vvgene;	// 存储选择的基因的全排列
        Permutation(vTemp, vTemp.begin(), vTemp.end(), vvgene);
    
        // 删除和原始基因一样的序列
        int numGene = vvgene.size();
        for (auto it = vvgene.cbegin(); it != vvgene.cend(); it++)
        {
            for (int j = 0; j != (*it).size(); j++)
            {
                if((*it)[j] == vtemp[j])
                {
                    if(j == (*it).size() - 1)
                    {
                        vvgene.erase(it);
                    }
                }
                else
                {
                    break;
                }
            }
            if(numGene != vvgene.size())	// 已经找到重复基因,跳出循环
            {
                break;
            }
        }
        // 将生成的全排列数组分配到基因中
        vector<int> gene(vGene.begin(),vGene.end());
    
        for (auto a:vvgene)
        {
            int i = 0;
            for (auto b:a)
            {
                gene[position[i]] = b;
                i++;
            }
            vvGene.push_back(gene);
        }
    }
    
    /*
    function: 该函数的功能是生成n个数的全排列
    @vi:存储的是需要进行全排列的n个数
    @begin:存储的是vi的首迭代器
    @end: 存储的是vi的尾迭代器
    */
    void TSP::Permutation(vector<int> &vi, vector<int>::iterator begin,
                          vector<int>::iterator end, vector<vector<int> > &vvi) const
    {
        if (begin == end)//递归的基础部分
        {
            vector<int> temp;
            for (vector<int>::iterator it = vi.begin(); it != end; it++)
            {
                temp.push_back(*it);
            }
            vvi.push_back(temp);
        }
        else
        {
            for (auto it = begin; it != end; it++)
            {
                swap(*begin, *it);
                Permutation(vi, begin+1, end, vvi);
                swap(*begin, *it);
            }
        }
    }
    
    /*
    @ n : 产生随机数的个数
    @ start :
    @ end : [start end] 产生随机数的范围
    @ vi :生成的随机数	(存储随机选择的基因位置)
    */
    void TSP::GeneratorRand(int n, int start, int end, vector<int> &vi) const
    {
        int randNum;
        int j;
        for (int i = 0; i != n; i++)
        {
            while(1)
            {
                randNum = rand() % (end - start + 1) + start;
                for (j = 0; j < i; j++)
                {
                    if (vi[j] == randNum)
                        break;
                }
                if (j == i)
                {
                    vi.push_back(randNum);
                    break;
                }
            }
        }
    }
    /*
     * @ Update():该函数的功能是更新种群
     */
    void TSP::Update(void)
    {
        for (auto a:vOffspring)
        {
            vParent.push_back(a);
        }
        for (auto a:vMutOffspring)
        {
            vParent.push_back(a);
        }
    
        SelectOffspring(vParent);
    }
    /*
     * @SelectOffspring(): 该函数的功能是选择最优的染色体(选择的数量是初始种群的个数)
     * @ vparent: 需要进行选择的种群
     */
    void TSP::SelectOffspring(vector<vector<int> > &vparent)
    {
        vector<DT> vDT;	// 存储距离和标号
    
        for (int i = 0; i != vparent.size(); i++)
        {
            DT dt;
            GetCityDist(vparent[i], dt.distance);
            dt.table = i;
            vDT.push_back(dt);
        }
    
        sort(vDT.begin(),vDT.end(),
             []( struct DistTable &dtOne,  struct DistTable &dtTwo){ return (dtOne.distance < dtTwo.distance);
             });
    
        for (int i = 0; i != vDT.size(); i++)
        {
            for (int j = i + 1; j != vDT.size(); j++)
            {
                if (vDT[i].distance == vDT[j].distance)
                {
                    vDT.erase(vDT.begin() + i);
                    j = j - 1;
                }
            }
        }
    
        vector<vector<int> > VPARENT;
        for (int i = 0; i != Size; i++)
        {
            VPARENT.push_back(vparent[vDT[i].table]);
        }
    
        vparent.clear();	// 删除所有元素
    
        for (auto a:VPARENT)
        {
            vparent.push_back(a);
        }
    }
    
    /*
     * Print(): 该函数的功能是打印种群的最优路径和最优路径距离
     */
    void TSP::Print()
    {
    //    cout << "交叉产生的后代" << endl;
    //    for (int i = 0; i != vOffspring.size(); i++)
    //    {
    //        cout << i+1 << "#         ";
    //        printFunc(vOffspring[i]);
    //    }
    //    cout << "变异产生的后代" << endl;
    //    for (int i = 0; i != vMutOffspring.size(); i++)
    //    {
    //        cout << i+1 << "#         ";
    //        printFunc(vMutOffspring[i]);
    //    }
        vOffspring.clear(); // 删除本代产生的交叉子代
        vMutOffspring.clear();  // 删除本代变异产生的子代
    //    cout << "物竞天择,适者生存后的种群" << endl;
    //    for (int i = 0; i != vParent.size(); i++)
    //    {
    //        cout << i+1 << "#         ";
    //        printFunc(vParent[i]);
    //    }
    
        vector<int> bestSoulation;
        SelectOffspring(vParent, bestSoulation);
        cout << "该种群中的最优解:" << endl;
        printFunc(bestSoulation);
    
        double distance ;
        GetCityDist(bestSoulation, distance);
    
        ShowRoute(bestSoulation);
        cout << "该种群中的最短路径为:" << distance << endl;
        
        // 将distance存储在CSV格式文件中
        static int start = 0;
    	ofstream oFile;
    	if (start == 0)	// 第一代 
    	{
    		oFile.open("distance.csv");
    		oFile << distance << endl;
    		oFile.close();
    	}
    	oFile.open("distance.csv", ofstream::app);	// 为了保留文件内容,必须显示指定app模式
    	oFile << distance << endl;
    	oFile.close(); 
    	start++;
    }
    
    /*
    @ function : 根据适值选择最好的子代
    @ mutoffspring : 变异基因的全排列组合
    @ bestMuOffspring:  选择出最好的子代
    */
    void TSP::SelectOffspring(const vector<vector<int> > &mutoffspring, vector<int> &bestMuOffspring) const
    {
        vector<double> vd;	// 存储城市路径的总距离
        for (auto a:mutoffspring)
        {
            double distance;
            GetCityDist(a,distance);
            vd.push_back(distance);
        }
    
        double min = vd[0];
        int minKpoint = 0;
        for (int i = 0; i != vd.size(); i++)
        {
            if (vd[i] <= min)
            {
                minKpoint = i;
            }
        }
    
        for (auto a:mutoffspring[minKpoint])
        {
            bestMuOffspring.push_back(a);
        }
    }
    
    int TSP::GetPopulationAlgebra(void) const
    {
        return (PopulationAlgebra);
    }
    
    void TSP::InputData(struct Data & data) const
    {
        cout << "请输入数据信息:种群代数,种群数量,种群交叉率,种群突变率等" << endl << endl;
        cout << "种群代数: " ;
        cin >> data.PopulationAlgebra;
        cout << "种群数量:";
        cin >> data.NumPopulation;
        cout << "种群交叉率:";
        cin >> data.CrossoverRate;
        cout << "种群突变率:";
        cin >> data.MutationRate;
    }
    
    /*
     * @PringMessage(): 该函数的功能是打印程序信息
     */
    void PrintMessage(void)
    {
    	cout << "学校:东北大学" << endl;
        cout << "学院:信息科学与工程学院" << endl;
        cout << "专业:控制科学与工程" << endl;
        cout << "学号:2000764" << endl;
        cout << "班级:2005班" << endl;
        cout << "姓名:荆黎明" << endl;
    
        cout << endl << endl;
        cout << "注:" << endl;
        cout << "本程序的调试工作是在Ubuntu18.04上完成的!!!" << endl;
        cout << "染色体的编码方式:换位表达" << endl;
        cout << "染色体的交叉方式:启发式交叉" << endl;
        cout << "染色体的变异方式:启发式变异" << endl;
        cout << endl << endl;
    }
    
    
    
    展开全文
  • 关于免疫启发式变异算子在某些离散优化问题中的有效性
  • 通过构建理想样本探讨了启发式分割算法在水文变异诊断中的可行性,比较了其与传统变异检验方法在检验性能上的差异,同时结合珠江三角洲河网三水站1900-2004年年最大洪峰流量序列检验其实际应用效果。研究表明该方法能...
  • 为了解决传统蚁群算法求解TSP问题的求解时间较长、易于局部收敛的问题,提出了一种基于变异启发式选择的蚁群优化算法。利用较优路径中城市相互之间的邻接特点,避免了大范围搜索求解,使得能具有较好的初始解,将...
  • CARP问题的元启发式算法综述,李庆华,李波,本文全面综述了国内外用于求解容量约束弧路径问题(CARP问题)及其变异形式的各种元启发式算法的研究现状,指出了元启发式算法的�
  • 启发式算法和元启发式算法

    千次阅读 2019-10-13 12:08:59
    启发式算法(Heuristic Algorigthm): 是一种基于直观或经验构造的算法,在可接受的花费(指计算时间、计算空间等)给出待解决优化问题的每一实例的一个可行解,该可行解与与最优解的偏离程度一般不可以事先预计。 启发...

    启发式算法(Heuristic Algorigthm):

    是一种基于直观或经验构造的算法,在可接受的花费(指计算时间、计算空间等)给出待解决优化问题的每一实例的一个可行解,该可行解与与最优解的偏离程度一般不可以事先预计。

    启发式算法是一种技术,这种算法可以在可接受的计算费用内找到最好的解,但不一定能保证所得到解的可行性及最优性,甚至大多数情况下无法阐述所得解与最优解之间的近似程度。

    元启发式算法(MetaHeuristic Algorigthm):

    是启发式算法的改进,它是随机算法局部搜索算法相结合的产物。

    .

    启发式算法包括遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法及神经网络算法等。

    比较:

    1)两者无法保证得到某个优化问题的全局最优解;
    2)两者存在意义就是快速地求解那些不存在或者暂时未找到多项式时间内算法的问题。比如TSP问题,flowshop问题。而像Linear programming就不会用heuristics或者meta-heuristics去求解了;
    3)不同点在于:heuristics算法中不会存在“随机因素”。对于同样一个问题,只要给定了一个输入,那么算法执行的步骤就固定下来了,输出也因此固定。但是meta-heuristics就不一样了,里面包括了“随机因素”。就拿遗传算法来说,同样一个初始的种群(输入一致),运行两次(每次100代),得到的结果很可能是不同的。因为交叉、变异操作的对象是随机选择的。在比如模拟退火,按照metropolis准则跳出局部最优解时也是随机的,这也解释了为神马SA可能得到全局最优解。总之,heuristics在固定的输入下得到固定的输出。meta-heuristics在固定的输入下得到的输出不固定。
    (引用自评论)

    展开全文
  • 启发式算法 定义:启发式算法(heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指计算...

    启发式算法

    定义:启发式算法(heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。现阶段,启发式算法以仿自然体算法为主,主要有蚁群算法模拟退火法神经网络等。

    通俗解释:针对某个特定(problem specific)的问题,由于这个问题的最优解不好求或者求不出,那么就退而求其次,求次优解或者可行解,巧了,启发式算法就是来干这个事的,即启发式算法用来求问题的可行解

     

    元启发式算法

    定义:元启发式算法主要指一类通用型的启发式算法,这类算法的优化机理不过分依赖于算法的组织结构信息,可以广泛的应用到函数的组合优化和函数计算中

    通俗解释:说白了,元启发式算法是启发式算法的一种改进,它不依赖于特定问题,通常是一个通用的启发式策略(problem independent),因而能够运用于更广泛的方面

     

    异同点比较

    首先说相同点:(1)两者都无法保证得到某优化问题的全局最优解(2)二者目的相同,都是为了快速地求解那些不存在或者暂时未找到多项式时间内算法的问题,比如TSP问题,flowshop问题。而像Linear programming就不会用heuristics或者meta-heuristics去求解了

    不同点:不同点在于:heuristics算法中不会存在“随机因素”。对于同样一个问题,只要给定了一个输入,那么算法执行的步骤就固定下来了,输出也因此固定。但是meta-heuristics就不一样了,里面包括了“随机因素”。就拿遗传算法来说,同样一个初始的种群(输入一致),运行两次(每次100代),得到的结果很可能是不同的。因为交叉、变异操作的对象是随机选择的。在比如模拟退火,按照metropolis准则跳出局部最优解时也是随机的,这也解释了为神马SA可能得到全局最优解。总之,heuristics在固定的输入下得到固定的输出。meta-heuristics在固定的输入下得到的输出不固定。(PS:我有个疑问,看了网上很多资料,发现很多人把遗传算法、模拟退火、蚁群算法等也称作启发式算法,那它们到底是启发式算法还是元启发式算法?或者说根本没必要去对它们分类?希望有大神给予解答)

     

    超启发式算法

    定义:超启发式算法提供了某种高层策略(High-Level Strategy,HLS),通过操纵或管理一组低层启发式算法(Low-Level Heuristics, LLH),以获得新启发式算法。这些新启发式算法则被运用于求解各类NP-难解问题。

    通俗解释:这个概念是近些年新兴的,我只说下我自己的理解(没有深入研究,肯定存在不足之处)。首先,二者共同点是超启发式算法与启发式算法均是为了求解问题实例而提出的;二者的不同点在于各自的搜索空间构成不同:传统启发式算法是工作在由问题实例的解构成的搜索空间上;而超启发式算法运行在一个由启发式算法构成的搜索空间上。换句话说,就是超启发方法先对一堆启发式方法进行组合优化,之后拿着这一组方法再去对问题进行求解。

     

    主要参考以下文章:

    1. https://leovan.me/cn/2019/04/heuristic-algorithms/
    2. http://oscar-lab.org/paper/cccf_11.pdf
    3. https://www.cnblogs.com/tsingke/p/12512250.html
    4. https://zhuanlan.zhihu.com/p/37199993
    5. https://blog.csdn.net/econe_wei/article/details/102531451
    6. https://blog.csdn.net/u011561033/article/details/85623533?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.control&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.control
    展开全文
  • 五种典型启发式算法对比总结

    千次阅读 2021-08-24 16:42:49
    五种启发式算法包括:遗传算法,粒子群算法,蚁群算法,禁忌搜索,模拟退火 之前的博文中已经写了五种启发式算法的偏应用的总结,避开背景知识和代码,已经尝试从问题和解的角度去总结五种算法的流程和思路 其中: ...

    说明:

    1. 五种启发式算法包括:遗传算法,粒子群算法,蚁群算法,禁忌搜索,模拟退火
    之前的博文中已经写了五种启发式算法的偏应用的总结,避开背景知识和代码,已经尝试从问题和解的角度去总结五种算法的流程和思路
    其中:
    遗传算法,粒子群算法,模拟退火 附带的示例是求解函数极值
    蚁群算法,禁忌搜索 附带的示例是求解TSP

    遗传算法(GA):      遗传算法(GA)总结:算法流程,实例,思路
    粒子群算法(PSO):粒子群算法(PSO)总结:算法流程,实例,思路
    蚁群算法(ACO):   蚁群算法(ACO)总结:算法流程,实例,思路
    禁忌搜索(TS):      禁忌搜索(TS)总结:算法流程,实例,思路
    模拟退火(SA):      模拟退火(SA)总结:算法流程,实例,思路

    2. 不同的启发式算法原本就是针对不同的问题而发明的,各种方法有各自的适用范围,原则上应该是根据具体问题选择算法,脱离具体问题而单独对比算法不太合理。但是对比总结有助于理清各个算法的思路,所以本文还是给出简要对比

    3. 各种启发式方法都存在各种改进版,都在不断的更新完善,这里只是根据个人的理解,总结基础版的五种启发式方法

    以下是根据个人理解的对比总结

    注意:各种算法里的每种操作都可以自由设计,而且设计方式不固定,所以对比总结里的某些方面不一定完全准确,这里仍然是尝试从问题和解的角度去总结

    1.遗传算法

    2.粒子群算法

    3.蚁群算法

    4.禁忌搜索

    5.模拟退火

    群体/单体

    群体

    群体

    群体

    单体

    单体

    使用问题范围

    离散优化

    连续优化

    连续优化

    离散优化

    离散优化

    离散优化

    连续优化

    新解的产生方式

    (选择)

    交叉

    变异

    速度更新公式产生增量,增量添加到当前解上

    依据信息素和城市间距,以概率产生新解

    构造邻域,邻域中选取

    构造偏移量,偏移量加到当前解上

    逐步靠近优解

    (优解对于新解的产生过程的引导性)

    选择过程中的轮盘赌,更优的解保留的几率更大

    群体最优解、单体最优解都影响每个解的更新过程

    信息素越浓、城市间距越短的路径被选中的概率越大

    选用最优解产生领域

    更优的解一定接受

    劣解概率接受

    (跳出局部最优)

    交叉变异都会产生新解,种群更新时采用轮盘赌,劣解有几率保留

    解的更新过程中产生的新解会覆盖群体最优解、单体最优解的周边解空间

    信息素不浓、城市间距不短的路径也有概率被选中

    只能取和禁忌表中保存的解不相同的解,有几率取到次优解或劣解

    Metropolis准则,以概率接受劣解

    算法中的随机性

    1.初始解

    2.选择环节

    某个解是否保留

    3.交叉环节

    某个基因是否用于交叉,交叉位置

    4.变异环节

    某个基因是否变异,变异位置

    1.初始解

    2.初始速度

    3.速度更新公式里的随机权重

    蚂蚁在某城市选择下一个要去的城市的概率

    初始解

    1.初始解

    2.产生的新解

    3.接受劣解时概率

    核心思路

    (思想内涵)

    (算法特色)

    选择环节保留优解,交叉变异环节产生新解

    解的更新同时利用全局最优解和局部最优解信息

    反馈机制,且搜索机制深入到具体问题层面

    通过禁忌表避开已经搜索到的最优解,迫使算法搜索新的最优解

    搜索到的更好的解一定接受,搜索到的更差的解以概率接受

    展开全文
  • 基于启发式分割和近似熵法的径流序列变异诊断 (2014年)
  • 启发式算法

    千次阅读 2021-08-07 20:45:11
    启发式算法写在前面在这里插入图片描述传统启发式算法贪心算法局部搜索爬山算法元启发式算法禁忌搜索模拟退火算法遗传算法蚁群算法粒子群优化算法超级启发式算法参考 想了好久,还是准备要写下这篇文章,好好总结...
  • 启发式算法介绍

    千次阅读 2019-08-10 16:30:53
    启发式算法(Heuristic Algorithm)有不同的定义:一种定义为,一个基于直观或经验的构造的算法,对优化问题的实例能给出可接受的计算成本(计算时间、占用空间等)内,给出一个近似最优解,该近似解于真实最优解的...
  • 该代码包括遗传算法 (GA) 的主要功能:精英主义、锦标赛选择、交叉(两点和启发式)和变异。 有一些使用 GA 的 benchmank 测试函数。 * 它是在遗传工具箱的帮助下开发的。
  • 启发式搜索算法

    2021-08-24 21:57:55
    遗传算法:遗传算法本质上,是一种高效的启发式搜索算法。   算法步骤:(1)产生种群,在此,相当于产生染色体,本质上是对问题的解进行编码。常见的编码方案有:二进制编码,浮点编码等。 (2)计算适应度:...
  • 启发式算法详解——遗传算法算法原理算法详解算法详解算法总结 算法原理       遗传算法(Genetic Algorithm)遵循『适者生存』、『优胜劣汰』的原则,是一类借鉴生物界自然选择和自然遗传机制的随机...
  • 启发式算法(Heuristic)概述

    千次阅读 2020-10-13 10:29:47
    启发式算法(Heuristic)概述 一个启发式的例子。 驾驶汽车到达某人的家,写成算法是这样的:沿167 号高速公路往南行至Puyallup;从South Hill Mall 出口出来后往山上开 4.5 英里;在一个杂物店旁边的红绿灯路口右转...
  • 编码的表示代表,编码对算法的效率至关重要,其必须满足连通性原理才能为元启发式算法所用,为的是保证任意两解之间都存在一条搜索路径,尤其是对最优解来说更是如此。 常见的编码: 二进制编码:解可表示为一个n位...
  • matlab启发式算法

    千次阅读 2020-10-06 10:40:30
    启发式算法 (Heuristic Algorithm) 是一种基于直观或经验的局部优化算法.。 启发式算法的定义: 人们常常把从大自然的运行规律或者面向具体问题的经验和规则中启发出来的方法称之为启发式算法. 现在的启发式算法也...
  • 启发式

    2020-08-20 15:13:05
    启发式 是什么 怎么实现 应用 1. 是什么 启发式: 根据某种经验进行迭代求解,需要对要解决的问题有深入的认识,比如要确定天亮的时间,可以根据晨晓鸡叫这个经验来确定,听到鸡叫判断天亮,也可以根据其他的...
  • 浅析超启发式算法(hyper heuristic)

    千次阅读 多人点赞 2019-01-02 17:02:08
    在介绍超启发式算法前,先来简单聊一聊启发式算法。为解决NP难问题(精确求解非常困难,但验证结果十分简单,例如旅行商问题就是一个典型的NP难问题),启发式算法应运而生。据我所知,启发式算法中有基于种群的遗传...
  • 启发式算法解TSP问题

    千次阅读 2018-05-30 10:24:03
    从结果可以看出启发式算法的特点,由于是经验算法,结果并不是严格意义上的最优解,因此具有一定的随机性,但只要迭代次数足够多,总可以收敛到最优解附近。 三、遗传算法  遗传算法(GA)是模拟达尔文生物进化论的...
  • 启发式算法(Heuristic Algorithm)

    千次阅读 2019-01-17 10:56:42
    启发式算法(Heuristic Algorithm)有不同的定义:一种定义为,一个基于直观或经验的构造的算法,对优化问题的实例能给出可接受的计算成本(计算时间、占用空间等)内,给出一个近似最优解,该近似解于真实最优解的...
  • 启发式算法是一种技术,这种技术使得在可接受的计算成本内去搜寻最好的解,但不一定能保证所得的可行解和最优解,甚至在多数情况下,无法阐述所得解同最优解的近似程度。 就是说这种算法的全局最优解只是理论上可行...
  • 各种元启发式算法(Metaheuristics)介绍前言一、模拟退火算法(Simulated Annealing)1.二、使用步骤1.引入库2.读入数据总结 前言 元启发式算法能够在一定程度上在全局进行搜索,找到最优解的近似解。元启发式算法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,330
精华内容 1,332
关键字:

启发式变异