多目标遗传算法（精选12篇）
多目标遗传算法 篇1
目前物流与国民经济的诸多领域都密切相关, 物流产业也越来越得到重视, 被称为企业获取利润的第三个源泉。多目标车辆路径问题作为一种典型的多目标优化问题与日常生活联系紧密, 被广泛的应用于民用物流、军事补给等各个领域, 很难用传统方法获得理想的结果, 属于NP问题。
本文首先重点研究了遗传多目标算法, 并对其不足之处进行了改进, 随后讨论了无时间窗和带时间窗的两类多目标车辆路径问题的模型, 然后将改进的遗传多目标算法应用于这两类车辆路径问题。由于车辆路径问题是物流配送中的主要问题之一, 对该问题进行研究具有很强的现实意义。
1 遗传多目标优化算法
遗传算法是仿生学的搜索方法, 将问题的解编码成染色体, 通过模拟自然界的进化过程, 进行选择、交叉、变异算子的操作, 最终全局解能收敛到最适应环境的子集, 即得到问题的最优解。遗传算法的过程体现了适者生存, 优胜劣汰的自然规律。
其中计算个体的适应度值需要提前确定评价函数, 适应度值用来评价中个体的优劣。终止条件的判断可以是迭代次数或者其他收敛条件。
由于遗传算法不依赖于具体的问题, 本身就具有自组织, 自适应和自学习特征, 已经发展成为有效求解多目标优化的重要算法, 因为被广泛应用于从工程科学到社会科学的各个领域。
遗传算法对解的优劣评价是根据实际问题的目标值而定, 而实际生活中大多数优化问题都是多目标的, 各目标之间通过决策变量相互制约, 导致此类优化问题的解不唯一, 表现为一个最优解的集合。多目标遗传算法必须对多个目标上的值进行评价, 而往往这些目标相互冲突, 很难找到在每个目标上的值都是最优的解, 必须要考虑折衷办法。引入Pareto概念, 用基于Pareto方法来求解问题的最优解。
2 多目标车辆路径问题
车辆路径问题 (Vehicle Routing Problem, VRP) 由Dantzig和Ramser于1959年首次提出, 一直是组合优化领域的热点和前沿问题。对于车辆路径问题的多目标优化, 国内外学者已经进行了较深入的研究, 这些研究基本都是采用聚集函数法, 即将多目标优化问题转化为单目标优化问题, 但这种转化可能导致搜索不到非凸解的问题。本文将车辆路径问题描述成一个多目标优化问题, 对有时间窗限制的多目标车辆路径问题的情况出发, 将遗传多目标优化算法应用其中, 对车辆总行驶距离最短和车辆使用最少等多目标同时优化处理。
2.1 问题描述
车辆路径优化问题是一个典型的组合优化问题, 对其一般描述是:车辆路径问题 (VRP) 是指有一系列客户点 (发货点或收货点) , 为满足客户的需求, 选择适当的行车路线, 并在一定约束条件下 (如货物需求量、发送量、车辆容量限制、交发货时间、行驶里程限制等) , 达到一定的目标 (如花费成本最小, 行驶距离最短, 消耗时间最少、使用车辆尽量小等) 。车辆路径问题示意图如下图1。车辆路径问题考虑约束条件和目标不同也分为很多种类, 本文对有时间窗限制的多目标车辆路径问题进行分析和建模, 并将遗传多目标优化算法应用其中, 期望达到最小化总运输时间和总延迟时间这两个目标。
2.2 问题分析与建模
2.2.1 带时间窗限制的多目标车辆路径问题
对于有时间窗限制的多目标车辆路径问题可以描述如下:配送中心拥有M辆车, 每辆车最大容量为q。一个配送中心为N个客户点 (i=1, 2 3, …, N) 配送货物, 每个客户点有自己对应的需求量和时间窗, 令配送中心的编号为0号节点, 各客户节点的编号为i (i=, 1, 2L, n) , 每个客户的需求量为gi (i=, 1, 2L, n) , g i
其中公式 (1) 表示第一个目标, 要使总行驶距离最短;公式 (2) 表示第二个目标, 要使分派的车辆数最少。
约束条件如下:
上述约束条件中, 式 (3) 表示一个客户点只有一辆车服务且安排给某车辆的运输量不超过最大容量;式 (4) 表示配送任务由m辆车完成并且每个客户的配送任务仅由一辆车完成。
再者或0, xijk=1或0确保到达客户的车必须离开该客户, 并在客户规定的时间内到达。
2.2.2 车辆路径问题的求解算法
根据实际情况和考虑问题的不同, VRP存在多种不同类型的问题。经过长期的研究, 车辆路径问题的求解算法有精确算法和启发式算法两大类。
1) 精确算法
目前的研究中, 精确算法主要有:网络流算法 (Network Flow Approach) 、割平面法 (Cutting Planes Approach) 、分支定界法 (Branch and Bound Approach) 、动态规划法 (Dynamic Programming Approach) 。精确算法随问题规模的增大求解复杂度增大, 导致应用受限。
2) 启发式算法
启发式算法不像精确算法要给出一个严格的方法求出最优解, 而是根据一些启发式的规则快速搜索, 因此在车辆路径问题求解中得到了广泛应用。
本文采用的是遗传多目标优化算法应用到车辆路径问题中, 主要利用遗传算法迭代搜索的全局搜索和局部优化相结合的特性, 在全局范围内搜索车辆路径的最优解。在寻优过程体现出了自然界中“适者生存、优胜劣汰”的自然法则, 给出计算规则, 直至迭代结束, 得到最优配送路线。遗传算法本身的特性如良好的鲁棒性、灵活性、通用性, 特别适合于大规模车辆路径问题的求解。
3 多目标遗传算法求解车辆路径问题
本文将带时间窗约束的车辆路径问题描述成多目标最优化问题, 针对最小化车辆数和最小化总行驶距离这两个目标同时进行优化。首先, 避免以往化双目标为单目标的优化方法带来的影响, 而是充分考虑两个目标的实际变化, 达到最终的优化结果。其次, 对于最优解不唯一的多目标优化问题, 避免以往只考虑单目标最小的峰值情况, 而是寻求所有多目标都能优化的结果, 进而做出更有利于决策者的方案, 真正将车辆路径问题视为一个多目标最优化问题。
本文将带时间窗约束车辆路径问题描述成一个多目标优化问题, 设计了基于Pareto优化的求解带时间窗的车辆路径问题的遗传多目标优化算法。
3.1 染色体编码及种群初始化方法
通过遗传多目标优化算法解决车辆路径问题, 首先为遗传算法操作准备一个由若干初始解组成的初始群体。种群初始化的方法跟染色体的编码方式有着密切的关系, 因此编码方式是基础和关键。大多数遗传算法的设计都需要以实际问题的描述方法作为基础。一般来说, 编码方法需要考虑个体的合法性、可行性、有效性以及需要完全覆盖问题解空间, 同时解码过程也决定了个体是否合法和可行。
本文采用自然数进行染色体的编码。在自然数编码方案中, 采用自然数串编码机制, 染色体中每一个基因代表一个客户点, 基因之间的先后顺序表示对每个客户的服务的先后顺序。其中每个染色体由区间[1, l]中互不相同的自然数序列构成, l代表客户点数。例如有5个客户按照自然数编码方案, 生成的染色体为P (5 3 1 2 4) 。我们采用随机生成的方法产生染色体, 并通过判断染色体的有效性加快优化解的搜索速度。
对于带时间窗约束的车辆路径问题避免通俗种群初始化方法产生大量不合法解, 本文引入前向插入启发式算法用于构造初始路径的算法, 在其基础上进行一定的改进进行车辆路径问题的种群初始化。
本文提出的解决方案使用的路径初始化方式是采用随机指定的任意一个客户x, 且xÎ1{, , 2LN}, 使用最佳客户插入原则确定该路径的其它客户, 则随后插入的客户可以由客户x惟一确定, 其它路径依次类推, 直至全部客户被插入。不仅满足了多目标遗传算法初始化种群的需要, 而且可以有效的提高初始化种群的多样性, 避免早熟收敛。
3.2 评价适应度函数和遗传算子
适应度函数是衡量染色体优劣的评判标准, 本文采用的带时间窗约束的车辆路径问题是总行驶距离和车辆数这两个目标, 适应度函数就是总行驶距离最短和分派的车辆数最少的两个函数。
遗传算子包括选择算子, 交叉算子和变异算子。本文提出了一种新的Pareto锦标赛选择算子, 不是用设置权重来选择新的子代, 而是用适应度函数解向量来选择, 4.3节会具体给出构造非支配个体的擂台法。对选择的种群按照一定的概率进行交叉, 对基于路径表示的部分匹配交叉算子。变异操作使遗传算法不容易陷入局部最优, 包括逆转变异、插入变异、易位变异。
3.3 改进的擂台法则
用擂台法则 (arena’s principle, AP) 来构造进化群体的非支配解集时, 每次搜索新的非支配个体不需要与已有的非支配个体进行比较, 在每一轮比较过程中从构造集中选出一个个体出任擂主 (一般为当前构造集的第一个个体) , 由擂主与构造集中的其它个体进行比较, 败者被淘汰出局, 胜者成为新的擂主, 并继续该论比较;一轮比较后, 最后的擂主个体即为非支配个体。本文给出改进的AP算法如下:
显然本文改进后AP算法比原算法更加简洁、效率更高。
4 带时间窗约束的车辆路径问题的仿真实验
4.1 测试实例和运行环境
本文采用带时间窗约束的车辆路径问题的Solomon标准测试集, Solomon标准测试集包括3种规模, 分别是25、50、100个客户, 每种问题的规模优包含有56个问题, 56个问题又可以分为六类:C1、C2、R1、R2、RC1和RC2。本文主要针对100个客户的大规模Solomon测试实例进行仿真计算与分析。
用MATLAB编写程序, 测试环境为Microsoft Windows XP操作系统, CPU P4-3.0G, 内存为2G。
4.2 仿真实验
采用100个客户的R103测试实例, 设置参数为交叉概率为0.9, 变异概率为0.1。用例已知最优解:车辆数为13, 距离为1292.68km。通过仿真计算, 设定参数:种群大小:100, 迭代次数:1000, 结果见下表1。
从表1可以看出, 配送车辆数为15, 行驶距离最小值为1250.9km, 优于用例已知最优解距离1292.68km。相应的车辆路径调度方案如下:
配送路径1:[0 92 98 14 44 38 86 16 61 85 91 100 37 0]
配送路径2:[0 94 96 99 6 0]
配送路径3:[0 36 64 49 19 47 46 48 0]
配送路径4:[0 52 82 7 88 8 83 60 93 59 0]
配送路径5:[0 42 43 15 57 41 74 72 73 21 58 0]
配送路径6:[0 31 62 11 63 10 90 32 70 0]
配送路径7:[0 95 97 87 13 0]
配送路径8:[0 18 45 84 17 5 89 0]
配送路径9:[0 27 69 30 66 20 1 0]
配送路径10:[0 39 23 67 55 25 54 0]
配送路径11:[0 51 65 71 9 35 34 81 0]
配送路径12:[0 50 33 78 3 77 0]
配送路径13:[0 40 53 0]
配送路径14:[0 28 76 79 29 24 68 80 12 0]
配送路径15:[0 2 22 75 56 4 26 0]
因此, 本文提出的求解带时间窗约束车辆路径问题的遗传多目标优化算法能有效地求得Solomon标准测试集中的问题。
5 总结
本文描述了带时间窗约束的车辆路径问题的数学模型。针对这两个车辆路径问题的总行驶距离和车辆数这两个目标, 设计了用遗传多目标优化算法进行优化。在原擂台基础上, 提出了新的Pareto锦标赛选择算子。通过测试问题模拟仿真得到多个非支配解供决策者选择, 对实际应用有很好的指导意义。
参考文献
[1]牟旭东.物流:第三利润源泉[M].上海远东出版社, 2002.6.
[2]陈国良, 王煦法, 庄镇泉等.遗传算法及其应用[M].人民邮电出版社, 1996.
[3]张铃, 张钹.遗传算法机理的研究[J].软件学报, 2000, 11 (7) :945-952.
[4]刘敏, 郑金华, 蒋浩.基于多目标遗传算法求解时间窗车辆路径问题[J].计算机工程与应用, 2006 (9) :186-189.
多目标遗传算法 篇2
改进的多目标遗传算法在无人机机翼结构优化中的应用
现有的多目标遗传算法往往只能求得整个非劣曲线的一部分,同时局部搜索能力差,收敛速度较慢.为了解决这些问题,提出了一种改进算法,该算法将非劣分层遗传算法(NSGA)与向量评估遗传算法(VEGA)的优点结合起来,并且提供了一个利用往代信息构造搜索方向的局部搜索算子,有效扩展了非劣曲线的范围,加快了收敛速度.以某无人机机翼结构的`多目标优化问题为例,证明本文改进算法可以较为快速地获得一个分布均匀的非劣解集.
作 者：苟仲秋 宋笔锋 李为吉 GOU Zhong-qiu SONG Bi-feng LI Wei-ji 作者单位：西北工业大学,航空学院,陕西,西安,710072刊 名：空军工程大学学报(自然科学版) ISTIC PKU英文刊名：JOURNAL OF AIR FORCE ENGINEERING UNIVERSITY (NATURAL SCIENCE EDITION)年，卷(期)：7(3)分类号：V214.19关键词：多目标优化 遗传算法 结构优化
双目标瓶颈指派问题的遗传算法 篇3
关键词 双目标； 瓶颈指派问题； 遗传算法； Pareto最优解
中图分类号 O221.6 文献标识码 A
1 引 言
经典指派问题是一类特殊的组合优化问题，是指将n项工作分配给n个工人去完成，且每个工人只能完成一项工作，每项工作只能由一个人来完成，不同的工人完成每一项工作的费用是不同的，从而求出最优指派. 所谓的最优是指使总体费用最大或者总体用时最小.
指派问题最早由Votaw和Orden提出[1]， 1955年，Kuhn给出了解指派问题的匈牙利算法[2]， 从此指派问题得到了真正的发展. 此后的几十年，指派问题的解法日趋成熟，出现了隐枚举法、分支定界法和割平面法等，但是用到最多的还是匈牙利法. 与此同时，还出现许多经典指派问题的变形，如瓶颈指派问题[3]、平衡指派问题[4]、半指派问题、多准则指派问题、分数指派问题、二次指派问题[5]、随机指派问题[6，7]、模糊指派问题[8]以及带负荷约束的指派问题[9]等，有关这些问题的介绍可参阅综述文章[10]及其参考文献.
指派问题在生产和服务系统中有着广泛的应用. 例如在咨询服务行业，决策者或者管理人员根据咨询师以往的工作表现和顾客反馈，可以给出不同咨询师完成某项工作的合适性，即费用. 经典指派问题的目标是要使这项费用最大化. 本文将在此基础上，同时考虑咨询师（工人）对工作的排名偏好，建立双目标瓶颈指派问题的模型，进而将此问题转化为单目标规划问题，并设计遗传算法来求解.
同样，模型（4）的最优解也是问题（2）的Pareto最优解. 问题（2）到模型（4）的转化方式也是处理多目标优化的常用方法.模型（3）与模型（4）相比其优势在于约束条件相较于问题（2）没有增加，问题的规模没有增大，利用我们给出的编码、交叉和变异算子可以保证个体的可行性.
参考文献
[1] DF VOTAW， A ORDEN. The personnel assignment problem[C]//Symposium on Linear Inequalities and Programming. Scoop 10， US Air Force， 1952： 155-163.
[2] H W KUHN. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly， 1955， 2（1/2）： 83-97.
[3] J GORSKI， K KLAMROTH， S RUZIKA. Generalized multiple objective bottleneck problems[J]. Operations Research Letters， 2012， 40（4）： 276-281.
[4] L LIU， H MU， Y SONG， et al. The equilibrium generalized assignment problem and genetic algorithm[J]. Applied Mathematics and Computation， 2012， 218（11）： 6526–6535.
[5] A A PESSOA， PM HAHN， M GUIGNARD， et al. Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization technique[J]. European Journal of Operational Research， 2010， 206（1）： 54-63.
[6] PA KROKHMAL， PM PARDALOS. Random assignment problems[J]. European Journal of Operational Research， 2009， 194（1）： 1-17.
[7] F LI， LD XU， C JIN， et al. Random assignment method based on genetic algorithms and its application in resource allocation[J]. Expert Systems with Applications， 2012， 39（15）： 12213-12219.
[8] PN TAPKAN， LZBAKIR， A BAYKASOGLU. Solving fuzzy multiple objective generalized assignment problems directly via bees algorithm and fuzzy ranking[J]. Expert Systems with Applications， 2013， 40（3）： 892-898.
[9] 林浩，林澜. 有负荷约束的指派问题[J]. 经济数学，2013，30（1）： 17-21.
[10]D W PENTICO. Assignment problem： A golden anniversary survey[J]. European Journal of Operational Research， 2007， 176（2）： 774-793.
[11]葛悦. 模糊环境下若干网络优化问题的模型及其算法研究[D]. 哈尔滨：哈尔滨工业大学理学院数学系， 2012.
[12]D Z DU， P M PARDALOS. Minmax and Applications[M]. Netherland： Kluwer Academic Publishers， 1995.
[13]I H TOROSLU， Y ARSLANOGLU. Genetic algorithm for the personnel assignment problem with multiple objectives[J]. Information Sciences， 2007， 177（3）： 787–803.
[14]S Y LIN， S J HORNG， T W KAO， et al. Solving the bi-objective personnel assignment problem using particle swarm optimization[J]. Applied Soft Computing， 2012， 12（9）： 2840-2845.
[15]A ZINFLOU， C GAGNE， M GRAVEL. GISMOO： A new hybrid genetic/immune strategy for multiple-objective optimization[J]. Computers & Operations Research， 2012，39（9）： 1951-1968.
多目标遗传算法 篇4
多目标最优化是一门迅速发展起来的学科,是最优化的一个重要分支,它主要研究在某种意义下多个数值目标的同时最优化问题[1],吸引了不少学者的关注。在现实生活中,人类改造自然的方案规划与设计过程在总体上都反映了“最大化效益,最小化成本”这一基本优化原则,在合作对策问题中如何求解最优策略以获得共赢目标,在非合作对策问题中如何使自己的利益实现最大化,使对方的受益最小化,以及控制工程中的稳、准、快等时域指标与稳定域度、系统带宽等频域特性的综合问题等,实际上都是多目标的优化问题,因此多目标优化问题在现实世界中随处可见。
多目标优化是最优化领域的一个重要的研究方向,因为科学研究和工程实践中许多优化问题都可归结为一个多目标优化问题。多目标优化问题起源于许多实际复杂系统的设计、建模和规划。这些系统所在的领域包括工业制造、城市运输、资本预算、水库管理、能量分配、后勤补给、网络通信等等,可以说多目标优化问题无处不有、无处不在。
2 多目标优化模型
多目标优化问题(Muliti-objective Optimization Problem,MOP),又称多准则优化问题(Multicriteria Optimization Problem),多性能优化问题(Multi-performance Optimization Problem)或向量优化问题(Vector Optimization Problem)。
一般的多目标优化问题(MOP)由一组目标函数和相关的一些约束组成,可作如下数学描述:
其中X=(X1,X2,…,Xn)T是Rn空间的n维向量,称X所在的空间D为问题的决策空间,fi(X)(i=1,2,…,m)为问题子目标函数,它们之间是相互冲突的,即不埚X∈Ω使(f1(X),f2(X),…,fm(X))在X处同时取最小值,m维向量(f1(X),f2(X),…,fm(X))所在的空间称为问题的目标空间,gi(X)≤0(i=1,2,…,p)为约束函数。
多目标优化问题的本质是在很多情况下,各个子目标可能是相互冲突的,一个子目标的改善有可能引起另一个子目标性能的降低,也就是说,要使多个子目标同时达到最优是不可能的,而且只能在他们中间进行协调和折中处理,使各个子目标函数尽可能达到最优。法国经济学家V.Pareto(1848-1923)最早研究了经济学领域内的多目标优化问题,提出了Pareto解集。多目标优化问题的Pareto最优解仅仅是一个可以接受的“不坏”的解,并且通常一个多目标问题大多会具有很多个Pareto最优解。在实际应用问题中,必须根据对问题的了解程度和决策人员的个人偏好,从Pareto最优解集合中挑选一个或一些解作为多目标优化问题的最优解。所以,求解多目标优化问题的首要步骤和关键问题就是求解多目标优化问题的所有最优解。
3 传统的优化方法
绝大多数传统的多目标优化方法是将多个目标通过某种技术转换为一个目标的优化问题,然后再借助数学规划工具来求解。常见的传统优化方法有:
(1)加权求和法(Weighted Sum Method)
这种方法由Zadeh首先提出,该方法就是将多目标优化中的各个目标函数加权(即乘以一个用户自定义的权值)然后求和,将其转换为单目标优化问题进行求解。
利用加权求和可以将多目标优化转化为以下形式:
通过选取不同的权重组合,可以获得不同的Pareto最优解。这也是最为简单有效的一种求解多目标优化问题的经典方法,而且对与Pareto最优前端为凸的多目标优化问题,这种方法可以保证获得Pareto最优解。但其缺点也很明显,权重的选取与各个目标的相对重要程度有很大关系。此外,在搜索空间非凸时,很难在Pareto最优前端的非凸部分上求得解。
(2)ε-约束法(ε-Constraint Method)
ε-约束法是由Marglin[2]和Haimes[3]等人于1971年提出的,其原理是将某个目标函数作为优化目标,而约束其他目标函数的方法来求解多目标优化问题,模型如下:
εi作为上界可在优化过程中取不同的值,以便搜索到多个Pareto最优解,记Xf为可行解集合。通过这种方式将多目标优化问题转换为单目标优化问题,然后通过一般的数学规划方法或者模拟退火等方法进行求解。
(3)最小-最大法(Min-Max Approach)
最小最大法起源于博弈论法,是为求解有冲突的目标函数而设计的。这种方法的线性模型由Jutler和Solich提出[4],后由Osyczka和Rao进一步发展[5],是通过最小化各个目标函数值与预设目标值之间的最大偏移量来寻求问题的最优解。
4 多目标遗传算法
遗传算法GA(Genetic Algorithm)是受生物学进化学说和遗传学理论的启发而发展起来的,是一类模拟自然生物进化过程与机制求解问题的自组织与自适应的人工智能技术,是一种借鉴生物界自然选择和自然遗传机制的随机的搜索算法,由Holland教授于1975年提出[6]。Goldberg总结了一种统一的最基本的遗传算法,称为基本遗传算法(Simple Genetic Algorithms,SGA)。只使用基本的遗传算子:选择算子、交叉算子和变异算子。其遗传进化过程简单,容易理解,是其他遗传算法的雏形和基础。
常用的几种多目标遗传算法:
(1)并列选择法
Schaffer提出的“向量评估多目标遗传算法”是一种非Pareto方法。此方法先将种群中全部个体按子目标函数的数目均等分成若干个子种群,对各子群体分配一个子目标函数,各子目标函数在其相应的子群体中独立进行选择操作后,再组成一新的子种群,将所有生成的子种群合并成完整群体再进行交叉和变异操作,如此循环,最终求得问题的Pareto最优解。
(2)非劣分层遗传算法(NSGA)
Srinivas和Deb于1994年提出的非劣分层遗传算法(Non-dominated Sorting Genetic Algorithm)也是一种基于Pareto最优概念的多目标演化算法。首先,找出当代种群中的非劣解并分配最高序号(如零级),赋给该层非劣解集与当前种群规模成比例的总体适应值。为了保持解的多样性,所有该层非劣解基于决策向量空间距离共享此总体适应值。此后,该层非劣解集将不予考虑。然后,开始下一层非劣解集的搜索,在该层得到的非劣解集称为第二层,分配排列序号(如一级),并赋给与该层种群规模(除去以上各层已被赋予适应度的非劣解)成比例的总体适应值,同样,必须在该层非劣解集中实行适应值共享。如此重复直到当前种群中最后一个个体被赋予适应度值。
在前面的研究基础上,Deb等人于2002年又提出了一种非劣分层选择法2(NSGA-II)[7],这种方法的主要思想是对种群中的个体按Pareto进行排序,按照序值从小到大选择个体,若某些个体具有相同的序值,则偏好于那些位于目标空间中稀疏区域的个体。
(3)基于目标加权法的遗传算法
其基本思想是给问题中的每一个目标向量一个权重,将多有目标分量乘上各自相应的权重系数后再加和,合起来构成一个新的目标函数,将其转化成一个单目标优化方法求解。
若以这个线性加权和作为多目标优化问题的评价函数,则多目标优化问题可以转化为单目标优化问题。权重系数变化方法是在这个评价函数的基础上,对每个个体去不同的权重系数,就可以利用通常的遗传算法来求解多目标优化问题的多个pareto最优解。
(4)多目标粒子群算法(MOPSO)
粒子群优化算法(Particle Swarm Optimization,PSO)是一种进化计算技术,由美国学者Eberhart和kennedy于1995年提出,但直到2002年它才被逐渐应用到多目标优化问题中。PSO初始化为一随机粒子种群,然后随着迭代演化逐步找到最优解。在每次迭代中,粒子通过跟踪两个“极值”来更新自己,一个是粒子本身所找到的个体极值p Best,另一个是该粒子所属邻居范围内所有粒子找出的全局极值q Best。MOPSO与求解单目标的PSO相比,唯一的区别就是不能直接确定全局极值q Best,按照pareto支配关系从该粒子的当前位置和历史最优位置中选取较优者作为当前个体极值,若无支配关系,则从两者中随机选取一个。
(5)微遗传算法(Micro-Genetic Algorithm,Micro-GA)
Micro-GA是由Coello和Toscano Pulido于2001年提出的,是一种包含小的种群和重新初始化过程的遗传算法GA,其过程如下:首先,产生随机的种群,并注入种群内存,种群内存分为可替代和不可替代两部分。不可替代部分在整个运行过程中保持不变,提供算法所需要的多样性;可替代部分则随算法的运行而变化。在每一轮运行开始,Micro-GA的种群从种群内存的两部分选择个体,包含随机生成的个体(不可替代部分)和进化个体(可替代部分);Micro-GA使用传统的遗传操作;其后,从最终的种群选择两个非劣向量,与外部种群中的向量比较,若与外部种群的向量比较,任何一个都保持非劣,则将其注入外部种群,并从外部种群中删除所有被它支配的个体。
5 传统方法和遗传算法比较
尽管遗传算法的理论基础还不尽完善,但遗传算法已经很广泛的应用于多目标问题的求解上,并且取得了不错的效果。相比其他算法,遗传算法具有适应性和通用性、隐并行性、扩展性这三个独特的特点。但是它还是不能很好的解释遗传算法的早熟问题和欺骗问题,缺少完整的收敛性证明等。理论研究比较滞后,参数设置比较困难,解决约束优化问题还缺乏有效的手段,易早熟,而且计算量相对于传统方法要大的多,即使是使用遗传算法解决多目标优化问题,目前的多目标进化算法能有效的求解的目标数一般不超过4个。
与遗传算法相比较，传统算法在处理多目标优 化问题上，也具有其特有的优势。相对遗传算法来 说，传统算法的计算量小、计算速度快、设计简单、 容易理解，方便建立数学模型，并且传统方法有充分的理论支持。因此虽然遗传算法在解决多目标 优化问题上取得了很多成效，但这并不意味着传 统方法不及遗传算法有效，会被多目标遗传算法 取代。相反，传统算法在解决一些问题上仍然具有 很大的优势，比如计算速度快，易实现。所以我们 在求解多目标问题中，如果能结合遗传算法和传 统方法间的优点，效果将会越来越好。
6 结束语
在工程实践中和科学领域中存在着很多复杂的多目标优化问题。在单目标优化问题中,最优解就是一个且已经具有了明确的概念,但对于多目标优化问题,不同于单目标优化,多目标优化处理的是一些相互冲突、相互制约的目标,其解集也不是单一的一个解,而是一组最优解的集合。传统的数学规划原理在多目标优化的实际应用中虽然不太适用,但其也有自己的优点,而且就对于现在的多目标遗传算法也并不是很完善的,需要解决的问题也很多。因此,有必要进一步研究求解多目标优化问题的更多高效算法,结合两者的优点,使处理多目标问题的效果越来越好。
摘要：多目标优化是最优化领域的一个重要的研究方向。论述了多目标优化模型,同时介绍了常用的几种传统优化方法和常用的几种多目标遗传算法,对改进后的遗传算法与传统优化方法求解效果进行了比较,认为要进一步研究求解多目标优化问题的更多高效算法,若能结合两者的优点,处理多目标问题的效果将越来越好。
关键词：多目标优化,传统优化方法,遗传算法
参考文献
[1]林锉云,董家礼.多目标优化的方法与理论[M].吉林:吉林教育出版社,1992.
[2]Marglin S.Public Investment Criteria.MIT Press,Cambridge[M].Massachusetts:1967.
[3]Y.Haimes.Integrated system identification and optimization[J].control and Dynamic System:Advances in Theory andApplication,1973,10:435-518.
[4]Osyczka A.Multicriterion optimization in engineering withFORTRAN programs[J].Ellis Horwood LIMITED.1984.
[5]Tseng C H and Lu T W.Mini-max multi-objectiveoptimization in structural design[J].International Journal forNumerical Methods in Engineering.1990,30:1213-1228.
[6]Holland J H.Adaptation in naturation in naturalandartificial systems[J].The Uniuversityof Michigan Press,1975(1):21-24.
多目标遗传算法 篇5
空中目标识别是现代防空作战的重要研究内容.本文利用不同类型目标产生的`多类型传感器的数据信息对目标进行识别.为了训练神经网络目标识别分类器,将遗传算法和BP算法相结合,提出了一种新的自适应遗传BP算法,利用这种神经网络来确定指标的权值.仿真试验结果表明,基于自适应遗传BP算法神经网络的识别是一种简单、可靠的目标识别方法,具有很好的目标识别效果.
作 者：马峰 李富荣 张安 MA Feng LI Fu-rong ZHANG An 作者单位：马峰,MA Feng(西北工业大学电子信息学院・陕西西安・710072;92635部队・山东青岛・266041)
李富荣,LI Fu-rong(海军航空工程学院青岛分院・山东青岛・266041)
张安,ZHANG An(西北工业大学电子信息学院・陕西西安・710072)
多目标遗传算法 篇6
摘要：针对目前企业配电网节能技术的不足，提出了一种基于多智能体遗传算法的配电网节能降耗综合管理系统。结合遗传算法（Genetic algorithm，GA）和多智能体系统（Multi-Agentsystem，MAS）技术构造了一种GA-MAS算法，每一个多智能体相当于遗传算法中一个个体，相邻的多智能体相互作用，并结合遗传算法的进化机理进行全局最优求解。提出了该系统各节能设备智能体结构模型和高压/低压多智能体系结构模型，运用GA_MAS算法，得出各个节能设备的最佳调节力度，使节能设备以最小的调节代价获得最大的节能效益。具体算例仿真及工程实际应用表明本文提出的配电网节能降耗综合管理系统能使总有功网损降低，电容器投入总组数减少，实现节能设备的最佳调节，同时表明GA_MAs算法收敛速度较快。
关键词：综合管理系统；节能降耗；节能设备多智能体；遗传算法
中图分类号：TM92 文献标识码：A
节能已成为我国经济和社会发展的一项长远战略方针，节电则是国家节能战略的重要组成部分。纵观目前企业配电网节能技术，存在以下不足：1）整个配电网缺乏全局的规划与管理手段，能量管理水平不高，没有形成“全方位、多方面”的综合节能降耗。2）企业配电网只是进行了局部优化管理，具有很大的局限性。3）企业配电网的节能设备还是单一运行的，形成“孤岛”林立的局面，信息比较分散，集成度不高，不便于高层管理和控制。4）单一独立节点节能设备之间相互影响，一旦局部调节过度或不足会造成临近线路的故障，形成“要害区域”。5）单一节能设备只具备某一方面的节能职能，不能满足社会对全方面节能的需要。且节能设备的独立控制容易导致设备调节过于频繁，设备使用寿命缩短，维护成本增加。
智能体（Agent）是一种具有感知能力、问题求解能力和与外界通信能力的实体。多智能体系统（Multi-Agent System，MAS）由多个松散耦合的、粗粒度的、具有感知能力、问题求解能力、能够与系统中其他智能体通信的智能体组成的网络结构。MAS在兼顾单个智能体系统优点的同时，通过协商、协调和协作，完成复杂的控制任务或解决复杂的问题。
遗传算法（GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化算法。本文结合GA和MAS技术构造了多智能体遗传优化算法（GA-MAS），该算法利用Agent的局部感知、竞争协同和自学习等特性来实现生物对环境的自适应。由于所有操作都作用于局部种群而不是整个种群，从而维持了群体的多样性，在一定程度上抑制了遗传算法的早熟现象。
针对上述现有技术的不足及其存在的缺陷，结合GA和MAS技术，提出了一种基于多智能体遗传优化算法（GA-MAS）的配电网节能降耗综合管理系统。给出了管理系统的基本结构模型和节能设备多智能体的结构模型，运用GA-MAS算法，得出各个节能设备的最佳调节力度，使节能设备以最小的调节代价获得最大的节能效益。通过具体算例仿真及工程实际应用表明本文提出的管理系统能使总有功网损降低，电容器投人总组数减小，同时表明GA-MAS算法有很好的计算效率及收敛稳定性。
1 无功优化模型
在实际工程应用中，无功补偿装置必然会产生有功损耗及运行维护费用，另外，当配电网无功资源不足时，需要增加无功补偿设备，产生额外投资。因而，系统在追求有功网损最小的同时，综合考虑无功补偿装置总投入最小建立目标函数：其中，N为系统节点数，n为加装无功补偿装置的节点数，QCi为节点i上无功补偿容量，△PC为每kVar无功补偿容量的有功损耗，C为上网电价，丁为年运行小时数，K1为电容器年运行维护费用，△P为系统有功损耗，t为每年最大负荷运行时间。Vi，Vj分别指节点i，j的电压幅值，Gij，Bij分别指网络导纳矩阵的互导纳元素（互电导、互电纳），θij指节点电压相位差。其中，△u为控制变量的变化量；m为补偿装置种类数，即cui为第i种装置调节代价。以变压器为例，成本为Acost元，允许抽头总调节次数为Tn次，抽头永远不调整时的预期寿命是a年，经过Tn次的抽头调整后寿命缩短到a'年，调整设备所增加的运行维护工作量为B，则该变压器的抽头每次操作的调节代价（元/次）为：
cu11=B+（a-a'）Acost/aTn。 （4）
由式（4）可类似地计算无功补偿装置投切开关的调节代价。
Vi为节点i电压，QCiSVC，QCiHAPF，QCiIVC，QCiDSTATCOM分别为SVC，HAPF，IVC，DSTATCOM的无功补偿容量，Ti为有载调压变压器分接头档位，QCi为发电机无功出力。
2 多智能体遗传优化算法（GA-MAS）
2.1 Agent的环境
多智能体遗传优化算法是结合GA算法和MAS的主要特征构造的一种算法。首先构造Agent的生存环境，每个Agent与其邻域相互作用，并结合GA算法的进化机制，使其能快速、准确地收敛到全局最优解。
将任意一个Agenta相当于GA算法中一个体，其适应值为：
f（α）=FQ。 （9）
Agenta的目的就是在满足运行条件的限制下尽可能减小其适应值。
所有的Agent都被放人一个生存环境，即一个L×L的网格，其中L=根号下N，N为群体中个体数。如图1所示，每个Agent都“居住”在该环境里，并且被固定在一个格子中。每个Agent都有其生存周期和自学习能力，能感知其邻域中的个体，并根据感知到的信息自主采取行动策略来完成其意图和目的。每个Agent和其邻域的个体组成了该Agent的局部环境，如图1所示，虚线框构成了Agent2，2的局部环境。每个Agent只和邻域内其他智能体交配产生新个体，具有一定局部性，而它邻域内其他个体又和自身邻域个体交配，由于邻域的重叠性，因而所有个体间均存在信息交换，又具有一定的全局性，可以维持群体的多样性。
2.2 GA-MAS算法流程
GA-MAS算法流程图如图2所示。
1）Pareto择优操作
每个Agent根据其局部环境与其邻域个体两两比较寻找最优解。在任意一个智能体的局部环境中，若该个体优于周围其他个体，则该个体为其邻域中的Pareto最优解。由于是在每个个体的局部环境中进行择优操作，而不是作用于整个群体，因而保证了群体的多样性。
2）交配操作其中，rand是[0，1]中的一个随机数。Pareto择优操作后得到的种群以交叉概率pc按式（12）（13）进行交叉。交叉后得到的子代个体与其父代进行优劣比较，若子代优于父代，则保留子代，否则，继续保留父代。
3）死亡和再生操作
智能体A1，A2，如果两点的距离d（A1，A2）
3 基于GA-MAS的配电网节能降耗综合管理系统
3.1 系统结构
依据多智能体分层分布式系统理论，基于多智能体的配电网节能降耗综合管理系统结构图如图3所示，包括高压侧、低压侧两级多智能体和管理层。
高/低压侧各个智能体的交互和协调通过任务协调智能体完成，且任务协调智能体之间可相互通信；各个智能体通过任务分解智能体与管理层连接，使不同的智能体连通了相应的管理层的各个系统。管理层各系统通过智能体之间的通信和交互相互连接起来，实现了操作平台的互联、互操作和互协调。管理层各系统的数据可通过TCP/IP协议实现各数据库之间互访，达到数据共享与交换的目的。从而管理层各系统连通了高压侧多智能体和低压侧多智能体，实现了高低压侧智能体的交互和协作，进一步实现多层次节能降耗。
3.2 节能设备智能体结构模型
节能设备智能体是具有节能设备功能结构属性的智能体。图3中节能设备智能体构建过程如下：
第j个节能设备智能体结构属性为：
Shj={ghj，Msj，Mrj，Ncj，T1}。 （14）
式（14）中ghj为第j个节能设备智能体对其他节能设备智能体的信念度；Msj为第j个节能设备智能体的初始状态；Mrj为第j个节能设备智能体的目标状态；Ncj为第j个节能设备智能体的优先级指标；T1为定义时间间隔。
1）SVC智能体
第K个SVC智能体其初始状态MsSVCk和目标状态MrSVCk分别为：
式（15）中QSVCk为第K个SVC设备补偿无功；VSVCk为第K个SVC设备节点电压；iSVCk为第K个SVC设备输出电流；NSVCk为第K个SVC设备优先级；TSVCk为时间脉冲。
那么第K个SVC智能体结构属性为：
式（17）中IHAPFk为第K个HAPF设备补偿谐波电流；VHPAFk为第K个HAPF设备节点电压；iHAPFk为第K个HAPF设备输出电流；NHAPFk为第K个HAPF设备优先级；THAPFk为时间脉冲。
那么第K个HAPF智能体结构属性为：
3）IVC智能体
第K个IVC智能体其初始状态MsIVCk和目标状态MrIVCk分别为：
式（19）中QIVCk为第K个IVC设备补偿无功；VIVCk为第K个IVC设备节点电压；iIVCk为第K个IVC设备输出电流；NIVCk为第K个IVC设备优先级；TIVCk为时间脉冲。
那么第K个IVC智能体结构属性分别为：
4）DSTATCOM智能体
第K个DSTATCOM智能体其初始状态MsDCOMk和目标状态MrDCOMk为：
式（21）中IDCOMk为第K个DSTATCOM设备补偿无功；VDCOMk为第K个DSTATCOM设备节点电压；iDCOMk为第K个DSTATCOM设备输出电流；NDCOMk为第K个DSTATCOM设备优先级；TDCOMk为时间脉冲。
那么第K个DSTATCOM智能体结构属性为：
3.3 高压/低压多智能体系结构模型
在节能设备智能体基础上，构建的高压/低压多智能体系结构为：
HV/LVMSh={Sh1，Sh2，…，Shj，N，T} （23）
式（23）中sh1，…，Shj为图3中高/低压侧各个节能设备智能体；N为各个智能体的优先级信息表；T为时间脉冲。在实例中可具体表示为：
3.4 系统的管理方法
图4是基于多智能体遗传优化算法的配电网节能降耗综合管理系统的管理方法流程图。首先从系统获取实时数据，比较各节能设备智能体当前状态和目标状态。然后高压/低压多智能体汇总所有信息，运用GA-MAS优化算法制定优化方案，再通过任务协调与分解智能体，根据优先级别N确定哪些节能设备智能体参与任务，根据时间脉冲T确定节能设备什么时候响应任务，实现各个节能设备智能体之间的交互和协作，减小节能设备之间的相互影响。
4 仿真分析
为验证以上算法的正确性与可行性，在Delphi环境下应用Pascal语言编制程序，对IEEE-14节点系统进行计算分析。在本文选取的IEEE-14节点系统中，设节点数为14个、发电机数6个、变压器数4个、节能装置6套。变压器当成有载调压变压器，变压器变比调节范围在1±1.25%×8，共分为0～16共17档，并且限制变压器的一次调节档位±2档，其档位与实际变比的换算关系为：T=0.9+n×1.25%（n=0，1，…，16），发电机端电压上下限制为0.9～1.1pu，节点电压限制在0.95～1.05pu。计算过程中，有功功率基准值为100MW，无功功率基准值为100MVar。
表1和表2为基于GA-MAS优化算法与PSO优化算法的配网节能降耗比对结果，对于IEEE-14节点系统，利用优化算法求解高低压节能设备投入套数，总有功网损最小，同时满足节点电压约束，控制方案合理，达到节能设备优化运行效果。在节点电压控制、发电机有功出力和电压最大最小畸变率等方面，本文所提基于GA-MAS的配网节能降耗系统展现出了优异结果。相比于PSO优化算法，当GA-MAS优化算法实施后，总有功网损降低到0.135pu，而PSO优化算法高达0.138pu，节能设备投入总数减少2套。
图5为GA-MAS和PSO迭代曲线，其中实线表示的是GA-MAS迭代曲线，虚线表示的是PSO迭代曲线。从图中可以看出，GA-MAS算法的收敛精度和速度比PSO算法要好，在算法计算速度方面，经GA-MAS和PSO优化的时间分别为16.3s和34.5s，由此看出，GA-MAS的计算速度和收敛性明显优于PSO算法。
5 工程应用
某企业配电网拥有110kV变电站一座，自备热电厂一座，10kV配电变电站两座。其中，25000kVA容量110±8×1.25%有载调压变压器2台，110kV线路两回，分别从不同的变电站引人为厂区供电，6300kVA容量10±8×1.25%有载调压变压器4台，10kV馈线143回，6kV馈线256回，6300kVA发电机组2台，系统共接人各种高低压节能设备16套。本文所提出的基于多智能体遗传优化算法的配电网节能降耗管理系统，被成功应用于该企业配电网，产生的节能降耗效益如下：
1）减少了有载调压变压器分接头开关的动作次数。变压器分接头由本文所提系统投运前的每台每周3.87次降低到目前的每台每周2.08次，动作次数降低了46%，提高了设备的使用寿命，减轻了检修劳动强度。
2）提高了配电网进线端口功率因数，减少了节能设备投入套数。系统接人运行后，使配电网内总的无功补偿容量降低了33%，同时，功率因数由原来的0.92稳步提升至0.96。节能设备总计投入11套，总共减少了5套。
3）减少电能损耗，取得了明显的节能降耗效果。对配电网三个月网损率的统计分析表明，平均网损率为8.0%，比系统接人运行前同比降低了1.9个百分点，节能降耗效果显著。
4）提高了电压质量。图6（a）～（c）分别为110kV，10kV，6kV节点整点时刻电压曲线，从中可以看出，使用本文提出的配电网节能降耗综合系统，并经过系统优化后，各节点电压得到明显改善，其中110kV节点优化前最低电压为101.1kV，优化后最低电压为105.4kV；10kV节点优化前最低电压9.51kV，优化后最低电压为9.82kV；6kV节点优化前最低电压为5.69kV，优化后最低电压为5.91kV。据统计，系统接人运行的三个月内，地区电网6kV以上母线电压合格率为99.96%，同比提高了0.4个百分点。
6 结论
多目标遗传算法 篇7
针对上述问题, 该文采用Pareto多目标遗传算法来进行优化计算。该方法无需对优化的各个目标掌握先验知识, 并具有极强的鲁棒性、全局寻优能力和隐含的并行性等特点, 使得该方法成为多目标优化方法中的一个研究热点。
1 排课系统设计
课表的安排除了要考虑教学计划、教师资源以及教室使用情况, 同时还要以其他教学要求来评判课程安排的优劣, 如:
(1) 课程分布均匀, 避免课程都集中在某一两天的情况;
(2) 重要课程尽量安排在上午;
(3) 对于一周多节的课程要尽量保证同一门课程两节之间时间间隔较长。
该文设定一个班级一天排6节课, 上午排4节课, 下午排2节课, 即一周有30节课, 因此每一节上课时间的变量在整数区间 (1-30) 上取值。量化排课优劣程度的方法如下描述。
(1) 为了使重要课程尽量安排在上午, 首先将每一节课的值进行修正:一周有n节课时, 按先后顺序记课的值分别为1, 2, …, n。其中, 式中, 若该节无课, 则当前值设为0。假设排课结果为x1, x2, …, xn, 评价函数f1 (X) 如式 (1) 所示:
由式 (1) 可以看出, 当f1 (X) 的值越小时, 课程就越集中在上午。
(2) 为使课程安排均匀, 需统计一周每天安排的课程数目, 并求这5天课程数目的方差f2 (X) 。那么, 方差f2 (X) 越小则排课越均匀。
(3) 对于每周要安排多节的课程, 要使同一门课程两节之间间隔的时间尽可能长, 则计算同一门课 (每周需要安排多节的课程) 两次值的相差绝对值。那么, 一周内所有课的相差绝对值之和f3 (X) 越大, 则课程安排越合理。
2 多目标遗传算法优化
传统多目标优化方法是将多目标优化问题转化为单目标优化问题。如线性加权法, 将上述三个目标函数f1 (X) , f2 (X) , f3 (X) 按其重要程度给出一组权系数w1, w2, w3, 则评价函数的最优解如式 (2) 所示:
但该方法要求对优化问题掌握先验知识时。而该文采用Pareto多目标遗传算法来进行优化计算, 无需掌握先验知识。
Pareto占优定义如下:假设x1, x2∈某一可行域Ω, x1被x2占优是指对部分i, 有fi (X) ≥fj (X) , 而对其他的j≠i, fi (X) >fj (X) 。Pareto最优解x0是指在Ω中不存在任何x占优于x0。
从定义中可知, Pareto最优解不是唯一的, 而是由许多“非劣解” (非劣解, 是指在不降低其它性能指标的前提下, 再也不能提高该性能指标) 组成的解集, 因此群体搜索策略 (如遗传算法) 是非常合适的求解方法。
遗传算法是通过对一代群体按照寻优目标进行一系列的选种、交叉、变异而使下一代群体从整体上更接近最优解[3]。该文将选择算子中引入Pareto占优概念, 即Pareto遗传算法。
该文Pareto遗传算法操作流程如表1所示。
相比较以往传统遗传算法, 该文算法改进措施如下。
(1) 根据种群中占优的个数多少来赋予个体相应适应度。
(2) 在每代中采用部分种群来决定占优的情况。而且, 当两个个体之间彼此互不占优的时候, 其结果通过适应度共享来决定。由于该文没有在整个种群中使用Pareto意义选种, 而是在每代中只采用部分种群, 因此其能快速并产生较好的Pareto意义占优解。
(3) 相比较传统遗传算法, 该文算法还引入小生境技术[4,5]。该技术可以防止基因漂移, 使群体均匀分布在Pareto最优解集中。由于一周有5天课程, 该文将个体划分为5类, 即从这5个类当中选出适应度较大的个体作为该类的代表组群。
3 实验结果及分析
假设需为某班排课, 共6门课程, 英语、语文、数学等。其中英语、语文、数学每周需要安排6节, 其他课程每周安排2节。
首先通过随机方法生成30次排课解作为初始群体, 以上述f1 (X) , f2 (X) , f3 (X) 的极值作为优化目标。根据遗传算法进行优化计算, 设突变率为1%, 经过100代进化, 结果如表1所示。
由表1可以看出, 尽管实验没有提供对优化目标的先验知识, 但通过Pareto遗传算法优化后, 3个优化目标f1 (X) , f2 (X) , f3 (X) 都得到同时优化, 并且优化结果比较理想。
4 结语
该文针对传统多目标优化排课算法需要先验知识的缺点, 将Pareto多目标遗传算法应用到排课系统中, 并实验证明该方法的有效性。
摘要：中小学课表编排要考虑时间、空间和人员安排问题等多个目标的同时优化问题。传统方法是将多目标优化问题的多个目标函数通过适当方法 (如加权法等) 转化为单目标优化问题进行处理。该方法的缺点需要对优化问题掌握一定的先验知识, 否则难以确定加权系数。针对传统多目标算法需要对目标掌握先验知识的缺点, 该文提出一种基于Pareto多目标遗传算法的排课算法, 并实验证明该方法的有效性。
关键词：遗传算法,Pareto,多目标,排课
参考文献
[1]Tan K C, Lee T H, Khoo D, and et al.A multi-objective evolutionary algorithm toolbox for computer-aided multi-objective optimization[J].IEEE Transactions on Systems, Man and Cybernetics:Part B (Cybernetics) , 2001, 31 (4) :537-556.
[2]Vieira D A G, Adriano R, Vasconcelos J A, and et al.Treating constraints as objectives in multiobjective optimization problems using niched Pareto genetic algorithm[J].IEEE Transactions on Magnetics, 2004, 40 (2) :1188-1191.
[3]陆金桂.遗传算法原理及其工程应用[M].徐州:中国矿业大学出版社, 1997:40-52.
[4]乔佩利, 郑林, 马丽丽.一种小生境遗传算法研究[J].哈尔滨理工大学学报, 2011, 16 (1) :90-93.
多目标遗传算法 篇8
随着游戏产业的快速发展, 对游戏质量的要求逐步上升, 玩家希望看到趣味性足、挑战性强的高质量游戏。为了提高游戏质量, 大量游戏引入了非玩家控制角色[1] (NPC) 与玩家进行交互, 以提高游戏的可玩性和真实性。因此, NPC的行为研究成为游戏设计者关心的重要因素。而在游戏中, NPC的行为除与玩家交互外, 主要就是自主寻路, 其所选路径的质量决定其自身的智能性和游戏的真实性。
对于游戏NPC智能路径规划的研究, 提出过许多方法, 主要有A*算法及其改进算法[2，3]、遗传算法[4]、蚁群算法[5]和神经网络方法[6]等。但在实际应用中, 游戏设计者普遍选择A*算法, 这是由其较高的正确率和较好的实时性决定的。但是, 随着游戏地图[7]的多样化, 仅仅用路径长短去评估路径质量是不够的, 游戏地图中通常还需要考虑路径的安全性、路径的耗费等多个方面。在此情况下, A*算法就变得不适用, 由此诞生了许多不同的方法。 其中, 孙纯哲提出了双蚁群交叉算法[8], 但该方法未考虑连续障碍物, 实时性差。此外, Xiao J, Z.Michalewicz[9]提出了线性加权的改进A*算法, 其只是将多个目标进行简单加权相加, 得到启发函数, 故该方法存在主观性和随意性。针对以上情况, 本文提出了一种多目标遗传算法的路径规划方法。
本文为游戏中的NPC寻路, 提出了一种多目标智能路径规划算法, 并将其与传统寻路算法进行对比, 突出其在游戏中智能自动寻路的优点。本文使用基于多目标的遗传算法优化路径, 同时引入帕累托最优解集[10]作为寻路结果, 在综合考虑多个寻路目标平衡的基础上, 获得满足条件的最优解集。最后, 从解集中, 筛选满足游戏情景的最优路径选择。
1多目标路径规划遗传算法
游戏中的非玩家控制角色需要智能路径规划算法, 为其提供最优行动路线, 让其看上去更具智能性。然而, 每种智能路径规划算法都存在局限性, 不存在一种智能路径规划算法适用所有游戏。然而, 目前的计算机游戏种类众多, 这导致游戏地图的多样性和复杂度较高, 直接在游戏地图上测试寻路算法难度较大, 而且测试结果不具有代表性。
综合以上原因, 打算使用笔者设计的多目标地图编辑器进行游戏地图模拟, 提供可操作的测试环境。首先, 给出待测试地图组成元素, 鉴于游戏场景的复杂性和多样性, 选择6种地形作为模拟测试地图组成元素, 其分别是道路、障碍物、树林、深水、浅水和炮台;其次, 由上面介绍的地形特性可看出, 角色寻路需要考虑3个目标, 以下给出对各目标的定义。
定义1:路径长度, 即游戏角色从起点到终点走过的栅格数。使用
表示所走过栅格总数。
定义2:路径安全, 即游戏角色从起点到终点所遭受攻击的程度, 使用
表示路径的安全性, 走到炮塔可攻击的区域, 角色受到一定程度的伤害。
定义3:路径耗费, 即游戏角色耗费的体力值, 使用
表示路径对角色产生的体力耗费程度。
2多目标路径规划遗传算法
遗传算法需要经过多代的进化, 逐渐逼近问题的最优解, 同样路径规划也一样, 需要不断通过遗传算子的作用, 产生逼近最优路径的行走序列, 其关键在于编码、适应函数的设计、遗传算子使用。
2.1编码
经过反复实验, 决定采用不定长编码方式, 使用一串二进制数表示行走序列, 在起点和终点确定的情形下, 在表示编码的二进制序列中取数, 连续取两位, 若为00, 则向上行走;若为01, 则向下行走;若为10, 朝右行走;若为11, 朝左行走。这里要注意, 若取数后, 下步走到的是障碍物地形, 则跳过概数, 继续进行取数;若到达终点, 则结束取数过程;若都达到取数终止条件, 还没有找到终点, 则直接结束。
2.2适应性函数
与一般的遗传算法不同, 这里的适值函数有3个, 需要引入帕累托最优解集, 保证每一代一半以上的个体都可组成帕累托最优解集。同时, 对3个目标进行评估, 依次将满足帕累托最优解集条件的连通解加入子代, 除此之外, 使用赌轮算法随机找上代中的部分个体加入子代。这样, 既保证启发式地提供进化方向, 又保证优化朝着期望的方向进行。
2.3遗传算子
在遗传算法的遗传算子选择中, 最常采用的是交叉算子和变异算子进行优化, 达到对个体的变异。
(1) 交叉算子。使用传统的双点交叉方式, 对选择的两个等长基因个体, 以一定的概率将个体相对应的后半部分断裂、交换, 以形成新的个体。这里需要注意, 可能会产生不连通的路径序列, 交叉概率不应太高。
(2) 变异算子。变异算子与一般的遗传变异算子相同, 以一定的概率将个体上的基因位反转。这里要注意, 变异的概率控制在一定的范围, 太高导致与父代差异太大, 太低导致差异性不够。
2.4多目标遗传算法流程
由于是多目标优化的问题, 需要根据各个目标的重要性分配不同的权系数, 以确定适应性函数。由于引入了帕累托最优解, 在求解过程中就需要建立单独的集合去存放个体的非支配解, 最后再从集合中选出最符合实际需要的解。具体的步骤如下:
第1步:种群初始化。设置每代种群大小为N=30, 每个个体含有数量为n=20的基因, 遗传代数为max= 100。
第2步:生成初始种群。这需要两种策略, 利用启发式思想, 生成一半确定终点的路径, 再随机生成另一半可能混乱的路径。
第3步:评估个体适应值。取出每个个体的基因序列, 依次计算其3个目标上的适值, 再依据权值比重对3个目标进行合并, 作为其真正的适值。注意, 这里需要将该代个体满足帕累托非支配解的个体取出, 作为从该代选出的集合。
第4步:挑选个体。利用赌轮算法挑选个体, 由于各个目标上的适值是越小越好, 则对适值取倒数, 将每个个体适值相加, 计算每个个体适值所占的比重, 随机0~1的数, 依次累加每个个体比重值, 超过该概率值则停止, 选择最后累加个体。
第5步:判断终止条件。若达到终止条件, 则退出执行, 在帕累托解集中选择最优解序列作为问题解。否则, 通过遗传算子执行交叉和变异操作, 得到新个体, 新个体组成新种群, 转第二步。
3实验结果
为了测试算法的有效性, 自发模拟游戏环境, 设计测试地图, 用该算法在地图上进行寻路实验。在忽略寻路快慢的前提下, 将本算法所寻路径和传统A* 算法进行对比, 对比结果模拟如图2所示。
对比实验结果可以看出, A* 算法寻路结果 (图2中下) 拥有较好的实时性, 但缺乏对所寻路径的总体把握, 适应性不足。而本文提出的算法 (图1中上) 弥补了该方面的不足, 在对地形未知的情形下, 通过遗传进化, 准确把握路径各个目标的情形, 不断向最优方案逼近, 得到全局最优寻路结果。
4结语
本文提出一种适合于游戏中非玩家控制角色寻路的智能路径规划算法, 考虑到游戏中复杂地形的状况, 寻路过程具有很好的适应性, 算法可以综合多目标的要求, 找出一条从起始点到终点的全局折中最优路径。正如实验结果所示, 算法通过对地图全局的把握和对多目标的考虑, 综合多方面影响游戏路径的因素, 找出了一条在多个目标之间达到平衡的最优路径。
本文的研究和尝试仅仅是模拟游戏环境, 后续还需要在真实的游戏环境下进行实验, 发掘算法的适应度。另外, 本文算法与传统游戏中寻路算法相比, 实时性稍显不足, 未来还需要继续改进, 加快算法的收敛速度, 使其在游戏中体现非玩家控制角色的智能性, 让游戏更真实。
参考文献
[1]SCHRUM J R, MIIKKULAINEN.Constructing complex NPC behavior via multi-objective neuroevolution[M].In Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE) , 2008.
[2]XU X, K ZOU.An improved pathfinding algorithm in RTS games[M].Advanced Research on Computer Science and Information En-gineering, 2011.
[3]王红卫.基于平滑A*算法的移动机器人路径规划[J].同济大学学报:自然科学版, 2010, 38 (11) :1647-1650.
[4]孙树栋, 曲彦宾.遗传算法在机器人路径规划中的应用研究[J].西北工业大学学报, 1998, 16 (1) :79-83.
[5]靳凯文, 李春葆, 秦前清.基于蚁群算法的最短路径搜索方法研究[J].公路交通科技, 2006, 23 (3) :128-130.
[6]禹建丽, 孙增圻.一种快速神经网络路径规划算法[J].机器人, 2001, 23 (3) :201-205.
[7]STURTEVANT N R.Benchmarks for grid-based pathfinding[J].Computational Intelligence and AI in Games, IEEE Transactions on, 2012, 4 (2) :144-148.
[8]孙纯哲.凹形障碍全局路径规划的双蚁群完全交叉算法[J].农业机械学报, 2008, 39 (7) :149-153.
[9]XIAO J Z, MICHALEWICZ, L ZHANG.Evolutionary planner/navigator:operator performance and self-tuning[M].In Evolutionary Computation, 1996.
多目标遗传算法 篇9
缓冲气囊[1]作为一种有效的缓冲吸能装置[2], 已经广泛地应用于航天返回、无人机回收、装备空投等领域。国外已有成功案例, 如加拿大CL-89战地无人侦察机的回收方式和美国火星探索者的着陆方式采用的均是气囊减振技术。而在国内, 应用于装备空投、无人机回收领域的气囊减振技术尚处于初期研究阶段。
装备在空投着陆过程中, 缓冲气囊通过内部气体压缩吸收重物的冲击能量, 在适当的时机排出压缩气体释放能量, 防止重物反弹, 从而达到减小冲击过载、保护装备的目的。
在气囊缓冲过程中, 影响其动态特性的参数有很多, 如气囊的底面积、压缩行程 (气囊高度) 、初始囊压、爆破膜起爆阈值以及喷管排气口面积等。以往气囊的设计方法中, 通过大量的模型气囊落振实验来确定气囊的动态特性参数, 这样不仅实验周期长、研制成本高, 而且设计结果也不理想, 体积太大, 使气囊的应用受到限制, 因此气囊缓冲特性的优化和控制受到越来越多的研究者关注。在着陆缓冲过程中, 不但要使空投装备所受到的冲击过载最小, 而且还要确保缓冲气囊所占用的空间体积不能过大, 因此此类问题属于典型的多目标优化问题。针对这一问题, 本文采用理论和实验相结合的方法, 首先构建出气囊缓冲动力学模型, 然后再采用一种多目标优化策略, 对影响气囊缓冲效果的关键参数进行优化, 最后对优化结果加以实验验证, 使缓冲气囊在落地过程中既控制过载又避免反弹, 从而达到预期的效果。
1 气囊缓冲动力学模型的构建
1.1 气囊缓冲动力学模型的数学描述
气囊缓冲的动力学模型可用状态方程[3]表示为
X=f (D, B, t) (1)
式中, X为状态向量, 包括缓冲体的位移y、速度u和加速度a等;D为设计向量, 包括气囊底面积Sb、初始高度h、初始囊压p、爆破膜起爆阈值ppop和喷管排气口面积S等;B为条件向量, 包括允许过载am、缓冲体质量mh和初速度u0等;t为时间。
式 (1) 中的函数关系较为复杂, 其精确表达式难以写出。本文应用热力学中气体的状态方程及相关定律找出各影响参数之间的联系, 并自行编写程序建立气囊缓冲的动力学模型, 同时结合微型多目标遗传算法对气囊参数进行优化, 形成从缓冲气囊性能指标的提出、动力学模型的建立到其参数优化的一套优化设计方法。设计流程如图1所示。
1.2气囊缓冲动力学模型的控制方程
1.2.1 气体的状态方程
气态工质在同一状态下的状态参数之间存在着一定的关系。工质的三个基本状态参数的关系为
F (p, V, T) =0 (2)
式中, V为体积, m3;T为温度, K。
式 (2) 称为工质的状态方程[4]。实际气体的状态方程是十分复杂的, 实用上往往以图表代替。而理想气体的基本状态参数之间存在着确定的函数关系, 其关系式为
pV=RgT (3)
其中, Rg为气体常数, 其数值只与气体的种类有关而与气体的状态无关。式 (3) 称为克拉贝龙状态方程。
1.2.2 能量方程
在气囊缓冲过程中, 缓冲气囊可看作一个一般热力系, 热力系初始状态下总能量为E, 因本系统为绝热系统, 不考虑系统与外界的热量交换, 故ΔQ=0。在无限短时间Δt内, 重物压缩气囊, 对气囊做功ΔW;同时, 缓冲气囊向外喷出气体, 若流出系统的工质质量为Δm, 热力学能为ΔU, 流速为u′, 出口系统对流出Δm工质所作的推挤功为ptVt, 则缓冲气囊热力系总能量的变化ΔE为
ΔE=ΔW-ΔU-ptVt-Δmu′2/2 (4)
ΔW=ptΔV
ΔE=mcVΔT
式中, pt为缓冲气囊t时刻的内压;Vt为缓冲气囊t时刻排出的气体体积;cV为质量定容热容;m为气体质量;ΔT为气体变化温度;ΔV为气体变化体积。
令
H=U+ptVt
其中, H称为工质的焓[4], 每千克工质的焓称为比焓[4], 用j表示, 则比焓j的变化为
Δj=cpΔT (5)
式中, cp为质量定压热容。
则式 (4) 可以写成
ΔE=ΔW-Δm (j0+Δj) -Δmu′2/2 (6)
式中, j0为气体初始状态下的比焓。
1.2.3 出口截面气体状态参数
(1) 出口截面气体速度。一元稳定流动的能量方程[4]为
dj+u′du′=0 (7)
对于理想气体, 因Δj=cpΔT, 所以由式 (7) 可求得出口截面上工质的流速:
T2=T0 (pb/p0) (k-1) /k (9)
式中, T0为气囊内气体温度;T2为出口气体温度;k为定熵指数;pb为背压 (喷管出口截面外的环境压力) ;p0为滞止压力。
(2) 出口截面气体流量。
根据质量守恒定律, 流体经任一截面的质量流量保持不变, 即
qm=Au′/z (10)
z=RgT2/pb (11)
式中, A为截面面积;z为比体积。
1.2.4 缓冲气囊喷管的选用
在实际工程中, 经常需要根据实际工况选择合适形状的喷管, 并计算出其主要尺寸。喷管形状选择的方法[4]如下:
当pb≥pcr, 即pb/p0≥pcr/p0=vcr时, 选择渐缩喷管 (图2) ;当pb<pcr, 即pb/p0≤pcr/p0=vcr时, 选择缩放喷管 (图3) 。其中, 临界压力pcr与滞止压力p0之比称为临界压力比vcr。
对于渐缩喷管, 只需计算喷管出口截面面积 (排气口面积) S, 即
S=qmz/u′
对于缩放喷管, 需计算临界截面面积Smin、出口截面面积S及渐扩部分的长度l, 即
Smin=qmzcr/u′cr, S=qmz/u′,
l= (d2-dmin) /[2tan (ϕ/2) ]
需要说明的是, 长度并无一定的标准, 依经验而定。选得太短, 则气流扩张过快, 易引起扰动而增加内部损失;如选得过长, 则气流与管壁之间摩擦损失增加, 也是不利的, 经验证明, 图3所示的顶锥角ϕ在10°～12°之间时, 效果比较好。
1.2.5 缓冲气囊的初始体积气囊在初始时刻的体积V为
V=Sbh (12)
式中, h为初始囊高。
1.2.6 空投设备的加速度空投设备在t时刻的加速度at为
at=[ (pt-pb) Sb-G]/mk (13)
式中, G为空投设备的重力;mk为空投设备的质量。
2 气囊缓冲特性多目标优化方法
2.1气囊缓冲特性多目标优化问题的描述
根据气体热力学方程, 可以建立气囊缓冲过程中的动力学模型, 根据实验结果并结合气囊缓冲的技术指标确定设计变量、优化目标函数和约束条件, 对设计参数进行优化。在着陆缓冲过程中, 直接反映气囊的最佳缓冲特性的指标是最小化的最大过载, 同时又要确保缓冲气囊所占用的空间体积不能过大, 所以选择空投设备的最大加速度和缓冲气囊的体积作为优化目标。
经实验发现, 在气囊缓冲过程中, 影响空投设备最大过载的因素有很多, 其中以气囊底面积Sb、初始囊高h、初始囊压p、爆破膜起爆阈值ppop和喷管排气口面积S最为敏感。因此选取这5个参数作为优化的设计变量, 气囊缓冲模型的多目标优化问题可描述如下:
式中, maxa为着陆缓冲过程中空投设备的最大加速度;K*为排气口流动系数;Rg=287.06J/ (kg·K) ;Tin为内部气体总温;g1为最小缓冲行程条件;g2为最小囊压条件;g3为喷管排气口面积条件。
2.2微型多目标遗传算法[5]
一般来说, 多目标优化问题的解不止一个, 而是一组, 即非支配解或Pareto最优解。多目标遗传算法较之传统多目标算法具有在单次优化过程中找到多个Pareto最优解的能力, 并且还可以处理所有类型的目标函数和约束, 而不需要许多数学上的必备条件。微型多目标遗传算法是在微型遗传算法[6,7]基础上提出的一种基于非支配分级的多目标优化算法。传统遗传算法种群规模大、收敛效率低, 而微型多目标遗传算法则采用小规模种群, 具有较高的计算效率和收敛速度。该算法除了通过非支配分级为个体分配适应度, 还为具有相同非支配级的个体计算其个体间距离, 以确保种群的多样性。这些具有相同非支配级的个体则通过个体间距值来进一步比较个体之间的优劣, 个体间距值越小则个体的适应度越低, 反之亦然。一旦种群收敛, 则运用重启动策略产生新种群。该算法的计算流程如图4所示。
3 气囊缓冲特性多目标优化算例
3.1算例条件
某空投设备从离地1.8m处进行空投, 着地竖直速度u0=6m/s, 着落角θ=0, 最大允许过载[am]为25g[8] (人体对胸-背向冲击耐力的峰值) 。气囊底面积Sb的取值范围为15～30m2, 喷管排气孔面积S的取值范围为0～1m2, 初始囊高h的取值范围为0～1m, 初始充气压力的取值范围为101～120kPa, 喷管爆破膜起爆阈值的取值范围为101～135kPa。气囊的缓冲模型如图5所示。
3.2优化结果及分析
微型多目标遗传算法采用的参数设置如下:种群大小取为5, 交叉概率为0.6, 变异概率为0.05, 重启动判断代数为5。图6为气囊缓冲模型计算1000次后得到的Pareto最优解集。由图6可以看出, 所得到的Pareto最优解分布均匀, 空投设备的最大加速度在19g～22g范围内, 体积则在3～30m3之间。表1列出了从Pareto最优解集中均匀选择的10个解。
最后可根据经验或工程人员的偏好选择其中的某一个解作为最优解。若只重点考虑使max a最小, 则可以选取表3中的第1个解;本文则希望max a、V都考虑到, 故选择第6个解作为最优解。图7所示为采用第6个解时空投设备的加速度曲线。时间起点为气囊缓冲的初始时刻, 即空投设备刚好与缓冲气囊发生接触的时刻。
由图7可知, 优化后加速度曲线的第一个峰值为空投设备尚未着地时在气囊缓冲过程中所受到的冲击载荷;第二个峰值则是空投设备与地面发生碰撞所造成, 其值为21.21g, 它是整个缓冲过程中空投设备所受到的最大冲击载荷, 且21.21g<[am]=25g;余后的峰值为余振。
3.3实际应用
利用优化后的气囊设计参数研制缓冲气囊, 并应用于某重装设备的空投中。其中设备重8t, 在离地1.8m处实施空投。图8为实验结果和数值结果的对比。
从图8可以看出, 所建立数值模型的计算结果与实验结果的变化趋势比较一致, 尽管实验结果中加速度曲线出现负值, 这是因为空投设备两侧落地不同步造成, 但两者曲线峰值的大小和峰值出现的时间基本一致, 而且实验结果中空投设备最大加速度值为23.15g, 完全低于最大允许过载25g。这说明本文所建立的气囊缓冲数值模型是可信的, 优化方法的原理是正确的, 所得的结果比较准确, 符合实际工况要求。
4 结束语
本文应用气体的热力性质建立了气囊缓冲的动力学模型, 并采用微型多目标遗传算法对影响空投缓冲气囊动态特性的参数进行了优化。该方法不仅能为缓冲气囊的优化设计提供特征参数, 减少空投实验的次数, 降低昂贵的空投实验成本, 同时还能为工程人员提供多种方案, 以满足不同产品要求, 而且在载人空投技术领域也具有一定的实际工程意义。
参考文献
[1]张君媛, 黄柏, 冯原.基于多工况的汽车碰撞乘员约束系统参数匹配的研究[J].中国机械工程, 2007, 18 (24) :3005-3008.
[2]Northey D, Morgan C.I mproved Inflatable LandingSystems for Lowcost Planetary Landers[J].ActaAstronautica, 2006, 59:726-733.
[3]戈嗣诚, 施允涛, 徐庆华.无人机回收气囊的优化设计初探[J].震动, 测试与诊断, 2002, 22 (1) :34-36.
[4]陶文铨, 李永堂.工程热力学[M].武汉:武汉理工大学出版社, 2001.
[5]Liu G P, Han X.A Micro Multi-objective GeneticAlgorithmfor Multi-objective Opti mization[C]//The Fourth China-Japan-Korea Joint Symposiumon Opti mization of Structural and Mechanical Sys-tems.Kunming:The Chinese Association of Compu-tational Mechanics, 2006:419-424.
[6]Lee J, Ki mS-M.Opti mum Design of Cold-formedSteel Columns by Using Micro Genetic Algorithms[J].Thin-walled Structures, 2006, 44:952-960.
[7]Madadi R R, Balaji C.Opti mization of the Locationof Multiple Discrete Heat Sources in a VentilatedCavity Using Artificial Neural Networks and MicroGenetic Algorithm[J].International Journal of Heatand Mass Transfer, 2008, 51:2299-2312.
多目标遗传算法 篇10
混合动力客车(hybrid electric bus,HEB)是由多个动力部件构成的复杂系统,其性能优劣与动力传动系参数有密切关系,且HEB的动力性与经济性是互相牵制的,因此HEB动力传动系的参数优化属于有约束非线性多目标参数优化问题。目前,研究HEB动力传动系的参数优化方法主要有多目标优化方法和智能优化方法等[1,2,3]。传统的多目标优化方法把多目标优化问题转化为单目标优化问题来解决,其结果受人为因素影响较大,且可比性差。智能优化方法可以较好地解决多目标优化问题,其中,带精英策略的非支配排序遗传算法(elitist non-dominated sorting genetic algorithm,NSGA-Ⅱ)在解决HEB动力传动系参数优化这类多目标优化问题时表现出很大的优势[4,5]。故笔者在分析基于超级电容的HEB行驶特性的基础上,以等效燃油消耗量和加速时间为优化目标,运用NSGA-Ⅱ和iSIGHT优化软件对HEB传动系参数进行多目标优化。
1 HEB动力系统设计与建模
1.1 HEB动力系统设计
HEB动力系统通常有串联、并联、混联等形式。因并联式具有效率高、驱动特性更符合实际路况、能实现制动能量回馈等优点[6],故所设计的基于超级电容的HEB采用并联式混合动力系统,如图1所示。该系统采用后置后驱形式,柴油发动机发出的转矩经离合器、变速器,再与电机产生的转矩经转矩耦合器传至主减速器,最后经过后桥传至驱动轮。电机由超级电容提供电能,在汽车起步、加速等工况下辅助发动机工作;在巡航工况下,发动机工作在经济区域;制动工况下,电动机转换为发电机对超级电容充电,实现制动能量回馈。
1.2 HEB控制策略的设计
HEB动力传动系统的参数优化与控制策略密切相关,在动力传动系统参数优化前,先设定HEB的控制策略。文中采用发动机为主、电机为辅的电机辅助控制策略。控制逻辑设计如下:
(1)车辆起步时,速度低于设定值,电动机单独驱动车辆。
(2)当车速达到设定值,电动机关闭,发动机单独驱动,且富裕功率向超级电容充电。
(3)车辆在加速、爬坡及大负荷情况下,发动机和电动机共同驱动车辆。
(4)车辆在制动时,电动机转换为发电机,尽可能多地回收制动能量。
1.3 基于CRUISE的HEB整车建模
根据HEB动力系统结构特点,在CRUISE下建立整车仿真模型,如图2所示。该模型包括发动机模块、离合器模块、变速器模块、电机模块、超级电容模块、控制模块等,各模块上有机械接口、电气接口或数据接口。
2 HEB传动系参数优化设计
2.1 传动系参数优化目标确定
由于混合动力汽车的动力性与经济性是互相牵制的,故如何匹配传动系参数显得尤为重要[7,8]。HEB传动系参数优化的目的是在满足排放的基础上,尽量使动力性和经济性有较大的改善[9,10],因此笔者以等效燃油消耗量和加速时间为优化目标,进行多目标优化。优化目标函数表达如下:
式中,f(X)为目标函数;X为优化参数(HEB传动系中变速器速比与主减速器速比)组成的向量;T(X)为加速时间;F(X)为等效燃油消耗量。
2.2 HEB传动系优化参数选择
变速器和主减速器的速比均影响HEB整车动力性和经济性,故选择它们为传动系的优化参数。对于五挡手动变速器,倒挡对动力性和经济性影响很小,忽略不计,则确定传动系优化参数为主减速比i0、一挡传动比i1、二挡传动比i2、三挡传动比i3、四挡传动比i4、五挡传动比i5。
2.3 约束条件确定
2.3.1 变速器速比约束条件
手动变速器相邻挡传动比的比值一般在1.4~1.8之间[11],故变速器速比约束条件确定如下:
2.3.2 防止动力中断的约束条件
为了保证当前挡位下发动机的最高转速ngmax对应的最大车速vmmax(m=1,2,3,4)高于换入下一挡位时发动机最大转矩点转速nT对应的车速vm+1,约束条件确定为
2.3.3 整车性能要求
为满足HEB整体设计要求,确定最高车速大于80km/h;最大爬坡度大于20%;0~50km/h连续换挡加速时间小于30s。
2.3.4 地面附着力的限制
为满足最大爬坡度要求,整车最大驱动力必须大于或等于坡道阻力和滚动阻力之和,即
式中,Tmax为发动机最大转矩;r为车轮滚动半径;G为汽车重力;f为滚动阻力系数;α为坡道角。
在汽车行驶过程中为防止轮胎滑转,最大驱动力不能大于驱动轮与路面之间的附着力,即
式中,Fz为地面对车轮的法向反作用力;φ为地面附着系数。
2.3.5 动力因数的要求
为了使整车具有足够的动力,要保证一挡和最高挡(直接挡)足够大的动力因数,具体要求如下:
式中,CD为空气阻力系数;A为迎风面积,m2;vT为发动机最大转矩对应的车速,km/h;D1*为设计一挡动力因素要求,取值范围为0.30~0.45;D5*为设计直接挡动力因素要求,取值范围为0.09~0.12;η为传动系的效率。
3 NSGA-Ⅱ算法的传动系参数优化
3.1 NSGA-Ⅱ算法
遗传算法作为一种基于遗传进化原理的随机搜索算法,已广泛运用到各领域,但仍存在收敛速度慢、易于落入局部最优和早熟等问题,而NS-GA-Ⅱ可以得到分布均匀的非劣最优解,在多目标优化领域表现出很大的优势。NSGA-Ⅱ降低了算法的计算复杂度;引入精英策略,扩大了采样空间;通过拥挤度和拥挤度比较算子的计算,使Pareto最优解前沿中的个体能均匀地扩展到整个Pareto域,保证了种群的多样性。NSGA-Ⅱ算法的基本思想是:首先,随机产生规模为N的初始种群Pt,产生子代种群Qt,并将两个种群联合在一起形成大小为2 N的种群Rt;然后,将父代种群与子代种群合并,进行快速非支配排序,同时对每个非支配层中的个体进行拥挤度计算,根据非支配关系及个体的拥挤度选取合适的个体组成新的父代种群Pt+1;最后,通过遗传算法的基本操作产生新的子代种群Qt+1,将Pt+1与Qt+1合并形成新的种群Rt,重复以上操作,直到满足程序结束的条件。其程序流程如图3所示。图3中,Gen为进化代数,Z为非支配集,f为支配集中Z中的个体数。
3.2 iSIGHT集成优化
iSIGHT是智能多学科优化软件,可以将各种计算分析程序集成在一起,自动完成“设计-评价-再设计”的反复迭代过程。iSIGHT按照选用的算法要求,首先修改输入文件中需要优化的参数,然后调用软件进行运算,求解出最优解并输入到输出文件,之后对所求的最优解进行分析判断,如果是最优解则输出结果,完成优化;否则,再按照所选用的算法要求修改输入文件中需要优化的参数,继续调用软件运算,求解最优解等操作,直至求得最优解。iSIGHT集成优化流程如图4所示。
在iSIGHT9.0中,采用NSGA-Ⅱ遗传算法,基于iSIGHT/CRUISE平台进行集成优化[12]。在优化过程中,iSIGHT自动调用CRUISE软件,并改写CRUISE软件输入文件中的参数,读取CRUISE软件输出文件中的计算结果等。
3.3 基于NSGA-Ⅱ算法的HEB传动系参数优化
基于NSGA-Ⅱ算法进行HEB传动系参数多目标优化时,仿真模型是以模块形式嵌入到整个执行程序中进行参数优化的。采用NSGA-Ⅱ算法,基于iSIGHT/CRUISE实现HEB动力传动系参数优化的模型如图5所示。
4 实例HEB传动系参数优化分析
4.1 实例HEB样车主要技术参数
实例HEB样车是在某传统燃油客车基础上改装而成的。实例HEB样车主要技术参数如表1所示。
4.2 循环工况选择
文中选用中国典型城市公交循环工况进行优化仿真分析,如图6所示。该循环共用时1314s,行驶里程5.8km,平均车速为15.9km/h,最高车速达60.0km/h。基本反映出我国城市公交运行时速度低、变化大的特点。
4.3 基于NSGA-Ⅱ的传动系参数优化
采用NSGA-Ⅱ遗传算法,基于iSIGHT/CRUISE进行HEB动力传动系参数优化。在反复迭代过程中,优化变量不断被修改,逐渐趋向最优解,经过多次迭代,得到一组传动系参数优化结果,如表2所示。
4.4 优化前后的实例HEB性能分析
基于CRUISE的HEB整车仿真模型(图2)进行优化前后的HEB性能仿真分析,得到实例HEB优化前后的各挡爬坡度与各挡加速度随车速变化曲线,如图7、图8所示。仿真结果表明,优化后各挡爬坡度与加速度明显提高。
在中国典型城市公交循环工况下进行实例HEB仿真分析,优化后发动机的工作点向高效率工作区集中,燃油经济性得到改善。
基于中国典型循环工况进行实例HEB优化前后的整车性能道路试验,结果如表3所示。
5 结论
(1)设计了基于超级电容的HEB动力系统结构,采用NSGA-Ⅱ遗传算法在iSIGHT/CRUISE平台上进行了HEB传动系的多目标参数优化,并基于CRUISE所建立的整车仿真模型进行了实例HEB仿真分析。
(2)进行了优化前后的实例HEB的道路试验分析。结果表明:优化后的传动系参数能够满足HEB设计性能要求;与优化前HEB样车道路试验值相比,优化后的等效燃油消耗量降低了7.8%,0~50km/h加速时间减少了6.5%。同时验证了基于NSGA-Ⅱ遗传算法的HEB动力传动系多目标参数优化方法的可行性,从而为新能源汽车(包括纯电动汽车、增程式混合动力汽车)的参数优化提供了一种新方法。
摘要：对基于超级电容的混合动力客车(hybrid electric bus,HEB)进行了混合动力传动系多目标参数优化设计。通过CRUISE建立HEB整车仿真模型和传动系多目标参数优化模型,以等效燃油消耗量和加速时间为优化目标,同时运用带精英策略的非支配排序遗传算法(NSGA-Ⅱ)和iSIGHT优化软件对HEB传动系参数进行多目标优化,并进行了HEB性能仿真分析。结果表明,与优化前相比,优化后的等效燃油消耗量降低了7.8%,连续换挡加速时间减少了6.5%。
关键词：混合动力客车,动力传动系,多目标遗传算法,参数优化
参考文献
[1]吴光强,陈慧勇.基于遗传算法的混合动力汽车参数多目标优化[J].汽车工程,2009,31(1):60-64.Wu Guangqiang,Chen Huiyong.Multi-objectiveOptimization of HEV Parameters Based on GeneticAlgorithm[J].Automotive Engineering,2009,31(1):60-64.
[2]杨伟斌,吴光强,秦大同,等.混合动力汽车传动系优化匹配及性能仿真[J].同济大学学报(自然科学版),2006,34(7):937-942.Yang Weibin,Wu Guangqiang,Qin Datong,et al.Optimization Matching and Performance Simulationfor Hybrid Electric Vehicle Powertrain[J].Journalof Tongji University(Natural Science),2006,34(7):937-942.
[3]浦金欢,殷承良,张建武.遗传算法在混合动力汽车控制策略优化中的应用[J].中国机械工程,2005,16(7):648-651...Pu Jinhuan,Yin Chengliang,Zhang Jianwu.Applica-tion of Genetic Algorithm in Optimization of ControlStrategy for Hybrid Electric Vehicles[J].China Me-chanical Engineering,2005,16(7):648-651.
[4]Deb K,Pratap A,Agarwal S.A Fast and ElieistMulti-objective Genetic Algorithm:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Compata-tion,2002,6(2):182-197.
[5]李莉.基于遗传算法的多目标寻优策略的应用研究[D].无锡:江南大学,2008.
[6]陈清泉.先进电动汽车技术[M].北京:化学工业出版社,2007.
[7]余志生.汽车理论[M].北京:机械工业出版社,2010.
[8]颜伏伍,胡峰,田韶鹏,等.基于多目标遗传算法的汽车动力传动系统参数优化设计[J].汽车技术,2009(12):20-23.Yan Fuwu,Hu Feng,Tian Shaopeng,et al.Paramet-ric Optimization Design of Automobile PowertrainBased on Multi-objective Genetic Algorithm[J].Automobile Technology,2009(12):20-23.
[9]钱立军,吴伟岸,赵韩,等.混合动力汽车传动系优化匹配[J].农业机械学报,2005,36(9):5-8.Qian Lijun,Wu Weian,Zhao Han,et al.MatchingOptimization of Powertrain for a Hybrid ElectricVehicle[J].Transactions of the Chinese Society ofAgricultural Machinery,2005,36(9):5-8.
[10]尹安东,赵韩.混合动力客车动力系统综合参数正交优化与应用[J].合肥工业大学学报(自然科学版),2010,33(3):341-345.Yin Andong,Zhao Han.Orthogonal Optimizationand Application of System Parameters of HybridElectric Bus[J].Journal of Hefei University ofTechnology(Natural Science),2010,33(3):341-345.
[11]王望予.汽车设计[M].北京:机械工业出版社,2006.
多目标遗传算法 篇11
摘要：蚁群优化算法作为单目标优化问题，由于只有一个目标函数，通常会将解限制到特定的范围内。当优化的目标不恰当时，算法可能失效，比如分辨率限制问题。我们将多目标优化的思想与传统的用于社区检测的蚁群优化算法相结合，增加了目标函数个数，即增加了解的评价指标数目。该算法引入多目标策略，提出多目标ACO算法，该算法在一次运行过程中会产生一组Pareto最优解。并在三个真实世界网络证明该算法的有效性和准确性。
关键词：复杂网络；社区检测；蚁群优化算法；多目标优化
中图分类号：TP18文献标识码：A
1引言
1991年意大利学者Dorigo M等人首次提出了蚁群优化算法[1，2]引起了学者的广泛关注与研究。蚁群算法是一种基于种群的启发式仿生进化系统，该算法采用了正反馈分布式并行计算机制，易于与其它方法相结合并且具有较强的鲁棒性。
本文介绍了一种基于蚁群优化的多目标社区检测方法，将蚁群优化算法与多目标策略[3]相结合，是一种优化模块度的社区检测方法。对于多目标优化问题，通常无法得到最优解，若同时考虑多个目标函数则算法将会得到一组优于其它解的最优解集。该集合叫做帕雷托（Pareto）解集或者非支配解集。
2基于蚁群优化的多目标社区检测
蚁群优化算法（ACO），是一种基于蚂蚁觅食行为的启发式方法，用来解决困难的组合优化问题，并且已经成功的应用到了各种棘手的问题，像二次分配问题（QAP），车辆路径问题（VRP）等。在1996年，Gambardella等人提出了一种修正的蚁群优化算法——蚁群系统（Ant System，AS），已经成功地应用在旅行商问题上。在这之后，科学家们也发明了一些改进的算法，比如精英蚁群系统（Elitist Ant System，EAS），最大最小蚁群系统（MaxMin Ant System，MMAS）以及排序蚁群系统（RankBased Ant System，ASrank）。
运用蚁群优化来做社区检测，首先需要指出如何表达一个解，其次就是如何构建一个解，然后就是信息素的初始化以及更新。下面我们将详细描述该算法。
2.1编码方式
社区就是复杂网络的子图，因而检测社区结构就等价于找出能揭示网络最好分割的一组子图。因此，社区检测问题的解可以明确地表示为：一个n个元素的向量表示图，其连通分量相当于社区。向量的元素和索引对应于图G=（V，A）中的节点。例如，向量中第i个元素等于j，即节点Vi和Vj之间有边相连，也就是说这两个节点在同一个连通分量里面，即处于同一个社区。
该编码框架的优点有很多，最重要的是不需要预先知道复杂网络的社区划分数目。解码的过程需要找出所有的连通分量。所有属于同一个连通分量的节点被划分到一个社区，解码过程是有必要的且可以通过广度优先搜索（breadthfirst search，BFS）或者深度优先搜索（depthfirst search，DFS）在线性时间内完成。解码完成后，会得到一个表示每个节点归属的向量。这种基于基因近邻的编码框架已经应用到了多目标聚类领域。该框架在社区检测的应用中有几个主要的优点，最重要的是，不需要预先知道社区的真实划分数目K，因为在解码过程中能够自动地得到K的取值。
3.1真实世界网络
本节将MOACO算法应用在三个真实世界网络上，分别是Zacharys Karate Club、Bottlenose Dolphins、Books about US politics。以上复杂网络是社会网络分析领域中的经典数据集，将这些数据在并与没有加入多目标策略的ACO算法以及GA、GAloacal算法进行了对比。由表2可以看出，三十次独立运行后，在Zacharys Karate Club网络中，ACO和MOACO的平均模块度值均不如GA和GA-local算法的结果好，而MOACO和ACO的平均模块度相差不大；在Dolphin social network网络中，本文提出的MOACO算法的平均NMI值明显好于其它算法。在Dolphin social network网络中，MOACO算法的模块度Q平均值与ACO算法的结果相差不大，而NMI的平均值要好于ACO算法。
为了验证蚁群规模和迭代次数对算法的影响，以Zacharys Karate Club网络为例进行参数分析，参数α、β、T、ρ、ε的值不变化，算法独立运行三十次求平均模块度值Q和平均NMI值，讨论蚁群规模N对算法结果的影响。
由表3可以看出，随着蚁群规模的增加，平均模块度值呈增长趋势，在蚁群规模为80时，达到了最大值。而由于蚁群优化算法中蚂蚁个体选择路径是随机的，因而平均NMI值没有呈现一定的规律，而当蚁群规模为40时，平均NMI值取得最大值。
表4表示参数α、β、N、ρ、ε保持不变，讨论迭代次数T对算法结果的影响，算法独立运行三十次的算法结果如表4所示。
由表4可知，迭代次数对算法的平均模块度值影响不大，而当迭代次数为150次的时候，平均NMI值取得了最大值。
图2表示调节参数过程中，算法取得的最优结果，即每一次运行的模块度值和NMI值，data1表示平均模块度值，data2表示平均NMI值。最优参数为：迭代次数150次，种群规模40。可以看出模块度值非常稳定。
3.2计算机仿真网络
本节使用经典的GN benchmark复杂网络来检测算法的可行性和有效性。GN基准网络是由Newman等提出。对于该基准网络，每个图包含了128个节点，分为4个由32个节点构成的社区。每个节点平均有Zin条边与同社区内节点连接，Zout条边与社区外节点连接。其中Zin+Zout = 16，作为每个节点的期望的度。随着Zout的增大，所产生的随机网络给社区检测算法带来了更大的挑战。特别是当Zout大于8时，意味着每个节点在社区内的边都要小于社区外的边，这时网络的社区结构就会非常模糊。当Zout≤ 8时，节点外度所占的比例小于内度所占的比例，因此算法应该能检测出网络中存在的社区结构，当Zout = 0时，表明节点的外度为0，此时节点仅与自身社区内的节点相连接，社区结构非常明显。分别对Zout从0到2进行了测试，对每种类型的网络产生一个复杂网络，使用NMI来衡量算法检测的结果和真实网络划分之间的相似性。对于每个网络，计算三十次独立运行的平均值。
由表5可以看出，当GN网络的外度为0时，该算法可以准确地检测出网络划分情况；当GN网络的外度为1和2的时候，该算法得到的结果也还都是有效的。
但是，在蚁群优化方法中，其算法复杂度比较高，所需要的搜索时间很长，而且容易出现所有的蚂蚁所对应的解完全相同这种“停滞现象”。导致了当复杂网络的社区数目较大时，算法不能产生有效解。另外，该算法对计算机生成的仿真网络不能得到有效的结果，这是我们进一步研究的内容。
4小结
基于传统的蚁群优化算法（ACO）算法的缺陷，提出了一种用于复杂网络社区检测的多目标蚁群优化算法MOACO，该算法将继续沿用传统的基于模块度优化的策略，加入了多目标的思想，每次迭代过程中，根据两个目标函数的不同折中，最终得到Pareto解集，选取每一代中优先级最高的那一组解。在三个真实世界网络和GN网络中的外度较小的网络上证明了算法的有效性，并将提出算法与ACO算法进行了比较，NMI平均值要优于ACO算法，模块度Q的平均值与ACO算法相当。缺点是不能处理社区划分类别多的复杂网络，对于结构模糊的GN网络，算法的效果不明显。
参考文献
[1]HONGHAO C， ZUREN F， ZHIGANG R. Community detection using ant colony optimization [C] Evolutionary Computation （CEC）， 2013 IEEE Congress on. IEEE， 2013： 3072-3078.
[2]DORIGO M，BIRATTARI M，STUTZLE T. Ant colony optimization[J]. Computational Intelligence Magazine， IEEE， 2006， 1（4）： 28-39.
[3]SOLNON C， Ghédira K. Ant colony optimization for multi-objective optimization problems[J]. Internation Journal on computer science， 2010.
[4]GONG M， CAI Q，CHEN X， et al. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition[J]. Evolutionary Computation， IEEE Transactions on， 2014， 18（1）： 82-97.
多目标遗传算法 篇12
调度功能是车间管理的核心功能之一, 它直接关系着车间能否在指定的时间段内合理利用有限的制造资源完成相应的加工任务。调度问题不但冲突多、求解过程相当复杂, 而且在不同制造环境下所考虑的约束、达到的目的等均不相同, 使得调度问题之间的差别很大[1], 特别是对于多目标问题, 求解尤其困难。
组合优化问题通常具有大量的局部极值点, 往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题, 因此, 精确求解组合优化问题往往是不可能的。生产调度 (JSP) 问题是一类典型NP完全问题, 随着问题规模的扩大, 会发生组合爆炸, 算法复杂性呈指数增长[2,3]。各类混合遗传算法是解决实际调度问题最有效的途径和最有前途的调度方法[4]。在充分进行调查研究和比较各类优化搜索方法[5,6,7,8,9]的基础上, 提出一种混合遗传算法来有效解决生产调度中的多目标问题。
2 JSP问题描述
JSP (Job-Shop) 问题研究n个工件在m台机器上的加工, 已知各操作的加工时间和各工件在各机器上的加工次序约束, 要求确定与工艺约束条件相容的各机器上所有工件的加工时间或完成时间或加工次序[10]。
使加工性能指标达到最优, 具体满足如下条件:
1) 同一时刻同一台机器只能加工一个工件;
2) 每个工件在某一时刻只能在一台机器上加工, 不能中途中断每一个操作;
3) 不同工件的工序之间有部分联系;
4) 不同工件具有优先级的差别;
5) 每个工件相邻工序之间的间隔为零 (准备时间可计入机器的加工时间) 。
AOE带权有向无环网模型是描述JSP调度问题的一种行之有效的方法, 如图1所示。
顶点表示事件, 弧aij表示工件i的某道工序j, 权表示工序加工时间 (为了简化模型, 准备时间包含于加工时间内视为整体) 。
分析AOE网可以得到生产过程中的关键路径, 对于解决生产调度中的瓶颈问题有很强的现实意义。通过改善关键活动的工效, 可以有效缩短整个工期, 提高设备利用率。
车间调度分为静态调度和动态调度两种。静态调度目标为在满足生产任务交货期的前提下, 尽可能提高设备资源的利用率, 减少调整时间, 使生产周期最短。静态调度是车间计划进入执行阶段的基础和依据, 遗传算法 (GA) 在静态调度问题中已经有成功的应用。动态调度指在车间实际的运行过程中, 存在着不可预期的被称为动态时间的随机扰动, 如机器故障、订单的突然加入或取消等, 因此往往需要不断地进行动态重调度[11,12,13]。具体生产调度加工目标和解决策略如下:
1) 企业成本最小化、降低库存;
2) 按期交货订单数量最大化。考虑缩短制造周期方面, 则调用完工时间最早的工序;考虑不同交货期方面, 则计算不同完工提前期, 根据事情紧急情况分别对待;
3) 资源设备均衡利用。考虑减少机器负荷方面, 则调用加工时间最小的工序;考虑设备能力方面, 则涉及加班、外协等问题;
4) 任务优先数的考虑。在上层决策时, 充分关注市场销售、机器生产、库存等方面问题;而装配完成情况与加工次序紧密联系;动态调度事, 对于缺件未能按时完工, 需要优先加工, 将其优先级增大;
5) 减少调整准备时间。充分考虑运输时间的问题, 其中涉及到设备地理位置情况、工件准备时间、刀具准备时间等方面。
3 混合遗传算法描述
3.1 混合遗传算法
遗传算法 (GA) 是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化算法, 在许多领域中得到了成功的应用, 如函数优化、旅行商问题等。利用遗传算法已经成功解决静态生产调度问题, 本文重点针对动态调度中的多目标问题, 采用以遗传算法为基础, 结合AOE找寻关键路径的混合遗传算法来弥补遗传算法的局部搜索能力的不足, 根据适应度的变化采用相应的交叉变异算子, 避免“早熟”收敛现象发生, 对于生产调度中的动态多目标问题进行有效的解决[11,12,13]。
3.2 编码方案
编码问题是算法设计的首要和关键问题, 常见的有二进制编码、格雷码编码、实数编码、符号编码、排列编码、二倍体编码、DNA编码、多参数编码、矩阵编码等[14]。解决经典的工作车间调度问题有基于工序的编码、基于机器编码、基于操作的编码等多种方法。采用基于工序和机器的编码[15], 工序aij用Gi来表示工件i, 其出现的次序表示工序加工顺序;机器m用Jm表示某工序加工的机器。如染色体J1G1-J2G2-J1G1-J2G1表示工件1第1道工序在机器1上加工, 工件2第1道工序在机器2上加工, 工件1第2道工序在机器1上加工, 工件1第3道工序在机器2上加工。
3.3 种子选择
首先对各工序生成的AOE网进行拓扑排序及逆拓扑排序判断, 在该前提下求得关键路径, 并对关键活动优先分配机器, 保证关键活动的正常如期完成。将关键活动基因置前, 后随机生成一定数量的不完全染色体种子, 结合工序要求对非关键路径上的工序进行机器分配, 形成最终的染色体。采用常用的轮盘赌方法进行选择适应度高的个体, 为了防止算法收敛于局部解, 种群规模取30个。
为了保证所得到的最优个体不会被交叉、变异等遗传操作所破坏, 结合使用最优保存策略, 若当前群体中最佳个体的适应度低于总的迄今为止的最好个体的适应度, 用迄今为止的最好个体替换掉当前群体中的最差个体。
3.4 适应度函数
多目标优化问题是指一个问题存在多个需要优化的性能指标, 每个性能指标都有其不同约束条件, 多目标优化就是要寻求一个在满足各个约束条件下且能使各个需要优化的目标能得到优化解[11,12]。企业生产调度问题是一个典型的多目标优化问题, 生产系统的效率取决于很多因素如生产周期 (市场销售) 、机器生产的利用率、库存 (成本) 等, 上层管理决策对各目标的考虑权重不同也直接决定着生产调度的结果发生变化。本文算法在交叉变异过程中使用相关参数α、β进行环境适应性调整, 以达到多目标综合决策要求。
1) 最小生产周期。
, 其中F是染色体的适应度;ET是机器的完工时间;Mj代表机器j;m是总的机器数量。
2) 最小生产成本。
, 其中F是染色体适应度;MC是制造成本;WC是机器空闲成本;k是机器ID;m是工厂里的机器数量。
3) 加权平均生产周期和成本 (WMC) 。
, 其中F是染色体的适应度;α是生产周期的权重;β是成本的权重;T是单位时间到单位成本的转换系数, 可在实际的排产过程中估算[8]。
3.5 交叉变异操作
交叉算法直接决定着遗传算法的全局搜索能力, 基于关键路径的交叉算子操作如下;首先根据交叉概率和适应度权重的配置选择一对父母个体, 仅对后续非关键基因部分进行交叉操作;随机选择非关键活动上的一个工件, 其在父母个体中对应的x个操作不变, 父母个体剩余其他操作按顺序进行对应变换, 分别得到新的两个子代个体。
变异算子决定了遗传算法的局部搜索能力, 良好的算子可以有效的维持群体的多样性, 防止早熟现象的出现。为了保证关键活动的顺利完成以及种群的多样性, 变异操作分为两大步骤进行:首先根据变异概率对关键路径上的工序进行机器配置变异, 然后对非关键工序进行局部重新定位[16,17,18]。
3.6 算法流程
1) 调度任务数据初始化;
2) 建立AOE网, 求出关键路径, 随机生成初始种群;
3) 计算适应度, 结合使用最优保存策略采用轮盘赌方法进行选择;
4) 基于关键路径进行交叉变异操作;
5) 满足终止条件, 转步骤6, 否则转步骤3;
6) 输出最终解集。
4 计算应用实例与实验仿真
系统演示使用Visual C++编程工具完成, 如下是一个标准实例:已知实际工作环境及条件:5类机床, 数量分别为2、1、1、1、1台, 编号i-j表示i类机床第j台;工件号和工序号从1开始排列, 交货期均设为零值, 具体数据见表1。
注:内容标注依次为加工时间、机床类型-同类机床编号
利用关键路径的遗传算法得到实验结果仿真如图2所示。图中aij表示第i个工件第j工序。可以看出整体的加工顺序安排合理, 充分考虑了关键工件的加工工序, 使得工期达到最短, 成本最低。
5 结论
针对制造企业生了车间生产调度系统框架。根据生产调度中动态多目标特征, 使用相应的交叉变异算子改善了遗传算法的搜索性能, 在算法流程中考虑了同类型机床的负荷平衡优化问题, 最后使用该算法对实例进行了调度仿真, 通过分析比较, 表明本文的调度算法性能良好, 能够较好的适应制造环境实际。
摘要：针对生产调度多目标动态复杂性, 提出了一种基于AOE图寻找关键路径的改进遗传算法。采用基于工件和机器相结合的编码方法, 根据多目标要求, 设计了相应的交叉遗传算子。实验结果表明, 改进的遗传算法符合车间实际应用情况, 对解决多目标动态车间调度问题有实际的应用意义。
【多目标遗传算法】推荐阅读：
多目标混合遗传算法06-25
多目标自适应遗传算法07-19
多Agent遗传算法06-09
雷达多目标跟踪算法09-11
遗传基因算法08-21
遗传禁忌算法09-01
遗传算法研究概述07-19
元胞遗传算法05-11
进化遗传算法论文05-20
混沌遗传优化算法05-26