一种求解完整Pareto前沿的多目标优化方法
一种求解完整Pareto前沿的多目标优化方法
【技术领域】：
[0001]本发明提供了一种求解完整Pareto前沿的多目标优化方法，属于计算机算法和管 理优化领域。
【背景技术】：
[0002]多目标优化问题(multi-objective optimization problem，简称Μ0Ρ)涉及生活 的方方面面，相关的求解方法对解决政治、金融、军事、环境、生产制造、社会保障等各方面 的规划决策问题起着至关重要的作用。Pareto最优解和Pare to前沿是Μ0Ρ中的核心概念，它 们起源于经济学中对收入分配优化的研究。简单地说，对于一个给定的解，如果不存在任何 一个解在各个指标上都不比它差，而且至少在一个指标上比它好，则这个给定解就是一个 Pare to最优解。所有Pare to最优解在目标函数空间里的投影就构成了完整Par e to前沿。求 解MOP的关键就在于寻找Pareto前沿。然而，现有的绝大多数MOP求解方法都只能寻找部分 的、或近似的Pareto前沿。
[0003]现有的求解Μ0Ρ的方法大体可以分为三大类：重构单目标函数法（aggregate objective function，简称A0F)，约束目标函数法（constrained objective function，简 称C0F)，和Pareto标准评级法(Pareto-compliant ranking，简称PCR) aAOF会把MOP中的所 有原始目标函数整合到一个单一的重构目标函数中，然后针对这个重构单目标函数进行单 目标优化，即可得到一个Pareto最优解。然而，定义重构单目标函数时存在主观性，并且很 多重构单目标函数的定义从理论上就决定了A0F不可能找到Pareto前沿上的凹面所对应的 Pareto最优解。C0F把Μ0Ρ转化成一个带约束的单目标优化问题，即仅针对Μ0Ρ的一个目标进 行优化，而把所有其它目标当成额外的约束条件。PCR基本都是基于种群的各种进化算法， 通过筛选和进化种群中的当前非劣解，在种群进化结束后将当前非劣解集作为近似的 Pareto前沿输出。PCR虽然没有A0F的问题（如主观性等），但A0F的输出肯定是Pareto最优 解，而PCR的输出有可能根本就不包含任何Pareto最优解。
[0004] 对一些基于非线性重构单目标函数的A0F而言，对任一给定的Pareto最优解，在理 论上总可以证明存在一组重构参数，使得A0F的输出为该指定的Pareto最优解。然而，却缺 少实际有效可行的理论和方法保证找出能够对应涵盖所有Pareto最优解的重构参数集合。 C0F在理论上，通过将优化目标转化成约束条件，是可能求解完整Pareto前沿的。但是和A0F 的情况一样，C0F缺少实际有效可行的理论和方法来确定所需的转化参数集合，因而难以确 保所生成的约束条件能找到完整Pareto前沿。在目前为数不多的关于求解完整Pareto前沿 的研究报导中，基本都是通过精心设计针对特殊类型问题的A0F重构参数集合或C0F转化参 数集合，从而把所有Pareto最优解都找出来。尽管PCR是Μ0Ρ研究中最热门的方法，但是因为 其所依赖的进化算法具有随机特性，所以PCR在理论上根本不能保证找到完整Pareto前沿。
[0005] 最近在文献[1]和文献[2]中提出了一种利用涟漪扩散算法求解前k个单目标最优 解，进而再基于各个目标函数下的前k个单目标最优解求解Μ0Ρ的完整Pareto前沿的方法。 需要强调的是：（1)文献[1]和文献[2]中的涟漪扩散算法本身不能解决Μ0Ρ，而是仅仅针对 单目标优化问题的，即，文献[1 ]和文献[2]中的涟漪扩散算法是单目标涟漪扩散算法；（2) 为了求解MOP的完整Pareto前沿，需要在各个目标函数下多次运行文献[1 ]和文献[2]中的 单目标涟漪扩散算法；（3)在多目标路径优化问题中，每当求解给定起点到另外一个网络结 点的完整Pareto前沿时，都需要单独运行一次文献[1]或文献[2]中的方法，换句话说，假设 路网中有Nn个结点，其中一个结点为给定起点，如果我们需要求解给定起点到另外(Nn-1 )个 结点中每一个结点的完整Pareto前沿，那么我们总共需要运行(Nn-1)次文献[1]或文献[2] 中的方法(在每一次方法运行中，又需要运行若干次单目标涟漪扩散算法）。所以文献[1]和 文献[2]中求解完整Pareto前沿的方法是非常低效的。
[0006] 本发明将提出一种真正的多目标涟漪扩散算法，其求解效果是:仅仅需要运行一 次本发明的方法，就可以求解出从给定起点到所有另外(Nn-ι)个结点中每一个结点的完整 Pareto 前沿。
[0007] [1]Χ·B·Hu，M·Wang，and E·Di Paolo，"Calculating Complete and Exact Pareto Front for Multi-Objective Optimization：A New Deterministic Approach for Discrete Problems"，IEEE Transactions on Systems?Man and Cybernetics，Part B，Vol.43，No.3，pp:1088-1101，2013.
[0008] [2]胡小兵，《求解完整Pareto前沿的多目标优化新方法研究》，国家自然科学基金 面上研究项目（项目号:61472041)，2015年1月。
【发明内容】
：
[0009] 本发明的目的是要提供一种求解完整Pareto前沿的多目标优化方法。对于多目标 路径优化问题，假设路网中有Nn个结点，本发明的方法具有如下求解效果:仅仅需要运行一 次本发明的方法，就可以求解出从给定起点到所有另外(Nn-Ι)个结点中每一个结点的完整 Pareto 前沿。
[0010]假设有一个网络系统（可以是现实物理网络系统，如：公路网，也可以是抽象虚拟 网络系统，如:决策树），包含Nn个结点。结点间的链接可由一个邻接矩阵A表示，其中的元素 A(i，j) = 1表示结点i和结点j之间存在一条链接;A(i，j) =0则表示结点i和结点j之间没有 链接。假设结点i和结点j之间存在一条链接，则该链接有N〇bj个目标权重值，可分别记为Ck (1，」）汰=1，一，他^。假设?表示一条路径，路径?包含见2 2个结点，？（1)表示路径？的第1个 结点，l<i<NL，l<P(iHNN。
[0011] 对于多目标一到一路径优化问题（即，从一个给定起点到一个给定终点），假设结 点S是给定起点，而结点D是给定终点，那么我们需要求解如下最小化问题：
[0012]
⑴
[0013] 其中
[0014] p(i)=s，P(Nl)=D， (2)
[0015] P(i)关P( j)，if i 关 j，i = l，· · ·，NL，and j = 1，· · ·，Nl， (3)
[0016] A(P(i)，P(i+l)) = l， (4)
[0017] ΩΡ表示所有可能路径的集合，fk是第k个单目标函数，k=l，-_，Nc^，fk可以是任何 形式的满足下列条件的函数：
[0018] 如果f^Pi) <fk(P2)，那么f^Pi+P) <fk(P2+P)， (5)
[0019] 如果 f^PiXf^p〗），那么 fk(p1+p)<fk(p2+p)。 (6)
[0020] 对于多目标一到多路径优化问题（即，从一个给定起点到路网中每一个其它结 点），在问题的数学描述上，可以当作(Nn-1)个独立的多目标一到一路径优化问题，每个一 到一问题中的终点为起点以外的其它(Nn-1)个结点中的某一个。显然，一到一问题只是一 到多问题的一个部分或者一个特例。所以，能解决一到多问题的方法，必然也能够解决一到 一问题。
[0021] 本发明为解决上述的多目标一到多路径优化问题，将通过下述的方案来实现。本 发明的方法在路网中模拟一场涟漪扩散接力赛;接力赛开始于一个以给定起点为波源的初 始涟漪;涟漪沿路网中的链接按预设的速度扩散；当一个涟漪扩散到一条链接的另一端的 结点时，如果该涟漪所代表的路径与该结点上已产生的所有涟漪所代表的路径相比是 Pareto非劣的，则一个新涟漪将以该结点为波源被激发出来并扩散；当一个涟漪已经到达 了与其波源结点相连的所有结点，该涟漪就消亡；当接力赛中的所有涟漪都消亡了，则通过 回溯一个结点上的所有涟漪，就能得到从给定起点到该结点的完整Pareto前沿。
[0022]为求解出从给定起点到所有另外(Nn-1)个结点中每一个结点的完整Pareto前沿， 本发明的方法的一次性优化计算过程包括以下几个主要步骤：
[0023] (步骤一)如果在个单目标函数中至少存在一个求和单目标函数，即，至少存在 一个fk具有如下函数形式
[0024]
(7)
[0025] 则选一个求和单目标函数用以标定涟漪接力赛中的路径长度，假设第kBM个单目标 函数被选中；如果在Ncibj个单目标函数中没有求和单目标函数，则人为增加一个具有函数形 式(7)的求和单目标函数fNClbj+l，用以标定接力赛中的路径长度，因而设置kBM = N〇bj + l，简单 起见，可 以定义fNc^+1(P)=NL-l，也就是说，每条链接的第(N_+l)个目标权重值都等于1， 即，对任意1 < i < Nn和1 < Nn，如果A( i，j) = 1，则定义(：_+1 (i，j) = 1;然后预设一个涟漪 扩散速度V。
[0026](步骤二)初始化各种用以记录涟漪接力赛中的涟漪的状态的变量。
[0027] (步骤三）以起点S为波源生成一个初始涟漪（即，第一个活跃涟漪），设置当前涟漪 数量为Nr=1，设置第一个涟漪的波源为E(1) = S(即，起点为波源），设置第一个涟漪的半径 为R(1) =〇，设置第一个涟漪的状态为Sr(1 ) = 1 (即，活跃），设置第一个涟漪的激发涟漪为T (1)=0(即，第一个涟漪不由任何涟漪激发，而是自发产生的），设置第一个涟漪的适应度向 量为其所对应路径的各单目标函数值(即〇向量，因为第一个涟漪所对应路径是S-S);设定 当前仿真时刻为t = 0，以便开始涟漪接力赛。
[0028] (步骤四）：判断涟漪接力赛是否该结束？如果涟漪接力赛中已经没有任何活跃涟 漪，即，对任意一个KHNr，都有SR(r) = 0,即涟漪r不活跃，则到步骤(八）；否则，到步骤 (五)。
[0029] (步骤五）：更新仿真时间t = t+l;对每个活跃涟漪按预设的涟漪扩散速度和一个 时间单位长度更新半径，即，对任意一个1 < r < Nr，如果SR(r) = l，则更新R(r)=R(r)+v。
[0030] (步骤六）：对任何一个结点n，如果在当前这个时间单位长度内有涟漪到达(可能 是1个涟漪或多个涟漪;涟漪的波源结点与结点η之间必需有链接），即，对结点η，存在至少 一个1 < r < Nr，满足SR(r) = 1，A(E(r)，n) = 1，R(r) 2 CkBM(E(r)，η)，那么，根据所有的单目标 函数，将这些新到的涟漪彼此进行Pareto优劣比较，再与结点η的已有涟漪进行Pareto优劣 比较，以便将这些新到涟漪中的Pareto非劣涟漪(对该结点而言）找出来，以两个涟漪i和j 的Pareto优劣比较为例，分别计算或提取沿涟漪i所对应的路径以及沿涟漪j所对应的路径 从结点S走到结点η的各个单目标函数值，然后按Pareto优劣的定义比较涟漪i和涟漪j的各 个单目标函数值，从而确定涟漪i与涟漪j之间的Pareto优劣关系，只有当一个新到涟漪与 所有其它新到涟漪以及结点η的已有涟漪相比都是Pareto非劣的，这个新到涟漪对结点η来 说才是Pareto非劣的；然后由每个Pareto非劣的新到涟漪在结点η上激发产生一个新的活 跃涟漪（即，所有新激发产生出的涟漪都是活跃涟漪），并对新涟漪的状态进行相应的设置； 对结点η上的一个由涟漪i所激发出的新涟漪的设置主要如下：当前涟漪数量加1 (即，Nr = Nr + 1)，然后为新涟漪咏设置3[?(咏）=^(咏）=11，1'(咏）=丨，1?(咏）=1?(丨）-01^江（丨），11)，并根 据沿涟漪i所对应的路径从结点S走到结点η的各个单目标函数值来设置新涟漪Nr的适应度 向量（以用于今后的Pareto优劣比较）。
[0031](步骤七）：对任何一个活跃涟漪，如果该涟漪已经到达了与其波源结点有链接的 所有其它结点(不考虑该涟漪所对应路径已包含的结点），即，对任何一个r，1 < r < NR，SR(r) =1，如果对每一个满足A(E(r)，n) = l的结点n，都有R(r) 2 CkBM(E(r)，n)，那么，设置涟漪r 变为不活跃，即，设置SR(r)=0,或者说涟漪r消亡了；然后回到(步骤四）。
[0032 ](步骤八）：对任意一个结点（非起点），从起点到该结点的完整Pare to前沿由该结 点上所产生的所有涟漪来确定，即，该结点所产生的每一个涟漪都对应一个Pareto最优解。 如果(步骤一）中人为增加了一个求和单目标函数f N_+1，则从已确定出该结点的(N_+l)维 Pareto前沿中筛选出不考虑该求和单目标函数fNQbj+i的Nobj维Pareto前沿，就是原始问题中 从起点到该结点的完整Pareto前沿。
[0033] 虽然上述(步骤一）到（步骤八)是用于求解多目标一到多路径优化问题（即，从一 个给定起点到路网中每一个其它结点），但是基于(步骤一)到（步骤八），无需任何修改，就 可以求解多目标一到一路径优化问题（即，从一个给定起点到一个给定终点）。不过，为了避 免不必要的计算以提高求解一到一问题的效率，可以对上述（步骤四）、（步骤六)和（步骤 八)进行轻微修改，如下：
[0034](步骤四改）：判断涟漪接力赛是否该结束？如果涟漪接力赛中已经没有任何活跃 涟漪，或者所有活跃涟漪与终点D上已有的涟漪相比都不是Pareto非劣的，即，对任意一个1 < r < Nr，都有SR(r)=0(即，涟漪r不活跃），或者，对任一1 < r < Nr，Sr(i·) = 1，如果涟漪1*所 对应的路径与终点D上已有涟漪所对应的路径相比都不是Pareto非劣的，则到步骤(八）；否 贝1J，到步骤(五）。
[0035](步骤六改）：开始一切同（步骤六），直到:然后由每个Pareto非劣的新到涟漪在结 点η上激发产生一个新的涟漪(可能是活跃涟漪，也可能是不活跃涟漪），新涟漪的其它设置 同（步骤六），惟有新涟漪的活跃状态需如下设置:如果结点η不是终点（即，η矣D)，则设置新 涟漪为活跃涟漪，即，Sr(Nr) = 1;否则（即，n = D)，设置新涟漪为不活跃涟漪，即，Sr(Nr)=0。 换句话说，非终点的结点所产生的涟漪都初始化为活跃涟漪，而终点D所产生的涟漪都是不 活跃涟漪。
[0036] (步骤八改）：根据终点D产生的所有涟漪，确定从起点S到终点D的完整Pareto前 沿，即，终点D所产生的每一个涟漪都对应一个Pareto最优解。如果(步骤一）中人为增加了 一个求和单目标函数fNQbj+1，则从已确定出的(Ncibj+Ι)维Pareto前沿中筛选出不考虑该求和 单目标函数fNQbj+i的Ncibj维Pareto前沿，就是原始问题中从起点S到终点D的完整Pareto前 沿。
[0037] 需要特别强调的是，在描述本发明的方法时，为了更加形象和容易理解，我们将其 比喻成涟漪扩散接力赛，但这个比喻不是必须的，核心是比喻所对应的计算步骤的内容，这 些内容可以被比喻成其它任何恰当的事物或过程，或者不用比喻，而是纯粹用抽象的数学 变量和术语表示，例如，涟漪r的半径:R(r)，我们完全可以不用"涟漪"和"半径"这两个词汇 字眼，而是抽象地说成：向量R的第r个元素 R(r)。
[0038] 同理，在描述本发明的方法时所使用的各个变量符号本身不是必须的，核心是变 量的意义以及对变量的操作计算过程，例如，（步骤五）中更新涟漪半径:R(r)=R(r)+v，可 以用任意变量符号来改写，如:W(m) =W(m)+z，其效果是一样的。
[0039] 本发明的方法在实现上可以采用各种恰当的硬件计算设备(例如：单片机、手机、 个人电脑、大型计算机、计算机网络，等等)和软件编程技术(例如:路网的链接不用邻接矩 阵A表示，而是采用链接向量表的数据结构；可以采用集中式的算法设计思路，也可以采用 分散并行式的算法设计思路;可以采用各种计算机编程语言和软件系统）。
[0040] 本发明的一种求解完整Pareto前沿的多目标优化方法具有以下有益效果:对于任 何可以转化为多目标路径优化的问题，本发明的方法可以求解出完整的（而不是部分的、或 近似的）Pareto前沿;对于多目标一到多路径优化问题（即，从一个给定起点到路网中每一 个其它结点），假设路网有Nn个结点，本发明的方法不需要将其作为(Nn-1)个独立的多目标 一到一路径优化问题（即，从一个给定起点到一个给定终点）分别求解，而是通过一次性的 计算，就可以求解出从给定起点到所有另外(Nn_ 1)个结点中每一个结点的完整Pareto前 沿。
【附图说明】：
[0041] 附图给出本发明的一种求解完整Pareto前沿的多目标优化方法的示意图：
[0042]图1: 一种求解完整Pareto前沿的多目标优化方法的主要步骤示意图（针对一到一 问题）。
[0043]图2:-种求解完整Pareto前沿的多目标优化方法的主要步骤示意图（针对一到多 问题）。
[0044]图3: -种求解完整Pareto前沿的多目标优化方法的求解过程示意图。
[0045]图4: 一种求解完整Pareto前沿的多目标优化方法的求解效果示意图。
【具体实施方式】：
[0046] 下面结合附图，对本发明的一种求解完整Pareto前沿的多目标优化方法所采用的 优选方式做进一步说明。
[0047] 图1给出了本发明的方法在求解多目标一到一路径优化问题（即，从一个给定起点 到一个给定终点)时所包括的主要步骤：
[0048] (步骤一)如果在NQbj个单目标函数中至少存在一个求和单目标函数，即，至少存在 一个fk具有函数形式(7)，则选一个求和单目标函数用以标定涟漪接力赛中的路径长度，假 设第k BM个单目标函数被选中；如果在N〇bj个单目标函数中没有求和单目标函数，则人为增加 一个具有函数形式(7)的求和单 目标函数f NQbj+1，用以标定接力赛中的路径长度，因而设置 kBM=Ncibj+l，简单起见，可以定义fNQbj+i(P) =Nl_1，也就是说，每条链接的第(Ncibj+Ι)个目标 权重值都等于1，即，对任意1 < i < Nn和1 < j < Nn，如果A( i，j) = 1，则定义C_j+1 (i，j) = 1;然 后预设一个涟漪扩散速度v。
[0049] (步骤二)初始化各种用以记录涟漪接力赛中的涟漪的状态的变量。
[0050] (步骤三）以起点S为波源生成一个初始涟漪（即，第一个活跃涟漪），设置当前涟漪 数量为Nr=1，设置第一个涟漪的波源为E(1) = S(即，起点为波源），设置第一个涟漪的半径 为R(1) =〇，设置第一个涟漪的状态为Sr(1 ) = 1 (即，活跃），设置第一个涟漪的激发涟漪为T (1)=0(即，第一个涟漪不由任何涟漪激发，而是自发产生的），设置第一个涟漪的适应度向 量为其所对应路径的各单目标函数值(即〇向量，因为第一个涟漪所对应路径是S-S);设定 当前仿真时刻为t = 0，以便开始涟漪接力赛。
[0051] (步骤四）：判断涟漪接力赛是否该结束？如果涟漪接力赛中已经没有任何活跃涟 漪，或者所有活跃涟漪与终点D上已有的涟漪相比都不是Pareto非劣的，即，对任意一个 1'<咏，者卩有5[?(1')=0(8卩，涟漪1'不活跃），或者，对任一1<1^咏，5[?(1') = 1，如果涟漪1'所对 应的路径与终点D上已有涟漪所对应的路径相比都不是Pareto非劣的，则到步骤（八）；否 贝1J，到步骤(五）。
[0052](步骤五）：更新仿真时间t = t+l;对每个活跃涟漪按预设的涟漪扩散速度和一个 时间单位长度更新半径，即，对任意一个1 < r < Nr，如果SR(r) = l，则更新R(r)=R(r)+v。 [0053](步骤六）：对任何一个结点n，如果在当前这个时间单位长度内有涟漪到达(可能 是1个涟漪或多个涟漪;涟漪的波源结点与结点η之间必需有链接），即，对结点η，存在至少 一个1 < r < Nr，满足SR(r) = 1，A(E(r)，n) = 1，R(r) 2 CkBM(E(r)，η)，那么，根据所有的单目标 函数，将这些新到的涟漪彼此进行Pareto优劣比较，再与结点η的已有涟漪进行Pareto优劣 比较，以便将这些新到涟漪中的Pareto非劣涟漪(对该结点而言）找出来，以两个涟漪i和j 的Pareto优劣比较为例，分别计算或提取沿涟漪i所对应的路径以及沿涟漪j所对应的路径 从结点S走到结点η的各个单目标函数值，然后按Pareto优劣的定义比较涟漪i和涟漪j的各 个单目标函数值，从而确定涟漪i与涟漪j之间的Pareto优劣关系，只有当一个新到涟漪与 所有其它新到涟漪以及结点η的已有涟漪相比都是Pareto非劣的，这个新到涟漪对结点η来 说才是Pareto非劣的；然后由每个Pareto非劣的新到涟漪在结点η上激发产生一个新的涟 漪，并对新涟漪的状态进行相应的设置;对结点η上的一个由涟漪i所激发出的新涟漪的设 置主要如下：当前涟漪数量加1(即，Nr = Nr+1)，为新涟漪Nr设置E(Nr) = n，T(NR) = i，R(Nr)= R(i)-CkBM(E(i)，n)，并根据沿涟漪i所对应的路径从结点S走到结点η的各个单目标函数值 来设置新涟漪Nr的适应度向量（以用于今后的Pareto优劣比较），新涟漪Nr的活跃状态需如 下设置：如果结点η不是终点（即，η矣D)，则设置新涟漪Nr为活跃涟漪，即，Sr(Nr) = 1;否则 (即，n = D)，设置新涟漪Nr为不活跃涟漪，即，Sr(Nr)=0。换句话说，非终点的结点所产生的 涟漪都初始化为活跃涟漪，而终点D所产生的涟漪都是不活跃涟漪。
[0054](步骤七）：对任何一个活跃涟漪，如果该涟漪已经到达了与其波源结点有链接的 所有其它结点(不考虑该涟漪所对应路径已包含的结点），即，对任何一个r，1 < r < NR，SR(r) =1，如果对每一个满足A(E(r)，n) = l的结点n，都有R(r) 2 CkBM(E(r)，n)，那么，设置涟漪r 变为不活跃，即，设置SR(r)=0,或者说涟漪r消亡了；然后回到(步骤四）。
[0055] (步骤八）：根据终点D产生的所有涟漪，确定从起点S到终点D的完整Pareto前沿， 即，终点D所产生的每一个涟漪都对应一个Pareto最优解。如果(步骤一）中人为增加了一个 求和单目标函数扣，则从已确定出的(N_+l)维Pareto前沿中筛选出不考虑该求和单目 标函数fNQbj+i的Nobj维Pareto前沿，就是原始问题中从起点S至I」终点D的完整Pareto前沿。
[0056] 图2给出了本发明的方法在求解多目标一到多路径优化问题（即，从一个给定起点 到路网中每一个其它结点）时所包括的主要步骤。对比图1和图2可以看出，求解多目标一到 多路径优化问题与求解多目标一到一路径优化问题的基本步骤大都是一样的，细微的区别 只在于(步骤四）、（步骤六)和(步骤八）。
[0057] 在(步骤四）中，对求解多目标一到一路径优化问题而言，涟漪接力赛的结束条件 是:涟漪接力赛中已经没有任何活跃涟漪，或者所有活跃涟漪与终点上已有的涟漪相比都 不是Pareto非劣的；而对求解多目标一到多路径优化问题而言，涟漪接力赛的结束条件是： 涟漪接力赛中已经没有任何活跃涟漪(因为一到多问题中没有指定的单一终点，即，起点以 外的所有其它结点都是终点，所以结束条件不与任何单一终点有关系）。
[0058] 在(步骤六）中，对求解多目标一到一路径优化问题而言，终点上所产生的新涟漪 都是不活跃涟漪(从而避免不必要的计算量，以提高计算效率）；而对求解多目标一到多路 径优化问题而言，任何结点上所激发产生出的新涟漪都是活跃涟漪(这样才能确保求解出 从起点到网络中每一个其它结点的完整Pareto前沿）。
[0059] 在(步骤八）中，对求解多目标一到一路径优化问题而言，只需要回溯终点上所产 生的所有涟漪，以确定从起点到终点的完整Pareto前沿;而对求解多目标一到多路径优化 问题而言，则需要回溯每一个非起点的结点上所产生的所有涟漪，从而确定从起点到网络 中每一个其它结点的完整Pareto前沿。
[0060] 图3给出了一个应用本发明的方法对一个双目标最小化一到一路径优化问题求解 从结点S到结点D的完整Pareto前沿的求解过程示例。各条链接的两个目标权重值(gl，g2) 标注在时刻t = l的路网中。在图3的例子中，一条路径的某个单目标函数值定义为该路径上 所有链接的该单目标权重值的求和。本发明的方法中的多目标涟漪扩散算法是在所给路网 中开展一场涟漪扩散接力赛。接力赛开始于以起点S为波源的初始涟漪R1。初始涟漪R1沿起 点S的3条链接按预设的速度由近及远地扩散。
[0061 ]初始涟漪R1在时刻t = 2分别先后到达了结点2、结点1和结点3。由于结点2、结点1 和结点3此时还没产生过任何涟漪，所以初始涟漪R1对这3个结点来说，都是Pareto非劣的， 因而初始涟漪R1分别在结点2上激发出新涟漪R2，在结点1上激发出新涟漪R3，在结点3上激 发出新涟漪R4。新涟漪各自沿路网中的相关链接开始扩散。而初始涟漪R1因为已经到达了 与其波源结点S相连的所有结点，所以时刻t = 2以后，初始涟漪R1就消亡了（即，变为不活 跃)。
[0062] 在时刻t = 3，涟漪R2到达了终点D。此时终点D还未产生过任何涟漪，所以涟漪R2对 终点D来说是Pareto非劣的。于是通过回溯涟漪R2,得到路径S-2-D是一个Pareto最优解， 同时涟漪R2在终点D激发出一个不活跃涟漪(在针对一到一的多目标路径优化问题的涟漪 扩散算法中，终点只能产生不活跃涟漪）。涟漪R2在时刻t = 3也到达了结点1，但是因为涟漪 R2与结点1上已有的涟漪R3相比（与R3被激发时的状态相比）不是Pare to非劣的，所以涟漪 R2没能在结点1上激发出新涟漪。在时刻t = 3，涟漪R3到达了结点2，因为涟漪R3与结点2上 已有的涟漪R2相比是Pareto非劣的，所以涟漪R3在结点2激发出一个新涟漪R5。
[0063] 在时刻t = 4，涟漪R4到达了终点D。因为涟漪R4与其它同期到达终点D的涟漪（即， 涟漪R3和涟漪R5)以及终点D上已有的涟漪相比是Pareto非劣的，所以通过回溯涟漪R4,得 到路径S-3-D是一个Pareto最优解，同时涟漪R4在终点D激发出一个不活跃涟漪。在时刻t =4,涟漪R3也到达了终点D。但是由于涟漪R3与终点D上已有的涟漪相比（由R2激发产生的 不活跃涟漪)不是Pareto非劣的，所以涟漪R3所对应的路径不是Pareto最优解。虽然涟漪R5 在时亥ljt = 4也到达了终点D，但与涟漪R4在终点D所激发的不活跃涟漪相比，涟漪R5不是 Pareto非劣的，所以涟漪R5所对应的路径也不是Pareto最优解。在时刻t = 4，涟漪R4也到达 了结点2，因为涟漪R4与结点2上已有的涟漪相比是Pareto非劣的，所以涟漪R4在结点2上激 发出新涟漪R6。在时刻t = 4，涟漪R2到达了结点3，但因为涟漪R2与结点3上已有的涟漪相比 不是Pareto非劣的，所以涟漪R2没能在结点3上激 发出新涟漪。此时，因为涟漪R2已经到达 了与其波源结点2相连的所有结点（无需考虑涟漪R2所对应路径中已包含的结点，如起点 S)，所以时刻t = 4以后，涟漪R2就消亡了。同理，涟漪R3、R4和R5在时刻t = 4以后都消亡了。 [0064] 在时刻t = 5，涟漪R6到达了终点D。因为涟漪R6与终点D上已有的涟漪相比是 Pareto非劣的，所以通过回溯涟漪R6,得到路径S43-2-D是一个Pareto最优解，同时涟漪 R6在终点D激发出一个不活跃涟漪。涟漪R6在时刻t = 5也到达了结点1，因为涟漪R6与结点1 上已有的涟漪相比是Pareto非劣的，所以涟漪R6在结点1上激发出新涟漪R7。此时，因为涟 漪R6已经到达了与其波源结点2相连的所有结点，所以时刻t = 5以后，涟漪R6就消亡了。 [0065] 在时刻t = 6，涟漪R7到达了终点D。因为涟漪R7与终点D上已有的涟漪相比不是 Pareto非劣的，所以涟漪R7所对应的路径不是Pareto最优解。此时，因为涟漪R7已经到达了 与其波源结点1相连的所有结点，所以时刻t = 6以后，涟漪R7就消亡了。
[0066]至此，涟漪接力赛中已经没有任何活跃涟漪了，所以优化计算结束。图3问题中的 完整Pareto前沿就由终点D上所产生的3个不活跃涟漪(涟漪R2、R4和R6各激发出一个，分别 对应路径S-2-D，S-3-D，和S-3-2-D)来确定，即，该完整Pareto前沿由3个点构成。 [0067]图4给出了一组本发明的方法与现有的A0F方（即，重构单目标函数法)和PCR方法 (即，Pareto标准评级法)的对比实验的结果。图4的实验是求解一个双目标路径优化问题， 其两个目标函数，即gl和g2，都需要被最小化。图4中，每个麻子三角形代表一个由A0F方法 找到的Pareto最优解，每个白色圆圈代表一个由PCR方法最终输出的当前非劣解，而每个黑 色正方形代表一个由本发明的方法所找到的Pareto最优解，所有黑色正方形一起组成了图 4实验的完整Pareto前沿。
[0068]由图4可以看出，在对比实验中，A0F方法找到了Pareto前沿凸面上的4个Pareto最 优解，但是却没能找出Par e to前沿凹面上的Par e t 〇最优解。而凹面上的那个Par e to最优解 显然代表着两个目标函数之间最理想的折中方案，很可能是决策者最希望达到的效果。图4 的实验结果表明，虽然A0F方法得到的结果都是Pareto最优解，但是A0F方法并不能充分满 足决策者的需求(因为A0F方法只找到了部分的Pareto前沿）。
[0069]由图4还可以看出，在对比实验中，PCR方法最终输出了的5个当前非劣解（完整 Pareto前沿也有5个Pare to最优解），而且这5个当前非劣解所组成的阵面的形状与完整 Pareto前沿的形状也很相似。但是，这5个当前非劣解中有3个根本就不是Pareto最优解。所 以，显而易见，PCR方法也无法为决策者提供最理想的决策支持。
[0070]基于本发明的方法所求解出的完整Pareto前沿能够为决策者提供全面、准确的决 策支持。
【主权项】
1. 一种求解完整ParetO前沿的多目标优化方法，用以解决为多目标路径优化问题求解 完整的（而不是部分的、或近似的）Pareto前沿的技术问题，其特征是:所述的方法的求解过 程可以形象地比喻成在路网中模拟一场涟漪扩散接力赛（比喻不是必须的，只是为了更加 形象和容易理解;换句话说，核心是比喻所对应的计算过程的内容，这些内容可以被比喻成 其它任何恰当的事物或过程，或者不用比喻，而是纯粹用抽象的数学变量和术语表述）；涟 漪接力赛开始于一个以给定起点为波源的初始涟漪;涟漪沿路网中的链接按预设的速度扩 散；当一个涟漪扩散到一条链接的另一端的结点时，如果该涟漪所代表的路径与该结点上 已产生的所有涟漪所代表的路径相比是Pareto非劣的，则一个新涟漪将以该结点为波源被 激发出来并扩散;当一个涟漪已经到达了与其波源结点相连的所有结点，该涟漪就消亡；当 接力赛中的所有涟漪都消亡了，则通过回溯一个结点上的所有涟漪，就能得到从给定起点 到该结点的完整Pareto前沿。2. 根据权利要求1所述的求解完整Pareto前沿的多目标优化方法，其特征是:对于多目 标一到一路径优化问题（即，从一个给定起点到一个给定终点），所述的方法可以求解出从 给定起点到给定终点的完整Pareto前沿。 假设有一个网络系统（可以是现实物理网络系统，如：公路网，也可以是抽象虚拟网络 系统，如:决策树），包含Nn个结点；结点间的链接可由一个邻接矩阵A表示，其中的元素A(i， j) = 1表示结点i和结点j之间存在一条链接，而A(i，j) = 0则表示结点i和结点j之间没有链 接;假设结点i和结点j之间存在一条链接，则该链接有Nobj个目标权重值，可分别记为Ck( i， j)，k=l，-_，Nc^;假设P表示一条路径，路径P包含见2 2个结点，？（1)表示路径？的第1个结 点，1 < i <Nl，1 <P(iHNN;对于多目标一到一路径优化问题（即，从一个给定起点到一个给 定终点），假设结点S是给定起点，而结点D是给定终点，那么需要求解如下最小化问题：其中 P(I) = S,P(Nl)=D, P(i)关 P(j)，if i关 j，i = l，...，NL，andj = l，...，NL， A(P(i)，P(i+l)) = l， ΩΡ表示所有可能路径的集合，fk是第k个单目标函数，k=l，-_，N_，fk可以是任何形式 的满足下列条件的函数： 如果fk(PiH fk(P2)，那么fk(Pi+PH fk(P2+P)， 如果 fk(Pi)<fk(P2)，那么 fk(Pi+P)<fk(P2+P)。 对于上述多目标一到一路径优化问题，所述的方法主要包括以下几个步骤： (步骤一)如果在个单目标函数中至少存在一个求和单目标函数，即，至少存在一个 fk具有如下函数形式则选一个求和单目标函数用以标定涟漪接力赛中的路径长度，假设第kBM个单目标函数 被选中；如果在Ncibj个单目标函数中没有求和单目标函数，则人为增加一个具有上述函数形 式的求和单目标函数fNClbj + l，用以标定接力赛中的路径长度，因而设置kBM=Ncibj + l，简单起 见，可以定义fk^+1(P)=NL-l，也就是说，每条链接的第(N_+l)个目标权重值都等于1，即， 对任意I < i < Nn和I < j < Nn，如果A( i，j) = 1，则定义C_j+1 (i，j) = 1;然后预设一个涟漪扩 散速度V。 (步骤二)初始化各种用以记录涟漪接力赛中的涟漪的状态的变量。 (步骤三）以起点S为波源生成一个初始涟漪（即，第一个活跃涟漪），设置当前涟漪数量 为Nr=I，设置第一个涟漪的波源为E(I) = S(即，起点为波源），设置第一个涟漪的半径为R (1) = 〇，设置第一个涟漪的状态为Sr(1 ) = 1 (即，活跃），设置第一个涟漪的激发涟漪为T(1) =〇(即，第一个涟漪不由任何涟漪激发，而是自发产生的），设置第一个涟漪的适应度向量 为其所对应路径的各单目标函数值(即O向量，因为第一个涟漪所对应路径是S-S);设定当 前仿真时刻为t = 0,以便开始涟漪接力赛。 (步骤四）：判断涟漪接力赛是否该结束?如果涟漪接力赛中已经没有任何活跃涟漪，或 者所有活跃涟漪与终点D上已有的涟漪相比都不是Pareto非劣的，即，对任意一个I < r < Nr，都有Sr(r) = 0 (即，涟漪r不活跃），或者，对任一 I ^ r d Sr(r) = 1，如果涟漪r所对应的 路径与终点D上已有涟漪所对应的路径相比都不是Pareto非劣的，则到步骤(八）；否则，到 步骤(五）。 (步骤五）：更新仿真时间t = t+l;对每个活跃涟漪按预设的涟漪扩散速度和一个时间 单位长度更新半径，即，对任意一个I < r < Nr，如果SR(r) = l，则更新R(r)=R(r)+v。 (步骤六）：对任何一个结点n，如果在当前这个时间单位长度内有涟漪到达(可能是1个 涟漪或多个涟漪;涟漪的波源结点与结点η之间必需有链接），即，对结点n，存在至少一个1 <1'<咏，满足5[?(1') = 1，厶似1')，11) = 1，1?(1')2〇1?似1')，11)，那么，根据所有的单目标函数， 将这些新到的涟漪彼此进行Pareto优劣比较，再与结点η的已有涟漪进行Pareto优劣比较， 以便将这些新到涟漪中的Pareto非劣涟漪（对该结点而言）找出来，以两个涟漪i和j的 Pareto优劣比较为例，分别计算或提取沿涟漪i所对应的路径以及沿涟漪j所对应的路径从 结点S走到结点η的各个单目标函数值，然后按Pare to优劣的定义比较涟漪i和涟漪j的各个 单目标函数值，从而确定涟漪i与涟漪j之间的Pareto优劣关系，只有当一个新到涟漪与所 有其它新到涟漪以及结点η的已有涟漪相比都是Pareto非劣的，这个新到涟漪对结点η来说 才是Pareto非劣的；然后由每个Pareto非劣的新到涟漪在结点η上激发产生一个新的涟漪， 并对新涟漪的状态进行相应的设置;对结点η上的一个由涟漪i所激发出的新涟漪的设置主 要如下：当前涟漪数量加1 (即，Nr = Nr+ 1)，为新涟漪Nr设置E (Nr) = η，T (Nr ) = i，R(Nr) = R (i)-CkBM(E(i)，n)，并根据沿涟漪i所对应的路径从结点S走到结点η的各个单目标函数值来 设置新涟漪Nr的适应度向量（以用于今后的Pareto优劣比较），新涟漪Nr的活跃状态需如下 设置:如果结点η不是终点（即，η判），则设置新涟漪Nr为活跃涟漪，即，Sr(Nr) = 1;否则（BP， n = D)，设置新涟漪Nr为不活跃涟漪，即，Sr(Nr)=0。换句话说，非终点的结点所产生的涟漪 都初始化为活跃涟漪，而终点D所产生的涟漪都是不活跃涟漪。 (步骤七）：对任何一个活跃涟漪，如果该涟漪已经到达了与其波源结点有链接的所有 其它结点(不考虑该涟漪所对应路径已包含的结点），即，对任何一个r，I < r < Nr，SR(r) = 1， 如果对每一个满足A(E(r)，n) = 1的结点n，都有R(r) 2 CkBM(E(r)，n)，那么，设置涟漪r变为 不活跃，即，设置SR(r)=0,或者说涟漪r消亡了；然后回到(步骤四）。 (步骤八）：根据终点D产生的所有涟漪，确定从起点S到终点D的完整Pareto前沿，即，终 点D所产生的每一个涟漪都对应一个Pareto最优解。如果(步骤一）中人为增加了一个求和 单目标函数fNQbj+1，则从已确定出的(NQbj+l)维Pareto前沿中筛选出不考虑该求和单目标函 数fkibj+i的Ncibj维Pareto前沿，就是原始问题中从起点S至丨」终点D的完整Pareto前沿。3.根据权利要求1所述的求解完整Pareto前沿的多目标优化方法，其特征是:对于多目 标一到多路径优化问题（即，从一个给定起点到路网中每一个其它结点），所述的方法只需 要运行一次，就可以求解出从给定起点到路网中所有其它每一个结点的完整Pareto前沿。 假设网络系统包含Nn个结点，则多目标一到多路径优化问题在数学描述上，可以当作 (Nn-I)个独立的多目标一到一路径优化问题，每个一到一问题中的终点为起点以外的其它 (Nn-I)个结点中的某一个。在求解多目标一到多路径优化问题时，所述的方法不需要对每 个一到一问题进行单独求解，而是按以下主要步骤，进行一次性的计算即可： (步骤一)如果在个单目标函数中至少存在一个求和单目标函数，即，至少存在一个 fk具有如下函数形式则选一个求和单目标函数用以标定涟漪接力赛中的路径长度，假设第kBM个单目标函数 被选中；如果在Ncibj个单目标函数中没有求和单目标函数，则人为增加一个具有上述函数形 式的求和单目标函数fNClbj + l，用以标定接力赛中的路径长度，因而设置kBM=Ncibj + l，简单起 见，可以定义fk^+1(P)=NL-l，也就是说，每条链接的第(N_+l)个目标权重值都等于1，即， 对任意I < i < Nn和I < j < Nn，如果A( i，j) = 1，则定义C_j+1 (i，j) = 1;然后预设一个涟漪扩 散速度V。 (步骤二)初始化各种用以记录涟漪接力赛中的涟漪的状态的变量。 (步骤三）以起点S为波源生成一个初始涟漪（即，第一个活跃涟漪），设置当前涟漪数量 为Nr=I，设置第一个涟漪的波源为E(I) = S(即，起点为波源），设置第一个涟漪的半径为R (1) = 〇，设置第一个涟漪的状态为Sr(1 ) = 1 (即，活跃），设置第一个涟漪的激发涟漪为T(1) =〇(即，第一个涟漪不由任何涟漪激发，而是自发产生的），设置第一个涟漪的适应度向量 为其所对应路径的各单目标函数值(即0向量，因为第一个涟漪所对应路径是S-S);设定当 前仿真时刻为t = 0,以便开始涟漪接力赛。 (步骤四）：判断涟漪接力赛是否该结束？如果涟漪接力赛中已经没有任何活跃涟漪， 即，对任意一个I <r<NR，都有SR(r)=0(即，涟漪r不活跃），则到步骤(八）；否则，到步骤 (五)。 (步骤五）：更新仿真时间t = t+l;对每个活跃涟漪按预设的涟漪扩散速度和一个时间 单位长度更新半径，即，对任意一个I < r < Nr，如果SR(r) = l，则更新R(r)=R(r)+v。 (步骤六）：对任何一个结点n，如果在当前这个时间单位长度内有涟漪到达(可能是1个 涟漪或多个涟漪;涟漪的波源结点与结点η之间必需有链接），即，对结点n，存在至少一个1 <1'<咏，满足5[?(1') = 1，厶似1')，11) = 1，1?(1')2〇1?似1')，11)，那么，根据所有的单目标函数， 将这些新到的涟漪彼此进行Pareto优劣比较，再与结点η的已有涟漪进行Pareto优劣比较， 以便将这些新到涟漪中的Pareto非劣涟漪（对该结点而言）找出来，以两个涟漪i和j的 Pareto优劣比较为例，分别计算或提取沿涟漪i所对应的路径以及沿涟漪j所对应的路径从 结点S走到结点η的各个单目标函数值，然后按Pare to优劣的定义比较涟漪i和涟漪j的各个 单目标函数值，从而确定涟漪i与涟漪j之间的Pareto优劣关系，只有当一个新到涟漪与所 有其它新到涟漪以及结点η的已有涟漪相比都是Pareto非劣的，这个新到涟漪对结点η来说 才是Pareto非劣的；然后由每个Pareto非劣的新到涟漪在结点η上激发产生一个新的活跃 涟漪(即，所有新激发产生出的涟漪都是活跃涟漪），并对新涟漪的状态进行相应的设置;对 结点η上的一个由涟漪i所激发出的新涟漪的设置主要如下：当前涟漪数量加1(即，Nr = Nr+ 1)，然后为新涟漪Nr设置Sr(Nr) = l，E(NR)=n，T(NR) = i，R(NR)=R(i)-Ck_(E(i)，n)，并根据 沿涟漪i所对应的路径从结点S走到结点η的各个单目标函数值来设置新涟漪Nr的适应度向 量（以用于今后的Pareto优劣比较）。 (步骤七）：对任何一个活跃涟漪，如果该涟漪已经到达了与其波源结点有链接的所有 其它结点(不考虑该涟漪所对应路径已包含的结点），即，对任何一个r，I < r < Nr，SR(r) = 1， 如果对每一个满足A(E(r)，n) = 1的结点n，都有R(r) 2 CkBM(E(r)，n)，那么，设置涟漪r变为 不活跃，即，设置SR(r)=0,或者说涟漪r消亡了；然后回到(步骤四）。 (步骤八）：对任意一个结点（非起点），从起点到该结点的完整Pareto前沿由该结点上 所产生的所有涟漪来确定，即，该结点所产生的每一个涟漪都对应一个Pareto最优解。如果 (步骤一）中人为增加了一个求和单目标函数&(^ +1，则从已确定出该结点的（N_ + l)维 Pareto前沿中筛选出不考虑该求和单目标函数fNQbj+i的Ncibj维Pareto前沿，就是原始问题中 从起点到该结点的完整Pareto前沿。4. 根据权利要求1和权利要求2所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以采用各种恰当的数学表述形式(例如，网络中的链接可以不用邻接矩阵 A表示，而是采用链接向量表的数据结构;所使用的各个变量符号本身不是必须的，核心是 变量的意义以及对变量的操作计算过程，例如，（步骤五）中更新涟漪半径，即，R(r)=R(r) + v，可以用任意变量符号来改写，如，W(m)=W(m)+z，甚至不用"涟漪"和"半径"这些词汇字 目艮，而是抽象地说成：向量R的第r个元素R(r)增加V，其效果是一样的）。5. 根据权利要求1和权利要求3所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以采用各种恰当的数学表述形式。6. 根据权利要求1和权利要求2所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以应用于各种能够转化为多目标路径优化的问题(例如:多目标组合优化 和多目标决策管理问题）。7. 根据权利要求1和权利要求3所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以应用于各种能够转化为多目标路径优化的问题。8. 根据权利要求1和权利要求2所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以采用各种恰当的硬件计算设备和软件编程技术来实现。9. 根据权利要求1和权利要求3所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以采用各种恰当的硬件计算设备和软件编程技术来实现。
【专利摘要】一种求解完整Pareto前沿的多目标优化方法。属于计算机算法和管理优化领域。目的是为多目标路径优化问题(或等效问题)求解出完整的(而不是部分、或近似的)Pareto前沿。本发明的方法在路网中模拟一场涟漪扩散接力赛；接力赛开始于一个以给定起点为波源的初始涟漪；涟漪沿路网中的链接按预设的速度扩散；当一个涟漪扩散到一条链接的另一端的结点时，如果该涟漪所代表的路径与该结点上已产生的所有涟漪所代表的路径相比是Pareto非劣的，则一个新涟漪将以该结点为波源被激发出来并扩散；当一个涟漪已经到达了与其波源结点相连的所有结点，该涟漪就消亡；当接力赛中所有涟漪都消亡了，则通过回溯一个结点上的所有涟漪，就能得到从给定起点到该结点的完整Pareto前沿。
【IPC分类】G06Q10/04
【公开号】CN105488601
【申请号】CN201610030464
【发明人】胡小兵, 廖建勤
【申请人】北京师范大学, 廖建勤
【公开日】2016年4月13日
【申请日】2016年1月19日
【技术领域】：
[0001]本发明提供了一种求解完整Pareto前沿的多目标优化方法，属于计算机算法和管 理优化领域。
【背景技术】：
[0002]多目标优化问题(multi-objective optimization problem，简称Μ0Ρ)涉及生活 的方方面面，相关的求解方法对解决政治、金融、军事、环境、生产制造、社会保障等各方面 的规划决策问题起着至关重要的作用。Pareto最优解和Pare to前沿是Μ0Ρ中的核心概念，它 们起源于经济学中对收入分配优化的研究。简单地说，对于一个给定的解，如果不存在任何 一个解在各个指标上都不比它差，而且至少在一个指标上比它好，则这个给定解就是一个 Pare to最优解。所有Pare to最优解在目标函数空间里的投影就构成了完整Par e to前沿。求 解MOP的关键就在于寻找Pareto前沿。然而，现有的绝大多数MOP求解方法都只能寻找部分 的、或近似的Pareto前沿。
[0003]现有的求解Μ0Ρ的方法大体可以分为三大类：重构单目标函数法（aggregate objective function，简称A0F)，约束目标函数法（constrained objective function，简 称C0F)，和Pareto标准评级法(Pareto-compliant ranking，简称PCR) aAOF会把MOP中的所 有原始目标函数整合到一个单一的重构目标函数中，然后针对这个重构单目标函数进行单 目标优化，即可得到一个Pareto最优解。然而，定义重构单目标函数时存在主观性，并且很 多重构单目标函数的定义从理论上就决定了A0F不可能找到Pareto前沿上的凹面所对应的 Pareto最优解。C0F把Μ0Ρ转化成一个带约束的单目标优化问题，即仅针对Μ0Ρ的一个目标进 行优化，而把所有其它目标当成额外的约束条件。PCR基本都是基于种群的各种进化算法， 通过筛选和进化种群中的当前非劣解，在种群进化结束后将当前非劣解集作为近似的 Pareto前沿输出。PCR虽然没有A0F的问题（如主观性等），但A0F的输出肯定是Pareto最优 解，而PCR的输出有可能根本就不包含任何Pareto最优解。
[0004] 对一些基于非线性重构单目标函数的A0F而言，对任一给定的Pareto最优解，在理 论上总可以证明存在一组重构参数，使得A0F的输出为该指定的Pareto最优解。然而，却缺 少实际有效可行的理论和方法保证找出能够对应涵盖所有Pareto最优解的重构参数集合。 C0F在理论上，通过将优化目标转化成约束条件，是可能求解完整Pareto前沿的。但是和A0F 的情况一样，C0F缺少实际有效可行的理论和方法来确定所需的转化参数集合，因而难以确 保所生成的约束条件能找到完整Pareto前沿。在目前为数不多的关于求解完整Pareto前沿 的研究报导中，基本都是通过精心设计针对特殊类型问题的A0F重构参数集合或C0F转化参 数集合，从而把所有Pareto最优解都找出来。尽管PCR是Μ0Ρ研究中最热门的方法，但是因为 其所依赖的进化算法具有随机特性，所以PCR在理论上根本不能保证找到完整Pareto前沿。
[0005] 最近在文献[1]和文献[2]中提出了一种利用涟漪扩散算法求解前k个单目标最优 解，进而再基于各个目标函数下的前k个单目标最优解求解Μ0Ρ的完整Pareto前沿的方法。 需要强调的是：（1)文献[1]和文献[2]中的涟漪扩散算法本身不能解决Μ0Ρ，而是仅仅针对 单目标优化问题的，即，文献[1 ]和文献[2]中的涟漪扩散算法是单目标涟漪扩散算法；（2) 为了求解MOP的完整Pareto前沿，需要在各个目标函数下多次运行文献[1 ]和文献[2]中的 单目标涟漪扩散算法；（3)在多目标路径优化问题中，每当求解给定起点到另外一个网络结 点的完整Pareto前沿时，都需要单独运行一次文献[1]或文献[2]中的方法，换句话说，假设 路网中有Nn个结点，其中一个结点为给定起点，如果我们需要求解给定起点到另外(Nn-1 )个 结点中每一个结点的完整Pareto前沿，那么我们总共需要运行(Nn-1)次文献[1]或文献[2] 中的方法(在每一次方法运行中，又需要运行若干次单目标涟漪扩散算法）。所以文献[1]和 文献[2]中求解完整Pareto前沿的方法是非常低效的。
[0006] 本发明将提出一种真正的多目标涟漪扩散算法，其求解效果是:仅仅需要运行一 次本发明的方法，就可以求解出从给定起点到所有另外(Nn-ι)个结点中每一个结点的完整 Pareto 前沿。
[0007] [1]Χ·B·Hu，M·Wang，and E·Di Paolo，"Calculating Complete and Exact Pareto Front for Multi-Objective Optimization：A New Deterministic Approach for Discrete Problems"，IEEE Transactions on Systems?Man and Cybernetics，Part B，Vol.43，No.3，pp:1088-1101，2013.
[0008] [2]胡小兵，《求解完整Pareto前沿的多目标优化新方法研究》，国家自然科学基金 面上研究项目（项目号:61472041)，2015年1月。
【发明内容】
：
[0009] 本发明的目的是要提供一种求解完整Pareto前沿的多目标优化方法。对于多目标 路径优化问题，假设路网中有Nn个结点，本发明的方法具有如下求解效果:仅仅需要运行一 次本发明的方法，就可以求解出从给定起点到所有另外(Nn-Ι)个结点中每一个结点的完整 Pareto 前沿。
[0010]假设有一个网络系统（可以是现实物理网络系统，如：公路网，也可以是抽象虚拟 网络系统，如:决策树），包含Nn个结点。结点间的链接可由一个邻接矩阵A表示，其中的元素 A(i，j) = 1表示结点i和结点j之间存在一条链接;A(i，j) =0则表示结点i和结点j之间没有 链接。假设结点i和结点j之间存在一条链接，则该链接有N〇bj个目标权重值，可分别记为Ck (1，」）汰=1，一，他^。假设?表示一条路径，路径?包含见2 2个结点，？（1)表示路径？的第1个 结点，l<i<NL，l<P(iHNN。
[0011] 对于多目标一到一路径优化问题（即，从一个给定起点到一个给定终点），假设结 点S是给定起点，而结点D是给定终点，那么我们需要求解如下最小化问题：
[0012]
⑴
[0013] 其中
[0014] p(i)=s，P(Nl)=D， (2)
[0015] P(i)关P( j)，if i 关 j，i = l，· · ·，NL，and j = 1，· · ·，Nl， (3)
[0016] A(P(i)，P(i+l)) = l， (4)
[0017] ΩΡ表示所有可能路径的集合，fk是第k个单目标函数，k=l，-_，Nc^，fk可以是任何 形式的满足下列条件的函数：
[0018] 如果f^Pi) <fk(P2)，那么f^Pi+P) <fk(P2+P)， (5)
[0019] 如果 f^PiXf^p〗），那么 fk(p1+p)<fk(p2+p)。 (6)
[0020] 对于多目标一到多路径优化问题（即，从一个给定起点到路网中每一个其它结 点），在问题的数学描述上，可以当作(Nn-1)个独立的多目标一到一路径优化问题，每个一 到一问题中的终点为起点以外的其它(Nn-1)个结点中的某一个。显然，一到一问题只是一 到多问题的一个部分或者一个特例。所以，能解决一到多问题的方法，必然也能够解决一到 一问题。
[0021] 本发明为解决上述的多目标一到多路径优化问题，将通过下述的方案来实现。本 发明的方法在路网中模拟一场涟漪扩散接力赛;接力赛开始于一个以给定起点为波源的初 始涟漪;涟漪沿路网中的链接按预设的速度扩散；当一个涟漪扩散到一条链接的另一端的 结点时，如果该涟漪所代表的路径与该结点上已产生的所有涟漪所代表的路径相比是 Pareto非劣的，则一个新涟漪将以该结点为波源被激发出来并扩散；当一个涟漪已经到达 了与其波源结点相连的所有结点，该涟漪就消亡；当接力赛中的所有涟漪都消亡了，则通过 回溯一个结点上的所有涟漪，就能得到从给定起点到该结点的完整Pareto前沿。
[0022]为求解出从给定起点到所有另外(Nn-1)个结点中每一个结点的完整Pareto前沿， 本发明的方法的一次性优化计算过程包括以下几个主要步骤：
[0023] (步骤一)如果在个单目标函数中至少存在一个求和单目标函数，即，至少存在 一个fk具有如下函数形式
[0024]
(7)
[0025] 则选一个求和单目标函数用以标定涟漪接力赛中的路径长度，假设第kBM个单目标 函数被选中；如果在Ncibj个单目标函数中没有求和单目标函数，则人为增加一个具有函数形 式(7)的求和单目标函数fNClbj+l，用以标定接力赛中的路径长度，因而设置kBM = N〇bj + l，简单 起见，可 以定义fNc^+1(P)=NL-l，也就是说，每条链接的第(N_+l)个目标权重值都等于1， 即，对任意1 < i < Nn和1 < Nn，如果A( i，j) = 1，则定义(：_+1 (i，j) = 1;然后预设一个涟漪 扩散速度V。
[0026](步骤二)初始化各种用以记录涟漪接力赛中的涟漪的状态的变量。
[0027] (步骤三）以起点S为波源生成一个初始涟漪（即，第一个活跃涟漪），设置当前涟漪 数量为Nr=1，设置第一个涟漪的波源为E(1) = S(即，起点为波源），设置第一个涟漪的半径 为R(1) =〇，设置第一个涟漪的状态为Sr(1 ) = 1 (即，活跃），设置第一个涟漪的激发涟漪为T (1)=0(即，第一个涟漪不由任何涟漪激发，而是自发产生的），设置第一个涟漪的适应度向 量为其所对应路径的各单目标函数值(即〇向量，因为第一个涟漪所对应路径是S-S);设定 当前仿真时刻为t = 0，以便开始涟漪接力赛。
[0028] (步骤四）：判断涟漪接力赛是否该结束？如果涟漪接力赛中已经没有任何活跃涟 漪，即，对任意一个KHNr，都有SR(r) = 0,即涟漪r不活跃，则到步骤(八）；否则，到步骤 (五)。
[0029] (步骤五）：更新仿真时间t = t+l;对每个活跃涟漪按预设的涟漪扩散速度和一个 时间单位长度更新半径，即，对任意一个1 < r < Nr，如果SR(r) = l，则更新R(r)=R(r)+v。
[0030] (步骤六）：对任何一个结点n，如果在当前这个时间单位长度内有涟漪到达(可能 是1个涟漪或多个涟漪;涟漪的波源结点与结点η之间必需有链接），即，对结点η，存在至少 一个1 < r < Nr，满足SR(r) = 1，A(E(r)，n) = 1，R(r) 2 CkBM(E(r)，η)，那么，根据所有的单目标 函数，将这些新到的涟漪彼此进行Pareto优劣比较，再与结点η的已有涟漪进行Pareto优劣 比较，以便将这些新到涟漪中的Pareto非劣涟漪(对该结点而言）找出来，以两个涟漪i和j 的Pareto优劣比较为例，分别计算或提取沿涟漪i所对应的路径以及沿涟漪j所对应的路径 从结点S走到结点η的各个单目标函数值，然后按Pareto优劣的定义比较涟漪i和涟漪j的各 个单目标函数值，从而确定涟漪i与涟漪j之间的Pareto优劣关系，只有当一个新到涟漪与 所有其它新到涟漪以及结点η的已有涟漪相比都是Pareto非劣的，这个新到涟漪对结点η来 说才是Pareto非劣的；然后由每个Pareto非劣的新到涟漪在结点η上激发产生一个新的活 跃涟漪（即，所有新激发产生出的涟漪都是活跃涟漪），并对新涟漪的状态进行相应的设置； 对结点η上的一个由涟漪i所激发出的新涟漪的设置主要如下：当前涟漪数量加1 (即，Nr = Nr + 1)，然后为新涟漪咏设置3[?(咏）=^(咏）=11，1'(咏）=丨，1?(咏）=1?(丨）-01^江（丨），11)，并根 据沿涟漪i所对应的路径从结点S走到结点η的各个单目标函数值来设置新涟漪Nr的适应度 向量（以用于今后的Pareto优劣比较）。
[0031](步骤七）：对任何一个活跃涟漪，如果该涟漪已经到达了与其波源结点有链接的 所有其它结点(不考虑该涟漪所对应路径已包含的结点），即，对任何一个r，1 < r < NR，SR(r) =1，如果对每一个满足A(E(r)，n) = l的结点n，都有R(r) 2 CkBM(E(r)，n)，那么，设置涟漪r 变为不活跃，即，设置SR(r)=0,或者说涟漪r消亡了；然后回到(步骤四）。
[0032 ](步骤八）：对任意一个结点（非起点），从起点到该结点的完整Pare to前沿由该结 点上所产生的所有涟漪来确定，即，该结点所产生的每一个涟漪都对应一个Pareto最优解。 如果(步骤一）中人为增加了一个求和单目标函数f N_+1，则从已确定出该结点的(N_+l)维 Pareto前沿中筛选出不考虑该求和单目标函数fNQbj+i的Nobj维Pareto前沿，就是原始问题中 从起点到该结点的完整Pareto前沿。
[0033] 虽然上述(步骤一）到（步骤八)是用于求解多目标一到多路径优化问题（即，从一 个给定起点到路网中每一个其它结点），但是基于(步骤一)到（步骤八），无需任何修改，就 可以求解多目标一到一路径优化问题（即，从一个给定起点到一个给定终点）。不过，为了避 免不必要的计算以提高求解一到一问题的效率，可以对上述（步骤四）、（步骤六)和（步骤 八)进行轻微修改，如下：
[0034](步骤四改）：判断涟漪接力赛是否该结束？如果涟漪接力赛中已经没有任何活跃 涟漪，或者所有活跃涟漪与终点D上已有的涟漪相比都不是Pareto非劣的，即，对任意一个1 < r < Nr，都有SR(r)=0(即，涟漪r不活跃），或者，对任一1 < r < Nr，Sr(i·) = 1，如果涟漪1*所 对应的路径与终点D上已有涟漪所对应的路径相比都不是Pareto非劣的，则到步骤(八）；否 贝1J，到步骤(五）。
[0035](步骤六改）：开始一切同（步骤六），直到:然后由每个Pareto非劣的新到涟漪在结 点η上激发产生一个新的涟漪(可能是活跃涟漪，也可能是不活跃涟漪），新涟漪的其它设置 同（步骤六），惟有新涟漪的活跃状态需如下设置:如果结点η不是终点（即，η矣D)，则设置新 涟漪为活跃涟漪，即，Sr(Nr) = 1;否则（即，n = D)，设置新涟漪为不活跃涟漪，即，Sr(Nr)=0。 换句话说，非终点的结点所产生的涟漪都初始化为活跃涟漪，而终点D所产生的涟漪都是不 活跃涟漪。
[0036] (步骤八改）：根据终点D产生的所有涟漪，确定从起点S到终点D的完整Pareto前 沿，即，终点D所产生的每一个涟漪都对应一个Pareto最优解。如果(步骤一）中人为增加了 一个求和单目标函数fNQbj+1，则从已确定出的(Ncibj+Ι)维Pareto前沿中筛选出不考虑该求和 单目标函数fNQbj+i的Ncibj维Pareto前沿，就是原始问题中从起点S到终点D的完整Pareto前 沿。
[0037] 需要特别强调的是，在描述本发明的方法时，为了更加形象和容易理解，我们将其 比喻成涟漪扩散接力赛，但这个比喻不是必须的，核心是比喻所对应的计算步骤的内容，这 些内容可以被比喻成其它任何恰当的事物或过程，或者不用比喻，而是纯粹用抽象的数学 变量和术语表示，例如，涟漪r的半径:R(r)，我们完全可以不用"涟漪"和"半径"这两个词汇 字眼，而是抽象地说成：向量R的第r个元素 R(r)。
[0038] 同理，在描述本发明的方法时所使用的各个变量符号本身不是必须的，核心是变 量的意义以及对变量的操作计算过程，例如，（步骤五）中更新涟漪半径:R(r)=R(r)+v，可 以用任意变量符号来改写，如:W(m) =W(m)+z，其效果是一样的。
[0039] 本发明的方法在实现上可以采用各种恰当的硬件计算设备(例如：单片机、手机、 个人电脑、大型计算机、计算机网络，等等)和软件编程技术(例如:路网的链接不用邻接矩 阵A表示，而是采用链接向量表的数据结构；可以采用集中式的算法设计思路，也可以采用 分散并行式的算法设计思路;可以采用各种计算机编程语言和软件系统）。
[0040] 本发明的一种求解完整Pareto前沿的多目标优化方法具有以下有益效果:对于任 何可以转化为多目标路径优化的问题，本发明的方法可以求解出完整的（而不是部分的、或 近似的）Pareto前沿;对于多目标一到多路径优化问题（即，从一个给定起点到路网中每一 个其它结点），假设路网有Nn个结点，本发明的方法不需要将其作为(Nn-1)个独立的多目标 一到一路径优化问题（即，从一个给定起点到一个给定终点）分别求解，而是通过一次性的 计算，就可以求解出从给定起点到所有另外(Nn_ 1)个结点中每一个结点的完整Pareto前 沿。
【附图说明】：
[0041] 附图给出本发明的一种求解完整Pareto前沿的多目标优化方法的示意图：
[0042]图1: 一种求解完整Pareto前沿的多目标优化方法的主要步骤示意图（针对一到一 问题）。
[0043]图2:-种求解完整Pareto前沿的多目标优化方法的主要步骤示意图（针对一到多 问题）。
[0044]图3: -种求解完整Pareto前沿的多目标优化方法的求解过程示意图。
[0045]图4: 一种求解完整Pareto前沿的多目标优化方法的求解效果示意图。
【具体实施方式】：
[0046] 下面结合附图，对本发明的一种求解完整Pareto前沿的多目标优化方法所采用的 优选方式做进一步说明。
[0047] 图1给出了本发明的方法在求解多目标一到一路径优化问题（即，从一个给定起点 到一个给定终点)时所包括的主要步骤：
[0048] (步骤一)如果在NQbj个单目标函数中至少存在一个求和单目标函数，即，至少存在 一个fk具有函数形式(7)，则选一个求和单目标函数用以标定涟漪接力赛中的路径长度，假 设第k BM个单目标函数被选中；如果在N〇bj个单目标函数中没有求和单目标函数，则人为增加 一个具有函数形式(7)的求和单 目标函数f NQbj+1，用以标定接力赛中的路径长度，因而设置 kBM=Ncibj+l，简单起见，可以定义fNQbj+i(P) =Nl_1，也就是说，每条链接的第(Ncibj+Ι)个目标 权重值都等于1，即，对任意1 < i < Nn和1 < j < Nn，如果A( i，j) = 1，则定义C_j+1 (i，j) = 1;然 后预设一个涟漪扩散速度v。
[0049] (步骤二)初始化各种用以记录涟漪接力赛中的涟漪的状态的变量。
[0050] (步骤三）以起点S为波源生成一个初始涟漪（即，第一个活跃涟漪），设置当前涟漪 数量为Nr=1，设置第一个涟漪的波源为E(1) = S(即，起点为波源），设置第一个涟漪的半径 为R(1) =〇，设置第一个涟漪的状态为Sr(1 ) = 1 (即，活跃），设置第一个涟漪的激发涟漪为T (1)=0(即，第一个涟漪不由任何涟漪激发，而是自发产生的），设置第一个涟漪的适应度向 量为其所对应路径的各单目标函数值(即〇向量，因为第一个涟漪所对应路径是S-S);设定 当前仿真时刻为t = 0，以便开始涟漪接力赛。
[0051] (步骤四）：判断涟漪接力赛是否该结束？如果涟漪接力赛中已经没有任何活跃涟 漪，或者所有活跃涟漪与终点D上已有的涟漪相比都不是Pareto非劣的，即，对任意一个 1'<咏，者卩有5[?(1')=0(8卩，涟漪1'不活跃），或者，对任一1<1^咏，5[?(1') = 1，如果涟漪1'所对 应的路径与终点D上已有涟漪所对应的路径相比都不是Pareto非劣的，则到步骤（八）；否 贝1J，到步骤(五）。
[0052](步骤五）：更新仿真时间t = t+l;对每个活跃涟漪按预设的涟漪扩散速度和一个 时间单位长度更新半径，即，对任意一个1 < r < Nr，如果SR(r) = l，则更新R(r)=R(r)+v。 [0053](步骤六）：对任何一个结点n，如果在当前这个时间单位长度内有涟漪到达(可能 是1个涟漪或多个涟漪;涟漪的波源结点与结点η之间必需有链接），即，对结点η，存在至少 一个1 < r < Nr，满足SR(r) = 1，A(E(r)，n) = 1，R(r) 2 CkBM(E(r)，η)，那么，根据所有的单目标 函数，将这些新到的涟漪彼此进行Pareto优劣比较，再与结点η的已有涟漪进行Pareto优劣 比较，以便将这些新到涟漪中的Pareto非劣涟漪(对该结点而言）找出来，以两个涟漪i和j 的Pareto优劣比较为例，分别计算或提取沿涟漪i所对应的路径以及沿涟漪j所对应的路径 从结点S走到结点η的各个单目标函数值，然后按Pareto优劣的定义比较涟漪i和涟漪j的各 个单目标函数值，从而确定涟漪i与涟漪j之间的Pareto优劣关系，只有当一个新到涟漪与 所有其它新到涟漪以及结点η的已有涟漪相比都是Pareto非劣的，这个新到涟漪对结点η来 说才是Pareto非劣的；然后由每个Pareto非劣的新到涟漪在结点η上激发产生一个新的涟 漪，并对新涟漪的状态进行相应的设置;对结点η上的一个由涟漪i所激发出的新涟漪的设 置主要如下：当前涟漪数量加1(即，Nr = Nr+1)，为新涟漪Nr设置E(Nr) = n，T(NR) = i，R(Nr)= R(i)-CkBM(E(i)，n)，并根据沿涟漪i所对应的路径从结点S走到结点η的各个单目标函数值 来设置新涟漪Nr的适应度向量（以用于今后的Pareto优劣比较），新涟漪Nr的活跃状态需如 下设置：如果结点η不是终点（即，η矣D)，则设置新涟漪Nr为活跃涟漪，即，Sr(Nr) = 1;否则 (即，n = D)，设置新涟漪Nr为不活跃涟漪，即，Sr(Nr)=0。换句话说，非终点的结点所产生的 涟漪都初始化为活跃涟漪，而终点D所产生的涟漪都是不活跃涟漪。
[0054](步骤七）：对任何一个活跃涟漪，如果该涟漪已经到达了与其波源结点有链接的 所有其它结点(不考虑该涟漪所对应路径已包含的结点），即，对任何一个r，1 < r < NR，SR(r) =1，如果对每一个满足A(E(r)，n) = l的结点n，都有R(r) 2 CkBM(E(r)，n)，那么，设置涟漪r 变为不活跃，即，设置SR(r)=0,或者说涟漪r消亡了；然后回到(步骤四）。
[0055] (步骤八）：根据终点D产生的所有涟漪，确定从起点S到终点D的完整Pareto前沿， 即，终点D所产生的每一个涟漪都对应一个Pareto最优解。如果(步骤一）中人为增加了一个 求和单目标函数扣，则从已确定出的(N_+l)维Pareto前沿中筛选出不考虑该求和单目 标函数fNQbj+i的Nobj维Pareto前沿，就是原始问题中从起点S至I」终点D的完整Pareto前沿。
[0056] 图2给出了本发明的方法在求解多目标一到多路径优化问题（即，从一个给定起点 到路网中每一个其它结点）时所包括的主要步骤。对比图1和图2可以看出，求解多目标一到 多路径优化问题与求解多目标一到一路径优化问题的基本步骤大都是一样的，细微的区别 只在于(步骤四）、（步骤六)和(步骤八）。
[0057] 在(步骤四）中，对求解多目标一到一路径优化问题而言，涟漪接力赛的结束条件 是:涟漪接力赛中已经没有任何活跃涟漪，或者所有活跃涟漪与终点上已有的涟漪相比都 不是Pareto非劣的；而对求解多目标一到多路径优化问题而言，涟漪接力赛的结束条件是： 涟漪接力赛中已经没有任何活跃涟漪(因为一到多问题中没有指定的单一终点，即，起点以 外的所有其它结点都是终点，所以结束条件不与任何单一终点有关系）。
[0058] 在(步骤六）中，对求解多目标一到一路径优化问题而言，终点上所产生的新涟漪 都是不活跃涟漪(从而避免不必要的计算量，以提高计算效率）；而对求解多目标一到多路 径优化问题而言，任何结点上所激发产生出的新涟漪都是活跃涟漪(这样才能确保求解出 从起点到网络中每一个其它结点的完整Pareto前沿）。
[0059] 在(步骤八）中，对求解多目标一到一路径优化问题而言，只需要回溯终点上所产 生的所有涟漪，以确定从起点到终点的完整Pareto前沿;而对求解多目标一到多路径优化 问题而言，则需要回溯每一个非起点的结点上所产生的所有涟漪，从而确定从起点到网络 中每一个其它结点的完整Pareto前沿。
[0060] 图3给出了一个应用本发明的方法对一个双目标最小化一到一路径优化问题求解 从结点S到结点D的完整Pareto前沿的求解过程示例。各条链接的两个目标权重值(gl，g2) 标注在时刻t = l的路网中。在图3的例子中，一条路径的某个单目标函数值定义为该路径上 所有链接的该单目标权重值的求和。本发明的方法中的多目标涟漪扩散算法是在所给路网 中开展一场涟漪扩散接力赛。接力赛开始于以起点S为波源的初始涟漪R1。初始涟漪R1沿起 点S的3条链接按预设的速度由近及远地扩散。
[0061 ]初始涟漪R1在时刻t = 2分别先后到达了结点2、结点1和结点3。由于结点2、结点1 和结点3此时还没产生过任何涟漪，所以初始涟漪R1对这3个结点来说，都是Pareto非劣的， 因而初始涟漪R1分别在结点2上激发出新涟漪R2，在结点1上激发出新涟漪R3，在结点3上激 发出新涟漪R4。新涟漪各自沿路网中的相关链接开始扩散。而初始涟漪R1因为已经到达了 与其波源结点S相连的所有结点，所以时刻t = 2以后，初始涟漪R1就消亡了（即，变为不活 跃)。
[0062] 在时刻t = 3，涟漪R2到达了终点D。此时终点D还未产生过任何涟漪，所以涟漪R2对 终点D来说是Pareto非劣的。于是通过回溯涟漪R2,得到路径S-2-D是一个Pareto最优解， 同时涟漪R2在终点D激发出一个不活跃涟漪(在针对一到一的多目标路径优化问题的涟漪 扩散算法中，终点只能产生不活跃涟漪）。涟漪R2在时刻t = 3也到达了结点1，但是因为涟漪 R2与结点1上已有的涟漪R3相比（与R3被激发时的状态相比）不是Pare to非劣的，所以涟漪 R2没能在结点1上激发出新涟漪。在时刻t = 3，涟漪R3到达了结点2，因为涟漪R3与结点2上 已有的涟漪R2相比是Pareto非劣的，所以涟漪R3在结点2激发出一个新涟漪R5。
[0063] 在时刻t = 4，涟漪R4到达了终点D。因为涟漪R4与其它同期到达终点D的涟漪（即， 涟漪R3和涟漪R5)以及终点D上已有的涟漪相比是Pareto非劣的，所以通过回溯涟漪R4,得 到路径S-3-D是一个Pareto最优解，同时涟漪R4在终点D激发出一个不活跃涟漪。在时刻t =4,涟漪R3也到达了终点D。但是由于涟漪R3与终点D上已有的涟漪相比（由R2激发产生的 不活跃涟漪)不是Pareto非劣的，所以涟漪R3所对应的路径不是Pareto最优解。虽然涟漪R5 在时亥ljt = 4也到达了终点D，但与涟漪R4在终点D所激发的不活跃涟漪相比，涟漪R5不是 Pareto非劣的，所以涟漪R5所对应的路径也不是Pareto最优解。在时刻t = 4，涟漪R4也到达 了结点2，因为涟漪R4与结点2上已有的涟漪相比是Pareto非劣的，所以涟漪R4在结点2上激 发出新涟漪R6。在时刻t = 4，涟漪R2到达了结点3，但因为涟漪R2与结点3上已有的涟漪相比 不是Pareto非劣的，所以涟漪R2没能在结点3上激 发出新涟漪。此时，因为涟漪R2已经到达 了与其波源结点2相连的所有结点（无需考虑涟漪R2所对应路径中已包含的结点，如起点 S)，所以时刻t = 4以后，涟漪R2就消亡了。同理，涟漪R3、R4和R5在时刻t = 4以后都消亡了。 [0064] 在时刻t = 5，涟漪R6到达了终点D。因为涟漪R6与终点D上已有的涟漪相比是 Pareto非劣的，所以通过回溯涟漪R6,得到路径S43-2-D是一个Pareto最优解，同时涟漪 R6在终点D激发出一个不活跃涟漪。涟漪R6在时刻t = 5也到达了结点1，因为涟漪R6与结点1 上已有的涟漪相比是Pareto非劣的，所以涟漪R6在结点1上激发出新涟漪R7。此时，因为涟 漪R6已经到达了与其波源结点2相连的所有结点，所以时刻t = 5以后，涟漪R6就消亡了。 [0065] 在时刻t = 6，涟漪R7到达了终点D。因为涟漪R7与终点D上已有的涟漪相比不是 Pareto非劣的，所以涟漪R7所对应的路径不是Pareto最优解。此时，因为涟漪R7已经到达了 与其波源结点1相连的所有结点，所以时刻t = 6以后，涟漪R7就消亡了。
[0066]至此，涟漪接力赛中已经没有任何活跃涟漪了，所以优化计算结束。图3问题中的 完整Pareto前沿就由终点D上所产生的3个不活跃涟漪(涟漪R2、R4和R6各激发出一个，分别 对应路径S-2-D，S-3-D，和S-3-2-D)来确定，即，该完整Pareto前沿由3个点构成。 [0067]图4给出了一组本发明的方法与现有的A0F方（即，重构单目标函数法)和PCR方法 (即，Pareto标准评级法)的对比实验的结果。图4的实验是求解一个双目标路径优化问题， 其两个目标函数，即gl和g2，都需要被最小化。图4中，每个麻子三角形代表一个由A0F方法 找到的Pareto最优解，每个白色圆圈代表一个由PCR方法最终输出的当前非劣解，而每个黑 色正方形代表一个由本发明的方法所找到的Pareto最优解，所有黑色正方形一起组成了图 4实验的完整Pareto前沿。
[0068]由图4可以看出，在对比实验中，A0F方法找到了Pareto前沿凸面上的4个Pareto最 优解，但是却没能找出Par e to前沿凹面上的Par e t 〇最优解。而凹面上的那个Par e to最优解 显然代表着两个目标函数之间最理想的折中方案，很可能是决策者最希望达到的效果。图4 的实验结果表明，虽然A0F方法得到的结果都是Pareto最优解，但是A0F方法并不能充分满 足决策者的需求(因为A0F方法只找到了部分的Pareto前沿）。
[0069]由图4还可以看出，在对比实验中，PCR方法最终输出了的5个当前非劣解（完整 Pareto前沿也有5个Pare to最优解），而且这5个当前非劣解所组成的阵面的形状与完整 Pareto前沿的形状也很相似。但是，这5个当前非劣解中有3个根本就不是Pareto最优解。所 以，显而易见，PCR方法也无法为决策者提供最理想的决策支持。
[0070]基于本发明的方法所求解出的完整Pareto前沿能够为决策者提供全面、准确的决 策支持。
【主权项】
1. 一种求解完整ParetO前沿的多目标优化方法，用以解决为多目标路径优化问题求解 完整的（而不是部分的、或近似的）Pareto前沿的技术问题，其特征是:所述的方法的求解过 程可以形象地比喻成在路网中模拟一场涟漪扩散接力赛（比喻不是必须的，只是为了更加 形象和容易理解;换句话说，核心是比喻所对应的计算过程的内容，这些内容可以被比喻成 其它任何恰当的事物或过程，或者不用比喻，而是纯粹用抽象的数学变量和术语表述）；涟 漪接力赛开始于一个以给定起点为波源的初始涟漪;涟漪沿路网中的链接按预设的速度扩 散；当一个涟漪扩散到一条链接的另一端的结点时，如果该涟漪所代表的路径与该结点上 已产生的所有涟漪所代表的路径相比是Pareto非劣的，则一个新涟漪将以该结点为波源被 激发出来并扩散;当一个涟漪已经到达了与其波源结点相连的所有结点，该涟漪就消亡；当 接力赛中的所有涟漪都消亡了，则通过回溯一个结点上的所有涟漪，就能得到从给定起点 到该结点的完整Pareto前沿。2. 根据权利要求1所述的求解完整Pareto前沿的多目标优化方法，其特征是:对于多目 标一到一路径优化问题（即，从一个给定起点到一个给定终点），所述的方法可以求解出从 给定起点到给定终点的完整Pareto前沿。 假设有一个网络系统（可以是现实物理网络系统，如：公路网，也可以是抽象虚拟网络 系统，如:决策树），包含Nn个结点；结点间的链接可由一个邻接矩阵A表示，其中的元素A(i， j) = 1表示结点i和结点j之间存在一条链接，而A(i，j) = 0则表示结点i和结点j之间没有链 接;假设结点i和结点j之间存在一条链接，则该链接有Nobj个目标权重值，可分别记为Ck( i， j)，k=l，-_，Nc^;假设P表示一条路径，路径P包含见2 2个结点，？（1)表示路径？的第1个结 点，1 < i <Nl，1 <P(iHNN;对于多目标一到一路径优化问题（即，从一个给定起点到一个给 定终点），假设结点S是给定起点，而结点D是给定终点，那么需要求解如下最小化问题：其中 P(I) = S,P(Nl)=D, P(i)关 P(j)，if i关 j，i = l，...，NL，andj = l，...，NL， A(P(i)，P(i+l)) = l， ΩΡ表示所有可能路径的集合，fk是第k个单目标函数，k=l，-_，N_，fk可以是任何形式 的满足下列条件的函数： 如果fk(PiH fk(P2)，那么fk(Pi+PH fk(P2+P)， 如果 fk(Pi)<fk(P2)，那么 fk(Pi+P)<fk(P2+P)。 对于上述多目标一到一路径优化问题，所述的方法主要包括以下几个步骤： (步骤一)如果在个单目标函数中至少存在一个求和单目标函数，即，至少存在一个 fk具有如下函数形式则选一个求和单目标函数用以标定涟漪接力赛中的路径长度，假设第kBM个单目标函数 被选中；如果在Ncibj个单目标函数中没有求和单目标函数，则人为增加一个具有上述函数形 式的求和单目标函数fNClbj + l，用以标定接力赛中的路径长度，因而设置kBM=Ncibj + l，简单起 见，可以定义fk^+1(P)=NL-l，也就是说，每条链接的第(N_+l)个目标权重值都等于1，即， 对任意I < i < Nn和I < j < Nn，如果A( i，j) = 1，则定义C_j+1 (i，j) = 1;然后预设一个涟漪扩 散速度V。 (步骤二)初始化各种用以记录涟漪接力赛中的涟漪的状态的变量。 (步骤三）以起点S为波源生成一个初始涟漪（即，第一个活跃涟漪），设置当前涟漪数量 为Nr=I，设置第一个涟漪的波源为E(I) = S(即，起点为波源），设置第一个涟漪的半径为R (1) = 〇，设置第一个涟漪的状态为Sr(1 ) = 1 (即，活跃），设置第一个涟漪的激发涟漪为T(1) =〇(即，第一个涟漪不由任何涟漪激发，而是自发产生的），设置第一个涟漪的适应度向量 为其所对应路径的各单目标函数值(即O向量，因为第一个涟漪所对应路径是S-S);设定当 前仿真时刻为t = 0,以便开始涟漪接力赛。 (步骤四）：判断涟漪接力赛是否该结束?如果涟漪接力赛中已经没有任何活跃涟漪，或 者所有活跃涟漪与终点D上已有的涟漪相比都不是Pareto非劣的，即，对任意一个I < r < Nr，都有Sr(r) = 0 (即，涟漪r不活跃），或者，对任一 I ^ r d Sr(r) = 1，如果涟漪r所对应的 路径与终点D上已有涟漪所对应的路径相比都不是Pareto非劣的，则到步骤(八）；否则，到 步骤(五）。 (步骤五）：更新仿真时间t = t+l;对每个活跃涟漪按预设的涟漪扩散速度和一个时间 单位长度更新半径，即，对任意一个I < r < Nr，如果SR(r) = l，则更新R(r)=R(r)+v。 (步骤六）：对任何一个结点n，如果在当前这个时间单位长度内有涟漪到达(可能是1个 涟漪或多个涟漪;涟漪的波源结点与结点η之间必需有链接），即，对结点n，存在至少一个1 <1'<咏，满足5[?(1') = 1，厶似1')，11) = 1，1?(1')2〇1?似1')，11)，那么，根据所有的单目标函数， 将这些新到的涟漪彼此进行Pareto优劣比较，再与结点η的已有涟漪进行Pareto优劣比较， 以便将这些新到涟漪中的Pareto非劣涟漪（对该结点而言）找出来，以两个涟漪i和j的 Pareto优劣比较为例，分别计算或提取沿涟漪i所对应的路径以及沿涟漪j所对应的路径从 结点S走到结点η的各个单目标函数值，然后按Pare to优劣的定义比较涟漪i和涟漪j的各个 单目标函数值，从而确定涟漪i与涟漪j之间的Pareto优劣关系，只有当一个新到涟漪与所 有其它新到涟漪以及结点η的已有涟漪相比都是Pareto非劣的，这个新到涟漪对结点η来说 才是Pareto非劣的；然后由每个Pareto非劣的新到涟漪在结点η上激发产生一个新的涟漪， 并对新涟漪的状态进行相应的设置;对结点η上的一个由涟漪i所激发出的新涟漪的设置主 要如下：当前涟漪数量加1 (即，Nr = Nr+ 1)，为新涟漪Nr设置E (Nr) = η，T (Nr ) = i，R(Nr) = R (i)-CkBM(E(i)，n)，并根据沿涟漪i所对应的路径从结点S走到结点η的各个单目标函数值来 设置新涟漪Nr的适应度向量（以用于今后的Pareto优劣比较），新涟漪Nr的活跃状态需如下 设置:如果结点η不是终点（即，η判），则设置新涟漪Nr为活跃涟漪，即，Sr(Nr) = 1;否则（BP， n = D)，设置新涟漪Nr为不活跃涟漪，即，Sr(Nr)=0。换句话说，非终点的结点所产生的涟漪 都初始化为活跃涟漪，而终点D所产生的涟漪都是不活跃涟漪。 (步骤七）：对任何一个活跃涟漪，如果该涟漪已经到达了与其波源结点有链接的所有 其它结点(不考虑该涟漪所对应路径已包含的结点），即，对任何一个r，I < r < Nr，SR(r) = 1， 如果对每一个满足A(E(r)，n) = 1的结点n，都有R(r) 2 CkBM(E(r)，n)，那么，设置涟漪r变为 不活跃，即，设置SR(r)=0,或者说涟漪r消亡了；然后回到(步骤四）。 (步骤八）：根据终点D产生的所有涟漪，确定从起点S到终点D的完整Pareto前沿，即，终 点D所产生的每一个涟漪都对应一个Pareto最优解。如果(步骤一）中人为增加了一个求和 单目标函数fNQbj+1，则从已确定出的(NQbj+l)维Pareto前沿中筛选出不考虑该求和单目标函 数fkibj+i的Ncibj维Pareto前沿，就是原始问题中从起点S至丨」终点D的完整Pareto前沿。3.根据权利要求1所述的求解完整Pareto前沿的多目标优化方法，其特征是:对于多目 标一到多路径优化问题（即，从一个给定起点到路网中每一个其它结点），所述的方法只需 要运行一次，就可以求解出从给定起点到路网中所有其它每一个结点的完整Pareto前沿。 假设网络系统包含Nn个结点，则多目标一到多路径优化问题在数学描述上，可以当作 (Nn-I)个独立的多目标一到一路径优化问题，每个一到一问题中的终点为起点以外的其它 (Nn-I)个结点中的某一个。在求解多目标一到多路径优化问题时，所述的方法不需要对每 个一到一问题进行单独求解，而是按以下主要步骤，进行一次性的计算即可： (步骤一)如果在个单目标函数中至少存在一个求和单目标函数，即，至少存在一个 fk具有如下函数形式则选一个求和单目标函数用以标定涟漪接力赛中的路径长度，假设第kBM个单目标函数 被选中；如果在Ncibj个单目标函数中没有求和单目标函数，则人为增加一个具有上述函数形 式的求和单目标函数fNClbj + l，用以标定接力赛中的路径长度，因而设置kBM=Ncibj + l，简单起 见，可以定义fk^+1(P)=NL-l，也就是说，每条链接的第(N_+l)个目标权重值都等于1，即， 对任意I < i < Nn和I < j < Nn，如果A( i，j) = 1，则定义C_j+1 (i，j) = 1;然后预设一个涟漪扩 散速度V。 (步骤二)初始化各种用以记录涟漪接力赛中的涟漪的状态的变量。 (步骤三）以起点S为波源生成一个初始涟漪（即，第一个活跃涟漪），设置当前涟漪数量 为Nr=I，设置第一个涟漪的波源为E(I) = S(即，起点为波源），设置第一个涟漪的半径为R (1) = 〇，设置第一个涟漪的状态为Sr(1 ) = 1 (即，活跃），设置第一个涟漪的激发涟漪为T(1) =〇(即，第一个涟漪不由任何涟漪激发，而是自发产生的），设置第一个涟漪的适应度向量 为其所对应路径的各单目标函数值(即0向量，因为第一个涟漪所对应路径是S-S);设定当 前仿真时刻为t = 0,以便开始涟漪接力赛。 (步骤四）：判断涟漪接力赛是否该结束？如果涟漪接力赛中已经没有任何活跃涟漪， 即，对任意一个I <r<NR，都有SR(r)=0(即，涟漪r不活跃），则到步骤(八）；否则，到步骤 (五)。 (步骤五）：更新仿真时间t = t+l;对每个活跃涟漪按预设的涟漪扩散速度和一个时间 单位长度更新半径，即，对任意一个I < r < Nr，如果SR(r) = l，则更新R(r)=R(r)+v。 (步骤六）：对任何一个结点n，如果在当前这个时间单位长度内有涟漪到达(可能是1个 涟漪或多个涟漪;涟漪的波源结点与结点η之间必需有链接），即，对结点n，存在至少一个1 <1'<咏，满足5[?(1') = 1，厶似1')，11) = 1，1?(1')2〇1?似1')，11)，那么，根据所有的单目标函数， 将这些新到的涟漪彼此进行Pareto优劣比较，再与结点η的已有涟漪进行Pareto优劣比较， 以便将这些新到涟漪中的Pareto非劣涟漪（对该结点而言）找出来，以两个涟漪i和j的 Pareto优劣比较为例，分别计算或提取沿涟漪i所对应的路径以及沿涟漪j所对应的路径从 结点S走到结点η的各个单目标函数值，然后按Pare to优劣的定义比较涟漪i和涟漪j的各个 单目标函数值，从而确定涟漪i与涟漪j之间的Pareto优劣关系，只有当一个新到涟漪与所 有其它新到涟漪以及结点η的已有涟漪相比都是Pareto非劣的，这个新到涟漪对结点η来说 才是Pareto非劣的；然后由每个Pareto非劣的新到涟漪在结点η上激发产生一个新的活跃 涟漪(即，所有新激发产生出的涟漪都是活跃涟漪），并对新涟漪的状态进行相应的设置;对 结点η上的一个由涟漪i所激发出的新涟漪的设置主要如下：当前涟漪数量加1(即，Nr = Nr+ 1)，然后为新涟漪Nr设置Sr(Nr) = l，E(NR)=n，T(NR) = i，R(NR)=R(i)-Ck_(E(i)，n)，并根据 沿涟漪i所对应的路径从结点S走到结点η的各个单目标函数值来设置新涟漪Nr的适应度向 量（以用于今后的Pareto优劣比较）。 (步骤七）：对任何一个活跃涟漪，如果该涟漪已经到达了与其波源结点有链接的所有 其它结点(不考虑该涟漪所对应路径已包含的结点），即，对任何一个r，I < r < Nr，SR(r) = 1， 如果对每一个满足A(E(r)，n) = 1的结点n，都有R(r) 2 CkBM(E(r)，n)，那么，设置涟漪r变为 不活跃，即，设置SR(r)=0,或者说涟漪r消亡了；然后回到(步骤四）。 (步骤八）：对任意一个结点（非起点），从起点到该结点的完整Pareto前沿由该结点上 所产生的所有涟漪来确定，即，该结点所产生的每一个涟漪都对应一个Pareto最优解。如果 (步骤一）中人为增加了一个求和单目标函数&(^ +1，则从已确定出该结点的（N_ + l)维 Pareto前沿中筛选出不考虑该求和单目标函数fNQbj+i的Ncibj维Pareto前沿，就是原始问题中 从起点到该结点的完整Pareto前沿。4. 根据权利要求1和权利要求2所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以采用各种恰当的数学表述形式(例如，网络中的链接可以不用邻接矩阵 A表示，而是采用链接向量表的数据结构;所使用的各个变量符号本身不是必须的，核心是 变量的意义以及对变量的操作计算过程，例如，（步骤五）中更新涟漪半径，即，R(r)=R(r) + v，可以用任意变量符号来改写，如，W(m)=W(m)+z，甚至不用"涟漪"和"半径"这些词汇字 目艮，而是抽象地说成：向量R的第r个元素R(r)增加V，其效果是一样的）。5. 根据权利要求1和权利要求3所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以采用各种恰当的数学表述形式。6. 根据权利要求1和权利要求2所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以应用于各种能够转化为多目标路径优化的问题(例如:多目标组合优化 和多目标决策管理问题）。7. 根据权利要求1和权利要求3所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以应用于各种能够转化为多目标路径优化的问题。8. 根据权利要求1和权利要求2所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以采用各种恰当的硬件计算设备和软件编程技术来实现。9. 根据权利要求1和权利要求3所述的求解完整Pareto前沿的多目标优化方法，其特征 是:所述的方法可以采用各种恰当的硬件计算设备和软件编程技术来实现。
【专利摘要】一种求解完整Pareto前沿的多目标优化方法。属于计算机算法和管理优化领域。目的是为多目标路径优化问题(或等效问题)求解出完整的(而不是部分、或近似的)Pareto前沿。本发明的方法在路网中模拟一场涟漪扩散接力赛；接力赛开始于一个以给定起点为波源的初始涟漪；涟漪沿路网中的链接按预设的速度扩散；当一个涟漪扩散到一条链接的另一端的结点时，如果该涟漪所代表的路径与该结点上已产生的所有涟漪所代表的路径相比是Pareto非劣的，则一个新涟漪将以该结点为波源被激发出来并扩散；当一个涟漪已经到达了与其波源结点相连的所有结点，该涟漪就消亡；当接力赛中所有涟漪都消亡了，则通过回溯一个结点上的所有涟漪，就能得到从给定起点到该结点的完整Pareto前沿。
【IPC分类】G06Q10/04
【公开号】CN105488601
【申请号】CN201610030464
【发明人】胡小兵, 廖建勤
【申请人】北京师范大学, 廖建勤
【公开日】2016年4月13日
【申请日】2016年1月19日
最新回复(0)