算法设计课程中的智能优化算法教学

摘 要 ：算法设计课程是计算机专业专科生选修课程,智能优化算法是其中的重要内容.针对智能优化算法中知识点抽象和学生难以理解的现状,提出将多种教学方法和手段运用到实际教学中,进一步优化教学效果和加强教学改革的观点.

关 键 词 ：算法设计；智能优化算法；教学方法

0 引言

培养高素质和创新型人才是各高等学校教育改革的重点.专科学校在人才培养上以学生就业为重点,着重培养学生的一技之长,学生对与专业相关的其他知识涉及不多.毕业生反馈虽然这种培养方式可以让学生很快找到工作并投入到实际工作中,但是在校所学知识的单一化导致工作的层次较低,工作面比较窄.适当增加和本专业相关的知识,拓宽学生的知识面,增强学生的就业能力,培养高素质人才是学校进行教学改革的目的.算法设计课程是计算机专业本科学生的必修课程,对于这门课程,专科学生理解起来比较困难,因此学校将其作为选修课程.这门课程的重点内容是什么,讲解的深度如何把握,都需要教师在实际教学过程中进行探讨.

1.选择重点教学内容

算法设计这门课程涉及的领域非常宽泛,通常包括的内容有基本和经典的算法,算法设计策略、问题复杂性等方面的理论研究,以及近年来在并行算法、随机算法、近似算法、加密算法、智能优化算法、模式识别算法等算法领域方面的最新研究成果.

智能优化算法是当今算法领域比较热门和应用比较广泛的算法之一.它又称为现代启发式算法,是一种具有全局优化性能、通用性强且适合并行处理的算法.这种算法一般具有严密的理论依据,从理论上讲可以在一定的时间内找到最优解或近似最优解.智能优化算法在实际中应用广泛,因此教师在算法设计课程中有必要将这部分内容介绍给学生.

1.1 常见的智能优化算法

1.1.1 遗传算法

遗传算法（Geic Algorithm,GA）是一类借鉴生物界的进化规律（适者生存,优胜劣汰遗传机制）演化而来的随机化搜索方法,由美国J·Holland教授于1975年首先提出.遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域.它是现代有关智能计算中的关键技术.

1.1.2 蚁群算法

蚁群算法（Ant Colony Optimization,ACO）,又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法.它由Marco Dorigo于1992年在博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为.蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.

1.1.3 模拟退火算法

模拟退火算法（Simulated Annealing,SA）最早由Kirkpatrick等应用于组合优化领域,是基于Mente-Carlo迭代求解策略的一种随机寻优算法,出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性.模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即能从局部最优解概率性地跳出并最终趋于全局最优.模拟退火算法是一种通用的优化算法,从理论上讲具有概率的全局优化性能,目前已在工程中得到广泛应用,诸如VLSI、生产调度、控制工程、机器学习、神经网絡、信号处理等领域.

1.2 智能优化算法特点与优势

遗传算法的主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定,具有内在的隐并行性和更好的全局寻优能力.它采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,而不需要确定的规则.

蚁群算法有别于传统编程模式,优势在于避免编写冗长的程序,程序本身是基于一定规则的随机运行来寻找最佳配置.也就是说,当程序最开始找到目标的时候,路径几乎不可能是最优的,甚至可能包含无数错误的选择.但是,程序可以通过蚂蚁寻找食物时候的信息素原理,不断地修正原来的路线,使整个路线越来越短,即程序执行的时间越长,所获得的路径就越可能接近最优路径.

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性,从而有效避免陷入局部极小并最终趋于全局最优的串行结构优化算法.

这3种算法的共同特点是从任一解出发,按照某种机制,以一定的概率在整个求解空间中探索最优解.由于它们可以把搜索空间扩展到整个问题空间,因而具有全局优化性能.

2.采用多种教学方法

从培养高素质计算机人才的需求出发,以拓宽学生知识面及提高学生实践能力为目标,针对智能优化算法这部分知识内容,授课教师可以采用多种教学方法和手段,充分发挥学生学习的潜能和积极性,改善课堂教学气氛,提高教学效果.

2.1 案例教学

案例教学是一种通过模拟或者重现现实生活中的一些场景,让学生把自己纳入案例场景,通过讨论或者研讨进行学习的一种教学方法.教学中既可以通过分析和比较,研究各种各样的成功和失败的案例,从中抽象出一般性的结论或原理,又可以让学生通过自己的思考或者他人的思考拓宽自己的视野,从而丰富自己的知识.

在教学过程中,教师可以通过实际生活中的一个案例帮助学生提升对算法的学习兴趣.如旅行商问题,检测设有一个旅行商人要拜访n个城市,他必须选择要走的路径,限制条件是每个城市只能拜访一次,而且最后要回到原来出发的城市.路径的选择目标是要求所得的路径长度为所有路径之中的最小值.

学生通过自己思考,再经过小组讨论,通常都会得出这样一个最容易想到的方法：利用排列组合的方法把所有路径都计算出来并逐一比较,选出最小路径.教师可以根据这个结论,引导学生明确虽然该方法在理论上是可行的,但路径的个数等于n!.当城市个数较大时,该方法的求解时间是难以忍受的,甚至是不可能完成的.例如,当包含20个城市时,20!等于2432902 008 176 640 000,以每秒1亿次的计算速度来估算,求解时间长达700多年.因此,学生认为旅行商问题的全局最优解是无法确定的,只可能得到近似最优解.这样,这类问题追求的目标就变成以尽可能短的时间求得质量尽可能好的近似解,自然地引导出模拟退火算法,从而为介绍该算法作了有序的铺垫. 2.2 多媒体演示教学

多媒体教学是指在教学过程中,根据教学目标和教学对象的特点,通过教学设计合理选择和运用现代教学媒体,并与传统教学手段有机组合,共同参与教学全过程,以多种媒体信息作用于学生,形成合理的教学过程结构,达到最优化的教学效果.

例如,教师在讲解蚁群优化算法时,学生对该算法理论知识的理解还不是很深刻,不能在头脑里形成对该算法的形象认知.教师可以利用多媒体课件向学生演示自然蚁群的生态行动,加强学生对这种算法的理解.

2.3 网絡远程教学

网絡远程教学是一种相对于面授教育的师生分离和非面对面组织的教学活动,它的特点是学生与教师分离,学习的场所和形式灵活多变.与面授教育相比,它的优势在于能够提供更多的学习机会,提高教学质量,降低教学成本.

针对学生在课堂上对知识点理解不深刻的现状,教师可以通过建立网站或个人网页设立教学园地,提供教学辅助软件下载,设计一些有关算法的动态演示,展示最新成果,与学生交流讨论并解答学生的问题.

3.教学实践应用及效果

在教学实践中,教师可以采用一些实例说明问题,如在讲解蚁群算法时介绍经典的TSP源程序,在课堂上改变相应的参数并进行调试,同时绘制出最优路径上信息素的变化曲线.教师在讲解过程中可以由简入深,还可以采用学校现有考试系统中的自动组卷功能,对比介绍遗传算法和模拟退火算法的特点.遗传算法的局部搜索能力差,但对搜索过程的总体把握能力强；模拟退火算法具有较强的局部搜索能力,但对整个搜索空间的状况掌控能力不强.因此,学校考试系统自动组卷功能的开发实现应结合2种算法的长处.教师采用对比方法进行讲解,可以使学生更容易理解2种算法的特点.

以上多种教学方法和实例的应用讲解,大大提高了学生对这部分知识的学习兴趣,增强学生主动参与课堂教学的积极性,使本来枯燥和复杂的算法问题也变得更加直观,有效地提高了教学效率.

4.结语

智能优化算法作为专科学校计算机专业的选修课程内容,教学内容侧重点需要任课教师认真讨论和挑选.针对智能优化算法的教学方法可以采用案例教学、多媒体演示教学、网絡远程教学等方法,以使学生快速掌握设计思想,提高知识层次,拓宽知识面.

（编辑：宋文婷）