深度优先搜索算法和A*算法在迷宫搜索中的仿真研究

本文通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在标准迷宫中的应用,在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性--未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度.机器人搜索的目的是为了进行搜救,因此机器人应该要在尽量短的时间内搜索到目标物并将目标物带回.通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法.     

双边装配线第二类平衡问题研究

与传统的单边装配线平衡问题不同,双边装配线平衡不仅要考虑任务优先顺序关系,而且要考虑任务操作方位以及双边并行作业的要求.为有效地解决双边装配线第二类平衡问题,建立了数学模型,并提出一种基于归组策略的启发式平衡算法.该算法利用图深度优先搜索方法,将任务进行归组,然后运用一系列启发式规则对组进行选择分配.最后,通过在某装载机总装生产线上的应用,验证了算法的有效性.     

同顺序加工调度问题的一种精确求解方法

同顺序加工调度问题是NP问题,分析了这类问题的特点及求解的难点,结合广度优先搜索方法的特点,提出了启发式双侧广度优先搜索方法,混合使用动态规划方法、下界算法和近似求解方法求解同顺序加工调度问题.实验结果表明,启发式双侧广度优先搜索方法求解同顺序加工调度问题时,可以大大减少搜索次数,适合于求解工序较少的同顺序加工调度问题;如果下界算法较好,还能快速求解工序较多的同顺序加工调度问题.     

一维下料问题的多叉树遍历算法研究

切割条形材料,获得不同长度工件问题普遍存在。为满足原材料利用率最大的实际加工要求,将数据建立为多叉树模型,添加剪枝优化条件,使用深度优先遍历,递归调用深度优先遍历函数,搜索全局最优解,即最优化的下料方案。使用其他论文中的实例,对比启发式多级序列线性优化方法的运算结果。对比结果表明:多叉树遍历算法的材料利用率最高、结果更优。     

基于模型推理的参数再设计方法研究

采用定性因果推理和启发式搜索的方法,提出了一种自动生成参数再设计方案的关键技术。以一个减速器再设计问题为例,探讨了基于参数的再设计问题的基本形式,建立了基于因果影响关系的再设计模型。描述了生成再设计方案的算法,包括再设计方案综合效果的估算方法和基于最佳-优先搜索的方法,分析了算法的完备性和复杂度问题。以减速器再设计的例子演示了算法的有效性和该工具的功能。     

机械运动方案知识库的建立和机构自动化型综合

用数据标准化技术和组合分类法对概念设计运动行为—结构映射域中的运动行为知识和机构知识进行合理分类,并建立相应的计算机编码和存储原则,使得机械运动方案在求解的初期快速高效地构建满足基本运动特性的初步解集合。然后采用启发式运动行为匹配传播原理和匹配传播真值表进行机构型综合,建立了基于启发式运动行为匹配传播原理的机械运动方案自动化知识库推理系统,通过深度优先搜索策略,按自顶向下的设计流程在4个层次上进行匹配,符合设计者创新思维的规律。如果较高一级的匹配不成功,则自动转为下一等级的匹配。根据匹配传播真值表,运动行为ID中非零元素值(如“2”或“3”)一旦在匹配过程中出现,则一直会传播下去,保留在最终的搜索结果编码中,匹配传播原理的启发式机制将复杂运动需求分解为简单的运动需求后进行求解,从而实现了自顶向下的复杂运动需求的求解。更有利于计算机辅助自动求解过程的实现。最后列举了实例证明方法的实用、可行。     

基于递归循环的层次化爆炸图自动生成方法

提出以递归循环和深度优先搜索层次化装配序列的策略自动生成复杂产品层次化爆炸图的方法。为使设计结构符合装配规划的要求,设计了可方便定义子装配体和编辑装配树的装配结构重构功能。为避免重复的干涉检测,研究干涉矩阵合成方法,通过对原始装配关系信息的整合,柔性化生成面向层次化结构的装配关系矩阵。为降低大规模序列规划问题的复杂性,将整体规划任务分解为若干个及若干层级子任务,子任务内采用多规则筛选算法,以基于干涉矩阵的几何可行性为前提,并行性、连续性、稳定性和方向性等为优化筛选指标,循环构建序列。提出递归爆炸算法,循环对层次化装配序列进行深度优先搜索,实时计算已爆炸零部件的累积包围盒,从而确定待爆炸零件位移矢量,自动生成间隔均匀有序、结构紧凑且空间层次感强的爆炸图。开发了基于Siemens NX的装配规划系统Auto Assem,以减速器及汽车部件实例验证了方法的有效性。     

基于几何推理有向图的装配序列规划

有向图是表示机械产品装配关系的有力结构,为减少有向图构造时的工作量,从拆装路径的空间可行性出发,提出了一种新的构造方法,从产品模型中提取装配关系矩阵并初始化有向图,建立层次化的结构,对产品中的零件进行路径规划,结合路径查找结果逐层填充节点,根据不同层次中节点的关系补充零件间的优先约束,从而生成相对完善的有向图。该方法基于CATIA二次开发自动进行几何推理,可用于存在复杂拆装路径的机械产品,具有良好的通用性。有向图拓扑排序生成的序列质量较高,运用粒子群算法对这些序列进行启发式搜索,相比传统方式缩小了搜索空间,能够更快找出较优的装配序列。     

光学显微镜自动聚焦的技术研究

在对普通光学显微镜进行一定改装的基础之上 ,设计了一套显微镜自动聚焦系统 ,并且给出了图像的灰度差分绝对值之和算子 ,解决了自动聚焦过程中是否正确聚焦的判断问题。最后还给出了一套基于启发式搜索算法的聚焦搜索策略 ,以加快焦平面的搜索。     

基于广义产品结构的产品配置

针对传统的基于结构的产品配置方法中,零部件之间约束关系表达能力较弱的问题,将基于规则的方法和基于结构的方法相结合,给出了一种基于广义产品结构的产品配置模型和配置求解方法。该模型采用基于结构的方法描述配置知识的结构信息,采用基于规则的方法描述配置约束信息,增强了对配置约束的描述能力。配置求解方法中,提出了配置推理图的概念,并基于先根遍历访问模型中的节点,采用数据驱动的深度优先图搜索策略求解每个节点的配置约束,提高了配置求解能力。最后通过一个应用示例,给出了基于该产品配置模型的配置求解工作过程。     

非流水型生产调度问题的研究

采用赋时库所Petri-Net对非流水型的生产作业建立一般的调度模型,然后对模型进行代数化的描述,同时证明了非流水型生产调度问题的解空间如此之大以致很难用解析法来求得最优解.因此,运用深度优先规则和最短优先处理规则来搜索局部最优,得到的算法是一种(成本-时间)折中的启发式调度算法,在一定的程度上解决了对生产调度要求不高的调度问题.     

[供应链调度]装卸一体化车辆路径问题的自适应并行遗传算法

为了同时实现总配送成本最低、车辆行驶距离最短、车辆数最小等目标,综合考虑车辆指派成本及运输路径成本,建立了装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性,提出了一种自适应并行遗传算法。算法以C-W节约法为基础,设计了三种基于双重需求的启发式种群初始化方法,缩小搜索空间并优化初始解;引入多样性种群和高质量种群的双种群并行策略,实现深度与广度的同步搜索;设计自适应交叉变异操作,改善高质量种群个体搜索停滞,并针对全局最优个体采用特殊变异的后优化操作以进一步提高全局优化性能。采用标准数据集作为算例进行寻优测试,验证了所提算法的可行性和有效性。     

装卸一体化车辆路径问题的自适应并行遗传算法

为了同时实现总配送成本最低、车辆行驶距离最短、车辆数最小等目标,综合考虑车辆指派成本及运输路径成本,建立了装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性,提出了一种自适应并行遗传算法。算法以C-W节约法为基础,设计了三种基于双重需求的启发式种群初始化方法,缩小搜索空间并优化初始解;引入多样性种群和高质量种群的双种群并行策略,实现深度与广度的同步搜索;设计自适应交叉变异操作,改善高质量种群个体搜索停滞,并针对全局最优个体采用特殊变异的后优化操作以进一步提高全局优化性能。采用标准数据集作为算例进行寻优测试,验证了所提算法的可行性和有效性。     

[车间调度]一种求解单机总加权延迟调度问题的改进蚁群算法

针对极小化总加权延迟指标下的单机调度问题研究,提出一种基于信息素差异更新的改进蚁群算法。采用基于工件序列的编码方式,并结合修正交货期优先规则改进了启发式信息的设定;引入正负反馈机制来自适应地差异化更新各节点间信息素,同时将成对交换策略用于局部搜索,以进一步改善调度方案质量。结合OR-Library中多个基准实例的仿真验证了该算法的可行性和有效性。     

一种求解单机总加权延迟调度问题的改进蚁群算法

针对极小化总加权延迟指标下的单机调度问题研究,提出一种基于信息素差异更新的改进蚁群算法。采用基于工件序列的编码方式,并结合修正交货期优先规则改进了启发式信息的设定;引入正负反馈机制来自适应地差异化更新各节点间信息素,同时将成对交换策略用于局部搜索,以进一步改善调度方案质量。结合OR-Library中多个基准实例的仿真验证了该算法的可行性和有效性。     

作业车间类型多机器人制造单元调度算法

针对带多台机器人的作业车间类型机器人制造单元调度问题的特点,研究了以最小化最大完工时间为优化目标、将邻域搜索策略与启发式规则相结合的混合遗传算法,建立了作业车间类型多机器人制造单元调度问题的数学优化模型和析取图模型。基于析取图关键路径,采取移动机床块、交换机器人块、调整任务分配来构建搜索邻域;用启发式搬运工序插入法和启发式搬运任务分配法相结合的三层调度方法初始化种群;将基于邻域结构的局部搜索算法和基于三层调度的遗传算法相结合,有效实现问题的求解。通过基准算例测试表明,混合遗传算法有效并优于其他算法。     

基于结构模型的拆卸序列规划研究

为了解决装配结构复杂的产品拆卸序列规划中因数据组合爆炸而导致运算量剧增的问题,首先分析了典型装配体的拆卸特点,以零件自由度交集的运算结果作为拆卸方向的判断依据,提出了约束消除的概念,进而通过启发式算法实现了拆卸序列的自动生成;为了提高拆卸序列规划的运算效率和计算结果的实用性,引入了以装配关系为基础的层次化结构模型,通过逐层分解的方法降低了装配结构深度,避免了从整个复杂装配体上求单一零件的拆卸序列,达到了减少运算的目的;最后以简化的汽车为例,阐述了基于结构模型的拆卸序列规划过程。研究结果表明,以层次化结构模型为基础、以约束消除为原则的拆卸序列规划能有效降低运算量,从而控制复杂产品的数据组合爆炸问题。     

板式家具高速自动分拣系统出库及打包调度策略

为提升定制家具自动分拣系统出库及包装作业的整体效率,根据出库及包装作业的工作特点,将出库打包问题抽象为一类板件处理具有优先顺序约束及机器约束的三阶段柔性装配流水车间调度问题。在对各约束进行定义和数学描述的基础上,以最大出库完工时间、包装工位最大完工时间、板件平均等待时间三者加权和最小化为优化目标,建立了板件处理具有优先顺序约束和机器约束的三阶段柔性流水车间调度问题的数学模型;针对该模型,构造了一种启发式求解算法H~*。为验证算法的有效性,基于裂区试验设计的思想生成大量算例,并将启发式算法H~*与构造的9种组合规则算法、5种元启发式算法进行性能比较。结果表明,H~*算法可高效地获得高质量的解。     

基于Apriori算法的顾客需求自动映射研究

针对产品设计中顾客需求到产品功能技术特性的转化凭借设计者经验来完成的问题,通过计算机技术改善由于人员经验与流动性对设计进度与有效性造成的负面影响,提出基于质量功能展开(QFD,Quality Function Development)的顾客需求自动转换模型.首先,分析QFD中的顾客需求转换;接着,基于QFD提出适应产品创新设计的顾客需求自动搜索模式,通过引入Apriori算法,在知识库中展开搜索,将顾客需求自动映射到功能技术特性.最后,开发顾客需求自动映射系统,并通过实例验证系统的可行性.     

带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法

为了同时实现总配送成本最低、车辆数最少和车辆行驶距离最短等目标,考虑车辆指派成本及运输路径成本的相对重要性,建立了带时间窗装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性,提出了一种混合离散粒子群求解算法。算法基于客户排列的直观无分段大路径解表示法,采用改进深度优先搜索分割法对问题解进行解码与评价;嵌入一种变邻域下降搜索程序并在个体粒子每次迭代时以一定概率选择执行,利用混合粒子群算法在多邻域深度搜索和在全局空间广度搜索进行寻优,同时应用模拟退火思想和比例选择性变异最差个体来改善个体搜索停滞现象。采用两个不同目标算例进行寻优测试,验证了所提算法的可行性和有效性。