化学反应优化算法论文（精选9篇）
化学反应优化算法论文 第1篇
关键词：人工智能算法,多目标任务调度,化学反应优化算法,任务调度
0 引言
如今, 在学术研究和现代工程技术中, 经常会遇到众多复杂的数学问题, 他们大多涉及大量的数学与计算问题, 但是这些复杂计算问题由研究人员解决起来非常困难, 所以研究用计算机处理最优解方面问题是势在必行的。通过解决众多的数学与最优解问题, 可以给科学技术发展带来许多改变。随着通讯技术、计算机网络技术与大规模存储技术的发展和日趋成熟, 使得化学反应优化算法多目标任务调度的研究技术在商业运作和工业生产中开始扮演重要的角色。
近年来国内外对于化学反应优化算法的研究日趋热烈, 同时也取得了丰富的研究成果。化学反应优化算法多目标任务调度的研究展现了其特殊魅力, 被公认为是最具发展前景的关键技术之一。美国的能源部一份国家声明称:全球高性能计算领域的竞争日益激烈, 加强美国国家实验室的计算能力, 对美国在科技方面创新能力的可持续发展, 对维持美国的竞争力, 对加强美国经济和国家安全尤其核安全能力至关重要。突出强调了高性能计算对于一个国家未来而言的重要性, 对于一个民族加强国家竞争力的重要性。而化学反应优化算法多目标任务调度就可以提高计算能力。本文以化学反应优化算法为例介绍了在多目标任务调度的研究。
1 化学反应优化算法
化学反应优化 (Chemical Reaction Optimization, CRO) 算法是由Albert Y.S.Lam和Victor O.K.Li于2010年提出的一种基于种群的智能优化算法, 它是一种模拟化学反应里分子之间的各种反应而引起的分子间的相互作用, 通过代码不断迭代和数值比较来寻找确定代码里规定的最小系统势能, 通过最小系统势能的确定可以解决很多寻求最优解的问题, 解决很多大型工程里的计算和求解问题。
在化学反应优化算法里, 化学反应优化算法 (CRO) 是最近成立的一个启发式的优化, 是从化学反应的本质出发的。化学反应是一个自然的不稳定物质转化到稳定的过程。在微观上, 化学反应开始过度的能量不稳定的分子。分子相互作用, 通过一系列的化学反应。最后, 它们转化为以最优的能量来支持它们的存在。我们已经成功地利用CRO来解决范围广泛的工程问题, 包括二次分配问题, 神经网络训练, 多式联运等连续问题, 仿真结果表明, CRO与其他现有的优化算法相比, 性能优越。
化学反应优化算法总共包括4部分反应组成:与容器壁的碰撞反应 (分子m的一个任务被重新随机分配) 、分解反应 (分子m的奇数位置分配成m1, 偶数位置分配成m2, m1、m2未分配的位置由随机数填充) 、分子间的碰撞 (随机产生一个交叉点, 该点之前的分配保留不变, 之后对分子m1、m2进行互换。) , 合成反应 (随机产生一个位置p, 将分子m1的p位置前保留, p及其之后的位置由分子m2的相同位置复制得来) 。
算法大致流程如下, 如图所示:
在化学反应算法里, 通过计算机可以模拟化学反应开始之初的一种混乱状态 (通过利用Random () ) , 通过回顾化学反应的相关知识, 在代码里可以表现出分解反应释放势能等化学领域的知识。在化学反应算法里, 是允许误差的, 在与容器壁的碰撞反应里, 通过更改位置参数可以实现分子的一个任务被重新随机分配, 在合成反应中, 两个分子m1, m2, 随机产生一个位置pos, 将分子m1的p位置前保留, p及其之后的位置由分子m2的相同的p及其之后的位置复制得来, 可以实现更新, 并且在合成反应后计算能量, 并通过后续的比较大小等操作来完成整个合成反应的过程。在分子间的碰撞过程里, 两个分子m1, m2, 随机产生一个交叉点pos, 两个分子m1, m2, 该点之前的分配保留不变, 对该点之后的分子m1、m2进行互换来实现碰撞过程, 也使用了相应的比较大小, 更新参数操作。
2 化学反应优化算法的优化
化学反应算法具有实现易, 灵活性, 执行效率高和通用性的特点, 所以在目标值优化问题上有着突出的表现且被广泛使用, 优化问题主要有两个点, 一是寻找全局最优点, 二是要求有较高的收敛速度, 在实际代码里, 如果适应度函数选择不当, 会使结果收敛于局部最优, 而不能达到全局最优, 这就要求需要有较好的寻优方法, 在搜索空间里自适应地调整搜索方向, 来达到全局最优的目的, 并且在有的算法里, 需要确定好终止条件, 进行终止条件判断, 来终止计算。在化学反应算法中, 因为有动能和势能相互转换的存在, 会使分子的变化, 比如能量和状态的改变。这种现象一方面使分子群体具有多样性, 使算法有更好的全局搜索能力;但是另一方面也减缓了算法的收敛速度, 为了要求有较高的收敛速度。因此在改进算法中, 引入了精英保留策略。
在化学反应优化算法里, 排序操作不应一直使用冒泡排序, 冒泡排序基本思路:每趟不断将记录两两比较, 并按“前小后大” (或“前大后小”) 规则交换。它需要以顺序存储结构为前提, 它的最坏情形是初始排列逆序, 算法要执行n-1趟起泡, 第i趟做了n-i次关键码比较, 执行了n-i次对象交换。而应该改为快速排序算法, 快速排序算法在顺序存储结构的前提下, 因为每趟可以确定不止一个元素的位置, 而且呈指数增加, 可以提高排序速度。
在本化学反应优化算法实验中, 快速排序算法基本思想:从待排序列中任取一个元素 (例如取第一个) 作为中心, 所有比它小的元素一律前放, 所有比它大的元素一律后放, 形成左右两个子表;然后再对各子表重新选择中心元素并依此规则调整, 直到每个子表的元素只剩一个。这样依次操作, 直至数列中所有元素均有序为止, 此时便为有序序列了。
这里结合了遗传算法的相应概念, 在遗传算法里, 实验选定的种群规模, 任务数量, 遗传算法交叉概率, 遗传算法变异概率等都会对算法产生影响, 在算法实现过程中还应计算时间矩阵, ETC[i][j]=work Load[i]/computing Power[j]。在循坏里每次只有两代, 经过操作使一代再生一代。而且也可以选择parent1和parent2, 再基因突变生成子代。而且基因突变操作是随机的, 在计算群体中每一个个体被自然选择的概率时, 用于轮盘赌选择算法选择个体, 并且计算相应适应度的值。最后通过比较大小交换得出最优解。最后整体算法的完成时间需要由用时最长完成所分配任务的设备的完成时间决定。
在整个化学反应优化算法里, 实验需要计算势能 (potential energy) 即适应度值, 工作流的执行时间makespan:完成时间, 由用时最长完成所分配任务的设备的完成时间决定。以及对于分子 (代表一个可行解) 的把握。通过寻找容器内最优分子以及确定全局解空间可以进行化学反应优化算法的运行。
通过在Workflow Sim中运行相应的化学反应优化算法, 设置适宜的算法和参数可以得到我们想要的最优解, 从而解决现实生活中的实际问题。
由仿真实验实验结果可以知道, 改进过的化学反应优化算法是解决多目标任务调度的有效算法。
3 结束语
有效的化学反应优化算法多目标任务调度可以提高企业提供服务的质量, 进行有效的提取信息与计算。帮助企业做出更准确的决策, 是化学反应优化算法多目标任务调度的主要领域。本文对化学反应优化算法多目标任务调度里的一个例子改进的化学反应优化算法进行了探讨, 指出在多目标任务调度的使用范例。
目前, 对化学反应优化算法多目标任务调度的研究虽然取得了一定的进展, 但研究大多停留在理论阶段, 较少考虑海量数据和市场需求对化学反应优化算法多目标任务调度所造成的影响。因此多目标任务调度对实际的指导将是研究的重点和热点。
参考文献
[1]Wei Shen, Beibei Xu, An Improved Genetic Algorithm for 0-1 Knapsack Problems, Networking and Distributed Computing (ICNDC) , 2011Second International Conference, pp.32-35 (2011)
[2]Tung Khac Truong, Kenli Li, Chemicalreactionoptimizationwithgreedystrategyforthe0-1 knapsackproblem, Applied Soft Computing, vol.13, no.4, pp.1774-1780 (2013)
[3]Xie, T;Qin, X;Security-Aware Resource Allocation for Real-Time Parallel Jobs on Homogeneous and Heterogeneous Clusters, IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, vol.19, no.5, pp.682-697 (2008)
[4]Albert Y.S.Lam, Victor O.K.Li, Chemical Reaction Optimization:a tutorial, Memetic Computing, vol.4, no.1, pp 3-17 (2012) .
[5]F.Glover, Tabu Search:Part I, ORSA Journal on Computing, vol.1, no.3, pp.190-206 (1989)
[6]F.Glover, Tabu Search:Part II, ORSA Journal on Computing, vol.2, no.1, pp.4-32 (1990) .
[7]Bechikh, S.Chaabani, A.;Said, L.B.;An Efficient Chemical Reaction Optimization Algorithm for Multiobjective Optimization, IEEE Transactions on Cybernetics, mo.99, pp.1-14 (2014)
[8]Chen, WW, da Silva, RF;Deelman, E;Sakellariou, R;Using imbalance metrics to optimize task clustering in scientific workflow executions, FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF GRID COMPUTING AND ESCIENCE, vol.46, pp.69-84 (2015)
一类优化问题的快速收敛算法 第2篇
一类优化问题的快速收敛算法
给出了一个用于解决LC1线性约束优化问题的BFGS-SQP算法,这个算法是用Armijo线性原则来求步长的.为推广BFGS-SGP算法,本文采用Wolfe线性搜索原则来替代该BFGS-SQP算法的.Armijo原则,经过分析,同样得到了BFGS-SGP算法的全局收敛性及超线性收敛性.
作 者：王道林 宁伟 作者单位：山东泰山学院计算机科学与技术系,山东,泰安,271000刊 名：数学的实践与认识 ISTIC PKU英文刊名：MATHEMATICS IN PRACTICE AND THEORY年，卷(期)：34(5)分类号：O1关键词：LC1问题 BFGS-SQP算法 全局收敛 超线性收敛
蚁群算法的BP网络优化算法 第3篇
借鉴蚁群算法的思想，对无线传感网络中的地理路由协议算法进行了研究改进，以期从中能够找到更快速的地理路由搜寻算法，并以此和广大同行分享。
2 原理
蚁群算法(ant colony optimization,ACO)，又称蚂蚁算法，是一种随机搜索算法。简单地说，蚂蚁在运动过程中，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。蚂蚁能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且在运动过程中能够感知这种物质，并以此指导自己的运动方向，当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行，与此同时释放出与路径长度有关的信息素，路径越长，释放的激素浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大。因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。最优路径上的激素浓度越来越大，而其他的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。蚁群算法吸收了蚂蚁群体行为的典型特征：(1)察觉小范围区域内状况，并判断出是否有事物或其他同类的信息素轨迹;(2)能释放自己的信息素;(3)所遗留的信息素数量会随时间而逐步减少。
3 BP网络优化
3.1 算法原理
神经网络中应用最多的就是多层前向神经网络模型，其中误差反向传播算法(BP算法)具有概念清楚、计算简单的特点，因其推导过程严谨、通用性强而得到广泛应用。但BP算法本质是一种局部搜索算法，不能用于搜索多峰值函数的全局极小点，且具有收敛时间长、易于出现局部极值等缺陷。为此人们提出了很多改进的算法，其中最简单且容易实现的是加入动量项的变学习率BP算法，但其仍是局部搜索算法，从本质上仍然摆脱不了陷入局部极小点的可能。因此，将蚁群算法引入到前向神经网络的优化训练中来，建立一种基于蚁群算法的前向神经网络训练模型，即蚁群神经网络。
针对BP算法容易陷入局部极小等不足，提出ACO-BP神经网络训练方法。神经网络训练过程可以看作是一个最优化问题，即找到一组最优的权值组合，使得在此权值下的输出结果与期望结果之间的误差能够最小，蚁群算法成为寻找这一最优权值组合的较好选择。
基于蚁群算法的BP神经网络算法即ACO-BP算法基本思想是：利用蚁群算法大致搜索出一定的权值范围，以此时的权值作为BP网络的初始权值，可以改善BP网络的易陷入局部极小、收敛速度慢和引起振荡效应等缺陷。
3.2 算法执行步骤
Step1：将上述BP神经网络权值区间[-1,1]均匀分割为20等分，为每一个权值参数建立一张信息素表，设置信息素初值为τ0，信息素挥发系数ρ，信息素增量强度Q,ACO的最大迭代次数countMax,ACO优化结束条件为εACO;BP网络初始化使用Matlab工具箱函数生成，训练误差退出条件为εBP。
Step2：释放m只蚂蚁。蚂蚁k依据如下概率公式从一点移动到下一点：
蚂蚁从每一个权值的子区域穿过且仅穿过一次，并记录相应点的标号。这些子区域的组合构成了神经网络的一组权值。根据输入输出样本得到误差值，再利用误差值的大小进行信息素的更新。
Step3：将整个无线传感网络的节点值样本集作为输入训练样本，根据BP网络的输入层到隐层的Sigmoid S型正切曲线激励函数及隐层到输出层的线性函数，计算得到相应的路由路径值输出，计算误差E。
Step4：所有蚂蚁构造解以后记录误差最小的一组权值，并比较最小误差Emin与εACO的大小，如果Emin≤εACO，则转Step7，否则转Step5。
Step5：信息素更新：第i个权值的信息素更新策略如下公式(2)：
其中，。
En为第n只蚂蚁所选权值计算所得的误差平方和，M,N分别表示BP网络的输入样本个数及输出层节点数，τt+1(i,n)为第i个权值对应第t代蚁群的第n只蚂蚁经过后更新的信息素值。
在具体应用中发现采用如上的信息素更新策略的ACO-BP算法进行路由路径搜索时，其搜索速率算法的收敛速度效果不够理想，因此进一步分析改进如下：在上述ACO算法的N次迭代过程中，后代蚂蚁是根据前代蚂蚁搜索后更新的信息素表来进行概率性选择路径的，因此前代蚂蚁对于后代蚂蚁有着信息素的引导作用。由于信息素挥发系数ρ的存在且其值不变，那些从未被搜索到的路径上的信息素会逐渐消失，导致这些路径被选择的概率减小，而信息素增加的非最优路径的概率却增大，进而算法容易陷入局部最优。因此要提高算法的全局搜索能力，使算法尽量找到最优解，就必须适当减少已选择路径上的信息素数量，即适当地减弱后代蚂蚁的信息素贡献能力。改进(2)公式如下：
其中，。
Step6：重复Step2到Step4，直到满足最大迭代数countMax，转步骤Step7。
Step7：采用BP算法进一步训练神经网络：将蚁群算法找到的一组最好权值分别作为BP算法的初始权值，计算网络输出和实际输出之间的误差，并将误差由输出层反向传播到输入层，调整权值。重复以上过程，直到满足训练退出条件。
Step8：对训练好的神经网络的泛化能力进行检验，如果验证误差满足要求，退出程序;否则转步骤Step1，重新开始训练。
3.3 算法性能仿真
为了验证上述基于蚁群算法的BP网络优化算法的有效性与可靠性，借助于无线网络性能测试软件NS-2软件，构建了如下无线传感网络节点仿真场景：场景大小1500500，由30个节点组成，10秒后每个节点每4秒发送cbr包给数据接收处理终端节点，传感器节点的拓扑结构如图1所示，节点数30，根节点为15号节点，最大子节点数为4，最大层数为5。
仿真测试的目的是为了验证该优化算法在具体执行无线传感网络节点的路由搜索时的快速性及其搜索算法的收敛性。如图2所示，是算法性能仿真测试结果对比图，其中(a)图是单纯使用BP网络训练后的路由路径搜索算法执行收敛结果，(b)图是将蚁群算法和BP网络算法结合起来后的路由路径搜索算法执行收敛结果，(c)图是基于蚁群算法的BP网络优化算法执行的路由路径搜索算法执行收敛结果。
如上实验结果可以看出，图2(a)中的BP网络训练到第8步长时网络训练达到0.002的误差精度，训练完毕;改进前的ACO-BP网络则只要7步长时间即可达到同样的误差精度值，而改进后的ACO-BP网络仅用4步即可收敛;明显使用ACO-BP网络训练的收敛速度要快于BP网络，相同时间下可以得到较小的均方误差和，这充分说明了提出的基于蚁群算法的BP网络优化算法在无线传感网络节点的路由路径搜寻方面具有更好的快速性与可靠性。由此可见，使用的由蚁群算法优化的BP神经网络混合算法，在利用蚁群算法优化BP网络的权值后，得到更优的BP网络参数用以进一步的训练，动态调整了网络参数，使得网络的训练收敛速度加快且能得到更小的均方误差和，提升了蚁群算法对于BP网络的训练优化的能力，具有一定推广研究的价值。
4 结语
路由选择问题，是无传感器网络中的核心问题，也是目前该领域研究的热点问题。以提高无线传感器网络的路由路径搜寻效率为目的，深入分析了己有路由协议，用人工智能神经网络BP技术结合一种改进蚁群算法的思想提出了一种无线传感器路由算法，这对于无线传感网络路由搜索算法的研究是一次有益的尝试与探索，在今后的研究中将结合具体应用，提出实用、特定环境下的WSN的路由算法，并将考虑网络路由的安全性因素，这是下一步重点需要解决的研究难题。
摘要：利用蚁群算法和BP网络训练算法相结合的方法对无线传感网络节点路由路径搜索展开了分析研究,简单分析了蚁群算法实现的基本原理,在此基础上重点给出了基于蚁群算法的BP网络优化算法的基本原理及其实现步骤,并对该优化算法与传统的BP网络训练算法的性能进行了对比仿真测试。
关键词：BP网络,蚁群算法,算法优化
参考文献
[1]李建电.无线传感器网络专刊前言[J].软件学报,2007,18(5):1077-1079.
[2]任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291.
[3]唐勇,周明天,张欣.无线传感器网络路由协议研究进展[J].软件学报,2006,17(3):410-421.
[4]Manjeshwar,A.&D.P.Agarwal.TEEN:a Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[A].In:Parallel and Distributed Processing Symposium,Proceedings15th International[C].2001:2009-2015.
[5]马祖长,孙怡宁,梅涛.无线传感器网络综述[J].通信学报,2004,25(4):114-124.
基于遗传算法的飞机气动优化设计 第4篇
基于遗传算法的飞机气动优化设计
建立了一种以实数编码技术为基础的遗传算法模型,并把它与通过工程估算的气动分析方法相结合,进行飞机气动外形的单点和多点优化设计.优化设计中,设计变量取为机翼、机身和尾翼的外形及三者之间的相对位置,优化目标是使飞机在跨音速和超音速飞行状态下获得配平状态下最大的升阻比.设计结果表明该优化设计方法是十分有效的.,可以用来对具有正常布局形式的飞机进行气动外形的优化设计.
作 者：王晓鹏 作者单位：西北工业大学,飞机系,西安,710072;上海航天技术研究院,上海,33刊 名：计算力学学报 ISTIC EI PKU英文刊名：CHINESE JOURNAL OF COMPUTATIONAL MECHANICS年，卷(期)：200219(2)分类号：V211.3关键词：遗传算法 气动外形 优化设计
化学反应优化算法论文 第5篇
现在,物流配送多指配送中心按照多个客户的不同要求进行组织配送,并满足客户在产品质量、产品数量、到货时间等多方面的要求的同时使配送成本尽可能的低[1,2],为了能够达到这一目标就要对配送路径进行优化。对配送路径进行优化就是对车辆路径进行优化,这是一个NP问题,以往的很多研究都证明了使用遗传算法求解这一类问题具有很大的优越性[3,4]。与与蚁群算法[5]相比,它能更大概率地搜索到最优解,因为蚁群算法在寻找最优解的过程中,当搜索的一定程度后,容易出现停滞现象,所有的个体发现的解都是同一个,不能再对解空间进行深入的搜索;与禁忌搜索算法[6]相比它的收敛性好一些,因为禁忌搜索算法对初始解得依赖性强,当初始解的质量较差时,收敛速度会大大降低。但以往的各种物流路径优化算法在物品的配送上都有局限性,它们只考虑了配送单一种类的物品,本文我们着重解决了这个问题,使其既能配送常温下的物品,也能配送需要冷藏处理的生鲜食品。
1 物流配送路径优化问题的解决方案
1.1 多目标物流配送问题描述
由于多目标物流配送中的各个目标之间存在着相互制约的关系,这在一定程度上增加了建模和求解的难度。因此在研究多目标物流配送路径优化问题时,我们只考虑对最优路径的选取影响较大的几个因素,包括个体客户的货物需求量、要求的到货时间,配送中心的车辆数目、每个车辆的容量限制等,我们要做的是在满足上述这些要求的条件下,使车辆行驶的总里程尽可能短、花费时间尽可能少和使用车辆尽可能少等目标[7],其中当运送生鲜食品时还要考虑配送过程中车厢的温度控制和能量损耗问题,而且配送生鲜食品对时间有很严格的要求[8]。
1.2 多目标物流配送模型建立
多目标物流配送模型是一个配送中心为多个顾客派送货物的配送模型,配送的货物类型多种多样多样,同时还要满足以下九个条件:
(1)配送是单向的,即纯送货;
(2)运输工具为M辆汽车,且每辆汽车的装载能力是一样的,所运送货物的总质量要低于车辆的最大装载量;
(3)每个客户的需求量是已知的;
(4)所有客户都应该得到服务;
(5)生鲜食品不能和其他物品同车,它们有专门的车辆配送;
(6)每条线路的开始和结束位置都在配送中心;
(7)配送中心与各客户之间以及两两客户之间的行车线路是确定的,即两者之间的距离已知。
(8)生鲜食品不能和其他物品同车,它们有专门的车辆配送;
(9)目标有多个:路程最短、费用最少、使用车辆最少、车辆运输时间及客户等待时间最短;
其配送优化模型如下:
其中:f=0表示第k部车装的是普通货物,f=1表示第k部车装的是生鲜食品。
模型以总成本最低作为目标函数。成本包括:运输成本、超重惩罚成本,如果配送物品中含有生鲜食品的话还包括在配送途中腐坏所造成的货损成本。
(1)运输成本
运输成本包括固定成本和变动成本两部分。其中固定成本为常数,与运输里程和运送量没有直接关系[9];变动成本包括耗油量、车辆维修和车辆保养等成本,变动成本与车辆行驶的里程数呈正比。因此,为了简化计算,我们不考虑固定成本。对于运输成本,采用公式(1)来计算。
约束条件:
其中:f=0表示第k部车装的是普通货物,在路段(Vi,Vj)的运输成本为Cijk,f=1表示第k部车装的是生鲜食品,运输成本为Dijk,且Cijk=Ckij,Dijk=Dkij;Xijk为0,1变量,若第k部车行经(Vi,Vj)路段,则Xijk为1,否则为0;yik为0,1变量,若客户i的任务由第k部车完成,则yik为1,否则为0。目标函数(1)要求合理安排车辆运送任务和行驶路径,使运输成本最小,式(1.1)要求每个客户点仅有一辆车提供服务,所有的运输任务由m辆车协同完成,式(1.2)为汽车容量约束。
(2)超重惩罚成本
每辆车都有它限制的载重量,当车辆的实际载重量大于其限制载重量时是极其危险的,我们要避免这种情况的出现,所以我们在计算超重惩罚成本时给它加上一个极大地系数,以此来避免超重情况的出现。超重惩罚成本可用公式(2)来计算。
其中:M为惩罚系数;gi为i客户的货物数量;yik为0,1变量,若客户i的任务由第k部车完成,则yik为1,否则为0;q为车辆的限制载货量。
(3)货损成本
生鲜食品容易腐坏,造成生鲜食品腐坏的原因有很多。在这里我们假定生鲜食品是在固定温度下配送的,其腐坏原因可概括为:一运送途中因时间累积,生鲜食品腐坏;二在服务客户时,开启车厢门造成空气对流,车厢内的冷空气流出,外界热空气流入,车厢内的温度上升,造成生鲜食品腐坏[12]。所以货损成本可用公式(3)计算。
其中:p为生鲜产品单价;λjk为0,1变量,若第k部车辆服务j客户,则λjk=1,否则,λjk=0;a1为运生鲜食品在运送中的货损比例;a2为生鲜食品在装卸操作过程中货损比例;dij为服务完i客户后前往j客户的里程;gj为j客户的货物数量。
2 物流配送路径优化问题的改进遗传算法
2.1 构造染色体,初始化种群
解向量可编成一条长度为n+m+1的染色体{0,i1,i2,i3,…ij,0,ij+1,ij+2,…ik,0,……0,ip+1,ip+2,ip+3…iq,0}。在整条染色体中,自然数ij表示第j个客户,共有n个客户,0代表配送中心。0把染色体分为m段,形成了m个子路径,这表示完成所有运输任务需使用m辆车。初始化染色体时,先随机生成一个m个客户的全排列,再将m+1个0随机插入排列中。需要注意的是排列的头部和尾部必须都有一个0,并且排列中不能出现2个连续的0。
2.2 适应度函数
将成本转换为适应度函数:fi=min Z/Zi其中fi为第i条染色体的适应度,min Z为当前群体中最优染色体的目标值,Zi为第i条染色体的目标值。
2.3 自然选择
分别计算父代染色体、子代染色体的适应度值,父代和子代中最优的染色体直接进入种群,其它染色体采用轮盘赌的选择方法来确定。
2.4 交叉算子
随机选择进行交叉的染色体和交叉位,如果染色体交叉点处的基因都为0,则交换染色体交叉位的前段得到新的染色体;如果染色体交叉点处的基因不全为0,则将交叉点左移(另一个右移),直到左右两个交叉点处的基因都为0,再进行上述操作,如果左移(右移)到首部(尾部),则对方染色体不变,只将对方染色体交叉位的前段放在自己的前端。削去相同的元素,调整形成两个合法的染色体。
2.5 变异算子
在一定的概率条件下随机地选取发生变异的个体染色体,然后在选中的染色体上随机选取两个非零基因位,将这两个位置上的基因互换,形成新的染色体。
2.6 结束条件
一次运算结束且当前进化代数小于预先设定的迭代次数时,返回2.2节,继续该运算。
3 实例分析
实例描述:配送中心数为1,客户数n为12,车辆总数m为4;车辆载重上限q为6吨;各客户点需求量为g(单位为吨),f为物品种类标识。f=0,表示物品为普通物品;f=1,表示物品为生冷食品。客户点与配送中心之间的距离、两两客户点之间的距离和客户的需求量如表1(其中济南为配送中心),要求合理安排车辆的运输路线、运送任务,使总成本最小。为方便记录和计算我们给配送中心和客户点编号,济南为0,淄博为1,青岛为2,枣庄为3,烟台为4,潍坊为5,威海为6,济宁为7,日照为8,临沂为9,德州为10,聊城为11,滨州为12。
参数设置为s i z e p o p=5 0(种群规模),m a x g e n=1 0 0(迭代次数),pmutation=0.2(变异概率)和pcross=0.9(交叉概率),对于变异概率和交叉概率大小的选择是要经过验证的,当种群规模改变时变异概率和交叉概率的最合适值也要进行调整。验证结果见图1。图中纵坐标是目标值,横坐标是迭代次数除以10,即取第10的倍数的次迭代的值,共10个。
用文中改进遗传算法、蚁群算法和禁忌搜索算法,分别对文中实例运行10次,得到的计算结果对比情况如图2,并记录改进遗传算法这10次运算中的最佳值,见表2。从表中数据可以看出,10次运行得到的结果均优于蚁群算法和禁忌搜索算法所得的最佳结果8295、8694。而且第4次还得到了最优解7165,其对应的配送路径为:0→11→7→0;0→10→0;0→4→2→0;0→6→1→0;0→3→9→0;0→8→5→12→0。计算结果表明,用改进的遗传算法解决物流配送路径优化问题,可以方便有效地求得问题的最优解或近似最优解。
4 结语
在当今社会使用遗传算法对物流路径进行优化已经很广泛,但都是针对单一种类的物品而进行的,本文针对同时配送常温物品和冷藏物品给出了解决方案。考虑到常温物品和冷藏物品在运输成本上有很大差别,而且配送冷藏物品会产生货损成本,因此本文先对物品进行分类处理并标识,然后在考虑其他成本的前提下进行了路径的选择优化,最后给出了实例验证,并取得了很好地效果,证明了该方案的可行性和有效性。
摘要：物流配送路径优化问题是一个NP(非确定多项式)问题,使用传统优化方法很难得到最优解或满意解。为了很好地解决这个NP问题,本文建立了一个配送中心、多个顾客的物流配送数学模型,用自己改进的遗传算法加以分析求解并进行了实例验证,而且在物品的配送种类上取得了突破,不在只是针对单一品种,对物流企业实现科学快捷的配送调度和路径优化有实际意义。
化学反应优化算法论文 第6篇
全文检索是一种非常有效的信息检索技术, 它能帮助人们快速地从海量数据中获得所需的信息。但由于用户通常在初次检索信息时输入的关键词不够具体或所能够反映的信息量有限, 从而导致检索效率的低下。查询效率成为全文检索系统的一个突出瓶颈。查询优化的目的是提高信息检索的查全率和查准率。
1 研究现状
上世纪70年代至今已提出多种查询优化技术, 比较流行的如查询扩展、相关反馈和伪相关反馈等。上述优化技术在应用中由于检索数据集的巨大且影响检索效率因素多样, 效果并不理想。信息检索中的查询优化属于寻找一个最能表达用户需求的查询, 即寻找最优解问题, 而遗传算法 (GA) 作为一种自适应全局优化概率搜索算法, 其重要的应用领域就是寻找最优解, 由此遗传算法被引入到全文检索领域[1,2]。文献[3, 4]提出一种基于局部类别分析的查询扩展优化算法 (简称LCLA) 。在LCLA算法中, 重点研究了如何选择扩展词对初始查询进行扩展, 但并没有进一步讨论如何更为有效地对扩展后的查询进行权重分配, 因此本文结合LCLA算法的优点和基于遗传算法的权重分配方法, 提出一种基于局部类别分析和遗传算法的查询优化算法 (简称LCAGA) 。
2 LCAGA算法
2.1 LCAGA算法基本思想
该算法对用户的查询分2个阶段进行处理:
(1) 采用基于局部类别分析的查询扩展方法对用户初始查询Qold进行扩展得到新查询Qnew;
(2) 采用遗传算法对新查询Qnew进行权重调整形成优化的查询。
该算法的设计框架如图1所示。
为方便描述, 引入定义如下:
定义1文档向量对于文档dk, 表示为文档向量dk= (wlk, w2k, , wnk) 。其中, 文档dk中关键词的个数用n表示, 第i个关键词用ti表示, 分量wik表示ti在文档dk中的权重。
定义2查询向量用户的查询表示为查询向量Q= (wlq, w2q, , wnq) 。其中, 查询关键词的个数用n表示, 第i个关键词用ti表示, 分量wiq表示ti在查询Q中的权重。关键词对于用户的重要程度即为权重。
关键词ti在查询Q中的权重wiq可由下式计算[5]:
其中, tfiq表示ti在查询Q中的出现次数, maxtfq为查询Q中所有关键词出现次数的最大值。
定义3相似度是指文档与查询相关联程度。按两向量夹角余弦的计算含义, 文档dk和查询Q的相似度值sim (dk, Q) 可由下式计算:
定义4局部文档集合在文档集合D中, 针对给定查询Q检出的结果集合为局部文档集合, 记作Dl。Dl中所有不相同词语集合称为局部词汇表。
扩展词的选取采用关联簇的思想, 关联簇的生成方法如下[2]:
定义5关联矩阵词语si在文档dk (dk∈Dl) 中出现的频率用tfsik表示, m= (mij) 是一个|Vl|行、|Dl|列的关联矩阵, 其中mij=tfsik;设mT为m的转置矩阵, 则矩阵s=mmT是一个局部词语-词语的关联矩阵。矩阵s中的元素suv代表了词语su与词语sv之间的关联Cu, v, 即:
但关联因子Cu, v是非规范化的, 规范关联因子可由式 (4) 计算获得:
定义6文档类别c与查询Qold的相似度rc, Q用n表示初始查询得到的Dl中属于文档类别c的文档个数, 则:
定义7查询Qnew返回的相关文献数为N;第i篇相关文档在返回的文档列表中的次序为Ranki, 则染色体适应度函数定义为NAP:
定义8个体i被选中的概率pis。其中M表示群体大小, Fi表示个体i的适应度, 则:
2.2 LCAGA算法具体描述
(1) 采用基于局部类别分析的查询扩展方法对用户初始查询Qold进行扩展得到新查询Qnew。
对于给定初始查询Qold, 检索出的结果为局部文档集合Dl, 相对于海量的文档集合D而言, Dl的信息蕴含量是很有限的, 不适合作为进行查询词扩展的文档集合, 因此该算法将与初始查询Qold相关的文档类别看作局部文档集合, 构造相关类别的局部关联簇并从中选取扩展词。该算法的查询扩展过程描述如下:
Step1利用式 (2) 计算用户初始查询Qold与文档集合D中文档的相似度sim (dk, Qold) , 按照相似程度对得到的初检文档进行排序, 选取前n篇文档构成局部文档集合Dl。
Step2利用式 (5) 计算文档类别c与查询Qold的相似度rc, Q。
Step3选取相似度rc, Q较大的文档类别, 利用定义5构造文档类别的局部关联簇。利用式 (4) 计算关联簇中标引词u与Qold之间的相关因子Su, Qold, 查询扩展词的选取原则为:初始查询Qold中未出现的前h个相关因子较大的关键词。
设用户的初始查询向量为Qold= (wlq, w2q, , wjq) , 查询扩展向量为Qe= (wlq, w2q, , whq) , Qold与Qe相结合即形成扩展后的新查询为Qnew= (wlq, w2q, , wjq, wj+1q, wj+2q, , wj+hq) 。
(2) 采用遗传算法对新查询Qnew进行权重调整形成优化的查询。
遗传算法主要是通过选择、交叉、变异等操作对对象进行优化, 对对象的适应能力是利用适应度函数来判断的。对查询词权值进行优化过程描述如下:
Step1初始种群的构造和个体编码。初始种群设为30。采用浮点数编码方法对染色体进行编码。将查询向量Qnew= (wlq, w2q, , wjq, wj+1q, wj+2q, , wj+hq) 编码成长度为j+h的染色体, 染色体中的基因与关键词的权重相对应。先为每个关键词随机赋某一权值 (取值范围为[0, l]) 。
Step2适应度的计算。利用式 (6) 计算每个个体适应度值函数。
Step3遗传算法中算子设计:
Step3.1交叉操作算子。采用双点交叉策略, 首先从当前的种群中随机选择相互配对的两个染色体w和v, ;然后在w和v中随机产生两个交叉点m和n, 要求满足1≤m≤n≤j+h, j+h为染色体中基因的个数 (即关键词的个数) ;最后将w和v中的交叉点m和n之间的内容进行交换操作, 从而产生两个新的个体w'和v'。
Step3.2变异操作算子。首先从当前种群中随机选择一个染色体w= (wlq, w2q, , wi-1q, wiq, , wj+hq) , 此染色体w即作为将被执行变异操作的父染色体;然后随机产生一个整数i (即将发生变异的基因) , 要求满足1≤i≤j+h;最后再随机产生一个实数w'i, 要求满足0≤w'i≤1, 使得父染色体w繁殖了一个新的后代w'= (wlq, w2q, , wi-1q, wiq', , wj+hq) 。
Step3.3选择操作算子。本文将比例选择方法和最优保存策略相结合, 给出选择操作算子。其中比例选择法采用式 (7) 进行计算。
Step4将最优染色体解码为查询向量, 即为优化的查询向量。
3 实验
3.1 实验内容及参数确定
实验测试数据采用“Citeseer”计算机专业论文网站所提供的文献资源, 将网站的计算机论文进行归并至10个大类。选取每类前50篇文档, 共500篇作为实验数据集。
本文实验中算法的参数设置为:查询扩展词的个数h设为n-1, 交叉概率设为0.4, 变异概率设为0.3, 最大进化代数设为100。
3.2 实验结果及分析
软件平台是Microsoft Windows XP, 硬件平台CPU为Penfium IV 4.3GHZ, l G内存。实验模拟了局部上下文分析 (LCA) 、局部类别分析 (LCLA) 及本文算法 (LCAGA) 三种算法。首先从检索速度方面比较这三种算法的优劣, 三种算法检索速度的对比实验结果如图2所示。
从图2可知, 检索相同文档篇数时, 本文算法的检索时间最少。分析可知, 对于LCA算法而言, 它需要对文档集合D中的部分文档进行检索, 而文档集合D数量越大标引词数目就越大, 计算开销也相应增大;LCLA算法只对相关类别中的文档进行分析, 缩小了查询扩展的范围, 标引词的数目较少, 因而减少了计算词间关系的时间;LCAGA算法对扩展后的查询Qnew又重新进行了权重调整, 得到是最优查询向量, 因此新算法的检索时间要低于前2者。
其次从检索性能方面比较这三种算法的优劣。在查全率为0.1~1.0时获得算法相应的查准率, 对比实验结果如图3所示。
从图3可以看出, 在查全率相同的情况下, 本文算法的查准率最高。通过分析可知在LCA算法中, 由于进行分析的对象只是部分文档, 与查询相关的信息较少, 从而导致在查全率较低时仍获得较低的查准率。LCLA算法是将内容相近的文档归并为一类, 在相关文档类别中进行查询词的扩展能更加接近用户的查询意愿, 有效避免了初始查询被加入不相关的词, 从而提高了查准率。而本文算法将用遗传算法优化后的查询再次对测试集中的文档进行二次检索, 因而查准率得到了提高。
4 结语
本文将遗传算法与局部类别分析的查询扩展方法相结合, 提出一种基于局部类别分析和遗传算法的查询优化算法。该算法对用户查询分2个阶段进行。实验表明, 相比局部上下文分析算法及局部类别分析算法, 本文算法具有更优的性能。
摘要：查询扩展是信息检索中优化查询的一种有效方法。针对信息检索中用户查询关键词与文档标引词不匹配的问题, 提出一种基于局部类别分析和遗传算法的查询优化算法。该算法分两个阶段实现:第1阶段对用户提交的查询Qold进行扩展, 采用基于局部类别分析的查询扩展方法选择查询扩展词构成新查询Qnew;第2阶段对新查询Qnew进行权重分配, 采用遗传算法对扩展后的查询进行权重调整得到最优查询向量, 再次对测试集中的文档进行二次检索。实验结果表明, 该算法比单独使用局部上下文分析算法、局部类别分析算法均有更优的检索性能。
关键词：信息检索,查询扩展,局部分析,遗传算法
参考文献
[1]Boughanem M, Chrisment C, Tamine L.Genetic approach to query space exploration[J].Information Retrieval, 1999, 1 (3) :175-192.
[2]徐莹.信息检索中的查询优化技术研究[D].合肥工业大学, 2008.
[3]冯运, 陈治平.基于局部类别分析的查询扩展[J].计算机应用, 2007, 1 (27) :207-209.
[4]冯运.信息检索中的查询算法研究[D].湖南大学, 2007.
函数优化的遗传算法 第7篇
近年来,随着计算技术的发展,一些新的智能算法(如遗传算法、模拟退火算法、禁忌搜索算法)得到了迅速发展和广泛应用。特别是模拟进化算法(GA、GP、Es),无论是理论研究还是应用研究都空前活跃。同时,一些新的模拟进化算法也逐渐出现并日益完善,为这类复杂优化问题提供了一定的解决方案。遗传算法是目前研究最多、应用最广的模拟进化算法,在众多领域得到了广泛应用。
1 遗传算法
遗传算法是基于自然选择和自然遗传机制的一种随机搜索算法。遗传算法与传统的搜索算法不同,具有如下特点:(1)遗传算法不是对变量直接操作,而是对其编码进行操作;(2)它是从一组点出发进行搜索,而不是从单个点开始;(3)它不需要导数等信息;(4)它是一种随机搜索算法。
遗传算法的主要操作有:复制、交叉、变异。复制体现了“适者生存,不适者淘汰”的自然选择机制。交叉操作使得后代能够继承父代的优良特性。变异操作在增加种群多样性方面具有重要作用。
遗传算法的应用过程主要包括:编码、构造初始种群、设计适应度函数、确定遗传算法结构、选择遗传算子、确定遗传算法的控制参数。
2 函数优化问题中的遗传算法
2.1 编码问题
遗传算法编码方式有多种形式,如二进制编码、浮点数编码、整数编码、符号编码、矩阵编码等。对于实值函数编码,最常用的编码方式是二进制编码,二进制编码实际就是对搜索空间均匀划分,所求解的精度受到编码长度的限制。如果编码长度过短,则求解精度下降;反之,如果编码长度过长,则搜索时间相应增加,不利于实际应用。因而对函数优化问题,实数编码已逐渐引起重视。
2.2 选择方法
常用的选择方式有:(1)适应度比例选择方法。这是最基本最常用的选择方法,又称赌轮选择。个体被选中的概率与其适应度成比例。(2)最佳个体保留方法。它把群体中性能最好的个体直接复制到下一代。(3)期望值方法。它首先计算每个个体在下一代中的期望数目。若某一个体被选中并参与交叉配对,则它在下一代中的期望生存数目减去0.5。否则,该个体的期望生存数目减去1。当某一个体的期望生存数目小于0时,该个体不参与选择。(4)联赛选择方法。从群体中任意选择一定数目的个体,将其中性能最好的个体保留到下一代,重复这一过程,直到生成整个种群。(5)排挤方法。在该方法中,新生成的子代将替代或排挤相似的旧父个体。
2.3 遗传算子
以优化问题
为例进行说明。
(1)变异算子
均匀变异:随机选择某一位j:1≤j≤n,把该位改变为区间[ai,bi]上的随机变量
边界变异:随机选定某一位j,把该位变为相应元素的上(下)界
非均匀变异:随机选定某一位j,把它变为[ai,bi]内的非均匀随机数
其中,f(G)=(r2(1-fracGGmax)b;r1,r2∈U(0,1);G,Gmax分别表示当前遗传代数和最大遗传代数;b是一控制参数。
多点非均匀变异:每次选定多个点进行上面所述的变异。
(2)交叉算子
实值简单交叉:与二进制编码中的简单交叉方式相同。
算术交叉:对个体X、Y,交叉后代为(r∈U(0,1))
启发式交叉:
同时执行可行性检查,即检查各元素是否超出其上(下)界(其中r∈U(0,1))。
3 遗传算法求解函数优化的Matlab程序实现
为了体现优化问题的普遍性,这里的优化对象选择一个多峰函数
采用二进制编码,种群中的个体数目为10,染色体长度为20,交叉和变异概率分别为0.95和0.08.其Matlab的主程序源代码如下:
图1为目标函数的图形和初始化随机种群的个体分布图。经过一次遗传迭代后,寻优结果如图2所示,图中”o”表示经过一次迭代后的个体分布,此时最优解=2.8979,16.2130。
经过25次遗传迭代后,寻优结果如图3所示,图中“*”表示经过迭代后的最优结果,此时最优解x=7.8567,24.8554。迭代过程中迭代次数与函数值的变化如表1所示。图4则通过进化过程中种群平均值和解的变化绘出了遗传算法的寻优性能。
4 结束语
本文对遗传算法用于函数优化问题的主要遗传算子进行了综述。并利用Matlab中已有的遗传算法工具箱给出了一个多峰函数的实际算法。
参考文献
[1]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004.
[2]王小平,曹立明.遗传算法—理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[3]潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998.
[4]孔敦卫,潘凤萍.自适应遗传算法及应用[M].北京:中国矿业大学出版社,2003.
[5]殷铭,张兴华.基于Matlab的遗传算法实现[J].电子技术应用,2000(1).
[6]王玉良.基于MATLAB的遗传算法可视化仿真系统研究[J].计算机系统应用,2004(10).
[7]E.B.马格雷伯.MATLAB原理与工程应用[M].北京:电子工业出版社,2002.
PID参数优化算法 第8篇
PID控制即比例-积分-微分 (Proportion-Integral-Derivative) 控制, 它是建立在经典控制理论上的一种控制策略。在工业过程控制系统中, 当被控对象的结构和参数不能完全掌握, 或精确的数学模型难以建立, 或控制理论的技术难以采用时, 系统控制器的结构和参数必须依靠经验和现场调试来确定, 这时最常用的就是PID控制。即使我们不完全了解一个系统和被控对象, 或不能通过有效的测量手段来获得系统参数时, 也适合采用PID控制技术。PID控制器就是根据系统的误差, 利用比例、积分、微分计算出控制量进行控制的。它是迄今为止历史最悠久, 生命力最强的控制方式, 国内外95%以上的控制回路仍然采用PID结构。在控制理论和技术飞跃发展的今天, PID控制器仍被广泛应用主要是因为其控制结构简单、稳定性能好、可靠性高、易于实现等优点, 而且许多高级控制都是以PID控制为基础的。而PID控制效果完全取决于PID参数的整定与优化, 因此, PID参数的整定[1,2,3]与优化算法显得尤为重要。为了实现最优PID控制, PID参数优化算法已成为国内外控制理论研究的一个热点, 由于单纯形法等算法运算量大, 而且极易陷入局部最优, 因此需要找一种简单而高效的PID参数优化算法。近年来, 随着计算机技术的发展, 一些新的智能算法得到了迅速发展和广泛应用, 特别是模拟进化算法, 在理论研究和应用研究方面都相当活跃。目前, 对PID参数优化算法的研究仍在继续, 许多期刊不断地发表新的研究成果。本文主要介绍了五种PID参数优化算法, 并对PID参数优化算法的发展作一综述。
2 PID参数优化简介
PID控制器由比例、积分和微分环节组成, 其控制规律可表示为:
undefined
将式 (1) 写成传递函数形式:
undefined
式中:KP比例系数;TI积分时间常数;TD微分时间常数。
PID参数优化通常由两部分组成, 分别为目标函数与优化算法的选取。PID参数优化的目标函数通常是控制系统性能指标的定量描述, 而控制系统的性能指标通常包括动态和静态两个方面。动态性能指标用于反应控制系统的瞬态响应情况, 体现在:①控制系统的准确性或控制精度, 通常用稳态误差来描述, 它表示系统输出稳态值与期望值之差;②响应的快速性, 通常用上升时间 (系统输出值第一次达到稳态值的时间) 来定量描述;③控制系统的稳定性, 通常用超调量和调节时间来描述。
PID控制器的比例环节可以缩短系统响应时间, 积分环节可以减小系统稳态误差, 微分环节可以改善系统超调量, 因此, 可以通过调整KP, TI, TD这三个参数来改善动态性能指标, 使系统的控制性能达到给定的要求。从优化的角度来说, 就是在这三个变量的参数空间寻找最优值, 使系统的控制性能达到最优。
3 PID参数优化算法
3.1 基于遗传算法的PID参数优化
遗传算法 (Genetic Algorithm, GA) 是一种新发展起来的优化算法, 它起源于60年代对自然和人工自适应系统的研究, 是模拟生物在自然环境中的遗传和进化进程而形成的一种自适应全局优化概率搜索算法, 其基本思想是, 将待求解问题转换成由个体组成的演化群体和对该群体进行操作的一组遗传算子, 经历生成评价选择操作的演化过程, 反复进行, 直到搜索到最优解。
遗传算法的基本特点是:①它是对所求参数对应染色体进行进化, 而不是对参数本身, 因此不受目标函数约束条件的限制, 也不受搜索空间的限制;②它是对参数表示成的二进制编码串群体进行搜索, 而不是在单个点上寻优, 这大大减小了陷入局部最优的可能性, 具有全局快速收敛的特点;③它只需已知目标函数及适应度函数便可开始操作;④其初始群体是随机生成的, 可以很快到达最优解附近;⑤它具有并行性, 即用较少的编码串对数量较大的区域完成搜索;⑥其缺点是实时性不好, 容易出现早熟现象, 对于系统中的反馈信息利用却无能为力, 而且求解到一定范围时往往做大量无为的冗余迭代, 求解最优解的效率较低。
毛敏等用基本的遗传算法对PID参数进行了优化, 但在优化一些复杂问题时有着不可忽视的缺点, 而且基本遗传算法收敛速度慢、容易早熟, 这就使得该算法的优化性能大大降低;范敏提出了基于多种群遗传算法的优化方法, 并将其与下山单纯形法相结合, 用下山单纯形法进行局部优化, 加快了收敛速度, 避免了早熟现象的发生, 实现了快速优化求解, 并得到了比基本遗传算法更为理想的控制效果;王焱等针对标准遗传算法收敛速度慢、易陷入局部极小等问题, 提出了基于变尺度混沌优化策略的混沌遗传算法, 该算法对经过一次遗传操作的群体进行混沌搜索寻优, 引导种群快速进化, 并将其成功应用于冷轧参数的优化计算中, 大大提高了局部搜索能力, 有效地避免了早熟以及局部最优现象的发生。
3.2 基于蚁群算法的PID参数优化
蚁群算法由意大利学者M.Dorigo、V.Maniez-zo、A.Colorini等人根据蚂蚁群体具有智能的特点首先提出, 当时他们称之为蚁群系统, 后来M.Dorigo等为了其他学者研究的方便, 将各种蚂蚁算法统称为蚁群算法, 并为该算法提出了一个统一的框架结构模型。蚁群算法是90年代初期才提出的一种新型的进化算法, 虽然其起步较晚, 但是对蚁群算法的研究已引起了国际上学者们的广泛关注。
蚁群算法是一种基于种群的启发式仿生进化算法, 其基本思想来源于蚂蚁之间的交流过程。外出觅食的蚂蚁在自己经过的路上留下一定数量的信息素, 信息素一方面会随着时间的流逝而挥发, 另一方面, 当有其他的蚂蚁再次经过该路径时会再次留下信息素以加强该处的信息素。在任何一个路口, 蚂蚁会按照概率选择任意一个方向前进, 在信息素浓度较高的方向具有较大的选择概率。
蚁群算法的基本特点是:①其原理是一种正反馈机制, 它通过信息素的累积和更新收敛于最优路径;②它是一种通用型随机优化算法, 但人工蚁群算法决不是对蚂蚁的简单模拟, 它融进了人类的智能;③它具有分布式并行搜索能力, 该计算机制易于与其它算法结合;④它是一种全局优化的算法, 可用于任何一类优化问题;⑤它有较强的鲁棒性;⑥其缺点是初期信息素匮乏, 求解速度较慢, 计算时间较长。
王建国等将神经网络作为预测模型来预估过程未来的偏差值, 并利用数字计算机的计算能力实现在线滚动优化计算, 从而确定当前最优输入策略, 运用蚁群算法预测PID控制能够适应控制对象模型参数的时变, 具有较好的鲁棒性, 相对传统PID控制策略还表现出了良好的动态性能;贺慧杰将遗传算法和蚁群算法相结合对PID参数进行优化, 可以较好地控制复杂的对象, 但是, 一旦外界扰动发生时, 必须重新根据需要再进行参数的整定优化;陈建涛等用高斯分布较好的局部搜索能力来增强蚁群算法的局部寻优能力, 很好地弥补了基本蚁群算法易于陷入局部最优的缺点, 且该算法不依赖于被控对象的精确数学模型, 有着很好的适应性和鲁棒性。
3.3 基于粒子群算法的PID参数优化
粒子群 (Particle Swarm Optimization, PSO) 算法是由Kennedy和Eberhart博士于1995年受鸟类群体行为研究结果的启发, 而提出的一种基于群体智能的进化计算技术。在PSO算法中, 每个粒子代表解空间的一个候选解, 粒子在搜索空间以一定的速度飞行, 飞行速度根据飞行经验进行动态调整。该算法基于群智能的并行全局搜索策略, 采用速度-位置搜索模型实现对整个空间的寻优操作。PSO算法是模仿生物社会性行为而得出的一种全局优化算法, 是一种高效、简单的并行搜索算法, 其优点在于概念简单、实现容易、鲁棒性好, 并且能以较大概率收敛到全局最优, 而且它对所优化目标的先验知识要求甚少, 一般只需知道其数值关系即可。但是, 该算法的惯性权重对算法性能具有很大的影响, 另外, 在初始群体的生成上, 它是根据经验估计出PID三个参数的取值范围, 并在此范围内采用随机生成的方式, 对其可行解空间进行搜索的, 因此需要合理估计PID三个参数的取值范围。
杨诚等针对全局版标准PSO算法容易陷入局部极值点这一缺点, 提出了实数编码的局部版标准PSO算法, 采用该算法搜索所得的解比全局版算法更优, 但速度较慢;熊伟丽等对标准PSO算法进行了改进, 提出了一种改进的粒子群算法MWPSO, 使惯性权重具有了一定的灵活性, 同时, 该算法在收敛的情况下, 所有粒子都向最优解的方向飞去, 从而粒子趋于同一化的问题进行了改进, 为改善系统的过渡性能和动态特性, 还在目标函数中加入控制输入的平方项, 并采用了惩罚功能, 使得相同迭代次数下该算法的性能指标远远优于遗传算法;李凌舟等提出一种改进的微粒群优化算法 (IPSO) , 该算法是在基本PSO算法的惯性权重部分加入一个调节因子项, 实现惯性权重的非线性调整, 并通过调节因子的调节, 使得算法的前期有较大的收敛速度, 后期则能以较大的概率收敛到全局最优;郭成等针对微粒群优化算法存在的早熟问题, 提出了一种基于T-S模型的模糊自适应PSO算法 (T-SPSO算法) , 该算法通过T-S规则, 动态自适应更新惯性权重取值, 使得算法前期以较大惯性权重值保证算法的全局搜索能力, 而后期则以较小惯性权重值加快收敛, 从而有效解决了PSO算法的早熟问题, 改善了算法的收敛性。
3.4 基于模糊推理的PID参数优化
随着计算机尤其是微机的发展和应用, 自动控制理论和技术获得了飞跃的发展。基于状态变量描述的现代控制理论对于解决线性或非线性、定常或时变的多输入多输出系统问题, 获得了广泛的应用。但是, 无论采用经典控制理论还是现代控制理论设计一个控制系统, 都需要事先知道被控制对象精确的数学模型, 然后根据数学模型以及给定的性能指标, 选择适当的控制规律, 进行控制系统设计。PID控制器设计的关键在于如何合理地确定比例、积分、微分参数的大小, 然后进行人工在线整定。然而, 在许多情况下被控对象 (或生产过程) 的精确数学模型很难建立, 或系统参数不能通过有效的测量手段来获得, 或控制理论的技术难以采用时, 就难以进行自动控制。自1965年L.A.Zadeh提出模糊集的概念以来, 关于模糊系统的研究得到了飞速的发展, 随后模糊控制技术也被广泛应用于工业控制过程中, 并取得了令人瞩目的成就。模糊推理是模糊控制的理论基础, 该算法就是运用模糊数学的基本理论和方法, 把控制规则的条件、操作用模糊集表示, 并把这些模糊控制规则以及有关信息 (评价指数、初始PID参数等) 作为知识存入计算机知识库中, 然后计算机会根据控制系统的实际响应情况 (即专家系统的输入条件) , 运用模糊推理自动实现对PID参数的整定。
由于主管道蒸汽温度控制具有大惯性、大延迟、时变等特性, 而采用常规PID控制难以获得满意的控制效果, 李茜等提出一种模糊自整定PID控制器的串级控制算法, 该算法通过模糊决策来对其控制器的PID参数进行调整, 用模糊规则进行推理, 模糊规则采用产生式表示方式, 即IF (条件) THEN (结果) 形式, 并且它对不同的控制指标和被控对象均能实现PID最佳调整, 是一种实施简单、性能良好、易于工程实现的方法;曾晓红等首先利用遗传算法的全局优化能力优化PID参数, 得到PID参数的初始值, 然后根据系统当前的误差和误差变化率, 用模糊推理方法在线优化调整PID参数的权值来动态地调整参数, 抗干扰强, 灵敏性较好。
3.5 基于神经网络的PID参数优化
人工神经网络 (Artificial Neural Network, ANN) 是由大量简单人工神经元互联而成的一种计算结构。由于其大规模并行处理、学习、联想和记忆等功能, 以及它的高度自组织和自适应能力, 并且能够充分任意地逼近任何复杂的非线性系统, 所有定量和定性分析都等势分布储存于神经网络内的各种神经元中, 具有很强的信息综合能力, 能够学习和适应严重不确定系统的动态特性, 有很强的鲁棒性和容错性, 可以处理那些难以用模型和规则描述的过程, 因此, 神经网络已成为解决许多工程问题的有力工具, 并且在一些不确定系统的控制中已成功应用。Hopfield神经网络 (Hopfield Neural Network, HNN) 是Hopfield于1982年提出的反馈神经网络模型, 简称Hopfield网络。由于网络中引入了反馈, 所以它是一个非线性动力学系统。通常非线性动力学系统最关心的是系统的稳定性问题, 在Hopfield模型中, 神经网络之间的联系总是设为对称的, 这保证了系统最终会达到一个固定的有序状态, 即稳定状态。利用该特性, 可以将Hopfield网络用于联想记忆, 也可以用来对组合优化问题进行求解。
韩伟利用神经网络来逼近实际系统, 用闭环控制下所得的观测数据进行系统在线辨识, 并针对不同的系统建立不同的对象模型, 并在该模型的基础上, 运用遗传算法进行PID参数寻优, 取得了较好的控制效果;鉴于遗传算法虽能求得全局解, 但收敛速度慢, 而基于神经网络的控制器结构简单、可塑性强, 但容易陷入局部解, 何军旗等提出将遗传算法和BP神经网络相结合进行PID参数优化, 使系统整体得到优化, 且动态性能更好, 调节精度更高。
4 小 结
PID控制器是整个控制系统的核心, 它的控制作用以及参数对控制品质有直接影响。目前, PID参数优化算法很多, 但是, 无论哪种优化算法, 都有一定的适用范围。以上介绍的参数优化算法也只是其中比较有代表性的算法, 对其研究已经取得一定的成果, 但仍有许多不足之处, 有待进一步研究。从目前PID参数优化算法的研究现状来看, 以下几个方面将是今后一段时间内研究和实践的重点。
(1) 由于基本的粒子群算法易陷入局部极小值点, 且搜索精度不高, 因此, 可以利用混沌序列的“遍历性、随机性、规律性”, 在其中加入混沌细搜索, 使得局部搜索能力大大提高。
(2) 鉴于蚁群算法具有分布式并行搜索能力, 且易于与其它算法结合, 是一种全局优化的算法, 因此, 可以利用蚁群算法的全局优化能力优化PID参数, 得到PID参数的初始值, 然后根据系统当前的误差和误差变化率, 用模糊推理方法在线优化调整PID参数的权值来动态地调整参数。
(3) 由于人工神经网络能够充分任意地逼近任何复杂的非线性系统, 能够学习和适应严重不确定系统的动态特性, 有很强的鲁棒性和容错性, 可以处理那些难以用模型和规则描述的过程, 因此, 可以用神经网络来逼近实际系统, 用闭环控制下所得的观测数据进行系统在线辨识, 并针对不同的系统建立不同的对象模型, 并在该模型的基础上, 运用蚁群算法进行PID参数寻优。
(4) 除了对各种算法继续进行全面深入的研究外, 还应考虑将各种算法互相结合, 互相渗透, 充分发挥各自的优势, 并且希望能更多地结合实际工程应用, 扩展各算法的应用领域, 从而进一步提高控制系统的性能, 实现PID最优控制。
摘要：PID参数优化是自动控制领域研究的一个重要问题。为了实现最优PID控制, PID参数优化算法已成为国内外控制理论研究的一个热点。随着计算机技术的发展, 一些新的智能算法得到了迅速发展和广泛应用, 并在理论和应用方面都有重要的意义。主要介绍了PID参数优化算法以及近年来在此方面取得的研究成果, 并对未来PID参数优化的研究方向作了展望。
粒子群优化算法简介 第9篇
由于认识到PSO在函数优化等领域所蕴涵的广阔的应用前景，目前已提出了多种PSO改进算法，并且广泛应用于函数优化，神经网络训练，模式分类等应用领域。本文将介绍基本PSO算法以及几种典型的改进算法。
1 粒子群算法
PSO是群智算法中的一种，PSO中，每个优化问题的解都是搜索空间中一个“粒子”的状态。所有的粒子都有一个适应函数(fitness function)决定的适应值(fitness value)，每个粒子还有一个速度直接影响它们飞翔的距离。粒子根据当前自身情况和粒子群的情况在解空间中搜索。PSO初始化时，将一群粒子的状态赋随机值(随机解)，然后根据公式(1)和(2)来更新自己的速度和新的位置。
其中vid是粒子的速度，c1,c2是学习因子，Rand()是介于(0,1)之间的随机数，xid是粒子当前位置，pid是粒子当前极值，pgd是粒子群当前极值，在公式(1)，等式右边共有三项，第一项是粒子上一次的速度vid与惯性因子w的乘积，惯性因子即是粒子上一次的速度对本次飞行速度的影响因子，Shi[1]研究了惯性因子w对优化性能的影响，发现较大的w值有利于跳出局部极小点，而较小的w值有利于算法收敛;第二项是粒子自身行为差异比较;第三项是粒子群体行为差异比较;后两项合称为粒子的“意识”部分。
图1是PSO迭代曲线示例，其实验参数分别为：粒子个数是20;w=0.9;维度为10;适应函数为;粒子群最佳适应值变化曲线为左下方的红色虚线;平均适应值变化曲线为右边的蓝色实线;迭代次数为400。从图1中可以看出粒子群最佳适应值在不断减小，平均适应值有起有落表明在不断快速跳出局部极小值最终到达全局极小值。
2 邻域粒子群优化算法
粒子群算法中的每个粒子的每一次迭代，速度的更新由三个因素决定即在(1)中等式右边的三项：粒子上一次的速度vid与惯性因子w的乘积，粒子自身的认知部分，粒子群体意识部分。由于视野和视力范围的限制，实际觅食鸟群中的个体并不一定拥有全局“意识”而是观察周围飞鸟的位置和速度情况。在全局模式中，每个粒子的轨迹受例子群中所有粒子的所有的经验和意识的影响。在局部模式中，粒子的轨迹只受自身的认知和最邻近的粒子状况的影响。观察实际的飞鸟觅食过程，往往只是看到相邻的飞鸟的位置和动向，就这一点而言，局部模式更接近粒子群算法的生态本质。
3 混沌粒子群算法
3.1 混沌理论
1972年12月29日，美国麻省理工学院教授、混沌学开创人之一E.N.洛伦兹[1]在美国科学发展学会上提出一个貌似荒谬的论断：在巴西一只蝴蝶翅膀的拍打能在美国得克萨斯州产生一个陆龙卷，并由此提出了天气的不可准确预报性。混沌是一种普遍的非线性现象，其行为复杂且类似随机，但存在精致的内在规律性。混沌具有其独特的性质：随机性、遍历性、规律性。
3.2 混沌粒子群算法
针对粒子群算法中存在粒子的位置和速度初始赋值具有随机性，不宜有遍历性的弱点，产生了混沌粒子群优化算法，该算法利用混沌确定性与随机性的统一、对初始值敏感性和混沌的遍历性特点，引导粒子群中的粒子搜索。混沌PSO基本思想就是用类似载波的方法将混沌状态引入到优化变量(在粒子群算法中用粒子的维度表示)中，并把混沌运动的遍历范围由[0,1]区间“放大”到优化变量的取值范围，然后利用混沌变量进行搜索，具体表现在群体的混沌初始化和最优个体的混沌变尺度载波。
4 结论
本文介绍了基本PSO算法以及两种典型的改进算法，基于这两种方法，可以有效避免粒子搜索过程中容易发生的早熟，甚至是停滞，提高了粒子的搜索效率，改善了粒子群优化的性能。
参考文献
[1]R.C.Eberhart,Y.Shi.Comparison between genetic algorithms and particle swarm optimization[M].Proceedings of7th annual confer-ence on evolutionary computation,1998,611-616.
[2]J.Kennedy,R.Eberhart.Swarm Intelligence.Morgan Kaufmann Publishers[J].Inc,San Francisco,CA,2001.
[3]R.C.Eberhart,Y.Shi.Comparison between genetic algorithms and particle swarm optimization.Proceedings of7th annual conference on evolutionary computation,1998:611-616.
[4]V.Ferrari,T.Tuytelaars,and L.Van Gool.Markerless Augmented Reality with a Real-Time Affine Region Tracker[J]Proc.IEEE and ACM Int'l Symp.Augmented Reality,pp.87-96,2001.
[5]E.S.Peer,F.van den Bergh,A.P.Engelbrecht,Using Neighborhoods with the guaranteed Convergence PSO[J].Proceed of IEEE con-ference on Evolutionary Computation,2003,235-2.
