10BX06220黄丹燕_中期答辩.ppt

1、基于主动数据库的信用卡额度管理系统,BX06220 黄丹燕 指导老师：陈群贤,进度介绍,10.11.27-10.12.26,10.12.27-10.12.31,11.01.01-11.04.05,11.04.06-11.04.13,11.04.04-11.05.14,11.05.28-11.06.02,收集资料，准备开题报告和文献翻译,开题报告答辩、修改开题报告和文件翻译,完成毕业设计程序开发工作,毕业设计（论文）中期检查报核,完成毕业设计论文，并完善毕业设计程序,毕业设计答辩,完成,基本完成,完成,完成,进行中。,进行中。,论文框架,选题背景,随着以信息科学为代表的现代科学技术和知识经济的迅

2、猛发展， 全球经济一体化的趋势日益明显。在当今的市场中，制造企业的竞争主要取决于产品的供货周期、质量和售后服务水平。先进的生产管理是实现提高竞争力的一个重要手段。生产调度是生产管理的核心内容和关键技术，其任务是在企业车间有限的资源约束下，确定工件在相关设备上的加工顺序和加工时间，以保证所选定的生产目标最优。,选题意义,本课题研究内容是基于量子遗传算法的并行机调度，从算法的角度来说，量子遗传算法的研究可以推动相关算法的研究，为其他领域类似问题的解决提供了条件和手段；其次，并行机调度问题的解决本身就具有良好的实际意义，科学地制定生产调度方案，对于提高企业生产效率起着至关重要的作用。 一个好的调度方

3、案不仅可以降低生产成本，而且可以提高企业产品的准时交货能力，从而增强企业的竞争力。,并行机调度问题,调度问题描述 调度问题一般可以描述为：针对某项可以分解的工作，在一定的约束条件下，如何安排其组成部分（操作）所占用的资源、加工时间及先后顺序，以获得产品制造时间或者成本等性能指标最优。 调度问题特点 复杂性、随机性、约束性、多目标,并行机调度问题,求解调度问题的传统优化方法 （1）数学规划方法 （2）规则的调度方法 （3）基于知识的调度方法 （4）仿真调度方法 （5）启发式图搜索法 （6）局部搜索方法,遗传算法及其并行机调度问题,遗传算法在几个基本方面不同于传统优化方法： (1)遗传算法运算的是

4、解集的编码，而不是解集本身。 (2)遗传算法的搜索始于解的一个种群，而不是单个解。 (3)遗传算法只使用报酬信息（适应值函数），而不使用导数或其他辅助知识。 (4)遗传算法采用概率的，而不是确定的状态转移规则。,遗传算法及其并行机调度问题,用遗传算法来求解并行机调度问题的方法，分析了问题可行解的染色体表示方法和可行调度的判定方法，以3台机器5个工件为例，深入分析算法的思路和运行效果，给出遗传算法调度结果的工件在机器上的甘特图和优化曲线图。,量子遗传算法及其并行机调度问题,量子遗传算法概述 量子遗传算法是一种量子计算理论与进化计算理论相结合的概率搜索的优化算法，它在量子的态矢量表达基础上，将量子

5、比特的几率幅表示应用于染色体的编码，使得一个染色体可以表达多个态的叠加，比传统遗传算法（GA）更具并行性。同时，利用当前最优个体的信息更新量子旋转门可加速算法收敛，引入量子交叉、变异和选择等操作可克服早熟收敛现象。,量子遗传算法及其并行机调度问题,量子位：在量子信息论中，信息的载体不再是经典的比特，而是一个一般的二态量子体系。 区别于经典比特，量子比特可以处于0，1两个本征态的任意叠加状态，而且对量子比特的操作过程中，两态的叠加振幅可以相互干涉，这就是量子相干性； 一个量子比特的状态可取值0或1，其状态表示为： 一个有个量子比特位的系统可描述为： 其中,量子遗传算法及其并行机调度问题,量子门的

6、选择有多种，如非门、受控非门、哈玛达门、旋转门等。本论文中选择量子旋转门来进行量子变异：,量子遗传算法及其并行机调度问题,以3台机器5个工件为例： （1）编码和种群初始化 量子遗传算法在并行机调度问题中的编码和解码只需要随机产生初始种群即可，令种群规模为pop_size，工件数量为n，机器数量为m，迭代次数为，交叉率为pc，变异率为pm：计算出每个工件k所需的染色体长度q：fix(log2(m)+1)，因此，总的染色体长度为m=q*n。种群规模定义为Pop_Size. （2）解码 编写解码函数：Decoding=Decode(m,n,Pop_Size,In)，把维的工件数组改写成维的机器数组，

7、为计算各个机器的加工完成时间做准备。最终生成3行5列的10个种群。,量子遗传算法及其并行机调度问题,（3）选择最优个体 用calculate函数计算种群中每个个体的各机器上各工件的起始加工时间st，完工时间c，以及整个加工过程的最大完工时间mk；用函数fitnesscalculate计算种群中各个个体的适应度；通过适应度大小的比较，获得最优个体，并记录在Best数组中。 （4）选择和交叉 由于每个工件可在任意机器上加工，因此可对两个体的基因串进行双点交叉，这样后代个体仍能满足要求。用轮盘赌方法Ga=gambling(Pop_Size,Fi)选择一个相同规模的种群Se=selection(n,Ga,Pop_Size,In)，然后，用Pc和rand(1)随机选择交叉位，进行交换操作。 对于第i和第个个体中的第j个量子个体，随机生成一个交叉位置，保持父本交叉位置前的基因片段不变，交换位置后的基因片段。,量子遗传算法及其并行机调度问题,交叉（双点交叉）,量子遗传算法及其并行机调度问题,（5）变异 种群内每个个体的每个位置都有的概率变异。对各基因，随机产生(0，1)之间的实数，若该实数小于变异概率，则生成n个1到m的随机值替代Se。最后还原个体把Se值赋给输入In.,