人工智能导论——遗传算法求解TSP问题实验 人工智能导论计算题怎么做的啊

人工智能导论——遗传算法求解TSP问题实验

一、实验目的：

熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传算法求解组合优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。

二、实验原理：

旅行商问题，即TSP问题（TravelingSalesmanProblem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

遗传算法的基本原理是通过作用于染色体上的基因寻找好的染色体来求解问题，它需要对算法所产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会，在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下一代新的种群，对这个新的种群进行下一轮的进化。本实验要求利用遗传算法求解TSP问题的最短路径。

三、实验内容：

1、参考实验系统给出的遗传算法核心代码，要求在相同的种群规模、最大迭代步数、独立运行次数下，用遗传算法求解不同规模（例如10个城市，30个城市，100个城市）的TSP问题，把结果填入表1。

表1遗传算法求解不同规模的TSP问题的结果

城市规模

种群规模

最大迭代步数

独立运行次数

最好适应度

最差适应度

平均适应度

平均运行时间

10

100

100

10

25.1652

25.8521

25.3501

47s

30

100

100

10

10605.7

11868

11281.2

122.8s

100

100

100

10

44334.9

47149.1

46117.6

484.2s

设置种群规模为100，交叉概率为0.8，变异概率为0.8，然后增加1种变异策略（例如相邻两点互换变异、逆转变异或插入变异等）和1种个体选择概率分配策略（例如按线性排序或者按非线性排序分配个体选择概率）用于求解30个城市的TSP问题（30个城市坐标如下），把结果填入表2。

30个城市坐标：

x[0]=41,x[1]=37,x[2]=54,x[3]=25,x[4]=7,x[5]=2,x[6]=68,x[7]=71,x[8]=54,x[9]=83;

y[0]=94,y[1]=84,y[2]=67,y[3]=62,y[4]=64,y[5]=99,y[6]=58,y[7]=44,y[8]=62,y[9]=69;

x[10]=64,x[11]=18,x[12]=22,x[13]=83,x[14]=91,x[15]=25,x[16]=24,x[17]=58,x[18]=71,x[19]=74;

y[10]=60,y[11]=54,y[12]=60,y[13]=46,y[14]=38,y[15]=38,y[16]=42,y[17]=69,y[18]=71,y[19]=78;

x[20]=87,x[21]=18,x[22]=13,x[23]=82,x[24]=62,x[25]=58,x[26]=45,x[27]=41,x[28]=44,x[29]=4;

y[20]=76,y[21]=40,y[22]=40,y[23]=7,y[24]=32,y[25]=35,y[26]=21,y[27]=26,y[28]=35;y[29]=50;

表2不同的变异策略和个体选择概率分配策略的求解结果

变异策略

个体选择概率分配

最大迭代步数

独立运行次数

最好适应度

最差适应度

平均适应度

平均运行时间

两点互换

按适应度比例分配

100

10

889.434

982.154

938.503

59s

两点互换

按线性排序

100

10

488.833

567.304

513.735

51s

相邻两点互换变异

按线性排序

100

10

1022.77

1104.54

1064.78

49.1s

相邻两点互换变异

按适应度比例分配

100

10

878.549

969.802

939.414

58s

3、现给出中国34个省会数据，要求基于此数据设计遗传算法的改进算法解决该TSP问题。要求给出1）改进算法策略及核心代码，2）改进算法的主要参数设置（种群规模、交叉概率、变异概率、最大迭代步数等），3）改进算法最后求得的34个省会的最短路径值、最优个体和算法运行时间，4）给出在相同的参数设置（种群规模、交叉概率、变异概率、最大迭代步数等）下，用基本遗传算法（没有使用改进策略）求得的34个省会的最短路径值、最优个体和算法运行时间。

图1 中国34省会位置(1295.72)

表3 34个省会城市及像素坐标表

城市

西藏

云南

四川

青海

宁夏

甘肃

内蒙古

黑龙江

吉林

辽宁

北京

天津

城市号

1

2

3

4

5

6

7

8

9

10

11

12

X坐标

100

187

201

187

221

202

258

352

346

336

290

297

Y坐标

211

265

214

158

142

165

121

66

85

106

127

135

城市

河北

山东

河南

山西

陕西

安徽

江苏

上海

浙江

江西

湖北

湖南

城市号

13

14

15

16

17

18

19

20

21

22

23

24

X坐标

278

296

274

265

239

302

316

334

325

293

280

271

Y坐标

147

158

177

148

182

203

199

206

215

233

216

238

城市

贵州

广西

广东

福建

海南

澳门

香港

台湾

重庆

新疆

城市号

25

26

27

28

29

30

31

32

33

34

X坐标

221

233

275

322

250

277

286

342

220

104

Y坐标

253

287

285

254

315

293

290

263

226

77

x[0]=100,x[1]=187,x[2]=201,x[3]=187,x[4]=221,x[5]=202,x[6]=258,x[7]=352,x[8]=346,x[9]=336;

y[0]=211,y[1]=265,y[2]=214,y[3]=158,y[4]=142,y[5]=165,y[6]=121,y[7]=66,y[8]=85,y[9]=106;

x[10]=290,x[11]=297,x[12]=278,x[13]=296,x[14]=274,x[15]=265,x[16]=239,x[17]=302,x[18]=316,x[19]=334;

y[10]=127,y[11]=135,y[12]=147,y[13]=158,y[14]=177,y[15]=148,y[16]=182,y[17]=203,y[18]=199,y[19]=206;

x[20]=325,x[21]=293,x[22]=280,x[23]=271,x[24]=221,x[25]=233,x[26]=275,x[27]=322,x[28]=250,x[29]=277;

y[20]=215,y[21]=233,y[22]=216,y[23]=238,y[24]=253,y[25]=287,y[26]=285,y[27]=254,y[28]=315;y[29]=293;

x[30]=286,x[31]=342,x[32]=220,x[33]=104;

y[30]=290,y[31]=263,y[32]=226,y[33]=77;

3.1结果：

3.1.1这边放了两个实验结果，区别仅是初始起点不同

①绘制路径如图2（基于python，起点15）：

图2绘图表示最优解

最短路径长度1532.3994414550848

路径表示：[23,32,24,1,2,0,33,3,5,4,12,14,16,22,21,27,31,30,26,29,28,25,20,19,18,17,13,11,9,8,7,10,6]

路径长度随着迭代次数下降：

图3迭代次数和最优解关系

②绘制路径如图（基于python，起点32）：

图4绘图表示最优解

最短路径长度：1551.0699954694958

路径表示：[1,28,25,24,18,20,19,31,27,29,30,26,23,21,22,16,14,17,13,9,8,7,11,10,12,15,6,4,5,0,33,3,2]

路径长度随着迭代次数下降：

图5最优解和迭代次数关系

3.1.2

若不改进，使用原先的程序，参数设置如下(基于C++)：

染色体长度:34

最大迭代步数:500

种群规模:100

交叉概率:0.5

变异概率0.15

选择操作：按适应度比例分配个体的选择概率，轮盘赌选择个体

交叉操作：PMX交叉

变异操作：相邻两点互换则

结果如图6：

图6结果

最优路径长度为：6246.62

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

运行时间为：214.6s

可见，改进算法还是比较很有效的。

3.2改进算法策略及核心代码：

①参数设定：#种群数

count=300

#改良次数

improve_count=10000

#进化次数

itter_time=3000

#设置强者的定义概率，即种群前30%为强者

retain_rate=0.3

#设置弱者的存活概率

random_select_rate=0.5

#变异率

mutation_rate=0.1

②路径编码：

对城市进行编号0，1，2，3……33，染色体{x1,x2,x3....x33},表示从x1出发，依次经过x2,x3....x33再回到x1的路径，起点可任意设置，本程序中设为15.

③初始化种群：

为了加快程序的运行速度，在初始种群的选取中要选取一些较优秀的个体。先利用经典的近似算法—改良圈算法求得一个较好的初始种群。算法思想是随机生成一个染色体，比如{1，2，……33}，任意交换两城市顺序位置，如果总距离减小，则更新改变染色体，如此重复，直至不能再做修改。

代码：

#初始化种群

population=[]

foriinrange(count):

    #随机生成个体

    x=index.copy()

    random.shuffle(x)

    improve(x)

    population.append(x)

#改良

defimprove(x):

    i=0

    distance=get_total_distance(x)

    whilei

人工智能———贝叶斯公式简单计算题

（1）如下数据集中，计算“温度=热”，“是否适合打网球=是”后验概率；

（2）使用特征独立假设，在如下数据集中，计算P（“是否有风=否”，”天气=晴“，|“是否适合打网球=是”）；

天气(x1)

温度(x2)湿度(x3)是否有风(x4)是否适合打网球（Y）晴热高否否(n)晴热高是否(n)阴热高否是(y)雨温高否是(y)雨凉爽中否是(y)雨凉爽中是否(n)阴凉爽中是是(y)晴温高否否(n)晴凉爽中否是(y)雨温中否是(y)晴温中是是(y)阴温高是是(y)阴热中否是(y)雨温高是否(n)

介绍 ——贝叶斯决策公式：

             

        贝叶斯决策就是在贝叶斯公式计算出后验概率的基础上，进一步做归属的决定——分类。其主要包括两种决策方式，即最小错误贝叶斯决策，和最小风险贝叶斯决策。前者是在比较理想或者各类类别地位均等的情况下的决策，而后者则要考虑决策本身带来的代价和各类别地位的不均等。

        

解：

（1）即求x2={热}时的“是否适合打篮球”的结果为“是”的后检概率：

    根据贝叶斯定理：P(Y=y|X)=P(X1|Y=y)*P(Y=y)*P(x2|Y=y)*P(x3|Y=y)*P(x4|Y=y)*P(Y=y)

    得P(Y=n|X)=P(X1|Y=n)*P(Y=y)*P(x2|Y=n)*P(x3|Y=n)*P(x4|Y=n)*P(Y=n),

        P(Y=y)=9/14,P(x2=热|Y=y)=2/14,

    因此，P(x2=热|Y=y)=2/9

（2）我们知道：P(a,b,c)=P(c)P(a|c)P(b|c)

        在c给定的时候，可得P(a,b|c)=P(a,b,c)/P(c)=P(a|c)P(b|c)

        但在c未知的情况下：

        

    故说特征是条件独立的，而不是独立的。

    由本题知：

        P(x4=否,x2=晴,y=n)=9/14*3/9*6/9=2/14

 

人工智能导论

 1、什么是人工智能？

    关于人工智能的定义有很多。目前，较多的是从计算机学科分支的角度将其理解为利用计算机技术模拟人类智能特征的技术。在哲学上对智能的不同理解，形成了不同的人工智能技术流派及相应的方法。

 2、什么专业的学生应该学习人工智能？

   无论文科、理科，新工科还是传统理工科，理、工、医、管、法、农、商、经、社会、哲学、人文等各专业学生都应该对人工智能有所理解。而不仅仅局限于理工科和人工智能专业学生。非专业、非理工科应对人工智能基本概念、内涵、价值以及其对个体和社会的颠覆性作用有一定或深刻认识。

 3、课程有配套教材吗？

   有的，与本课程配套的最新教材《人工智能导论》已于2020年7月由人民邮电出版社出版。

 4、本课程与其他人工智能导论类课程有什么区别？

   本课程与其他同类课程最大的区别，首先在学习对象上是面向所有专业的学生，不局限于理工科、新工科专业学生；其次，从宇宙大历史、哲学、社会与文明、多学科交叉、工程与技术五个层次来教育学生学习和理解人工智能；最后，本课程内容涵盖了从人工智能基础概念、传统人工智能理论与技术以及前沿人工智能理论与技术，从人工智能思想基础(基本定义、哲学、脑科学)、人工智能技术基础（人工神经网络、机器学习）、机器智能（感知智能、认知智能、行为智能、语言智能、混合智能、类脑计算）、人工智能与社会发展、人工智能伦理与法律五大部分分别讲解人工智能。

人工智能导论(5)——搜索策略(Search Strategy)

文章目录一、概述二、重点内容三、思维导图四、重点知识笔记1.概述1.1基本概念1.2状态空间图表示2.搜索过程及回溯策略3.盲目搜索3.1宽度优先搜索3.1深度优先搜索4.启发式搜索一、概述

人工智能经典三大基本技术为：知识表示、推理、搜索策略。其中搜索直接关系到智能系统的性能与运行效率，搜索技术渗透在各种人工智能系统中。专家系统、自然语言理解、自动程序设计、模式识别、机器学习、信息检索和博弈等领域都广泛使用搜索技术。

为方便记忆和回顾，根据个人学习，总结人工智能基础知识和思维导图形成系列。

二、重点内容基本概念状态空间图表示方法盲目搜索启发式搜索三、思维导图

四、重点知识笔记1.概述1.1基本概念

求解一个问题时，涉及到两个方面：

问题的表示选择一个相对合适的求解方法

问题求解的基本方法：

搜索法归约法归结法推理法产生式

搜索就是找到智能系统的操作序列(如下棋走一步棋)的过程，是一种求解问题的一般方法。

1.2状态空间图表示

概念

人工智能中把描述问题的有向图称为状态空间图，简称状态图。

状态图中的结点代表问题的一种格局，一般称为问题的一个状态；边表示两结点之间操作关系状态2↗操作1╱状态1——操作2——>状态3╲操作3↘状态4

状态空间表示法

状态空间表示法是指用“状态”和“操作”组成的“状态空间”来表示问题求解的一种方法。

（1）状态state

描述问题求解过程中不同时刻下状况的一组变量或数组。

S=[s1,s2,...]

例如：三个硬币的正反面状态

状态1：[正，正，正]状态2：[正，正，反]状态3：[正，反，反]等共8种状态

（2）操作operator

操作表示引起状态变化的一组关系或函数。

例如：上述示例中的，给某个硬币翻面。

（3）状态空间statespace

用状态变量和操作符号，表示系统或问题。

示例：八数空间问题

初始状态：

31257846color{#888}egin{array}{|c|c|c|}hline3&1&2\hline5&&7\hline8&4&6\hlineend{array}358​14​276​​

目标状态：

12384765color{#888}egin{array}{|c|c|c|}hline1&2&3\hline8&&4\hline7&6&5\hlineend{array}187​26​345​​

状态集：数字在表格中的所有排法。

操作算子：空格上移、空格左移、空格下移、空格右移。

2.搜索过程及回溯策略

搜索过程

从初始状态出发不断地、试探性地寻找路径达到目的或者“死胡同”

回溯策略

遇到“死胡同”，就回溯到路径最近的父节点查看该节点是否还有其他子节点若有，沿着子节点继续搜索若无，继续回溯找到目标就成功退出搜索

回溯搜索算法的术语说明

PS(pathstates)表：当前搜索路径的状态。如果找到了目标，PS就是解的路径。NPS(newpathstates)表：新路径状态表。待搜索的状态。NSS(nosolvablestates)表：不可解状态集，即“死胡同”状态表。记录无解的路径，遇到路径上的状态就立即排除。3.盲目搜索

盲目搜索是指在问题的求解过程中，不运用启发性知识，需要进行全方位的搜索，而没有选择最优的搜索途径。这种搜索具有盲目性，效率较低，容易出现“组合爆炸”问题。

典型的盲目搜索有深度优先搜索和广度优先搜索。

3.1宽度优先搜索

宽度优先搜索（Breadth-FirstSearch，BFS）又称为广度优先搜索。

宽度优先搜索是指:

从初始结点S0开始向下逐层搜索：在n层结点未搜索完之前，不进入n+1层搜索

搜索路径示意图如下：

宽度优先搜索的复杂度

时间复杂度度：O(bn)指数空间复杂度度：O(bn)最坏为指数

宽度优先搜索特点

时间空间复杂度都比较高搜索效率低可总可以找到目标节点，而且是最短路径节点3.1深度优先搜索

深度优先搜索（Depth-FirstSearch，DFS）是一种一直向下的搜索策略：

从初始结点S0开始按生成规则生成下一级各子结点逐级“纵向”深入搜索，直至达到目标节点

搜索路径示意图如下：

深度优先搜索的复杂度

时间复杂度度：O(bn)指数空间复杂度度：O(bn)线性

深度优先搜索特点

需要较少的空间（只需要保存搜索树的一部分）可能搜索到了错误的路径（有些问题具有无限的搜索树，可能无法返回正确的路径）最终可能会陷入无限循环，不能给出答案或者找到一个路径很长，且不是最优的答案

有界深度搜索和迭代加深搜索

对于深度比较大的情况，深度优先可能搜索需要很长的运行时间，而且可能得不到解答。一种比较好的问题求解方法是对搜索树的深度进行控制，即有界深度优先搜索方法。

深度优先搜索过程总体上按深度优先算法进行，但对搜索深度需要给出一个深度限制。当深度达到了限制深度时，如果还没有找到解答，就停止对该分支的搜索，换到另一个分支进行搜索。

4.启发式搜索

利用与问题有关的启发信息进行搜索。

在搜索过程中，关键的一步是如何确定下一个要考察的节点，确定方法不同就形成了不同的搜索策略。如果在确定节点时能利用问题的启发信息，估计出节点的重要性，就可以在搜索时选择重要性高的节点。

估价函数

用于估计节点重要性的函数称为估价函数。其一般形式为：

f(x)=g(x)+h(x)f(x)=g(x)+h(x)f(x)=g(x)+h(x)

g(x)g(x)g(x)表示从初始节点到节点x，已经实际付出的代价h(x)h(x)h(x)表示从节点x到目标节点的最优路径的估计代价

八数码问题的多种估价函数

最简单的估价函数：与目标相比，位置不符合的数字数量。较好的估价函数：各数字移动到目的位置所需移动距离的总和。第三种估价函数：对每一对逆转数字乘以一个倍数。第四种估价函数：将位置不符合的数字数目总和与3倍逆转数目相加。

一般启发式图搜索算法（简记为A算法）

待搜索状态表按照f(x)进行排序。

A*算法

最小代价函数：f*(x)=g*(x)+h*(x)f*(x)——从初始状态到目标状态的最小代价g*(x)——从初始状态到x的最小代价h*(x)——从x到目标状态的最小代价估价函数f(x)=g(x)+h(x)如果满足以下条件，称为f*(x)的估价函数g(x)是g*(x)的估计，且g(x)>0h(x)是h*(x)的估计，且有：h(x)≤h*(x)

使用f*(x)的估价函数对待搜索状态表按照f(x)进行排序的算法，称为A*算法。

在A*算法中：

g(x)笔记容易得到，随着更多搜索信息的获得，g(x)的值呈下降趋势h(x)的确定依赖于具体问题领域的启发性信息，其中h(x)≤h*(x)的限制十分重要，它可以保证A*算法都能找到最优解。

个人总结，部分内容进行了简单的处理和归纳，如有谬误，希望大家指出，持续修订更新中。

修订历史版本见：https://github.com/hustlei/AI_Learning_MindMap

人工智能导论课程论文：人工智能及其发展趋势

摘要：人工智能，又简称AI，它是当今最火的一门科学，是研究使计算机来完能表现出人类智能的任务的学科。主要包括计算机实现智能的原理，制造类似于人脑的智能计算机，以及使计算机更巧妙些实现高层次的应用。人工智能科学，它起源于近代，在电气时代随着计算机科学的发展，以及生物学，脑科学等相关科学的发展，极大地推动了人工智能的发展。人工智能还涉及信息论、控制论、自动化、仿生学、生物学，数理逻辑、语言学、心理学等多门学科。导致其非常复杂，所以其研究领域也分成许多方面，从最开始的博弈论，专家系统，模式识别，神经网络，机器学习到现在大热的深度学习。其应用领域，也非常之多，比如机器翻译，语音交互，ORC，图像识别，智能驾驶等等。自从谷歌的阿尔法狗在围棋打败了人类棋手，人工智能也进入了一个新的发展阶段，如今各国，各大公司都在大力发展人工智能技术，争取在新时代把握先机，把握未来。人工智能即将在无人驾驶，机器翻译，语言交互等应用领域取得巨大成功。即使如此，人工智能现在还是处于弱人工智能阶段，人工智能还面临着许多问题和挑战。向强人工智能发展的道路上，仍然充满巨大的困难。

关键词：人工智能