江苏开放大学人工智能导论第二次形考作业

江苏开放大学人工智能导论第二次形考作业 1 农夫过河问题描述的是农夫、狼、⽺、⽩菜如何借助⼀条船过河的问题，有三个限制条件： 1. 只有农夫能开船 2. 船上除了农夫外只能放⼀样物品 3. 没有农夫看管时，狼会吃⽺，⽺会吃⽩菜 在农夫过河问题的状态空间中，⽤四维向量分别表示农夫、狼、⽺、⽩菜的过河状态，1表示已经过 河，0表示未过河，下列哪种状态是不合理的 客观题满分： 5分 A:(0,0,0,0) B:(1,0,1,0) C:(0,0,1,1) D:(1,0,1,1) 正确答案：C:老师点评： 答案解析： (0,0,1,1)表示⽺和⽩菜同时过河，但在农夫过河问题中，农夫不在的情况下，狼会吃⽺，⽺会吃⽩菜，因此(0,0,1,1)是不合理状态。 2 下列有关启发式搜索说法正确的是 客观题满分： 5分 A:启发式搜索不对当前状态优劣做判断 B:盲⽬搜索对当前状态优劣做判断 C:启发式搜索的启发函数代表当前节点到⽬标状态的差距 D:在搜索中添加与问题有关的启发性信息对搜索效率没有提升 正确答案：C:老师点评： 答案解析： 在搜索过程中，盲⽬搜索只判断当前状态是否为⽬标状态，不对当前状态优劣进⾏判断，仅按照固定⽅式搜索，这样的⽅式效率⽐较低；启发函数是启发式搜索的关键，通常可以是当前节点到⽬标状态的某种距离或者是当前节点和⽬标状态的差异程度；启发式搜索在搜索中加⼊了与问题有关的启发性信息，使得机器能够更“聪明”地实现搜索，效率更⾼。 3 下列关于群体智能的特点叙述错误的是 客观题满分： 5分 A:控制是分布式的，不存在中⼼控制 B:群体具有较好的可扩充性 C:群体智能实现⽅便，但具有复杂性 D:群体具有⾃组织性 正确答案：C:老师点评： 答案解析： 群体智能实现⽅便，具有简单性。 4 下列关于群体智能叙述错误的是 客观题满分： 5分 A:群体智能的两个维度包括时间维度和空间维度 B:种群通过代际繁衍，经历千万年的发展，不断进化以适应环境，借鉴物种随时间进化的过程来求解 问题 C:在同⼀时间，种群内的⼤量简单个体在限定条件下通过独⾃运作，使整体种群具有某种适应环境的 能⼒，模拟这种群体⾏为产⽣的智能 D:群体智能的基本思想：模仿⽣物界的进化机理（时间维度）和群体协作（空间维度）⾏为 正确答案：C:老师点评： 答案解析： 在同⼀时间，种群内的⼤量简单个体在限定条件下通过交互协作，使整体种群具有某种适应环境的能⼒，模拟这种群体⾏为产⽣的智能。 5 下列关于粒⼦群算法的叙述错误的是 客观题满分： 5分 A:粒⼦群算法，也称粒⼦群优化算法或⻦群觅⻝算法 B:粒⼦群算法是⼀种基于种群的随机优化技术 C:粒⼦群算法模仿昆⾍、兽群、⻦群和⻥群等的群集⾏为 D:粒⼦群算法不需要利⽤群体中的个体对信息的共享 正确答案：D:老师点评： 答案解析： 粒⼦群算法利⽤群体中的个体对信息的共享使整个群体的运动在问题求解空间中产⽣从⽆序到有序的演化过程，从⽽获得最优解。 6 下列关于搜索技术说法正确的是 客观题满分： 5分 A:搜索技术是实现⼈⼯智能的技术之⼀ B:实现智能的系统不需要搜索技术 C:搜索技术只有在百度、⾕歌这样的搜索引擎中使⽤ D:好的搜索算法能提升系统的⼯作效率 正确答案：A；D:老师点评： 答案解析： 搜索是实现⼈⼯智能的⼀个重要组成部分，它能使机器像⼈⼀样思考；搜索算法的好坏会影响到智能系统的性能和运⾏效率；搜索技术不只在搜索引擎中使⽤，例如在许多下棋的程序中也有使⽤。 7 对于A算法，下列描述正确的是 客观题满分： 5分 A:对于某个确定状态，g(n)和h(n)都是定值 B:对于某个确定状态，g(n)和h(n)都不是定值 C:在A算法中，⽤g(n)和h(n)的和评估当前节点的性能 D:在A算法中，⽤g(n)和h(n)的差评估当前节点的性能 正确答案：A；C:老师点评： 答案解析： 在A算法中当前节点的总代价写为f(n) = g(n) + h(n)，对于某个确定状态，g(n)和h(n)都是定值，⽤两者的和评估当前节点性能，优先遍历性能最佳的节点进⾏求解。 8 在⼋数码游戏中，棋盘是由1到8这8个数字和⼀个空位组成的3*3的阵列，要求通过移动数字，使得该棋局转为标准形式，即数值由⼩到⼤顺时针排列，空位处在正中间。在该游戏中，以下哪 种启发⽅法属于A∗ 算法 客观题满分： 5分 A:当前错位数字的数量 B:错位数字距离⽬标位置的距离的和 C:当前正确数字的数量 D:错位数字距离⽬标位置的距离的差 正确答案：A；B:老师点评： 答案解析： 选项1和选项2的启发函数始终满⾜h(n) ≤ h∗ (n)，因此是A∗ 算法。 9 群体智能的基本原则有5条，其中包括 客观题满分： 5分 A:邻近原则 B:顺序原则 C:多样性反应原则 D:稳定性原则 正确答案：A；C；D:老师点评： 答案解析： 群体智能5条基本原则包括：邻近原则，品质原则，多样性反应原则，稳定性原则，适应性原则。 10 遗传算法对进化论的模拟包括哪些⽅⾯ 客观题满分： 5分 A:种群 B:繁殖 C:突变 D:竞争与选择 正确答案：B；C；D:老师点评： 答案解析： 遗传算法对进化论的模拟包括：物种、物种的⽣存环境、繁殖、突变、竞争与选择。 11 用状态空间搜索法求解农夫、狐狸、鸡、小米问题。农夫、狐狸、鸡、小米都在一条河的左岸，现在要把它们全部送到右岸去，农夫有一条船,过河时，除农夫外，船上至多能载狐狸、鸡和小米中的一样。狐狸要吃鸡，鸡要吃小米，除非农夫在那里。试规划出一个确保全部安全的过河计划。（提示：a.用四元组（农夫、狐狸、鸡、小米）表示状态，其中每个元素都可为0或1，0表示在左岸，1表示在右岸。b.每次过河的一种安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。） 主观题满分： 30分 正确答案：答：用状态空间法进行表示。根据状态空间表示问题的步骤问题求解如下： 第一步定义问题状态的描述形式。 以四元组SK=(1hjm)作为状态变量表示农夫、狐狸、鸡和小米是否在左岸每个元素共有两个取值1或01表示在左岸0表示不在左岸。 第二步用所定义的状态变量把问题的所有可能状态都表示出来并确定出问题的初始状态集和目标状态集。 由于状态变量有4个元素每个元素有2种取值所以共有16种可能状态。各状态的形式描述如下：  问题的初始状态集为：S={S0}={(11l1))目标状态集为：G={S15}={(0000)} 第三步定义一组用于状态变换的算符F。 由于船上除了农夫外每次只能载狐狸、鸡和小米中的一样且每次农夫都必须在船上故定义算符如下： L(fj)表示从左岸将第j样东西送到右岸(j=1表示狐狸j=2表示鸡j=3表示小米j=0表示除农夫外不载任何东西)f表示农夫始终在船上。 R(fj)表示从右岸将第j样东西带回左岸。 所以所定义的算符组F中可能有8种算符： F：L(f0)L(f1)L(f2)L(f3)R(f0)R(f1)R(f2)R(f3) 这里要指出的是操作算符中的厂可以不要也就是说完全可以把操作算符定义成L(j)和R(j)。这里加上f是为了表示农夫总是在船上划船。 至此该问题的状态空间(SFG)构造完成。这就完成了对问题的状态空间表示。 为了求解该问题根据该状态空间的16种状态和8种算符构造它的状态转换图如图2．22所示。  在图2．22所示的状态转换图中每个节点只能取L、R操作之一这取决于状态变量中第一个元素l的取值。若l=1表明农夫在左岸船也就在左岸(因为农夫始终和船相随)这时只能取l操作。若l=0表明船在右岸则只能取尺操作。从初始节点(1111)(状态S0)到目标节点(0000)(状态S15)的任何一条通路都是问题的一个解。其中： L(f2)R(f0)L(f3)R(f2)L(f1)R(f0)L(f3)是算符最少的解之一如图2．23所示。  用状态空间法进行表示。根据状态空间表示问题的步骤,问题求解如下：第一步,定义问题状态的描述形式。以四元组SK=(1,h,j,m)作为状态变量,表示农夫、狐狸、鸡和小米是否在左岸,每个元素共有两个取值1或0,1表示在左岸,0表示不在左岸。第二步,用所定义的状态变量把问题的所有可能状态都表示出来,并确定出问题的初始状态集和目标状态集。由于状态变量有4个元素,每个元素有2种取值,所以共有16种可能状态。各状态的形式描述如下：问题的初始状态集为：S={S0}={(1,1,l,1)),目标状态集为：G={S15}={(0,0,0,0)}第三步,定义一组用于状态变换的算符F。由于船上除了农夫外,每次只能载狐狸、鸡和小米中的一样,且每次农夫都必须在船上,故定义算符如下：L(f,j)表示从左岸将第j样东西送到右岸(j=1表示狐狸,j=2表示鸡,j=3表示小米,j=0表示除农夫外不载任何东西),f表示农夫始终在船上。R(f,j)表示从右岸将第j样东西带回左岸。所以,所定义的算符组F中可能有8种算符：F：L(f,0),L(f,1),L(f,2),L(f,3),R(f,0),R(f,1),R(f,2),R(f,3)这里要指出的是,操作算符中的厂可以不要,也就是说,完全可以把操作算符定义成L(j)和R(j)。这里加上f是为了表示农夫总是在船上划船。至此,该问题的状态空间(S,F,G)构造完成。这就完成了对问题的状态空间表示。为了求解该问题,根据该状态空间的16种状态和8种算符,构造它的状态转换图,如图2．22所示。在图2．22所示的状态转换图中,每个节点只能取L、R操作之一,这取决于状态变量中第一个元素l的取值。若l=1,表明农夫在左岸,船也就在左岸(因为农夫始终和船相随),这时只能取l操作。若l=0,表明船在右岸,则只能取尺操作。从初始节点(1,1,1,1)(状态S0)到目标节点(0,0,0,0)(状态S15)的任何一条通路都是问题的一个解。其中：L(f,2),R(f,0),L(f,3),R(f,2),L(f,1),R(f,0),L(f,3)是算符最少的解之一,如图2．23所示。 老师点评： 12 粒子群算法的参数及选择。 主观题满分： 20分 正确答案：答：粒子群算法，也称粒子群优化算法或鸟群觅食算法，是一种基于种群的随机优化技术。参数包括：群体规模，惯性权重、加速度、最大速度、最大代数。 粒子速度更新公式 v i = ω v i + c 1 r 1 ( p b e s t d − x i ) + c 2 r 2 ( g b e s t d − x i ) v_i = omega v_i + c_1r_1(p_{bestd} – x_i) + c_2r_2(g_{bestd} – x_i) vi=ωvi+c1r1(pbestd−xi)+c2r2(gbestd−xi) 粒子位置更新公式 x i = x i + v i x_i = x_i + v_i xi=xi+vi 其中： ω v i omega v_i ωvi理解为粒子先前的速度和惯性，这是其自身属性的体现； c 1 r 1 ( p b e s t d − x i ) c_1r_1(p_{bestd} – x_i) c1r1(pbestd−xi)是粒子自身的学习性、思考性的体现； c 2 r 2 ( g b e s t d − x i ) c_2r_2(g_{bestd} – x_i) c2r2(gbestd−xi)可以理解为粒子的信息共享、合作等社会性的体现。而其位置计算公式也是表明由于粒子间的相互影响，导致其位置的最终变化。 v i v_i vi 为第 i i i 个粒子的速度 ω omega ω 为惯性因子，其较大时，全局收敛能力较强，局部收敛能力较弱，反之全局收敛能力较弱，局部收敛能力较强。其计算公式为: ω = ω m a x + ( i t e r