论文研究-一种面向汽车系统可靠性优化的任务分配方法.pdf

所需积分/C币:5 2019-07-22 23:32:10 873KB .PDF

对电子控制单元进行任务分配是汽车电子软件设计阶段一项非常重要的工作;以最大化系统可靠性为目标进行任务最优分配是一个NP-难问题。提出了一种改进的粒子群优化算法用于对任务进行近似最优分配以尽量提高系统的可靠性;通过在基本粒子群优化算法中引入一个新的变异操作有效提高了算法的收敛速度和解的精度。实验仿真表明该算法具有良好的有效性和可行性。
2464 计算机应用研究 PA,p≤P 4)其中:为惯性权重,表示粒子上一次的迭代速度对当前速度 的影响程度,可以平衡算法的全局和局部搜索能力;c1和c2是 3.2ECU的内存消耗约束 两个常数,叫做学习因f;和3是[0,1范围内的随机数。 ECU的存储容量非常有限,任务分配必须考志内存消耗为了避免粒了“飞出”搜索空间,每个粒了的速度通常被限制 约束要求。分配到ECU上的若十任务所消耗的内存之和不能在[-tm,Dm中。 超过该FCU的最大可用内存。假设任务i消耗的内存用m表4.2改进的粒子群优化算法 示,M为eu的最大可用内存,则内存消耗约束条件表示为 粒子群优化算法最初主要用于求解连续函数的优化问题, ∑m,A1,≤M (5)而任务分配问题属于离散组合优化问题,因此需要对粒子的位 3.3广义目标函数 置和速度进行重新定义。假设ECU的数目为n,任务数目为 m,则ECU可用[1,n]内的整数进行编号,任务可用[1,m内 结合前面的分析,得到任务分配的可靠性优化模型如下: 的整数进行编号。粒子的位置、速度和适应度函数定义如下 min:cos(A)=∑∑A,ET.,4,+∑∑2∑ApC.A,4 p=19>q=1j= n)粒子位置。定义粒子的位置为一个m维向量,其元素 st.2P:A,1≤Pp,Veu 取值为[1,n]中的整数,代表任务编号到ECU编号的一种映 射。如某粒子位置为x(1,2,1,1,3),表示编号为1、2、3、4、5 的任务分别映射到编号为1、2、1、1、3的ECU上,其含义恰好 显然这是一个带约束的优化问题,采用罚函数法将具转换代表了一种任务分配方案 为一个不带约束的优化问题。根据上面的可靠性优化模型定 b)粒子速度。速度的作用主要是用于改变粒子的位置。 义广义目标函数如下 本文中定义粒子的速度为一个m维向量,并用「0,1范围内的 min; value( A)=cost(A)+8((a)+8,B(A) (6 随机数对其进行初始化 其中:第一部分cos(A)为要优化的代价函数;第二部分81a c)适应度函数。适应值主要用于评价粒子质量的好坏, (A)+8(A)为惩罚项,惩罚不满足约束要求的解,a(A)、B其值越大直观上粒子质量越好。本文中适应值的极性恰好与 (A)分别为违反约束条件(式(4)和(5))对应的惩罚函数,6、所定义的广义目标数(式(6))的极性相反,因此适应度函数 6为两个怎罚函数的权重。为了取得较好的惩罚效果,本文被定义为 的惩罚函数定义如下 fitness( A)=1/value (A) (11) 此外,由于位置在速度的作用下可能会产生负数和小数从 (A)=∑max(0.∑PA,-P) 7) 而违背粒子位置的含义,本文采用了舍去符号和取整的方法, B(A)=∑ Ai p-M) (8)使得粒子史新后的位置仍然是合法的位置。 针对粒子群算法容易陷入局部最优导致解精度下降的缺 4改进的粒子群优化算法 陷,本文引人了一种变异策略。在每次迭代过程中,随机选择 粒子位置向量的某个元素进行随机变异生成新的粒子,通过比 4.1基本粒子群优化算法 较新旧两个粒子的适应值来控制变异的代数。一旦变异后生 粒子群优化算法( particle swarm optimization,rsO)是Kem成的新粒子适应值比原粒子好,则用新粒子替换原粒子进入下 ncdy等人受到鸟类觅食行为的启发于199年提出的一种群智代,否则继续变异直到生成适应值比原粒子更优的粒子。通 能算法,算法实现简单、效率较高,自其提出以来便引起了过引人这种变异操作有效地增强了种群在迭代过程中的多样 研究者的广泛关注。 性,一定程度上提高了粒子的全局收敛能力,从而提高了解的 粒子群优化算法的基本思想是:将群体中每个无质量的粒精度。 子看做问题解空间中的一个潜在解,每个粒子在某一时刻都有 本文设计的改进的粒子群优化算法流程图如图3所示,算 个由目标函数决定的适应值和一个多维的速度和位置向量,法具体步如下 其中适应值用于评价粒千的质量,维数由解空间的大小决定。 a)随机生成规模为N的粒」种群,并在允许的范围内对 算法首先随机初始化一群粒了,然后在迭代过程中粒子通过跟粒子的位置和这度进行初始化,每个微粒的p1设为其初始位 踪两个极值来更新白己:一个是粒子本身找到的最优解,称为置,P灬中的最好值设为P; 个体历史最优位置p-;另一个是整个粒子群体目前找到的最 b)计算粒子的适应值,并且根据粒子适应值更新个体历 优位置,称为群体历史最优位置P算法终止时的群体历史史最优位置p和群休历史最优位置P; 最优位置p即是所求问题的最优解。 c)采用粒子速度和位置向量更新公式更新粒子的状态; 设粒子种群规模为N,X={x1,xa,…,xD}为第i个粒子 d)随机选择粒子的某个元素进行随机变异生成新粒子; 的当前位置向量;V=1,D,…,Dm为第i个粒子的当前“飞 e)比较新旧两个粒子的适应值,如果新粒子适应值较优 行”速度向量粒子当前搜索到的个体历史最优粒子位置为则转下一步,否则转d)继续进行变异 P,样体历史最优粒子位置为p;粒子在“飞行”过程中按照 f)判断算法迭代终止条件是否满足,如果满足终止条件贝 下列公式更新自己的速度和位置向量 输出结果,程序结束;否则,转b D;(t+1)=1(1)+c1r1(t)( presl-x(t))+ 5实验结果及分析 (9) (t+1 (+1)+x;() (10) 本文的实验平台是: Windows XP操作系统,512MB内存 第7期 李蕊,等:一种面向汽车系统可靠性优仳的任务分配方法 2465 MATLAB7.0工具以及LINO8.0工具。其中, LINGO8.0是有效解。如图5中对于8个任务到16个ECU上的分型、图6 种通用优化求解器,可以用来求解问题的全局最优解。关于中当任务数超过18时, LINGO优化求解器均出现了求解失败 任务分配问题的相关参数说明如下:FCL的失效率和通信链的现象。 路的失效率范围分别为[0.00005,0.000,[0.00015, 0.96885 文算法 0.000],内存容量和ECU的最大负载范围均设定为[100, 三D.93770 0算法 D算法 200],任务计算所需要的CPU资源和内存资源设定为1,60]。 20.87540 E0.81310 初始化 4,8)(5.10)(6,12)(7,14)(8.16) task 计算子适应度更新和2 图5第二组实验中四种方法的性能比较 [根掂速度、位置史公式史浙粒子状态 0.99491 TINGO 092643 文算法 变异产生新的粒子 e0.85795 目O算法 下0算法 近粒子适应值较好 a0.78947 0.65251 新粒子替换原粒于1 0.51555 4,12)(5,15)6,8)(7,21)(8,24) 否满足终止条丌 feel, task) 结束 图6第三组实验中四种方法的性能比较 图3算法流程图 表1是三个近似算法运行10次所需要的平均计算时间和 本文算法的其他参数设置如下:粒子种群规模N取 ECU LINGO优化求解器的计算时间的详细比较表中的NA表示算 法运行时间无穷大,LⅠNCO求解失败。由表中数据可知,本文 节点数的两倍,惯性权重系数设定为=m20m-吨×算法的不足之处是在平均计算时间方面较一般PSO算法耗时 ler。其中ler。和ier分别为算法的最大迭代次数和当前迭稍长些,这是由于变异操作产生新粒子的过程耗费了一定时 代次数;m和m分别取0.9和0.4。随着达代的进行,线性间,但是其计算时间相对HPSO算法增长较缓慢,总体上可以 减少v的值可使算法获得更好的收敛速度和求解精度。学习接受。特别是相对LNO优化求解器来说,随着LCU数和任 因子c1=c2=2.05,mn=10,最大迭代次数 iter=100 务数的组合规模扩大时,INGO求解器所需的计算时间剧增, 为了能较准确地反呋问题,实验总休上分为三个组。第一甚至不能求得可行解时,利用本文算法来获得精度较高的近似 组对应较低负载情况,一个ECU上平均大概执行一个任务;第最优解将是一种非常可行而有效的方法。 二组和第三组对应较高负载情况,分别考虑任务数为ECU数 表1算法计算时问详细比较/s 的两倍和三倍的情况。对于每一组实验,在保持算法在共有参 (ecu,tdsk)本文算法 FSO算法 PSO算法LNGO 数一致的前提下,针对不同的ECL数和任务数的每个组合在 0.69221 4.09063 6.07031 0.8734 同一P机上分别独立运行本文算法、文献7]中的HPSO算 5.57656 6.68281 1.2140 法以及一般Ⅳ算法各10次,然后求得平均值。对于LNG (9,11) 7.8750 9.46940 1.55784 求解器,由于其求得的解是一个精确的全局最优解,对于每个 (10,12 8.42656 144.30000 1.54219 8658 组合只需宴用LNGO求解一次即可。 1.82344 2.75156 按照上述实验方汏分别进行实验。图4是第一组实验中 2.62188 2.91250 U.65469 (6,12)2.985944.38125 0.81094 三个近似算法和IIN(O优化求解器所获得的全局最优解的直 (7.14) 3.56719 12.80938 0.96875 1751 观比较。由图可知本文算法所获得的平均最大可靠性较HP- 17.70000 1.1750 sO算法、一般PSO算法更接近于 LINGO所获得的全局最优 2.10469 4.62969 0.51250 (5,15) 2.58594 9.|828 D.71250 解,特别是相对于PSO算法其最优解的精度得到了非常明显 (6,18) 3.41720 0.85875 的提高。这是因为本文算法中引入的变异操作一定程度上增 (7,21) 强了粒子的全局寻优能力,提高了算法的全局搜索能力,从而 8,24) 4.475U0 38.26250 1.33125 提高了算法的求解精度。 6结束语 100000 INGO 0.98412 0.96824 又算法 本文针对汽车电子系统中ECU节点的任务分配问题,提 0.93648 nsO算法 0.92060 算法 出了一种在非冗余条件下将系统可靠性作为优化日标进行任 0.90472 务分配的方法。在基本粒子群优化算法的基础上通过对粒子 7.9)(8,10)(9,11)(10.12) 位置、速度和适应度函数进行重新设计,成功地将其用于求解 图4第一组实验中四种方法的性能比较 仟务分配这一组合优化问题。通过在算法的迭代过程中引人 图5和6是较高负载情况下四妽方法所获得的平均最大一种变异操作提高了解的精度,一定程度上克服了PSO算法 可靠性的直观比较。由图可知,在较大规模的问题下本文算法过早陷入局部最优的缺陷。实验仿真表明,该算法具有良好的 所获得的最优解的精度仍然优于另两种近似算法所求得的解。可行性和有效性。下一步工作是结合汽车电子系统的特点综 在这两组实验中,随着任务数和ECU数的增加,LNCO优化求合考虑可靠性及其他优化日标对任务分配进行多日标优化。 解器的计算岀现了爆炸性増长,直至求解失败不能得到问题的 (下转第2469页) 第7期 王欣:两阶段的多元时间序列异常检测算法 2469 以同时记录几百到几千个传感器采集的飞行参数,大多数参数包括MIS相似性度量和异常程度度量的改进,以及算法效率 的采样频率是1Hz。实验采用某航空公司的同一个航线上同的优化等。 一个机型的1200个航班的QAR数据,并从飞行参数中选择参考文献 了包含飞机性能和飞行状态的30个参数。为了使航班之间的 [ 1] HODGE Y J, AUSTIN J. A survey uf outlier detection Inethudologit 飞行数据具有可比性,将飞行过程划分为若干飞行阶段(滑 IJ. Artificial Intelligence Review, 2004. 22(2): 85-126 跑、起飞、爬升巡航、下降、进近、着陆等),每个阶段的飞行数 [2 YANG K, SHAHABI C. A PCA-based similarity measure for multiva 据就构成一个MTS序列。由于各航班的同一个飞行阶段的时 ate time serics[C//Proc of the 2nd ACM International Workshop on 问长短不一,数据集中的MS是不等长序。MTS序列中数 Ultimedia databases. New York. ACM P. 据趋势的突变或变量间相关关系的突变等都会使得序列呈现[3孔成安,李文华,尹湛,利用QAR数据实施飞机性能监控[J.中 出异常,其中可能蕴涵着飞机性能和飞行状态方面的重要信 国民用航空,2008,94(10):54-56 息。取最近邻个数k=10、异常点个数n=5,在QAR数据集上4] ANgiUlLi F, PIZZUTI C. Outlier mining in large high- dimensional 执行 TSOD-MTS算法,得到五个偏离于大多数正常航班的包含 data sets[ J]. IEEE Trans on Knowledge and Data Engineering 异常飞行阶段的航班。经航空公司的飞行品质监控的专家分 2005,17(2):203-215 析,排除了其中的三个航班,剩下两个航班的异常分别是由于[51 RAMASWAMY S, RASTOGI R,SHIK. Efficient algorithms for 飞行员的不规范操作和发动机性能衰退造成的。说明算法能 mining outliers from large data sets[C//Pror of ACM SIGMOD In 够有效地从大量的OAR数据中发现机组操作和飞行性能方面 lernalional Conference unl Management uf Dala. New Yurk: ACM 存在的问题 Press,2000:427-438 [6 ZHANG Xiao-lei, BEGLEITER H. PORJESZ B, et al. Event related 一T0DMIS算法 potentials during object recognition tasks J. Brain Research Bulle 1200 循环嵌套算法 tin,1995,38(6):531-538 [7 SINGHAL A, SEBORG D E Pattern matching in historical batch data using PCA[J. IEEE Control Systems Magazine, 2002, 22(5) 53-63 100200300400500600700 [8 SHEN H T, ZHOU X, HUANG 7, et aL. Statistical summarization of 样本个数 图1对数据集大小的伸缩性对比 content featuIres for fast near-duplicate video detection [C]//Proc of the 15th aCm International conference on Multimedia. New york 4结束语 ACM Press,2007:164-165 [9] JIANG M F, TSENG SS, SU C M. Twu-phase cluslering proce 本文研究了多元时间序列上的异常检测问题,提出了 TSOD-MTS算法。算法采用BCs方法计算MTS样本之间的相 outlier detection J. Pattern Recognition Letters, 2001, 22( 6-7) 691-700 似性,采用基于距离的方法实现异常检测。为了提高异常挖掘 L10 VU N H, GOPALKRISHNAN V. Efficient pruning schemes for dis- 的效率,算法分为两个阶段。第一阶段采用K- means算法对数 tanee-based outlier detection[ C]//Proc of European Conferenee on 据集进行大致聚类,并用一个启发式规则估计每个簇包含异常 ne learning ane d Principles and Practice of Know ledge Diseovery 点的可能性,按可能性从大到小进行排序;第二阶段在循环嵌 n Databases. London: Springer-Verlag, 2009: 160-175 套算法的基础上增加了两个剪枝规则,可以有效地减少对象间 [11 BAY SD, KIBLER D, PAZZA NI M J, et al. The UCI KDD archive of 距离计算的次数,实现近似线性的时间复杂度。实验结果表 large data sets for data mining researrh and experimentation [J].ACM 明,本文提出的算法是可行而有效的。进一步的研究内容主要 SIGKDD Explorations Newsletter, 2000, 2(2): 81-85 (上接第2465页) rithm[J]. Journal of Systems Architecture, 2001, 47(6): 549 参考文献 554 [I CHIL CC, YEH Y SH, CHOU J S. A fast algorithm for reliability- [6 ATTIYA G, HAMAM Y. Task allocation for maximizing reliability of distributed systems: a simulated annealing approach[J. Journal of oriented task assignment in a distributed system[ J]. Computer Com Parallel and Distributed Computing, 2006, 66( 10): 1259-1266 munications,2002,25(17):1622-1630 [7] YIN P Y, YU SS, WANG Pei-pei, et al. Task allocation for maximi- [ 2] HSIEH CC. Opt im al task allocation and hardware redundancy policies zing reliability of a distributed system using hybrid particle swarm op in distributed computing systems[ I]. European Journal of Opera timization J] Journal of Systems and Software, 2007, 80(5) tional research,2003,147(2):430-447 724-735 liability of distributed computer sys tems J]. IEEE Trans on Com./8 3 SHATZ SM, WANG J P, COTO M. Task allocation for maximizing re [8 TINDELL K, BURNS A, WELLINGS A. Allocation hard real-time task: an NP-hard problem made easy[ J]. Real Time Systems Re puters,1992,41(9):l156-1168 search Group, 1992. 4(2): 145-16 [4] KARTIK S, MURTHY C S R. Task allocation algorithms for maximi--「91明平顺,李晓霞汽车可靠性理论「M1.北京:机械工业出版社, zing reliabilily uf distributed compuling sysleIus[J]. IEEE Trans on 2003 Computers,1997,46(6);719-724. [10 KENNEDY J, EBERHART R C. Particle swarm optimization [C// [5 VIDYARTHI D P, TRIPATHI A K. Maximizing reliahility of distribu Iroc of ieee International Conference on Neural Networks. Pisca ted computing sy stems with task allocation using simple genetic alg away: IEEE Service Center, 1995: 1942-1948

...展开详情
试读 5P 论文研究-一种面向汽车系统可靠性优化的任务分配方法.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-一种面向汽车系统可靠性优化的任务分配方法.pdf 5积分/C币 立即下载
    1/5
    论文研究-一种面向汽车系统可靠性优化的任务分配方法.pdf第1页
    论文研究-一种面向汽车系统可靠性优化的任务分配方法.pdf第2页

    试读已结束,剩余3页未读...

    5积分/C币 立即下载 >