数学建模论文-基于改进的遗传算法的打孔机最优作业方案设计.doc

2012“深圳杯”全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛区设置报名号的话）： 10038 所属学校（请填写完整的全名）： 西安交通大学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 5 月 7 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2012“深圳杯”全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）：基于改进的遗传算法的打孔机最优作业方案设计 摘要 本文的背景是印刷电路板过孔孔群的加工问题。通过建立单孔模型成功将具有复杂加工要求的电路板加工路径规划问题转化为常见的循环旅行商问题（）和多旅行商问题（），我们研究了使用单钻头加工和多钻头加工时的加工路线优化问题。 我们首先根据孔的加工要求和孔的类型对所给待加工孔群进行了重新定义，将孔的孔型和所需加工刀具都作为孔的特征，把需要多把刀加工的孔拆分为由孔型和加工刀具共同区分的多个孔，并使用逻辑值对孔是否已打进行标记，从而对孔进行扩展，使复杂孔群成为只需单一刀具一次加工的孔群，得到了单孔孔群模型。在单孔模型中，钻头在孔间的可达与否受加工刀序的控制，这在单孔孔群模型中成为孔间加工的关联问题，可以通过访问标记进行。 单钻头对线路板加工时，使用单孔模型后，孔的相异性变得清晰，孔与孔间的关系我们建立了权值计算函数模型，把单孔孔群看成了点间关联的寻找最优加工路径的问题成为具有访问顺序的。对孔扩展后单孔的规模为，属于大规模的最优路径问题单纯遗传算法的有哪些信誉好的足球投注网站效率较低，我们将模拟退火算法与遗传算法相结合，并在其选择的方式上进行了时间节约化的改进，使计算时间复杂度有所下降，有效提高了最优解的求解效率，在计算机上对所有点全部有哪些信誉好的足球投注网站，约为半个小时，表明其有较高的求解效率。 多钻头打孔时的路径规划成为多旅行商的最优旅行线路问题，在对路径的规划上，对了第一问的遗传算法中的染色体产生形式和适应度函数进行修改，通过插入虚拟点的方法，使多钻头的影响变成单一路径求解，在相应的限制下找到最好的合作路线。 　 关键字：单孔孔群模型　问题　遗传算法　模拟退火算法　最优化　 1 问题重述 现有一类给印刷电路板打过孔的打孔机，现在普遍采用单钻头作业。它的某种钻头，上装有8种刀具… , h，依次排列呈圆环状这由生产工艺决定 问题一中要求在单钻头作业的情况下，根据提供了某块印刷线路板过孔中心坐标的数据单钻头作业 问题二中，为提高效能现在设计一双钻头的打孔机，两钻头可以同时作业，。两钻头间距于3cm两钻头合作间距钻头作业传统单钻头打孔机生产效能提高多少？）打孔机的两钻头合作间距对作业路线影响 2 符号说明 表一：本文使用的主要符号及说明 单孔编号数组 工作时间目标时间 适应度函数名 线路板的平面区域 刀具编号集合 孔类型集合 单孔孔群集合 刀具编号 孔型编号 访问标记逻辑值 孔间行进时间 孔间