人工智能原理实验四：智能算法与机器学习

一、实验目的

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

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 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个城市的坐标进行测试：

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

路径长度是166.541336

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

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

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

3.利用贝叶斯算法和决策树算法进行数据分类操作

数据集：汽车评估数据集(见附录)

实验步骤：

仔细阅读并了解实验数据集；

使用任何一种熟悉的计算机语言(比如C,Java或者matlab)实现朴素贝叶斯算法和决策树算法；

利用朴素贝叶斯算法和决策树算法在训练数据的基础上学习分类器；

利用测试数据对学习的分类器进行性能评估；

统计分析实验结果并上交实验报告；

五、学生实验报告要求

实验报告需要包含以下几个部分

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

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

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

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

# 遗传算法参数
population_size = 50
num_generations = 1000
crossover_rate = 0.8
mutation_rate = 0.02

# 蚁群算法参数设置
num_ants = 10  # 蚂蚁数量，即蚁群规模
pheromone_decay = 0.5  # 信息素挥发系数，控制信息素的挥发速度，取值范围一般在(0, 1)之间
alpha = 1.0  # 信息素的重要程度参数，用于控制蚂蚁选择下一步路径时信息素的影响力
beta = 2.0  # 启发函数（即路径长度）的重要程度参数，用于控制蚂蚁选择下一步路径时路径长度的影响力
Q = 100.0  # 信息素增加强度，表示每次蚂蚁经过一条路径后释放的信息素量
num_iterations = 100  # 蚁群算法迭代次数，即蚂蚁搜索的总轮数

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

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

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

第一次运行结果：最终最佳路径: [11, 5, 6, 10, 9, 7, 8, 3, 2, 4, 30, 29, 28, 26, 27, 25, 24, 23, 22, 21, 17, 20, 18, 19, 14, 15, 13, 12, 16, 1], 距离: 524.0661832365629

第二次运行结果：最终最佳路径: [24, 23, 22, 21, 17, 20, 18, 19, 14, 15, 13, 12, 11, 5, 6, 10, 9, 7, 8, 3, 2, 4, 30, 29, 28, 26, 27, 25, 16, 1], 距离: 529.3772998688348

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

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

较大的种群规模可能会增加算法的运行时间和内存开销，但通常能够更好地探索搜索空间。

五、实验结果讨论。

从实验结果来看，不同的种群规模对算法的性能和结果产生了影响。以下是对实验结果的一些讨论：

1.性能比较：随着种群规模的增加，算法的性能有所提高。这是因为较大的种群规模有助于更好地探索搜索空间，提高全局搜索的能力。然而，这也伴随着更多的计算开销。

2.最佳解决方案：在这个实验中，种群规模为50和100的情况下，最终的最佳解决方案是相同的。这可能是由于算法在较小规模下已经找到了局部最优解，增加种群规模没有进一步改善结果。

3.运行时间：随着种群规模的增加，运行时间也相应增加。较大的种群规模需要更多的计算资源，因此运行时间较长。在实际应用中，需要权衡运行时间和结果质量。

4. 结果稳定性：实验中显示，不同的种群规模下最终的最佳解决方案并不总是一致的。这表明在某些情况下，增加种群规模并不能保证一定能够找到更好的解决方案。这也反映了遗传算法在某些问题上可能受到初始条件和随机性的影响。

3.

朴素贝叶斯算法结果分析：

准确率: 约为 68.5%。该指标表示模型正确分类的样本所占比例。在这个场景下，准确率较低，可能是因为朴素贝叶斯算法对于这个数据集的特征分布假设过于简单，或者数据集中的特征与类别的关系不符合朴素贝叶斯的假设。

精确率: 对于类别 0 和类别 2，精确率分别为 1.00 和 0.68。精确率表示在模型预测为某一类别时，实际为该类别的概率。在这里，类别 0 的精确率较高，说明模型在预测类别 0时的准确性较高。

召回率: 对于类别0、1和类别2，召回率分别为0.02、0.00和1.00。召回率表示实际为某一类别的样本中，模型成功预测为该类别的概率。在这里，类别2的召回率较高，说明模型成功捕捉了该类别的样本。

F1-score: 类别 2 的 F1-score 较高，表示在精确率和召回率之间取得了一种平衡。

决策树算法结果分析：

准确率: 约为 96.8%。相对于朴素贝叶斯，决策树在这个数据集上表现得更好，准确率较高。精确率: 对于所有类别，精确率均较高。说明决策树模型在预测各个类别时的准确性都很高。召回率: 对于所有类别，召回率均较高。说明决策树模型能够成功捕捉各个类别的样本。

F1-score: 各个类别的 F1-score 均较高，表明模型在精确率和召回率之间取得了良好的平衡。

总体而言，决策树模型在这个数据集上的性能明显优于朴素贝叶斯模型。朴素贝叶斯在这里可能过于简化了特征之间的关系，而决策树能够更好地适应数据集的复杂性。

六、程序清单

1.

import numpy as np
import time# 定义城市坐标
cities = {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),11: (58, 69), 12: (54, 62), 13: (51, 67), 14: (37, 84), 15: (41, 94),16: (2, 99), 17: (7, 64), 18: (22, 60), 19: (25, 62), 20: (18, 54),21: (4, 50), 22: (13, 40), 23: (18, 40), 24: (24, 42), 25: (25, 38),26: (41, 26), 27: (45, 21), 28: (44, 35), 29: (58, 35), 30: (62, 32)
}# 城市数量
num_cities = len(cities)# 遗传算法参数
# 不同的种群规模
population_sizes = [20, 50, 100, 200]
num_generations = 1000
crossover_rate = 0.8
mutation_rate = 0.02# 计算两个城市之间的距离
def calculate_distance(city1, city2):return np.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)# 计算整个路径的总距离
def calculate_total_distance(tour):total_distance = 0for i in range(num_cities - 1):total_distance += calculate_distance(cities[tour[i]], cities[tour[i + 1]])total_distance += calculate_distance(cities[tour[-1]], cities[tour[0]])  # 返回起始城市return total_distancefor population_size in population_sizes:print(f"\n测试种群规模 {population_size}\n{'='*20}")# 初始化种群population = [np.random.permutation(num_cities) + 1 for _ in range(population_size)]  # 注意城市编号从1开始start_time = time.time()# 遗传算法主循环for generation in range(num_generations):# 计算种群中每个个体的适应度fitness = [1 / calculate_total_distance(individual) for individual in population]# 使用轮盘赌选择交叉的父母selected_indices = np.random.choice(range(population_size), size=population_size, p=fitness/np.sum(fitness))# 进行交叉操作生成新一代new_population = []for i in range(0, population_size, 2):parent1 = population[selected_indices[i]]parent2 = population[selected_indices[i + 1]]crossover_point = np.random.randint(1, num_cities - 1)child1 = np.concatenate((parent1[:crossover_point], np.setdiff1d(parent2, parent1[:crossover_point])))child2 = np.concatenate((parent2[:crossover_point], np.setdiff1d(parent1, parent2[:crossover_point])))new_population.extend([child1, child2])# 进行变异操作for i in range(population_size):if np.random.rand() < mutation_rate:mutation_indices = np.random.choice(num_cities, size=2, replace=False)new_population[i][mutation_indices[0]], new_population[i][mutation_indices[1]] = (new_population[i][mutation_indices[1]], new_population[i][mutation_indices[0]])# 用新一代替换旧一代population = new_population# 显示每一代中的最佳解决方案best_solution_index = np.argmax(fitness)best_solution = population[best_solution_index]best_distance = calculate_total_distance(best_solution)# print(f"第 {generation + 1}/{num_generations} 代, 最短路径: {best_solution}, 距离: {best_distance}")end_time = time.time()# 显示最终的最佳解决方案final_best_solution_index = np.argmax(fitness)final_best_solution = population[final_best_solution_index]final_best_distance = calculate_total_distance(final_best_solution)print(f"最终最佳解决方案: {final_best_solution}, 距离: {final_best_distance}")print(f"运行时间: {end_time - start_time:.2f}秒\n")

2.

import numpy as np# 定义城市坐标
cities = {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),11: (58, 69), 12: (54, 62), 13: (51, 67), 14: (37, 84), 15: (41, 94),16: (2, 99), 17: (7, 64), 18: (22, 60), 19: (25, 62), 20: (18, 54),21: (4, 50), 22: (13, 40), 23: (18, 40), 24: (24, 42), 25: (25, 38),26: (41, 26), 27: (45, 21), 28: (44, 35), 29: (58, 35), 30: (62, 32)
}
# 城市数量
num_cities = len(cities)
# 蚁群算法参数设置
num_ants = 10  # 蚂蚁数量，即蚁群规模
pheromone_decay = 0.5  # 信息素挥发系数，控制信息素的挥发速度，取值范围一般在(0, 1)之间
alpha = 1.0  # 信息素的重要程度参数，用于控制蚂蚁选择下一步路径时信息素的影响力
beta = 2.0  # 启发函数（即路径长度）的重要程度参数，用于控制蚂蚁选择下一步路径时路径长度的影响力
Q = 100.0  # 信息素增加强度，表示每次蚂蚁经过一条路径后释放的信息素量
num_iterations = 100  # 蚁群算法迭代次数，即蚂蚁搜索的总轮数# 初始化信息素矩阵
pheromone_matrix = np.ones((num_cities, num_cities))
# 计算城市间距离矩阵
distance_matrix = np.zeros((num_cities, num_cities))
for i in range(1, num_cities + 1):for j in range(1, num_cities + 1):distance_matrix[i - 1, j - 1] = np.sqrt((cities[i][0] - cities[j][0])**2 + (cities[i][1] - cities[j][1])**2)
# 主循环
for iteration in range(num_iterations):ant_tours = []# 每只蚂蚁构建路径for ant in range(num_ants):visited_cities = []current_city = np.random.randint(1, num_cities + 1)visited_cities.append(current_city)# 构建路径while len(visited_cities) < num_cities:# 计算选择下一个城市的概率probabilities = []for city in range(1, num_cities + 1):if city not in visited_cities:pheromone = pheromone_matrix[current_city - 1, city - 1]distance = distance_matrix[current_city - 1, city - 1]probability = (pheromone**alpha) * ((1.0 / distance)**beta)probabilities.append((city, probability))# 选择下一个城市selected_city = max(probabilities, key=lambda x: x[1])[0]visited_cities.append(selected_city)current_city = selected_cityant_tours.append(visited_cities)# 更新信息素pheromone_matrix *= pheromone_decayfor tour in ant_tours:for i in range(num_cities - 1):pheromone_matrix[tour[i] - 1, tour[i + 1] - 1] += Q / distance_matrix[tour[i] - 1, tour[i + 1] - 1]# 考虑最后一个城市到第一个城市的信息素更新pheromone_matrix[tour[-1] - 1, tour[0] - 1] += Q / distance_matrix[tour[-1] - 1, tour[0] - 1]# 打印最终的路径
best_tour = max(ant_tours, key=lambda x: sum(distance_matrix[x[i] - 1, x[i + 1] - 1] for i in range(num_cities - 1)))
best_distance = sum(distance_matrix[best_tour[i] - 1, best_tour[i + 1] - 1] for i in range(num_cities - 1))
print(f"最终最佳路径: {best_tour}, 距离: {best_distance}")

3.

mport pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.naive_bayes import MultinomialNB
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score, classification_report
from sklearn.preprocessing import LabelEncoder# 1. 读取数据集
data = pd.read_csv('CarDatas.txt', header=None, delimiter=' ')
# 给数据集添加列名
data.columns = ['buying', 'maint', 'doors', 'persons', 'lug_boot', 'safety', 'class']# 2. 将文本数据转换为数值型数据
label_encoder = LabelEncoder()
data_encoded = data.apply(label_encoder.fit_transform)# 3. 划分训练集和测试集
X = data_encoded.drop('class', axis=1)
y = data_encoded['class']
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)# 4. 朴素贝叶斯算法
nb_classifier = MultinomialNB()
nb_classifier.fit(X_train, y_train)
nb_predictions = nb_classifier.predict(X_test)# 5. 决策树算法
dt_classifier = DecisionTreeClassifier()
dt_classifier.fit(X_train, y_train)
dt_predictions = dt_classifier.predict(X_test)# 6. 性能评估
print("朴素贝叶斯性能评估：")
print("准确率:", accuracy_score(y_test, nb_predictions))
print("分类报告:\n", classification_report(y_test, nb_predictions))print("\n决策树性能评估：")
print("准确率:", accuracy_score(y_test, dt_predictions))
print("分类报告:\n", classification_report(y_test, dt_predictions))