桶纱配重过程的计算机软件模拟
桶纱配重过程的计算机软件模拟,配重,过程,进程,计算机软件,模拟,摹拟
桶纱配重过程的计算机软件模拟1 背景介绍近几十年来,随着我国综合国力和科技水平的不断提升,纺织行业与国外先进水平的差距日渐缩小,但也存在不少问题。例如劳动力较为密集,自动化程度不高,生产效率相对较低等。因此,提高企业生产自动化和管理水平,改进产品质量和生产效率将成为整个纺织企业的发展趋势。随着市场的多元化和用工成本的不断上涨,纺织行业也需要转型升级。除了纺织机械的主要设备外,纺织生产和流通的不同环节也逐步采用智能化装置来代替人工。目前网络交流以及网上购物的发展与流行,纺织企业为了在竞争日益激烈市场中吸引潜在的客户,利用互联网平台来实现产品的推广,网上销售纺纱的店铺越来越多。互联网电子商务的迅速发展,也就出现了一些个性化的客户市场,企业要根据客户的需求生产桶纱并装箱。但是每箱桶纱的重量都不是一定的,选择哪几箱桶纱进行装箱,如何才能让客户和商贩都满意,就需要计算机程序的帮助了。2 研究现状我国是纺织大国,2015 年纺纱产量高达四千多万吨,纺纱生产的最后环节是将生产好的桶纱进行装箱,装箱前需要对装箱的桶纱重量进行测量。目前纺织行业的自动化技术水平仍然比较低,一方面由于用工成本不断上涨,纺织行业也需要进行转型升级,通过智能化装备来节省劳动力成本,提高生产效率已经成为纺织企业的必由之路。另一方面,互联网电子商务发展迅速,为了在激烈竞争的市场中增加企业的客户,利用互联网平台来实现产品的推广和销售纺纱已经越来越普遍,这种小批量个性化的需求,每箱桶纱的重量往往是不同的。采用计算机软件对桶纱装箱过程进行优化,不仅可以减轻装箱人员的工作量,还可优化装箱质量,降低装箱成本,使装箱过程快速高效,这些情况使得1用计算机辅助桶纱装箱更有必要。3 课题研究的内容本课题针对中国纺纱企业多,产量巨大,生产智能化程度需要进一步提升的现状,以纺纱生产的最后环节的桶纱装箱为研究对象,解决人工装纱工作量太大并且误差也很大的问题。通过采用计算机来管理桶纱装纱,在装箱前对桶纱的重量进行测量和控制,收集桶纱信息,采用遗传算法,利用 Matlab 软件编写程序来实现桶纱装纱过程的优化。4 课题研究的意义根据博思数据发布的2016-2022 年中国纱线产业调研现状及投资咨询战略研究报告 ,我国在 2015 年的纺纱市场生产的纱量将高达 4047.5 万吨,同比2014 年增长 4.7%。因此采用计算机软件对桶纱装箱过程进行优化是十分重要的,这不仅可以减轻装箱人员的工作量,还可以优化选择的过程,降低装箱的成本,使装箱过程高效、快速。5 技术路线运用软件开发工具,使用两种不同的方法(智能算法或穷举方法)实现桶纱配重的自动计算,软件可以设定配重范围和装箱的桶纱数量(10-50 个) ,为自动配重提供支持。最后以计算机动画的方式演示配重的计算结果。1. 收集资料。包括:(1)开发软件的相关资料。了解所用软件工具的主要功能、运行环境等;(2)收集智能算法、配种知识等信息,为软件开发提供基础。2采用 matlab 为开发平台,实现配重的自动计算软件和结果的动画显示软件的开发。26 关键技术介绍遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。1962年霍兰德(Holland)首次提出了 GA 算法的思想,它借用了仿真生物遗传学和自然选择机理,通过自然选择、遗传、变异等作用机制,实现各个个体的适应性的提高。1975 年 Holland 出版专著自然系统和人工系统的自适应 ,系统论述遗传算法,有人把 1975 年作为遗传算法的诞生年。6.1 遗传算法的基本原理遗传算法是一种优化种群规模,使其走向某一优势的过程。遗传算法运用的原理跟达尔文在进化论中提到的适者生存、优胜劣汰的原理是一样的。遗传算法就是模拟生物遗传、变异、繁衍、基因优化的过程。通过某种需求确定所需的种群要求,然后进行遗传优化,使得遗传下来的基因中符合要求的基因越来越多,最终一步步达到所需的要求。它比枚举法运算更快速,是一种全局优化方法。6.2 遗传算法的特点(1) 简捷、试用范围广,适应性强,应用领域广。(2) 是一种群体优化过程,可以同时处理大量数据; (3) 不是枚举法,是一种优化过程;(4) 适应度函数受到的约束条件少,因此在很多领域都可以使用。(5) 为了达到所需要某种要求,对种群不断地进行筛选、优化,在一定的迭代次数内选出最优解,运算量小。6.3 遗传算法的组成6.3.1 编码遗传算法将所要研究的对象(桶纱)看成是生物遗传进化过程中的染色体,然后将染色体作为初始种群进行优化。由于染色体上存在基因,因此种群优化3的过程实际上就是染色体上的基因变异的过程。遗传算法根据研究者的需要,用一定的方法将研究对象也就是染色体分成若干个部分,每个部分就叫做一个种群。每个种群中拥有的染色体的数量称为种群规模。 6.3.2 适应度函数在遗传算法中,适应度函数值是用来评价优化结果符合要求的程度大小,适应度函数值越大说明优化效果越好,种群的质量越高。适应度函数值越小,说明优化效果越差,种群的质量越低。不同的研究对象所确定的适应度值也是不一样的。不同问题不同讨论(适应度值=1/重量偏离合格区间的距离) 。 6.3.3 遗传算子 (1) 选择算子选择算子是选择优势个体的过程,通过对所研究的种群进行优胜劣汰的选择,使得符合要求的个体有更多的机会生存下来,并且把他们的基因遗传给下一代。而不符合要求的个体虽然也有机会生存下来,但是经过很多次的迭代必然所占比例逐渐减少,最终慢慢会走向消亡。(2) 交叉算子我们所说的交叉算子,实际上是根据生物遗传过程中相互配对的两个染色体可能由于某种原因交换它们的一部分基因从而产生新的个体的原理,依据一定的变异概率 Pc 通过改变研究对象的部分基因以便产生新的个体,正是由于交叉算子使得遗传算法同其他算法区别开来。遗传算法产生新个体的主要方式是通过交叉算子实现的。 (3) 变异算子通常所说的变异运算是指依据生物染色体在遗传的过程中有一定的概率 Pm将自身的一部分基因转换为其他的基因,进而产生新的种群。变异算子是遗传算法产生新个体的辅助方法。交叉算子和变异算子的互相交流与融合,共同完成了遗传算法的种群更新,使得产生符合要求的种群的数量的概率大大提升。46.3.4 运行参数 (1) M:所研究的种群的规模(2) T:遗传算法终止的迭代次数(3) Pc:染色体交叉概率(4) Pm:染色体变异概率6.4 遗传算法的选择机制遗传算法的基本原理是模仿了大自然中生物在生存繁衍过程中基因的变异现象,利用遗传算子(选择算子、交叉算子、变异算子)来改变所研究种群的基因,以便在每次的迭代过程中不断优化种群,选择更符合要求的个体生存下来并将它们的基因遗传给下一代。直到种群满足所要达到的要求。达到这种要求的种群往往比其他种群更具有某一方面的优势。6.5 遗传算法的流程遗传算法基本原理框图如图 2.1 所示。5图 2-1 遗传算法基本原理框图遗传算法的基本流程是:(1) 初始化群体;(2) 计算群体上每个个体的适应度值;(3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体;(4) 按概率进行交叉操作;(5) 按概率进行突变操作;(6) 没有满足某种停止条件,则转第(2)步,否则进入第(7)步;(7) 输出种群中适应度值最优者作为最优解。遗传算法通过不断的遗传并且积累下来,使所得到的后代种群越来越接近所需要的最优解。6.6 遗传算法的收敛性分析要进行遗传算法的收敛性分析,必须要保证初始的种群经过一定次数的迭6代循环都能达到所需要的最优解。并且必须要保证最优解包含的基因在遗传的过程不会丢失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。 6.6.1 种群规模对收敛性的影响 一般地,种群规模太小可能会导致遗传算法经过有限次的迭代进化不出符合要求的种群,使得算法的优势无法体现出来。而种群的规模和数目如果太大,会使得运算量十分巨大,加重劳动量降低效率,因此在实际应用的时候要注意选择合适的种群规模。6.6.2 选择操作对收敛性的影响选择操作通过选择能达到所需要求的个体,让他们的基因一代代地遗传下来,不进行任何的变异或者交叉。这样就会使得每一代种群中含有该基因的个体越来越多,该基因所占的百分比也越来越大,使得遗传算法以无限接近于 1的概率得到所需的最优解。6.6.3 交叉概率对收敛性的影响交叉概率主要是通过交换相互配对的染色体之间的部分基因产生新的个体。如果交叉的概率很大,那么产生新个体的速度就会太快,基因也更新很快,使得前代父本保留下来的优良基因被淡化、降低了他们遗传下去的概率。而交叉概率太小,基因更新的频率就会太慢,可能父本中一直选不出好的基因来进行遗传。因此合理的选择交叉概率是保障遗传算法正常进行、缩短迭代时间的必要条件。6.6.4 变异概率对收敛性的影响变异操作可以丰富种群的多样性。变异概率如果太小,则种群的多样性会一直得不到提高,而变异概率太大则会使种群的个体太多样性,使得遗传算法的迭代次数无限增大,使得遗传算法的操作显得十分的复杂。因此要选择合适7的变异频率限制新模式产生的频率,使得遗传算法能够更快的优化。 6.7 遗传算法的本质遗传算法的本质就是利用生物界染色体的基因在遗传过程中产生的交叉、变异的现象,通过改变所研究对象的基因从而产生新的个体,再从这些个体中选择符合要求的个体将他们的基因遗传下来,从而使包含这些优良基因的个体在种群中所占的比例逐渐增加,使问题逐渐地得到解决。 6.8 遗传算法的发展遗传欺骗问题:在遗传算法进行迭代优化的过程中,有时候可能会由于某个个体的十分突出,导致了其竞争力远远的超过了包含所需求基因的个体。从而使得遗传算法没能选择出优良基因而是选择了错误的个体的基因。因此这时候就需要对遗传算法进行改进以弥补这个不足。6.8.1 编码方式二进制编码的优点是只有 0 和 1 两个数字,编写起来方便。缺点是如果种群的规模太大,则二进制编码就会太长,显得十分冗长。也会无形中加大遗传算法的计算量。6.8.2 遗传算子6.8.2.1 排序选择 (1)按照种群的适应度函数值由高(低)到低(高)对种群里面的个体进行降(升)序排序;(2) 根据具体的实际要解决的问题,确定种群中每个个体基因遗传下来的概率。(3) 基于确定好的概率,产生新的种群。 86.8.2.2 均匀交叉 (1) 随机产生一个与种群个体染色体所含基因长度相同的二进制编码A=W1W2.Wn(2)按照如下规则从父代种群中产生新的种群,如果 Wi=0 则将父代染色体的基因一一对应的遗传给子代;如果 Wi=1,就将父代的染色体进行交叉然后在分别传给对应的子代。 6.8.2.3 逆序变异变异前:2 |5 9 | 4 3 7 |9 7 |9变异前:3 |5 9 | 3 4 5 |6 7 |96.8.3 控制参数Schaffer 建议的最优参数范围是: M = 20-100, T = 100-500, Pc = 0.4-0.9,Pm = 0.001-0.01。Srinvivas 和它的同事提出了一种叫做自适应的遗传算法,这种遗传算法的特点是它的交叉概率 Pc 和变异概率 Pm 会随着适应度函数值的变化而变化,这种遗传算法当种群无限趋于最优解的时候就会增大交叉概率 Pc 和变异概率Pm,以增大种群的丰富性以便继续优化。当种群的优化迭代次数比较少的时候就降低交叉概率 Pc 和变异概率 Pm,以便先使种群中原有的符合要求的个体优先遗传进而完成优化过程。6.8.4 执行策略(1)混合遗传算法9(2)免疫遗传算法(3)小生境遗传算法(4)单亲遗传算法(5)并行遗传算法7、要解决的技术问题7.1 桶纱装箱过程相关信息的收集。7.2 遗传算法与穷举方法的对比分析。7.3 如何用 Matlab 制作动画。7.4 选取过程要一直持续下去直到手动停止。108、日程安排序号 各阶段名称 起止日期1 调研、收集资料 2015 年 12 月 15 日 2015年 12 月 22 日2 学习资料、选择开发工具、设计软件 功能 2015 年 12 月 23 日 2016年 1 月 25 日3 编制配重的计算程序 2016 年 2 月 20 日 2016 年3 月 22 日4 编制计算机的动画演示程序 2016 年 3 月 23 日 2016 年4 月 24 日5 撰写毕业论文 2016 年 4 月 25 日 2016 年5 月 1 日6 准备答辩文件 2016 年 5 月 2 日 2016 年5 月 10 日9 参考文献1 物流配送区域划分模型及优化计算研究 重庆交通大学硕士论文 20092 基于库存策略的生产计划问题的研究 吉林 2008 43-503 遗传算法和模拟退火算法求解 TSP 的性能分析 计算机技术与发展 2009 年 11 期 97-1004 2006-5-18 唐慧丰-遗传算法原理与应用-百度文库 20125 基于 Petri 网和改进遗传算法的 AS/RS 调度系统的研究 河北 2009 301-3066 MIMO 检测算法研究与实现 西安 2010 119-1237 遗传算法的改进与算法收敛性分析 机械研究与应用 2008 年 4 期 90-92118 MIMO 检测算法研究与实现 西安 2010 156-1589 基于遗传算法的船舶电力系统网络故障重构 华中科技大学 2009 322-32310 城市交通路径诱导算法研究 长安 2009 492-49211 基于混合遗传算法的汽车企业营销资源分配策略研究 武汉 2012 67-6812 移动计算设备电能消耗估计 合肥 2007 32-3413 基于 QoS 的 Web 服务发现与组合研究 湖南 2010 68-7014 遗传算法的收敛性统一判据 电子科技大学 2010 19-2315 冲突探测与解脱技术在未来空中交通管理中的应用 计算机应用于软件 2004 年 2 期 69-7316 三相异步电动机稳态参数优化研究 黑龙江科技信息 2010 年 13 期 79-8017 磁粉检测系统中图像恢复的方法研究 学院 2011 年 11期 12-1518 一种基于遗传神经网络的股票决策的方法研究 陕西 2010 34-39 19 基于 MATLAB/Simulink/GUIDE 的 PID 工具箱的设计 山东 200820 混合式步进电动机无刷直流电机方式驱动方案及其仿真分析长春 2010 100-10321 基于 BP 神经网络的企业技术创新能力评价及应用研究 青岛 2010 87-901222 基于 MATLAB 的大学物理仿真实验研究 湖南 2008 年 5期 67-7423 IDL 与 MATLAB 的比较分析 广西 2011 95-9724 轿车后桥混流装配线规划设计及平衡研究 苏州 2004 78-8325 胡志鹏,卢险锋.提高冲裁件断面剪切面的新方法J .机械工人(冷加工 ), 2007 .(4):33-37.26 秦小琼 , 盛尚雄.冲裁间隙对产质量及模具寿命的影响J .金属成形工艺, 2004 .(3):67-69.27 肖作义 , 房晓东.对影响冲裁件质量的几个参数的讨论J .锻压机械, 2001 .(1):13-15.28 G.F.Pan, L.Lou. Finite element simulation of the effect of clearance on the forming quality in the blanking processJ.Journal of Material Processing Technology.2002.(122).29 E.Taupin, J.Breitling, et al. Material fracture and burr formation in blanking results of FEM simulaition and comparison and experimentsJ. Materials Processing Technology , 1996.(59):68-78.30 N.Hatanaka, K.Yamaguchi, N.Takakura, et al. Simulation of sheared edge fo rmation process in blanking of sheet metalsJ. Journal of Materials Processing Technology, 2003.(140):628-634.31 赵振铎,邵明志,张召铎等.金属塑性成形中的摩擦与润滑 M.北京:化学工业出版社,200432 袁清珂 . Logopress 3 冲压模设计从入门到精通M. 北京:化学工业出版社,2009:1-2.33 H.Q.Wang, G.cheng, et al. Standard of Edge Quality of Precise Part. Tool Engineering,2004,41:11-14.34 P. F. Zheng. Finite element analysis of the combined fine-blanking and extrusion process. PhD. Dissertation of Hong Kong Polytechnic 13University,2000.35 W.X.Liu. Simple Fine Blanking. Science and Technology Publishing House, Shanghai 1990, 281:111-112.桶纱配重过程的计算机软件模拟摘要我国是纺织大国,2015年纺纱产量高达四千多万吨,纺纱生产的最后环节是将生产好的桶纱进行装箱,装箱前需要对装箱的桶纱重量进行测量。目前纺织行业的自动化技术水平仍然比较低,一方面由于用工成本不断上涨,纺织行业也需要进行转型升级,通过智能化装备来节省劳动力成本,提高生产效率已经成为纺织企业的必由之路。另一方面,互联网电子商务发展迅速,为了在激烈竞争的市场中增加企业的客户,利用互联网平台来实现产品的推广和销售纺纱已经越来越普遍,这种小批量个性化的需求,每箱桶纱的重量往往是不同的。采用计算机软件对桶纱装箱过程进行优化,不仅可以减轻装箱人员的工作量,还可优化装箱质量,降低装箱成本,使装箱过程快速高效,这些情况使得用计算机辅助桶纱装箱更有必要。本文首先分析了遗传算法和穷举算法的特点,通过在装箱前对桶纱的重量进行测量和控制,收集到桶纱重量等信息,同时采用穷举法和遗传算法计算了不同数量桶纱的装箱重量,分别利用正态分布和均匀分布两种方法对桶纱重量进行随机确定,通过改变桶纱的重量分布,模拟比较了在不同数量时的计算结果。最后应用Matlab 软件编写了遗传算法进行桶纱配重的计算机模拟,并通过动画演示了计算结果。关键字:遗传算法,桶纱,装箱,动画模拟The simulation process of the computer software barrel yarn weightabstractChina is a textile country. In 2015, spinning production up to about forty million tons. The last part of the spinning production is the production of good barrels of yarn packing. Before packing, the weight of the container is measured. At present, the level of automation technology in the textile industry is still relatively low. On the one hand, due to rising labor costs, the textile industry also need to upgrade, through automation, intelligent to save labor costs, improve production efficiency has become the only way for the textile enterprises. On the other hand, the rapid development of Internet e-commerce. In order to increase business customers in the fierce market competition, the use of the Internet platform to achieve product promotion and sales of spinning has become more and more common. This small batch of individual needs, the weight of each box of barrels of yarn is often different. Using the computer software to optimize the packing process of the drums, not only can reduce the workload of the staff, but also optimize the packing quality, reduce the packing cost, so that the packing process is efficient and fast.This paper first analyzes the characteristics of genetic algorithm and exhaustive algorithm. By measuring and controlling the weight of the container before packing, the weight of the bucket is collected. At the same time the exhaustive method and genetic algorithm to calculate the different number of barrels of yarn packing weight, respectively, using positive normal distribution and uniform distribution two methods of barrel yarn weight were randomly determined. By changing the weight distribution of the bucket, the results of the calculation are compared. Finally, using genetic algorithm written MATLAB software barrel yarn weight of computer simulation, and the animation demonstration of the calculation results.Key words: genetic algorithm, bucket yarn, packing, animation simulation目录1 绪论 -11.1 引言 -11.2课题研究的背景 -11.3课题研究的意义 -11.4课题研究的内容 -22 遗传算法(GA)简介 -32.1 遗传算法的基本原理 -32.2 遗传算法的特点 -32.3 遗传算法的组成 -42.3.1 编码 -42.3.2 适应度函数 -42.3.3 遗传算子 -42.3.4 运行参数 -52.4 遗传算法的选择机制 -52.5 遗传算法的流程 -52.6 遗传算法的收敛性分析 -72.6.1 种群规模对收敛性的影响 -72.6.2 选择操作对收敛性的影响 -72.6.3 交叉概率对收敛性的影响 -72.6.4 变异概率对收敛性的影响 -82.7 遗传算法的本质 -82.8 遗传算法的发展 -82.8.1 编码方式 -82.8.2 遗传算子 -92.8.3 控制参数 -92.8.4 执行策略 -103 桶纱配重过程的计算机模拟软件的实现 -113.1 Matlab简介 -113.2 Matlab的基本功能 -113.3 Matlab的应用领域 -123.4总流程图 -133.5 算法设计 -133.5.1 编码方法 -133.5.2 变异 -143.5.3 交叉 两点交叉 -143.5.4 解码 -153.5.5 选择 -153.6 程序编写的要求 -173.7程序运行后的结果 -184 结论与展望 -21参考文献 -23致 谢 -25附录1 -26附录2 -3411 绪论1.1 引言近几十年来,随着我国综合国力和科技水平的不断提升,纺织行业与国外先进水平的差距日渐缩小,但也存在不少问题。例如劳动力较为密集,自动化程度不高,生产效率相对较低等。因此,提高企业生产自动化和管理水平,改进产品质量和生产效率将成为整个纺织企业的发展趋势。1.2课题研究的背景随着市场的多元化和用工成本的不断上涨,纺织行业也需要转型升级。除了纺织机械的主要设备外,纺织生产和流通的不同环节也逐步采用智能化装置来代替人工。目前网络交流以及网上购物的发展与流行,纺织企业为了在竞争日益激烈市场中吸引潜在的客户,利用互联网平台来实现产品的推广,网上销售纺纱的店铺越来越多。互联网电子商务的迅速发展,也就出现了一些个性化的客户市场,企业要根据客户的需求生产桶纱并装箱。但是每箱桶纱的重量都不是一定的,选择哪几箱桶纱进行装箱,如何才能让客户和商贩都满意,就需要计算机程序的帮助了 1。1.3课题研究的意义根据博思数据发布的2016-2022年中国纱线产业调研现状及投资咨询战略研究报告,我国在2015年的纺纱市场生产的纱量将高达4047.5万吨,同比2014年增长4.7%。因此采用计算机软件对桶纱装箱过程进行优化是十分重要的,这不仅可以减轻装箱人员的工作量,还可以优化选择的过程,降低装箱的成本,使装箱过程高效、快速。21.4课题研究的内容本课题针对中国纺纱企业多,产量巨大,生产智能化程度需要进一步提升的现状,以纺纱生产的最后环节的桶纱装箱为研究对象,解决人工装纱工作量太大并且误差也很大的问题。通过采用计算机来管理桶纱装纱,在装箱前对桶纱的重量进行测量和控制,收集桶纱信息,采用遗传算法,利用Matlab软件编写程序来实现桶纱装纱过程的优化。32 遗传算法(GA)简介遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法 Error! Reference source not found.。 1962年霍兰德(Holland)首次提出了GA算法的思想,它借用了仿真生物遗传学和自然选择机理,通过自然选择、遗传、变异等作用机制,实现各个个体的适应性的提高。1975年Holland出版专著自然系统和人工系统的自适应,系统论述遗传算法,有人把1975年作为遗传算法的诞生年。2.1 遗传算法的基本原理遗传算法是一种优化种群规模,使其走向某一优势的过程。遗传算法运用的原理跟达尔文在进化论中提到的适者生存、优胜劣汰的原理是一样的。遗传算法就是模拟生物遗传、变异、繁衍、基因优化的过程。通过某种需求确定所需的种群要求,然后进行遗传优化,使得遗传下来的基因中符合要求的基因越来越多,最终一步步达到所需的要求。它比枚举法运算更快速,是一种全局优化方法 2。2.2 遗传算法的特点(1) 简捷、试用范围广,适应性强,应用领域广;(2) 是一种群体优化过程,可以同时处理大量数据; (3) 不是枚举法,是一种优化过程;(4) 适应度函数受到的约束条件少,因此在很多领域都可以使用;(5) 为了达到所需要某种要求,对种群不断地进行筛选、优化,在一定的迭代次数内选出最优解,运算量小 Error! Reference source not found.。42.3 遗传算法的组成2.3.1 编码遗传算法将所要研究的对象(桶纱)看成是生物遗传进化过程中的染色体,然后将染色体作为初始种群进行优化。由于染色体上存在基因,因此种群优化的过程实际上就是染色体上的基因变异的过程 4。遗传算法根据研究者的需要,用一定的方法将研究对象也就是染色体分成若干个部分,每个部分就叫做一个种群。每个种群中拥有的染色体的数量称为种群规模 6。 2.3.2 适应度函数在遗传算法中,适应度函数值是用来评价优化结果符合要求的程度大小,适应度函数值越大说明优化效果越好,种群的质量越高。适应度函数值越小,说明优化效果越差,种群的质量越低。不同的研究对象所确定的适应度值也是不一样的。不同问题不同讨论(适应度值=1/重量偏离合格区间的距离)。 2.3.3 遗传算子 (1) 选择算子选择算子是选择优势个体的过程,通过对所研究的种群进行优胜劣汰的选择,使得符合要求的个体有更多的机会生存下来,并且把他们的基因遗传给下一代。而不符合要求的个体虽然也有机会生存下来,但是经过很多次的迭代必然所占比例逐渐减少,最终慢慢会走向消亡。(2) 交叉算子我们所说的交叉算子,实际上是根据生物遗传过程中相互配对的两个染色体可能由于某种原因交换它们的一部分基因从而产生新的个体的原理,依据一定的变异概率Pc通过改变研究对象的部分基因以便产生新的个体,正是由于交叉算5子使得遗传算法同其他算法区别开来。遗传算法产生新个体的主要方式是通过交叉算子实现的 8。 (3) 变异算子通常所说的变异运算是指依据生物染色体在遗传的过程中有一定的概率Pm将自身的一部分基因转换为其他的基因,进而产生新的种群。变异算子是遗传算法产生新个体的辅助方法。交叉算子和变异算子的互相交流与融合,共同完成了遗传算法的种群更新,使得产生符合要求的种群的数量的概率大大提升。2.3.4 运行参数 (1) M: 所研究的种群的规模(2) T:遗传算法终止的迭代次数(3) Pc:染色体交叉概率(4) Pm:染色体变异概率2.4 遗传算法的选择机制遗传算法的基本原理是模仿了大自然中生物在生存繁衍过程中基因的变异现象,利用遗传算子(选择算子、交叉算子、变异算子)来改变所研究种群的基因,以便在每次的迭代过程中不断优化种群,选择更符合要求的个体生存下来并将它们的基因遗传给下一代。直到种群满足所要达到的要求。达到这种要求的种群往往比其他种群更具有某一方面的优势 9。2.5 遗传算法的流程遗传算法基本原理框图如图2.1所示。6图2-1 遗传算法基本原理框图遗传算法的基本流程是:(1) 初始化群体;(2) 计算群体上每个个体的适应度值;(3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体;(4) 按概率进行交叉操作;(5) 按概率进行突变操作;(6) 没有满足某种停止条件,则转第(2) 步,否则进入第(7)步;(7) 输出种群中适应度值最优者作为最优解。7遗传算法通过不断的遗传并且积累下来,使所得到的后代种群越来越接近所需要的最优解。2.6 遗传算法的收敛性分析要进行遗传算法的收敛性分析,必须要保证初始的种群经过一定次数的迭代循环都能达到所需要的最优解。并且必须要保证最优解包含的基因在遗传的过程不会丢失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率 11。 2.6.1 种群规模对收敛性的影响 一般地,种群规模太小可能会导致遗传算法经过有限次的迭代进化不出符合要求的种群,使得算法的优势无法体现出来。而种群的规模和数目如果太大,会使得运算量十分巨大,加重劳动量降低效率,因此在实际应用的时候要注意选择合适的种群规模 12。2.6.2 选择操作对收敛性的影响选择操作通过选择能达到所需要求的个体,让他们的基因一代代地遗传下来,不进行任何的变异或者交叉。这样就会使得每一代种群中含有该基因的个体越来越多,该基因所占的百分比也越来越大,使得遗传算法以无限接近于1的概率得到所需的最优解。2.6.3 交叉概率对收敛性的影响交叉概率主要是通过交换相互配对的染色体之间的部分基因产生新的个体。如果交叉的概率很大,那么产生新个体的速度就会太快,基因也更新很快,使得前代父本保留下来的优良基因被淡化、降低了他们遗传下去的概率。而交叉概率太小,基因更新的频率就会太慢,可能父本中一直选不出好的基因来进行遗传。因此合理的选择交叉概率是保障遗传算法正常进行、缩短迭代时间的必要条件。82.6.4 变异概率对收敛性的影响变异操作可以丰富种群的多样性。变异概率如果太小,则种群的多样性会一直得不到提高,而变异概率太大则会使种群的个体太多样性,使得遗传算法的迭代次数无限增大,使得遗传算法的操作显得十分的复杂。因此要选择合适的变异频率限制新模式产生的频率,使得遗传算法能够更快的优化 13。 2.7 遗传算法的本质遗传算法的本质就是利用生物界染色体的基因在遗传过程中产生的交叉、变异的现象,通过改变所研究对象的基因从而产生新的个体,再从这些个体中选择符合要求的个体将他们的基因遗传下来,从而使包含这些优良基因的个体在种群中所占的比例逐渐增加,使问题逐渐地得到解决 14。 2.8 遗传算法的发展遗传欺骗问题:在遗传算法进行迭代优化的过程中,有时候可能会由于某个个体的十分突出,导致了其竞争力远远的超过了包含所需求基因的个体。从而使得遗传算法没能选择出优良基因而是选择了错误的个体的基因。因此这时候就需要对遗传算法进行改进以弥补这个不足。2.8.1 编码方式二进制编码的优点是只有0和1两个数字,编写起来方便。缺点是如果种群的规模太大,则二进制编码就会太长,显得十分冗长。也会无形中加大遗传算法的计算量。2.8.2 遗传算子2.8.2.1 排序选择 (1)按照种群的适应度函数值由高(低)到低(高)对种群里面的个体进行降(升)序排序;9(2) 根据具体的实际要解决的问题,确定种群中每个个体基因遗传下来的概率。(3) 基于确定好的概率,产生新的种群 15。 2.8.2.2 均匀交叉 (1) 随机产生一个与种群个体染色体所含基因长度相同的二进制编码A=W1W2.Wn(2)按照如下规则从父代种群中产生新的种群,如果Wi=0则将父代染色体的基因一一对应的遗传给子代;如果Wi=1,就将父代的染色体进行交叉然后在分别传给对应的子代。 2.8.2.3 逆序变异变异前:2 |5 9 | 4 3 7 |9 7 |9变异前:3 |5 9 | 3 4 5 |6 7 |92.8.3 控制参数Schaffer建议的最优参数范围是: M = 20-100, T = 100-500, Pc = 0.4-0.9,Pm = 0.001-0.01。Srinvivas和它的同事提出了一种叫做自适应的遗传算法,这种遗传算法的特点是它的交叉概率Pc和变异概率Pm会随着适应度函数值的变化而变化,这种10遗传算法当种群无限趋于最优解的时候就会增大交叉概率Pc和变异概率Pm,以增大种群的丰富性以便继续优化。当种群的优化迭代次数比较少的时候就降低交叉概率Pc和变异概率Pm,以便先使种群中原有的符合要求的个体优先遗传进而完成优化过程 16。2.8.4 执行策略(1)混合遗传算法(2)免疫遗传算法(3)小生境遗传算法(4)单亲遗传算法(5)并行遗传算法113 桶纱配重过程的计算机模拟软件的实现3.1 Matlab简介Matlab程序是由 Clever Moler和它的同事在 20世纪 70年代共同研究创立出来的。他们之所以给这个程序取名为Matlab ,是为了将矩阵和实验室的两个英文单词组合在一起。以后几年,Matlab作为免费软件在大学里被广泛使用,深受大学生的喜爱。1984年,Mathworks公司成立了,该公司的创办人正是Clever 和他的同事John Little。公司成立之后, Clever和他的同事马上着手将Matlab推向大众,并且在宣传推广的同时,他们仍然致力于Matlab软件的改进和完善。Matlab 软件经过几个版本的升级进化之后,功能越来越完善,操作也越来越便捷。逐渐成为最流行的办公软件。Matlab由于具有处理速度快,效率高的特点,使得软具有很强的市场竞争力,因此很快就占据了绝大部分的软件市场。Matlab 软件的不断完善不仅方便了人们的生活,也优化了程序编写的过程 17。3.2 Matlab的基本功能Matlab程序通过接收用户发布的各种指示和命令,运用一定的程序,输出计算结构,完成计算过程并输出计算结果 18。具体来说,Matlab具有以下功能:(1)运算矩阵的功能(2)将数据可视化的功能(3)绘图功能12(4)完善的工具箱(5)GUI设计(6)Simulink仿真通过运用Matlab 这些强大的功能,世界各地从事不同工作的人员可以被联系到一起,他们可以在同一个平台下共同完成一向创作或者研究。Matlab软件的功能非常强大,涉及到的领域包括诸如航天、交通、信息等。Mathworks公司刚刚推出了Matlab r2007版本产品,即Matlab r2007,增加了两个新产品模块,同时还升级和修正了82个产品模块。3.3 Matlab的应用领域(1)数据分析(2)数值和符号计算(3)建模、仿真和原型开发(4)控制系统设计(5)工程与科学绘图(6)图形用户界面设计等(7)数据图像信号处理(8)财务工作Matlab产品涉及领域的广泛以及功能的不断完善,使得Matlab 软件在激烈的市场竞争中越来越具有竞争力,不断的摆脱其他竞争对手,一枝独秀。然而,尽管Matlab 软件的研发已经取得了如此重大的成就,但是作为软件研发者的Clever和他的同事并没有忘记对软件的继续开发和利用。如今的Matlab已经和其他的软件逐渐的融为一体,在互相汲取彼此优点,弥补缺点的过程中共同发展 19。133.4总流程图开 始设 定 仿 真 数 据设 置 遗 传 算 法 参 数初 始 化 染 色 体遗 传 算 法 迭 代染 色 体 变 异染 色 体 交 叉染 色 体 解 码计 算 目 标 函 数染 色 体 选 择遗 传 算 法 迭 代完 成 ?输 出 结 果结 束NY取 前 n个 装 箱 计 算 总 重 量计 算 是 否 满 足 约 束图3-1 遗传算法模拟装箱过程的总流程图3.5 算法设计3.5.1 编码方法每次称取m个桶纱, 每箱装n个桶纱, 则编码长度为m,基因为1至m的整数的一个排序如m=5, n=4,则一个合法的染色体可表示为1,3,2,5,4143.5.2 变异 采用两点互易进行变异:(1) 产生2个随机自然数 r1,r2;(2) 交换第r1位和r2位的基因 。举例:r1=2, 那么染色体的变异为1,3,2,5,41, 5,2,3,43.5.3 交叉 两点交叉(1) 随机选择两个染色体作为父本;(2) 产生2个随机自然数 r1和r2 ;(3) 将两个父本染色体r1至r2之间的基因片段进行交换, 得到两个子代染色体,并对得到的两个染色体进行修订处理,使得不发生冲突。举例:选择的两个父本染色体1,3,2,5,4 1,2,4,5,3r1=2, r2=4那么交叉过程为1,3,2,5,4 1,2,4,5,3交叉后1, 2,4,5,4 1, 3,2,5,3 修补 1, 2,4,5,4 1, 3,2,5,3修补方法: 交叉后, 取交叉片段的补集重新随机排列到非交叉片段153.5.4 解码对每个染色体, 取其1至n位的基因, 计算总重量, 再计算这个重量偏离目标区间的距离作为目标函数。(3-1)(3-2)其中 为基因 代表的桶纱的重量 ;w为n个桶纱的重量;n为每箱装的桶纱的重量;Wmax为装箱允许的最大重量;Wmin为装箱允许的最小重量;式(3-2)为目标函数, 其意义为最小化装箱重量w与允许区间的距离, 也就是越接近允许区间越好。3.5.5 选择轮盘赌选择也被叫做比例选择算子基本思想:种群中每个个体被选中的概率与其适应度函数值是有关系的,一般是正比的关系。设群体大小为popsize,个体i的适应度为Fi,则个体i被选中遗传到下一代群体的概率为:16(3-3)工作过程:设想群体全部个体的适应性分数由一张饼图来代表 ,见图3-2。图3-2 群体全部个体的适应性分数饼图中的每一个小块都代表了一条染色体,块的大小与染色体的适应性分数成正比。选取的过程就是转动圆盘,等到圆盘停止的时候观察指针停在哪个小块上,然后就选取该小块所对应的那一条染色体。17表3-1 轮盘赌选择法的选择概率计算个体 1 2 3 4 5 6适应度 2 1.8 1.6 1.4 1.2 1选择概率 0.18 0.16 0.15 0.13 0.11 0.09累计概率 0.18 0.34 0.49 0.62 0.73 0.82续表3-1个体 7 8 9 10 11适应度 0.8 0.6 0.4 0.2 0.1选择概率 0.07 0.06 0.03 0.02 0累计概率 0.89 0.95 0.98 1 13.6 程序编写的要求软件的功能要求:每个桶纱的重量范围为2.481-2.580公斤,一次称取20个桶纱(20个传感器),运用遗传算法从20个桶纱中选出重量范围之和在45.1-45.5公斤之间的18个桶纱(只选1组)进行装箱,选出之后重新换20个桶纱再次选择,但在运用遗传算法选择之前先用穷举的方法选择一遍,一是为了确定是否可以选出这样的18个桶纱,二是为了和遗传算法进行对比,比较二者的区别和相似之处,桶纱重量分别运用均匀分布和正态分布进行随机确定,程序要求重复运行直到手动停止为止。程序最后要用动画显示出选取的过程并显示出每种算法选择所用的时间,以便比较。183.7程序运行后的结果编写程序后在Matlab 环境下运行,首先可以看到界面有20个桶纱分成两排,然后开始穷举的方法,红色的那两个桶纱是不被选取的桶纱,桶纱的上面红色的字会显示出已选的那18个桶纱的总重量。当所有的18个桶纱都被选取之后,界面会跳转并显示出通过穷举算法选出18个符合要求的桶纱所需要的时间(有可选的装箱方案),并且在下面显示出是哪18个桶纱符合要求,之后程序界面会跳转到遗传算法选取的结果以及所需要的时间,最后会弹出对话框询问是否继续选取或者选择退出。正态分布穷举方法选取的过程截图19正态分布遗传算法的运行结果图正态分布选取的符合要求的桶纱图前(选取前18个)均匀分布穷举算法运行过程截图20均匀分布遗传算法运行结果图均匀分布选取的符合要求的桶纱图(选取前18个)从图中可以看出来,正态分布中穷举的方法所用的时间为0.0026726s ,遗传算法所用的时间为0.39624s,选出的18个桶纱编号为 5、11、13、18、9、15、7、14、8、12、20、19、4、2、10、3、16、17(最后两个编号为6、1的桶纱是不被选取的)。均匀分布中穷举方法选取所用的时间为0.0041709s ,遗传算法所用的时间为0.39614s,选出的18个桶纱的编号分别为 4、19、2、3、14、20、6、13、10、7、15、18、17、9、5、1、8、11(12和16两个桶纱不被选取)。经过对比分析我们可以看出来不论桶纱的重量采用何种分布方法,遗传算法的选取时间都要长于穷举的方法。214 结论与展望运用Matlab软件,分别利用正态分布和均匀分布两种方法对桶纱重量进行随机确定,每次供选择的20个桶纱的重量也是随机选取的。通过程序的运行结果可以看到从20个桶纱中选取18个桶纱进行装箱,枚举的方法每次都可以选出符合重量范围在45.1-45.5公斤之间的18个桶纱进行装箱。之后进行的均匀分布和正态分布的遗传算法也可以选出,并且可以看出枚举的方法比遗传算法用到的时间要短。但这并不是说枚举的方法就比遗传算法的优化效果好。众所周知枚举法的运算量是很大的要大于遗传算法,而遗传算法又相对复杂,产生这种结果的主要原因是由于桶纱只有20个,从20个桶纱中选出18个桶纱进行装箱,显示不出枚举法运算量大的劣势,反而却可以体现出遗传算法的复杂性,因此会产生枚举法优于遗传算法的结果。但如果我们把桶纱换成1000个,遗传算法绝对是要大大优于枚举法的。本文基于遗传算法的桶纱装箱解决方案,可为企业提高竞争力,发展前景良好。在刚开始做这个桶纱配重的毕业设计的时候,当时跟老师商量之后,由于要考虑成本,所以本打算用20个传感器对桶纱进行称重,然后先用穷举的方法选,如果能选出来就继续用遗传算法选,如果选不出来就换掉其中的10个,但换下来的这10个桶纱也可以参与选择。但是实际操作的时候却发现如果这样做那么换下来的那10个桶纱的编号会非常麻烦,经过和老师再次商讨之后决定换下来的10个桶纱不参与选择就从20个桶纱里面选。从这里我知道了有时候看上去理所当然的事情其实等你实际操作的时候会遇到各种各样的困难,任何事情都不像你想象中的那么简单,只有自己亲自动手去尝试了,才能真正收获其中的乐趣。22虽然我的毕业设计完成了,但是我感觉还是存在很多不足,比如由于成本和技术的约束,每次供选取的桶纱只有20个,选取的方法有190种,由于染色体少导致得出穷举的方法要优于遗传算法的结果。但是我们知道,如果增加桶纱的数量到足够大,那么遗传算法应该是大大优于穷举的方法。但是考虑到每增加一个桶纱,穷举选取的方法就会成倍的增长,我们目前的技术条件还达不到能满足这样的要求。因此当桶纱数据足够大的时候,编写程序以及实际操作会遇到什么样的困难仍然是一个未知数。23参考文献1 王勇. 物流配送区域划分模型及优化计算研究. 重庆交通大学硕士论文. 2009.2 朱学良. 基于库存策略的生产计划问题的研究. 吉林2008. 43-50.3 何伟兵. 遗传算法和模拟退火算法求解TSP 的性能分析. 计算机技术与发展. 2009,11: 97-100.4 2006-5-18唐慧丰-遗传算法原理与应用-百度文库 . 2012.5 李玮. 基于Petri网和改进遗传算法的AS/RS调度系统的研究.河北. 2009. 301-306.6 徐波. MIMO 检测算法研究与实现. 西安. 2010. 119-123.7 张建平. 黄晓云. 遗传算法的改进与算法收敛性分析. 机械研究与应用. 2008年4期. 90-92.8 周瑛. 陈基漓. MIMO检测算法研究与实现. 西安. 2010. 156-158.9 梁阔洋. 基于遗传算法的船舶电力系统网络故障重构. 华中科技大学. 2009. 322-323.10 陈俊男. 城市交通路径诱导算法研究. 长安. 2009. 492-492.11 顾凯. 基于混合遗传算法的汽车企业营销资源分配策略研究. 武汉. 2012. 67-68.12 于淑瑶. 移动计算设备电能消耗估计. 合肥. 2007. 32-34.13 邓生. 基于QoS 的Web服务发现与组合研究. 湖南 . 2010 68-70.2414 朱寒晨. 遗传算法的收敛性统一判据. 电子科技大学. 2010. 19-23.15 罗俊. 冲突探测与解脱技术在未来空中交通管理中的应用. 计算机应用于软件. 2004年2期. 69-73.16 张雅荣 三相异步电动机稳态参数优化研究. 黑龙江科技信息. 2010年13期. 79-80.17 周佳颖. 磁粉检测系统中图像恢复的方法研究. 学院. 2011年11期. 12-15.18 钟科艾. 一种基于遗传神经网络的股票决策的方法研究. 陕西. 2010. 34-39. 19 马从国. 基于MATLAB/Simulink/GUIDE的PID工具箱的设计. 山东. 2008.20 玉洁. 曾宇. 混合式步进电动机无刷直流电机方式驱动方案及其仿真分析. 长春. 2010. 100-103.21 高曼. 基于BP神经网络的企业技术创新能力评价及应用研究. 青岛. 2010. 87-90.22 吴永刚. 基于MATLAB的大学物理仿真实验研究. 湖南. 2008年5期. 67-74.23 高大鹏. 王欣. 朱清新. IDL与MATLAB的比较分析. 广西. 2011. 95-97.24 双永强. 轿车后桥混流装配线规划设计及平衡研究. 苏州. 2004 .78-83.致 谢25当我写到的论文写到这里的时候,意味着我的毕业设计就快要完结,也意味着我大学四年的生活即将终结。在此我要感谢在大学这四年的学习生活中陪伴我并且在我遇到困难时帮助过我的老师和同学,没有你们的帮助,我是不可能在四年的大学生活中收获这么多的知识、快乐和友谊。在此我要特别感谢我的毕业设计的指导老师陈晓川老师。在我刚开始做毕业设计的时候,当时由于找工作以及对毕业设计的态度不认真等等各种原因没有与老师及时的沟通,导致我的毕业设计进度十分的缓慢。在中期答辩之后的时间里,陈老师在百忙之中专门抽出宝贵的时间指导我的毕业设计,给我分析编写程序的要点以及注意的事项。每次去跟老师交流我都能很快的找到程序中存在的不足和缺陷,然后加以修改。本以为看上去十分简单的问题,但是实际操作的时候却显得很麻烦。比如当初编写从20个桶纱选取18个桶纱的程序的时候,本以为选出来的概率很小,需要换掉其中的10个桶纱再换上去10个,然后从30个桶纱中选取。但是实际编写的时候发现,20个桶纱选取18个装箱有190种选取方法,概率还是很大的,并且如果换掉10个再换上去10个那么每次换下去的桶纱要进行编号,这会使得程序编写极为复杂,编写桶纱编号也有诸多不便。和老师研究讨论之后,我们放弃了之前的选取想法,直接编写程序从20个桶纱中选取18个。程序编写完成之后,进行了动画分析,发现每次都可以选出符合重量范围的18箱桶纱。由此可见,实践比理论更加重要。这次的毕业设计我感触颇深,从翻译外文文献到搜集桶纱的相关信息、以及最后的Matlab 编写程序和制作动画都使我懂得了很多,也很好的锻炼了自己分析和运算的能力。这次毕业设计的成功完成,是离不开老师和同学对我的帮助的支持的。这次毕业设计也使我懂得了分析认真数据、自己动手操作的重要性。它告诉了我做任何事情都要一步步慢慢来,做事情是没有捷径可走的,只有自己亲自去实践了,才能知道哪一种方法更好、更适合。就像刚开始我们都以为遗传算法要优于穷举的算法一样,但是实际操作之后才发现,当问题维度很小的时候,遗传算法并不优化,相反穷举的算法要优于遗传算法。只有当问题的维度足够大的时候,遗传算法才会优于穷举的方法。所以在今后我要养成自己动手、认真实践的习惯,做事情不能想当然,只有自己动手实践才能发现问题所在,找到解决的办法,从而开始通往成功的大门。26附录1正态分布算法的matlab程序% 遗传算法 优化函数clc;close all;clear all;%清除变量% rand(seed,100);% 每个桶纱的重量为2.5公斤左右% 每箱装18个桶纱% 要求装箱后的重量范围:45.1-45.5公斤% 画桶纱 矩形代替h1=10;%桶纱高w1=7;%桶纱宽h2=3;% 传感器高w2=9;% 传感器宽N1=20;% 一次性称的个数N2=10;% 新增个数x1 = linspace(0,50*N1);x2 = linspace(-1,50*N1+1);x011 = x1(1:N1/2);y011 = h2*ones(1,N1/2);x012 = x011 ;y012 = y011+20;
收藏