广州大学人工智能原理实验四-智能算法与机器学习

广州大学学生实验报告

开课学院及实验室: 计算机科学与网络工程学院电子信息楼416 2023年12月21日

学院	计算机科学与网络工程学院	年级/专业/班	****	姓名	*****	学号	*****
实验课程名称	人工智能原理实验					成绩
实验项目名称	智能算法与机器学习					指导老师	****

实验四智能算法与机器学习

一、实验目的

本实验课程是计算机、智能、物联网等专业学生的一门专业课程，通过实验，帮助学生更好地掌握人工智能相关概念、技术、原理、应用等；通过实验提高学生编写实验报告、总结实验结果的能力；使学生对智能程序、智能算法等有比较深入的认识。要掌握的知识点如下：

1、掌握人工智能中涉及的相关概念、算法；

2、熟悉人工智能中的知识表示方法；

3、掌握问题表示、求解及编程实现；

4、熟悉和掌握遗传算法、蚁群算法、决策树、贝叶斯等的基本概念和基本思想；

5、能够用选定的编程语言设计简单的算法系统；

6、通过实验培养学生利用智能算法和机器学习算法进行问题求解的基本技能。

二、基本要求

1、实验前，复习《人工智能》课程中的有关内容。

2、准备好实验数据。

3、程序可以组队完成（实验报告上要标明自己完成部分，切勿提交一样的报告），程序应加适当的注释。

4、完成实验报告，由小组完成报告要有明显区别，分析和总结应该按照自己完成的部分进行。

三、实验软件

推荐使用C或C++（Visual studio等平台）（不限制语言使用，如Java，matlab，Python等都可以）。

四、实验内容

1、以N个节点的TSP（旅行商问题）问题为例，应用遗传算法进行求解，求出问题的最优解。

【问题描述】

旅行商问题（Traveling Salesman Problem, TSP），又译为旅行推销员问题、货担郎问题，简称为TSP问题，是最基本的路线问题。假设有n个可直达的城市，一销售商从其中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。

TSP问题是组合数学中一个古老而又困难的问题，也是一个典型的组合优化问题，现已归入NP完备问题类。NP问题用穷举法不能在有效时间内求解，所以只能使用启发式搜索。遗传算法是求解此类问题比较实用、有效的方法之一。

下面给出30个城市的位置信息：

表1 Oliver TSP问题的30个城市位置坐标

城市编号	坐标	城市编号	坐标	城市编号	坐标
1	(87，7)	11	(58，69)	21	(4，50)
2	(91，38)	12	(54，62)	22	(13，40)
3	(83，46)	13	(51，67)	23	(18，40)
4	(71，44)	14	(37，84)	24	(24，42)
5	(64，60)	15	(41，94)	25	(25，38)
6	(68，58)	16	(2，99)	26	(41，26)
7	(83，69)	17	(7，64)	27	(45，21)
8	(87，76)	18	(22，60)	28	(44，35)
9	(74，78)	19	(25，62)	29	(58，35)
10	(71，71)	20	(18，54)	30	(62，32)

最优路径为：1 2 3 4 6 5 7 8 9 10 11 12 13 14 15 16 17 19 18 20 21 22 23 24 25 28 26 27 29 30

其路径长度为：424.869292

也可取前10个城市的坐标进行测试：

表2 Oliver TSP问题的10个城市位置坐标

城市编号	坐标
1	(87，7)
2	(91，38)
3	(83，46)
4	(71，44)
5	(64，60)
6	(68，58)
7	(83，69)
8	(87，76)
9	(74，78)
10	(71，71)

有人求得的最优路径为： 0 3 5 4 9 8 7 6 2 1 0

路径长度为：166.541336

上述10个城市的求解中编号从0开始，把所有路径搜索完又返回到出发节点。

应用遗传算法求解30/10个节点的TSP（旅行商问题）问题，求问题的最优解。

2、使用蚁群优化算法或者粒群优化算法求解以上TSP问题。

五、学生实验报告要求

（1）求出问题最优解，若得不出最优解，请分析原因；

广州大学人工智能原理实验四-智能算法与机器学习

最优解 : 路径总和是425.869

对实验中的几个算法控制参数进行仔细定义，并能通过实验选择参数的最佳值；

广州大学人工智能原理实验四-智能算法与机器学习

要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。

广州大学人工智能原理实验四-智能算法与机器学习

测试种群规模对算法结果的影响。（运算速度，内存空间，准确率等）

我设定了50个城市, 随机生成他们的坐标, 使用遗传算法解决50个城市tsp问题

父代基因串200个 :

广州大学人工智能原理实验四-智能算法与机器学习

父代基因串150个 :

广州大学人工智能原理实验四-智能算法与机器学习

父代基因串100个 :

广州大学人工智能原理实验四-智能算法与机器学习

父代基因串50个:

广州大学人工智能原理实验四-智能算法与机器学习

结论 : 随着父代基因串数目即种群的规模减少, 路径总和变大, 说明距离最优解越来越远. 反之, 种群规模越大, 越能找到较好的解.

测试算法中重要参数（如遗传算法中的交叉概率、变异概率）对算法结果的影响（运算速度，内存空间，准确率等），以表格或者曲线图等形式表达。

广州大学人工智能原理实验四-智能算法与机器学习

实验完整代码

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair pii;
map points;
vector<vector> matrix;  // 父代基因
vector<vector> matrix400;  // 父代基因*2
vector cost(400);  // 每一条基因串的路径总和
vector ansList;  // 最优结果的list
const int geneCount = 200;  // 基因数目
int cityCount = 10;  // 城市数目
double crossRate = 50;                     // 交叉率
double mutationRate = 50; // 变异率
double ans = 0x3f3f3f;  // 最短路径

/**
 * @brief 初始化 ： 点位坐标
 *
 * @return
 */
void initPoint() {
    points[1] = { 87, 7 };
    points[2] = { 91, 38 };
    points[3] = { 83, 46 };
    points[4] = { 71, 44 };
    points[5] = { 64, 60 };
    points[6] = { 68, 58 };
    points[7] = { 83, 69 };
    points[8] = { 87, 76 };
    points[9] = { 74, 78 };
    points[10] = { 71, 71 };
    
    
    points[11] = {58, 69};
    points[12] = {54, 62};
    points[13] = {51, 67};
    points[14] = {37, 84};
    points[15] = {41, 94};
    points[16] = {2, 99};
    points[17] = {7, 64};
    points[18] = {22, 60};
    points[19] = {25, 62};
    points[20] = {18, 54};
    
    points[21] = {4,50};
    points[22] = {13,40};
    points[23] = {18,40};
    points[24] = {24,42};
    points[25] = {25,38};
    points[26] = {41,26};
    points[27] = {45,21};
    points[28] = {44,35};
    points[29] = {58,35};
    points[30] = {62,32};
}

/**
 * @brief 生成一条基因串
 *
 * @return
 */
vector list0;
bool st[50];
void generateList() {
    // 父代基于数目已经足够
    if (matrix.size() == geneCount) {
        return;
    }
    // 单条基因
    if ((int)list0.size() >= cityCount) {
        auto ver = list0;
        ver.push_back(1);
        matrix.push_back(ver);
        return;
    }
    for (int i = 2; i <= cityCount; i++) {
        if (!st[i]) {
            list0.push_back(i);
            st[i] = true;
            generateList();
            list0.pop_back();
            st[i] = false;
        }
    }
}




/**
 * @brief 生成父代基因
 */
void generate() {
    list0.push_back(1);
    generateList();
    cout << matrix.size() << endl;
    for (int i = 0; i < (int)matrix.size(); i++) {
        for (int j = 0; j <= cityCount; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

/**
 * @brief 交叉
 */
void crossover () {
    int index = rand() % cityCount; // 交叉的点
    
    int ii = 0, jj = 0;
    while (ii == jj)
    {
        ii = rand() % geneCount;
        jj = rand() % geneCount; // 交叉的两个串
    }
    
    auto list1 = matrix[ii], list2 = matrix[jj];
    
    /**
     * 把list1中的【1， index】的拼接到list2的后面
     */
    unordered_set st;
    for (int i = 1; i <= index; i++)
    {
        st.insert(list1[i]);
    }
    
    // 把原来的删掉， 然后拼接上去
    vector newList;
    for (auto x : list2) {
        if(!st.count(x)) {
            newList.push_back(x);
        }
    }
    
    // 拼接
    newList.pop_back(); // 把最后的1移走, 后面再拼接上去
    for (auto x : st) {
        newList.push_back(x);
    }
    newList.push_back(1);
    
    // 添加到400个串中
    matrix400.push_back(newList);
}


/**
 * 变异
 */
void mutation()
{
    // 变异的点的下标
    // srand(time(0));
    int idx = -1;
    while (!(idx > 0 && idx < cityCount - 1))
        idx = rand() % cityCount;
    
    // 变异的基因
    int ii = rand() % geneCount;
    auto list = matrix[ii];
    

    // 交换位置
    swap(list[idx], list[idx + 1]);

    
    matrix400.push_back(list);

}

/**
 * @brief 计算两个城市之间的距离
 * 
 * @param x 
 * @param y 
 */
double getDist(int x, int y) {
    auto [a, b] = points[x];
    auto [c, d] = points[y];
    double distance = sqrt(pow(a - c, 2) + pow(b - d, 2));
    return distance;
}

/**
 * 适应度计算 : 就是路程的计算
 */
void fitness()
{
    
    // 计算400个子代的cost值
    for (int i = 0; i < geneCount * 2; i++)
    {
        
        vector ver = matrix400[i];
        double sum = 0;
        for (int j = 0; j < cityCount; j++)
        {
            int x = matrix400[i][j];
            int y = matrix400[i][j + 1];
            sum += getDist(x, y);
        }
        
        cost[i] = sum; // 赋值
        
        // 保存最优解
        if (cost[i] - ans < 1e-8)
        {
            ansList = ver;
            ans = cost[i];
        }
    }
    
    // 排序 : 冒泡排序
    for (int i = 0; i < geneCount * 2 - 1; i++)
    {
        for (int j = 0; j  1e-8)
            {
//                int t = cost[j]; // 注意 ： 这里的是double
                double t = cost[j];
                auto ver = matrix400[j];
                
                cost[j] = cost[j + 1];
                matrix400[j] = matrix400[j + 1];
                
                cost[j + 1] = t;
                matrix400[j + 1] = ver;
            }
        }
    }
    
    // 排序完之后， 取400个中的前200个
    for (int i = 0; i < geneCount; i++)
    {
        matrix[i] = matrix400[i];
    }
}


void iteration() {
    auto matrix_tmp = matrix;
    while (1)
    {
        matrix = matrix_tmp;
        ans = 1e6;
        int T; // 迭代次数
        cout << endl;
        cout << "请输入要迭代的次数 T" <> T;
        int T2 = T;
        while (T--)
        {
            matrix400 = matrix;
            // cout << "T" << endl;
            while (matrix400.size() < geneCount * 2)
            {
                int x = rand() % 100 + 1;
                // 交叉
                if (x <= crossRate)
                {
                    crossover();
                }
                // 变异
                else
                {
                    mutation();
                }
            }
            fitness();
            cout << "第" << (T2 - T) << "次迭代 : " << cost[0] << endl;
        }
        cout << "最优的基因串是 : ";
        for (auto x : ansList)
            cout << x << ' ';
        cout << endl;
        cout << "最短路径是: " << ans << endl;
    }
}
int main() {
    srand(time(0));
    cout <>>" << endl;
    initPoint();
    cityCount = points.size();
    generate();
    iteration();
}