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

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/5e13221755.html,

Journal of Software,2011,22(9):1985?1993 [doi: 10.3724/SP.J.1001.2011.03948] https://www.wendangku.net/doc/5e13221755.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/5e13221755.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/5e13221755.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

1986 Journal of Software软件学报 V ol.22, No.9, September 2011

和自动化水平.

20世纪80年代以来,人们提出了一些抽象代数模型来精确刻画组合优化问题的结构和求解过程,但复杂的

表示法使其难以在计算机上进行有效实现.如Helman[2]的搜索模型将解空间视为一组连接子的集合,求解过程

就是通过反复执行连接子的横向组合和纵向组合来对解空间进行隐式枚举搜索,组合过程中采用的不同计算

辅助关系可以用于不同类型的算法设计[3,4].Kumar和Kanal等人[5?7]对与或图、游戏树等特定结构上的最优化

问题进行了形式化的定义,通过抽象的分支限界和动态规划方法对这些结构上的多种具体算法进行了统一归

纳,从而简化了算法的开发和证明,但其应用范围在很大程度上受到数据结构的限制,一些搜索算法还要求特殊

的结构性质,适应性和可扩展性不强.Bird和Meertens提出的B-M公理表示法[8,9]同样提倡从问题规约出发,通

过应用融合(fusion)和提升(promotion)等一系列定理逐步推导算法,但该方法需要在各种问题结构上定义大量

的定理和规则,其表示法不易于使用[10],且推导结果很难直接转换为结构化程序.

除了递归程序变换等较简单的功能,早期的算法生成系统[11?13]需要设计人员的干预较多.南京大学开发的

NDADAS系统[14,15]基于函数分解树模型来将问题逐步分解成可直接求解的若干子函数,通过CASE结构形成、

直接替换、递归节点生成等规则来支持许多算法的机械化设计,但并不保证这些规则和分解出的子函数能够满

足求解需求,其后续研究也转向使用机器学习等技术简化人工设计[16].美国Kestrel研究所的KIDS系统[17]则通

过演绎推理、有限差分、部分求值和类型求精等一系列技术生成算法程序,后续的Designware系统[18]进一步

将设计知识分类存放在数据库中,并借助范畴论工具来提高自动化水平.不过,其最关键的设计策略在很大程度

上仍需要手工选择,问题/算法的种类和范围也始终存在较大的限制.

以我们前期的PAR(partition-and-recur)方法[1,19]研究为基础,同时借鉴相关研究中算法形式化开发和程序

自动生成的思想,本文提出了一种新的组合优化算法设计方法.它从组合优化问题的代数规约出发,通过谓词和

量词演算将问题逐步简约为更易求解的子问题,在此基础上得到正确高效的算法程序;开发的实验系统已成功

应用于多个典型组合优化算法的自动生成.

1 问题简约模型和方法

使用结构化的代数规约,一个问题可由问题输入域以及从输入到输出的构造方式来刻画.给定问题输入域

D和输出域R,那么一般组合优化问题的规约可定义为

P(d)≡(Q z:c(z)∧z∈ζ(d):f(z)) (1) 其中:Q为二元运算符q的一般化量词,对于优化类问题,q一般取min或max;ζ:D→SET(Z)为解空间生成函数;

c:Z→BOOLEAN为解的可行性约束函数;f:Z→REAL为解的目标函数.

人们处理复杂问题的一个基本方法就是将其分解为更简单的子问题.采用穷举法求解问题(1)时,需要搜索

的解空间为{z|c(z)∧z∈ζ(d)},那么我们对同一结构上问题间的关系作如下定义[20]:

定义1. 问题P′(d′)=?ζ′,c′,f?称为问题P(d)=?ζ,c,f?的等价问题,当且仅当{z|c′(z)∧z∈ζ′(d′)}={z|c(z)∧z∈ζ(d)}.

定义2. 问题P′(d′)=?ζ,c′,f?称为问题P(d)=?ζ,c,f?的子问题,当且仅当ζ′(d′)?ζ(d)并且?z∈ζ(d′):c′(z)?c(z).

定义2还可以细分为以下3种情况:

定义3. 如果P′(d′)=?ζ,c′,f?为P(d)=?ζ,c,f?子问题,且c′≠c,那么称P′(d′)=?ζ,c′,f?为P(d)的派生子问题.

定义4. 问题P(d′)=?ζ,c,f?称为问题P(d)=?ζ,c,f?的直接子问题,当且仅当ζ(d′)?ζ(d).

定义5. 问题P′(d′)=?ζ,c∧c1,f?称为问题P(d)=?ζ,c,f?的强化约束子问题(简称为强化问题);相反,P(d)称为

P′(d′)的放松约束问题(简称为放松问题).

将函数分解关系代入初始问题规约,通过谓词和量词演算来对规约进行变换,不断地将问题简约为更易求

解的子问题,最后根据简约过程和演算结果得出问题的求解算法.

问题的简约过程可以通过问题简约图(problem reduction graph,简称PRG)形象地描述.PRG是一个有向无

环图,其中每一个节点都代表一个问题;图中的一个无入边的特殊节点称为根节点,它表示要求解的原始问题;

无出边的节点称为叶节点或终点,它们表示可直接求解的问题;设问题P(d)被简约为一组子问题P1(d1),

郑宇军等:组合优化问题简约与算法推演1987

P2(d2),…,P n(d n),那么从P(d)到每个P i(d i)绘制一条边,P i(d i)称为P(d)的子节点(0

2 算法推演技术

2.1 基本演算规则

从问题的初始代数规约出发,通过不断应用数学定律、一阶谓词演算、量词性质等演算规则,能够对问题规约进行不断变化,从而进行问题简约和算法推演.除了常用的数学定律和谓词演算规则外,表1中的量词性质在组合优化算法推演中起到关键性的作用.

Table 1Main quantifier rules for algorithm calculation

表1主要的量词演算规则

Rules Equations Remark Cartesian product (Q i,J: r(i)∧s(i,J): f(i,J)) ≡ (Q i:r(i): (Q J: s(i,J): f(i,J)))

variable, and s(i,J) is a predicate of i and J Range splitting (Q i: r(i): f(i)) ≡ (Q i: r(i)∧b(i):f(i)) q (Q i: r(i)∧?b(i): f(i))b(i) is a boolean expression of i

Single range (Q i: i=k: f(i)) ≡f(k) Range disjunction (Q i: r(i)∨s(i): f(i)) ≡ (Q i: r(i):f(i)) q (Q i: s(i): f(i)) q is an idempotent operator Functional associativity (Q i: r(i): f(i) Q g(i)) ≡(Q i: r(i):f(i)) q (Q i: r(i):g(i))

Functional commutativity (Q i: r(i):(Q j:s(j):f(i,j))) ≡ (Q j:s(j):(Q i:r(i):f(i,j)))

General distributivity (Q i: r(i): g?f(i)) ≡g?(Q i: r(i): f(i))

? is a commutative binary operator and is

associative with respect to q, and x is not a

free variable of g

Functional distributivity g((Q i:r(i):f(i))) = (P i:r(i):g(f(i))) g(a q b)＝g(a)p g(b) where P is the

generalized quantifiers of p ?-rule (?i: r(i)∧s(i): p(i)) ≡ (?i: r(i): s(i) => p(i))

?-rule (?i: r(i)∧s(i): p(i)) ≡ (?i: r(i): s(i)∧p(i))

Conditional separation (Q i: r(i)∨(s(i)∧t(i)): f(i)) ≡

(Q i: r(i): f(i)) q (Q i: s(i): f(i)), if t(i) (Q i: r(i): f(i)), else

基于抽象规约(1),对组合优化问题进行简约的出发点一般有两种:

(1) 分解生成函数ζ(d)=ζ1(d)∪ζ2(d)∪…∪ζm(d);

(2) 分解约束函数c(z) = c1(z)∪c2(z)∪…∪c m(z).

将函数分解关系代入初始问题规约,之后就可以通过谓词和量词演算来对规约进行变换,不断将问题简约

为更易求解的子问题,最后根据简约过程和演算结果得出问题的求解算法.

2.2 算法推演与效率提升

毋庸置疑,抽象规约(1)本身就蕴含了问题的求解算法,即遍历解空间ζ(d)中每一个满足可行性约束c(z)的

解,找出其中目标函数值f(z)最优的一个.但这样的穷举算法在绝大多数情况下都是低效的,各种高效算法则往

往需要设计人员去发现和证明.而使用逻辑推演来简约问题,能够自动确定问题与子问题最优解之间的关系,同

时,自动发现并合并相同或等价的子问题(即在PRG中不能包含两个相同或等价的问题节点),从而提高了算法

的求解效率.

例1:最大子段和问题.给定一个整数序列A n={a1,a2,…,a n},要找出其元素之和最大的子序列.设ss为所有子

序列的生成函数,那么该问题的规约为

MS(A n)≡(MAX z:z∈ss(A n):sum(z)) (2) 该问题的生成函数可以划分为ss(A n)={a n}∪ss(A n?1)∪{z|z=z′↑a n∧z′∈ss(A n?1)∧last(z′)=a n?1},即A n的子序列

要么是A n?1的子序列,要么以a n结尾(可以只含a n).将其代入问题规约并进行推演可得:

MS(A n)

1988 Journal of Software软件学报 V ol.22, No.9, September 2011

≡(MAX z:z=a n∨z∈ss(A n?1)∨(z=z′↑a n∧z′∈ss(A n?1)∧last(z′)=a n?1):sum(z))

≡[范围分裂]

max((MAX z:z=a n:sum(z)),(MAX z:z∈ss(A n?1):sum(z)),(MAX z′:z′∈ss(A n?1)∧last(z′)=a n?1:sum(z′↑a n)))

≡[单点范围和卷叠]

max(a n,MS(A n?1),(MAX z′:z′∈ss(A n?1)∧last(z′)=a n?1:sum(z′)+a n))

≡[令MS′(A n)≡(MAX z:z∈ss(A n)∧last(z)=a n:sum(z))]

max(a n,MS(A n?1),MS′(A n?1)+a n)

≡[a n≤MS′(A n?1)+a n]

max(MS(A n?1),MS′(A n?1)+a n)

其中,MS′(A n)为原问题的派生子问题,对其继续进行推演可得:

MS′(A n)

≡[等价问题]

(MAX i:0

≡[范围分裂:(0

max((MAX i:0

≡[单点范围和卷叠]

max(MS′(A n?1)+a n,a n))

将原问题与子问题的简约关系合并,就可以得到如下线性算法:

Algorithm MS(A n).

begin

ms←0; ms′←0;

for i=1 to n do

ms′←max(ms′+a i,a i);

ms←max(ms,ms′);

return ms;

end.

例2:最小时间调度问题.给定要在某机器上完成的一组任务S n={1,2,…,n},其中,第i项任务需要的处理时间

为t i.要确定这些任务的一个调度,使得所有任务的完成时间之和最小.设z为S n的一个排列,那么其中第z i项

t).令ps返回一个序列的所有排列,那么该问题的规约

任务的完成时间就是(Σj:0

j z

MTS(S n)≡(MIN z:z∈ps(S n):(Σi:0

t))) (3)

j z

该问题的生成函数可以划分为ps(S n)=(∪i:0

MTS(S n)

t))

≡(MIN z:z∈(∪k:0

i z

≡[交叉积]

(MIN k:0

t)))

i z

≡[范围分裂和单点范围]

(MIN k:0

t)))

i z

≡[卷叠]

(MIN k:0

这样得到的是原问题与其多个子问题的简约关系,其蕴含的算法效率并不高.不过,对此还可以做进一步简

约:易证MST(S n\{i})?MST(S n\{j})≤n(t j?t i),故i≤j?nt i+MST(S n\{i})≤nt j+MST(S n\{j}),那么令k*=(MIN k:0

t k),简约关系中其他子问题就都可以消去,最后得到:

郑宇军 等:组合优化问题简约与算法推演

1989

MTS (S n )≡*k nt +MST (S n \{k *}) (4)

从简约关系(4)中很容易得到求解该问题的线性算法,即按t k 由小到大的顺序安排任务调度.

例1和例2推演得到的都是线性算法,但它们既有相同点又有不同点.相同点是二者都存在最优子结构性质,这是动态规划法的基本特征[21];基于最优结构的贪心算法则可视为是动态规划法的精化[22].例1推演得到的算法属于动态规划算法;而例2还满足特殊的性质,故进一步得到了贪心算法.

许多可应用贪心算法的问题都具有如下性质:在将原问题简约到多个子问题时,如果这些子问题满足某些附加的单调性质,使得只有一个或少数几个子问题需要保留,而其他的子问题可以被舍去.我们称此简约为“贪心简约”.形式化地,设问题P (d )与其子问题之间的简约关系为(以最小值问题为例)

P (d )≡min(P 1(d ⊙e 1)⊕w (e 1),P 2(d ⊙e 2)⊕w (e 2),…,P n (d ⊙e n )⊕w (e n )) (5) 其中,e 1,e 2,…,e n ∈E 称为问题的单点域,⊙:D ×E →D 称为单点函数,⊕为目标函数值域上的二元算子.如果能够找到E 上的某个单调函数v ,使得v (e i )≤v (e j )?P i (d ⊙e i )⊕w (e i )≤P j (d ⊙e j )⊕w (e j ),那么可以选取各单点对象中v 值最小的e k ,这样就得到了对于P (d )的贪心简约:

P (d )≡P k (d ⊙e k )⊕w (e k ) (6) 这种方式不仅适用于推演符合拟阵结构[23]的贪心选择算法,也同样适用于不符合拟阵结构的其他贪心算法(如以上最小时间调度算法、Huffman 编码算法等).

2.3 分支限界、近似和参数化策略

动态规划和贪心法是寻求多项式时间算法的两种基本方法,难以有效应用对于大量NP 难题.分支限界法是为复杂问题设计确定性算法的主要手段,通过问题简约过程来生成分支限界算法的基本步骤为:

(1) 将原始问题标记为活节点,其目标函数收益为0;

(2) 选取一个活节点,对其进行简约得到一组子问题;

(3) 对于可直接求解的子问题,计算其目标函数值,并对当前最优解进行更新;

(4) 舍去那些无解或不能导致最优解的子问题,而将其余的子问题标记为活节点,其目标函数收益由父

节点及其到当前节点的简约关系确定;

(5) 重复第(2)步,直至不再有未处理过的活节点.

设某个子问题的目标函数值上界为x ,而该节点的当前收益为y ,如果x +y 不优于当前最优解,那么可以判断其不能导致最优解,该节点可以被舍弃.问题的上界可由其放松问题的解来确定,而活节点的选取方式则决定了分支限界法是按照广度优先、深度优先还是效益优先的方式执行.

以0-1背包问题为例,给定背包容量W 和一组物品A n ={a 1,a 2,…,a n },其中,a i 的重量和价值分别为w (a i )和v (a i ),那么问题规约为

KS (A n ,W )≡(MAX z :w (z )≤W ∧z ∈P (A n ):v (z )) (7) 其生成函数为幂集函数,分解形式为P (A n )=P (A n ?1)∪{z |z =z ′∪{a n }∧z ′∈P (A n ?1)},那么推演过程为: KS (A n )

≡(MAX z :w (z )≤W ∧(z ∈P (A n ?1)∨(z =z ′∪{a n }∧z ′∈P (A n ?1))):v (z ))

≡[范围分裂]

max((MAX z :w (z )≤W ∧(z ∈P (A n ?1):v (z )),(MAX z ′:w (z ′∪{a n })≤W ∧z ′∈P (A n ?1):v (z ′∪{a n })))

≡[卷叠]

max(KS (A n ?1),(MAX z ′:w (z ′)∧z ′≤W ?w (a n )∧z ′∈P (A n ?1)=v (z ′)+v (a n )))

≡[条件分离和卷叠]

111max((,),(,())()), if ()((,), else

n n n n n n KS A W KS A W w a v a w a W KS A W ????+???≤ 问题的简约可一直持续到KS (Φ,W ′)=0,采用深度优先的策略就得到了问题的回溯算法.再通过上界限制能

1990 Journal of Software软件学报 V ol.22, No.9, September 2011

够显著减小搜索范围,其上界可为无约束问题MAX z:z∈P(A n):v(z)的解v(A n),也可为放松约束的连续背包问题的

解(由贪心算法求得).

许多NP难题在实际应用中只需要找到一个近似最优解.在算法推演的过程中,可以舍弃一些复杂的问题

节点来提高算法效率,并根据问题的简约关系来估算解的近似程度.

仍以0-1背包问题为例,不失一般性,令w(a i)≤W,那么在前述推演的基础上可得:

KS(A n,W)≡(MAX i:0

如果对各个子问题KS(A n\a i,W?w(a i))不再进行完整的推演,而只是分别进行贪心简约,那么就得到了近似

比为2的多项式算法.进一步地,如果贪心简约是从PRG的第k层开始进行,那么算法的近似比将为1+1/k,即0-1

背包问题具有多项式时间的近似框架[24].

NP完全问题并不意味着该问题的所有实例都是难以求解的.参数复杂性理论[25]就将问题的部分输入视为

参数,那么在特定的参数范围内,问题也很可能是容易求解的.以最小顶点覆盖问题为例,给定图G=(V m,E n),要找

出V中的一个最小顶点集,使得对于E中的每一条边x,左端点x.a和右端点x.b至少有一个属于该顶点集,那么

问题的规约为

MVC(V m,E n)≡(MIN z:(?x:x∈E n:x.a∈z∨x.b∈z)∧z∈P(V m):|z|) (8) 令N(a)表示与顶点a相邻的所有边集,那么约束条件可分解为

(e n.a∈z∧(?x:x∈E n\N(e n.a):x.a∈z∨x.b∈z))∨(e n.b∈z∧(?x:x∈\N(e n.b):x.a∈z∨x.b∈z)).

在此基础上,可对问题作如下推演:

MVC(V m,E n)

≡(MIN z:((e n.a∈z∧(?x:x∈E n\N(e n.a):x.a∈z∨x.b∈z))∨(e n.b∈z∧(?x:x∈\N(e n.b):x.a∈z∨x.b∈z)))∧z∈P(V m)):|z|)

≡[范围分裂]

min((MIN z:e n.a∈z∧(?x:x∈E n\N(e n.a):x.a∈z∨x.b∈z)∧z∈P(V m):|z|),

(MIN z:e n.b∈z∧(?x:x∈\N(e n.b):x.a∈z∨x.b∈z)∧z∈P(V m):|z|))

≡[拆分V m]

min((MIN z′:(?x:x∈E n\N(e n.a):x.a∈z′∨x.b∈z′)∧z′∈P(V m\{e n.a}):|z′∪{e n.a}|),

(MIN z′:(?x:x∈\N(e n.b):x.a∈z′∨x.b∈z′)∧z′∈P(V m\{e n.b}):|z′∪{e n.b}|))

≡[单点范围和范围分裂]

min((MIN z′:(?x:x∈E n\N(e n.a):x.a∈z′∨x.b∈z′)∧z′∈P(V m\{e n.a}):|z′|)+1,

(MIN z′:(?x:x∈\N(e n.b):x.a∈z′∨x.b∈z′)∧z′∈P(V m\{e n.b}):|z′|)+1)

≡[卷叠]

min(MVC(V m\{e n.a},E n\N(e n.a))+1,MVC(V m\{e n.b},E n\N(e n.b))+1)

而对于判断图G=(V m,E n)是否有度数小于k的最小顶点覆盖的参数化问题MVC(V m,E n,k),基于上述推演过

程可得

MVC(V m,E n,k)≡min(MVC(V m\{e n.a},E n\N(e n.a),k?1),MVC(V m\{e n.b},E n\N(e n.b),k?1)).

这样就得到了该问题的固定参数算法,由于问题简约至多只需要执行k层,得到的参数化算法的时间复杂

度为O(2k|V|).由于参数化算法可以方便地进行组合,对原始问题规约还可以再次基于生成函数的分解关系

P(V m)=P(V m?1)∪{z|z=z′∪{v m}∧z′∈P(V m?1)进行如下推演:

MVC(V m,E n)

≡(MIN z:z:(?x:x∈E n:x.a∈z∨x.b∈z)∧(z∈P(V m?1)∨(z=z′∪{v m}∧z′∈P(V m?1))):|z|)

≡[范围分裂]

min((MIN z:(?x:x∈E n:x.a∈z∨x.b∈z)∧z∈P(V m?1):v(z)),

(MIN z′:(?x:x∈E n\N(v m):x.a∈z′∨x.b∈z′)∧z′∈P(V m?1):|z′∪{v m}|))

≡[卷叠和单点范围]

郑宇军 等:组合优化问题简约与算法推演

1991

min(MVC (V m ?1,E n ),(MIN z ′:(?x :x ∈E n \N (v m ):x .a ∈z ′∨x .b ∈z ′)∧z ′∈P (V m ?1):|z ′|+1))

≡[卷叠]

min(MVC (V m ?1,E n ),MVC (V m ?1,E n \N (v m ))+1) 将上述两步组合得到的算法效率为O (k |V |+2k k 2);基于问题核心推演,还可以进一步提高算法效率至O (k |V |+1.32k k 2)乃至更高[26,27].

3 算法生成系统

我们设计了基于问题简约的组合优化算法生成系统,其主要由以下5个部件组成,结构如图1所示.

(1) 算法设计器:系统的核心部件,运用演算规则进行问题简约和算法生成;

(2) 知识库:有关问题基础结构的知识库,包括各种基本数据类型(如集合、序列、树、图等)的代数规约,

其上的典型生成函数(如幂集函数、排列函数、子序列函数、子树/图函数等)及其分解关系等;

(3) 算法模式库:存放典型的问题简约模式及泛型算法;如果新问题的简约模式与库中某个模式同态,那

么可以直接通过泛型实例化来得到其求解算法.表2中列出了系统预定义的主要抽象算法模式;

(4) 定理证明器:如果生成函数或约束函数的分解关系、贪心简约中的单调函数等是由用户自行指定的,

那么定理证明器将对有关结果的正确性进行证明;

(5) 程序生成器:将抽象算法自动转换为可执行语言(如C++,C#,Java 等)的算法程序,并针对特定目标平

台进行代码优化. Algorithm pattern library Algorithm designer

Knowledge base Program generator Theorem prover User interface

Fig.1 Basic structure of combinatorial optimization algorithm generation system

图1 组合优化算法生成系统的基本结构

Table 2 Reduction-Based algorithm patterns and their application problems

表2 简约算法模式及应用问题

Algorithm patterns

Application problems Single singleton greedy reduction

deadlines and penalties for a single processor Multiple singleton greedy reduction

Single machine scheduling, Huffman coding tree, single-source shortest path, shuttle transportation Sequencial reduction

decomposition Binary reduction

maximum-flow/minimum-cut General reduction Integer knapsack, traveling salesman, set covering, multiple vechile routing

4 结束语

算法问题是计算机科学中最为核心的问题之一.本文提出了一种基于代数规约的组合优化算法推演技术,它通过一组算法演算规则对问题进行简约,并基于简约关系构造正确高效的问题求解算法.该方法综合了动态规划、贪心、分支限界多种传统算法设计策略,并在传统方法与近似算法、参数化算法等NP 难题的有效处理方法之间建立了联系,更加有利于人们对算法本质特征的理解.实验系统证明,该方法能够有效支持大量算法程序的自动生成,后续研究的重点将放在对并行算法自动生成的支持上.我们相信,随着最关键的算法设计形式化和自动化程度的不断提高,整个软件工程自动化的研究将有望取得新进展.

1992 Journal of Software软件学报 V ol.22, No.9, September 2011

References:

[1] Xue JY. A unified approach for developing efficient algorithmic programs. Journal of Computer Science & Technology, 1997,12(4):

103?118.

[2] Helman P. An algebra for search problems and their solutions. In: Kanal L, Kumar V, eds. Proc. of the Search in Artificial

Intelligence. Berlin: Springer-Verlag, 1988. 28?90.

[3] Helman P. A common schema for dynamic programming and branch and bound algorithms. Journal of the ACM, 1989,36(1):

97?128. [doi: 10.1145/58562.59304]

[4] Luan SM, Li W, Ma SH. Algorithm framework: An operational approach to algorithm relocation. Journal of Software, 1999,10(7):

679?684 (in Chinese with English abstract). https://www.wendangku.net/doc/5e13221755.html,/1000-9825/10/679.htm

[5] Kumar V. A unified approach to problem solving search procedures [Ph.D. Thesis]. Department of Computer Science, University

of Maryland, 1982.

[6] Kumar V, Kanal LN. A general branch and bound formulation for understanding and synthesizing and/or tree search. Artificial

Intelligence, 1983,21(1-2):179?198. [doi: 10.1016/S0004-3702(83)80009-5]

[7] Kumar V. A general heuristic bottom-up procedure for searching and/or graphs. Information Science, 1991,56(1-3):39?57.

[8] Bird RS. An introduction to the theory of lists. NATO ASI Series F, 1987,36:5?42.

[9] Meertens L. Algorithmics towards programming as a mathematical activity. In: Bakker JW, Vliet JC, eds. Proc. of the CWI Symp.

on Mathematics and Computer Science. 1986. 289?334.

[10] Backhouse RC. An exploration of the bird-meertens formalism. Technical Report, CS 8810, Department of Computing Science,

Groningen University, 1988.

[11] Burstall RM, Darlington J. A transformation system for developing recursive programs. Journal of the ACM, 1977,24(1):44?67.

[doi: 10.1145/321992.321996]

[12] Bibel W, Hornig KM. LOPS—A system based on a strategical approach to program synthesis. In: Biermann AW, Guiho G,

Kodratoff Y, eds. Proc. of the Automatic Program Construction Techniques. New York: MacMillan, 1984. 69?89.

[13] Neugebauer G, Fronh?fer, B, Kreitz C. XPRTS—An implementation tool for program synthesis. In: Metzing D, ed. Proc. of the

13th German Workshop on Artificial Intelligence, Vol.216. Informatik-Fachberichte, 1989. 348?357.

[14] Xu JF, Dai M, Lü J. Algorithm design automation system NDADAS. Journal of Computer Research and Development,

1990,27(2):1?5 (in Chinese with English abstract).

[15] Lü J. Framework of algorithm correctness in NDADAS. Science in China, Series F, 1991,34(7):875?884.

[16] Zhang JZ, Fei ZM. Automatic generation of software based on scheme. Journal of Computer Research and Development,

1992,29(6):1?6 (in Chinese with English abstract).

[17] Smith DR. KIDS: A knowledge-based software development system. In: Lowry M, McCartney R, eds. Proc. of the Automating

Software Design. Cambridge: The MIT Press, 1991. 483?514.

[18] Smith DR. Designware: Software development by refinement, high integrity software. IEEE Computer, 2001,20(4):10?19.

[19] Xue JY. PAR method and its supporting platform. In: Proc. of the 1st Asian Working Conf. on Verified Software (AWCVS 2006).

2006. 29?31.

[20] Zheng YJ, Xue JY. A problem reduction based approach to discrete optimization algorithm design. Computing, 2010,88(1-2):

31?54. [doi: 10.1007/s00607-010-0085-0]

[21] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithm. 2nd ed., New York: McGraw-Hill, 2001. 339?341.

[22] Bird RS, de Moor O. From dynamic programming to greedy algorithms. In: Proc. of the IFIP TC2/WG 2.1 State-of-the-Art Report

on Formal Program Development. LNCS 755, 1993. 43?61.

[23] Edmonds J. Matroids and the greedy algorithm. Mathematical Programming, 1971,1(1):171?236. [doi: 10.1007/BF01584082]

[24] Sahni S. Approximate algorithms for the 0/1 knapsack problem. Journal of the ACM, 1975,22(1):115?124. [doi: 10.1145/321864.

321873]

[25] Downey RG, Fellows MR. Fixed-Parameter tractability and completeness I: Basic theory. SIAM Journal of Computing, 1995,24(4):

873?921. [doi: 10.1137/S0097539792228228]

郑宇军等:组合优化问题简约与算法推演1993

[26] Chen JE, Huang ZX, Kanjd IA, Xia G. Polynomial time approximation schemes and parameterized complexity. Discrete Applied

Mathematics, 2007,15(2):180?193. [doi: 10.1016/j.dam.2006.04.040]

[27] Li SH, Wang JX, Chen JE. Kernelization techniques and its applications to parameterized computation. Journal of Software, 2009,

20(9):2307?2319 (in Chinese with English abstract). https://www.wendangku.net/doc/5e13221755.html,/1000-9825/3593.htm [doi: 10.3724/SP.J.1001.2009.

03593]

附中文参考文献:

[4] 栾尚敏,李未,马绍汉.算法框架:算法重定位的一种可操作的方法.软件学报,1999,10(7):679?684. https://www.wendangku.net/doc/5e13221755.html,/1000-

9825/10/679.htm

[14] 徐家福,戴敏,吕建.算法自动化系统NDADAS.计算机研究与发展,1990,27(2):1?5.

[16] 张家重,费宗铭.基于算法构架的软件自动产生.计算机研究与发展,1992,29(6):1?6.

[27] 李绍华,王建新,陈建二.参数计算中核心化技术及其应用.软件学报,2009,20(9):2307?2319. https://www.wendangku.net/doc/5e13221755.html,/1000-9825/

3593.htm [doi: 10.3724/SP.J.1001.2009.03593]

郑宇军(1979－),男,福建莆田人,博士,高级工程师,主要研究领域为运筹学,自动化软件工程.

凌海风(1975－),女,博士,副教授,主要研究领域为软件工程方法学

.

薛锦云(1947－),男,教授,博士生导师,主

要研究领域为软件形式化和自动化.

混合群智能优化算法研究及应用

混合群智能优化算法研究及应用 优化问题广泛地存在于科学研究和工程实践中。群智能优化算法是优化算法中最新的一个分支,也是最热门的发展方向。群智能优化算法是通过模拟自然界中生物间相互合作、共享信息等群体行为而建立起来的随机搜索算法,相较于经典优化算法具有结构简单、易于实现等优点。不同的群智能优化算法是模拟不同生物行为形成的,所以它们各具特点和适用场景。然而,单一的群智能优化算法均有其局限性,如搜索精度不够高、收敛速度慢、性能受参数影响较大和容易陷入局部最优等。将不同群智能优化算法有机结合,设计混合群智能优化算法是一种提高算法性能的有效方法,具有重要的研究意义。本文的主要研究内容及创新点包括以下几个方面:(1)针对单目标数值优 化问题提出了一种基于跟随蜂搜索的自适应粒子群算法(Follower Bee Search Based Adapitve Particle Swarm Optimization,F-APSO)。首先在经典粒子群算法粒子飞行轨迹分析的基础上提出了一种自适 应的粒子群算法(Adapitve Particle Swarm Optimization,APSO), 提高了算法在求解单峰问题时的性能。然后提出了一种针对自适应粒子群算法的稳定性分析方法,基于该方法对APSO进行了稳定性分析,给出了能够保证算法稳定的参数取值条件。接着通过引入人工蜂群算法中的跟随蜂搜索,提高了算法的开拓性,并将APSO的稳定性条件拓展到了 F-APSO中。仿真实验表明F-APSO在求解单目标数值优化问题时在解的质量和时间消耗上都具有良好表现。将F-APSO用于解决矿山生产排程优化问题,与原有生产方案相比优化后的方案在不同铁

MATLAB实验遗传算法和优化设计

实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）； 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题； 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。微带电极的结构参数如图所示，W 、t 分别是上电极的宽度和厚度，D 是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率1GHz ），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）： 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率， ρ为电阻率。可见电极的结构参数影响着电极损耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个：W 、D 、t ，它们组成决策向量[W, D ,t ] T ，待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述： ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2)

遗传算法与组合优化.

第四章 遗传算法与组合优化 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 问题等有着多方面的重要意义。

遗传算法与优化问题(重要,有代码)

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： 序号遗传学概念遗传算法概念数学概念 1 个体要处理的基本对象、结构也就是可行解 2 群体个体的集合被选定的一组可行解 3 染色体个体的表现形式可行解的编码 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体， 淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解 9 交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组新解 10 交叉概率染色体对应基因段交换的概 率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.90 11 变异染色体水平上基因变化编码的某些元素被改变

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

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

组合最优化简介

weili@https://www.wendangku.net/doc/5e13221755.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 =∈≤∑∑==

基于遗传算法和神经网络算法的吊车结构优化设计与实现

·制造业信息化· 图1吊车结构系统有限元模型 Fig.1The finite element model of a fixed crane Based on Genetic Algorithms and Artificial Neural Network Algorithms to Optimize the Structure Design and Implementation of Crane XUE Jia-Hai ，YU Xiao-Mo ，QING Ai-Ling ，ZHOU Wen-Jing ，YE Jun-Ke （College of Mechanical Engineering,Guangxi University,Nanning Guangxi 530004,China ） Abstract:This paper by using the finite element method,orthogonal test method,BP neural network and genetic algorithm to optimization of crane structure system.At last ，the neural network model will be optimized through the generic algorithm and the optimal parameters of the structure dynamic behavior will be obtained ． Key words ：finite element ；orthogonal experimental method ；BP-neural network ；genetic algorithm 0引言 随着吊车向大型化方向发展，结构在动载荷作用下的振动问题变得日益突出。因此，进行基于动态特性的优化设计，使产品在设计阶段就可以预测其动态特性，可有效减小系统的振动，提高整机工作性能。结构动力学建模方法主要有有限元法、试验模态法、混合建模法及基于人工神经网络的建模方法。基于人工神经网络的动态优化设计建模方法，是利用多层人工神经网络极强的非线性映射功能，来描述和处理动态系统中设计变量及其动态参数之间的关系。人工神经网络模型一旦建立，可取代有限元模型进行结构动态特性重分析，其分 析过程简单而直接，且远比有限元模型计算速度快，尤其适用于工程技术人员使用。由于吊车结构系统的动态特性很难用设计变量显式表达，因此用遗传算法对建立的神经网络模型寻优，计算出可行区域内动态特性最优时的设计变量及目标值。 1吊车结构系统动态特性分析 图1所示为某厂生产的固定式吊车的有限元模型。主要参数为：塔身高48．5m ，起重臂长70m ，最大起重力矩4400kN ·m 。吊车结构的弦杆、腹杆、钢丝绳及集中质量分别以空间梁单元、杆单元、弹簧单元及质量单元模拟。表1所示 为按最大起重力矩工况计算的系统前8阶固有频率。修稿日期：2012－12－21 作者简介：薛加海（1986-），男，云南彝族人，在读硕士研究生。主要研究方向：制造业管理信息化研究；于晓默（1982-），男，蒙古族人，在读博士研究生。主要研究方向：制造业管理信息化研究。 摘要：论文综合利用BP 神经网络、遗传算法有限元法以及正交试验法对吊车结构系统进行优化研究。利 用遗传算法和BP 神经网络建立复杂结构系统动态优化的计算模型，该模型可代替系统原来的有限元模型。首先对吊车起重机结构系统进行模态分析及谐响应动力学分析，找出对结构动态特性影响最大的模态频率，再利用灵敏度分析，确定对动态特性较敏感的设计变量作为神经网络的输入变量，并利用正交试验法确定神经网络训练样本，用有限元模型计算出样本点数据，建立反映结构振动特性的人工神经网络模型，最后利用遗传算法对所建立的神经网络模型寻优，得到使结构动态性能最优的设计参数。 关键词：有限元法；正交试验法；BP 神经网络；遗传算法中图分类号：TP18 文献标识码：A doi:10.3969/j.issn.1002-6673.2013.01.037 文章编号：1002－6673（2013）01－093－03 基于遗传算法和神经网络算法的吊车结构优化设计与实现 薛加海，于晓默，秦爱玲，周文景，叶俊科 （广西大学机械工程学院，广西南宁530004） 机电产品开发与创新 Development ＆Innovation of M achinery ＆E lectrical P roducts Vol．26,No．1Jan ．,2013第26卷第1期2013年1月 93

粒子群算法和蚁群算法的结合及其在组合优化中的应用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问题（Traveling Saleman Problem）是数学领域的一个著名问题，也称作货郎担问题，简单描述为：一个旅行商需要拜访n个城市（1，2，…，n），他必须选择所走的路径，每个城市只能拜访一次，最后回到原来出发的城市，使得所走的路径最短。其最早的描述是1759年欧拉研究的骑士周游问题，对于国际象棋棋盘中的64个方格，走访64个方格一次且最终返回起始点。 用图论解释为有一个图G=（V,E），其中V是顶点集，E是边集，设D=（d ij）是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于城市V={v1，v2，v3，...，vn}的一个访问顺序为T=(t1，t2，t3，…，ti，…，tn)，其中ti∈V(i=1，2，3，…，n)，且记tn+1= t1，则旅行商问题的数学模型为：min L=Σd(t(i),t(i+1)) （i=1，…，n） 旅行商问题是一个典型组合优化的问题，是一个NP难问题，其可能的路径数为（n-1）！，随着城市数目的增加，路径数急剧增加，对与小规模的旅行商问题，可以采取穷举法得到最优路径，但对于大型旅行商问题，则很难采用穷举法进行计算。 在生活中TSP有着广泛的应用，在交通方面，如何规划合理高效的道路交通，以减少拥堵；在物流方面，更好的规划物流，减少运营成本；在互联网中，如何设置节点，更好的让信息流动。许多实际工程问题属于大规模TSP，Korte于1988年提出的VLSI芯片加工问题可以对应于1.2e6的城市TSP，Bland于1989年提出X-ray衍射问题对应于14000城市TSP，Litke于1984年提出电路板设计中钻孔问题对应于17000城市TSP，以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。

遗传算法及其在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年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机

基于BP神经网络和遗传算法的结构优化设计

收稿日期:2002-11-13;修订日期:2003-02-12 作者简介:郭海丁(1958-) 男 山东潍坊人 南京航空航天大学能源与动力学院副教授 博士 主要从事工程结构强度~断裂~疲 劳损伤及结构优化设计方法等研究. 第18卷第2期2003年4月 航空动力学报 Journal of Aerospace Power Vol.18No.2 E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E Apr.2003 文章编号:1000-8055(2003)02-0216-05 基于BP 神经网络和遗传算法 的结构优化设计 郭海丁1 路志峰2 (1.南京航空航天大学能源与动力学院 江苏南京210016; 2.北京运载火箭技术研究院 北京100076) 摘要:现代航空发动机不断追求提高推重比 优化其零部件的结构设计日益重要 传统结构优化方法耗时多且不易掌握 针对这一问题 本文提出了将BP 神经网络和遗传算法相结合用于结构优化设计的方法 并编制了相应的计算程序 实现了一个含9个设计变量的发动机盘模型的结构优化计算 计算证明 与传统结构优化方法相比 此方法计算速度快~精度良好 关 键 词:航空~航天推进系统;结构优化;神经网络;遗传算法;航空发动机 中图分类号:V 231 文献标识码:A Structure Design Optimization Based on BP -Neural Networks and Genetic Algorithms GUO -ai -ding 1 LU Zhi -feng 2 (1.Nanjing University of Aeronautics and Astronautics Nanjing 210016 China ; 2.Beijing institute of Astronautics Beijing 100076 China ) Abstract :Owing to the increasing demand for raising the thrust -weight ratio of modern aero -engine it is very important to optimize the structures of the components .Traditional optimization methods of structure design are time -consuming and hard to be put into practice .So in this paper a new method of structure design optimization is induced to which both BP neural networks and genetic algorithms (in short :BPN -GA )are applied .A program which contains 9variables is designed for the structure optimization of a disk model with the BPN -GA method which proves that it has better calculating rate and precision than those with traditional optimization methods . Key words :aerospace propulsion ;structure optimization ;neural network ; genetic algorithms ;aero -engine 1 引言 在航空~航天等领域 结构优化设计技术正在得到越来越广泛的应用 结构优化设计逐步进入工程实用阶段!1"3# 但从工程应用角度来看 结构优化设计方法的推广仍存不少障碍 主要表现为: (1)优化中靠经验调整的参数较多 掌握困难;(2)优化计算效率较低 应用现有的结构优化算法进

利用遗传算法进行结构优化设计(开题报告)

本科生毕业设计开题报告书 题目利用遗传算法进行结构优 化设计的一些研究学生姓名 专业班级 指导老师 机械工程学院 2011年11月30日

论文题目用遗传算法进行结构优化设计的一些研究 课题目的、意义及相关研究动态： 优化设计是设计概念与方法的一种革命，它用系统的、目的定向的和有良好标准的过程与方法来代替传统的实验纠错的手工方法。优化设计是寻求最好或最合理的设计方案，而优化方法便是达到这一目的的手段。虽然对大多数现实问题而言，最好饿不一定能实现，但它提供了一种指导思想与标准，形成了概念和运作手段，只要一个问题存在有多种可能的解决方案，它就可以利用优化的思想和概念来更好地解决，故优化方法是求解问题和帮助决策的重要手段和工具。 现代工程结构设计中，大量的应用问题要求结构优化能够适用于各种类型的设计变量（尺寸变量、形状变量、拓扑变量、材料种类。结构布局等）、各种类型的约束（强度。刚度、稳定性、频率等）及各种类型的单元（杆、梁、板、壳、膜、二维元及三维实体元等）的组合结构的线性、非线性、静力、动力或控制结构优化等。为了有效地解决复杂工程优化问题，人们一直在不停地探索。多年来，通过对自然界的探索，人们认为自然界生物的某些行为是可以在计算机上模拟的优化过程。人们将这种生物行为的计算机模拟用于工程目的，提出了一些解决复杂工程优化问题的现代优化方法。 一类是用计算机模拟人类智能行为的智能计算方法，包括模拟人类大脑处理模糊信息能力的模糊系统、模拟人类大脑神经元的连接关系的神经网络和模拟生物进化过程中“物竞天择，适者生存”这一自然规律的进化计算三个方面。其中进化计算已经突破了传统优化方法基于数值计算的确定性搜索模式，而是采取非数值计算的概率性随机搜索模式，已经被广泛地应用于各个领域。进化计算又有分别模拟自然界生物进化不同方面的三条研究途径:遗传算法、进化策略和进化规划，其中以遗传算法(GAs)的研究最为深入、持久，应用也最为广泛。另一类是用计算机模仿生物的某种特性的仿生计算方法，如模拟生物免疫系统自我调节功能的人工免疫系统、模拟蚁群搜索食物过程的蚁群算法等。模拟自然界生物进化过程中“优胜劣汰”机制的遗传算法也属于仿生计算方法的范畴。我此次毕设主要研究的就是基于遗传算法的工程结构优化设计。

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

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/5e13221755.html, Journal of Software,2011,22(9):1985?1993 [doi: 10.3724/SP.J.1001.2011.03948] https://www.wendangku.net/doc/5e13221755.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/5e13221755.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/5e13221755.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)。 智能优化算法是一种通用的算法框架，只要根据具体问题特点对这种算法框架结构进行局部修改，就可以直接应用它去解决不同的问题。这类算法本身不局限于某个框架，具有实践的通用性，适应于求解工业实际问题，能较快地处理大规模数据的同时得到令人满意的解。基于智能优化的近似算法，采用不同的搜索策略和优化搜索机制，寻找问题的近似最优解，具有很好的求解优势。虽然基于智能优化的近似算法不能保证求得全局最优解，但因其高效的优化性能、无需问题特殊信息、易于实现且速度较快等优点, 受到诸多领域广泛的关注和应用。基于智能优化的近似算法(超启发式算法)成为求解复杂组合最优化问题主要的有效方法。