相关标签

基于智能优化算法的选播路由方案设计与实现

发布时间:2019-12-04 20:16

  摘要

  科学既改变了人类的生活,又推动了社会的进步。然而社会的进步使得各行各业的竞争压力更大,网络发展也不例外。现阶段的网络,服务容量和服务需求不协调,后者早已超越了前者,对QoS服务的应用产生了很大的影响。生活中人们处处使用网络,已经习惯和依赖如今的网络服务,这就显得互联网服务更具吸引力。现阶段,网络服务的容量比较缺乏,所以为了提高服务的利用率,复制服务器技术被网络服务提供商引进;然而我们可以利用选播路由技术给用户提供最优的服务器并且均衡服务器间的负载。本文中学习和研究了GA、TS、SA的基本原理及它们的优缺点,分析了基于遗传算法作为主体的混合优化算法的原理,主要优势和不足之处。最后提出了基于混合策略的全局路由优化问题的解决方案。该算法以负载分配和网络资源消耗为目标函数,以网络资源的最小消耗为基础,最小化总路径和,最少化路径调整次数而且相对均衡服务器的负载。

  关键词:智能优化;遗传算法;模拟退火;禁忌搜索;混合优化策略;选播路由。

  前言

  人们对于优化问题的重视程度随着社会各方面的发展进一步提高。虽然优化问题是当今社会的热点研究对象,但是它也被认为是当今科学工作的难点,其研究的目的是在众多方案中找出最优的方案。高速数字计算机的大量应用随着科学技术的快速发展更进一步,为优化问题的研究和解决提供了有利的线索和必要的工具。在实际应用中,优化算法以及它的理论作用显得越为重要,在各类因素的推动下,优化理论及优化算法已经发展为包含线性和非线性规划,动态与几何规划等分支在内的新型学科。

  近几年来,由于人们所面对的问题越来越复杂化,这些常见的优化机制已经无法解决一些难点问题,这也推动了研究人员和学者把研究目标转向提高优化算法的性能和效率问题之上。

  本文通过分析目前常用的一些智能优化算法的机制,在研究和掌握这几种算法的基础上,处理实际优化问题时通过混合策略,融合或者结合等机制达到去粗取精,提高算法的应用能力的目的。

  全文共分五章。第一章中,主要讲述智能算法的研究背景与意义。第二章中主要讲了在实际应用中遇到的一些智能算法,他们在应用问题中的特点。第三章是混合策略下的智能优化算法。第四章是混合策略应用在选播路由问题,讲述了混合机制下的优化算法的优点,功能,实现步骤等。第五章是对课题的总结和和未来在网络发展方面的展望。

  第1章 绪论

  本章中依次讲解了智能优化算法的研究意义及背景,混合智能优化算法在国内外的进展和应用;

  1.1 智能算法的研究意义

  最优化问题是目前在多个范畴中常常碰到的问题,包括在教育,信息,军事,航空等多个工程范畴的问题,可以把这些领域内的问题看作优化问题提出解决方案。在诸多领域范围内,跟着社会化网络和计算机技术的跟着进一步完善,各类工程领域都引入了智能优化并且在这些领域内的应用愈广泛。譬如产业工程中的智能操控,管理科学领域中的智能策略体系创建,矿山工程中的材料填充和优化质量等,这些领域都跟智能优化细细相连。虽然现阶段人工智能和计算智能取得了显著的实践成果,但都无法回避地展露出其利用的约束性。智能优化策略问题的重要性通过人工智能等智能技术取得的进展,超强的性能和在实际问题中的应用被证明。现阶段,国内外还没有形成彻底处理智能优化策略问题的完善的理论和方法。

  在计算机网络中智能优化算法是能够很好地处理路由优化问题的一种方式,因此也被国际上科学界的很多学者关注和钻研。智能优化算法是怎么来的,需要我们了解,它是通过研究自然界或生物界的规律和原理、通过模拟它们的规律来求解现实生活中复杂的问题的一种算法[1]。它是遵循生物或者自然界的生存竞争中适应力强的保留,而适应力差的被淘汰的这一原则,把不适合的解淘汰掉,保留满足要求的解,通过这种方式去搜索问题的最优解。近三十多年来,许多专家和学者致力于智能优化算法的研究,提出了许多的不同类型的智能优化算法,如神经网络,遗传算法、鱼群算法、文化基因算法,模拟退火算法、粒子群算法,蚁群算法等等[2];一般的传统搜索解决不了数量未知的,或者是规模过于庞大的复杂而繁琐问题和不确定元素的问题。NP-hard问题是众所周知的难点问题,智能优化是解决这类问题的重要方法之一;然而随着出现各类大规模,复杂的优化问题,我们常用的智能优化算法都有它自身的缺陷。这些年来科学界的许多研究人员为了提高算法的性能对智能优化算法尝试改进,找到更好的改进方案 ,但是算法的自身缺陷还是没能从根本上解决。所以,有不少学者针对在实际生活中遇到的问题,给出了结合两种或者多种智能优化算法,利用它们的优缺点,实现结合优点避免缺点,增强算法求解繁琐,复杂问题的能力,也取得了很好的成果。实际应用中,使得算法的收敛性增强,解决复杂度高的各类工程问题,继续研究各类智能算法,提出和实现新的或者是性能更强的混合策略下算法显得更为重要。

  1.2 智能算法的研究背景

  1.2.1 智能控制

  说道智能控制,它是这些年来新出现的学科,有许多分支,包括专家控制,学习控制等。没有精确的数学模型和严格的假设的前提下,智能控制可以解决工程中真实有的不完全性或者不确定性、非线性的问题。

  智能控制的分支还有很多,比如各种混合型方法以及神经网络控制,模糊控制等。 有些研究人员把一些进化算法也当成智能控制。模糊控制以及神经控制是在一些智能控制系统中发展相对较快的,它们在智能优化方面的作用也很显著。几年前,智能控制得分支模糊控制系统取得了突破性的成就,和神经控制也是。在工程领域的工厂,包括机器人在内的很多机器,一般没有智能控制部分在内,它是通过按部就班的方式完成工作的,它不属于智能控制。由于当今社会乃是网络信息化社会,对人工智能,大数据等,每个人都有所耳闻,因此研究各类智能算法被广大计算机爱好者和科学工作者所喜欢,越来越受欢迎。各个领域对它们的要求都很严格,因此不难看出智能控制在智能机器人领域中更普遍的运用。

  1.2.2 搜索机制

  搜索是推理工作中不可或缺的一部分,也是在人工智能中占据主导地位,它能够影响到智能系统的工作效率和性能。精准的搜索策略作为搜索问题的关键,不但能决定状态或问题的访问次序,还能够扩大状态空间。

  u 传统的搜索方法

  传统的搜寻办法可以被用来处理一部分相对简单的问题,包含图搜索方法,深度优先搜寻及广度优先搜寻。把这几种搜索方法作为基础,发展了启发式搜索策略,有序搜索,此中最有名的是A*算法。启发式搜索策略战胜了毫无目的搜索扩大节点的随意性,很大程度上提升了算法完成的效率

  u 规则演绎和推理

  针对一些复杂系统的优化问题,传统的搜寻方式平常力所不及,但是规则演绎体系则为处理这个缺陷开辟了新的道路。它具有反向,双向和正向的规则演绎系统。对于复杂度很高的智能优化问题,对它仅仅使用系统组织技术是远远不够的,我们还需要对它用规则演绎。

  对于一个特别复杂的系统使用优化算法时,高复杂度,不清楚的因素,而且有不完全性,所以需要设置一种计算机制和它的推理步骤。一种不明确性表现在对证据,结论,同一事实的规则系统的不明确性,而另一种是不使用位次的推理方法。

  u 专家系统

  专家系统有诊断和预测,检测和规划,揭示和控制等多种类型,它们都是一种系统而且在人类专家水平上处理问题,它是人工智能的一个主要而灵活的分支 ,它的使用填补了人类专家缺少等空缺,并且能够解决专家的丰富知识和经验的利用、推广和保存等问题。专家系统事实上是以产生式系统为基础进步发展的。它有学习人类专家积累和研究过的知识,经验,为了提供更好地科学策略,继续搜索,推理研究。专家系统可以结合人类专家的经验和各类算法的多方面的优点,它最突出的优点时没有工作时间限制,也没有工作环境限制。专家系统的特点有非常多,它有并行性,可分布式处理问题,也可以协调其他专家系统工作,有自学能力,检测和诊断错误的能力。

  u 机器学习

  对于机器学习而言,它的主要工作就是学习。机器学习领域中的研究的重点是想方设法让机器像我们人类一样通过外界的环境因素来进行学习,提高自身的效率。假如,有一台带有程序的机器,在这个程序的作用之下,它能够跟着解决问题的积累可以增强自身的性能,自身的处理问题的能力,这样的程序我们就认为他有学习的功能。如果这样的一台机器,之前解决某一个问题是给了解决方案A,但是他随着解决的问题的数量增多,当过一段时间后再次遇到之前的这一问题时这台机器给出了解决方案B,经过测试B方案确实比方案A更准确,或者更容易实现,更容易理解,那么我们称这台机器的解决问题的能力有所提高。

  u 遗传算法

  遗传算法是近似算法,它存在仿生学原理,即模仿或者模拟生态系统中的各类生物的遗传方法,选择方法研究出的算法,有很强的地位。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象[4],算法每一次的迭代,就会产生一个候选对象,遗传算法则会选择次优解作为新的解,对他们按照某种循序组合,产生新一代的候选解群。除非算法已经处于收敛状态,否则对它反复之前的步骤。各种各样的复杂工程问题的优化,可用遗传算法来解决,因为它的并行性非常适合在并行机上操作。在实现具体操作中,我们可以通过保存最优值,遗传算法的混合机制等方法来确保算法在最优解上收敛,这就处理掉了算法早熟问题,局部搜索的性能差问题。

  u 进化算法

  进化策略和基本遗传算法等算法是属于进化计算的,根据研究表明,如果更深刻的研究这些算法,可发现它们的区别愈来愈小,几乎没有什么明显的区别的。对于生活中的其基本着眼点是基于对生物进化过程的模拟,开发一种具有较强鲁棒性的通用计算模型[5]。

  第2章 常见的智能优化算法以及其特点

  智能优化算法是人类通过自然进程,遗传变异及与各种生物之间的生存竞争等一系列过程的仿照和演化而形成的。主要包括以下几种形式:模仿人类的行为,生物的举动,以及仿照物理学原理的优化方案。它们都是从任意的可行初始解开始,经由适者生存的过程,去迫近问题的最优化解决。即使上述智能优化算法无法保证最后肯定能求出题目的最优解,它们也能够在搜索精确度和计算复杂程度之间找到一个平衡点。至今为止,一大批研究人员提出了许多的智能优化算法,比如属于群智能算法类的粒子群算法,属于进化算法类的遗传算法,还有很多智能算法,在这里不详细介绍。无论是在教育,经济,航空,工等诸多领域当中的那一种,如果要解决NP-Hard问题,智能算法是最合适的参考对象,完全可以解决一般的NP-Hard问题,因此他在这些领域一直在普遍的被利用。智能优化算法有很多种,在本课题当中,我们重点学习遗传算法,模拟退火,禁忌搜索这三种算法以及它们的两两混合机制和三者混合的混合策略,学习原理及特点,实现步骤。

  1.1 遗传算法(Genetic Algorithms 简称 GA)

  遗传算法(Genetic Algorithms 简称 GA)是模拟生物在自然环境中的遗传和进行过程而形成的一种高度并行,随机和自适应的通用性优化算法 [6]。即根据优胜劣汰、适者生存的自然规律,也就是在求得最优解的过程当中保留有用的部分,去除没有用的部分。在科学实践活动中的体现是,在全部可能的解决策略中找出最能满足这一问题所求的前提条件的解决方案,即找到一个最优解。

  遗传算法是迭代算法,它的初始解时任意设定的,而产生的新的解是由初始解通过模拟进化,继承等一系列遗传操作产生的,目标函数判断它的每一个解,通过一次迭代变成一代。

  典型的算法步骤有:

  通过研究人员和科学工作者的不断研究,在理论方面,它的收敛性已经被证明,然而在实际应用遗传算法的时候,有研究表明它在很大程度上依赖遗传算子,对于设置的参数,也有一定程度上的依赖。假如有并不完全符合条件的遗传算子做这个算法的参数,很有可能导致早熟。我们需要对遗传操作进行优化,因为遗传算法在求解问题的过程中可能会出现求到次优解、也有可能出现进化速率低、陷入局部解等一系列问题。

  遗传算法的设计主要按以下步骤进行:

  2.0.1 遗传算法特点

  遗传算法的一个显著的优势,是有很好地的稳健性,它的特点是:

  (1) 遗传算法和传统优化算法的最大的区别在于它仅仅利用适应度函数值确定搜索规模和搜索方向,并不需要导数等其他知识来辅助,且遗传算法从问题解的串集开始嫂索,因此覆盖范围大,有利于全局择优。一般的优化算法易陷入最优解是因为它的最优解是从一个初始解迭代得到的。

  (2) 单点搜索算法很容易就可能陷入局部最优,而一般比较传统的搜索算法都属于单点搜索,所以他们都容易陷入局部最优。群体中的很多个体解能够同时被遗传算法所解决,这就降低了陷入局部最优解的可能性。

  (3) 具备自己学习、自己适应及自己组织能力。硬度较大的个体在遗传算法自行组织搜索在演化过程得到的信息时,可得到环境适应度较高的基因构造,它的生存几率也更高一些。

  (4) 遗传算法的优化对象是决策变量的编码方式,即采用合适的编码策略,有助于解决复杂的优化工程问题。

  遗传算法的收敛性研究方面,虽然已经有了一些研究进展,可是还是存在专业的分析,中肯的评价。遗传算法的研究问题上,科学工作者群体优化的收敛概率,收敛速度,交叉和变异方法,优劣判断等方面需要进一步研究。

  2.1 模拟退火(Simulated Annealing,简称 SA)

  SA有仿生学思想,它的出现离不开固体退火的原理,因为它就是通过研究,模仿这一原理而出现在科学界的优化问题上,也就是通过研究在一定温度上的固体物质,渐渐地降温之一过程,并用计算机模拟这一系列反应。当加热一个固体的时候它的热能会增强,固体中的每个原子都处于很强的热运动,当温度提升到这个固体的极限时,它的形态被完全的破坏掉,而冷却这个高温固体时,它的原子慢慢的变的有序,随着冷却时间,热能也渐渐降到最低,渐渐的达到平衡,最终在常温的时候能恢复到加热之前的原状态。SA是一种几乎可以找到问题最优解的迭代算法,因此在各类工程的优化中被大量使用。给模拟退化算法设置一个初始状态,同时设置一个初始的温度,在解空间范围内随机的搜索就可以得到整体的最优解。

  通过分析SA的基本原理,可知,模拟退火法在一系列递减温度下产生的点列,从理论上讲,可以看作是一系列的马尔可夫链(Markov Chains)[7]。为了让目标函数的分布规律符合玻尔兹曼分布规律,在给定的温度下,我们可以用反复进行马尔克夫过程,如果以足够慢的速率让系统温度降低,就可以使得玻尔兹曼分布收敛于它的均匀分布。虽然理论上认为只要有足够的计算时间,模拟退火算法就能确保以低几率收敛于全局最优点,但在算法的实现过程当中会发现优化效果因为受到计算时间及速度等因素的约束,很难确保结果的全局最优。而且,在所有温度下难以判断是不是到了平衡状态,即很难控制马尔可夫链的长度,反映到算法上也就是说难以控制Metropolis过程的次数。除此之外,模拟退火算法也有不够科学的地方,即模拟退火算法中的退火方式,T自始至终都根据优化前设定的规律改变而没有纠正。以上分析结果表明,模拟退火算法的主要难点是:管理温度和控制退火速度以及设定它的初温

  2.1.1 模拟退火算法的特点

  模拟退火(SA)算法是一种适用于很多已知信息量较少的问题的随机搜索算法,也是一种全局优化方法, 它的特征主要包含下列几点:

  1) 以特定的几率接纳恶化解,SA算法在迭代过程当中,接受使目标函数变“好”的探测点的同时还能以特定的几率接受使得目标函数变“差”的探测点,迭代中呈现的状态是随机发生的,即以某种可能容纳的退化状态的呈现。

  2) 优化过程将被带入的控制参数分为不同阶段,并且由它决定各阶段随机状态的舍取尺度,接受函数被算法给予一个简洁的数学模型,接受概率跟着温度的降低而渐渐下降。

  3) 利用对象函数值开启搜索,SA算法确定深度搜索领域及搜索方向时,只需利用由目标函数转化而来的适应度函数值就能达到目的,不需要额外信息来辅助完成。

  4) 模拟退火的强大本领之一是它有全局优化搜索,而且它不受搜索空间和时间的约束。在某种程度上,算法能在某种程度上容忍目标函数值较差的状态,即可以向着好的方向发展也可以向坏的方向发展,只要给它足够的时间,即便进入了恶性圈套中,它也可以从坏的方向,向好的方向发展,最终也能够成功的在最优解收敛。

  2.2 禁忌搜索

  禁忌搜索(Tabu Search,TS)算法是模仿人类智慧的一种全局优化算法,现已应用于多个工程。在函数优化问题里,禁忌搜索算法依赖自身灵活多变的特性,通过实数标记全部的参数,实现了程序的更加清楚与直观,与此同时也防止了编解码过程中的延时现象的出现。作为一种全局优化策略,具备比较强大的爬山本领,能依靠其独特的记忆机制诱导搜索程序生成局部最优解,以此接近全局最优。所谓禁忌便是阻止反复出现之前形成局部最优的状态。禁忌搜索算法在禁忌对象、邻域构建及特赦准则等的选择上拥有很好的灵活性,方便我们解决问题。可因为其理论基础不够全面,相比于遗传算法而言禁忌搜索算法尚无一个完型,其中邻域规模和禁忌长度等参数的选择也在一定程度上依赖经验。如今,主要从两个方面展开对禁忌搜索算法的研究:包括理论及实践研究两方面。

  禁忌搜索算法的设计,需要确定算法的以下环节:

  2.2.1 禁忌搜索算法的特点

  禁忌搜索算法的局部搜索性能较好并有爬山能力,在搜索过程当中,不但可以接受劣解,且还能 够生成局部最优解,所以全局最优解获取的几率也提高了不少。此外,搜索过程当中的新解不是在目前的解空间内随机获取的,必须比目前最优解或者非禁忌的最优解更优,所以选取优良解的几率比较大。

  禁忌搜索算法也有不可否认的缺点:第一,算法在一定程度上靠初始解的好坏,质量低的初始解会减慢搜索的收敛速度进而搜取到低质量的解;此外,由于禁忌搜索采取串行的搜索方法,搜取时每代的当前解必须只能有一个,相比于其他并行搜索算法而言,搜索性能占劣势。

  第3章 智能优化算法的混合策略

  3.1 开发混合算法的原因及目的

  就像每个事物都有两面性,智能优化算法也是一样,各有个的优点和缺点,优化问题随着规模变大,也跟着复杂起来。虽然遗传算法的稳定性高,全面优化能力强,也能解决各类繁琐的全局优化问题,但是规模很大或者超大规模的全局优化问题来说,它显得任务解决性比较差。对于神经网络,它可以从数据中学习,提高自身性能,但是存在表达知识比较困难的缺点。粒子群算法,它虽然存在搜索不够精准、搜索性能相对弱以及轻易误入局部最优解的局限性,但是它具备搜索速度快、稳定收敛和记忆功能强大等优势。再说蚁群算法,它有很好的全局搜索,分布式计算,还具有鲁棒性,但是它搜索速度较慢,需要的时间较长、而且很容易出现早熟等一些缺陷。我们在文章中重点介绍的模拟退火算法和禁忌搜索算法也不例外,前者局部搜索比较快,需要运行的时间也很短,但是全局搜索能力很差,这样的话会影响参数;后者操作方便,简单,并且引入了禁忌表,利用这一技术充分避免了重复搜索,局部领域也不会陷入局部最优,这也提高了自身性能,但是它对于初始解的依赖比较大。

  通过阅读大量参考文献了解到对于这些算法的缺陷,研究学者对他们提出了很多改进方案,这些方案也有了很大的帮助,算法的性能提升了一个层次,可是并没有找到从根本上解决这些缺点的方案。对于特定的问题,有不少学者提出用混合策略将两个或多个算法相结合,充分利用这些算法的互补性 ,实现优势互补,缺点避免,而信息增值。开发混合算法的目的将单一算法之前的优点保持不变,减弱它拥有的缺陷或者直接消除,将混合后的算法的解决问题能力大大提高。为了我们能够综合的利用这些混合策略下的智能算法,继续提出并实现它们的优势互补,克服缺点,并全面提高这个算法的全局收敛性,局部收敛性。

  本文中为了构造高性能的优化算法,我们把一些常见的智能优化算法作为研究对象,在分析这些算法的核心部分以及主要性能并继续研究和设计以上智能优化算法的混合策略。

  3.2 常见的混合策略

  3.2.1 模拟退火—遗传算法

  模拟退火算法 (Simulated Annealing,简称 SA)和遗传算法(Genetic Algorithms,简称GA)是两种通用且有效的指导性搜索算法,为复杂问题的优化提供了新的途径;虽然SA算法的性能在一定程度上受温度的影响,但缺乏并行性,不保留历史及冗余信息,且每次只保留一个解。不同于模拟退火算法的是,GA 算法虽然可以在某种程度上存储历史信息,它也具备并行性,但很难以调控收敛性,表现为早熟等异常现象。

  结合模拟退火概率突跳特性和遗传算法群体并行化搜索能力提出一类 GASA 混合优化策略如下:

  上述混合策略在顺利避免模拟退火的低收敛性和遗传算法的收敛易早熟等局限性的基础上,将模拟退火算法的搜索规模大的特点和遗传算法的收敛速度快的特点集于一身。在GA操作中,选择加入了杰出个体保护策略集自适应的进化操作,使已获得的进化成果不丧失,又保证高适值的解,加快GA收敛的同时,低适值的解防止GA陷入局部极小,从而防止算法陷入局部最优[8]。通过添加记忆功能,当SA运作和调控收敛性时,使搜索处于最优状态为条件的基础上降低计算量,达到高效搜索地目的。利用这些改进的策略,我们可以加快优化的收敛速度的同时也可以提升搜索效率。

  3.2.2 贪婪—遗传算法

  贪婪算法可以说是比较突出的领域搜索的技术,它的初始解是被随机选择的,在后面的搜索过程当中,假如找到了更优解,把它当成新解,解的质量不能被所有的邻域操作而改变之前,继续反复做之前的操作。贪婪算法得局部寻优能力是非常强大的,它不会考虑整体最优,因此在当前看来,它做出的选择是最好的。但是对于有些问题,它得不到全局最优解。

  对于贪婪算法和遗传算法的混合机制,在进化的时候,它的主题仍然是遗传算法,对遗传算法的每一个种群都需要做贪婪操作,又因为贪婪操作自身都需要一定的时间,再加上对遗传算法的所有新种群做贪婪操作,这样就导致了计算时间很长,降低性能,减慢收敛。所以在这种情况下并不能对遗传算法所有的新种群做贪婪操作,而是选择一些比较有的种群,对他们做贪婪操作,这样就没有之前的问题了。

  3.2.3 禁忌搜索—遗传算法

  算法的早熟会导致局部最优,而我们难以判断什么时候算法会早熟,削弱这样的缺陷的同时对GA和TS去粗取精,提高算法功能,在特定问题下的实际应用中,研究人员提出了混合机制来让它们更强大。禁忌搜索的局部搜索能力,遗传算法的全局搜索的能力,通过混合机制结合,提高各方面的性能,尤其是收敛性能!因为禁忌搜索的禁忌表,它有记忆功能,把它加入到GA中,构造新的重组算子TSR。因为GA爬山能力差,而 TS爬山能力强,结合它们的性能,可以GA,也就是说把TS作为GA的变异算子TSM。GATS通过把 GA具有多出发点的优势和TS具有的独特的记忆功能和较强的爬山能力强的优势相结合,保持GA 具有多出发点的优势的同时,还大大削弱了GA 爬山能力差的缺陷。

  第一步,让一条染色体作为TSM的初始解,经过TSM 以后,作为一个结果返回输出。由于它是一类搜索过程,因此确定移动值,需要调用评价函数;而移动值与禁忌表这两个因素就确定了那个移动值作为返回值输出。同样由于TSM 是一个TS搜索过程,在搜索过程中可以接受劣解[9],综上所述,TSM同样有爬山能力。

  TSR表中记录染色体的适应值,使用的禁忌表长度为7。假如渴望水平比子代适应值好,虽然它也被接受,但是它不属于禁忌。假如属于禁忌,我们让最好的父代进入下一代中,具体实现过程如下所示:

  3.3 GASATS混合策略

  3.3.1 GASATS混合策略的基本思想

  GA,TS、和SA这三种算法都只是经由目标函数和实际问题相互关联,表 ?3–1比较了这三个算法的。

  遗传算法(GA)是我们在实际生活中的解决优化问题时经常能碰到的并行化算法;禁忌搜索(TS)引入的禁忌技术能够避免算法陷入局部最优,有记忆功能,它是一种非常有效的优化工具,因此已经被应用于各种类型的优化问题当中。模拟退火(SA)算法也有避免落入局部最优解的方法,那就是用概率接受准则。通过结合表 ?3–1我们可以发现,尽管这三个算法都包含于领域搜索的范畴,但是各有各的优点和缺陷,具有相互弥补的特点。我们可以按照混合遗传算法的设计原则和这些算法的固有特点,可以将遗传算法、禁忌搜索算法和模拟退火算法相结合,组成混合算法,以达到结合它们优点的同时克服缺点的目的,提高他们求解优化问题的功能。在这一节中我们对GA,SA和TS这三个算法提出一种机制,就是要达到优势互补,克服缺点的目的;该混合策略算法成为混合遗传禁忌搜索模拟退火算法(GASATS)。

  初始解启发式方式或随机产生的单个解随机产生搜索域内的多个解(种群)启发式方法或随机产生单个解

  解的搜索方式从当前解邻域中随机产生通过交叉和变异从当前解邻域中随机产生

  迭代对象单个解整个种群单个解

  新解的选择Metropolis接受准则按适应值选择不被禁忌的最好解或者比当前解好

  搜索空间(-∞,+∞)(-∞,+∞)(-∞,+∞)

  确定性/随机搜索随机搜索随机搜索随机搜索

  表 ?3–1: 三种算法的比较

  在此混和算法GASATS里面,我们将TS和SA当作改进算法,将其应用到整体框架内,由GA负责控制算法的构造以及进程。在GA的复制操作中,为了提高GA,中每代的个体的,多样性而引入TS,生成新的个体,也以防GA落入局部最优而导致“早熟”现象,并且对新产生的GA种群,利用模拟退化算法优化。SA在整个算法搜索的初期可以接受更多的解,随着搜索进程的提高,只有较优的解才最有可能被接受,这样提高了GA的收敛性能,加速了算法的收敛[10] 。

  3.3.2 混合策略GASATS的运算过程

  让适应度值大的个体进入下一代的概率提高,同理,取概率大一点的变异算子,能够让适应度值小的个体进入下一代的机会更大。

  (二) 对遗传算法来说,适应值高的个体,可以通过选择算子的方法让它按照较大的几率生存下来,但是不适合的选择方式会让搜索过程陷入局部最优解得范围内,这会导致各个体趋于相同。尚未出现早熟时,假如群体中的各个体表现出不异性,除非用选择和交换,否则不能转移群体,这样导致了新的基因的不能进入算法最优解范围内,这样变异概率会较小。相同的运算被重复运用,降低响应时间,搜索能力,也会产生早熟。因此,我们可利用禁忌表,避免这些问题的出现。

  (三) 双层并行结构

  在各温度下逐渐进行降温操作时串行地实施GA和SA搜索,其中SA初始解是通过GA的进化结果提供的。GA有并行搜索能力,SA有概率突跳性,该算法通过结合这两个算法的这些能力,丰富了优化中的搜索性能和效率。总之GASATS很好地结合了这两个算法的优势的同时,满足了算法精度和搜索速度的要求。

  3.3.4 混合智能优化算法当前存在的问题

  ① 通过更深层次的研究,应该创新混合方法;

  极少数学者继续研究算法本身或者他们混合策略,现阶段的混合策略反而是针对这些算法自身的缺陷和特定的问题提出的,也就是说用某种策略将两个或多个智能优化算法相结合,形成混合智能优化算法。

  ② 对混合智能优化算法的内部机理性研究尚显不足;

  研究者从自己角度出发,对于一些特定的工程解决问题,提出一些多样化的混合机制而有了现阶段的这些智能优化算法,而且都是通过简单混合或融合它们的优点产生的。研究人员都是通过与已有算法比较它们自己按照某种混合机制提出的算法,证明它的功能更优或者更容易实现,但是很少有学者充分研究这些算法的内在联系,也没有提出全新的优化算法,这样就导致了算法的发展速度减慢。

  ③ 需要进一步加强混合智能优化算法的应用研究;

  已有的混合算法都是处于试验阶段,正式用于实践的混合优化算法很少,实用化的混合智能优化算法更是少得可怜。所以需要充分研究它们内在联系,进一步发展混合智能优化算法在实践中的应用。

  第4章 混合策略在选播路由上的应用

  4.1 网络通信方式

  现阶段计算机网络的通信形式主要有以下几种:Unicast ,Multicast , Broadcast ,Anycast;虽然还有其他通信方式,但是到目前为止还没有广泛应用;一种应用服务可以使用多种通信方式,也可以使用单一的通信方式。通过互相结合这些通信方式,利用很少的带宽完成繁琐的的功能,协同实现特定的服务。

  定义一个发送方和一个接收方之间的通信一个发送方和多个接收方之间的通信一个发送方和网内全部接收方之间的通信一个发送方和多个接收方中的任意一个之间的通信

  优点服务器及时响应客户机的请求;

  不同用户有不同的服务请求,这事服务器对他们发送不一样的,满足用户需求的消息。可以在因特网的宽带网上传送数据;节省服务器负载;提供的服务丰富。低负载;低成本;易维护;简单的设备。减弱了分布式拒绝服务攻击对用户带来的影响;拥塞被减弱;响应时间短。

  缺点服务器流量等于客户机数量和流量的积,数据流庞大导致服务器无法支持或者加大负载量发生丢包错包后难以弥补;服务质量不高,客户认证存在缺陷。比较单一,无个性。因特网上不能用广播传送数据;难维护;设备复杂;高成本;易受攻击。

  应用所有 LANs和 IP网络都支持单播通信方式,并且 http、smtp、ftp和telnet 等大多数服务也是以单播为基础的[11]。视频 会议、远程 教育、网络游戏、网络电视、数据收集等领域主要应用 在局域网协议复制服务器;并行计算;负载均衡;视频点播等领域我相信,随着科技和网络技术的不断发展,科学工作者还会研究出更多,更有效的通信方式。在这一章中我们重点介绍选播这一种通信方式。

  4.2 选播

  选播是IPv6中定义的一种新的通信服务,是为了达到服务质量QOS的要求提出的。选播消息是在网络中指定的接收者组中应该从源节点传递到一个成员的消息。传统的单播消息是选播消息的特殊情况,对于单播消息来说,接收者组的大小是一个。使用选播通信服务能够很大程度上简化某些应用。例如,当网络中有相同的服务的多个服务器时,客户端向一个适当的服务器发送消息要容易得多。多个镜像网站可以共享一个单播地址,用户可以简单地发送与选播地址的请求,以获得信息。

  选播被普遍的应用在大量领域中,证明了它的重要性;跟着新模式,新应用的网络不断出现,人们对网络的要求一直在提高;但是,选播提出的时间不长,在许多方面都存在着缺陷,限制着这种服务的发展,因此这些问题还需要研究人员的进一步研究并找到合适的解决办法。

  在 IPv6 中,选播地址从单播地址空间中分配,可以使用任何类型的单播地址格式,所以选播和单播在地址结构上没有任何区别,在 RFC 1546 中,选播地址和多播地址一样,都独立的占用地址空间[11]。 如果我们在网络中大规模的运用选播服务,那么对它预留分配空间是很有必要的。

  4.2.1 选播的应用

  ? 提高视频流传输的效率

  选播提高视频流的效率跟多播解决视频流的点播问题特别相像,视频流的点播问题选播能够很好地解决[10];在现阶段因为服务器资源的约束,网络带宽的限定原因,很难确保远程点播问题的服务质量(Qos),一般仅仅在局域网当中网络带宽相对较高,客户端的数量一般最多几百的情况下才能应用视频流的点播。

  ? 路由协议上的应用

  路由协议是选播的研究最多的一个方向,在网络层和应用层都有很重要的作用;

  自动选择和定位服务器等技术,就是对选播在应用层的作用体现。其中服务器自动选择能够应用在镜像服务器的提供这一方面。

  ? 负载均衡

  选播(Anycast) 能够有效地分摊网络中不同链路的负载[12]。选择最近的服务器,可以让路由系统的响应时间降低,延迟被降低,也均衡负载。

  4.2.2 存在的问题

  在计算机网络领域中,选播的性能越来越受欢迎,而且它对于很多计算机技术和网络技术的发展有着突破性的作用,但是到现阶段为止,也有不少问题没能很好的解决,需要研究人员更深刻的探索并找到合适的解决办法;还有下面的一些问题要处理:

  ① 交错服务问题

  网络的状况是时不时地出现变化,但是服务质量选播流的服务是需要一定的时间响应的,因此最初初始化的路径和最优的服务器,这个时候不一定是最优的,因为网络的状况是时不时地出现变化。无论采用上节哪一种方法进行 Qo S 选播流路由,都会产生不同区域的选播服务器和客户端之间交叉访问的问题,我们称这种问题为交错服务(Cross Service)问题[11]。

  ② 路由协议

  路由问题能够决定服务的效率和利用性,如果我们从选播服务的定义出发,路由协议最主要的用途是向客户提供“最近”的服务器,也就是说向客户做出合适的选择。除非研究出更多更新的路由协议算法,否则没有办法解决选播地址的路由。

  ③ 无状态连接

  所谓无状态的连接服务,就是将数据包投递到最近的服务器,而路由过程不依赖于以前的数据包,这是选播的自然属性,正是这种属性使选播能够平衡网络的负载[11]。被分段的数据包能够使得这样的无状态服务导致出人预料的结果。假如不相同的选播服务器上,同一个客户前后发送两个数据包,如果这两个数据包没有联系,也不是独自发出相应的请求,那么很有可能会导致通信异常!

  ④ 安全性问题

  网络中通信安全的重要性是家喻户晓得,否则可能会带来很严重的后果;选播虽然性能很轻,但比较容易收到各类攻击。可是到现在为止研究人员还没有研究出具体的解决策略,不难看出选播服务的安全性问题是多方面的。

  4.2.3 解决策略

  为了解决这些问题,需要科学工作者和研究人员在不辞辛苦的努力下才能够完成的。我们可以用路由调整或者是路由优化的策略来解决选播的交错服务问题;路由优化有两个类型,包括全局路由优化(整体优化)和局部路由优化,在本文中我们重点讲述全局路由优化的方式;对于无状态连接服务问题,虽然系统的成本会增多,但是我们可以用最直接的办法,IP报头的流标签,可以直接解决;选播路由的安全性和路由协议问题,包括无状态连接服务在内的解决策略有着直接或者间接关系,因此受这些解决方案的限制,在这里不详细解释。

  4.3 混合策略应用在选播路由

  在第三章中我们介绍了以遗传算法(GA)作为基础和整体框架,禁忌搜索(TS)和模拟退火(SA)算法作为辅助的混合策略的算法GASATS。 这个算法在保证遗传算法的选择,交叉,变异等重要环节的基础上,还要包含禁忌搜索算法的禁忌表以及模拟退火算法的退温函数,循环终止条件,状态产生和接受函数;之前我们在第二章中研究了该算法,给了实现方案,在这一章中的首要任务是利用该策略,优化路由。

  常见的路由优化方式有单流优化和全局优化,路由优化的目标有很多种,本文介绍以下四点作为路由优化的目标:

  ① 均衡网络的流量—太多的选播流堆在一个链路会导致这条链路拥塞,需要解决这一问题就得平衡各链路的数据流;

  ② 最小化总和路径;

  ③ 均衡服务器间的负载:为了达到这一目的,对每一个服务器平均的分配用户的各类请求;

  ④ 路径调整最少--保留尽可能多的路径不发生变化,避免大量路径调整需要消耗过多的网络资源[10]。

  4.4 实现过程

  定义为:

  四个目标函数的权重我们分别用a1, a2, a3, a4来表示。对f1(x), f2(x), f3(x), f4(x)取值都大于零而且在1之间取值的话,就可以保证F(x)恒正。

  4.4.3 群体的设定

  根据模式定理的内容我们可以知道,群体规模和大小对算法的作用有着很大的影响。如果群体规模太大,虽然获得最优解的几率增长,但是会导致计算时间很长即实验很长,影响优化甚至也有可能出现严重错误,而且我们最后算出的最优解在数据流调整时就不一定是最优解了。计算规模太小的群体让算法结果容易产生早熟。

  4.4.4 选择交叉操作

  因为基因位互不关联,所以在这个算法中,基因排列顺序对于计算结果没有影响,因此可以随意的选择交叉位置,利用多点交叉方式。为了保护在遗传算法中的较优的个体,选择操作采用比例和复制相结合的一种方法。

  4.4.5 变异和状态产生函数

  我们在该算法中利用模拟退火的状态产生函数和遗传操作的的变异操作互相融合的一种机制,然后随意的选择染色体基因位。

  4.4.6 状态接受函数

  4.4.7 禁忌表

  禁忌搜索算法的禁忌表的作用很大;通过用禁忌表可以成功的降低算法的计算时间,提高算法的执行能力,比其余算法速度更快。把它运用在混合策略上作用不言而喻。

  4.4.8 退温函数

  初始温度T0=|maxΔF| /lnP0,其中| max(ΔF)|为初始种群各染色体适应度之差的最大值,P0为初始接收概率[12]。

  4.4.9 内循环终止条件

  在生活中的实际应用中使用算法时,通过内部循环结束条件断定该搜索是否已经成功收敛在最优解,是否已经有了稳定的抽样。

  4.4.10 外循环终止条件

  算法的终止条件;判断在特定区域内有没有更好的结果出现;公式如下:

  第5章 总结与展望

  5.1 结论

  在本文中,我们通过对遗传算法(GA),禁忌搜索(TS),模拟退火(SA)这三种算法博采众长,实现优点结合,各算法的缺点尽量的被避免,提出了GASATS算法,它的主题仍是遗传算法;本课题通过混合遗传禁忌搜索模拟退火算法来实现选播路由的优化,体现出混合策略的优点,能够实现网络路径中路径总和最小,均衡网络的流量,均衡服务器负载以及最少调整路径的优化目标。

  5.2 后续展望

  在本文中提出的混合策略算法还存在一些不稳定的因素,需要在多方面的继续研究包括降算法复杂度。虽然跟传统的单一算法相比有不少优点和特性,但是实现太复杂会导致不能很好地被利用,也有可能被埋没而不继续研究。

毕业论文:http://www.3lunwen.com/jsj/dzjs/5428.html

上一篇:基于知识图谱的自动问答系统构建

下一篇:没有了

     移动版:基于智能优化算法的选播路由方案设计与实现

本文标签:
最新论文