求解0-1背包问题的混合贪婪遗传算法

求解0-1背包问题(KP)的最优解的时候,传统遗传算法(GA)的局部求精能力不足而简单局部搜索算法的全局探索能力有限,针对上述问题,将这两个算法整合并提出了混合贪婪遗传算法(HGGA)。在GA全局搜索框架下增加局部搜索模块,并改进传统仅基于物品价值密度的修复算子,增加基于物品价值的贪婪混合选项,从而加速寻优过程。HGGA一方面引导种群在进化的优质解空间中展开精细搜索,另一方面依靠GA的经典操作算子开拓全局搜索空间,从而达到算法求精能力和开拓能力的良好平衡。HGGA分别在三组数据上做了测试,结果表明在第一组15个测试用例中的12个上,HGGA能够百分百找到最优解,成功率达到80%;在第二组小规模数据集上,HGGA的性能明显好于其他同类GA和其他元启发算法;在第三组大规模数据集上,HGGA较其他元启发式算法具有更好的稳定性和高效性。

结合图像和图形特征的原木轮廓识别

针对原木端面存在污渍、裂痕和伐痕等导致原木轮廓难以被鲁棒地识别的问题,提出了结合图像和图形特征的原木轮廓识别方法.首先,引入YOLO V3,在对200多张原木图像样本进行学习后,实现利用图像信息进行目标检测;其次,利用原木轮廓图形上近似于圆的特点,采用轮廓重叠度计算和随机Hough变换校正YOLO V3识别结果的中心不准的问题.与同类原木图像的识别结果进行比较,结果表明,它能100%识别其中的完整原木,边缘的平均重叠度提高了10个点;在各类复杂端面轮廓情况下的识别结果中,该方法都有较好的鲁棒性,识别率达到98.8%.

结合深度学习与Hough变换的等长原木材积检测系统

针对成捆堆放的原木端面图像,利用机器视觉方法开发一个材积检测系统,算法的鲁棒性和系统应用的方便性是两个关键难点。为了解决上述问题,实现原木材积自动化检测,设计并开发了结合深度学习与Hough变换的等长原木材积检测系统。首先,在对训练样本做了旋转、调整曝光度、加噪声等提高模型鲁棒性的预处理后,使用YOLOv3⁃tiny卷积神经网络对原木端面图像进行目标检测,计算得到每一个原木端面对应的目标区域;其次,在对目标区域计算边缘并去除目标区域中心噪声边缘后,利用Hough变换圆检测算法计算原木端面轮廓的准确直径;最后,开发了操作简捷方便的用户界面,根据用户输入的一个原木轮廓径级校准信息和长度,即可实现图中所有原木的材积检测。本系统在多种原木端面图像上,包括端面完好、端面伐痕、端面霉变、环境复杂等情景进行实验验证,系统真检率为98.79%,误检率为0.602%。结果显示本系统在各种复杂原木端面图像上具有很好的鲁棒性,同时为了兼容深度学习算法与用户界面设计,本系统在PyQt5核心库上实现了操作界面,其操作简洁、使用方便。

混合群体增量学习算法求解闭环布局问题

闭环布局问题(CLLP)是一种NP-困难的混合优化问题,它在大小可调的矩形环上寻找设施最佳放置次序,目标是最小化设施之间物料流的运输成本。现有方法均采用元启发式算法来寻找最优的设施放置次序,并且通过枚举方法来获得最优的矩形环大小,而枚举方法的计算效率不高。为了解决这个问题,提出了求解CLLP的混合群体增量学习(HPBIL)算法,分别使用离散群体增量学习(DPBIL)算子和连续PBIL(CPBIL)算子同时对设施放置次序和矩形环大小进行优化,提高了搜索效率;同时还设计了一个局部搜索算法来优化每代中的部分优质解,以提高算法的求精能力。在13个CLLP测试实例上进行实验,结果表明HPBIL算法在9个测试实例上找到了新的最优布局,它对CLLP的寻优能力明显优于对比算法。

改进蚁群优化算法求解折扣{0-1}背包问题

折扣{0-1}背包问题(Discounted{0-1}Knapsack Problem,DKP)是一个NP-困难的组合优化问题,尽管已经存在一些求解DKP的智能优化算法,但目前尚没有用蚁群优化(Ant Colony Optimization,ACO)算法求解DKP的研究。提出了一个求解DKP的改进ACO(Modified ACO,MACO)算法。MACO算法使用整数编码以保证每组物品最多只有一个物品被选中,在MACO算法构造解的每一步,采用组内竞争选择来降低算法的时间复杂性,对计算选择概率的公式,放弃启发式信息以减少参数并简化算法参数设置,对蚂蚁构造出的解,经修复后使用基于价值密度和价值的混合贪婪优化算子来提高算法的寻优能力。在四类测试用例上对MACO算法进行了测试并与其他算法进行比较,实验结果表明MACO算法的性能明显优于其他算法。

基于拉马克进化的差分进化算法求解KPC问题

具有单连续变量的背包问题(knapsack problem with a single continuous variable,KPC)是标准0-1背包问题的自然推广,在KPC中背包容量不是固定的,因此其求解难度变大。针对现有差分进化(differential evolution,DE)算法在高维KPC实例上求解精度不够高的不足,提出基于拉马克进化的DE(Lamarckian evolution-based DE,LEDE)算法,将贪心修复优化算子产生的改进遗传给后代,以加快DE算法的收敛速度,提高DE算法在高维KPC实例上的求解精度。同时,在贪心修复优化算子中引入基于价值的贪心优化策略,用于优化使用基于价值密度的贪心修复策略生成的可行解,以帮助算法跳出局部最优。在40个KPC实例上对LEDE算法进行了实验分析,结果表明拉马克进化和基于价值的贪心优化策略能够提高LEDE算法的求精能力,LEDE算法在获得最优解和平均解方面均优于其他智能优化算法。