（信号与信息处理专业论文）基于fpga的蚁群算法硬件化技术研究.pdf

哈尔滨t 程大学硕十学位论文 摘要 蚁群算法( a c a ) 是模拟蚁群觅食行为的一种启发式仿生类智能进化算 法。近年来它在组合优化、函数优化等领域以及网络路由、数据挖掘、机器 人路径规划等工程问题上广泛应用，取得了良好的效果。蚁群算法的硬件实 现是仿生硬件( b h w ) 领域的一个分支，也是蚁群算法发展的高级阶段。蚁 群算法采用分布式并行计算和正反馈机制。其硬件实现具有：自组织、自适 应、自修复以及执行速度快等优点，能满足实时系统的需要。 本论文中心议题是蚁群算法的硬件实现。针对蚁群算法在f p g a 上的有 效映射以及实时系统的构建问题，进行了模型选择和算法改进：提出并命名 逐轮定位加权蚁群优化b w - a c o 算法，建立蚁群算法在迭代更新问题上的一 组经验公式，代替原有的迭代算法；给出硬件实现方案，成功实现了其在 f p g a 上的有效映射；论文详细讨论硬件结构及各个模块的内部实现细节。 本论文的主要研究内容包括： 第1 章概述课题背景及蚁群硬件实现的研究现状。 第2 章概述蚁群算法的基本原理及本文涉及的可编程逻辑器件f p g a 、 开发环境、开发语言及其开发流程。 第3 章详细论述蚁群硬件实现技术：一是基于单机总误时排序问题 ( s m l v r p ) 模型的群体蚁群算法( p a c o ) 在f p g a 上的有效实现；另一个 是基于旅行商问题( t s p ) 模型的计数器蚁群优化( c - a c o ) 硬件自启发实 现。 基于蚁群算法的离散性和并行性特点，本文选择数字图像分割问题，作 为硬件实现的模型。 蚁群算法与图像分割问题相结合，有不同的切入方式。目前，研究学者 已提出三种不同模型：基于像素的模型、基于聚类的模型和基于阈值的模型。 模型不同，运算量大不相同，硬件实现结构及复杂程度差别很大。综合考虑， 本文选择较适合的基于阈值的模型。 哈尔滨工程大学硕士学位论文 本文提出并命名逐轮定位加权蚁群优化b w - a c o 算法，给出其硬件实现 方案，其主要的创新点如下： 提出了一种逐轮定位搜索方法：蚂蚁每做一轮迭代，依次从阈值的高 位向低位进行定位，留出最后低三位作为搜索空间，在优化搜索进程的同时 避免陷入局部最优。 依据信息素矩阵和转移概率矩阵的数值规律，研究出一种以简单的加 减法、左右移运算代替复杂乘除法的方法，得到下一轮迭代所需的信息素和 转移概率，在此基础上提出一组经验公式用于硬件实现时的有效映射，以适 合现有的f p g a 硬件条件。 采用数字量化的定量加权信息素更新方式代替原有的需要复杂计算 的信息素增量更新方案，同时采用精英策略以加快搜索进程。 第4 章针对提出的b w - a c o 算法进行硬件结构设计，并对各个模块的功 能和具体实现进行详细的描述。 第5 章基于实验结果，给出结论：b w - a c o 算法方案有效，图像分割所 需时间满足实时性要求，适合于硬件实现。 关键词：蚁群算法；f p g a 信息素；逐轮定位加权蚁群优化算法；图像分 割 哈尔滨t 程大学硕七学位论文 a b s t r a c t a n tc o l o n ya l g o r i t h m ( a c a ) i san o v e lc a t e g o r yo fb i o n i cm e t a - h e u r i s t i c a l g o r i t h mw h i c hs i m u l a t e st h eb e h a v i o ro fa n tc o l o n yi nt h ep r o c e s so fs e a r c h i n g f o rf o o d i nt h ep a s ts e v e r a ly e a r st h ea l g o r i t h mh a sb e e nw i d e l ya p p l i e dt ot h e f i e l d so fc o m b i n a t o r i a lo p t i m i z a t i o nn e t w o r kr o u t i n g ，f u n c t i o n a lo p t i m i z a t i o n , d a t am i n i n g ，a n dp a t hp l a n n i n go fr o b o te t c ，a n dg o o de f f e c t so fa p p l i c a t i o na l e g a i n e df a v o r a b l ee f f e c t i nt h ea l g o r i t h m ，d i s t r i b u t e d ，p a r a l l e lc o m p u t a t i o na n d p o s i t i v ef e e d b a c km e c h a n i s ma r ea d o p t e d t h eh a r d w a r ei m p l e m e n t a t i o no fa c o i sa ne m b r a n c h m e n to ft h eb i o n i c sh a r d w a r e ( b h w ) ，a sw e l la sa na d v a n c e d p h a s eo ft h ea c od e v e l o p m e n tp r o c e d u r e ，w h i c hi sp r o v i d e d 晰t hm u c h s t r o n g p o i n ts u c ha sa u t o - o r g a n i z a t i o n ，a u t o - a d a p t a t i o n ，a u t o - r e h a b i l i t a t i o na n d h i g hs p e e di ne x e c u t i o nw h i c hi sa b l et os a t i s f yt h en e e do ft h er e a l t i m es y s t e m t h em a i nt o p i co ft h i sp a p e ri st h eh a r d w a r ei m p l e m e n t a t i o no fa n tc o l o n y a l g o r i t h m i te m p h a s i z e do nt h ei s s u eo fs e l e c t i n gas u i t a b l em o d e la n dt h e i m p r o v e m e n to fa c aw h i c ha i m sa tt h ee f f e c t i v em a pt ot h ef p g aa n dt h e c o n s t r u c t i o no fr e a l - t i m es y s t e m a n dt h e ni ti sp r o p o s e dt h ea l g o r i t h mn a m e d b i t f i tw e i g h ta c oa n dt h ec o r r e s p o n d i n gh a r d w a r ei m p l e m e n t a t i o ns c h e m e ，a n d p r e s e n t sag r o u po fe m p i r i c a lf o r m u l at or e p l a c et h eo r i g i n a la l g o r i t h mo nt h e i s s u eo ft h ei t e r a t i v eu p d a t e ，w h i c hi sm a p p e de f f e c t i v e l yi nf p g a f i n a l l yi t g i v e st h eh a r d w a r es t r u c t u r ea n de a c hm o d u l e si n t e r n a li m p l e m e n t a t i o nd e t a i l s t h em a i nr e s e a r c hc o n t e n to ft h i sp a p e ri n c l u d e ss e v e r a lp o i n t sa sf o l l o w s i nc h a p t e r1 ，i tp r e s e n t st h eb a c k g r o u n do ft h i sp a p e ra n dt h er e s e a r c hs t a t u s i nq u oo fh a r d w a r ei m p l e m e n t a t i o no f a c a i nc h a p t e r2 ，i tg i v e sa no v e r v i e wo ft h eb a s i ca n tc o l o n ya l g o r i t h ma n d i n v o l v e dd e v i c ef p g a ，t h ed e v e l o p m e n te n v i r o n m e n t ，t h ed e v e l o p m e n tl a n g u a g e a n df l o w 哈尔滨丁程大学硕士学位论文 i nc h a p t e r3 ，i te x p a t i a t e st h et e c h n o l o g yo fa c oh a r d w a r ei m p l e m e n t a t i o n i nd e t a i l s ，o n ei st h ee f f e c t i v ei m p l e m e n t a t i o no ft h ep o p u l a t i o na n tc o l o n y a l g o r i t h m ( p a c o ) b a s e do ns i n g l em a c h i n et o t a lt i m ep r o b l e m ( s m t t p ) i n f p g a ；t h eo t h e ri st h es e l f - e n l i g h t e n m e n ti m p l e m e n t a t i o no fc o u n t e ra n tc o l o n y o p t i m i z a t i o n ( c a c o ) b a s e do nt r a v e l i n gs a l e s m a np r o b l e m ( t s p ) i tc h o o s e st h ei m a g es e g m e n t a t i o na st h em o d e lo fh a r d w a r ei m p l e m e n t a t i o n i nt h i sp a p e rb e c a u s et h ed i s c r e t ea n dp a r a l l e lc h a r a c t e r i s t i co f a c a w h e na c ai sa p p l i e di nt h ei m a g es e g m e n t a t i o nt h e r e r ed i f f e r e n tp o i n t so f p e n e t r a t i o na n dt h ec u r r e n tt h r e em o d e l sp u tf o r w a r db ys c h o l a r si st h em o d e l b a s e do np i x e l s ，o nc l u s t e r i n ga n do nt h r e s h o l d c o n s i d e r i n ge a c ho ft h e mh a s d i f f e r e n tr e q u i r e m e n t si nh a r d w a r er e s o u r c e ，s oi tc h o o s e st h et h i r dm o d e l i t b r i n g sf o r w a r db i t f i x e dw e i g h ta n tc o l o n yo p t i m i z a t i o n ( b w - a c o ) a l g o r i t h mi n t h i sp a p e ra n dg i v e si t sh a r d w a r ei m p l e m e n t a t i o n t h em a i n i n n o v a t i o ni sa sf o l l o w s 1 ) i tp r o p o s e dar e s e a r c hm e t h o do fr o u n d - b y - l o c a t i o n ，n a m e l y , a n t sd oe v e r y r o u n do fi t e r a t i o n ，i tf i x e st h eb i t so ft h r e s h o l df r o mh i g hp o s i t i o nt ol o wp o s i t i o n , a tl a s tl e a v i n gt h ef i n a lt h r e eb i t sa st h es e a r c hs p a c ew h i c ho p t i m i z e st h es e a r c h p r o c e s sw h i l ea v o i d i n gr u n n i n gi n t ot h el o c a lo p t i m a ls o l u t i o n 2 ) i td e v e l o p e dan e wm e t h o dt h a tu s et h es i m p l ea d d i t i o na n ds u b t r a c t i o nt o r e p l a c et h ec o m p l e xm u l t i p l i c a t i o na n dd i v i s i o nw h i c hs u i tt ot h ec u r r e n tf p g a c o n d i t i o n st or e c e i v et h ep h e r o m o n ei n f o r m a t i o na n dt r a n s f o r m a t i o np r o b a b i l i t y n e e d e di nt h en e x ti t e r a t i o n ，a c c o r d i n gt ot h en u m e r i c a ll a w so ft h ep h e r o m o n e m a t r i xa n dt r a n s f o r m a t i o np r o b a b i l i t ym a t r i x b a s e do nw h i c hm e n t i o n e da b o v ei t p r o p o s e dag r o u po fe m p i r i c a lf o r m u l at oa c h i e v et h ee f f e c t i v em a p p i n go ft h e b w 二a c oi nf p g a 3 ) i ti n t r o d u c e dt h eq u a n t i t a t i v ed i g i t a lm o d en a m e dq u a n t i f i e dw e i g h t e d p h e r o m o n eu p d a t ei n s t e a do f t h eo r i g i n a lm o d et h a tn e e d sc o m p l e xc a l c u l a t i o nt o 哈尔滨t 程大学硕士学位论文 s p e e du pt h es e a r c hp r o c e s s i nc h a p t e r4 ，i tg i v e st h es t r u c t u r a ld e s i g no fb w a c oi nh a r d w a r ea n dt h e d e t a i l e dd e s c r i p t i o no fe a c hm o d u l e sf u n c t i o na sw e l la si t sc o n c r e t er e a l i z a t i o n i nc h a p t e r5 t h ee x p e r i m e n t a lr e s u l t ss h o w e dt h a tt h ep r o p o s e db w a c o a l g o r i t h mi se f f e c t i v ea n dt h et i m en e e d e db yt h ei m a g es e g m e n t a t i o ni sm e t t h e r e q u i r e m e n to f t h er e a l t i m es y s t e mw h i c hs u i tt oi m p l e m e n ti nh a r d w a r e k e yw o r d s ：a n tc o l o n ya l g o r i t h m ；f p g a ；p h e r o m o n ei n f o r m a t i o n ；b w - a c o ； i m a g es e g m e n t a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：乡，) 三，娣1 日期： 硎7 年弓月j 驴日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文在授予学位后即可由哈尔滨工程大学送交有关部门进 行保存、汇编等。 作者( 签字) ：多1 专少罚 日期：矽7 年弓月孑日 导师c 答字) 晕( 趣( 吲年3 月l 寥日 哈尔滨丁程大学硕十学何论文 1 1 引言 第1 章绪论 自2 0 世纪5 0 年代中期仿生学创立后，人们从生物进化的机理中受到启 发，提出了许多用以解决复杂优化问题的新方法。如遗传算法、进化规划、 禁忌搜索算法等。2 0 世纪9 0 年代初，意大利学者m d o r i g o 等人受蚂蚁在觅 食过程中可以找出从巢穴到食物源的最短路径的启发，提出了蚁群算法( a n t c o l o n ya l g o r i t h m ，a c a ) 。在管理科学、计算机科学和工程技术等许多领域中， 存在着大量组合优化问题，其中许多是n p c 类计算复杂度问题，至今尚无 很好的解决办法。人们先后使用了禁忌搜索算法、模拟退火算法、遗传算法、 人工神经网络等启发式搜索算法。这些新的智能算法迅速发展，无论是理论 研究还是应用研究都空前活跃。而蚁群算法用于求解局部最优化问题旅 行商问题( t s p ) 、分配问题、车间作业调度问题取得了较好的结果。受其影 响，蚁群系统模型在图形着色、网络路由、车辆路由、有序排列( s o p ) 、频 率分配等问题上有了一定的应用，这些初步研究和应用已显示出蚁群算法在 求解复杂优化问题，特别是离散优化问题方面的一些优越性。 蚁群算法不仅能够智能搜索、全局优化，而且具有稳健性、正反馈、分 布式计算、易与其它算法相结合等特点。利用正反馈原理，可以加快进化过 程分布式计算，使该法易于并行实现。个体之间不断进行信息交流和传递， 有利于发现较好解，不容易陷入局部最优。该方法易与多种启发式算法结合， 可改善算法的性能。由于其稳健性强，故在基本蚁群算法模型的基础上进行 修改，便可用于其它问题。因此，蚁群算法为诸多领域解决复杂优化问题提 供了有力的工具。 但是，蚁群算法还不像其它启发式算法那样已形成系统的分析方法和具 有坚实的数学基础。少有解析式作为确定参数的依据，更多的是依靠实验和 经验，而且其计算时间偏长。国内外的相关研究仍停留在实验探索阶段。 l 哈尔滨t 程人学硕十学位论文 对于蚁群算法的硬件实现技术，在蚁群算法提出来的这十几年间很少有 学者研究。一是因为算法本身的发展并不成熟，二是还未出现一种真正适合 于蚁群算法的硬件体出现，现时的硬件技术本身还不太支持蚁群算法的大计 算量( 浮点数运算、乘法和求幂运算) 以及对大量逻辑单元的需求。随着问 题规模的扩大，算法对存储器以及i o 口的需求都呈线性趋势增长，其硬件 实现技术还有待于更好的硬件体以及更好的改进算法的出现。 1 2 课题背景 蚁群算法的离散性和并行性特点对于离散的数字图像非常适用，它能在 不需要任何先验条件的情况下，直接自发地搜索到最优值。实现蚁群算法的 硬件系统与基于高级语言的软件系统相比，能得到显著的提速，而这正是实 时系统所需要的。 图像分割是图像处理和计算机视觉等领域中重要的研究课题。图像分割 的效果直接决定了后续图像分析、图像理解与识别的性能。通常的阈值法、 边缘检测法、区域跟踪法等图像分割方法其分割过程一般比较耗时。有效快 速实时地实现图像分割具有重要的现实意义。 本文的目的是：寻求一种高效实用的蚁群算法以实时实现图像分割。 1 3 蚁群算法硬件实现的研究现状 蚁群算法的硬件属于仿生硬件的一个分支，仿生硬件既不同于传统的硬 件电路，也不同于基于计算机的可编程系统，仿生硬件有其独特的电路结构 和硬件设计方法。仿生硬件由两个基本要素构成：一个是大规模现场可重构 逻辑器件；另一个是进化计算方法，以进化算法作为全局搜索和组合优化的 主要工具，寻求在不依赖先验知识与人工干预的情况下，通过进化来得到满 足给定性能指标要求的电路结构，以及使系统能在线自适应调整其内部结构， 以适应内部状态( 如局部故障) 和外部环境的变化。 能用于硬件在线进化的器件主要是现场可编程门( 单元) 阵列f p g a 。 2 哈尔滨工程大学硕士学位论文 目前国际上主要用x i l i n x 公司生产的现场可编程门阵列f p g a - x c v 6 2 0 0 系 列芯片、v i r t e x 系列芯片开展仿生硬件研究，这种芯片基于s r a m 编程、支 持部分动态重构。有了硬件体的支持，蚁群算法的硬件实现研究也逐步发展 起来。 m o s t a f aa b d e 1 b a r r 和s a d i qm s a i t 等人于2 0 0 3 年首先提出将改进蚁群 算法引入数字进化硬件电路中，用一系列的随机产生电路评估该算法的性能， 其结果与基于标准的a c o 技术相当，而用他们提出的改进算法设计的电路 性能则优于标准a c o 算法映射的硬件性能n 1 。 m g u n t s c h 和m m i d d e n d o r f 等人在2 0 0 4 年发表了基于群体的蚁群优化 p a c o ( p o p u l a t i o nb a s e da n tc o l o n yo p t i m i z a t i o n ) 算法在f p g a 上的实现的 文章，其中，以单机总误时排序问题s m t t p ( s i n g l em a c h i n et o t a lt a r d i n e s s p r o b l e m s ) 这一具体问题为蚁群算法的应用环境，给出了基于f p g a 的电路 实现结构，评析了算法在硬件空间上的需求。与软件实现相比较，硬件实现 时运行的时间大大减少，取得了较好的结果闭。 但是，因单机排序问题不涉及启发函数，上述的实现方法并没把启发函 数引入硬件实现模块中，所以，p a c o 算法并不适用于所有问题。针对此问 题，b e m ds c h e u e r m a n n 和m a r t i nm i d d e n d o r f 于2 0 0 6 年提出了基于计数器的 蚁群优化c - a c o ( c o u n t e r - b a s e da n tc o l o n yo p t i m i z a t i o n ) 算法在f p g a 上 的有效映射p 1 ：当问题的规模逐渐扩大时，其对硬件资源的需求不是像标准 蚁群算法那样呈线性增长趋势，而是水平渐近的；针对硬件的结构需求，给 出一种灵活的将启发函数信息引入优化过程的方法。 若要用硬件实现类似蚁群这一表现复杂群体行为的系统，首先需要构造 具有单只蚂蚁功能的智能体。i s a a c s 等将遗传算法和蚁群算法结合，提出一 种嵌入式硬件随机数据发生器设计的新思路川，但他们只是做了离线仿真， 并没有在硬件上给予实现。忻斌健等提出一种将归类结构方法与f p g a 设计 相结合的蚂蚁智能体硬件实现设想p 1 。归类结构是一种行为控制法，它将自 动控制的问题按任务而不是按功能进行分解，主张构造面向任务的专用模块， 3 哈尔滨丁程大学硕十学位论文 直接与传感器和执行器相连，其工作方式为并行的。x i o n g 等提出了遗传算 法与蚁群算法动态融合的软硬件划分算法( d c g 3 a ) 豫 r l ，其基本思想是利用 遗传算法群体性、全局随机搜索等优势生成初始划分解，并将其转化为蚁群 算法所需的初始信息量分布。实验表明，d c g 3 a 能非常有效地解决嵌入式 系统的软硬件划分问题，且划分问题规模越大，其优势越明显。蚁群算法的 硬件实现是当今仿生硬件研究领域的一个新内容，也是一个研究难点。 蚁群算法的发展历史只有十几年左右，其硬件技术的发展更是仅有几年 的时间，不像其它的启发式算法那样已形成系统的分析方法、具有坚实的数 学基础以及完整的硬件实现方案。国内外的大多数研究仍停留在实验探索阶 段，对于硬件的研究则更少，但蚁群算法的系统性、并行性、分布性等优点 及其适合在f p g a 上实现硬件的特点，使该算法具有广阔的应用前景。 1 4 本文内容介绍 本文围绕蚁群算法的硬件化实现技术展开研究工作，在这一过程中，采 用理论分析和计算机仿真相结合的方法，验证理论的正确性和实践的可行性。 主要进行了以下几方面的研究工作：分析了基本蚁群算法的原理及当今蚁群 算法硬件实现技术领域内的最新研究成果；简要概述课题中的软硬件开发平 台；详细分析了基于群体的蚁群优化( p a c o ) 算法硬件实现的特点以及用 于此算法的模型、基于计数器的蚁群优化( c a c o ) 算法硬件实现特点及其 模型；全面分析了基于图像分割的蚁群算法模型，并在此基础上提出了改进 的逐轮定位加权蚁群优化b w - a c o 算法，在降低算法复杂度和提高运行时间 上进行了分析，并用计算机进行了仿真，得出了改进算法优于已有算法的结 论；最后给出了b w - a c o 算法的硬件实现方案及各个模块的仿真波形图。 本文的内容分为五章，其结构如下： 第1 章简要介绍课题背景及蚁群算法硬件实现的研究现状。 第2 章概述蚁群算法的基本原理以及f p g a 的基本原理及设计方法与流 程，对课题所选的芯片进行简单的描述，简要介绍了系统开发过程中所涉及 4 哈尔滨- 1 ：程大学硕+ 学何论文 到的一些e d a 软件和编程语言。 第3 章介绍了目前蚁群算法硬件的实现技术，分析了其硬件实现的主要 特点和难点，分析了p a c o 及c a c o 的硬件实现方案，随后根据图像分割 模型的蚁群算法改进并提出了b w - a c o 算法，并做了仿真，得出了有效的结 论。 第4 章给出了b w - a c o 算法的硬件实现方案及内部各个模块的具体实现 细节。 第5 章对硬件方案的各个模块进行验证与仿真，给出了仿真结果，并通 过时序仿真证明是可行的。 结论部分总结了全文的内容。 5 哈尔滨工稃人学硕十学位论文 第2 章蚁群算法及f p g a 概述 2 1 蚁群算法的基本原理 2 1 1 蚁群行为描述 根据仿生态学家的长期研究发现：自然界中的蚂蚁虽然没有视觉，但其 运动时会通过在路径上释放出一种特殊的分泌物信息素来寻找路径佟“9 1 。 当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行，同时释 放出与路径长度相关的信息素。蚂蚁走的路径越长，则释放出的信息素越少。 当后来的蚂蚁再次碰到这个路口的时候，选择信息素量较大的路径的概率相 对越大，这样便形成了一个正反馈机制。最优路径上的信息素量越来越大， 而其他路径上的信息素量却会随着时间的流逝而逐渐消减，最终整个蚁群会 找到最优路径。同时，蚁群还能够适应环境的变化，当蚁群的运动路径上突 然出现障碍物时，蚂蚁能很快地重新找到最优路径。 由此可见，单个蚂蚁的行为极其简单，选择的能力有限，但是通过信息 素的作用使整个蚁群的行为具有高度的自组织性，通过相互协作能完成极其 复杂的行为。正是由于蚂蚁之间的路径信息的交换，整个蚁群能找出最优路 径。 cdcdcd ( a ) 各点之间的距离( b ) 随机选择c 和d 点( c ) 以较大概率选择b c e 路径 图2 1 蚁群觅食模拟图 6 哈尔滨工程大学硕士学位论文 图2 1 是一个形象化的图示，用以说明蚁群的路径搜索过程。 图2 1 中，各点及各点之间的距离已知，设a 点是蚁巢，f 点是食物源， c d 之间为障碍物。由于障碍物的存在，蚂蚁要想由a 到达f ，或者由f 返 回a ，只能由c 或d 绕过障碍物。设每个时间单位有3 0 只蚂蚁由a 到达b ， ( 或有3 0 只蚂蚁由f 到达e 点) ，蚂蚁过后留下的信息素浓度为1 。为方便， 设信息素停留时间为1 。 在初始时刻，由于路径b c 、b d 、e c 、e d 上均无信息素存在，位于b ( 或e ) 的蚂蚁可以随机选择路径。从统计的角度可以认为它们以相同的概 率选择b c e 与b d e ，如图2 1 ( b ) 所示。由于路径b d e 长度是路径b c e 的2 倍，所以经过一个时间单位后，在路径b c e 上的信息量是路径b d e 上信息 量的2 倍。t = l 时刻，将有2 0 只蚂蚁由b ( 或e ) 到达c ，有1 0 只蚂蚁由b ( 或e ) 到达d 。随着时间的推移，蚂蚁将会以越来越大的概率选择路径b c e ， 如图2 1 ( c ) 所示，直至最终完全选择路径b c e 。这样也就找到了由蚁巢到食 物源的最短路径。由此可见，蚂蚁个体之间的信息交换是一个正反馈过程。 蚂蚁觅食协作本质可概括成如下三点： 路径概率选择机制：信息素踪迹越浓的路径，被选中的概率越大； 信息素更新机制：路径越短，路径上的信息素踪迹增长得越快； 协同工作机制：蚂蚁个体通过信息素进行信息交流。 2 1 2 基本蚁群算法的数学模型 旅行商问题( t s p ) ：有刀个城市，一旅行商要从其中某一个城市出发， 访问各城市一次且仅有一次，再回到原出发城市，求最短的路线。 以t s p 为例说明d o r i g o 等人提出的蚂蚁系统( a n ts y s t e m ) 模型n 卅， 在t s p 中，目标是极小化 c o s t ( a ，) = 同n - 1 d ( q ，c ：( ，+ ) + d ( q ，q ) ( 2 1 ) 其中，d ( q ，c v ) 表示城市x 与城市少之间的距离。 7 哈尔滨工程大学硕士学位论文 设匆( f ) 表示f 时刻位于城市i 的蚂蚁数目，r , j ( t ) 为f 时刻路径( f ，力上的 信息素浓度，n 为t s p 规模大小，m 为蚁群中蚂蚁的总数目，即m = ：。后l ( f ) 。 在初始时刻各条路径上信息素浓度相等，设r , ( 0 ) = e o n s t ，e o n s t 为常量。蚂 蚁k ( k = - i ，2 ，所) 在运动过程中，根据各条路径上的信息素浓度决定其转 移方向。用禁忌表t a b u k ( k = - i ，2 ，肌) 来记录蚂蚁k 当前所走过的城市，随 着t a b u k 进化过程，对蚂蚁下一步可选择的欲行进城市的集合作动态调整。在 搜索过程中，蚂蚁根据各条路径上的信息素浓度及路径的启发信息来计算状 态转移概率。硝( f ) 表示在，时刻蚂蚁k 由城市f 转移到城市，的状态转移概 率。有 或( f ) = 掣黑，萄all。wd七e h o ) 】。【仉p ) r 侣j 一七 ( 2 2 ) $ c ：a l l o w d 0 ，否则 其中：a u o w e d k 表示蚂蚁k 下一步允许选择的城市；口为信息启发式因子， 为期望启发式因子，r v ( t ) 是与路径( f ，力相关联的启发式信息值。口表示轨迹 的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的 作用，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间的 协作性越强；表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信 息在蚂蚁选择路径时受重视的程度，其值越大，则该状态转移概率越接近于 贪心规则( 即在对问题求解时，总是做出在当前看来是最好的选择，不从整 体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解) 。 对于t s p ，r 0 ( t ) 表达式如下 锄( f ) = 1 吒( 2 3 ) 式中，西表示相邻两城市f 和歹之间的距离。对于蚂蚁k ，嘞越小，则r u ( t ) 越 大，露( f ) 也就越大。故，启发函数嘞( f ) 表示蚂蚁从城市j 转移到城市的期 望程度。 为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完 8 哈尔滨t 程大学硕十学位论文 一步或者完成对所有以个城市的遍历( 也即一个循环结束) 后，要对残留信 息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断 存入大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘 记。由此，t + n 时刻在路径( 力上的信息量可按照如下规则进行调整。 r , j ( t + n ) = ( 1 一力r , j ( t ) + a r , j ( t ) ( 2 - 4 ) 乃( ，) = 辨= 。芍o )( 2 5 ) 式中：p 表示信息素挥发系数，则1 一p 表示信息素残留因子，为了防止信息 的无限积累，p 的取值范围为：pc 【0 , 1 ) ；a r , j ( t ) 表示本次循环中路径( f ，力 上的信息素增量，初始时刻a t , j ( 0 ) = 0 ；( f ) 表示第k 只蚂蚁在本次循环 中留在路径( 力上的信息素量。 根据信息素更新策略的不同，m d o r i g o 提出三种不同的基本蚁群算法模 型来确定彭( ，) 。其中的a n t c y c l e 模型性能较好，它利用了全局信息：蚂 蚁完成一个循环后更新所有路径上的信息素。 硝，) _ 睁若第职蚂蚁在本次循种经过( f ，力 ( 2 - 6 ) 10 ， 否则 式中，q 表示信息素强度，三七表示第k 只蚂蚁在本次循环中所走路经的总长 度。 2 1 3 基本蚁群算法的实现步骤 以t s p 问题为例，基本蚁群算法的具体实现步骤如下： s t e pl ：参数初始化。令时间l = 0 和循环次数n o = 0 ，设置最大循环次数 c 。；将m 个蚂蚁置于刀个城市上；令有向图上每条边( f ，力的初始化信息量 r , j ( t ) = c o n s t ，其中c o n s t 表示常数，且初始时刻a t , j ( 0 ) = 0 。 s t e p2 ：循环次数他一c + 1 s t e p3 ：蚂蚁的禁忌表索引号k = o 9 哈尔滨下程大学硕士学位论文 s t e p4 ：蚂蚁标号七- k + l s t e p5 ：蚂蚁k 依据状态转移概率公式( 2 2 ) 计算的概率选择城市j | f 并前进， c 表示由y 个城市构成的集合，j c t a b u 。 。 s t e p6 ：修改禁忌表指针，将蚂蚁k 移到新选择的城市，并把该城市归入 到该蚂蚁个体的禁忌表t a b u 七中。 s t e p7 - 若集合c 中城市未遍历完，即 c - t a b u k 不为空集，跳转s t e p5 s t e p8 ：根据公式( 2 4 ) 和( 2 5 ) 更新每条路径上的信息量。 s t e p9 ：若未遍历完所有蚂蚁，即k o 用整数表示， 这样比浮点数表示能省下更多的硬件资源。初始化时，所有信息素值 ( f _ ，) 都赋予同样的初始值i 。+ 打。 选择转移概率：在确定选择转移概率的过程中，信息素的挥发不再是直 2 1 哈尔滨： 程大学硕+ 学位论文 接乘以1 一p ，而是：当一个城市，被选中后，对应的信息素值被消耗掉 a p = m i n r , j 一，l ，信息素的行为类似于递减计数器。每当一个城市被选 中后，其信息素值就递减，削弱对应的路径对后续蚂蚁的吸引力，那么那些 未被遍历的路径将吸引到更多的蚂蚁，避免陷入局部最优。而在标准蚁群算 法中，每经过一轮迭代，信息素的更新为：r , j = ( 1 - p ) r , + p r o ，即保留一部 分原始的信息素并重置一部分新的信息素。c a c o 的选择过程，用整型的常 数减法运算代替原始的乘运算，更适合于f p g a 实现。 更新计数器：在信息素更新矩阵的每行引入一个更新计数器u ，用于在 每轮迭代中累计行亍所挥发的所有信息素总值。在一轮迭代结束时，当朋只 蚂蚁的解建立完成时，每个更新计数器的值范围为0 u m 。 信息素更新：当寻找到该轮迭代的最优路径万时，信息素将根据相应的 解进行如下的更新：f 行的信息素值7 ( f ) 累加该行的更新计数器值， t 矿( ，) 2o ( ，) + u ，代替原来的o ( j ) 2t ，( 。) + ，这样，每行的信息素总量将 一直保持不变。 2 ) c a c o 到f p g a 的映射 c a c o 算法在f p g a 上的实现是将信息素矩阵直接映射到芯片上。这个 设计包括了静态矩阵的每个元素所需要的所有计算和存储资源。蚂蚁以紧密 的矩阵方式管状排列，蚂蚁口的索引及其选择的城市集合将通过矩阵电路单 元从顶至下地传播，这样的单元如图3 2 所示。 。 一 图3 2 信息素矩阵单元电路结构 哈尔滨。丁= 程大学硕+ 学位论文 若蚂蚁a 访问了城市f 后还未访问下一个城市_ ，则= l ，否则= 0 。信 息素值乃存储在一个递减计数器中，计数器最小值为诅。该设计中，忽略 启发信息的影响。设置信息素权重为口= 1 ，以避免求幂运算。因此，选择转 移概率的计算由式( 3 1 ) 简化为 岛2 乃乞膦 ( 3 8 ) 为选择一个城市，不必再计算这个等式中的分母和除法，只需计算分子中还 未被选中的城市之和。因此，在信息素矩阵的每一行，设计包含了一个计算 和= ：。气的电路。下一个将要被选中的城市则由一个随机数决定。 所有( 1 ，j ) 单元的决策屯都存储在一个决策存储器中，如果比较得出 彤一。，： ( 砌为随机数产生器所产生的任意随机数) ，则= l ，否则 = o 。 单元矩阵中的疗行，即每只蚂蚁的所有步骤。计算一行所需要的时间是 o ( 1 0 9 n ) ( 由和2 艺：；。气的计算量决定) ，那么建立一个解所需要的时 间则是o ( n l o g n ) 。因为蚂蚁以一种紧密的方式排列，如果解的建立过程中， 蚂蚁的解评估、比较以及更新过程都是并行进行计算的，那么计算z 个解所 需要总时间为o ( ( z + n ) l o g n ) 。而标准蚁群算法在单机c p u 上的运行时间是 o ( z n 2 ) 。所以，运行的时问提升了o ( z n 2 i ( ( z + n ) l o g n ) ) 倍。 3 4 逐轮定位加权蚁群优化b w 么c o 算法硬件实现方案 本文提出逐轮定位加权蚁群优化b w - a c o ( b i t f i x e dw e i g h t a c o ) 算法。 它适用于蚁群算法应用于图像分割的硬件实现问题。逐轮定位，即在蚂蚁搜 索阈值的迭代过程中，每经过一轮迭代，就逐渐确定阈值编码的一个高位： 加权，即在硬件实现系统中，在排序精英策略的基础上，引入定量加权信息 代替信息素增量的计算：算法中，引入一套普适的经验公式用于信息素和转 移概率的更新。这样更