论文部分内容阅读
蚁群算法(ACA)是模拟蚁群觅食行为的一种启发式仿生类智能进化算法。近年来它在组合优化、函数优化等领域以及网络路由、数据挖掘、机器人路径规划等工程问题上广泛应用,取得了良好的效果。蚁群算法的硬件实现是仿生硬件(BHW)领域的一个分支,也是蚁群算法发展的高级阶段。蚁群算法采用分布式并行计算和正反馈机制。其硬件实现具有:自组织、自适应、自修复以及执行速度快等优点,能满足实时系统的需要。本论文中心议题是蚁群算法的硬件实现。针对蚁群算法在FPGA上的有效映射以及实时系统的构建问题,进行了模型选择和算法改进;提出并命名逐轮定位加权蚁群优化BW-ACO算法,建立蚁群算法在迭代更新问题上的一组经验公式,代替原有的迭代算法;给出硬件实现方案,成功实现了其在FPGA上的有效映射;论文详细讨论硬件结构及各个模块的内部实现细节。本论文的主要研究内容包括:第1章概述课题背景及蚁群硬件实现的研究现状。第2章概述蚁群算法的基本原理及本文涉及的可编程逻辑器件FPGA、开发环境、开发语言及其开发流程。第3章详细论述蚁群硬件实现技术:一是基于单机总误时排序问题(SMTTP)模型的群体蚁群算法(P-ACO)在FPGA上的有效实现;另一个是基于旅行商问题(TSP)模型的计数器蚁群优化(C-ACO)硬件自启发实现。基于蚁群算法的离散性和并行性特点,本文选择数字图像分割问题,作为硬件实现的模型。蚁群算法与图像分割问题相结合,有不同的切入方式。目前,研究学者已提出三种不同模型:基于像素的模型、基于聚类的模型和基于阈值的模型。模型不同,运算量大不相同,硬件实现结构及复杂程度差别很大。综合考虑,本文选择较适合的基于阈值的模型。本文提出并命名逐轮定位加权蚁群优化BW-ACO算法,给出其硬件实现方案,其主要的创新点如下:①提出了一种逐轮定位搜索方法:蚂蚁每做一轮迭代,依次从阈值的高位向低位进行定位,留出最后低三位作为搜索空间,在优化搜索进程的同时避免陷入局部最优。②依据信息素矩阵和转移概率矩阵的数值规律,研究出一种以简单的加减法、左右移运算代替复杂乘除法的方法,得到下一轮迭代所需的信息素和转移概率,在此基础上提出一组经验公式用于硬件实现时的有效映射,以适合现有的FPGA硬件条件。③采用数字量化的定量加权信息素更新方式代替原有的需要复杂计算的信息素增量更新方案,同时采用精英策略以加快搜索进程。第4章针对提出的BW-ACO算法进行硬件结构设计,并对各个模块的功能和具体实现进行详细的描述。第5章基于实验结果,给出结论:BW-ACO算法方案有效,图像分割所需时间满足实时性要求,适合于硬件实现。