图像恢复重建(浙大人工智能导论作业四)
图像恢复重建(浙大人工智能导论作业四)实验思路代码有很多不完善之处，仅供学习参考如果同是NKU2021人工智能导论的同学，可以跳过这篇博客，因为会等到实验截止之后笔者才会将实验的具体代码补全。
实验描述：作业的详细描述移步至：图像恢复重建实验描述截图：
实验中待处理的图片(sample)：生成的噪声图片：局部均值滤波器恢复后的图片：
实验的要求：主要是补写两部分代码：主要噪声及去噪方法的介绍
生成噪声图像:noise_mask_image根据实验给出的noise_ratio描述，noise_ratio[i]分别表示任意一行的像素点的第i个通道受损的数量在该行所有像素点的数量的比例。根据实验描述，可知此方式生成的噪声是属于均匀噪声，在接下来的restore_image中要设计一种算法尽可能来恢复图片
恢复噪声图像：restore_image笔者对于均匀噪声恢复的想法主要还是对于像素点周围区域中有效像素点求均值的方式来进行恢复。此方法比较简陋，会损失一部分图像的细节。对于这种方法，还想了一种改进的措施，即根据区域内有效像素点到中心待恢复点的欧氏距离作为权重，求加权平均值作为待恢复像素点的对应通道的值，但是这种方法好像想过并不明显？对于好几张图片，笔者均值用了两种算法，发现直接求均值的方式反而恢复效果更好。
实验代码：noise_mask_image#在实验截止后笔者在将代码补全defnoise_mask_image(img,noise_ratio=[0.8,0.4,0.6]):"""根据题目要求生成受损图片:paramimg:cv2读取图片,而且通道数顺序为RGB:paramnoise_ratio:噪声比率，类型是List,，内容:[r上的噪声比率,g上的噪声比率,b上的噪声比率]默认值分别是[0.8,0.4,0.6]:return:noise_img受损图片,图像矩阵值0-1之间，数据类型为np.array,数据类型对象(dtype):np.double,图像形状:(height,width,channel),通道(channel)顺序为RGB"""#受损图片初始化noise_img=None#-------------实现受损图像答题区域-----------------ifnoise_ratio[0]人工智能导论——人工智能学科研究的基本内容及主要研究领域
一、人工智能研究的基本内容
（1）知识表示
人工智能研究的目的是要建立一个能模拟人类智能行为的系统，但知识是一切智能行为的基础，因此首先要研究知识表示方法。只有这样才能把只是存储到计算机中去，供求解现实问题使用。知识表示方法可分为两类：符号表示法（用各种包含具体含义的符号以各种不同的方式和顺序组合起来表示知识的方法）和连接机制表示法（用神经网络表示知识）。
（2）机器感知
所谓机器感知就是使机器（计算机）具有类似于人的感知能力，其中以机器视觉和机器听觉为主。机器感知是机器获取外部信息的基本途径。
（3）机器思维
所谓机器思维是指通过感知得来的外部信息及机器内部的各种工作信息进行有目的的处理。
（4）机器学习
机器学习就是研究如何使计算机具有类似于人的学习能力，使它能通过学习自动的获取知识。
（5）机器行为
机器行为主要是指计算机的表达能力，即“说”、“写”、“画”等能力。对于智能机器人，它还应具有人的四肢功能，即能走路、能取物、能操作等。
二、人工智能的主要研究领域
目前，随着智能科学和技术的发展和计算机网络技术的广泛应用，人工智能技术应用到越来越多的领域。下面简要介绍几个主要领域：
（1）自动定理证明
自动定理证明是人工智能中最先进行研究并得到成功应用的一个研究领域，同时它也为人工智能的发展起到了重要的推动作用。实际上，除了数学定理证明以外，医疗诊断、信息检索、问题求解等许多非数学领域问题，都可以转化为定理证明问题。
（2）博弈
诸如下棋、打牌、战争等一类竞争性的智能活动称为博弈(gameplaying)。人工智能研究博弈的目的并不是为了让计算机与人进行下棋、打牌之类的游戏，而是通过对博弈的研究来检验某些人工智能技术是否能实现对人类智慧的模拟，促进人工智能技术的深入研究。
（3）模式识别
模式识别（patternrecognition）是一门研究对象描述和分类方法的学科。分析和识别的模式可以是信号、图象或者普通数据。模式是对一个物体或者某些其他感兴趣实体定量的或者结构的描述，而模式类是指具有某些共同属性的模式集合。
模式识别方法有统计模式识别、结构模式识别、模糊模式识别、神经网络模式识别等。
（4）机器视觉
机器视觉（machinevision）或者计算机视觉（computervision）是用机器代替人眼进行测量和判断，是模式识别研究的一个重要方面。计算机视觉通常分为低层视觉和高层视觉两类。
（5）自然语言理解
自然语言理解（naturallanguageunderstanding）就是研究如何让计算机理解人类自然语言，是人工智能中十分重要的一个研究领域。它是研究能够实现人与计算机之间用自然语言进行通讯的理论与方法。
（6）智能信息检索
数据库系统是存储大量信息的计算机系统。随着计算机应用的发展，存储的信息量越来越大，研究智能信息检索系统具有重要的理论意义和实际应用价值。智能信息检索系统应具有下述功能：能理解自然语言、具有推理能力、系统拥有一定的常识性知识。
（7）数据挖掘与知识发现
知识发现系统通过各种学习方法，自动处理数据库中大量的原始数据，提炼出具有必然性的、有有意义的知识，从而揭示出蕴涵在这些数据背后的内在联系和本质规律，实现知识的自动获取。知识发现是从数据库中发现知识的全过程，而数据挖掘则是这个全过程的一个特定的、关键的步骤，数据挖掘的目的是从数据库中找出有意义的模式。
（8）专家系统
专家系统是一个智能的计算机程序，运用知识和推理步骤来解决只有专家才能解决的疑难问题，是目前人工智能最活跃、最有成效的一个研究领域。可以这样定义，专家系统是一种具有特定领域内大量知识和经验的程序系统，它应用人工智能技术模拟人类专家求解问题的思维过程求解领域内的各种问题，其水平可以达到甚至超过人类专家的水平。
（9）自动程序设计
自动程序设计是将自然语言描述的程序自动转换可执行程序的技术，包括程序综合和程序正确性验证两个方面的内容。
（10）机器人
机器人是指可模拟人类行为的机器。它可分为三代：程序控制机器人（第一代）、自适应机器人（第二代）、智能机器人（第三代）。
（11）组合优化问题
组合优化问题一般是NP完全问题。NP完全问题是指：用目前知道的最好的方法求解，问题求解需要花费的时间（称为问题求解的复杂性）是随问题规模增大以指数关系增长。组合优化问题的求解方法已经应用于生产计划与调度、通信路由调度、交通运输调度等。
（12）人工神经网络
人工神经网络是一个用大量简单处理但愿经广泛连接而组成的人工网络，用来模拟大脑神经系统的结构与功能。
（13）分布式人工智能与多智能体
分布式人工智能（DAI）是分布式计算与人工智能结合的结果。分布式人工智能的研究目标是要建立一种描述自然系统和社会系统的模型。
（14）智能控制
智能控制就是把人工智能技术引入控制领域，建立智能控制系统。
（15）智能仿真
智能仿真就是将人工智能技术引入仿真领域，建立智能仿真系统。
（16）智能CAD
智能CAD就是将人工智能技术引入计算机辅助设计领域，建立智能CAD系统。
（17）智能CAI
智能CAI就是将人工智能技术引入计算机辅助教学领域，简历智能CAI系统即ICAI。
（18）智能管理与智能决策
智能管理就是将人工智能技术引入管理领域，建立智能管理系统，研究如何提高计算机管理系统的智能水平，以及智能管理系统的设计理论、方法和实现方法。智能决策就是将人工智能技术引入决策过程，建立智能决策支持系统。
（19）智能多媒体系统
智能多媒体实际上是人工智能与多媒体技术的有机结合。
（20）智能操作系统
智能操作系统就是将人工智能技术引入计算机的操作系统之中，从质上提高操作系统的性能和效率。
（21）智能计算机系统
智能计算机系统就是人们正在研制的新一代计算机系统，它将全面支持智能应用开发，且自身就具有智能。
（22）智能通信
智能通信就是将人工智能技术引入通信领域，建立智能通信系统，在通信系统的各个层次和环节上实现智能化。
（23）智能网络系统
智能网络系统就是将人工智能技术引入计算机网络系统。
（24）人工生命
人工生命是以计算机为研究工具，模拟自然界的生命现象，生成表现自然生命系统行为特点的仿真系统。
----内容来自于《人工智能导论(第四版)》
人工智能导论——遗传算法求解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