《基于NET的商品销售管理系统》开题报告.docx
《《基于NET的商品销售管理系统》开题报告.docx》由会员分享,可在线阅读,更多相关《《基于NET的商品销售管理系统》开题报告.docx(12页珍藏版)》请在冰点文库上搜索。
《基于NET的商品销售管理系统》开题报告
襄樊学院毕业论文(设计)开题申请表
学生姓名
马晨航
指导老师
谷琼
系(院)
理工学院
专业
计算机科学与技术
班级
0812
论文题目
八皇后问题遗传算法的研究
开题申请
遗传算法是计算数学中用于解决最优化的搜索算法,是进化算法的一种。
进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等。
本次研究就是通过遗传算法的选择算子、交叉算子、变异算子的方法进行染色体基因重组的方式重新生成新的个体的方法运用到解决八皇后的这种问题,由于遗传算法的运算方式是类似于随机排列而后的组合所以它不会像回溯法那样在每次的结果上有上一次的局限性,而且具有内在的隐并行性和更好的全局寻优能力。
在这里我们主要通过它对八皇后问题的应用来研究遗传算法的组合优化能力,既其运行效率以及自适应控制的稳定性。
申请人签名:
年月日
指导教师意见
指导教师签名:
年月日
毕业设计开题报告
基于遗传算法对八皇后问题的运用
理工学院计算机科学与技术专业0812班学号:
08317110姓名:
马晨航
指导老师:
谷琼
开题报告正文——
一、本算法设计(遗传算法)目的、现状及发展趋势
1、本算法设计(研究)的目的:
遗传算法(GeneticAlgorithm,GA)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。
1962年霍兰德(Holland)教授首次提出了GA算法的思想,它借用了仿真生物遗传学和自然选择机理,通过自然选择、遗传、变异等作用机制,实现各个个体的适应性的提高。
从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。
与自然界相似,遗传算法对求解问题的本身一无所知,它所需要的仅是对算法所产生的每个染色体进行评价,把问题的解表示成染色体,并基于适应值来选择染色体,使适应性好的染色体有更多的繁殖机会。
在算法中也即是以二进制编码的串。
并且,在执行遗传算法之前,给出一群染色体,也即是假设解。
然后,把这些假设解置于问题的“环境”中,也即一个适应度函数中来评价。
并按适者生存的原则,从中选择出较适应环境的染色体进行复制,淘汰低适应度的个体,再通过交叉,变异过程产生更适应环境的新一代染色体群。
对这个新种群进行下一轮进化,至到最适合环境的值。
由于遗传算法的整体搜索策略和优化搜索方法是不依赖于梯度信息或其它辅助知识,而只需要影响搜索方向的目标函数和相应的适应度函数,所以遗传算法提供了一种求解复杂系统问题的通用框架,它不依赖于问题的具体领域。
遗传算法已用于求解带有应用前景的一些问题,例如遗传程序设计、函数优化、排序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。
本课题的目的就是学习遗传算法的基本原理、特点,掌握基本的遗传算法。
编程实现各不同的遗传算法,对于具体的应用研究比对各遗传算法的性能,并就提出改进性能的方法。
通过该课题的学习,了解科学研究的方法和过程,能够理论联系实际,独立解决实际应用问题。
熟悉VC编程环境,提高编程能力。
2、设计(研究)现状和发展趋势:
进入90年代,遗传算法迎来了兴盛发展时期,无论是理论研究还是应用研究都成了十分热门的课题。
尤其是遗传算法的应用研究显得格外活跃,不但它的应用领域扩大,而且利用遗传算法进行优化和规则学习的能力也显著提高,同时产业应用方面的研究也在摸索之中。
此外一些新的理论和方法在应用研究中亦得到了迅速的发展,这些无疑均给遗传算法增添了新的活力。
遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。
随着应用领域的扩展,遗传算法的研究出现了几个引人注目的新动向:
一是基于遗传算法的机器学习,这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。
这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。
二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合,这对开拓21世纪中新的智能计算技术将具有重要的意义。
三是并行处理的遗传算法的研究十分活跃。
这一研究不仅对遗传算法本身的发展,而且对于新一代智能计算机体系结构的研究都是十分重要的。
四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。
所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象,其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象,而遗传算法在这方面将会发挥一定的作用。
五是遗传算法和进化规划以及进化策略等进化计算理论日益结合。
EP和ES几乎是和遗传算法同时独立发展起来的,同遗传算法一样,它们也是模拟自然界生物进化机制的只能计算方法,即同遗传算法具有相同之处,也有各自的特点。
目前,这三者之间的比较研究和彼此结合的探讨正形成热点。
二、本算法的研究应用技术
1、应用工具VisualC++6.0
本算法研究采用VisualC++6.0软件开发。
VisualC++6.0,简称VC或者VC6.0,是微软推出的一款C++编译器,将“高级语言”翻译为“机器语言(低级语言)”的程序。
VisualC++是一个功能强大的可视化软件开发工具。
VisualC++6.0由Microsoft开发,它不仅是一个C++编译器,而且是一个基于Windows操作系统的可视化集成开发环境(integrateddevelopmentenvironment,IDE)。
VisualC++6.0由许多组件组成,包括编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。
这些组件通过一个名为DeveloperStudio的组件集成为和谐的开发环境。
VisualC++是一个功能强大的可视化软件开发工具。
自1993年Microsoft公司推出VisualC++1.0后,随着其新版本的不断问世,VisualC++已成为专业程序员进行软件开发的首选工具。
虽然微软公司推出了VisualC++.NET(VisualC++7.0),但它的应用的很大的局限性,只适用于Windows2000,WindowsXP和WindowsNT4.0。
所以实际中,更多的是以VisualC++6.0为平台。
2、算法应用工程MFCAppWizard(exe)
MFC是微软基础类库的简称,是微软公司实现的一个c++类库,主要封装了大部分的windowsAPI函数,VC++是微软公司开发的c/c++的集成开发环境,所谓集成开发环境,就是说利用它你可以编辑,编译,调试,而不是使用多种工具轮换操作,灵活性较大。
有时人们说VC呢也指它的内部编译器,集成开发环境必须有一个编译器内核,要不有什么用,例如DEVC++其中一个编译器内核就是GCC。
MFC除了是一个类库以外,还是一个框架,你应该试过,在VC++里新建一个MFC的工程,开发环境会自动帮你产生许多文件,同时它使用了mfcxx.dll。
xx是版本,它封装了MFC内核,所以你在你的代码看不到原本的SDK编程中的消息循环等等东西,因为MFC框架帮你封装好了,这样你就可以专心的考虑你程序的逻辑,而不是这些每次编程都要重复的东西,但是由于是通用框架,没有最好的针对性,当然也就丧失了一些灵活性和效率但是MFC的封装很浅,所以效率上损失不大,灵活性还可以,虽然也有很多缺陷,但还是一个比较好的东西。
3、下面介绍最重要的MFC
CWnd:
窗口,它是大多数“看得见的东西”的父类(Windows里几乎所有看得见的东西都是一个窗口,大窗口里有许多小窗口),比如视图CView、框架窗口CFrameWnd、工具条CToolBar、对话框CDialog、按钮CButton,etc;一个例外是菜单(CMenu)不是从窗口派生的。
该类很大,一开始也不必学,知道就行了。
CDocument文档,负责内存数据与磁盘的交互。
最重要的是OnOpenDocument(读入),OnSaveDocument(写盘),Serialize(读写)
CView视图,负责内存数据与用户的交互。
包括数据的显示、用户操作的响应(如菜单的选取、鼠标的响应)。
最重要的是OnDraw(重画窗口),通常用CWnd:
:
Invalidate()来启动它。
另外,它通过消息映射表处理菜单、工具条、快捷键和其他用户消息。
你自己的许多功能都要加在里面,你打交道最多的就是它。
CDC设备文本。
无论是显示器还是打印机,都是画图给用户看。
这图就抽象为CDC。
CDC与其他GDI(图形设备接口)一起,完成文字和图形、图像的显示工作。
把CDC想象成一张纸,每个窗口都有一个CDC相联系,负责画窗口。
CDC有个常用子类CClientDC(窗口客户区),画图通常通过CClientDC完成。
CDialog对话框
CWinApp应用程序类。
似于C中的main函数,是程序执行的入口和管理者,负责程序建立、消灭,主窗口和文档模板的建立。
最常用函数InitInstance():
初始化。
CGdiObject及子类,用于向设备文本画图。
它们都需要在使用前选进DC。
CPen笔,画线
CBrush刷子,填充
CFont字体,控制文字输出的字体
CBitmap位图
CPalette调色板
CRgn区域,指定一块区域可以用于做特殊处理。
CFile文件。
最重要的不外是Open(打开),Read(读入),Write(写)
CString字符串。
封装了C中的字符数组,非常实用。
CPoint点,就是(x,y)对
CRect矩形,就是(left,top,right,bottom)
CSize大小,就是(cx,cy)对(宽、高)MFC是在1992年的Microsoft16位版的C/C++编译器的7.0版本中作为一个扩展轻量级的WindowsAPI面向对象的C++封装库而引入的。
此时,C++因为它在和API方面的卓越表现,刚刚开始被用来取代C应用于开发商用软件。
因此,他们推出了替代早期的老式的字符界面的集成开发环境(IDE)的PWB。
三、本算法的主要研究内容
遗传算法开始,像任何其他优化算法,通过定义优化变量。
它像其他优化算法,通过测试的收敛。
路径组成部分的遗传表现为如流程图
Definecostfunction,cost,variablesSelectGAparameters
Generateinitialpopulation
Decodechromosomes
Findcostforeachchromosome
Selectmates
Mating
Mutation
ConvergenceCheck
Done
1、定义成本函数和成本(Definecostfunctionandcost)
每个问题都有一个成本函数。
例如,最大的一个三维表面有高峰和低谷时显示在可变空间。
成本,价值,健身,分配给每个解决方案。
2、染色体和基因(Chromosomesandgenes)
一个基因是一个介于0到n-1数字。
染色体是这些基因的一个数组。
它可能是一个答案。
人口在每一代都有确定的染色体数目。
3、创建一个随机初始种群(Createarandominitialpopulation)
初步人口从染色体的随机选择开始建立。
后代收敛所需的数量取决于随机初始种群。
4、解码的染色体,并找到成本(Decodethechromosomeandfindthecost)
找到为每一个染色体的成本函数定义的指定费用。
由于成本函数称为成本价值。
最后,平均每代成本值收敛到理想的答案。
5、交配和下一代(Matingandnextgeneration)
这些染色体具有较高的适应价值(较低的成本)用于产生下一代。
后代子女由父亲和母亲产生,其子女结构是他们(此过程称为“跨越”)一个基因的组合,。
如果新一代包含染色体产生的输出是足够接近或等于所需的答案,这个问题已经解决了。
如果不是这样的话,那么新的一代将通过同样的过程,就像他们的父母一样。
这将继续直到达成解决办法。
6、有关8皇后问题(Aboutthe8queensproblem)
在国际象棋中,女王可以任意移动,水平,垂直,或斜。
国际象棋的棋盘有8行和8列。
标准8x8皇后问题是如何将8个皇后在普通棋盘上其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
在这里,我们用n解决皇后问题这一问题的遗传算法(n是在8和30之间)。
7、遗传算法对八皇后问题解决的基本步骤
算法中的一些控制参数:
1、种群规模
2、最大换代数
3、交叉率(crossoverrate)就是参加交叉运算的染色体个数占全体染色体总数的比例,记为Pc,取值范围一般为0.4~0.99。
4、变异率(mutationrate)是指发生变异的基因位数所占全体染色体的基因总位数的比例,记为Pm,取值范围一般为0.0001~0.1。
生成初始种群
基本流程图:
计算适应度
结束
终止?
交叉
变异
生成新一代种群
步1在搜索空间U上定义一个适应度函数f(x),给定种群规模N,交叉率Pc和变异率Pm,代数T;
步2随机产生U中的N个个体s1,s2,…,sN,组成初始种群S={s1,s2,…,sN},置代数计数器t=1;
步3计算S中每个个体的适应度f();
步4若终止条件满足,则取S中适应度最大的个体作为所求结果,算法结束。
步5按选择概率P(xi)所决定的选中机会,每次从S中随机选定1个个体并将其染色体复制,共做N次,然后将复制所得的N个染色体组成群体S1;
步6按交叉率Pc所决定的参加交叉的染色体数c,从S1中随机确定c个染色体,配对进行交叉操作,并用产生的新染色体代替原染色体,得群体S2;
步7按变异率Pm所决定的变异次数m,从S2中随机确定m个染色体,分别进行变异操作,并用产生的新染色体代替原染色体,得群体S3;
步8将群体S3作为新一代种群,即用S3代替S,t=t+1,转步3;
四、毕业论文(设计)的进度安排(以周为单位)
进度安排如表1
第7学期末及寒假
确定指导老师,选题,初步收集相关开题资料
第8学期第1-4周
定题,准备开题报告,并提交给指导教师审阅。
第8学期第5周
与指导老师沟通安排时间开题答辩。
第8学期第6周
查找论文相关资料
第8学期第7周
设计相关函数、数据表
第8学期第8周
系统总体框架建设
第8学期第9周
实现部分功能
第8学期第10-11周
实现功能全部
第8学期第12周
完成论文初稿,交给指导老师审阅。
第8学期第13-14周
论文修改,系统总调试
第8学期第15周
论文定稿
第8学期第16周
论文答辩
表1
四、主要参考文献
参考文献
1、Goldberg,DavidE(1989),遗传算法:
搜索、优化和机器学习,KluwerAcademicPublishers,Boston,MA.
2、Goldberg,DavidE(2002),创新的设计:
竞争遗传算法课程,Addison-Wesley,Reading,MA.
3、Harvey,Inman(1992),物种适应和遗传算法持续进行的基础in'TowardaPracticeofAutonomousSystems:
ProceedingsoftheFirstEuropeanConferenceonArtificialLife',F.J.VarelaandP.Bourgine(eds.),MITPress/BradfordBooks,Cambridge,MA,pp.346-354.
4、Koza,John(1992),遗传算法:
通过自然选择编写计算机程序
5、Michalewicz,Zbigniew(1999),遗传算法+数据结构=进化程序,Springer-Verlag
6、Poli,R.,Langdon,W.B.,McPhee,N.F..AFieldGuidetoGeneticProgramming.L,freelyavailablefromtheinternet.2008.
7、Schmitt,LotharM(2001),遗传算法理论,TheoreticalComputerScience(259).
8、Schmitt,LotharM(2004),遗传算法理论
(二),TheoreticalComputerScience(310).
9、Vose,MichaelD(1999),简单遗传算法:
基础和理论,MITPress,Cambridge,MA.
10、冯蔚东陈剑赵纯均《清华大学学报(自然科学版)》2000第10期-万方数据
11、王磊潘进《电子学报》2000第7期-维普资讯网
12、金菊良杨晓华丁晶《四川大学学报(工程科学版)》2000第4期-万方数据
13、丁建立陈增强袁著祉《计算机研究与发展》2003第9期-维普资讯网
14、周驰高海兵高亮章万国《计算机应用研究》2003第12期-万方数据
15、吉根林《计算机应用与软件》2004第2期-万方数据