算法设计课程论文模板
- 格式:doc
- 大小:898.00 KB
- 文档页数:16
资料范本本资料为word版本,可以直接编辑和打印,感谢您的下载算法分析与设计论文地点:__________________时间:__________________说明:本资料适用于约定双方经过谈判,协商而共同承认,共同遵守的责任与义务,仅供参考,文档可直接下载或修改,不需要的部分可直接删除,使用时请详细阅读内容算法设计与分析论文题目0-1背包问题的算法设计策略对比与分析专业班级学号姓名引言对于计算机科学来说,算法(Algorithm)的概念是至关重要的。
算法是一系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。
如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与 HYPERLINK"/view/104946.htm" \t "_blank" 时间复杂度来衡量。
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。
或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解决一类问题。
算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。
一个算法应该具有以下五个重要的特征:有穷性:一个算法必须保证执行有限步之后结束;确切性:算法的每一步骤必须有确切的定义;输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件;输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的;可行性:算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。
HYPERLINK "/view/92404.htm" \t "_blank" 计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》,可见算法在计算机科学界与计算机应用界的地位。
前言 (1)正文 (1)2.1设计的目的和意义 (1)2.1.1设计的目的 (1)2.1.2设计的意义 (1)2.2设计的目标与总体方案 (1)2.1.1设计的目标 (1)2.1.2设计的总体方案 (2)2.3设计的方法和内容 (2)2.3.1硬件环境要求 (2)2.3.2软件环境需求 (2)2.3.3设计的流程图 (2)2.3.4设计的方法及详细内容 (2)2.3.4.1让用户输入信息 (2)2.3.4.2数据整理 (3)2.3.4.3查找数据并输出结果 (4)2.3.4.4询问用户是否继续 (5)2.4设计的创新与关键技术 (6)2.4.1设计的特点 (6)2.4.2设计的难点 (7)2.4.3软硬件调试及结果分析 (7)2.5结论 (7)致谢 (7)参考文献: (8)附录: (9)算法研究是计算机科学的核心。
近年来,算法领域去得了很多重要的进展。
这些进展包括快速算法的开发,如发明了傅里叶变换开速算法,以及不存在有效算法的本质问题的惊人发现。
这些结果点燃了计算机学者对算法研究的兴趣。
算法设计与分析已成为一个受到广泛注意的领域。
计算机的普及极大地改变了人们的生活。
目前,各行业、各领域都广泛采用了计算机的信息技术,并由此产生出开发各种应用软件的需求。
为了最少的成本、最快的速度、最好的质量开发出适合各种应用需求的软件,必须遵循软件工程的原则。
设计一个高效的程序不仅需要编程小技巧,更需要合理的数据组织和清晰高效的算法,这正是计算机科学领域数据结构与算法设计所研究的主要内容。
一些著名的计算机科学家在有关计算机科学教育的论述中认为,计算机科学是一中创造性思维活动,其教育必须面向设计。
计算机算法设计与分析正是一门面向设计,且处于计算机学科核心地位的教育课程。
通过对计算机算法系统的学习与研究,掌握算法设计的主要法方法,培养对算法的计算复杂性正确分析的能力,为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。
目录前言 (1)项目概况 (1)2.1开发工具简介 (1)2.2基本情况 (1)正文 (1)3.1设计的目的和意义 (1)3.2目标与总体方案 (1)3.2.1 设计目标 (1)2.2.2 工作进度安排 (1)3.3设计方法和内容 (2)3.3.1硬件环境 (2)3.3.2软件环境 (2)3.3.3设计算法的基本思想 (2)3.3.4 运行环境及所用函数解析 (4)3.4设计创新与关键技术 (5)3.5结论 (5)有关说明 (5)致谢 (5)参考文献 (6)附录: (7)前言人类已经跨入了新世纪,正在进入信息时代。
现在信息技术的应用越来越普及,不但促进了社会的高速发展,也改变着人们的工作、学习、生活和娱乐的方式以及思想观念。
随着计算机的日益普及,计算机软件无处不在。
软件在计算机的发展和应用中至关重要,在人类进入信息化社会时成为新兴信息产业的支柱。
随着人类社会的发展,随着计算机及网络技术的飞速发展,Internet应用在全球范围内日益普及,当今社会正快速向信息化社会前进,信息系统的作用也越来越大。
要熟练而又灵活的运用与操作计算机,就要用到一些程序,程序的强大又简练,主要是靠程序的思想与算法,合理的设计程序思想,运用算法,才能更加体现出程序对计算机的操作,更能体现出计算机的强大。
项目概况2.1开发工具简介C语言是国际上广泛流行的计算机高级语言,它适合作为系统描述语言,既可以用于编写系统软件,也可以用来编写应用软件。
它具有语言简洁,使用灵活,运算符丰富,数据类型丰富,生成目标代码质量高,程序执行效率高,程序可移植性好,此次设计的项目是在Microsoft Visual C++的环境下编辑。
2.2基本情况此次项目是在校机房408室和宿舍,用了14天的时间编辑出来的。
前7天在查阅资料,规划系统结构,后面的几天中,在编辑系统程序,并且调试次程序。
此项目是皇后算法,我们所学的知识有限,时间也有限,所编辑的系统比较简单。
湖南理工学院课程论文论文题目贪心法的应用课程名称算法设计与分析姓名学号专业计算机科学与技术年级学院计算机日期(2014年4月10日)课程论文评价标准贪心法的应用摘要:在解决问题的过程中,通过逐步获得最优解从而获得整体最优解的策略就是贪心策略,在已经学会在解的范围可以确定的情况下,可以采用枚举或递归策略,一一比较它们最后找到最优解;但当解的范围非常大时,枚举和递归的效率会非常低。
这时就可以考虑用贪心策略。
贪心算法没有固定的框架,算法设计的关键是贪心策略的选择,贪心策略要具有无后向性,即某阶段状态一旦确定以后,不受这个状态以后的策略的影响。
当一个问题有好几种解决方法时,贪心法应该是最好的选择之一。
本文讲述了贪心算法的含义、基本思路以及贪心算法在实例中的应用。
关键词:贪心算法;删数问题;最小生成树一、引言在平时解决问题的过程中,当一个问题就有无后向性和贪心选择性质时,贪心算法通常会给出一个简单、直观和高效的解法。
贪心算法通过一系列的选择来得到一个问题的解。
它所做的每一个选择都是当前状态下就有某种意义的最好选择,即贪心选择;并且每次贪心选择都能将问题化解为一个更小的与原问题具有相同形式的子问题。
尽管贪心算法对于很多问题不能总是产生整体最优解,但对于最短路径、最小生成树问题,以及删数问题等却可以获得整体最优解,而且所给出的算法一般比动态规划算法更为简单、直观和高效。
二、贪心算法的含义和特点(一)贪心算法的含义贪心算法是通过一系列的选择来得到问题解的过程。
贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法,它总是做出在当前看来是最有的选择,也就是说贪心策略并不是从整体上加以考虑,它所做出的选择只是在某种意义上的局部最优解算法。
(二)贪心算法的特点1、从全局来看,运用贪心策略解决的问题在程序运行过程中无回溯过程,后面的每一步都是当前看似最佳的选择,这种选择依赖已作出的选择,但并不依赖未作出的选择。
2、不能保证最后求出的解是最佳的。
算法设计与分析基础期末论文专业:______________________班级:______________________学号:______________________姓名:______________________指导老师:______________________贪婪算法(Greedy algorithm)贪婪算法,又称贪心算法。
是指,在对问题求解时,总是做出在当前看来是最好的选择。
也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
贪婪算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
作为一种规律,贪婪算法看上去既直观又简单。
尽管看上去它们并不复杂,但在这种技术背后有着相当复杂的理论,它是基于一种称为“拟阵”的抽象组合结构。
贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。
用贪婪法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。
例如平时购物找钱时,为使找回的零钱的硬币数最少,不考虑找零钱的所有各种发表方案,而是从最大面值的币种开始,按递减的顺序考虑各币种,先尽量用大面值的币种,当不足大面值币种的金额时才去考虑下一种较小面值的币种。
这就是在使用贪婪法。
这种方法在这里总是最优,是因为银行对其发行的硬币种类和硬币面值的巧妙安排。
如只有面值分别为1、5和11单位的硬币,而希望找回总额为15单位的硬币。
按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬币,共找回5个硬币。
算法设计与分析结课论文Hash技术学生姓名:***学号:**********专业:计算机科学与技术年级:2009级完成日期:2010年月日指导教师:***成绩:Hash技术摘要:随着科技日益发展,Hash函数的重要性越来越突出。
本文介绍了几种构造Hash 的方法,例如直接定址法、数字分析法、平方取中法、折叠法、除留余数法等,在构造Hash函数时,应当注意两点问题:(1)函数值应在1至记录总数之间。
(2)尽量避免冲突。
还介绍了几种处理Hash算法冲突的方法。
除此之外,阐明了Hash函数的优缺点和它在现实生活中的应用。
关键词:Hash函数,构造方法,应用,优缺点目录1.绪论1.1 什么是算法1.2 搜索算法2.Hash函数2.1 Hash函数的基本概念2.2 Hash函数的基本思想与一般模型2.3 Hash函数的构造3. 处理冲突的方法3.1 开放定址法3.2 再哈希法3.3 链地址法3.4 建立一个公共溢出区4. Hash算法的优劣分析5. Hash函数的应用5.1 完整性的验证5.2 数字签名5.3 认证协议5.4 加密算法6. 总结1. 绪论1.1 什么是算法算法的概念在计算机科学与技术领域几乎无处不在,在各种计算机系统的实现中,算法的设计往往处于核心的位置。
1.2 搜索算法搜索问题是计算机技术面对的基本课题之一,自20世纪70年代以来,计算机应用的主流逐渐从计算机密集型向着数据密集型转化,计算机存储和处理的数据量越来越大,结构越来越复杂,因此,对搜索算法的研究始终是人们研究的重要领域。
搜索算法与其他问题不同,它与数据结合的组织形式密切相关。
在大多数情况下,搜索算法实际上是作为某种数据类型的运算或操作而不断的被调用的,搜索算法的优劣与数据结构密切相关。
2. Hash函数2.1 Hash函数的基本概念Hash函数是把任意长度的二进制串映射到特定长度的二进制串函数,是最基本的二进制函数之一。
Hash函数也被称为“凑数函数”,但这个名称很少被采用,70年代之前也被称为散列函数,现在我们经常将其称之为Hash或译为哈什。
编程算法课程设计摘要:对《编程算法》课程的课程描述、教学活动历程设计、教学平量设计等方面做了详细的描述,重在培养学生动手实践,提高学生整体能力素质。
关键词:成果导向;编程算法;多元评量;课程设计1课程基本情况高职软件技术专业,《编程算法》课程类型为软件技术专业核心课程,修读方式为必修课,学分/学时为4学分/72学时,上课场所为一体化实训教室。
课程的总体设计思想为以“成果导向+行动学习”教学理念为指导,遵循学生认知规律、技能形成规律及技术发展规律,采用成果导向教学模式,并运用五步技能训练法(必备理论、操作准备、引导训练、同步训练、拓展训练)进行学训一体、多元实时评量的课上课下教学活动。
在课程设计和实施过程中完成:转———转为现代职业教育教学理念;建———课程体系建设、教师专业建设;改———课程改革、方法改变、课堂改造的成果导向教育教学改革。
2课程描述设计本课程旨在引领学生运用经典算法处理程序设计问题,掌握C++程序设计技巧,选取合适数据结构、编写有效算法和对算法进行分析和评价(目的)。
3教学活动历程设计在教学活动历程中按照准备活动、发展活动、整合活动开展教学活动,完成12个教学环节。
3.1准备活动:提高沟通整合等能力。
教学导航:明确编程算法的教学目标、重点和难点、熟悉教学方法、了解教学环节必备知识:教师根据单元学习成果,对确保改学习成果能够顺利达成的相关理论知识进行讲解。
操作准备:提示本单元操作所需的学习资源,分发学习素材、信息单。
3.2发展活动:提高问题解决、沟通整合、专业技能、职业素养等能力。
引导训练:教师给出操作任务单、算法对应程序的执行结果-即学习成果,学生在教师的引导下进行操作,完成案例,形成操作技能单。
引导训练考核评价:对学生操作态度及完成情况进行评价。
同步训练:教师给出操作任务单、算法对应程序的执行结果-即学习成果,由学生按照引导训练中所学知识完成算法设计及程序编写,组内成员互相帮助,巩固所学技能。
算法设计与分析论文学院:计算机学院专业:计算机科学与技术姓名:***学号:************1.简述动态规划算法求解问题的一般步骤。
答:⑴找出最优解的性质,并刻画其机构特征;⑵递归地定义最优值;⑶以自底向上的方式计算出最优值;⑷根据计算最优值时地带的信息,构造最优解。
6.简述回溯法求解问题的一般步骤。
答:(1)用回溯法解题通常包含一下3个步骤(2)针对所给问题,定义问题的解空间;(3)确定易于搜索的解空间;(4)以深度优先方式搜索解空间,并在搜索过程中用剪枝反函数避免无效搜索。
1、工作分配问题:设有n 件工作分配给n 个人。
将工作i 分配给第j 个人所需费用为ij c 。
为每一个人分配一件不同的工作,并使总费用达到最小。
1.1设计算法工作分配按照遍历应该有n!种分法,从中找出所需费用最少的费用。
这里采用递归的方法解决问题对于每一条路径所需费用为expense=∑=ni ip j 1c ,其中j ip c 表示第i 建工作分配给第p i个人时所需费用,p1~p n互不相同,即每个人只能分配一件工作。
在计算的时候可以设计expense(i)等于分配过第i件工作后这时所达到的总费用,分配第i+1i+1件工作,总费用expense(i+1)=expense(i)+j ip c,当i<n时,继续递归,当i=n时判断本此分配的工作总费用是否比之前保存的最低费用小,是则把此次分配总费用值赋给minexpense,并保存此次分配的路径给q[]。
可以设计如下递归函数void workdistribute(int i,int n,int *p,int x[],int c[][N]){for(int j=1;j<=n;j++){if(x[j]==0){x[j]=1;x[0]+=c[i][j];p[i]=j;if(i<n){workdistribute(i+1,n,p,x,c);}else{if(minexpense>x[0]||minexpense==-1){minexpense=x[0];for(int k=1;k<=n;k++)q[k]=p[k];}x[0]-=c[i][j];}x[j]=0;}}}1.2分析计算复杂度1.3程序实现进行宏定义N大小为100,在以后可以重新赋值#define N 100int q[N]={0};//定义全局变量q数组用来保存工作分配路径int minexpense=-1;//定义全局变量用来保存分配中最小费用void workdistribute(int i,int n, int p[],int x[],int c[][N]);主函数void main() {int n=0;int c[N][N];int x[N]={0};int p[N]={0};printf("\t\t\t\1.工作分配问题n\n");printf("请输入人数\n");scanf("%d",&n);下面用来输入所需费用for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)scanf("%d",&c[i][j]);}调用workdistribute(1,n,p,x,c);函数进行递归分配工作,递归结束后进行输出最小费用和此分法,以矩阵的形式显示workdistribute(1,n,p,x,c);printf("%d\n",minexpense);此循环用来输出最少费用的分配方法for(int k=1;k<=n;k++){for(int j=1;j<=n;j++){if(q[k]!=j)printf(" ");elseprintf("%d ",c[k][j]);}printf("\n");}}//workdistribute(i,n,p,x,c)函数设计,传递进行分配的是第几件工作i,已分配过的人X[],分配的路径p[],以及费用数组c[][],用X[]来保存已非配工作所需费用void workdistribute(int i,int n,int *p,int x[],int c[][N]){for(int j=1;j<=n;j++){if(x[j]==0){x[j]=1;x[0]+=c[i][j];p[i]=j;if(i<n)//当未分配完时继续调用{workdistribute(i+1,n,p,x,c);}else//最后一事件分配完后,判断此次分配是不是最小费用{if(minexpense>x[0]||minexpense==-1)//如果是最小分配或第一次分配,则保存此次分配数据{minexpense=x[0];for(int k=1;k<=n;k++)q[k]=p[k];}}x[j]=0;x[0]-=c[i][j];//返回上一层之前,先减去此事件分配的费用}}}1.4最后通过简例说明程序实现过程输入事件数为3输入费用矩阵 C32 1 34 5 21 2 1第一层第一次分配workdistribute(1,n,p,x[],c[][N]);分配过程c[1][1],c[2][2],c[3][3] 此时最小费用是8 赋值给minexpense,并把1,2,3保存在q数组,最后一层递归返回上一次,第二中分配方式c[1][1],c[2][3],c[3][2]此时费用时6,minexpense为6,1,3,2保存在q中,第一层第一次分配完毕,然后循环workdistribute(2,n,p,x[],c[][N]);第三种分配,c[1][2],c[2][1],c[3][3],minexpesne=6,q[]:为1,3,2,第四次分配c[1][2],c[2][3],c[3][1],minexpense=4,q[]:2,3,1 第一层第二次分配完毕,然后循环workdistribute(3,n,p,x[],c[][N]);第五种分配c[1][3],c[2][1],c[3][2],minexpense=4,q[]:2,3,1,第六种分配c[1][3],c[2][2],c[3][1],minexpense=4,q[]:2,3,1 返回主程序,输出minexpense,q[],2,3,1。
算法论文范文摘要本文介绍了一种基于深度学习的图像分类算法。
该算法采用卷积神经网络(CNN)作为特征提取器,并结合支持向量机(SVM)进行分类。
实验结果表明,该算法在多个数据集上均取得了优秀的分类效果。
引言图像分类是计算机视觉领域的一个重要问题。
在实际应用中,我们需要将大量的图像按照其所属的类别进行分类。
传统的图像分类方法通常采用手工设计的特征提取器,如SIFT、HOG等。
这些方法虽然在一定程度上能够提取出图像的特征,但是其性能受到了很多限制,如对光照、旋转、尺度等变化的敏感性。
近年来,深度学习技术的发展为图像分类带来了新的思路。
卷积神经网络(CNN)是一种基于深度学习的图像分类方法,其可以自动学习图像的特征,并且对于光照、旋转、尺度等变化具有较好的鲁棒性。
本文提出了一种基于CNN的图像分类算法,并结合支持向量机(SVM)进行分类。
算法描述数据预处理在进行图像分类之前,我们需要对数据进行预处理。
本文采用了CIFAR-10数据集进行实验,该数据集包含了10个类别的60000张32x32的彩色图像。
我们首先将图像进行归一化处理,将像素值缩放到[0,1]之间。
然后,我们将数据集分为训练集和测试集,其中训练集包含50000张图像,测试集包含10000张图像。
特征提取本文采用了一个5层的卷积神经网络(CNN)作为特征提取器。
该网络的结构如下所示:Convolutional layer (32 filters, 3x3 kernel, stride 1)ReLU activationMax pooling layer (2x2 kernel, stride 2)Convolutional layer (64 filters, 3x3 kernel, stride 1)ReLU activationMax pooling layer (2x2 kernel, stride 2)Convolutional layer (128 filters, 3x3 kernel, stride 1)ReLU activationMax pooling layer (2x2 kernel, stride 2)Fully connected layer (1024 units)ReLU activation在训练过程中,我们采用了随机梯度下降(SGD)算法进行优化。
《算法设计》课程论文题目针对UBQP问题的量子文化基因算法学生姓名学号院系计算机与软件学院专业计算机科学与技术指导教师刘文杰2015年6 月30 日目录1 引言 (2)2 ** 算法简介 (3)3 针对UBQP问题的量子文化基因算法(QEA-TS) (3)3.1算法思想 (3)3.2算法流程 (3)3.3算法过程描述 (5)3.3.1输入权值矩阵 (5)3.3.2 量子染色体初始化 (5)3.3.3 染色体观测 (5)3.3.4禁忌搜索 (6)3.3.5评估适应度值 (7)3.3.6 量子旋转门和更新 (7)3.3.7算法终止条件 (10)3.4本章小结 (11)4代码实现与结果分析 (11)4.1代码实现 (11)4.2运行结果分析与比较 (12)4.2.1参数设置 (12)4.2.2运行结果分析与比较 (12)5 小结 (14)针对UBQP 问题的量子文化基因算法1 引 言无约束0-1二次规划问题(Unconstrained Binary Quadratic Problem ,UBQP )是一类选取合适的二进制决策变量,使得二次目标函数值极大化的优化问题,该问题用数学表达式可以写成UBQP :QX X x f T =)((1)的形式,其中Q 是一个n n ⨯对称矩阵,一般写成上三角的形式,是常量,X 是n 维二进制向量(每个分量都是0或者1),即需要求的解。
这是一个典型的NP (Non-deterministic Polynomial )难题,它有许多方面的应用,如计算机辅助设计,社会心理学,交通管理,金融分析,机器调度等等。
同时,UBQP 问题是组合优化问题的一种通用模型,大多数组合优化问题都能够转化成该问题后进行求解,如图着色问题,多维背包问题,最大团问题,集合分割问题等等。
同时UBQP 问题是一个多峰值函数问题,在它的函数图像中具有很多山峰一样的极值点。
对这一问题,学者们提出了多种求解的算法,这些算法大致可以归结为两大类:完整算法和启发式算法。
《算法设计》课程论文题目针对UBQP问题的量子文化基因算法学生姓名学号院系计算机与软件学院专业计算机科学与技术指导教师刘文杰2015年6 月30 日目录1 引言 (2)2 ** 算法简介 (3)3 针对UBQP问题的量子文化基因算法(QEA-TS) (3)3.1算法思想 (3)3.2算法流程 (3)3.3算法过程描述 (5)3.3.1输入权值矩阵 (5)3.3.2 量子染色体初始化 (5)3.3.3 染色体观测 (5)3.3.4禁忌搜索 (6)3.3.5评估适应度值 (7)3.3.6 量子旋转门和更新 (7)3.3.7算法终止条件 (10)3.4本章小结 (11)4代码实现与结果分析 (11)4.1代码实现 (11)4.2运行结果分析与比较 (12)4.2.1参数设置 (12)4.2.2运行结果分析与比较 (12)5 小结 (14)针对UBQP 问题的量子文化基因算法1 引 言无约束0-1二次规划问题(Unconstrained Binary Quadratic Problem ,UBQP )是一类选取合适的二进制决策变量,使得二次目标函数值极大化的优化问题,该问题用数学表达式可以写成UBQP :QX X x f T =)((1)的形式,其中Q 是一个n n ⨯对称矩阵,一般写成上三角的形式,是常量,X 是n 维二进制向量(每个分量都是0或者1),即需要求的解。
这是一个典型的NP (Non-deterministic Polynomial )难题,它有许多方面的应用,如计算机辅助设计,社会心理学,交通管理,金融分析,机器调度等等。
同时,UBQP 问题是组合优化问题的一种通用模型,大多数组合优化问题都能够转化成该问题后进行求解,如图着色问题,多维背包问题,最大团问题,集合分割问题等等。
同时UBQP 问题是一个多峰值函数问题,在它的函数图像中具有很多山峰一样的极值点。
对这一问题,学者们提出了多种求解的算法,这些算法大致可以归结为两大类:完整算法和启发式算法。
早期较成功的完整算法有分支定界法和分支切割法,这些算法在当变量个数超过100时,无法在一个合理的时间求得优化解。
于是一些学者提出了求解此问题的启发式算法,如禁忌搜索算法[1](Tabu Search ,TS ),模拟退火算法[2](Simulated Annealing ,SA ),遗传算法[3](Genetic Algorithm ,GA ),混合算法[4](Memetic Algorithm ,MA )等,这些算法在求解规模较大的问题时能够在可接受的时间求得问题的近似优化解。
禁忌搜索已在许多组合优化问题上被证明是一种非常高效的搜索算法。
但是,同其他局部搜索算法一样,禁忌搜索也难以避免落入局部最优值的“陷阱”。
针对这个缺陷,需要设计一种有效的跳坑策略使其逃离该局部最优值区域,找到更高优度的解。
另一方面,量子进化算法[5](Quantum Evolution Algorithm ,QEA )由于引入量子计算的概念,采用量子染色体对解空间进行编码,根据量子态概念特性,一个量子染色体可以表示多个解的线性叠加,因此QEA 具有较快的收敛速度和较强的全局搜索能力。
基于以上的全局算法和局部算法的研究,本文中引入了文化基因算法[6]——全局框架与局部框架结合——的概念,以量子进化算法(QEA )作为全局搜索框架,以禁忌搜索算法(TS )作为局部搜索框架,将这两种算法有机结合,形成量子文化基因算法,文中称该算法为QEA-TS 。
它的优势在于将量子进化算法的种群多样性和禁忌搜索算法较强的局部搜索性能充分发挥了出来,并且还针对QEA 在多峰值函数问题中容易陷入局部最优的缺陷对量子旋转门更新策略进行了改进,提出了一种新的更新思路,即靠近当前最优解过程中适当保持距离的策略,下文将对此详细介绍。
在评估本算法的效率和质量时,本文中针对3个较难的指标实例包括2500(包含10组实例),3000(包含5组实例),4000(包含5组实例)规模测试实例,本文将对这些实例进行测试并与以往的文献中的最好的结果进行比较。
2 ** 算法简介简要介绍该算法的基本思想,算法基本流程,以及特点等3 针对UBQP问题的量子文化基因算法(QEA-TS)3.1算法思想针对UBQP问题本文引入了文化基因算法和量子进化的概念,在前文基础知识介绍中曾经提到,文化基因算法是全局搜索和局部搜索的结合体,它是一种框架,一个笼统的概念;另一方面量子进化算法采用量子染色体机制,拥有良好的种群多样性,具有较好的全局搜索性能。
因此在本文中将量子进化算法(QEA)以及禁忌搜索算法(TS)结合起来,以量子进化算法作为全局搜索框架,而以禁忌搜索算法作为局部搜索,从而形成一种新的文化基因算法,称该算法为QEA-TS算法。
QEA-TS算法的思想就是在量子进化算法过程中插入禁忌搜索,插入的条件需要结合具体问题适当选择,比如可以以代数间隔为条件。
在解决问题过程中始终要保持种群的多样性,但是由于QEA 在解决多峰值函数问题时容易陷入局部最优,因此本文在量子旋转门上做了适当的改进,让种群在逐渐靠近最优解的同时又要保持适当的距离,以维持种群的多样性,保持算法的全局搜索性能,而禁忌搜索作为优秀的局部搜索算法,则可以在每一个“点”周围尽可能的去搜索局部最优解,在经过若干代数后,通过若干次局部最优解的比较后,获得全局最优解。
总体来讲QEA-TS算法就是由量子进化算法保持种群的多样性,保持全局搜索范围,可以提供给禁忌搜索算法不同的空间去探索更好的解,而不是一直在某一个范围内循环往复。
3.2算法流程图1中显示了本算法的基本流程,下面将分步骤说明。
输入权值矩阵Ai=0,初始化Q(t)t=t+1观察Q(t-1),获得P(t)满足禁忌搜索条件对P(t)禁忌搜索对P(t)计算适应度值存入F(t)中F(t)>B(t-1)量子旋转门更新,获得Q(t)B(t)=F(t)满足终止条件是是否否B(t)=B(t-1)否从B(t)中选择最优值存入全局最优解b离开图1.QEA-TS 算法流程图1. 输入权值矩阵A ,获得问题规模n ;2. 初始代数0=t ;3. 初始化量子染色体种群},...,...,{)(1t n t i t q q q t Q =;4. 1+=t t ;5. 观测量子染色体种群)1(-t Q ,获得确定的二进制染色体种群},...,,{)(21t m t t X X X t P =;6. 如果满足禁忌搜索条件,则转到步骤7;否则转到步骤8;7. 对)(t P 中的每个染色体调用禁忌搜索算法;8. 计算种群P(t)中每个染色体的适应度值},...,,...,{)(1tn t i t f f f t F =;9. 用量子旋转门对量子染色体种群)(t Q 进行更新;10. 将)(t F 中的每个适应度值t i f 与上一代最好解},...,...,,{)1(1111---=-t n t i t b b b t B 中的1-t i b 比较,将较大者保存到当前代的最好解)(t B 中;11. 比较},...,...,,{)(1tn t i t b b b t B =中的所有值,将最好解保存到全局历史最好解b 中;12. 如果不满足终止条件,则跳转到步骤4;13. 将全局最好解b 保存到记事本中,结束。
3.3算法过程描述3.3.1输入权值矩阵在开始程序前,需要从外部文件中导入权值矩阵A ,这在步骤1中所完成的,这是计算函数的适应度值所必须的, 网站中保存有几个A 矩阵的实例(规模有50、100、200、500、1000、2500的),由于A 矩阵是对称矩阵,因此它们一般都是上三角矩阵的形式存储,这些都可以从因特网上下载获得,在本文中只测试2500、3000、4000规模的实例,因为较小规模的实例本算法可以在很短的时间内获得最好值。
3.3.2 量子染色体初始化通常,在步骤3阶段,所有量子染色体tj q 的t i α和t i β被初始化为21,即量子染色体0j q 为所有叠加态的概率相等,其状态表示如下:k k m q X m j ∑==21210ψ (7) 式中),...,,...,,...,(1m j i k x x x x X =表示第k 个叠加状态,其中]1,0[),...,2,1(∈=m i x i 。
3.3.3 染色体观测在步骤5阶段通过观察)1(-t Q 生成一组确定的二进制解},...,,{)(21tm t t X X X t P =,其中),...,2,1(n j X tj =是一个对应于k X 的二进制串,它通过对量子染色体所有比特进行观察后得到,这里观察的意思就是随机产生一个0~1之间的一个小数r ,然后将该数与t i q 的[]2α进行比较,如果r<[]2α则0=i x ,否则1=i x 。
3.3.4禁忌搜索步骤6、7是本算法中的第一个关键,这两部通过判断是否达到禁忌搜索的条件TS-condition ,如果达到禁忌搜索条件,就要对种群中的每个染色体进行局部搜索,从而在当前染色体的一个局部范围内搜索局部最优解,在本文的算法中TS-condition 取为固定代数,即每隔一定代数就执行一次禁忌搜索。
下面详细介绍禁忌算法在UBQP 问题中的应用。
关于应用于UBQP 问题的禁忌搜索算法[14]是基于这样的思想:对一个解中的分量随机翻转(或者说移动)得到新解,那么说翻转后的向量和翻转前的向量是相邻的,然后考虑这两个相邻解的函数值之差。
对于分量翻转就是把一个解中的分量i x 变为i x -1,简单的说就是把1变成0,0变成1。
这里使用的是快速增量评估技术来预先计算每个分量相邻解的增加值,也就是说先假设某个分量被选中翻转,那么增长值就是翻转后的向量的函数值和翻转前的向量的函数值之差,从而可以代入已知公式在线性的时间内计算出来。
一般的,用},......,2,1{n N =来表示一个X 向量中的分量序号,把输入的Q 矩阵处理为下三角矩阵的形式(对角线以上的部分全部都是0)。
用i ∆表示翻转变量i x 后的移动值,用),(j i q 表示ij q 当i>j 时或者ji q 当j>i 时。
这样每次的增长值就能用下面的公式在线性的时间内用下面的公式预先估计到:)),()(21(1,,∑=≠∈+-=∆j x i j N j ii i j i q q x i (8)其),(j i q 中表示当j i >时),(j i q =ij q ,当j i <时),(j i q =ji q 。
另外,一旦某个分量被翻转,那么就意味着在翻转后的向量的基础上下一次预估就开始了。
特别的,可以执行下面的一段计算过程来重新估计翻转i 分量后该分量本身和其他分量的预估增加值。