（测试计量技术及仪器专业论文）混合并行遗传算法在双dsp平台上的实现技术研究.pdf

南京航空航天大学硕十学位论文 5802矿1 5 摘要 本文主要论述了混合并行遗传算法的基本原理及其实现技术。遗传算法作为一种 全局优化搜索算法，以其简单通用、适于并行处理以及应用范围广等显著特点而得到 广泛应用。同时数字信号处理器所具有的系统构成灵活、可编程、适用面广的特点， 使其在众多领域成为不可或缺的数字处理的计算引擎。本文研究了组合优化领域中的 巡回旅行商问题，在此基础上首先通过设计实现混合并行遗传算法来解决该问题，其 次对在双d s p 处理器系统上实现算法进行了研究实践。课题设计通过使用d s p 仿真平 台进行功能验证，并对结果进行分析，得出结论。整体方案具有一定可行性。 关键词：遗传算法：混合并行遗传算法；双d s p 并行系统巡回旅行商问题 颦冬者、导帮厨意 匆土：文公布 混合并行遗传算法在双d s p 平台上的实现技术研究 a b s t r a c t t h i sp a p e rjn t r o d u c e st h eb a s i ct h e o r yo fh y b r i dp a r a l l e lg e n e t i c a 1 9 0 r i t h ma n dt h et e c h n o l o g yo fh y b r i dp a r a l l e lg e n e t i ca l g o r i t h mb a s e do n m u l t i p r o c e s s i n gd s ps y s t e m s t h em a i nc h a r a c t e r i s t i co ft h eg ai s t h a ti ti s s i m p l e ，u n i v e r s a la n de a s yt op a r a l l e l g ah a sb e e ns u c c e s s f u l l yu s e di na l o to ff i e l d ss u c ha st h et r a v e l l i n gs a l e s m a np r o b l e m ，s c h e d u l i n g ，f u n c t i o n o p t i m i z a t i o n ，m a c h i n el e a r n i n ge t c a tt h es a m et i m ed s pa l s oh a sb e e n s u c c e s s f u l l yu s e di nm a n yf i e i d sb e c a u s eo fi t sf l e x i b i l i t y ，p r o g r a m m a b l e a h y b r i dp a r a l l e lg e n e t i ca l g o r i t h mb a s e do nm u l t i p r o c e s s i n gd s ps y s t e m sh a s b e e nd e s i g n e da n di m p l e m e n t e df o rs o l v et h et s pp r o b l e m t h es c h e m eh a db e e n c h e c k e do nd s ps i m u l a t i n gp l a t f o r ma n dac o n h s i o nh a sb e e nd r a w n t h er e s u lt s s h o w e d i t sf e a s i h i l i t y k e yw o r d s ：g e n e t i ca l g o r i t h m d u a l p r o c e s s i n gd s ps y s t e m s h y b r i dp a r a l l e lg e n e t i ca i g o r i t h m t r a v e l i n gs a l e s m a np r o b l e m i i 南京航空航天大学硕十学位论文 1 1 课题研究背景及来源 第一章绪论 本课题为模糊自适应遗传算法在多传感器多目标跟踪中的应用研究课题部分 内容的拓宽研究项目。 在多传感器多目标跟踪系统中，存在着两方面的需求：一方面系统要求采用具有 一定复杂度的跟踪算法来提高在复杂环境下的目标跟踪精度；另一方面从系统响应带 宽出发又要求算法具有足够的实时性。系统具有大数据量计算、高传输率、严格实时 性等要求，因此需要进行算法及其实现手段的最优化研究。 1 2 遗传算法研究现状 遗传算法作为人工智能的一个分支，是一类借鉴生物界自然选择和自然遗传机制 的随机搜索算法。生物是通过两个基本过程：自然选择和有性生殖不断进化的。通过 自然淘汰、突然变异、遗传等规律进化，以适应环境的变化。正因如此，人们开始把 进化这种变异的本领看成一种值得仿效的东西。二十世纪六十年代末，m i c h i g a n 大 学的j o h nh h o l l a n d 教授和他的同事、学生一起研究出一种叫遗传算法( g e n e t i c a l g o r i t h m s 简称g a ) 的搜索算法，其目的是解释自然界的自适应过程及设计一个体 现自然界机理的软件系统。后来这一算法被广泛应用于各种优化问题。近年来g a 这 一算法随着神经网络、人工生命、进化计算等研究的兴起而引起了人们越来越多的兴 趣，并已应用于搜索问题、优化问题及机器学习、自编制程序、模式识别、人工神经 网络等方面”1 。 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体 领域，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域： 1 函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算 例。遗传算法适用于各种形式的函数：连续函数和离散函数、凸函数和凹函数、低维 函数和高维函数、确定函数和随机函数、单峰值函数和多峰值函数等。对于一些非线 性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方 便的得到较好的结果。 2 组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算 机上用枚举法很难求出其最优解。对这类复杂的问题，人们已经意识到应把主要精力 放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传 算法对于组合优化中的n p 问题非常有效。例如，遗传算法已经在求解旅行商问题、 混合并行遗传算法在舣d s p 平台上的实现技术研究 背包问题、装箱问题、图形划分问题等方面得到成功的应用。 3 生产调度问题 生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过。些 简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。目前在 现实生产中也主要靠一些经验来进行调度。现在遗传算法已经成为解决复杂调度问题 的有效工具，在单间生产车间调度、流水生产车间调度、生产规划、任务分配等方面 遗传算法都得到了有效的应用。 4 机器学习 学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特 别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制 规则：基于遗传算法的机器学习调整人工神经网络的连接权，也可用于人工神经网络 的网络结构设优化设计等等。 5 图像处理 图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特 征提取、图像分割等不可避免的会存在一些误差，这些误差会影响图像处理的效果。 如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处 理中的优化计算方面( 包括模式识别、图像恢复、图像边缘特征提取等) 已经取得了 很成功的应用。 1 3 遗传算法的发展趋势 遗传算法在具有上述优点的同时也有许多不足和缺陷。客观的说，遗传算法尽管 有各种新策略和新提案不断被提出，但几乎都是针对特定问题求解而言的，对它们的 评估也都基于对比试验，其中缺乏深刻而具普遍意义的理论分析”3 。正因为如此，遗 传算法现阶段的研究重点回到了基本理论的开拓和深化以及更通用、更有效的操作技 术和方法的研究上。以下是遗传算法现阶段研究课题的几个主要方面。 1 优化搜索方法的研究 迄今为止，优化问题的求解仍在遗传算法研究中占很大的比例。例如t s p 等组合 优化问题一直是遗传算法十分活跃的研究课题。据报道，遗传算法对4 3 1 个城市的 t s p 问题的求解已经取得最优解，对6 6 6 个城市已经得到准优解。尽管遗传算法比其 它搜索方法有更强的鲁棒性，但它更擅长全局搜索而局部搜索能力却不足。据研究文 献“1 ，遗传算法可以用极快的速度达到最优解的9 0 左右，但要达到真正的最优解则 要花费很长的时间。一些对比实验还表明，如果兼顾收敛速度和解的品质两个指标， 单纯的遗传算法未必比其它搜索方法优越许多。为此，除了要进一步改进基本理论的 方法外，还要采用和神经网络、模拟退火、下山算法或专家系统等其它方法相结合的 策略。这种混合模型可能有效的提高遗传算法的局部搜索能力。混合遗传算法是这篇 南京航空航天人学硕士学位论文 论文所涉及的重要内容之一。 2 遗传算法的并行处理 传统的遗传算法虽然具有隐含的并行性，但其实现方法在本质上仍然是串行的。 这种串行的遗传算法在解决一些实际问题时，由于需要较多的个体数量和大量的计 算，使得进化过程比较缓慢，难以达到实时的要求。因此并行遗传算法( p a r a l l e l g e n e t i ca l g o r i t h m p g a ) 就受到了较大的重视，并且已经成为目前遗传算法研究的 主要课题。遗传算法与并行处理器相结合，能把并行处理芯片的高速性和遗传算法固 有的并行性两者的长处彼此结合起来。 遗传算法中各个体的适应度计算遗传算法中最大的计算开销可独立进 行而彼此之间无需任何通信，这为遗传算法并行化提供了有利条件。但是，标准的遗 传算法除了适应度计算外，其遗传操作是建立在全局统计处理的基础上( 比如说比较 适应的大小并进行排序等等) ，这意味着在整个进化过程中，这种全局统计处理所引 起的通信开销依然不可忽视，有时甚至成为主要问题。因此，设计有效的并行遗传算 法以及相应的实现系统对于遗传算法的理论研究和应用研究都是十分重要而迫切的 任务。 另外，遗传算法的研究方向还有学习系统的遗传算法研究、生物进化与遗传算法 的研究、人工生命与遗传算法的研究等等。 1 4 数字信号处理器的发展 数字信号处理器d s p ( d i g i t a ls i g n a lp r o c e s s o r ) 的发展已有近2 0 的历史，作 为一种具有极强处理实时性的处理芯片，近年来在通信、雷达、航空航天、汽车电子、 消费电器等各个领域都获得了广泛的应用。根据使用方法不同，d s p 可分为专用d s p 和可编程d s p ”1 。本课题使用a d 公司的可编程d s p 芯片a d s p 2 1 0 6 0 。可编程d s p 如同 g p p ( g e n e r a lp u r p o s ep r o c e s s o r ，如p e n t i u m ) 一样有完整的指令系统，通过软件实 现各种功能。d s p 的产生主要是为了满足通信、雷达、数字电视等领域对实时数字信 号处理的需要，这些算法的共同特点是要进行密集的数学计算，因此d s p 在体系结构 上采取了一系列措施，使之在数学计算方面具有特别突出的性能，而在其他反面，例 如文字处理、数据库管理等则不如g p p 。除了密集的数学计算之外，d s p 应用的另一 个突出特点是实时性。在许多应用领域，如通讯中的调制、解调、雷达中信号检测等 等，数据是以帧为单位更新的，每帧的长度一般为微秒到毫秒量级，d s p 必须在这段 时问内完成处理并输出结果。显然实时处理要求处理器具有极高的处理速度，能够对 外部事件迅速做出反应。 当今d s p 生产厂家为了应对实时信号处理领域对计算速度的巨大需求，在努力提 高d s p 处理主频的同时，采用大量新技术新功能部件来引入并行技术。t i 公司推出 的t m s 3 2 0 c 6 x 进一步发展了超长指令字( v l i w ) 和多流水线技术。而a d 公司推出的 堡盒堑堑望堡塞生鱼翌里塑兰鱼占盟塞型壁查婴塑 一 一一 a d s p 2 t 0 6 x 系列和t i 公司的t m s 3 2 0 c 4 x 系列则向片间并行发展，为顾客提供了设计 大规模并行系统的硬件基础，它们都提供了6 个通信链路口，并为共享总线系统的设 计提供了相应的总线控制信号线，可以组成松耦合的分布式并行系统和紧耦合的总线 共享式并行系统。在本课题中，使用两片a d s p 2 1 0 6 0 芯片组成基于总线共享的紧耦合 系统来实现并行遗传算法。 课题中采用的双a d s p 2 1 0 6 0 协作的平台结构框图如图1 1 所示： 该系统具有两个主要特点： 1 共享总线的紧祸合系统 两片d s p 芯片通过共享总线方式连成并行系统，不需外加任何控制逻辑。每个处 理器不仅可以访问共享存储区，还可以访问其他处理器的内部存储器、i o p 寄存器 等。通过访问操作，可以实现数据交换。 2 系统与p c 机的串口通讯 系统中采用由第一片d s p 与p c 机的串行口通讯，将d s p 处理芯片完成算法处理 后的最优值数据通过u a r t ( 通用异步收发芯片) 芯片返回p c 机，p c 机使用串口接收程 序取得数据，并进行画面显示和性能比较。 图1 1 基于总线共享的i v , a d s p 2 1 0 6 0 系统原理框图 1 5 本论文研究内容 课题研究内容及工作目标如下： 1 混合遗传算法的设计实现 在解决巡回旅行商问题的具体应用中，相对于简单遗传算法，研究模拟退火算法 与遗传算法的合作，设计并实现混合遗传算法，并从试验数据中证明该算法在巡回旅 行商问题中的有效性和可行性。 2 并行遗传算法研究 在对混合遗传算法实现的基础上，研究并实现基于群体分组的并行遗传算法，并 南京航空航天人学硕士学位论文 从试验数据中证明算法的综合效率达到一定要求。 3 双d s p 芯片并行系统的设计实现 在双d s p 芯片的平台上实现并行遗传算法，在算法实现中每进行l o 代进化，d s p 处理器就会将当前群体中适应值最好的个体发送给另一d s p 处理器，并接收对方发送 的个体，替换自身群体中适应度最差的个体。 4 d s p 与p c 机的串口通讯实现 由于a d s p 2 1 0 6 0 只支持同步串行通讯。所以使用了u a r t 芯片与p c 机的串行口相 连。u a r t 芯片使得d s p 方面的编程将u a r t 设置为外部存储器，通过读写u a r t 芯片 寄存器进行数据发送接受。p c 机方面的通讯直接使用目前较为广泛使用的串口通讯 精灵v 2 0 实现。 虽然遗传算法在理论上具备并行性，但实际应用中却容易面临着通讯开销太大使 并行优势丧失的问题。这也是遗传算法发展到今天，本身虽然具备固有的并行性，但 是在并行化方面始终进展甚少的原因之一“。目前在遗传算法并行化研究方面，国内 技术文章多以实际应用为主；在实现手段上，多以运行l i a u x 的微型机算计并行系统 为主，使用d s p 芯片进行算法实现的较为少见。 本课题尝试并行遗传算法的设计和多d s p 处理器协作等问题的研究，试图对以后 更复杂并行系统的设计奠定一定的基础。希望本课题的研究能对遗传算法及其相应变 种算法在其它实际工程领域中的应用提供一定的参考价值。 混合并行遗传算法在双d s p 平台上的实现技术研究 第二章混合遗传算法及其实现 2 1 遗传算法的生物学基础 遗传算法，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型， 它是由美国m i c h i g a n 大学的j h o l l a n d 教授于1 9 7 5 年首先提出的。 自然选择学说认为，生物要生存下去，就必须进行生存斗争。在生存斗争中，具 有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代：具有不利 变异的个体就容易被淘汰，产生后代的机会也少得多。这种选择的过程，启发了人工 智能的研究者们，因为所谓智能的一个重要方面，就是要在可能的解决方法中，找出 一种最好的方法。虽然计算机有很强的运算能力，但是在很多情况下，可能的解太多 了，以至于即使用最强大的计算机也难以通过逐一比较得到最好的解法。通过遗传算 法，可以通过模仿进化的过程，使得到的解越来越“适应环境”，也就是越来越接近 最优的解“1 。 在实现遗传算法的过程中，又使用到了现代细胞学和遗传学的研究成果；遗传物 质的主要载体是染色体，染色体中的d n a 又是最主要的遗传物质，基因是有遗传效应 的片段，它储存着遗传信息，可以准确地复制，也能够发生突变，并由它表现出生物 的性状。生物体自身通过对基因的复制和交叉的操作使其性状的遗传得到选择和控 制。同时，通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多采的 变异现象。生物的遗传特性，使生物界的物种能够保持相对的稳定：生物的变异特性， 使生物个体产生新的性状，以至于形成了新的物种，推动了生物的进化和发展。 2 2 基本遗传算法简介 对于一个寻优问题，多数情况下只要求出近似的最优解就能满足人们的需求了。 概括起来讲，求最优解或近似最优解的方法主要有三种”3 ： 1 枚举法：是指枚举出可行解集合内的所有可行解，以求出精确的最优解。对 于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远 达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时在目前 较为先进的计算工具上都难以求的最优解。 2 启发式算法：是指寻求一种能产生可行解的启发式规则，以找到一个最优解 或近似最优解。该方法的求解效率虽然比较高，但是要对每一个需要求解的问题都必 须找出其特有的启发式规则，而这个启发式规则没有通用性。 3 搜索算法：是指寻求一种算法，能在可行解集合的一个子集内进行搜索操作， 以找到问题的最优解或者近似最优解。该方法虽然保证不了一定能够得到问题的最优 解，但是如果适当的利用一些启发知识，就可在近似解的质量和求解效率上达到一种 南京航空航天大学硕士学位论文 较好的平衡。 随着问题种类的不同以及问题规模的扩大，要寻找到一种能以有限的代价来解决 上述最优化问题的通用方法仍旧是一个难题。而遗传算法为我们解决这类问题提供了 一个有效的途径和通用框架，开创了一种新的全局优化搜索算法 基本遗传算法( s i m p l eg e n e t i ca l g o r i t h m ，s g a ) 可定义为一个8 元组： s g a = ( c ，e ，p o ，m ，中，r ，v ，t )( 2 - i ) 式中，c 一个体的编码方法，s g a 使用固定长度二进制符号串的编码方法： e 一个体的适应度评价函数； p 旷一初始种群： m 一群体大小，一般取2 0 1 0 0 ； 中一选择算子，s g a 使用比例选择算子； r 一交叉算子，s g a 使用单点交叉算子； v 一变异算子，s g a 使用基本位变异算子； t 一算法终止条件，一般终止进化代数为1 0 0 一5 0 0 。 在遗传算法中，可将n 维决镱向量x = x ，x 。x 。，x 。 1 用x = x ，x ，x 。x 。的符号串来 表示，把每个x ，看作一个遗传基因，它的所有可能取值称为等位基因，这样，x 就可 以看作由个遗传基因所组成的一个染色体。在一般情况下，染色体长度是固定的，但 是对一些问题也可以是变化的。根据不同的情况，等位基因可以是一组整数，也可以 是某一范围内的实数，或者纯粹一个记号。最简单的等位基因是由0 和1 这两个整数 组成的，相应的染色体就可以表示成一个二进制符号串”3 。遗传算法中，决策变量组 成了问题的解空间。对问题最优解的搜索是通过对染色体的搜索过程来进行的。 生物的进化是以群体为主体的。与此对应，遗传算法的运算对象是由m 个个体所 组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过 程也是一个反复迭代的过程，第t 代群体记作p ( t ) ，经过一代遗传和进化以后，得 到t + l 代群体，记作p ( t + 1 ) 。这个群体不断的经过遗传和进化操作，并且每次都按 照优胜劣汰的规则将适应度较高的个体更多地遗传到下代，这样最终在群体中将会 得到一个优良的x ，它的表现型将达到或接近于问题的最优解。 如式( 2 1 ) 所示，基本遗传算法是使用比例选择、单点交叉和基本位变异的遗传 算法，其实现手段上是遗传算法的最简化方法。图中的选择算子部分可以置在交叉算 子和变异算子操作之前，这是图中所没有画出的。其大致流程图如图2 1 所示。 2 3 遗传算法的数学基础 遗传算法是个以适应度函数为依据，通过对群体个体施加遗传操作，实现群体 内个体结构重组的迭代处理过程。在这一过程中，群体个体一代代得以优化并逐渐逼 近最优解。但是作为一种智能搜索算法，它的本质内涵可以由模式定理和构造块假设 混合并行遗传算法在双d s p 平台上的实现技术研究 ”。等数学分析加以讨论。 模式( s c h e m a ) 是一个描述字符串集的模板，该字符串集中的串的某些位置上存在 相似性。例如二值字符集 0 ，1 ) ，由此可以产生通常的0 ，1 字符串。现在增加一个通 配符“ ”，“女”既可以被当作0 ，又可以被当作“1 ”。这样二值字符集 0 ，1 ) 就可扩展成三值字符集 o ，l ，女) 。将基于三值字符集 0 ，1 ，女 所产生的能描述具有某些 结构相似性的0 、1 字符串集的字符串称作模式。 图2 1基本遗传算法的流程 引入模式概念并不是仅仅为了描述上的方便。在引入模式概念前，我们看到的遗 传算法是：在某一代中，n 个互不相同的串在选择、交叉、变异等遗传算子的作用下 产生下一代的n 个新的互不相同的串。那么，两代之间究竟保留了什么性质，破坏了 什么性质，我们无从得知，因为我们所看到的串都是相互独立的，互不联系的。在引 入模式概念后，我们看到的一个串实际上隐含着多个模式，一个模式可以隐含在多个 串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。 因此通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢 弃，从而把握遗传算法的实质，这正是模式定理所要揭示的内容。 南京航空航天火学硕士学位论文 模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短的定义长度， 并且平均适应度高于群体平均适应度的模式将按指数级增长。 首先定义两个重要的概念：模式阶( s c h e m a o r d e r ) 和定义长度( s c h e m ad e f i n i n g l e n g t h ) 。模式h 中确定位置的个数称作该模式的模式阶，记作0 ( h ) 。比如模式0 1 l 1 的阶数为4 ，而模式0 料女 为l 。显然，一个模式的阶数越高，其样本数就越少，因 而确定性越高。但是，模式阶并不能反映模式的所有性质。即使具有同阶的模式，在 遗传操作下，也会有着不同的性质。为此，在引入长度的概念，模式中第一个确定位 置和最后一个确定位真之间的距离称作该模式的定义距离或定义长度，比如模式 0 1l * l $ 的定义长度为4 ，而模式o 料$ $ 为0 。 有了这两个概念，就可以开始讨论模式在遗传操作下的变化。令a ( t ) 表示第t 代群体，以a j ( j = l ，2 ，3 ，n ) 表示一代中的j 个个体串。第t 代中，群体a ( t ) 中模式 h 所能匹配的样本数为m ，记作m m ，d 。 下面对基本遗传算法在选择算子连续作用下，模式m ( h ，t ) 的变化情况进行分析。 选择算予的作用：一个串是以概率p = f 。e f ，进行选择的，其中f 。是个体a ( t ) 的 适应度。假设一代中群体大小为n ，且个体两两互不相同，则模式h 在第t + l 代中的 样本数m ( h ，t + 1 ) 为： j i l ( h ，t + 1 ) = m ( h ，t ) n f ( h ) e f 。( 2 - 2 ) 其中f ( h ) 是模式h 所有样本的平均适应度。令群体平均适应度为f o = e f i n ，则有 m ( h ，t + 1 ) = m ( h ，t ) f ( h ) f o ( 2 - 3 ) 可见，模式的增长( 减少) ，即样本数的增加( 减少) ，依赖于模式的平均适应度与 群体平均适应度的比值：那些平均适应度高于群体平均适应度的模式将在下一代中得 以增长；而那些平均适应度低于群体平均适应度的模式将在下一代中减少。若再假 设模式h 的平均适应度总是高出群体平均适应度的c 倍，则上式为 m ( h ，t + 1 ) = m ( h ，t ) ( f o + c f o ) f 。 由此可见，m ( h ，t ) 为一等比级数，其通项公式为m ( h ，t ) = m ( h ，0 ) ( 1 + c ) ( 2 - 4 ) 显然，当c 0 时。该模式呈指数级增长；当c 1 0 0 0 王0 0 1 图2 5 简单位变异 遗传算法引入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力。当 遗传算法通过交叉算子已接近最优解临近值时，利用变异算子的这种局部随机搜索能 力可以加速向最优解收敛。这种情况下变异概率应取较小值，否则已经接近最优解的 值会因为变异而遭到破坏：二是使遗传算法可以维持群体多样性，以防止出现早熟现 象。 2 5 遗传算法在组合优化问题中的应用 2 5 1 巡回旅行商问题简介 任何算法的优劣，其是否适合某些特定问题，都要有一个比较，所以本文引入巡 回旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 。它属于n p 完全问题，是近代组 合优化领域的一个典型难题。给定一组n 个城市和它们的坐标，或者两两之间的直达 距离，寻求一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。用遗 传算法解决t s p ，一个旅程很自然地表示为n 个城市的排列，用图语言来描述t s p “1 ， 给出一个图g ：( v ，e ) ，每边e e 上有非负权值w ( e ) ，寻找g 的h a m i l t o n 圈c ，使 得c 的总权w ( c ) = w ( e ) ，e e ( c ) 最小。t s p 搜索空间随着城市数的增加而增大， 所有的旅程路线组合为n ! 。 在遗传算法的研究中，t s p 问题已被广泛的用于评价不同的遗传操作及选择机制 的性能。原因如下： 1 t s p 问题是一个典型的、易于描述却难以处理的n p 完全问题。有效的解决t s p 问题在可计算理论上有着重要的理论价值； 2 t s p 问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此， 快速、有效的解决t s p 问题有着极高的实际应用价值： 3 t s p 问题因其典型性已经成为各种启发式搜索、优化算法的间接比较准则( 如 神经网络优化法、列表寻优法( t a b u ) 法、模拟退火法等) 。 2 5 2t s p 问题中编码方法与交叉算子的设计 t s p 问题常用的编码方法是以遍历城市的次序排列进行编码。比如码串1 2 3 4 5 6 7 8 表示从城市1 开始，依次经过城市2 ，3 ，4 ，5 ，6 ，7 ，8 ，最后返回城市1 的遍历路径。 1 2 南京航空航天大学硕士学位论文 这是一种针对t s p 问题的最自然的编码方式，但与这种编码方法所对应的交叉运算和 变异运算实现起来比较困难，因为常规的交叉运算和变异运算会使群体中产生一些不 满足问题约束条件或无实际意义的巡回路线。对于该问题许多学者提出了众多的解决 方法；如g r e f e n s t e t t e 提出的顺序表示与交叉；g o l d b e r g 提出的部分匹配交叉；d a v i s 提出的路径表示的顺序交叉( o x ) ：o l i v e r 提出的循环交叉( c x ) ；w h i t l e y 提出的边重组 交叉操作等，限于篇幅，在此不作详细解释，仅给出本课题中使用的o x 交叉算子的设 计思路。 对于下面两个父体，随机选择两个交叉点： p i ( 1 23 i 4567 1 8 9 ) p ：( 4 5 2 11876193 ) 首先，两个交叉点之间的中间段保持不变，得到： 0 ；( xxxl4567 l xx ) 0 2 ( xxxll876 ixx ) 然后记m 为( 9345 21876 ) 将p 。中的( 4567 ) 从顺序表中去掉，然后依 次写入0 ，中，得到 0 ( 2 l8456793 ) 0 。( 345187692 ) 2 5 3 遗传算法解决t s p 问题的优缺点及混合遗传算法的引入 遗传算法在解决t s p 问题中的优点： 1 遗传算法以决策变量的编码作为运算对象：传统的优化算法往往直接利用决策 变量的实际值本身来进行优化计算，但是遗传算法不是直接以决策变量的值，而是以 决策变量的某种形式的编码作为运算对象。这种对决策变量的编码处理方式，使得在 优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗 传和进化等机理，也可以方便的应用遗传操作算子。特别是对一些无数值概念或很难 有数值概念，而只有代码概念的优化问题，编码处理方式更显示出其独特的优越性。1 。 2 遗传算法直接以目标函数值作为搜索信息：传统的优化算法不仅需要利用目 标函数值，而且往往需要目标函数的导数值等其它一些辅助信息才能确定搜索方向。 而遗传算法仅仅使用由目标函数值变换来的适应度函数值就可以确定进一步的搜索 方向和搜索范围，无需目标函数的导数值等辅助信息。这个特性对很多无法或很难求 导数的函数或者是组合优化等问题提供了很大的便利。遗传算法不仅不受函数连续可 微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，对于输入可计 算出加以比较的正的输出。遗传算法的这一特点使它的应用范围大大扩展。 3 ，遗传算法同时使用多个搜索点的搜索信息：传统的优化算法往往是从解空间 中的一个初始点开始最优解的迭代搜索过程。单个搜索点提供的搜索信息毕竟不多， 混合并行遗传算法在双d s p 平台上的实现技术研究 所以搜索效率不高，有时甚至使搜索过程限于局部最优解而停滞不前。与此相对应， 遗传算法从有很多个体所组成的一个初始群体开始最优解的搜索过程，对这个群体进 行的选择、交叉和变异运算保留了群体的多种信息。这些信息可以避免搜索一些不必 搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行 性。遗传算法在解决t s p 问题中的不足： 实际应用中遗传算法易出现两难境界：当交叉概率和变异概率选择为较大时，算 法能够在全局中找寻到最优解，但耗时相当巨大，算法收敛性较差，往往丧失实时性 或不满足时间要求；当交叉概率和变异概率选择为较小时，算法收敛性较好，但容易 产生早熟现象，陷入局部最优。对不少问题，基本遗传算法的求解效果往往不是最为 有效的，它比专门针对某一问题的知识性启发算法的求解效率要差。另外，遗传算法 也无法避免多次搜索同一个可行解，这也是影响遗传算法运行效率的一个因素。 下面给出遗传算法关于收敛性的欺骗问题： 欺骗问题( d e c e p t i v ep r o b l e m ) ：在遗传算法中，将所有妨碍评价值高的个体生 成从而影响遗传算法正常工作的问题统称为欺骗问题。遗传算法运行过程中具有将高 于平均适应度，低阶和短定义距的模式重组为高阶模式的趋势。如果在低阶模式中包 含了最优解的话，则遗传算法就可能找出它来。但是低阶，高适应度的模式可能没有 包含最优串的具体取值，于是遗传算法就会收敛到一个次优的结果。”3 下面是有关 欺骗性的概念： 竞争模式：若模式h 与h 中，啪q 位置完全一致，但任一确定位的编码均不同， 则称h 与h 互为竞争模式。 欺骗性：假设f ( x ) 的最大值对应的x 集合为x 宰，h 为一包含x 的m 阶模式。h 的竞争模式为h ，而且f ( x ) f ( h7 ) ，则f 为m 阶欺骗。 由此雨提出的各种变形的遗传算法( v a r i a n t so fc a n o n i c i a lg e n e t i c a l g o r i t h m s ，简称v c g a ) 。其基本途径概括起来有以下几个方面： 1 改变遗传算法的组成成分或使用技术，如选用优化控制参数，适合问题特性的编 码技术等； 2 采用混合遗传算法； 3 采用动态自适应技术，在进化过程中调整算法控制参数和编码粒度； 4 采用非标准的遗传算子； 5 采用并行遗传算法。 混合遗传算法体现在两个方面，一是引入局部搜索过程，二是增加编码变换操作 过程。在构成混合遗传算法时，一般遵循下面三个原则： 1 尽量采用原有算法的编码； 2 利用原有算法全局搜索的优点； 3 改进遗传算子。 南京航空航天大学硕士学位论文 2 6 混合遗传算法的设计实现 下面在简单介绍模拟退火算法的基础上，设计并实现混合遗传算法，并对试验数 据进行分析。 2 6 1 模拟退火算法简介 下面简单介绍一下模拟退火算法，详细原理可参阅相关文献”。 模拟退火( s i m u l a t e da n n e a l i n g ，简称s a ) 算法是一种非导数的优化方法由于 它对离散( 组合) 优化问题像对连续问题一样适台，因此近来得到了较多的关注。当s a 最初被提出时，主要是因为它在寻找大规模组合优化问题近似解方面的作用而知名 例如旅行商问题( 为必须轮流到n 个城市的旅行商找到最短环形路线) 和配置问题( 确 定使总面积最小的计算机芯片布局) 近来有关s a 及其变形的应用还显示：当要求解 连续优化问题时，这类优化方法被认为与其它优化方法一样具有竞争性 固体退火是先将固体加热至熔化，然后徐徐降温、冷却使之凝固，最后形成晶体。 退火过程之所以必须徐徐进行，是为了使系统在每一温度下都达到平衡态，最终达到 固体的基态。这个过程若控制不好，可能产生非晶体的亚稳玻璃体。在退火中，处于 若平衡下的物理系统的能量会发生变化，晶体生成则物理系统的能量为最小，玻璃体 生成则对应其能量为局部极小。 在模拟退火法中，我们试图最小化的目标函数的值类似于热力学系统中的能量 温度高时。s a 允许对远处的点求函数值，并且有可能接受一个具有较高能量的新点 这对应高活动性的原子，它力图与其它非局部原子一起将自己定位，能量状态可以偶 尔上升温度低时，s a 只在局部点处求目标函数值，它接受较高能量的新点的可能性 非常小这类似于低活动性原子只能与局部原子起定位的情况，能量不太可能再次 上升。 模拟退火算法基本流程： 1 建立算法的初始状态：给定初始温度t 。，及初始解x 。，初次迭代次数k 。以及 初次迭代k 。的变换次数l 。，计算该点的函数值f ( x 。) 。 2 随机产生扰动ax ，得到新点x = x 。+ ax ，计算新点函数值f ( x7 ) ，及函数值 差a f = f ( x7 ) 一f ( x 。) 。 3 若af o ，则接受新点，作为下一次模拟的初始点： 4 ，若a f 0 ，则计算新点接受概率p ( f ) ，如果p ( f ) r ，则接受新点作为 下一次模拟的初始点；否则放弃新点，仍取原来的点作为下一次模拟的初始点。 5 对应每一次迭代，会有l 次变换，亦即生成l 个新解，这也是邻域结构s 的 大小。对每一个新解重复步骤2 ，3 ，4 。 6 迭代次数k = k 。，1 ，增加迭代次数，对每一次迭代，重新生成邻域结构s ，和变换 混合并行遗传算法在双d s p 平台上的实现技术研究 次数l ，重复步骤2 ，3 ，4 ，5 7 按退火时间表降温，计算新t 值，重复步骤2 ，3 ，4 ，5 ，6 8 达到中止条件后，接受解为全局最优解 由算法流程可以看出，模拟退火法依据m e t r o p o l i s 准则接受新解，因此除接受 优化解外，还在一定范围内接受恶化解。开始时t 值较大，可能接受较差的恶化解； 随着t 值的减小，只能接受较好的恶化解；最后在t 值趋于零时，就不在接受恶化解 了。这就使模拟退火法既可以从局部最优的陷阱中跳出，更有可能求得组合优化问题 的整体最优解。 m e t r o p o l i s 准则”：假设以粒子相对位置表征的初始状态为i 作为固体的当前 状态，该状态的能量为e 。然后用摄动装置使随机选取的某个粒子的位移随机地产生 一微小变化，得到一个新的状态为j ，新状态的能量为e ，。如果e e j ，则新状态是否作为重要状态，要依据固体处于该状态的 几率来判断，如公式所示： r = e x p ( ( e , - e 。) k 。)( 2 5 ) r 是一个小于l 的数，用随机数发生器产生一个 o ，1 区间的随机数e ，若r ，则新状态j 作为重要状态，否则舍去。如新状态j 是重要状态，就以j 取代i 作 为当前状态，否则仍以i 为当前状态。再重复以上新状态的产生过程。在大量重复比 较后，系统趋于能量较低的平衡状态。上述接受新状态的准则称为m e t r o p o l is 准则。 m e t r o p o l i s 准则已被理论和大量实践证明是具有绝对收敛性和全局寻优性的。 退火时间表及其构建原则： 任何有效的冷却进度表都必须解决两个问题：一是算法收敛性问题：模拟退火法 本身可由热力学平衡态统计理论和随机过程的m a p k o b 链理论证明在一定条件下具有 最终收敛性。但实际应用中必须谨慎选择温度参数t 的初值t 。，t 的衰减函数，t 的 中止值t ，和变换次数l ；二是算法的计算性能问题：它包括平均情况下最终解的质量 和c p u 时间两个指标，二者很难两全其美，一般会采用在合理的c p u 时间里尽量提高 最终解的质量的方法，这也涉及所有参数的合理均衡选取。 一般选取退火时间表有两种方法：一是在大量试验的基础上基于经验采用折衷原 则，这种方法简单有效但有赖于丰富的实践，而且存在不确定性。二是由已求得的最 终解的质量入手，进行精细的分析与推证，来设定退火各参数，这种方法效果明显， 但对有些复杂问题分析工作量极大，且特殊情况下会导致算法陷入局部最优。 2 6 2 混合遗传算法中模拟退火部分的设计 由前面的模拟退火算法的编程流程可以设计与遗传算法合作的的模拟退火部分 的大概流程如下： 由遗传算法得到当前种群p 南京航空航天大学硕士学位论文 w h i l e ( 不满足中止条件时) d o f f o r 每一个个体s i p d o s = s i 从s 中随机选择城市c r e p e a t i f ( r a n d 0 p ) 从s 中剩余城市中随机选择城市c e l s e 从p 中随机选择另一个体s 。 寻找s 。中城市c 相邻城市为c ， i f ( s7 中城市c 的下一城市已经是e7 ) 从重复循环中退出 否则反转在s 中城市c 到城市c7 间的部分 l i f ( e v a l ( s ) e v a l ( s i ) ) s i = s 7 e l s ei f ( r a n d 0 p 1 ) s i = s i f ( e v a l ( p7 ) r e v a l ( p ) ) p = p 7 e l s ei f ( r a n d 0 p 1 ) p = p 值得一提的是，p 。的取值是随着种群的迭代而衰减的，其变换规律应按式2 - 4 的 原则设计，在本课题里，我们将退火时间表里的初始温度定为固定迭代次数3 0 0 ，衰 减规律为每一代减l ，亦即0 3 3 3 从上述流程中可以看出，混合遗传算法的编程思想及其在算法中的实现手段是借 鉴了模拟退火法中的一些思想的，又具有自身的特点： 1 模拟退火部分中在每一代进化中，每个个体都参与遗传操作，且每个个体只 与自身经遗传操作产生的子代进行竞争。 混合并行遗传算法在双d s p 平台上的实现技术研究 2 模拟退火算法部分会对操作产生的新群体进行平均适应度评估，根掂其平均 适应度和当前退火系数决定是否使用新种群替代旧种群。 3 。每一代中每个个体参与的退火操作的次数是出算法中运行情况决定的，而不 是作为参数人为设定的。 2 7d s p 环境下算法的实现 试验的软硬件环境： l _ 基于a d s p 2 1 0 6 0 芯片的开发板，具有片外s r a m ( 设计中未使用) ，具有j t a g 接口 和串行线接口 2 开发软件：v i s u a l d s p + + 3 o 。 2 7 1d s p 开发软件的数据检测手段 在p c 机操作环境下，有许多方便的软件可以进行程序运行时效的检测和记录。 而v i s u a l d s p + + 3 0 开发平台，提供了多种代码分析工具，可以较为精确地分析代码 的执行效率，找出低效率的代码段。它有两种代码分析工具，分别对应软仿真和硬仿 真。在没有硬件仿真器的情况下，可以运用它提供的线性轮廓工具( l i n e a r p r o f i l i n g ) 进行测试，而在有硬件仿真器的时候可以应用它提供的统计轮廓工具( s t a t i s t i c a l p r o f i l i n g ) 进行测试。后者是在用户目标板真正工作时，通过随机地采样目标板的程 序计数器而得到的统计数字，相对而言，l i n e a rp r o f i l i n g 工具是采样程序计数器 的每个执行周期，因此它所测得的结果在理论上应该较为精确。 事实上，只要巧妙使用s i a r c 系列的e m u c l k 和e m u c l k 2 这一组寄存器，就可以精确 的得到程序运行的时钟数。在知道系统时钟数的情