2024年4月26日发(作者：)

502019，55（3）

ComputerEngineeringandApplications计算机工程与应用

软容量限制设施选址问题的竞争决策算法

何永梅，宁爱兵，彭大江，尚春剑，张惠珍

上海理工大学管理学院，上海200093

摘要：软容量设施选址问题是NP-Hard问题之一，具有广泛的应用价值。为了求解软容量设施选址问题，提出一

种基于数学性质的竞争决策算法。首先研究该问题的数学性质，运用这些数学性质不仅可以确定某些设施必定开

设或关闭，还可以确定部分顾客由哪个设施提供服务，从而缩小问题的规模，加快求解速度。在此基础上设计了求

解该问题的竞争决策算法，最后经过一个小规模的算例测试并与精确算法的结果比较，得出了最优解；针对大规模

的问题快速地求出了可行解，得到了令人满意的结果。

关键词：软容量设施选址；数学性质；竞争决策算法；竞争力函数

文献标志码：A中图分类号：TP301.6doi：10.3778/.1002-8331.1803-0292

何永梅，宁爱兵，彭大江，等.软容量限制设施选址问题的竞争决策算法.计算机工程与应用，2019，55（3）：50-54.

HEYongmei,NINGAibing,PENGDajiang,itivedecisionalgorithmforsoft-capacitatedfacilitylocation

erEngineeringandApplications,2019,55（3）：50-54.

CompetitiveDecisionAlgorithmforSoft-CapacitatedFacilityLocationProblem

HEYongmei,NINGAibing,PENGDajiang,SHANGChunjian,ZHANGHuizhen

SchoolofManagement,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China

Abstract：Thesoft-capacitatedfacilitylocationproblemisoneofNP-Hardproblems,whichhaswideapplicationvalue

ethesoft-capacitatedfacilitylocationproblem,acompetitivedecisionalgorithmbasedonmathe-

athematical

propertiesnotonlycanbeusedtodecidesomefacilitiesshouldbeopenorclosed,butalsocanbeusedtodetermine

ore,thesizeoftheoriginalproblemcanbereduced,andthe

soluthefact,anewcompetitivedecision

y,afterasmallscaletestandcomparison

withtheexactalgorithm,largescaleproblem,afeasiblesolutionisobtained

quickly,andtheresultissatisfied.

Keywords：soft-capacitatedfacilitylocation;mathematicalproperties;competitivedecisionalgorithm;competitiveforcefunction

1引言

时间精确算法。设施选址问题具有很强的实际背景，

设施选址问题（FacilityLocationProblem，FLP）

求解该问题所取得的进展往往有助于提高生产效率和

一直是运筹学研究的一个重要问题

[1]

，该问题应用非常

管理水平

[5]

。

广泛，如工厂、仓库、超市、学校、医院、图书馆等位置的

本文研究的是软容量限制设施选址问题（Soft-

确定问题

[2]

。非特殊的设施选址问题是NP-Hard问

CapacitatedFacilityLocationProblem，SCFLP），软容

题

[3-4]

，除非

P=NP

，否则设施选址问题不存在多项式量指的是设施提供的服务有限，但在实际的生活中设施

基金项目：国家自然科学基金（No.71401106）；上海市一流学科建设项目（No.S1201YLXK）；高等学校博士学科点专项科研基金联

合资助课题（No.25）。

作者简介：何永梅（1992—），通讯作者，女，硕士生，研究方向为算法、系统工程，E-mail：hyongmei68@；宁爱兵（1972—），

男，博士，副教授，研究方向为算法设计、系统工程；彭大江（1995—），男，硕士生，研究方向为算法、系统工程；尚春剑

（1994—），女，硕士生，研究方向为算法、系统工程；张惠珍（1979—），女，博士，副教授，研究方向为优化算法。

收稿日期：2018-03-19修回日期：2018-04-24文章编号：1002-8331（2019）03-0050-05

CNKI网络出版：2018-09-04,/kcms/detail/

何永梅，等：软容量限制设施选址问题的竞争决策算法

2019，55（3）

51

可以多次开设来增加自身容量，目标是使开设费用和连

min2_c

ij

：所有设施中，设施

i

为顾客

j

提供次小连

接费用之和最小。截止到目前已经有许多学者致力于

接费用

min2_c

ij

；即对顾客

j

来说，设施

i

的连接费用在

求解软容量限制设施选址问题的算法研究，大致可以

所有设施中的连接费用是次小的，次小的连接费用值是

分为三类。第一类是近似算法，如：当容量都相同时，

min2_c

Chudak和Shmoys

[6]

给出了线性规划舍入3-近似算法；对

ij

；

于一般情形，Jain和Vazirani

[7]

将该问题化归为无容量限

y

i

：表示设施

i

开设的次数，其取值范围为非负整数；

制设施选址问题，再调用原始对偶算法得到4-近似算

x

ij

：表示顾客

j

是否连接到设施

i

上，其为0-1变量。

法；Arya

[8]

等给出了局部搜索3.72-近似算法；Jain

[9]

等给

通常研究

d

j

=1

的情况，软容量限制设施选址问题

出3-近似算法。Mahdian

[10]

等利用归约的思想并调用对

的目标是在满足容量约束的条件下，使得开设费用与连

偶拟合算法得到该问题的2-近似算法，这是目前最好的

接费用之和最小，SCFLP的整数线性规划可以表示为以

近似比。用近似算法解决此问题，步骤简洁和复杂度较

下数学模型：

低，但其结果相对于最优解相差较大。第二类是精确算

min

i

∑

f

∈F

i

y

i

+

∑

i∈F

∑

c

j∈C

ij

x

ij

法，运用精确算法解决此类问题，虽然能够得到最优解，

但是时间复杂度较大，不适合求解大规模的问题。第三

ì

ï

x

ij

≤y

i

,∀i∈F,j∈C（1）

ï

类是启发式算法，如：张新邦等提出了改进差分进化算

ï

ï

∑

x

ij

≤u

i

y

i

,∀i∈F（2）

ï

法

[11]

，可以弥补以上两类方法的缺点。

s.t.

ï

j∈C

í

（3）

竞争决策算法（CompetitiveDecisionAlgorithm，

ï

∑

x

ij

=1,∀j∈C

ï

ï

i∈F

CDA）是在分析各种竞争规则和决策的基础上，利用优

ï

ï

x

ij

∈

{

0,1

}

,∀i∈F,j∈C（4）

胜劣汰的特性研究出的一种可解决组合优化问题的新

ï

î

y

i

是非负整数，∀i∈F（5）

型算法。CDA的原理与概念的详细情况可参阅文

在上述整数规划中，约束（1）表示如果顾客

j

连接

献[12-18]。在应用方面，已经实现车辆路径问题

[12]

、多

到某个设施

i

上，则设施

i

至少开设一次；约束（2）表示

目标旅行商问题

[15]

、0-1背包问题

[16]

、最小比率生成树问

连接到设施

i

上的顾客不能超过设施容量的

y

i

倍；约束

题

[17]

、最小顶点覆盖问题

[18]

和图的Steiner最小树问题等

（3）表示每个顾客都需要连到一个设施上。

NP-Hard问题的算法并编程实现。

2.2问题数学性质

本文将研究竞争决策算法在设施选址方面的应用，

竞争决策算法具有方便结合问题本身性质的特性，

进一步拓展CDA的应用领域。首先研究SCFLP模型的

通过对问题数学性质的分析，可以在一定程度上实现降

数学性质，利用该数学性质可以降低问题的规模，在此

阶，缩小规模，加快求解速度，所以在设计软容量设施选

基础上设计了求解软容量限制设施选址问题的竞争决

址的竞争决策算法之前，先讨论问题本身的数学性质。

策算法，加快了求解速度。最后经过数据测试和验证，

性质1若设施

i

的开设费用在所有设施的开设费

获得了令人满意的结果。

用中最小，且其与所有顾客

C={1,2,…,j,…,n}

的连

接费用都是该顾客的最小连接费用

min_c

ij

，则设施

i

必

2软容量限制设施选址问题的竞争决策算法

定开设，并开设

[n/u

2.1问题介绍

i

]

次（向上取整），直到为所有的顾

客提供服务。

为了描述方便，采用如下数学符号表示：

证明由该问题可知，显然成立。

m

：设施总个数；

性质2对于设施

i

n

：顾客总个数；

1

，如果存在某一设施

i

2

，设施开

设费用

f

u

1

>f

2

，且对于任意顾客

j∈C

，连接费用

c

1j

>

i

：设施

i

的容量（即一个设施

i

最多服务

u

i

个顾客）；

d

c

2j

，则称设施

i

1

相对设施

i

2

为严格劣势，则设施

i

1

必定

j

：表示顾客

j

的服务需求量；

f

关闭，并删除设施

i

1

的关联边。

i

：设施

i

的开设费用；

F={1,2,…,i,…,m}

：设施集合；

证明在软容量设施选址问题中，开设设施

i

2

比设

C={1,2,…,j,…,n}

：顾客集合；

施

i

1

更优，故性质2成立。

性质3若任一顾客

j

与设施

i

的连接费用为

c

c

ij

，而

ij

：设施

i

为顾客

j

提供单位服务的连接费用；

min_c

与其他设施的连接费用都为

+∞

，则顾客

j

必定由设

ij

：所有设施中，设施

i

为顾客

j

提供最小连

施

i

提供服务，且设施

i

必定开设，并删除顾客

j

与其他

接费用

min_c

ij

；即对顾客

j

来说，设施

i

的连接费用在

设施的连接边。

所有设施中的连接费用是最小的，最小的连接费用值是

证明顾客集

C

中的任一个顾客必须被提供服务，

min_c

ij

；

顾客

j

与其他设施（除设施

i

外）的连接费用都为+∞，则

522019，55（3）

ComputerEngineeringandApplications计算机工程与应用

顾客

j

只能由设施

i

提供服务，且设施

i

必定开设。

步骤3资源分配阶段

性质4若顾客

j

到各设施的连接费用中次小的连

计算每一个设施对顾客

j

的竞争力函数值

power(ij)

，

接费用

min2_c

ij

减去最小的连接费用

min_c

ij

之差大于

把顾客

j

分配给竞争力函数值最大的设施

k

，将顾客

j

为其提供最小连接费用的设施

i

的开设费用，即此时满

加入到集合

r(k)

中，表明设施

k

服务顾客

j

；执行

足

(min2_c

ij

-min_c

ij

)>f

i

，则设施

i

必定开设为顾客

j

j=j+1

，重复这个过程直到

j

大于顾客数

n

。

提供服务，并删除顾客

j

与其他设施的连接边。

步骤4资源争夺直到竞争决策状态均衡阶段

证明若设施

i

不开设，顾客

j

必定由其他设施为

对每个设施占有的资源重新计算竞争力函数值

其提供服务，服务费用必定大于或等于

min2_c

ij

，而

power(ij)

，重新计算之后，对于资源

j

来说，如果竞争力

min2_c

ij

又大于设施

i

的开设费用

f

i

与最小连接费用

函数值最大的设施

i

没有占用资源

j

，则可能按下面的

min_c

ij

之和，因此开设设施

i

使总费用更少。

详细操作步骤将资源

j

剥夺过来：

2.3原理

（1）

i=1

，没有进行资源剥夺标记

depr_flag=0

；

在竞争决策算法中，把每个设施当做一个竞争者，

（2）

h=1

，

r

2

(i)=r(i)

；

顾客当做被竞争的资源，设施为顾客提供服务也就是竞

（3）如果

h>|r

2

(i)|

，跳到（10），否则

j=r

2

(i)

中的第

h

争资源，用集合

r(1),r(2),…,r(m)

分别表示每个竞争者

个顾客；

占有的资源。竞争开始时所有的竞争者都没占用资源，

（4）

k=1

；

竞争结束时，竞争者占用的资源即该设施需要提供服务

（5）如果

k≠i

，则跳到（9）；

的顾客。

（6）如果

k=i

且

(k

，则

k=k+1

，跳到（9）；

2.4竞争力函数、决策函数、资源交换规则

（7）如果

k=i

且

k≥m

则

h=h+1

，跳到（3）；

（1）竞争力函数

（8）如果

h≤|r

2

(i)|

且

k≤m

，则跳到（5）；

本算法采用一个竞争力函数

power(ij)

，代表设施

i

（9）对

r(i)

中的顾客

j

，比较设施

i

和

k

对顾客

j

的

对顾客

j

的竞争力，其定义如下：

竞争力函数值。分以下四种情况：

power(ij)=

ì

í

1/(f

i

+c

ij

),设施i容量已满或不确定开设

情况1设施

k

未满且

|r(i)|/u

i

的余数>1，此时

î

1/c

ij

,设施i已经确定开设且容量未满

power(kj)=1/c

kj

,power(ij)=1/c

ij

；

该函数的思想描述为：若设施

i

已经确定开设且容量未

情况2设施

k

已满且

|r(i)|/u

i

的余数>1，此时

满，设施

i

对

j

的竞争力函数为设施

i

为顾客

j

的服务

power(kj)=1/(f

k

+c

kj

)

，

power(ij)=1/c

ij

；

费用的倒数；若设施

i

的容量已满或未开设，设施

i

对

j

情况3设施

k

未满且

|r(i)|/u

i

的余数=1，此时

的竞争力函数为设施

i

为顾客

j

的服务费用和开设费

power(kj)=1/c

kj

,power(ij)=1/(f

i

+c

ij

)

；

用之和的倒数，竞争函数值越大，竞争力越大。

情况4设施

k

已满且

|r(i)|/u

i

的余数=1，此时

（2）决策函数

power(kj)=1/(f

k

+c

kj

),power(ij)=1/(f

i

+c

ij

)

；若

power(kj)>

决策函数只有一个，竞争者

i

对资源

j

的竞争力函

power(ij)

，则

depr_flag=1

；

r(i)=r(i)-{j},r(k)=r(k)+{j}

，

数值越大，设施

i

就占有资源

j

，即为顾客

j

提供服务。

即设施

k

剥夺设施

i

中的资源

j

，也就是说顾客

j

原来

（3）资源交换规则

由设施

i

提供服务，现在改为由设施

k

提供服务；

具体的资源交换规则见算法中的说明。

（10）

i=i+1

，如果

i≤m

则跳到（2），否则跳到（11）；

2.5算法流程

（11）如果

depr_flag=1

，则跳到（1），否则转到步骤

步骤1重复剔除整体上的劣质竞争者或固定优质

4（资源争夺阶段）结束。

竞争者拥有的资源

说明：

depr_flag=1

说明有减少目标函数值的剥

调用降阶子程序，按照性质1~4确定一定关闭的设

夺，因此上述过程一定会终止。

施和开设的设施，在竞争者中去掉确定关闭的设施，确定

步骤5资源交换阶段

关闭设施用

y[i]=0

来标记，确定开设的设施用

y[i]=1

首先剔除没有拥有资源的竞争者并调用降阶子程

来标记，不能确定是否开设的设施用

y[i]=5

来标记；处

序，再将竞争者

i

和

k

中的顾客资源进行交换，直到不

理之后分两种情况：（1）由性质1得到问题的最优解，则

能再通过资源交换得到更好的解为止，交换竞争者

i

和

算法结束；（2）还没有得到最优解，则跳到步骤2。

k

中的顾客按下面的详细步骤操作：

步骤2初始化

（1）资源交换标记

swap_flag=0

；

初始状态只有一个，所有的竞争者刚开始都没占用

（2）

i=1

；

资源，

j=1

，集合

r(1)=r(2)=…=r(m)={}

。

（3）

k=1

；

何永梅，等：软容量限制设施选址问题的竞争决策算法

2019，55（3）

53

（4）

f=1

；本算法计算过程分析：

（5）

l=1

；

（1）调用降价子程序：首先利用数学性质2剔除竞

（6）如果

k=i

，且

(k≤m-1)

，则

k=k+1

；

争者设施

i

2

，并在矩阵

C

ij

中删除

{i

2

j

1

,i

2

j

2

,i

2

j

3

,i

2

j

4

,

（7）对于

r(i)

中的顾客

f

，

r(k)

中的顾客

l

若

c

il

+

i

2

j

5

}

，由性质4知设施

i

1

必定开设，并且顾客

j

1

由设施

c

kf

if

+c

kl

，则执行

r(i)=r(i)-{f}+{l}

，

r(k)=r(k)-

i

1

为其提供服务，即竞争者

i

1

占有资源

j

1

将

j

1

加入集

{l}+{f}

，即交换设施

i

的顾客

f

和

k

中的顾客

l

，此时

合

r(1)

中，

r(1)={j

1

}

。

设施开设费用不变，连接总费用变小，

swap_flag=1

，跳

（2）资源分配阶段：降阶处理后排除资源

{j

1

}

，剩下

到（9）；若没有交换则跳到（8）；

待分配的资源

{j

2

,j

3

,j

4

,j

5

}

，根据竞争力函数和决策函

（8）

l=l+1

，若

l≤|r(k)|

，则转到（7），否则跳到步

数，资源分配结果

r(1)={j

1

,j

2

,j

3

},r(3)={},r(4)={j

4

,j

5

},

骤（9）；

r(5)={}

。

（9）

f=f+1

，若

f≤|r(i)|

，则转到（5）；

（3）资源争夺阶段：对每个设施占有资源的重新计

（10）

k=k+1

，若

k≤m

，则转到（4），否则跳到（11）；

算竞争力函数值

power(ij)

，资源

{j

1

}

的占有者

i

1

在降

（11）

i=i+1

，若

i≤m

，则转到（3），否则跳到（12）；

阶子程序中已经固定，对于资源

{j

2

,j

3

,j

4

,j

5

}

，经计算资

（12）如果

swap_flag=1

，则转到（1）否则转到步骤

源

{j

2

}

仍属于集合

r(1)

，

{j

4

,j

5

}

仍属于集合

r(4)

，资源

j

3

5（资源交换阶段）结束。

的竞争力函数值

power(i

1

j

3

)=1/11

4

j

3

)=1/7

，

说明：

swap_flag=1

说明有减少目标函数值的交

故决策函数将资源

j

3

从

i

1

中剥夺出来并分配给

i

4

，此

换，因此上述过程一定会终止。

时有

r(1)={j

1

,j

2

},r(3)={},r(4)={j

3

,j

4

,j

5

},r(5)={}

。

步骤6输出竞争决策得到的结果。

（4）资源交换阶段：剔除没有拥有资源的竞争者

i

3

，

i

5

，当前资源的占有情况

r(1)={j

1

,j

2

},r(4)={j

3

,j

4

,j

5

}

，将

3算法时间复杂度及对比分析

设施

i

1

中的资源

j

1

强行与设施

i

4

中的

j

3

资源交换，由

步骤3资源分配阶段计算

m

个设施分别对

n

个顾

于

C

i1j1

+C

i4j3

i4j1

+C

i1j3

因此资源

j

1

又会回到

i

1

手

客的竞争力函数值，其时间复杂度为

O(m×n)

；步骤4和

中，

j

3

回到

i

4

手中，所以不执行交换。遍历每一个设

5中循环最坏的情况下时间复杂度为

O(n

4

)

，

n

为顾客

施拥有的资源直到不能再通过资源交换得到更好的解

数，因此整个算法最坏情况下的时间复杂度为

O(n

4

)

。

为止。

自从软容量限制设施选址问题被提出以来，相继有

（5）输出竞争决策结果：最终开设设施集

F

i

={i

1

,i

4

}

，

不同学者以不同的思想提出很多不同的算法，就目前的

开设次数

Y

i

=

[1，0，0，1，0]，服务集合

S={i

1

j

1

,i

1

j

2

,i

4

j

3

,

研究情况来看，近似算法虽然步骤简洁和计算复杂性

i

4

j

4

,i

4

j

5

}

，目标函数值

Z=49

。

低，但其结果与最优解差距较大；精确算法的优点是可

算例1运利用本文的算法与用精确算法-分支定界

以得到问题的最优解，但无法解决大规模的问题。一般

算法求得最优解一样，但是利用本文提供的算法的比一

的启发式算法可以快速得到问题的解，而本文给出的算

般的精确算法时间复杂度低，求解速度快。

法是首先利用数学性质进行降阶处理，降低了算法的时

其他算例：由于在其他文献中找不到可以参照对比

间复杂性，然后利用竞争决策算法对降阶后的问题进行

的算例，因此采用随机策略生成大规模算例，候选设施

求解，因此可以快速得到令人满意的解。

数为

m

，顾客数为

n

，设施的容量为

u

，如表1所示，设

施的开设费用

f

i

∈

（50，2000），顾客的需求量

d

i

=1

，

4数值算例

连接费用

c

ij

∈

（30，6000），采用本文中的算法算例结果

为验证算法的有效性，采用C++在PC机上实现了

如表1所示。

该算法。限于篇幅下面给出了一些算例，并给出了算例

表1大规模算例计算结果

1与用精确算法-分支定界算法求得结果做比较。

问题规模

算例1首先测试一个小规模的算例，候选设施数

m

n

设施容量

u

目标函数值

Z

m=5

，顾客数

n=5

，设施的容量

u

i

=3

，设施的开设费

3030317255

用

F

[10，28，21，15，16]，设施与顾客的连接费用：

5

i

=

8

é

ê

26111213

ù

ê

1

C

2

ij

=

ê

ê

1612131516

ú

ú

ú

ê

ú

ê

13

ê

ê

14

8

9

10

7

9

5

5

4

ú

ú

ú

以上测试算例的结果证明了本文算法在求解大规

ë

1510865

ú

û

模问题的可行性和有效性。

542019，55（3）

ComputerEngineeringandApplications计算机工程与应用

5结束语

oftheACM，2001，48（2）：274-296.

本文首先建立软容量限制设施选址问题的数学模

[8]AryaV，GargN，KhandekarR，earchheuristic

型，然后研究了该问题具有的数学性质，利用数学性质

for

k

-medianandfacilitylocationproblems[C]//Proceed-

进行降阶，缩小了问题的规模。在此基础上利用竞争决

ingsoftheThirty-thirdAnnualACMSymposiumon

策算法设计了求解该问题的竞争力函数、决策函数、资源

TheoryofComputing，2001：21-29.

交换规则和算法流程。通过算例1可以看出本算法仅对

[9]JainK，MahdianM，eedyapproachfor

部分设施进行分析，加快了算法的执行速度，并且求得

facilitylocationproblem[C]//ProceedingsoftheThiry-

了与使用精确算法一样的最优结果；针对大规模的算例，

fourthAnnualACMSymposiumonTheoryofComputing，

2002：731-740.

快速地求得了令人满意的结果。本文中的数学性质和算

[10]MahdianM，YeY，ZhangJ.A2-approximationalgo-

法可以推广到其他设施选址问题，具有良好的适应性。

rithmforthesoft-capacitatedfacilitylocationproblem[C]//

LectureNotesinComputerScience，2003，2764（1）：

参考文献：

129-140.

[1]imationalgorithms[M].Berlin：Springer-

[11]张新邦，邢航，李贵栋，等.软容量约束的物流设施选址问

Verlag，2001.

题的改进差分进化算法[J].物流科技，2016，39（6）：6-9.

[2]丁雪枫，马良，丁雪松.基于模拟植物生长算法的易腐物品

[12]宁爱兵，马良.竞争决策算法及其在车辆路径问题中的应

物流中心选址[J].系统工程，2009，27（2）：96-101.

用[J].管理科学学报，2005，8（6）：10-18.

[3]秦进，史峰.物流设施选址问题的双层模拟退火算法[J].系

[13]宁爱兵，马良.度约束最小生成树（DCMST）的竞争决策

统工程，2007，25（2）：36-40.

算法[J].系统工程学报，2005，20（6）：630-634.

[4]代文锋，仲秋雁，贺冬冬.基于灰理想关联熵的应急物资配

[14]刘勇，马良，宁爱兵.给定限期条件下应急选址问题的量

送中心选址[J].系统工程，2016，34（4）：101-108.

子竞争决策算法[J].运筹与管理，2011，20（3）：66-71.

[5]徐大川，张家伟.设施选址问题的近似算法[M].北京：科学

[15]宁爱兵，熊校华，马良.多目标旅行商问题的竞争决策算

出版社，2013.

法[J].计算机工程与应用，2009，45（34）：13-16.

[6]ChudakFA，edapproxiamtionalgo-

[16]熊小华，宁爱兵，马良.多目标0-1背包问题的元胞竞争决

rithmsforthecapacitatedfacilitylocationproblem[C]//

策算法[J].计算机应用研究，2010，27（10）：3680-3682.

ProceedingsofSODA，1999：875-876.

[17]熊小华，宁爱兵.最小比率生成树的竞争决策算法[J].计

[7]JainK，imationalgorithmsformetric

算机工程与应用，2012，48（28）：47-51.

facilitylocationand

k

-medianproblemsusingthethe

[18]金婷婷，王波，宁爱兵.最小顶点覆盖问题的竞争决策算

primal-dualschemaandLagrangianrelaxation[J].Journal

法[J].计算机工程与应用，2011，47（1）：32-34.

（上接第49页）

[9]汪洪桥.模式分析的多核方法及其应用[M].北京：国防工

[2]aticalcontributionstothetheoryof

业出版社，2014.

sion，heredity，andpanmixia[J].Philo-

[10]张晨光，张燕，张夏欢，等.从希尔伯特-施密特独立性中

sophicalTransactionsoftheRoyalSocietyA，1896，187：

学习的多标签半监督学习方法[J].中国科技论文，2013，8

253-318.

（10）：998-1002.

[3]ofandmeasurementofassociation

[11]FukumizuK，BachFR，JordanMI，ionality

betweentwothings[J].TheAmericanJournalofPsychology，

reductionforsupervisedlearningwithreproducingkernel

1904，15（1）：72-101.

hilbertspaces[J].JournalofMachineLearningResearch，

[4]周航星，陈松灿.有序判别典型相关分析[J].软件学报，

2004，5（11）：73-99.

2014，25（9）：2018-2025.

[12]GrettonA，BousquetO，SmolaAJ，ingsta-

tisticaldependencewithhilbert-schmidtnorms[C]//Inter-

[5]SzékelyGJ，RizzoML，ingand

nationalAlgorithmicLearningTheory，2005：63-77.

testingdependencebycorrelationofdistances[J].The

[13]SongL，SmolaAJ，GrettonA，eselectionvia

AnnalsofStatistics，2007，35（6）：2769-2794.

dependencemaximization[J].JournalofMachineLearning

[6]奉国和.SVM分类核函数及参数选择比较[J].计算机工程

Research，2012，13（1）：1393-1434.

与应用，2011，47（3）：123-124.

[14]楼俊钢，蒋云良，申情，等.软件可靠性预测中不同核函数

[7]吴涛，贺汉根，贺明科.基于插值的核函数构造[J].计算机

的预测能力评估[J].计算机学报，2013，36（6）：1303-1311.

学报，2003，26（8）：990-996.

[15]林升梁，刘志.基于RBF核函数的支持向量机参数选择[J].

[8]周志华.机器学习[M].北京：清华大学出版社，2016.

浙江工业大学学报，2007，35（2）：163-167.