针对本科生的演化算法教学

摘 要：演化算法是一种自然启发式全局优化算法,其鲁棒性、高效性、全局搜索能力和隐并行性好等特点,使其成为计算机领域的一个研究热点.为了能使本科生对演化计算方法有所了解,并对今后的工作或研究生学习有所帮助,有必要为计算机专业的本科生开设演化计算课程.文章结合在本科生教学中的心得,对如何开展本科生演化算法教学进行了探讨.

关 键 词：演化算法；本科生教育；教学方法；全局优化

中图分类号：G728文献标志码：A文章编号：1006-8228(2012)07-65-02

0引言

20世纪80年代中期以来,演化算法(EvolutionaryAlgorithms)已成为计算机领域的一大研究热点[1-2].近30年来,在演化算法中研究学者提出了多种算法,主要包括遗传算法(GeicAlgorithms)、演化策略(EvolutionStrategies)、进化规划(EvolutionaryProgramming)、遗传编程(GeicProgramming)等[3].

演化算法作为一种新兴的优化技术,在计算机研究和应用领域受到了广泛关注.作为一门研究型课程,结合我校计算机学院的特色,我校为计算机科学与技术专业大四学生开设了演化算法课程,笔者承担该课程的教学研讨工作.结合笔者的教学经验,认为为本科生开设演化算法课程十分有必要,这对于培养本科生的科研素养和创新能力[4-5]具有很重要的帮助.下面将结合笔者在本科生教学中的心得,对如何开展本科生演化算法教学进行初步探讨,以起到抛砖引玉作用.

1演化算法简介

作为一种优化算法,演化算法对所优化的问题具有广泛的适用性,不像经典优化算法需要所优化的问题具有可导、连续、单峰等特点.近年来,演化算法已广泛应用到各种领域,如：工程优化设计、运筹学、图像处理、地学工程、经济领域、电力负荷分配等[1].

演化算法求解问题的基本思想受到生物演化的启发,主要包括复制(reproduction)、变异(mutation)、重组(rebination)和选择(selection)等步骤,其基本思路为：由问题的候选解组成一个群体,然后通过随机变异,重组和选择等算子对群体进行演化,其中随机变异和重组算子提供了发现新解的机制,选择算子则确定保持哪些解作为下一步搜索的基础.演化算法的基本框架如图1所示.

演化算法具有以下几个优点：①以优化变量的遗传编码为运算、搜索对象,不仅可以用于优化数值优化问题,还可用于优化非数值优化问题；②只利用“适应值”信息,而不需利用目标函数的具体值及其他辅助信息,如连续、可导、平滑、无噪音等,从而使得演化算法可以应用于多种优化问题中；③非单点操作,使用群体搜索策略.这使得算法可以进行并行搜索,并且可以一次优化得到多个优化结果,特别适合于进行多目标优化决策；④使用随机搜索机制.随机搜索机制的一个优点是相应算法的健壮性(robustness)得到增强.总的来说,演化算法具有通用、并行、稳健、简单和全局优化能力强等突出优点.

2针对本科生的教学

2.1教学目的

我校计算机学院为本科生开设演化算法课程始于2003年,当时由我院已故康立山教授亲自为本科生授课,效果很好,为本科生打开了学术科研之门.

演化算法是一种基于生物界“优胜劣汰”进化机制的优化算法,该算法已经成功应用于多个领域.同时,演化算法中还存在许多亟待解决的问题,以使算法的求解能力更强,鲁棒性更好.本课程主要针对计算机专业和相关专业高年级本科生而开设,课程重点对演化算法的机制,不同算法的特点,以及演化算法在不同优化问题的求解进行讲解,旨在增强学生对演化算法的了解,同时为今后深造或在工作中应用算法和对算法进行进一步的改进研究.

针对本科生开设演化算法课程,与针对研究生所开设的演化算法课程目的不同.对于本科生我们的目标是提高学生兴趣和介绍当前演化算法的研究前沿.以期通过本课程学习,使学生对演化算法的发展概况、基本原理和应用领域有初步了解；对主要技术及应用有一定掌握；通过启发式授课培养学生对演化算法的兴趣,培养他们的知识创新和技术创新能力.为此,我校开设的演化算法课程主要包括课堂教学和实践教学两部分,分别为28课时和12课时.

2.2基于实例的算法演示教学

为了能够提高学生学习演化算法课程的兴趣,并培养学生的科技创新能力,演化算法教学应以实例教学为主,通过演化算法中所涉及的针对实际问题的求解进行演示教学,给学生以直观的感受.比如在讲解函数优化问题时,可以使用VC++和Matlab混合编程设计好的演示软件,利用Matlab软件绘制出优化函数的3D图形,然后动态显示演化算法群体中的个体搜索最优解的过程,并以此讲解群体初始化、父体选择、杂交、变异、生存选择的演化操作,使学生加深对利用演化算法求解函数优化问题的认识和理解.讲解利用演化算法求解离散优化问题时,可以选择经典TSP问题作为实例讲解.教学中,以TSP的实际应用问题为例,演示演化算法在求解该类问题时的过程,比如,利用演化算法优化属于TSP问题的动态卫星最短通讯距离问题、大规模集成电路板焊接点问题等.

2.3教学实践

在针对本科生进行演化算法教学时,一个必然会遇到的问题是,如何使学生能够自己编写演化算法的程序.这需要在实践教学中对学生进行示例和引导[6].实践教学对提高本科生的实际动手能力有着极为重要的作用,不仅可以对所学的编程语言进行巩固,同时,通过实践编写演化算法程序可以使学生进一步了解演化算法的机理和执行过程.

由于绝大部分本科生都是初次接触演化算法编程,因此在实践教学中教师有必要首先通过简单示例编写程序,演示演化算法程序的编写.比如演化算法中个体结构体的定义、随机数发生器的使用、群体初始化、个体适应值的评估、基于赌的父个体选择、杂交算子和变异算子的实现等等,需要根据演化算法的执行流程一步一步编写程序,示范教学.通过示例,使学生学会基本的演化算法程序的编写,并在实验课和课后练习以熟练编写演化算法程序.