袁 杭, 李林林, 孙良旭, 王 刚, 吴登权, 刘梦迪
(辽宁科技大学 软件学院, 辽宁 鞍山 114051)
人工智能(artificial intelligence,AI) 是研究人类智能模拟和扩展的理论、方法、技术及应用的科学。国内召开的人工智能教育论坛,进一步促进了“人工智能+教育”研究的深入和应用推广,同时也为人工智能向“人工智能+教育”发展提供了技术基础[1]。人工智能辅助教学系统是现代科研的重要成果,是新技术的体现,人工智能技术应用于教育教学,有利于促进学生和教师的发展,促进教育领域方面的改革[2-3]。教育人工智能则是人工智能与学习科学相结合而形成的一个新领域[4]。目前多数院校的计算机编程课程教学还存在着一些问题, 无法满足学生的发展需求[5-7]。国内的学者也提出了新的实验教学方法,例如以建构主义学习理论为依据、参照任务驱动和成就驱动的方法、结合教学过程中的实践经验提出的一种新的分层实验教学方法[8]。虽然在现有的计算机编程类综合性实验中能够体现问题导向、任务驱动等好的实验教学方法,但是问题或者任务本身多是数值计算或者信息管理问题,缺少新颖性和娱乐性,算法难度偏低、业务逻辑简单、技术实现容易,无法达到实践能力训练的工作量和难度要求,而且相关的技术难点可能超过课程现有知识,需要开源项目支持。随着开源项目的大力发展,现在很多项目开发都需要开源项目支持,有必要在实验中训练学生如何使用开源项目解决实际问题。
人工生命计算是一种以人工生命为形式、研究人工生命的信息表达和处理机制、提取相应的计算模型、嵌入相应的计算方法模拟自然界生物进化过程与信息处理机制来求解与优化问题的智能计算方法[9]。本文选择人工智能研究领域新颖有趣的人工生命模拟作为研究问题,设计和实现简单人工鱼模拟综合性实验,具体描述算法理论基础、类库设计和算法实现,为解决计算机编程类课程综合性实验设计问题提供一个新颖的案例参考。
人工生命(artificial life,AL) 首先由计算机科学家Christopher Langton在1987年召开的“生成以及模拟生命系统的国际会议”上提出。人工生命的概念属于计算机科学领域的虚拟生命系统,涉及计算机软件工程与人工智能技术。人工生命是借助计算机实现一个具有生物系统特征的过程或系统,特征主要包括:
(1) 繁殖和死亡。
(2) 进化和选择。
(3) 信息交换和处理。
(4) 决策。
遗传算法(genetic algorithm, GA)是受达尔文进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。将要解决的问题模拟成一个生物进化的过程,通过复制、交叉、突变等操作产生下一代的解,并逐步淘汰适应度低的解,保留适应度高的解。这样进化N代后就很有可能会进化出适应度很高的个体。
遗传算法有3个最基本的操作:选择、交叉、变异。
(1) 选择。选择一些染色体来产生下一代。
(2) 交叉。2条染色体交换部分基因来构造下一代的2条新的染色体。
(3) 变异。在繁殖过程,新产生的染色体中的基因会以一定的概率出错。
BP(back propagation)神经网络是1986年由Rumelhart和McClelland为首的科学家提出的概念[10],是一种按照误差逆向传播算法训练的多层前馈神经网络,是目前应用最广泛的神经网络。
强化学习(reinforcement learning, RL)是近年来机器学习和智能控制领域的主要方法之一,增强学习关注的是智能体如何在环境中采取一系列行为,从而获得最大的累积回报[11]。通过增强学习,一个智能体知道在什么状态下应该采取什么行为。
人工鱼具有自己的神经网络、颜色、大小、移动速度和食物感知器官,每一条人工鱼的染色体包括体质基因和智慧基因。体质基因描述人工鱼的大小、移动速度和颜色特征,采用列表方式描述;智慧基因描述人工鱼的智慧特征,采用神经网络形式表示。移动速度大的人工鱼移动更快,尺寸大的人工鱼需要更多食物,颜色对人工鱼没有影响。通过食物感知器官获取食物与人工鱼之间的角度和距离信息,将这些信息作为神经网络输入。计算神经网络输出、控制人工鱼的朝向和速度、找到食物的位置,循环反复,实现人工鱼在模拟环境中的生存。通过遗传变异、强化学习和适当选择,使人工鱼学习如何找到食物。通过2条人工鱼的染色体之间配对,产生变异的后代。
人工鱼相关类包括Fish类、FishChromozomes类和FishLearn类。类的字段和方法定义如图1所示。
图1 人工鱼相关类定义
Fish类定义了人工鱼的基本信息、位置信息、智慧能力和生存行为。基本消息包括年龄、大小、生命力、移动速度、染色体、吃食量;位置信息包括坐标位置、头和身体朝向;智慧能力包括神经网络、食物感知、自我学习;生存行为包括搜索食物、吃食、前进、边界检测。
FishChromozomes类在基因类和染色体类定义基础上,定义了人工鱼的体质染色体、智慧染色体和繁殖交配行为。
FishLearn类定义了人工鱼的觅食学习。
食物相关类包括Food类、FoodSensor类和FoodGnerator类,类的字段和方法定义如图2所示。
图2 食物相关类定义
Food类定义食物的基本信息,包括坐标位置和提供的生命力。
FoodSensor类根据人工鱼和食物之间角度和距离信息,定义了食物感知计算的功能。
FoodGenerator类定义了随机在不同位置生产食物的功能。
2.3.1 人工鱼觅食强化学习
设计人工鱼具有短期记忆,通过队列可以保存最近的n个行为。当成功搜索到食物后,使用这n个行为对其神经网络进行训练,以使其更好地按照上述n个行为进行食物搜索,这就是人工鱼的觅食强化学习过程。在仿真过程中,由于觅食强化学习,每条人工鱼的神经网络将发生连续不断的变化,描述人工鱼最新的觅食行为。
2.3.2 人工鱼繁殖遗传处理
人工鱼的基因存在概率突变,当2条人工鱼进行繁殖时,他们的基因会进行合并和组合,产生一个具有不同基因特征的新个体。在仿真生存环境中,如果人工鱼吃到食物,生命力会增加,说明其具有更好的觅食能力,生存环境适应度更好;如果人工鱼没有吃到食物,生命力会持续下降,说明其具有较差的觅食能力,生存环境的适应度较差。通过定义每代人工鱼的繁殖阈值条件,例如定时器,选择觅食能力强、生存环境适应度好的人工鱼进行繁殖交配,产生新的个体,实现人工鱼进化。由于每一条人工鱼的神经网络都是不同的,所以它们的后代将具有唯一的神经网络,具有不同的觅食行为。
对于使用普通列表描述的体质基因,根据列表长度随机选择一个交叉点,按照交叉点,将2个基因列表在交叉点两个相反方向上分别进行拷贝,如图3所示。
图3 体质基因遗传处理
人工鱼繁殖交配时,对使用神经网络描述的智慧基因,选择一个交叉点将2条人工鱼的神经网络进行遗传处理,如图4所示。
图4 智慧基因遗传处理
为了能够最大限度遗传有利生存的基因到下一代,一般选择从多条好的人工鱼中选择2条进行繁殖交配,产生后代。
2.3.3 人工鱼生存模拟
在人工鱼生存模拟中,一开始固定数量的食物随机在不同位置生成,一旦食物被人工鱼吃掉,都会自动重新在另一个随机位置生成。人工鱼彼此之间默认是不可见的,但是在任何时候都可以感知所有的食物信息。每条人工鱼获取的食物感知信息经过计算,作为其神经网络输入,获取神经网络输出,计算鱼头的朝向和前进速度,执行觅食行为。每条人工鱼根据觅食情况,处于健康生长或者逐渐死亡的状态。当每代进化阈值条件满足时,选择好的人工鱼进行繁殖交配,产生下一代人工鱼群,完成下一代生存模拟。
人工鱼综合性实验可以在Visual Studio 2015开发环境中使用C#编程实现,其中人工鱼生存环境的图形化动态界面可以使用WPF的Canvas类编程绘制完成,使用Background Worker类实现人工鱼的多线程生存模拟,通过人工鱼、食物、边界之间坐标关系的几何计算,获取人工鱼的食物感知信息,包括距离和角度,作为人工鱼神经网络输入。
由于学生普遍缺乏神经网络和增强学习相关算法的理论知识,直接通过编写代码实现上述算法非常困难。为了解决该问题,利用开源项目Neural Networks,该项目提供了基于.NET Framework的并行神经网络库实现,其中Backpropagation Network类实现BP神经网络,可以用于实现人工鱼的强化学习。
因此,人工鱼智慧基因使用开源项目Neural Networks的Backpropagation Network类来实现BP神经网络,获取食物感知信息作为输入,完成人工鱼觅食行为决策,最近n个行为作为输入输出,完成人工鱼觅食行为学习。
人工鱼综合性实验的实现程序运行效果如图5所示。
图5 人工鱼生存模拟
一开始人工鱼几乎不知道如何找到食物,有些鱼在不停地打转。逐渐地,经过多代进化,人工鱼逐渐获得了吃到更多食物的行为。种群中适应度可以描述为人工鱼消耗的总食物量,随着进化代数持续增加,通过优势个体的基因遗传,成功地产生了觅食能力更强的个体,能够找到更多的食物,程序模拟的效果与现实中的鱼群生存过程一致。
本文针对计算机编程类课程缺乏新颖有趣的综合性实验问题,选择人工智能的人工生命作为问题背景,以人工鱼生存模拟为例,详细描述了该综合性实验的理论基础、实验设计和编程实现过程。该综合性实验完全可以满足计算机编程类课程对学生基础语法、数据结构和算法的训练,具有一定的技术难度,又不失趣味性,同时让学生了解了利用开源项目解决实际问题的方式,为解决目前计算机编程类课程综合性实验中存在的问题提供了一个新颖的解决方案。