Web服务组合QoS全局优化算法

2011，47（8）随着Web 服务技术的快速发展，组合Web 服务的应用已经成为可能，组合Web 服务的QoS 优化问题的重要性也日益凸显。

目前常用的全局优化算法有0-1启发式算法、遗传算法[1-2]，模拟退火算法、蚁群算法[3-6]、自适应的蚁群算法[7-9]及粒子群算法[10-11]等。

遗传算法采用启发式搜索技术，不能保证得到全局最优解，但可以有效地改善解的质量。蚁群算法能很好利用算法执行过程中产生的中间结果，以达到正反馈的效果[5]。目前对于两种算法混合计算也有相关研究，如用遗传算法的二进制编码形式解决蚁群算法连续函数的离散化[12]等。

本文使用蚁群算法和遗传算法进行QoS 全局优化的求解，并给出一个融合蚁群算法和遗传算法两种算法优势的混合算法，最后分别对它们的性能进行分析比较。

1基本蚁群算法（ACO ）求解QoS 最优问题

按照蚁群算法对QoS 最优问题进行分析，可理解为：设有

n 个城市，每个城市与下一城市相连，且连接两城的道路有m 条。有x 只蚂蚁，它们都从统一的出发点，向下一个城市出发，它们每一站的目标均相同，不同的是它们在两站之间的m 条道路中选择一条作为自己的行走路线。

设有x 只蚂蚁，每只简单蚂蚁有以下特征：

它根据以连接边上外激素的数量为变量的概率函数选择下一城市。设τij (t )为t 时刻（t 时刻表示第t 次迭代）边E j

i 上外激素的强度，其中i 表示第i 个城市，j 表示从第i －1个城市到第i 个城市的第j 条道路。

规定蚂蚁走合法的路线，且遍历顺序需按照设计路线行进，不允许回头转到已访问过的城市或跳过其中某一城市直接到下一城市。

它完成整条路径后，蚂蚁在它的每一条访问的边上留下外激素。初始时刻，各条路径上的信息量相等，设τij (0)=C （C 为常数）。蚂蚁k （k =1，2，…，x ）在运动过程中，根据各条路径

上信息量决定转移方向，p k

ij

(t )表示在t 时刻蚂蚁k 由城市i －1Web 服务组合QoS 全局优化算法

娄渊胜1，陶振宏2

LOU Yuansheng 1，TAO Zhenhong 2

1.河海大学计算机与信息学院，南京210098

2.中兴通信股份有限公司南京研究所，南京210012

1.College of Computer &Information ，Hohai University ，Nanjing 210098，China

2.Nanjing Research Institute ，ZTE Corporation ，Nanjing 210012，China

LOU Yuansheng ，TAO Zhenhong.Web service composition algorithm for QoS global https://www.wendangku.net/doc/b31040962.html,puter Engineering and Applications ，2011，47（8）：207-210.

Abstract ：With the applications of composite Web service becoming universality ，the importance of QoS optimization prob-lems is becoming increasingly evident.Genetic algorithm and ant colony algorithm both belongs to the QoS global optimiza-tion methods.For ant colony algorithm easy to drop into the slow pace of convergence while genetic algorithm easy to fall into local optimal solution and the low efficiency problems ，the paper combines with two algorithms ’advantages ，gives full play to the positive feedback characteristics of ant colony algorithm and genetic algorithm's rapid global search capability ，im-proves the global optimization algorithm ’s ability ，better resolves the Web services QoS optimization problem.Key words ：global optimization method of quality of service ；ant colony algorithm ；genetic algorithm 摘

要：Web 服务技术的发展使得组合Web 服务的应用成为可能，组合服务的QoS 优化问题的重要性越来越明显。遗传算法与

蚁群算法是解决QoS 全局优化的两种方法，针对采用蚁群算法进行优化时易出现的收敛速度缓慢及遗传算法易陷入局部最优解、效率不高的问题，结合两种算法的优势，充分发挥蚁群算法正反馈特性与遗传算法的快速全局搜索能力，改善QoS 全局优化算法，提高了算法的优化能力，从而更好地解决了Web 服务的QoS 全局优化问题。关键词：服务质量（QoS ）全局优化；蚁群算法；遗传算法DOI ：10.3778/j.issn.1002-8331.2011.08.061

文章编号：1002-8331（2011）08-0207-04

文献标识码：A

中图分类号：TP 301.6

基金项目：国家高技术研究发展计划（863）重点项目（No.2007AA01Z179）。

作者简介：娄渊胜（1968—），男，博士，副教授，CCF 高级会员，主要研究方向：软件体系结构、分布式应用集成；陶振宏（1986—），男，硕士研究生，

Computer Engineering and Applications 计算机工程与应用?工程与应用?

207

Computer Engineering and Applications计算机工程与应用2011，47（8）

出发到城市i时，选择第j条路径的概率。

p k ij =

ì

í

?

?

?

?

?

τ

ij

(t)

?

s?allowed

k

τ

is

(t)

,j?allowed

k 0,?否则

其中，allowed

k

表示蚂蚁k下一步允许选择的路径。ρ表示信息的持久性，一般取0.5~0.9左右。随着时间的推移，以前留下的信息逐渐消失，用1-ρ表示信息的消逝程度，经过n个时刻，蚂蚁完成一次遍历，各路径上的信息量根据以下公式做调整：

τij (t+n)=ρ×τ

ij

(t)+Dτ

ij

，Dτ

ij

=?

k=1

m

Dτk

ij

Dτk

ij 表示第k只蚂蚁在本次遍历过程中留在路径E j

i

上的信息

量，Dτ

ij 表示本次遍历中路径E j

i

的信息量增量，L

k

表示第k

只蚂蚁遍历后整个路径的长度，Q为常数。

Dτk

ij =

ì

í

?

?

?

Q

L

k

,第k只蚂蚁在本次遍历中经过E j

i 0,否则

2基本遗传算法（GA）求解QoS最优问题

针对QoS最优化问题，可设计遗传算法计算思想如下：有n个任务，每个任务有[1，2，…，m]个可用服务，则编码表示为Xi（i=1，2，…，n，Xi=1，2，…，m），i表示第i个任务，Xi表示第i个任务选择的可用服务编号。根据应用场景，编码位数与任务数对应，种群规模数根据问题规模动态确定。各染色体编码随机生成，范围确定在[1，2，…，m]。

适应度函数与目标函数相关，是判断遗传算法产生的种群是否符合要求的判断依据。采用界限构造法构造适应度函

数：Fit(f(x))=power(f(x)-C

min )。其中C

min

表示适应度函数

的最小值。

选择策略：使用截断选择策略，在这种选择策略中，种群按照目标值进行排序。适应度仅取决于个体在种群中的序号，而不是实际的目标值。排序方法中引入种群均匀尺度，提供了控制选择压力的方法。为了在优化过程中保证种群的多样性，这里取截断阈值=0.9。

交叉策略：首先根据交叉概率，确定种群中需要进行交叉操作的次数。随机确定父代染色体A、B。在B中随机选择一个交叉点，把B交叉点后的区域与A的对应区域互换，得到两个新的基因。

变异策略：遍历染色体的每个基因，判断是否变异。若变异，随机生成这个节点的值，替换原有值，其余不变。同样检查产生子染色体的合法性。

本文的优化准则如下：将每一代中的最优个体的适应度值Gen Max（fitness）与目前存在的最大适应度值Max（fitness）进行比较，若连续经过N代进化，最优个体的适应度值没有明显的提高，即满足：

Gen Max(fitness)-Max(fitness)

Max(fitness)

′100%<0.01%

则终止迭代。否则，继续迭代，直至到达最大迭代数。

3求解QoS最优问题的混合算法（GA_ACO）

的信息正反馈影响，

不断积累较优中间结果的优势，并将优势

不断扩大，直至算法收敛，得到最优解。但在算法依靠计算过

程中不断产生的信息素，在前期计算次数很少时，无法得到所

需的信息素，导致求解速度缓慢。

遗传算法具有大范围的全局搜索能力，且在计算初期、中

期及后期都有充足的计算所需的要素，但对算法计算过程中

产生的反馈信息利用不够，仅根据适应度值判断整条染色体

的保留与否，并不关心染色体中具体基因的优劣。当求解到

一定范围时，往往由于种群中大量的染色体极为相似，而无法

进一步优化最终结果，使得算法早熟，难以求得精确解；且做

出大量无用的迭代，影响算法效率。

根据对蚁群算法和遗传算法的分析，给出了基于两种算

法的混合算法，它的主要思想是在遗传算法中利用蚁群算法

产生的信息素，并根据信息素浓度的高低来判断遗传算法中

基因的优劣程度（信息素浓度高的路径在染色体中就表现为

优势基因，反之则为劣势基因），尽可能地保留优势基因，达到

快速全局收敛的目的。

3.2算法相关处理

（1）编码方式

混合算法中采用整数编码作为算法的染色体编码，编码

顺序与Web Service组合流程结构一致，表示为一个有序序

列，使之能够在蚁群算法及遗传算法中顺利转换。

（2）适应度值计算方法

通过如下公式来计算QoS值：

Score(s)=?

i=1

n

(w

i

′?

k=1

Num

Q

ki

)

其中：w

i

表示用户赋予每个属性的权值，?

i=1

n

w

i

=1，n为用户所

关心的QoS属性个数。?

k=1

Num

Q

ki

表示组合服务的第i个QoS属

性的整体值。

（3）选择操作策略

选择策略以基本遗传算法中基于排序的选择策略为基

础，除了实现原有的挑选合适染色体的功能外，添加如下功

能：在现有种群中，找出适应度函数值最大的个体，将此染色

体的构造转化为蚂蚁前进路线，计算、更新路线上各段的信息

素分布，形成基因优劣表，为判断染色体优劣做准备。

（4）交叉操作策略

交叉策略：设染色体A与B进行交叉操作。A读取基因优

劣表，逐个比对自身与B对应基因的优劣程度。若在基因X

上，A优于B，则将A的X基因保留到下一代，以此类推，直至将

整条染色体比对结束。同时保留A、B到下一代。

交叉策略示意图如图1所示。

混合算法交叉策略

A

B

A

B

A

B

普通遗传算法交叉策略

图1交叉策略示意图

208

2011，47（8）娄渊胜，陶振宏：Web 服务组合QoS 全局优化算法

需要变异。若需要变异，则使用轮盘赌策略得到变异后的基

因，完成变异。

3.3算法的求解步骤

（1）随机生成初始种群，作为迭代对象。

（2）计算种群中各染色体的适应度值，找出最优解，并判断算法是否收敛或达到终止条件。若满足条件，算法终止，退出计算，否则继续执行。

（3）执行选择操作，选择合适染色体进入交配池。同时，将最优染色体转换为最优的蚂蚁前进路线，据此更新各个路线上的信息素，作为判断染色体优劣的依据。

（4）对照基因优劣表，按策略执行交叉、变异操作，生成新一代种群。

（5）跳转到（2）。

算法流程结构如图2所示。它的流程控制方面与遗传算法相似，在选择、交叉、变异操作的策略上作了改进。

下面给出了上述操作中改进部分的伪代码。

//选择操作

Function doChoose （）{

chooseBest （）；//选择最优染色体

doTransform （）；//转化染色体基因为蚂蚁行进路线updateInfo （）；//更新模型信息素

chooseBests （）；//选择合适的染色体进入交配池}

//交叉操作

Function doIntercross （A ，B ）{for （each Gene from A ）{

//遍历染色体A 的基因用A ，B 的优势基因生成新染色体newGene +=Compare （Gene_A ，Gene_B ）；}return newGene ；//返回新产生的染色体}

//变异操作

Function doAberrance （A ）{

for （each Gene from A ）{//遍历染色体A 的基因if （isAberrance ）{//判断是否需要变异aberrance （）；//根据信息素分布进行变异}}

return A ；//返回变异后的染色体}

上的解决问题能力，

下面对三种算法在解的质量及计算效率上作出分析。各算法在相同的环境下，使用不同的应用场景进行测试。本次实验环境为Pentium

?

4CPU ，3.00GHz ，512MB

的内存，使用开发工具为Eclipse3.2，Java （jdk1.6）实现。

实验数据分别模拟了几种场景（其中服务的组合方式任意），如表1所示。

三种算法所选参数如表2所示。

分别使用三种算法对以上实验场景对应的问题模型进行

计算，对得到的结果进行统计分析可得：

（1）找到最好解的次数比较在问题规模较小时，ACO 、GA 、GA_ACO 都有较好表现，绝大多数情况下都能找到最优解，总体质量很高。

随着问题规模的扩大，ACO 算法与GA 算法的能力急剧下降，在规模为7-20（组合流程中包含7个任务，每个任务有20个可选服务，下同）时，ACO 共找到14次最优解，GA 共找到16次最优解，而GA_ACO 找到85次最优解，是它们的5倍多。在规模更大的情况下，ACO 与GA 基本上不能找到最优解；而GA_ACO 算法只在获得最优解次数上稍有降低，规模为10-10时，获得77次最优解，规模为20-10时，获得73次最优解，都明显高于前两种算法。（2）最差解与平均解相对误差比较在问题规模较小时，ACO 、GA 、GA_ACO 都有较好表现，相对误差都比较低。

随着问题规模的扩大，ACO 算法与GA 算法的相对误差在逐渐扩大，呈上升趋势。而GA_ACO 算法的相对误差基本没有扩大，一直保持较低水平。

（3）从图3~图5中可以看到，在规模为10-20时，曲线浮动很大。经分析发现，这是由于这一规模下随机生成的数据中，最优解的值特别突出，远高于其他解。在这种情况下，三种算法的误差都有明显扩大。ACO 与GA 的误差在25%左右，GA_ACO 的相对误差为16%，说明GA_ACO 在处理异常情况时也优于上述两种算法。

（4）综上所述，GA_ACO 与ACO 、GA 算法相比，它的能力按照选择策略选择合适染色体进入交配池

转换基因与路线更新信息素

产生种群计算适

应度值

是否收敛

是

否

输出结果

判断基

因优劣交叉操作变异操作

取最优染色体图2

混合算法流程图

实验场景

123456

任务数

7710102020

可选服务数

102010201020

表1

实验场景

参数种群大小适应度函数初始信息素浓度C

常量Q

信息的持久性ρ选择概率交叉概率变异概率最大迭代次数

值30、100、500

Fit （f （x ））=power （f （x ）－C min ）

100200.90.90.81/12200

表2

算法参数

209

Computer Engineering and Applications 计算机工程与应用

2011，47（8）

计算量上要远高于前两种算法，计算效率要明显低于ACO ，略低于GA 算法。

5结束语

介绍了蚁群算法、遗传算法对QoS 最优的求解过程，并在求解过程中，用实验测试算法相关参数对算法性能的影响程度，为两算法确定合适的参数。提出了一个混合算法，该算法基于上两种算法，结合了蚁群算法的并行性、正反馈特性与遗传算法的全局搜索能力，有效提高了算法的收敛速度及计算效率。

参考文献：

[1]Holland J H.Concerning efficient adaptive systems[J].Yovits M

C.Self-Organizing Systems ，1962：215-230.

[2]Holland J H.Adaptation in natural and artificial systems[M].2nd

ed.Cambridge ，MA ：MIT Press ，1992.[3]Dorigo M ，Maniezzo V ，Colorni A.Ant system ：Optimization by

a colony of cooperating agents[J].IEEE Trans on SMC ，1996.[4]Dorigo M ，Maniezzo V ，Colorni A.Ant system ：An autocatalytic

optimizing process ，91-016[R].Milan ：Politecnicodi Milano ，1991.[5]高尚，杨静宇.群智能算法及其应用[M].北京：中国水利水电出版

社，2006．[6]高尚，钟娟，莫述军.连续优化问题的蚁群算法研究[J].微机发展，

2003，13（1）：21-22．[7]王颖，谢剑英.一种自适应蚁群算法及仿真研究[J].系统仿真学报，

2002，14（1）：31-33.[8]Sun Hong ，Zhan Shichang ，Jin Bailin.The research of anadaptive

evolutional ant colony algorithm and its simulation[J].Journal of Hangzhou Teachers College ：Natural Science Edition ，2003，2（5）：31-34.[9]陈岐，秦玲，陈宏建，等.具有感觉和知觉特征的蚁群算法[J].系统

仿真学报，2003，15（10）：1418-1425.[10]王正初，李微微.基于粒子群算法的可靠性优化[J].台州学院学

报，2006，28（6）：29-32.[11]张丹，李长河.基于混沌的粒子群优化算法研究与进展[J].软件导

刊，2007（6）：109-110．[12]肖宏峰，谭冠政.遗传算法在蚁群算法中的融合研究[J].小型微型

计算机系统，2009，3（3）：512-517．

ACD

GA

GA_ACO

120100806040200

次数

7-10

7-20

10-1010-20

20-10

20-20

解规模

图3

最优解找到次数图

ACD

GA

GA_ACO

35302520151050

误差百分比/（%）7-10

7-20

10-1010-20

20-1020-20

解规模

图4

最差解相对误差比较图

ACD

GA

GA_ACO

302520151050

误差百分比/（%）7-10

7-20

10-1010-20

20-1020-20

解规模

图5平均解相对误差比较图

技术，有效地弥补了归一化的不足，从而使所设计的算法对几何攻击具有高度的鲁棒性。结合人类视觉系统特性实现了DCT 域内水印的嵌入和提取。此外，本方案还具有容易实现、提取水印时无需原始载体等优点，这大大增强了其用于数字图像作品版权保护的实用性，具有一定的应用价值。

参考文献：

[1]刘方，杨峰.改进的基于DCT 的加密盲水印算法[J].计算机工程

与应用，2009，45（13）：124-126.

[2]冯少辉，郭宗明.基于小波变换的数字图像水印[J].计算机工程与

应用，2008，44（20）：75-77.

[3]Dong P ，Galatsanos N P.Affine transformation resistant water-marking based on image normalization[J].IEEE Trans on Image Processing ，2002，8：865-882.

[4]Dong P ，Brankov J G ，Galatsanos N P ，et al.Digital watermark-ing robust to geometric distortions[J].IEEE Trans Image Process-ing ，2005，14（12）：2140-2150.

[5]牛盼盼，杨红颖，邬俊，等.基于归一化图像重要区域的数字水印方

法

[J].小型微型计算机系统，2008，29（11）：2153-2156.

[7]Kang Xian-gui ，Huang Ji-wu.A DWT-DFT composite watermark-ing scheme robust to both affine transform and JPEG compres-sion[J].IEEE Trans on Circuits and Systems for Video Technolo-gy ，2003，13（8）：776-786.

[8]Jin S S ，Chang D Y .Image watermarking based on invariant re-gions of scale-space representation[J].IEEE Transactions on Sig-nal Processing ，2006，54（4）：1537-1549.

[9]Paute J ，Jordan https://www.wendangku.net/doc/b31040962.html,ing fractal compression scheme to embed a

digital signature into an image[C]//Proc SPIE Photonics East Symposium ，Boston ，USA ，1996：18-22.

[10]Pi M H ，Li C H ，Li H.A novel fractal image watermarking wa-termarking[J].IEEE Trans on Multimedia ，2006，8（3）：488-499.[11]Xie R S ，Yang S G.A digital image watermarking method based

on fractal transform in DWT domain[C]//1st International Con-ference on Modelling and Simulation ，Naning ，China ，2008，3：424-429.

[12]申小娜，何传江，刘维胜.一个分形图像水印算法的改进[J].计算

机工程与应用，2008，44（10）：91-94.

[13]Han Qiang ，Ma Hong.Blind watermark algorithms based on

（上接203页）

210

遗传算法与组合优化.

第四章 遗传算法与组合优化 4.1 背包问题（knapsack problem ） 4.1.1 问题描述 0/1背包问题：给出几个尺寸为S 1，S 2，…，S n 的物体和容量为C 的背包，此处S 1，S 2，…，S n 和C 都是正整数；要求找出n 个物件的一个子集使其尽可能多地填满容量为C 的背包。 数学形式： 最大化 ∑=n i i i X S 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 广义背包问题：输入由C 和两个向量C ＝(S 1，S 2，…，S n )和P ＝(P 1，P 2，…，P n )组成。设X 为一整数集合，即X ＝1，2，3，…，n ，T 为X 的子集，则问题就是找出满足约束条件∑∈≤T i i C X ，而使∑∈T i i P 获得最大的子集T ，即求S i 和P i 的下标子集。 在应用问题中，设S 的元素是n 项经营活动各自所需的资源消耗，C 是所能提供的资源总量，P 的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 广义背包问题可以数学形式更精确地描述如下： 最大化 ∑=n i i i X P 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 背包问题在计算理论中属于NP —完全问题，其计算复杂度为O (2n )，若允许物件可以部分地装入背包，即允许X ，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P 类问题，此时计算复杂度为O (n )。

4.1.2 遗传编码 采用下标子集T 的二进制编码方案是常用的遗传编码方法。串T 的长度等于n(问题规模)，T i (1≤i ≤n )＝1表示该物件装入背包，T i ＝0表示不装入背包。基于背包问题有近似求解知识，以及考虑到遗传算法的特点（适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题），通常将P i ，S i 按P i /S i 值的大小依次排列，即P 1/S 1≥P 2/S 2≥…≥P n /S n 。 4.1.3 适应度函数 在上述编码情况下，背包问题的目标函数和约束条件可表示如下。 目标函数：∑==n i i i P T T J 1 )( 约束条件：C S T n i i i ≤∑=1 按照利用惩罚函数处理约束条件的方法，我们可构造背包问题的适应度函数f (T )如下式： f (T ) = J (T ) + g (T ) 式中g (T )为对T 超越约束条件的惩罚函数，惩罚函数可构造如下: 式中E m 为P i /S (1≤i ≤n )i 的最大值，β为合适的惩罚系数。 4.2 货郎担问题（Traveling Salesman Problem ——TSP ） 在遗传其法研究中，TSP 问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此，主要有以下几个方面的原因： (1) TSP 问题是一个典型的、易于描述却难以处理的NP 完全（NP-complete ）问题。有效地 解决TSP 问题在可计算理论上有着重要的理论价值。 (2) TSP 问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效 地解决TSP 问题有着极高的实际应用价值。 (3) TSP 问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准，而遗传算法 就其本质来说，主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP 问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP 问题等有着多方面的重要意义。

基于遗传算法的多式联运组合优化

第四章基于遗传算法的集装箱多式联运运输组合优化模型 的求解 4.1 遗传算法简介 4.1.1 遗传算法 遗传算法(Genetic Algorithm,GA)是在20世纪六七十年代由美国密歇根大学的Holland J.H.教授及其学生和同事在研究人工自适应系统中发展起来的一种随机搜索方法,通过进一步的研究逐渐形成了一个完整的理论和方法体系取名为基本遗传算法(Simple Genetic Algorithm)。在接下来几年的研究过程中Holland在研究自然和人工系统的自适应行为的过程中采用了这个算法，并在他的著作《自然系统和人工系统的适配》中对基本遗传算法的理论和方法进行了系统的阐述与描写，同时提出了在遗传算法的理论研究和发展中具有极为重要的作用的模式理论，它的编码技术和遗传操作成为了遗传算法被广泛并成功的应用的基础，经过许多学者多年来的研究，遗传算法逐渐成熟起来，到现在已经成为了一个非常大的体系，广泛的应用于组合优化、系统优化、过程控制、经济预测、模式识别以及智能控制等多个领域。De Jong于1975年在他的博士论文中设计了一系列针对于各种函数优化问题的遗传算法的执行策略，详细分析了各项性能的评价指标。在此基础上，美国伊利诺大学的Goldberg于1989年系统全面的阐述了遗传算法理论，并通过例证对遗传算法的多领域应用进行了分析，为现代遗传算法的研究和发展奠定了基础。 遗传算法是一种模仿基于自然选择的生物进化过程的随机方法，它以类似于基因的编码作为种群的个体，首先，随机的产生初始种群的个体，从这个群体开始进行搜索，根据类似于生物适应能力的适应度函数值的大小，按照不同问题各自的特点，在当前的种群中运用适当的选择策略选择适应能力大的个体，其中所选择出来的个体经过遗传操作、交叉操作以及变异操作产生下一代种群个体。如此反复，像生物的进化过程一样逐代进化，直到满足期望的终止条件为止。

Maple全局优化应用

B5: 全局优化应用 西希安工程模拟软件（上海）有限公司，2010 优化介绍 优化（optimization）的目标是从一组可能的答案中发现问题的最佳解。答案通过使用一个或多个问题变量的实际值目标函数（objective function）进行对比。可能的集合（feasible set ）由约束条件（constraints）决定，约束条件通常是关于问题变量的不等式或方程（组）。数学意义上，目的是发现目标函数的最大值（maximizes）或最小值（minimizes ）、同时满足（ satisfying）约束条件的点，这个点称为极值（extremum）。优化问题定义如下。 的最大值（或最小值 约束条件 , , 和 , 这里， 优化模型由, , 和 的结构分类。如果所有的函数是 x 线性函数，这个模型是一个线性规划（linear program）。如果 是 x 的二次函数，以及 和 是 x 的线性函数，这个模型是一个二次规划（quadratic program）。如果 是一个平方和函数，这个模型是一个非线性规划（least-squares problem）。对于其他任意结构，模型称为非线性回归（NLP）。Maple 9.5中的优化程序包（Optimization）提供了一系列算法分别求解这些类型的问题。 传统上，优化研究集中在局部搜索算法（local）。局部搜索的目的是发现 f(x) 在可行区域内的局部极值。从一个初始点出发，局部搜索算法迭代（iteratively）搜索当前点领域中的一个点，提高目标函数值，同时维持或逼近可行性、使用当前点上关于 , , 和 的迭代信息。理想情况下，搜索会终止于一个可行的局部极值。优化算法的不同决定它们如何衡量逼近可行，以及它们如何搜索。 当在可行区域内有唯一的局部极值时，局部搜索是有效的，这是因为搜索发现的局部解是问题的全局解。如果, 都是凸函数（convex），并且所有的是仿射函数（affine）时，极值是唯一的。 当 在可行区域内有许多局部极值，局部搜索难以完成。在这种情况下，局部极值的发现依赖于起始点，但可能并不是全局解。当任一个, 是非凸函数，或者任一个 是非线性函数时，存在多个局部最小值。非凸性经常存在于现实问题中，可能是求解优化问题最大的障碍。全局优化（Global）是最新的和最成功方法，能够克服这个障碍。

Web服务组合技术框架及其研究进展

第17卷第2期计算机集成制造系统 Vol.17No.22011年2月 Computer Integrated Manufacturing Systems Feb.2011 文章编号:1006-5911(2011)02-0404-09 收稿日期:2009 10 13;修订日期:2010 08 25。Received 13Oct.2009;accepted 25Aug.2010. 基金项目:国家自然科学基金资助项目(60803004);国家863计划资助项目(2009AA01Z121);浙江省科技计划资助项目(2009C31109);浙江 省教育厅科研资助项目(Y200909534)。Founda tion items:Project sup ported by th e National Natu ral Science Foundation,China(No.60803004),the National H igh T ech.R&D Program,Ch ina(No.2009AA01Z121),the S cien ce &T echnology Plan of Zhejiang Province,China(No.2009C31109),and th e Education Bureau Research Foun dation of Zhejiang Province,Chin a(No.Y200909534). Web 服务组合技术框架及其研究进展 邓水光,黄龙涛,尹建伟,李 莹,吴 健 (浙江大学计算机科学与技术学院,浙江 杭州 310027) 摘 要:为了研究Web 服务组合技术,以促使服务计算从概念走向应用,提出了Web 服务组合的技术框架,该框架涵盖了服务组合过程涉及的主要关键技术。讨论了该研究框架中的服务发现、服务组合、服务验证三大关键问题,对当前国内外的主要方法和研究成果进行了分类和比较。最后指出了服务组合面临的问题和未来的发展方向。 关键词:W eb 服务;面向服务的计算;服务发现;服务组合;服务验证中图分类号:T P393 文献标志码:A Technical framework for Web Services composition and its progress D EN G Shui guang ,H UA N G Long tao,YI N J ian wei ,LI Ying,W U J ian (Co llege of Com puter Science &T echno lo gy ,Zhejiang U niver sity,Hang zhou 310027,China) Abstract:T o study W eb Serv ices co mpo sitio n techno lo gy ,so as to push serv ice co mputatio n into application,a kind of technical fr amewo rk fo r Web Ser vices composition w as pr oposed.Some key issues w ithin this framew or k,such as ser vice discover y,ser vice composit ion methods and service ver ificatio n,w ere discussed.Its r esear ch prog ress w as also intr oduced.F inally,o pen issues and future dir ect ions wer e po int ed out. Key words:W eb Ser vices;serv ice or iented computing;ser vice discover y;ser vice composit ion;ser vice ver ification 1 问题的提出 如何解决企业应用随需应变是当今软件产业的焦点问题,而面向服务的计算(Ser vice Oriented Co mputing ,SOC)正是为解决这一问题而提出来的一种新的计算方式,其核心思想在于以服务为基本单位,通过服务组合快速构建松耦合的分布式应用系统[1]。Web 服务的不断成熟和发展为SOC 提供了最佳支撑技术,在这一背景下,Web 服务组合的研究被提上日程,并迅速吸引了国内外学者的关注[2]。 Web 服务组合是将若干服务按照一定的业务逻辑进行组装形成组合服务,并通过执行该组合服务而达到业务目标的过程。该过程涉及了众多关键 问题,本文将这些问题归纳成如图1所示的Web 服务组合技术框架。根据Web 服务组合的生命周期,该研究框架所覆盖的问题可被划分为两大类:服务组合建立时问题和服务组合运行时问题。前者主要包含了服务发现、服务合成、服务组合描述和服务组合验证等问题,后者包含了服务组合执行与监控、服务组合的安全与事务管理等问题。由于服务组合的执行监控与工作流相似,专门研究这一问题的文献并不多见。此外,Web 服务本身的安全与事务研究刚刚起步,也鲜见于国内外文献中。因此,本文重在探索服务组合建立时问题的研究现状。鉴于已有学者对Web 服务组合建模语言进行了综述[3],本文着重介绍服务发现方法、服务组合方法和服务验证方法的研究进展。

遗传算法及优化问题重要有代码

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显着特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算． 1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下：

（2）遗传算法的步骤 遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection）、交叉（Crossover）、变异（Mutation）． 遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制

启发式优化算法综述

启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，

以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。 二、启发式算法类型

何为服务组合

服务组合综述 近年来，随着Web服务相关标准的持续完善和支持Web 服务的企业级软件平台的不断成熟，越来越多的稳定易用Web服务共享在网络上。然而单个Web服务的功能有限，难以满足实际应用中的多种多样的需求，因此为了更加充分地利用共享的Web服务，有必要将共享的Web服务组合起来，提供功能更为强大的服务。Web服务组合的研究正是在这种背景下被提出来，并吸引了工业界和学术界的广泛关注。 1. 基本概念 1.1 Web服务 Web 服务是基于网络的、分布式的、自描述的、模块化的组件, 它执行特定的任务, 遵循一定的技术规范, 提供了面向Internet应用的统一服务发布、发现、调用和合成机制。现在它已经成为广域环境下实现互操作的一种主要机制, 得到产业界和学术界的广泛认可。1.2 Web服务组合 由于目前尚未有统一的定义，不同的研究人员从不同的角度对Web 服务组合问题进行定义。我们对 Web服务组合提出一个更为通用和完整的定义：利用Internet上分布的现有Web服务，根据用户的应用需求，把相对简单的服务按照一定的逻辑方式组合起来，从而组合成更强大、更完整的服务的过程。Web服务组合可以利用较小的、较简单的、且易于执行的轻量级服务来创建功能更为丰富、更易于用户定制的复杂服务，从而能够将松散耦合的、分散在Internet上的各类相关 Web服务有机地组织成一个更为可用的系统，支持企业内、外部的企业应用集成和电子商务等网络应用。 Web 服务组合方法从组合方案生成方式来分有两大类：静态组合和动态组合。静态组合意味着请求者应在组合计划实施前就创建一个抽象的过程模型。抽象的过程模型包括任务的集合以及任务间的数据依赖关系, 每个任务包含一个查询的子句, 用来查找完成任务的真正的Web 服务。而动态组合不仅自动地选择、绑定Web 服务, 同时更重要的是自动地创建过程模型。 2. Web服务相关技术 Web服务的主要思想，就是未来的应用将由一组应用了网络的服务组合而成，只要求两个等同的服务使用统一标准和方法描述自己；Web服务另外一个重要的思想就是：所有东西

Web服务组合综述

Web服务组合综述 【摘要】近年来，Web服务技术作为服务计算（SOC）和面向服务架构（SOA）的主要实现技术，已经得到广泛应用，工业界和学术界分别从不同的角度对Web 服务的相关技术展开研究。本文详细阐述了服务组合的概念、框架和分类，分析了几种常用的Web服务组合方法，并对这几种组合方法作了比较，最后，对Web 服务组合方法进行了总结。 【关键词】Web服务；组合方法；服务组合；工作流 1.引言 近年来，电子商务的迅速发展，使得基于网络的、分布式的、模块化的Web 服务技术得到快速发展和广泛应用，Web服务遵循一定的技术规范，执行一定的任务。随着Web服务标准的持续完善和支持Web服务的企业级软件平台的不断成熟，越来越多的企业和商业组织参与到软件服务化（SaaS）的行列中来，纷纷将其业务功能和组件包装成标准的Web服务发布出去，实现快速便捷地寻求合作伙伴，挖掘潜在的客户和达到业务增值的目的[1]。然而，目前网络上发布的服务大多数都存在结构简单、功能单一的缺陷，无法满足企业复杂应用的需求。如何有效地组合分布于网络中的各种服务，实现服务之间的无缝集成，形成功能强大的企业级服务流程以完成企业的商业目标，已经成为Web服务发展过程中的一个重要步骤，也是SOC与SOA能否成功应用和实施的关键[2]。 2.Web服务基本概念 Web服务组合源于软件重用.其基本思想是使用现有的Web服务，通过它们一定顺序的组合或组合顺序的改变，创建出新的或更高质量的服务满足用户的需求。 2.1 Web服务概念 目前对Web服务组合尚无统一的定义，很多研究者从不同的角度和侧重点对Web服务组合给出了不同的定义。[3] 对Web服务组合定义是指由多个小粒度的Web服务相互之间通信和协作来实现大粒度的服务功能；通过有效地联合各种不同功能的Web服务，服务开发者可以借此解决较为复杂的问题，实现增值服务。 IBM对服务组合定义[4]是满足业务流程逻辑的一组Web服务，通过制定不同Web服务执行顺序和交互过程来实现新的业务功能。[5] 从两个不同的研究角度对Web服务组合进行了定义：（1）基于过程模型：从WSC内在因素的角度，将其定义为一个依赖于特定控制流和数据流结合起来的、能够完成一定任务的Web服务集合。（2）基于构件单元：从构件的角度，将WSC定义为一个由自治且能相互协作的自描述单元所组成的系统。 文献[1]提出了一个更为通用和完整的Web服务组合定义：用现有的分散的、小粒度的原子服务，根据服务请求者的需求，在某一特定的Web服务组合框架下，自动地选择满足需要的若干服务，并使它们按照一定的组合规则协同工作完成服务请求。 2.2 Web服务组合架构 典型的Web服务组合（WSC）的实现框架包括2种用户角色（服务请求者和服务提供者）和5个部件（翻译器、组合管理器、执行引擎、服务匹配器和服务库），可选部件本体库为服务描述提供本体定义和推理支持，如图1所示。WSC

组合最优化简介

weili@https://www.wendangku.net/doc/b31040962.html,

主要内容 ?组合最优化问题概论 ?现代最优化计算方法 –禁忌搜索（tabu search） –模拟退火（simulated annealing） –遗传算法（genetic algorithms） –人工神经网络（neural networks） –拉格朗日松弛算法（Lagrange slack arithmetic）

?组合最优化（combinatorial optimization ） –是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等 –组合最优化问题的数学模型 其中，f(x)为目标函数，g(x)为约束函数，x 为决策变量，D 表示有限个点组成的集合 D x 0 g(x) .t .s ) x (f min ∈≥

?组合最优化（combinatorial optimization ） –一个组合最优化问题可用三参数（D,F,f ）表示，其中D 表示决策变量的定义域，F 表示可行解区域F 中的任何一个元素称为该问题的可行解，f 表示目标函数。满足的可行解称为该问题的最优解 –组合最优化的特点是：可行解集合为有限点集 –有可行解一定有最优解 }0)x (g ,D x |x {F ≥∈=}F x |x)(f {min )x (f *∈=*x

?组合最优化问题 例1.（最优投资问题）设一个人的财富为b ，现有n 只价格为、预期收益分别为的股票，如何选择投资策略使得该人投资收益最大？解：用数学模型表示为： )n ,2,1i (a i L =)n ,2,1i (c i L =(3) n ,2,1i },1,0{ x (2) ,b x a .t .s (1) x c max i n 1 i i i n 1 i i i L =∈≤∑∑==

粒子群算法和蚁群算法的结合及其在组合优化中的应用e

2007年第2期空间电子技术收稿日期：2006-04-03；收修改稿日期：2006-04-30 粒子群算法和蚁群算法的结合及其在 组合优化中的应用 张长春苏昕易克初 （西安电子科技大学综合业务网国家重点实验室，西安710071） 摘要文章首次提出了一种用于求解组合优化问题的PAAA 算法。该算法有效地 结合了粒子群算法和蚁群算法的优点，先利用粒子群算法的随机性、快速性、全局性得到 初始信息素分布（即粗搜索），再利用蚁群算法的并行性、正反馈性、求解精度高等优点求 精确解（即细搜索）。将文中提出的算法用于经典TSP 问题的求解，仿真结果表明PAAA 算 法兼有两种算法的优点，同时抛弃了各自的缺点。该算法在时间效率上优于蚁群算法，在 求精效率上优于粒子群算法，是综合了两种算法长处的一种新的启发式算法，达到时间性 能和优化性能上的双赢，获得了非常好的效果。 主题词蚁群算法粒子群算法旅行商问题PAAA 0引言 近年来对生物启发式计算（Bio-inspired Computing ）的研究，越来越引起众多学者的关注和兴趣，产生了神经网络、遗传算法、模拟退火、粒子群算法、蚁群算法等许多用于解决复杂优化问题的新方法。然而，面对各种问题的特殊性和复杂性，每种算法都表现出了自身的优势和缺陷，都存在时间性能和优化性能不能兼得的矛盾。 粒子群优化（Particie Swarm Optimization ，PSO ）算法[1， 2]是由Eberhart 和Kennedy 于1995年提出的一种全局优化算法，该算法源于对鸟群觅食行为的模拟。它的优势在于：（1） 算法简洁，可调参数少，易于实现；（2） 随机初始化种群，具有较强的全局搜索能力，类似于遗传算法；（3）利用评价函数衡量个体的优劣程度，搜索速度快；（4）具有较强的可扩展性。其缺点是：不能充分利用系统中的反馈信息，求解组合优化问题的能力不强。 蚁群算法[3，4]（Ant Coiony Optimization ，ACO ） 是由意大利学者M.Dorigo ，V.Maniezzo 和A.Coiorni 于20世纪90年代初提出的一种新型的智能优化算法，已经被应用到TSP 问题[5，6]、二次分配问题、工 件调度问题、图着色问题等许多经典组合优化问题中，取得了很好的效果。它的优点是：（1）采用一种正反馈机制，通过信息素的不断更新，达到最终收敛于最优路径上的目的；（2）是一种分布式的优化方法，易于并行实现；（3）是一种全局优化的方法，不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（4）适合于求解离散优化问题；（5）鲁棒性强。但由于在算法的初始阶段信息素匮乏，所以求解速度较慢。 文章将粒子群算法和蚁群算法有机地结合，提出了PAAA 算法。它利用粒子群算法的较强的全局搜索能力生成信息素分布，再利用蚁群算法的正反馈机制求问题的精确解，汲取各自的优势，以达空间电子技术 SPACE ELECTRONIC TECHNOLOGY !"

遗传算法及其在TSP问题中的应用

遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机

2011-组合优化问题简约与算法推演

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/b31040962.html, Journal of Software,2011,22(9):1985?1993 [doi: 10.3724/SP.J.1001.2011.03948] https://www.wendangku.net/doc/b31040962.html, +86-10-62562563 ?中国科学院软件研究所版权所有. Tel/Fax: ? 组合优化问题简约与算法推演 郑宇军1,2+, 薛锦云1,2, 凌海风3 1(中国科学院软件研究所计算机科学国家重点实验室,北京 100190) 2(江西师范大学江西省高性能计算重点实验室,江西南昌 330027) 3(南京大学管理工程学院,江苏南京 210093) Combinatorial Optimization Problem Reduction and Algorithm Derivation ZHENG Yu-Jun1,2+, XUE Jin-Yun1,2, LING Hai-Feng3 1(The State Key Laboratory of Computer Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China) 2(Provincial Key Laboratory of High Performance Computing, Jiangxi Normal University, Nanchang 330027, China) 3(School of Management and Engineering, Nanjing University, Nanjing 210093, China) + Corresponding author: E-mail: yujun.zheng@https://www.wendangku.net/doc/b31040962.html, Zheng YJ, Xue JY, Ling HF. Combinatorial optimization problem reduction and algorithm derivation. Journal of Software, 2011,22(9):1985?1993. https://www.wendangku.net/doc/b31040962.html,/1000-9825/3948.htm Abstract: A unified algebraic model is used to represent optimization problems, which uses a transformational approach that starts from an initial problem specification and reduces it into sub-problems with less complexity. The model then constructs the problem reduction graph (PRG) describing the recurrence relations between the problem, and derives an algorithm with its correctness proof hand-in-hand. A prototype system that implements the formal algorithm development process mechanically is also designed. This approach significantly improves the automation of algorithmic program design and helps to understand inherent characteristics of the algorithms. Key words: combinatorial optimization problem; problem reduction; algorithm derivation; PAR (partition-and- recur); correctness proof 摘要: 针对组合优化类问题定义了代数结构模型,从问题的形式规约出发,通过一阶谓词和量词演算将问题逐 步简约为搜索空间更小、复杂度更低的子问题,根据问题的简约关系推导出求解算法,并在构造算法的同时也证明 了算法的正确性.开发了原型系统以支持上述形式化的开发过程.这种算法推演技术能够显著提高算法程序设计的 自动化水平,而问题简约的思想也更有利于对算法本质特征的理解. 关键词: 组合优化问题;问题简约;算法推演;PAR(partition-and-recur);正确性证明 中图法分类号: TP301文献标识码: A 组合优化问题是指在离散有限的数学结构中和给定的约束条件下寻找目标函数最优值的问题,它是组合 数学、运筹学和理论计算机科学中长期研究的重要问题之一.传统的组合优化算法设计策略(如动态规划、贪 心、回溯等)有着各自不同的适用范围,而且缺乏策略选择的有效标准[1],因而极大地限制了算法开发的形式化 ?基金项目: 国家自然科学基金(61105073, 60773054); 科技部国际科学技术合作项目(2008DFA11940) 收稿时间: 2009-09-25; 定稿时间: 2010-09-06

遗传算法

遗传算法 开放分类：编程、程序、数学、计算机、算法 目录 ? 遗传算法定义 ? 遗传算法特点 ? 遗传算法的应用 ? 遗传算法的现状 ? 遗传算法的一般算法 ? 遗传算法实例 遗传算法定义 [编辑本段] 遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。 遗传算法特点 [编辑本段] 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：1、遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。 2、遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 3、遗传算法使用多个点的搜索信息，具有隐含并行性。 4、遗传算法使用概率搜索技术，而非确定性规则。 遗传算法的应用 [编辑本段] 由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响

组合最优化问题及其求解优化算法

组合最优化问题最基本的特点就是变量是离散的, 由此导致其数学模型中的目标函数和约束函数在其可行域内是也是离散的。在现实世界中，许多的实际问题本质上是离散事件的而不是连续事件，都可归结为组合最优化问题。这类问题在理论上多数都属于NP难问题，NP类问题仍属于可计算问题，即存在算法来求解。求解这类组合最优化问题方法分为精确算法和近似算法两类。 常用的精确算法有动态规划、分支定界和枚举等。精确算法只能解决一些小规模问题，当求解小规模组合优化问题时可以用这类精确算法在较短的时间内得到最优解。当求解大规模组合优化问题时，理论上可以得到问题的最优解，但由于计算量太大，所以使用精确算法并不可行。利用精确算法求解NP-hard组合优化问题时，即使能得到最优解，但所需要的计算时间过长，在实际问题中难以直接应用。 近似算法是指在合理的计算时间内找到一个近似的最优解。近似算法虽然求解速度较快，但并不能保证得到问题的全局最优解。近似算法分为基于数学规划（最优化）的近似算法、启发式算法和基于智能优化的近似算法。 1) 基于数学规划（最优化）的近似算法是根据对问题建立的数学规划模型，运用如拉格朗日松弛、列生成等算法以获得问题的近似解，是以数学模型为基础，采用列生成、拉格朗日松弛和状态空间松弛等求解问题。 拉格朗日松弛（LR）算法求解问题的主要思想是分解和协调。首先对于NP难的优化问题，其数学模型须具有可分离性。通过使用拉格朗日乘子向量将模型中复杂的耦合约束引入目标函数，使耦合约束解除，形成松弛问题，从而分解为一些相互独立的易于求解的子问题，设计有效的算法求得所有子问题的最优解。利用乘子的迭代更新来实现子问题解的协调。列生成(Column generation, CG)算法是一种已经被认可的成功用于求解大规模线性规划、整数规划及混合整数规划问题的算法。 与智能优化算法相比，基于数学规划的近似算法的优点是通过建立问题的数学模型，松弛模型中难解的耦合约束或整数约束，得到的松弛问题的最优解可以为原问题提供一个下界。同时基于数学规划的近似算法还具有很好的自我评价功能，通过算法运行给出的问题的近优解(或最优解)为原问题提供一个上界，上界与下界进行比较，可以衡量算法的性能。 2) 启发式算法根据求解问题的特点，按照人们经验或某种规则设计的。这是一种构造式算法，比较直观、快速，利用问题的知识设计求解的方法步骤，相对比较简单，这种方法的求解速度较快，但所得解的质量不一定好。 3) 基于智能优化的近似算法是基于一定的优化搜索机制，并具有全局优化性能的一类算法。这类智能优化算法常见的有：模拟退火(SA)、遗传算法(GA)、蚁群算法(ACO)、路径重连算法(PR)、迭代局部搜索算法(ILS)、禁忌搜索算法(TS)、分散搜索算法(SS)、粒子群算法(PSO)等，这些算法也称超启发式算法(Meta-heuristic)。 智能优化算法是一种通用的算法框架，只要根据具体问题特点对这种算法框架结构进行局部修改，就可以直接应用它去解决不同的问题。这类算法本身不局限于某个框架，具有实践的通用性，适应于求解工业实际问题，能较快地处理大规模数据的同时得到令人满意的解。基于智能优化的近似算法，采用不同的搜索策略和优化搜索机制，寻找问题的近似最优解，具有很好的求解优势。虽然基于智能优化的近似算法不能保证求得全局最优解，但因其高效的优化性能、无需问题特殊信息、易于实现且速度较快等优点, 受到诸多领域广泛的关注和应用。基于智能优化的近似算法(超启发式算法)成为求解复杂组合最优化问题主要的有效方法。