前端规划:物流系统群智能优化方法
上QQ阅读APP看本书,新人免费读10天
设备和账号都新为新人

2
群智能算法

传统优化算法为优化问题的求解提供了巨大帮助,但在计算过程中也暴露出了一些缺点。[1]这些缺点主要表现为以下四点:①传统优化算法通常都是从一个初始点出发,每次迭代仅仅对一个点进行计算,这种算法架构很难发挥现代计算机高速计算的性能,尤其是高性能的多处理器计算机和现代并行计算模式往往很难应用到传统优化算法中,限制了算法求解大规模问题的能力和速度。②传统优化算法一般都要求目标函数是连续可微的,有时甚至要求是高阶可微的,但是在实际问题中这样的条件往往很难满足,这样就限制了传统优化算法的应用范围。③传统优化算法在每一次迭代时都要求迭代向改进方向移动,即每一次都要求目标函数值有所降低。如此算法就不会具有“爬山”能力,若算法陷入某个局部低谷,则无法继续搜索该区域之外的任何其他区域。因此,算法就失去了全局搜索能力。④每种传统优化算法只能求解一部分问题,即算法只能求解符合其适用条件的问题。要应用某种传统优化算法就必须简化甚至改变原有的问题,使之能满足该方法的使用条件。如果问题不满足传统优化算法的适用条件,那么用传统优化算法就无法有效求解。[23]

考虑到传统优化算法的不足,人们希望能够设计出新的有效的优化方法。特别是20世纪90年代以来,实际问题的结构越来越复杂,规模越来越大,不可微、非线性、不确定性、多目标已经成为问题的基本特征,而建立在解析基础上的传统优化算法往往对这些问题的求解显得无能为力。因此,人们逐渐意识到,必须探索新的优化方法来解决这些问题。计算机科学与技术的飞速发展,从根本上改变了人们的工作和生活,并已经渗透到各个领域,如何充分发挥计算机技术的优势推动优化方法的发展,成为人们越来越关注的问题。

20世纪60年代以来,智能优化作为一个新兴交叉学科,从无到有,由弱到强。智能优化的出发点是模拟自然以实现对复杂问题的求解,目前已成为系统科学、计算机科学、人工智能中最活跃的研究领域之一,得到了世界范围内众多学者的广泛关注和深入研究。[4-6]越来越多的人致力于研究自然界中存在的计算模式,先后从不同的研究视角通过模拟不同的自然现象从而获得更好、更有效的算法。智能算法是研究复杂的、不确定的、变化的环境中智能行为的自适应机制,包括学习能力、对新情况的适应能力、抽象能力、泛化能力、发现能力与联想能力等。智能算法具有很强的多学科交叉特点,它是生物学、神经科学、认知科学、计算机科学、免疫学、哲学、社会学、数学、信息科学、非线性科学、工程学、音乐、物理学等众多学科相互交叉融合的结果,是人们对自然的智能认识和模拟的最新成果,它的深入发展将极大地改变人们认识自然、求解现实问题的能力和水平。在工程技术、社会经济以及科学计算领域中存在大量的复杂计算问题,这些问题表现出高度的非线性、不可导、不连续性,复杂度非常高,在很长一段时间内科学家很难解决复杂系统的相关计算问题,于是开始模拟自然界的许多现象,如生物的演变进化、生物群体行为、DNA、文化、量子行为等,从而出现了智能优化,以试图解决自然或人造系统中的各类复杂优化问题,并已取得了很大的进展。[57-8]

智能优化算法的发展得益于运筹学、生物学、物理学、计算数学、计算机科学、人工智能和控制论等许多学科,充分吸收了这些学科的思想、概念和方法。智能优化算法,大都具备自组织性、正反馈性、鲁棒性、并行性和实现简单等特征,为在没有集中控制且不提供全局信息的条件下寻找复杂问题的求解方案提供了思路,为优化问题的求解开辟了新的途径。[9-11]应用智能优化算法求解优化问题时,其搜索过程通常具有以下一些特征:①个体都具有能执行简单的在空间或时间上评估和计算的能力;②当环境(包括其他个体)发生变化时,个体能够对变化做出响应,特别是出现值得付出代价的改变机会时,个体必须能够改变其行为模式;③不同的个体对环境中的某一变化所表现出的响应行为应该具备多样性。[12-14]

和传统优化算法相比,智能优化算法具有强大的全局搜索能力、问题域的独立性、信息处理的隐并行性、应用的鲁棒性和操作的简明性,是一种具有良好普适性和规模化的优化方法。它具有以下优化特点:①非单点操作,采用群体搜索策略。智能优化算法大都采用由多个个体组成的群体对可行解空间进行搜索,搜索过程中能够实现对各个个体所提供的信息的共享。信息的传播可以避免对一些不必要区域的搜索,既能提高算法的搜索效率,又能在一定程度上避免陷入局部极值。②智能优化算法在求解优化问题时,目标函数和约束函数可以不是解析的,更不必是连续和可微的。智能优化算法可有效求解那些目标函数没有明确表达式或有表达式但不可精确估值的优化问题。此外,智能优化算法对计算中数据的不确定性有较强的适应能力。③智能优化算法是对自然现象和自然规律的模拟,这些现象和规律所蕴含的深刻的优化思想为算法的设计提供了坚实的科学基础。在智能优化算法中,个体行为虽然简单但通过个体之间的相互作用,整个群体涌现出智能行为,而这种行为可用于优化问题求解。④智能优化算法不依赖于优化问题本身的数学性质和所求问题本身的结构特征以及其他辅助信息,可以用于求解不同类型的优化问题,具有广泛的适用性。[56]