0-1博弈

0-1博弈（共7篇）

0-1博弈 篇1

1 引言

博弈论文献中常出现囚徒困境、性别战、斗鸡博弈等等经典例子。这些博弈都是最简单最典型的非合作博弈——仅有两个参与人且每个参与人都恰有两个纯策略。若各参与人行动数目都大于1, 则可得一般的双矩阵博弈。若将上述博弈中参与人的数目推广到任意大于1的自然数, 且保持各参与人仍恰有两个纯行动, 则可得实际问题中常见的简单而典型的正规型博弈, 我们称为n人双行动博弈。此类博弈有很多实际背景, 如[1]、[2]中所提出的环境管理科学中的毛利益-环境博弈等。

传统策略博弈不考虑参与人混合策略的不明确性 (称Shannon熵) 和极大熵准则, 致使像夫妻争执和斗鸡博弈等著名博弈所得结论自相矛盾 (见[3]pp.1～2) 。本文将Shannon熵和极大熵准则引进博弈论形成所谓带熵博弈论[3]。[4]首先提出条件博弈及其期望均衡的概念, 文献[5]、[6]将期望均衡进一步引入有限理性博弈中, [7]研究了一些双矩阵理性博弈的期望均衡分析问题, 其例子说明用期望均衡分析所得结果是传统博弈论无法得到, 且更符合实际。

因本文研究各参与人都恰有两个行动的博弈, 可记行动为0和1, 故称其为0-1博弈, 因此可用长度为n的二进制表示博弈的局势。而有关标号可用二进制的十进制数表示。 此外, 因0和1具有良好的对偶性质, 故也导致局势的对偶问题。 因此本文的一个记号系统就是二进制和十进制数系并用其对偶性。首先证明了一个关于0-1博弈严格纯Nash均衡集合的结构定理, 然后转成算法。第二, 基于极大熵准则是全体参与人共同知识的前提假设 (将这个假设加入传统静态博弈系统就称之为理性博弈[3,5,6]) 以及信息熵理论中等概率分布的信息熵最大的原理, 给出计算在数学期望意义下的均衡——期望均衡的计算公式。 接着给出几个计算n人0-1理性博弈严格纯Nash均衡和期望均衡的例子。然后, 基于期望均衡的计算公式, 将n人0-1理性博弈中参与人的效用参数化, 由解不等式组得到在全体参与人对于其他参与人的决策信息一无所知的情况下最可能发生的局势——这就是所谓的期望均衡分析问题, 即将[7]中参与人数目从2推广到n. 最后给出两个3人0-1理性博弈的期望均衡分析的应用例子。

n人0-1博弈不但有广泛的应用, 而且与一般的n人策略博弈严格纯Nash均衡的求解相比较, 两种均衡的求解法均比较简单易行。此外, 当每个参与人关于其他参与人的决策信息一无所知时, 最可能出现的局势是传统博弈论无法得到且更加符合实际的, 故解决了处在博弈论和信息熵理论边缘的一个理论上重要, 具有实际应用前景, 且计算方便的问题。

2 前提假设

全体参与人的共同知识系统包括且仅包括:

①共有n个参与人;

②每个参与人都恰有两个待选行动;

③每个参与人都知道全体参与人所使用的行动时, 他的效用;

④每个参与人都希望在博弈中取得尽可能大的效用;

⑤每个参与人都知道极大熵原理 (PME) [3,4,5,6,7,8]:对于每个参与人, 为了清楚其他参与人的行动选择, 这个参与人的信息量需要达到最大。

3 基本概念

定义1 n-人策略博弈Γ≡[N, (Ai) , (ui) ]称为0-1博弈, 其中N={1, 2, …, n}是参与人集, Ai={0, 1}是参与人i的行动集, 而ui:$A={\displaystyle \prod _{i\in {\rm N}}A}{}_i=\{0,1\}{}^{{\rm N}}\to R$是参与人i的效用函数。 长度为n的二进制数a=an…a1∈{0, 1}N (也记 (an, …, a1) 或 (an…a1) ) 是此博弈的局势。对结盟C={i1, …, ir}⊆N, 记-C代替NC, aC代替 (ai1, …, air) 。

定义2 局势a*=a*n…a*1称严格Nash均衡, 若ui (a*) >ui (a*-i, a*i) , ∀i∈N. 其集记作PNE (Γ) , 故aNC=a-C, a= (a1, …, an) = (aC, a-C) , a{i}=ai, a-{i}=a-i.

定义3[4,5,6] 满足前提假设的博弈称理性博弈, 其在期望意义下的均衡称期望均衡。

定义0和1的对偶分别为1和0, 并记$\overline{0}=1,\overline{1}=0$。

定义4 n人0-1博弈Γ≡[N, (Ai) , (ui) ]称对称的, 若有二元函数S使得Ai={0, 1}, ui (a) =S (ai, s (a) ) , ∀a∈{0, 1}N, $s(a)={\displaystyle \sum _{i=1}^{n}a}{}_i$为a=an…a1中1的个数。

令Bn是长度n的二进制数集, 其中ai=0, 1, i=1, …, n. 如B3={000, 001, 010, 011, 100, 101, 110, 111}。则|Bn|=2n. 记Dn=d (Bn) ={d (b) |b∈Bn}, 其中$d(a)=d(a{}_n\cdots a{}_1)={\displaystyle \sum _{i=1}^{n}a}{}_{i}2{}^{i-1}$是二进制数a= (an…a1) 的十进制数, 如D3=d (B3) ={0, 1, 2, 3, 4, 5, 6, 7}。故Dn=d (Bn) ={0, …, 2n-1}。 记Dbi={d (a) |ai=b}, b=0, 1。如n=3时, D01={d (000) , d (010) , d (100) , d (110) }={0, 2, 4, 6}, D11={d (001) , d (011) , d (101) , d (111) }={1, 3, 5, 7}。以b (d) 记十进制数d的二进制数, 并记b (Dn) ={b (d) |d∈Dn}。定义a=an…ai…a1∈{0, 1}N的i-对偶为$\overline{a(i)}=a{}_n\cdots \overline{a{}_i}\cdots a{}_1\in \{0,1\}{}^{{\rm N}}$, 如$\overline{110101(2)}=110111$。

4 严格纯Nash均衡的

求解框图及其推导

引理$1(1)\overline{\overline{a(i)}}=a‚i=1,\cdots ,n.(2)\overline{a(i)}=b$当且仅当$b(i\overline{)}=a‚i=1,\cdots ,n.$

定理1 令$D(a)=\{\overline{a(i)}|u{}_i(a)>u{}_i(\overline{a(i)}),i\in {\rm N}\}$, 则${\rm P}{\rm N}E=A{\displaystyle \underset{a\in \{0,1\}{}^{{\rm N}}}{\cup }D}(a)$。

证明 设$a{}^{*}\in A{\displaystyle \underset{a\in \{0,1\}{}^{{\rm N}}}{\cup }D}(a),a{}^{*}=\overline{a{}^{(i)}(i)},\forall i\in {\rm N}$, 则a*∉D (a) , ∀a∈A, 特别a*∉D (a (i) ) , ∀i∈N. 因$a{}^{(i)}=\overline{a{}^{*}(i)}=(a{}_{-i}^{*},\overline{a{}_i^{*}})$, 故$u{}_i(a{}_{-i}^{*},\overline{a{}_i^{*}})=u{}_i(a{}^{(i)})\le u{}_i(\overline{a{}^{(i)}(i)})=u{}_i(a{}^{*}),\forall i\in {\rm N}$. 故a*∈PNE. 设$a{}^{*}\in A{\displaystyle \underset{a\in \{0,1\}{}^{{\rm N}}}{\cup }D}(a)。$则有a∈{0, 1}N使a*∈D (a) 。故有i∈N使$a{}^{*}=\overline{a(i)}$满足$u{}_i(a)>u{}_i(\overline{a(i)})$。由引理$1‚a=\overline{a{}^{*}(i)}=a{}_n^{*}\cdots \overline{a{}_i^{*}}\cdots a{}_1^{*}=(a{}_{-i}^{*},\overline{a{}_i^{*}})$。故$u{}_i(a{}_{-i}^{*},\overline{a{}_i^{*}})=u{}_i(a)>u{}_i(a{}^{*})‚\exists i\in {\rm N}$. 因此a*∉PNE.

定理2 (求解严格纯Nash均衡的算法)

① 置Ø⇒D, 0…0⇒a.

② 置1⇒i.

③ 若$u{}_i(a)>u{}_i(\overline{a(i)})$, 则转④; 否则转 (10) 。

$④\overline{a(i)}\Rightarrow a.$

⑤ 若a∈D, 则转⑥; 否则转⑦。

⑥ 若i+1>n, 则转⑦; 否则转 (12) 。

⑦ 若a+1≤1…1, 则转⑧; 否则转 (13) 。

⑧ D∪{a}⇒D.

⑨ a+1⇒a, 转②。

(10) 若$u{}_i(a)<u{}_i(\overline{a(i)})$, 则转 (11) ; 否则转⑥。

(11) a⇒a, 转⑤。

(12) i+1⇒i.

(13) 输出{0, 1}ND, 结束.

5 期望均衡的求解公式及其推导

引理2[9] 一个m维概率向量P= (p1, …, pm) , pi≥0, i=1, …, m;${\displaystyle \sum _{i=1}^{m}p}{}_i=1$的Shannon信息熵达到最大当且仅当pi=1/m, i=1, …, m.

定理3 期望均衡计算法:

① 计算$e{}_i(a{}_i)=2{}^{1-n}{\displaystyle \sum _{a{}_{-i}\in \{0,1\}{}^{{\rm N}i\}}u{}_i(a{}_i,a{}_{-i}),b=0,1‚i=1,\cdots ,n.}}$

② 设ei (a*i) =max{ei (0) , ei (1) }, i=1, 2, …, n, 则 (a*1, …, a*n) 是期望均衡。

证明 由前提假设, 各参与人除N, Ai={0, 1}, ui和MPE外, 其他一无所知。由引理2, 若i用ai, 则他断定 (ai, a-i) 出现的概率是21-n. 故$e{}_i(a{}_i)=2{}^{1-n}{\displaystyle \sum _{a{}_{-i}\in \{0,1\}{}^{{\rm N}i\}}u{}_i(a{}_i,a{}_{-i})}}$。 由共同知识概念, 各参与人必都选使ei (ai) =max{ei (1) , ei (0) }成立的ai.

6 例

例1 求下列三人0-1博弈的全体严格纯Nash均衡和期望均衡。000 (2, 1, 4) ; 001 (3, 2, 1) ; 010 (1, 3, 2) ; 011 (2, 1, 4) ; 100 (3, 4, 1) ; 101 (2, 2, 1) ; 110 (1, 1, 4) ; 111 (3, 2, 1) 。易知e1 (0) =11/4, e1 (1) =7/4, e2 (0) =9/4, e2 (1) =7/4, e3 (0) =2, e3 (1) =9/4, max{e1 (0) , e1 (1) }=e1 (0) , max{e2 (0) , e2 (1) }=e2 (0) , max{e3 (0) , e3 (1) }=e3 (1) 。 唯一期望均衡100。筛法:写出博弈000 (2, 1, 4) ; 001 (3, 2, 1) ; 010 (1, 3, 2) ; 011 (2, 1, 4) ; 100 (3, 4, 1) ; 101 (2, 2, 1) ; 110 (1, 1, 4) ; 111 (3, 2, 1) 。000 (2, 1, 4) 与001 (3, 2, 1) 比较, 因4>1, 故001 (3, 2, 1) 下划线。得000 (2, 1, 4) ;$\underset{¯}{001(3,2,1)}$; 010 (1, 3, 2) ; 011 (2, 1, 4) ; 100 (3, 4, 1) ; 101 (2, 2, 1) ;110 (1, 1, 4) ; 111 (3, 2, 1) 。如此类推, 最后得$\underset{¯}{000(2,1,4)}$;$\underset{¯}{001(3,2,1)}$;$\underset{¯}{010(1,3,2)}$;$\underset{¯}{011(2,1,4)}$; 100 (3, 4, 1) ;$\underset{¯}{101(2,2,1)}$;$\underset{¯}{110(1,1,4)}$;$\underset{¯}{111(3,2,1)}$。唯一纯Nash均衡为100。

例2 (采牡蛎博弈) [10] 三人一起在切萨皮克湾采牡蛎。他们都知道在海湾的东北岸外有一个从无人采过的牡蛎床, 若那些牡蛎在下个月之前没有被采走, 等它们长大成熟后, 能在市场上卖更多的钱。现在三个采牡蛎者都在考虑是去采 (行动0) 还是等一等 (行动1) 。 则博弈表为000 (5, 5, 5) ; 001 (7, 7, 1) ; 010 (7, 1, 7) ; 011 (12, 1, 1) ; 100 (1, 7, 7) ;101 (1, 12, 1) ;110 (1, 1, 12) ;111 (10, 10, 10) 。故ei (0) =31/4, ei (1) =13/4, i=1, 2, 3。即若每人不知其他人信息时, 则都会采集。

例3 (公共物品博弈) [10] 考虑三个参与者的公共物品提供博弈。各参与者可提供或不提供c个单位公共物品。若有k个人提供, 则每个人都得到ka个单位的利益, k=1, 2, 3。设各参与者的纯策略提供和不提供各表为0和1, 则博弈为000 (3a-c, 3a-c, 3a-c) ;001 (2a-c, 2a-c, 2a) ;010 (2a-c, 2a, 2a-c) ;011 (a-c, a, a) ;100 (2a, 2a-c, 2a-c) ;101 (a, a-c, a) ;110 (a, a, a-c) ;111 (0, 0, 0) 。由ei (0) =2a-c, ei (1) =a, i=1, 2, 3, 可得a>c⇔ei (0) >ei (1) , a<c⇔ei (0) <ei (1) , a=c⇔ei (0) =ei (1) , i=1, 2, 3。即若各参与者对其他参与者有关信息一无所知, 则当提供者所得利益大于 (小于或等于) 付出成本时, 各参与者都将提供 (不提供或等概地提供或不提供) 。

例4 三人做同种生意。若一或二人扩大生产, 则可从未扩大生产者手中抢到生意。但若三人都扩大生产, 则又回到原平衡状态。设扩大和不扩大生产各表为0和1, 则博弈000 (0, 0, 0) ; 001 (a, a, -2a) ; 010 (a, -2a, a) ; 011 (2a, -a, -a) ; 100 (-2a, a, a) ; 101 (-a, 2a, -a) ; 110 (-a, -a, 2a) ; 111 (0, 0, 0) 。由ei (0) =a, ei (1) =-a, i=1, 2, 3知, a>0⇔ei (0) >ei (1) , a<0⇔ei (0) <ei (1) , a=0⇔ei (0) =ei (1) , i=1, 2, 3。故若各参与者对其他两者有关信息一无所知, 则当扩大生产盈 (亏或不盈不亏) 时, 则将都扩大 (不扩大或等概扩大和不扩大) 生产。

摘要：为了解决每个参与人恰有两个行动且极大熵准则以及每个参与人都完全不知道其他参与人的行动信息是全体参与人的共同知识的多人策略博弈的可能出现局势, 给出了严格纯Nash均衡和期望均衡的求解法和最可能局势的分析法及其用应例子。以二进制和十进制数为基本工具, 证明了严格纯Nash均衡的一个求解算法, 基于全体参与人上述共同知识系统, 给出了一个明显的期望均衡求解公式。通过设定参与人的效用为未知参数并根据期望均衡求解公式, 由解不等式组的方法提出了期望均衡分析法。研究表明, 此类常用博弈的特殊性致使两种均衡和期望均衡分析计算简洁。实例分析表明, 此法可快速计算出博弈的严格纯Nash均衡和期望均衡, 由期望均衡分析法给出的结论由传统方法无法得到且更加符合实际。

关键词：0-1博弈,理性博弈,严格纯Nash均衡,期望均衡,极大熵原理,期望均衡分析

参考文献

[1]Jiang D Y.Gross interest-environment games ineconomic management science[J].ManagementScience and Engineering (Canada) , 2007, 1 (1) :25~31.

[2]Jiang D Y.Conditions for strictly Nash equilibriaand public!harm degrees in a gross interest-envi-ronment game[C]//International Conference ofProduction and Operation management (CD-ROM) , 2008, part 5 (251) :1~6.

[3]姜殿玉.带熵博弈论及其应用[M].北京:科学出版社, 2008.

[4]Jiang D Y, Zhang S K.Realizablity of expectedequilibria of n-person condition game under strongknowledge system[J].International Journal of In-novative Computing, Information and Control, 2006, 2 (4) :761~770.

[5]Jiang D Y.Static, completely static and rationalgames of complete information and their differentNash equilibria[J].International Journal of Inno-vative Computing, Information and Control, 2008, 4 (3) :649~657.

[6]Jiang D Y.Neumann-Morgenstern stable set of afinite static strategy game[J].Journal of Mathe-matical Control Science and Applications, 2007, 1 (2) :251~260.

[7]姜殿玉等.几个双矩阵经济管理理性博弈的期望均衡分析[J].系统工程, 2008, 16 (1) :106~109.

[8]姜殿玉.连续对策的最大熵策略密度对策解[J].系统科学与数学, 2008, 28 (9) :1158~1172.

[9]Roman S.Coding and information theory[M].NewYork:Spring-Verlag, 1992.

[10]McCain R A.Game theory:a non-technical intro-duction to the analysis of strategy[Z].ThomsonSouth-Western, 2004.

求解0-1背包问题算法综述 篇2

背包问题又称子集合问题, 最早是由Dantzing于20世纪50年代首次提出的, 已成为计算机学科中一个经典的NP问题。0-1背包问题可描述为:给定n个物品和一个背包, 物品的重量为wi, 价值为pi (i=1, 2, ……, n) , 背包能容纳的物品的重量为c, 要从这n个物品中选出若干件放入背包, 使得放入物品的总重量不超过c, 而总价值达到最大, 并找出一种放物品的方案。注意:在本问题中, 所有的重量值均为整数。

0-1背包问题是一个NP难题, 它在很多领域都有广泛的应用。很多实际问题都可转换为0-1背包问题, 例如下料问题、贷款组合优化决策问题等。0-l整数线性规划问题可以归结为0-1背包问题, 而整数线性规划问题都可以转化为0-l整数线性规划问题。所以, 对0-1背包问题求解方法的研究无论是在理论上还是在实践中都具有一定的意义。

1 0-1背包问题的数学模型及其分类

0-1背包问题的数学模型如下:

假设有n个物件, 其重量用wi表示, 价值为pi (i=1, 2, …, n) , 背包的最大容纳重量为c, 当物件i被选入背包时, 定义变量xi=1, 否则xi=0。现在考虑n个物件的选择与否, 则背包内n个物件总重量为, 物件的总价值为, 如何决定变量xi (i=1, 2, …, n) 的值 (即确定一个物件组合) 使背包内物件总价值为最大。其数学模型表示如下:

式中xi取0或1, i=1, 2, …, n, c均为正值。

到目前为止, 求解0-1背包问题的方法很多。精确算法有分支限界法、动态规划法等, 近似算法有贪婪方法、蚁群算法等。一般来说, 精确算法不能在较短时间内求解大规模0-1背包问题, 使其实用性受到限制。而近似算法只能求解问题的近似解, 有时所得的近似解质量很低。本文主要针对常见的求解0/1背包问题的算法设计方法进行阐述。

2 求解0-1背包问题的常用算法

2.1 动态规划法

动态规划法DM (Dynamic Programming, 简称DM) 是美国数学家Bellman R E等人在20世纪50年代初在研究多阶段决策过程的优化问题时提出的, 把多阶段决策过程转化为一系列单阶段决策问题, 逐个求解, 创立了解决这类过程优化问题的新方法———动态规划。动态规划算法是先把问题分成多个子问题 (一般地每个子问题是互相关联和影响的) , 再依次研究逐个问题的决策。决策就是某个阶段的状态确定后, 从该状态演变到下一阶段状态的选择。当全体子问题都解决时, 整体问题也随之解决。用枚举的方法从所有可能的决策序列中去选取最优决策序列可能是较费时的笨拙方法, 但利用最优性原理去找出递推关系, 再找最优决策序列就可能使得枚举数量大大下降, 这就是动态规划方法设计算法的主要思路。

设Fk (y) 为背包只装前k种东西, 总重限制为y的情况下所具有的最大价值, 即:

这两个式子分别为背包问题子问题的目标函数和约束条件, 不难看出是满足优化原则的。使用动态规划法求解, 所得递推公式和边界条件是:

Fk (y) =max (Fk-1 (y) , F (y-wk) +pk) ,

F0 (y) =0, 对一切y, 0≤y≤c,

Fk (y) =0, 对一切y, 0≤k≤n,

F1 (y) =[y/w1]·p1

用动态规划方法求解0-1背包问题的过程如下: (1) 将问题分解为若干个子问题 (一般每个子问题是相互关联和影响的) , 再依次研究逐个问题的决策, 也就是把整个问题的最优解与子问题的局部最优解用递推等式联系起来; (2) 定义边界条件; (3) 把边界条件代入递推公式, 逐步求得最优解。

动态规划算法是一种经典的背包问题求解算法, 其原理简单, 算法思路清晰, 易于实现。动态规划算法虽然高效, 但是对于规模较大的问题它并不是一个理想的算法, 最重要的原因就是它的维数障碍, 即计算和存储量的需要对于状态空间和决策空间的维数的增长呈指数增长关系。这样惊人的增长速度是计算机难以承受的, 这就使得直接的动态规划方法求解规划较大的背包问题发生了困难, 且目前尚没有好的解决办法。

2.2 蚁群算法

蚁群算法由意大利学者Dorigo等人首先提出, 是模仿真实的蚁群行为而提出的一种模拟进化算法。蚂蚁之间是通过一种称为信息素 (Pheromone) 的物质传递信息的, 蚂蚁能够在经过的路径上留下该种物质, 而且能够感知这种物质的存在及其强度, 并以此来指导自己的运动方向。因此, 由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象:某一条路径上走过的蚂蚁越多, 该路径上留下的信息素就越多, 则后来者选择该路径的概率就越大。蚂蚁之间就是通过这种信息素的交流, 搜索到一条从蚁巢到食物源的最短路径。将这一问题的核心运用到背包问题中:在某一物品上聚集的信息素越多, 则该物品被选择的概率就越大。就蚁群算法而言, 当处理的数据比较小时, 其具有很快的收敛速度, 而随着数据规模的增大, 算法的收敛速度明显降低。

假设有m只蚂蚁, n+1个城市, 第o个城市代表背包, 第1~n个城市代表各个物品。把第o个城市看成蚂蚁的寻优起点。令nij=pi/wi表示蚂蚁从城市转移到城市的期望程度, 这样价值越高同时重量越小的物品对蚂蚁的吸引就越大。令τij表示路径中留下的信息素强度。任一只蚂蚁k由城市i转移到城市j的概率可设为:

其中α表示路径上的信息量对蚂蚁选择路径所起的作用大小, β为吸引度的重要性。每只蚂蚁从寻优起点出发只需一步就可到达1~n当中任意一个食物源, 所以上式中有 (i=1, 2, …, n) 。寻优过程由多只蚂蚁进行, 当每只蚂蚁以较大的概率选中食物源j时, 如果有, 则变量xj将加1, 否则给从i到j的路径以罚值, 以使后续的蚂蚁不再选择本路径。当所有节点都受罚以后将结束一次求解过程。然后记录最优解, 更新信息素。更新的公式可为:

Δτij=Q*wj*xj

τij (t+1) = (1-ρ) *τij (t) +Δτij (i=0, j=1, 2, …, n)

上式中ρ为挥发系数, Q为正常数, xj为经过该路径的蚂蚁数量。

用蚁群算法求解0-1背包问题的过程如下: (1) 初始化:即将任意两个城市之间的道路上的信息素赋一个初值; (2) 搜索:让若干只蚂蚁根据信息素和距离选择城市; (3) 每到一个新城市, 进行信息素局部更新; (4) 所有蚂蚁完成回路后, 进行全局信息素更新; (5) 记录最优路径, 返回步骤 (2) 循环直到满足退出条件。

蚁群算法是近年来发展起来的一种随机算法, 已经证明可以有效解决背包问题。但是蚁群算法的收敛性证明尚处于初步阶段, 缺乏完善的理论基础。并且在减少寻优计算量和缩短算法运行时间方面, 有待进一步改进。

2.3 贪婪法

贪婪算法通过一系列的选择得到问题的解, 在每一次总是做出在当前状态下看来是最好的选择, 也就是希望通过局部的最优来达到一个全局的最优。这种启发式的策略并不总能获得最优解, 然而在许多情况下确能达到预期的目的, 而且对于很多N-P问题来说, 本身就不存在最优解。

对于0-1背包问题来说, 贪婪的策略有常用的3种。每种贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。

第一种贪婪准则:从剩余的物品中, 选出可以装入背包的价值最大的物品, 利用这种规则, 价值最大的物品首先被装入 (假设有足够容量) , 然后是下一个价值最大的物品, 如此继续下去。

第二种贪婪准则:从剩下的物品中选择可装入背包的重量最小的物品, 如此继续下去直到不能满足条件为止。

第三种贪婪准则:价值密度 (价值重量比pi/wi) 贪婪算法, 这种选择准则为:从剩余物品中选择可装入包的pi/wi值最大的物品, 这也是本文所选择的贪婪策略, 因为它是一个直觉上近似的解。

用贪婪算法求解0-1背包问题的过程如下: (1) 对于给定的物品, 分别求出价值密度 (价值重量比) , ri=pi/wi, i=1, 2, …, n; (2) 忽略先前的物品排序, 按照价值密度, 进行非升序排列: (p (1) /w (1) ) ≥ (p (2) /w (2) ) ≥…≥ (p (n) /w (n) ) ; (3) 重复以下步骤, 直到不满足条件为止:对于当前的物品, 如果重量小于包中剩余的容量, 则放入, 并置物品标志为1 (表明被选中) , 否则就停止。

算法主要耗时是在于将各种物品按价值密度大小排序, 本文利用MATLAB软件中的SORTROWS函数进行排序, 此函数是基于快速排序 (quicksort) 实现的, 因此, 算法的时间复杂度为O (nlogn) 。

2.4 模拟退火算法

1983年, Kirkpatric等将热力学中的退火思想引入组合优化领域, 提出了一种解大规模组合优化问题, 特别是N-P完全组合优化问题的有效近似算法———模拟退火算法。它源于对固体退火过程的模拟, 使算法在多项式时间内给出一个近似最优解。

模拟退火算法是模仿固体物质的退火过程。高温物质降温时其内能随之下降, 如果降温过程充分缓慢, 则在降温过程中物质体系始终处于平衡状态, 反之降温太快, 则降到同一低温时会保持内能。

用模拟退火算法求解0-1背包问题的过程如下:

(1) 解空间。由于模拟退火算法已经证明, 最后的最优解并不太依赖初始解的选取, 所以在这里可任选一初始解, 本文初始解为 (0, 0, …, 0) 1×n。

(2) 目标函数。最大价值的目标函数为:

(3) 新解的产生。随机选取物品, 若i不在背包中, 则将其直接放入背包中, 或同时从背包中随机取出另一物品j;若i已在背包中, 则将其取出, 并同时随机装入另一物品j。

(4) 背包的价值差和重量差。根据上述新解产生的3种可能, 相应的背包价值差为:

相应的背包重量差为

其中△m为当前状态下背包重量m的增量。

(5) 接受准则。由于0-1背包问题是个有约束的最优化问题, 所以本文采用的是扩充了的Metropolis准则

其中t为温度控制参数。

在算法实现过程中, 其退火温度t控制着求解过程向最小值的优化方向进行, 同时又以概率exp (Δf/t) 来接收劣质解, 因此模拟算法可跳出局部极小值点。只要初始温度足够高, 退火过程足够慢, 算法能收敛到全局最优解。

2.5 其它算法和各种算法的改进

除了以上介绍的算法外, 还有DNA算法、分支限界法、粒子群优化算法、人工神经网络、递归法、回溯法、克隆选择算法、禁忌搜索与GA算法, 混合算法等。

由于各种算法都有其自身的优点和不足, 许多学者通过利用一种算法的优点同时通过结合其它算法避免该算法的不足, 出现了混合算法, 这些算法都取得了很大的成功。

3 结束语

通过计算复杂度的研究表明, 0-1背包问题是一个经典的NP问题。对于规模过大的0-1背包问题, 人们还是无法找到完美的求解方法。所有智能算法都是在一定范围内求解。许多算法有其局限性, 例如只能解决特定的0-1背包问题, 但用于其它0-1背包问题时求解结果不一定好。

0-1背包问题未来的发展趋势: (1) 对现有算法开展理论上的研究, 寻求算法在理论上的解释和证明, 通过加深对算法理论的认识, 从而对算法进行改进和完善, 得到更优解; (2) 继续研究结合多种算法的混合优化算法; (3) 通过其它学科的算法得到启发, 提出新的算法, 继而推动0-1背包问题的研究。

参考文献

[1]赵建英.0/1背包问题的非线性降维近似算法[J].内蒙古师范大学学报 (自然科学汉文版) , 2007 (1) .

[2]王莉, 绍定宏, 陆金桂.基于遗传算法的0/1背包问题求解[J].计算机仿真, 2006 (3) .

基于0-1规划的数学模型设计 篇3

一家会议服务公司负责承办一届全国性会议, 会议筹备组要为与会代表预订宾馆客房.而筹备组已筛选出10家宾馆, 由于宾馆的客房和会议室数量有限, 所以与会代表分散到若干家宾馆住宿.而代表的总人数无法确定, 但可根据附表作为预订宾馆客房的参考.为了便于管理, 除尽量满足代表价位的需求外, 所选择的宾馆数量尽可能少, 并且距离上比较接近.而且预定的客房数量需要适当, 即不能太少也不能太多, 房费由代表自付.若预定客房的数量大于实际用房的数量, 则筹备组须支付一天的空房费.通过建立数学模型分析研究一个从经济、方便、代表满意等方面制定预订宾馆客房的一个合理方案.

二、模型假设

1.假设未发回执而与会的代表人群与发来回执的代表人群对住房要求的比例相同.

2.代表们是否参加会议相对独立.

三、模型的建立与分析

1.测算参会人数

根据附表以往几届会议代表回执和与会情况由统计结果表明:发来回执的代表人数在逐届上升, 而发来回执但未与会的代表人数和未发回执而与会的代表人数也在逐届上升.故考虑统计线性回归模型, 利用一元线性回归方程分别列出发来回执的代表数量与发来回执但未与会的代表数量之间的函数关系, 可测算出参加本次会议的代表总数为638人.并对回归方程作显著性检验, 易得通过检验.

2.建立0-1规划模型计算出预订宾馆数量的最少值

根据题意, 除尽量满足代表在价位等方面的需求之外, 要求宾馆的数量尽可能少, 故设置0-1变量

$h{}_i=\{\begin{array}{l}1\text{预}\text{订}\text{第}i\text{个}\text{宾}\text{馆}‚\\ 0\text{不}\text{预}\text{订}\text{第}i\text{个}\text{宾}\text{馆}‚\end{array}(i=1,2,\cdots ,10)$

.则建立宾馆个数的目标函数:min=${\displaystyle \sum _{i=1}^{10}}$hi, 对于目标函数进行约束:

(1) 宾馆与客房之间的制约关系为:令hi表示是否预订宾馆 (i=1, 2, 3, …, 32) , ai依次表示第i种宾馆客房的间数 (i=1, 2, 3, …, 32) , xi分别表示客房的各个规格房间的间数 (i=1, 2, …, 31, 32) , mi分别表示各个规格房间中独住双人间的间数 (i=1, 2, 3, …, 32) , xi+mi≤aihi.

(2) 参加会议的代表对住房要求的制约:x5+x6+x9+x12+x14+x15+x21+x25≥99等.

(3) 对各宾馆客房数量的制约:xi+mi≤ai.

最后用LINGO软件求解得最少有4个宾馆.最终结论:在满足代表要求的前提下, 宾馆数量为4是最优方案.

3.建立非线性0-1规划模型求解距离最近的4个宾馆

在确定宾馆数量为4的前提下, 分析宾馆数量为4的方案, 发现可选宾馆不唯一.如{①, ②, ⑤, ⑦}或{①, ②, ③, ⑦}, 设Si, j为i宾馆与j宾馆的实际距离.设置距离函数yi, j=Si, j*hi*hj, 其中hi, hj为0-1变量,

$\begin{array}{l}h{}_i=\{\begin{array}{l}1\text{预}\text{订}\text{第}i\text{个}\text{宾}\text{馆}‚\\ 0\text{不}\text{预}\text{订}\text{第}i\text{个}\text{宾}\text{馆}‚\end{array}\\ h{}_j=\{\begin{array}{l}1\text{预}\text{定}\text{第}j\text{个}\text{宾}\text{馆}‚\\ 0\text{不}\text{预}\text{定}\text{第}j\text{个}\text{宾}\text{馆}‚\end{array}(i\ne j).\end{array}$

以4个宾馆间两两的距离和大小, 来作为评价方便性的指标.即求出距离最近的 (最方便) 4个宾馆, 即满足方便性.每两宾馆的间距种类共有C${}_{10}^2$种, 按总路程建立目标函数:min=${\displaystyle \sum _{i,j=1}^{10}}$Si, j*yi, j, (i≠j) , 约束条件如下:

(1) 宾馆与客房之间的制约关系:xi+mi≤aihi.

(2) 参加会议的代表对住房要求的制约:x5+x6+x9+x12+x14+x15+x21+x25≥99等.

(3) 对各宾馆客房数量的制约:xi+mi≤ai.

(4) 宾馆总数为4:h1+h2+h3+h4+h5+h6+h7+h8+h9+h10=4.

运用LINGO软件可得, 所求的距离总和最短的4个宾馆分别是代号为1, 2, 5, 7宾馆.

4.建立整数规划模型求解各宾馆人数

在确定{①, ②, ⑤, ⑦}4个宾馆后, 意味优先考虑代表满意和方便性.另一方面, 考虑经济方面, 如果预订客房的数量大于实际用房数量, 筹备组需要支付一天的空房费, 而空房费与预订房间的总费用成正比, 故可以以预订房间的总费用为目标函数, 求出价格最优的安排方案, 并得到此方案每宾馆的预订人数.假设:

hi:分别表示是否预订宾馆①～⑩ (i=1, 2, 3, …, 10, hi为0-1变量) .

xi:依次表示客房的各个规格房间的间数 (i=1, 2, …, 32) .

mi:依次表示各个规格房间中用于独住的双人间的预订间数 (i=1, 2, …, 32) .

建立目标函数:

min=180* (x1+m1) +220* (x2+m2) +180*x3+220*x4+140* (x5+m5) +160* (x6+m6) +180* (x7+m7) +200* (x8+m8) +140* (x14+m14) +160* (x15+m15) +200* (x16+m16) +150* (x21+m21) +160*x22+300*x23.约束条件如下:

(1) 宾馆与客房之间的制约关系:xi+mi≤aihi.

(2) 参加会议的代表对住房要求的制约:x5+x6+x9+x12+x14+x15+x21+x25≥99等.

(3) 对各宾馆客房数量的制约:xi+mi≤ai.

(4) 是否预订宾馆 (1) ～ (10) (hi为0-1变量) , 运用LINGO软件即可得出最终结论.

四、总结

目前, 筹备工作已经成为会议能否成功举办的关键因素.本文利用0-1规划对会议筹备中需要预订宾馆客房进行详细分析, 并利用统计回归, 数学规划模型, 借助于计算机软件求解得到符合经济、方便、代表满意三个方面的最优模型.

参考文献

[1]杨启帆.数学建模[M].北京:高等教育出版社, 2005.

0-1博弈 篇4

1 一般资料

0-1周岁分为新生儿期、婴儿期。新生儿期指自娩出子宫腔后脐带结扎时起至出生后28天内;婴儿期又称乳儿期, 指出生后第28天至满1周岁, 江西省永新县某医院2012年1月至2012年6月共收足月妊娠产妇800例, 其中600例城镇居民, 把600例列入母乳喂养、生长发育、智力开发、预防接种、疾病筛查为指导对象, 并留有地址、联系方式, 以便随访。

2 方法

2.1 母乳喂养

产后半小时内让婴儿吸吮妈妈乳房, 剖宫产等麻醉清醒后半小时内吸吮乳房, 教给妈妈正确哺乳姿势, 含接姿势, 指导哺乳, 每2-3h一次, 每天至少吸吮8-10次, 按需哺乳。吸空一侧后再吸另一侧, 以防乳汁瘀积, 如果遇到乳房胀痛, 则需要行湿热敷。同时对于婴儿含接和乳房护理问题应注意乳房卫生, 以防乳头皲裂, 防止乳腺炎的发生。

母乳目前来讲是一种非常适宜婴儿消化功能、易消化吸收、且不易发生过敏、上火的婴儿食物, 婴儿可从母乳中获得抵抗疾病的抗体Ig G ( (英文全称为immunoglobulin G) , Ig G是一组具有特殊的化学结构和免疫功能的球蛋白, 存在于体液内和淋巴细胞表面, 是抗体的物质基础, 它对防止新生儿出生数周内的感染起很大作用。, 所以我们一定要坚持母乳喂养。对于婴儿来说, 纯母乳喂养至4-6个月需开始添加辅食, 辅食添加的原则是从稀到稠, 从流汁-半流质-固体, 从一种到多种, 当婴儿习惯一种食物后再添加另一种, 如6-7个月的婴儿可以添加乳类、粥、奶糕、蛋黄泥、菜泥、水果泥等;7-9个月婴儿可以添加乳类、米粉、烂面条、菜泥、肝泥、肉末、豆付、水果片、饼干、鱼泥、馒头等;10-12个月可以添加全蛋软饭、面条、馒头、碎菜、小块肉类、豆制品、饺子、水果, 以保证婴儿多方面的营养来源和营养需求, 以此促进婴儿的生长发育。

2.2 生长发育、智力开发

婴儿大脑发育尚未完善, 临床上我们鼓励和建议家长不要定时地对婴儿把屎把尿, 过多地干预对婴儿是对婴儿发育过程中的不良剌激, 在干预婴儿的过程中可能会影响到婴儿的膀胱功能及过多增加其腹压。临床经验表明4个月以下的婴儿颖让其多看、多听、多抚摸、多活动;4-6个月让孩子抓和玩一些颜色鲜艳的东西, 如塑料球、积木、训练翻身;6-12个月给孩子一些干净的塑料瓶盆、擀面杖等去抓, 敲、扔、训练爬行、捏小物品、训练手指的灵活性, 在此过程中, 一定要注意婴儿的安全, 在孩子不会说话的时候用清晰正确的语言与孩子交流引导发音。同时, 要注意婴儿的健康体检时间, 婴儿健康体检于3个月、6个月、9个月、1周岁各一次, 在此期间应尽量做到一次不差, 以在不同的阶段跟踪婴儿的发育状况, 如有异常, 能够做到及时采取措施, 防范于未然。

2.3 预防接种、疾病筛查

预防接种:卡介苗BCG vaccine (预防结核病、初出生初种、7岁-12岁各加强一次、第一次接种后3个月OT试验阴性者补种) ;乙肝疫苗hepatitis B vaccine (预防乙型肝炎, 初出生、1、6月各接种一次, 3岁加强一次) ;小儿麻痹糖丸疫苗 (预防小儿麻痹症, 2、4个月服三价混合疫苗各一次、4岁加强一次) ;百白破三联疫苗 (预防白喉、百日咳、破伤风, 3、4、5月各接种一次, 1岁半至2岁加强一次, 7岁白破疫苗加强一次) ;麻疹疫苗Measles Vaccine (预防麻疹、8个月初种、7岁加强一次) 。

疾病筛查:新生儿先天性甲状腺功能减低症、先天性甲状腺功能减低症、苯丙酮尿症等新生儿遗传性疾病和听力障碍, 苯丙酮尿症可造成严重的小儿体格生长迟缓、智能发育落后, 如能得到及时诊断和治疗大多数体格发育和智能发育能够达到正常水平。检查方法:宝宝出生72小时至1周内采血筛查先天性甲状腺功能减低症、苯丙酮尿症;宝宝出生后2-5天进行听力障碍的筛查, 能及时发现经过干预后, 使患儿聋而不哑。

3 结果

江西省永新县某医院发现一例先天性甲状腺功能减低症患儿, 经及时治疗, 现小儿15个月。健康检查:体格发育、智能发育正常;同时前文提到的江西省永新某医院600例孩子母乳喂养时间至12个月, 其好处是增加母婴感情, 有利于母亲健康, 延长生育间期, 经济卫生方便, 599名婴儿均为健康儿, 健康率达99.83%。S

摘要：小儿期的喂养关系到婴儿从出生开始的发育关键期, 具有十分重要的意义, 文章对小儿期的喂养的方法, 母乳喂养、护理进行了介绍, 并对小儿期的生长发育、疫苗接种、疾病筛查等进行了详细阐述, 同时结合临床实际进行了分析并提出处理建议。

关键词：小儿期,母乳喂养,预防接种,辅食添加,疾病筛查

参考文献

[1]乐杰.妇产科学[M].6版.北京人民卫生出版社.

[2]王慕逖.儿科学[M].5版.北京人民卫生出版社.

基于0-1规划的农网规划新方法 篇5

网架规划是电网规划的重点, 科学、合理的网架一方面保证供电需求得到满足, 另一方面做到资源索取最少 (如线路走廊、导线材料、运行损耗等) 。当前, 农村电网的规划多由专职人员按照规划导则及一定经验编制完成, 这种方法的明显不足是缺少数学模型的支撑, 随意性大, 对生产实际的指导意义不大。为了保证规划的辅助决策作用, 必须以计算机软件为工具, 采用数学方法对电网进行优化。

1 数学规划方法的分类

从原理上讲, 数学方法的规划主要分启发式和数学优化两个大类[1]。

1.1 启发式方法

通常是定义一个反映运行性能或投资需求的综合指标, 然后基于该指标对可行路径上的一些参数作灵敏度分析, 再结合一定原则选择要架设的线路;或校核每一种网络结构对该指标的满足程度, 当不能满足指标时, 根据一定原则修改网络结构, 再重新校核, 如此反复迭代, 直到得到满足指标的网络结构为止。启发式方法简单、直观、计算量小, 但不是严格的优化方法, 一般给出次优解而非最优解。

1.2 数学优化方法

就是将输电网络规划的问题归结为运筹学中的优化模型, 然后采用一定的算法求解, 获得满足约束条件的最优规划方案。数学优化的主要方法有:线性规划、非线性规划、整数规划、混合整数规划和动态规划等。

考虑到网架规划就是在变电站布点确定后, 基于一定约束条件, 决策出应新建 (或改造) 哪些线路的问题, 显然这一过程的决策变量全为0-1变量, 因此笔者尝试用0-1整数规划方法来求解农网网架。

2 关于LINGO软件

目前, 0-1规划的求解方法主要有隐枚举法和分枝定界法两种。可以预见, 将0-1规划应用到农网中, 将会出现大量可能组合 (尤其变电站点数较多的情况下) , 为了避免计算“维数灾”的出现, 选择LIN-GO软件进行模型求解。

LINGO软件特点[2]: (1) 具有数学模型语言, 使模型容易维护和扩展。 (2) 求解后能产生解答报告, 对于需作方案灵敏度分析的电网规划来说非常有利。 (3) 拥有数据功能, 允许将模型的数据和相应的公式分离, 使调试模型变得容易。 (4) 拥有处理0-1变量的功能, 且对变量维数没有限制。

综上, 选用LINGO软件符合规划要求。

3 农网规划的原则

农村电网规划的基本原则是要满足运行的可靠性、近远景发展的契合性以及供电的经济性等要求。针对当前农村的实际状况, 制定出以下规划原则:

3.1 可靠性

(1) 一般情况下, 110k V、35k V网络应满足“N-1”要求;经济欠发达或用电量较小的区域可建成放射式, 但应考虑扩建成环式电网的可能性。 (2) 采用放射式接线时, 每条高压配电线路上接入 (T接或π接) 的变电所数目不能超过3个。

3.2 灵活性

(1) 应能适应电力系统的近远景发展, 便于过渡。 (2) 能满足各种运行方式下的潮流变化。

3.3 经济性

规划方案要节约电网建设费和年运行费, 使年计算费用达到最小。

4 基于0-1规划的农网规划建模

4.1 规划水平年线路投资计算

为了方便问题的处理, 本部分建模基于以下几个假设: (1) 专家结合勘测情况给出可能的线路路径集合, 0-1规划模型则从集合中选出最科学的一种组合。 (2) 因本规划针对农网, 因此同一路径一般不超过两回线路。 (3) 如果同一路径有双回线路要新建, 那么线型应一致。 (4) 线路改造方式是换线不换杆。

(1) 新的路径上新增线路的投资等年值计算

一定电压等级线路的投资分两部分:一部分与导线截面有关, 另一部分与导线截面无关[3]。即:

式 (1) 中, S表示导线截面积;L表示线路长度;Z0、Z1为常数。

考虑资金时间价值的投资等年值可表示为:

式 (2) 中, l表示线路的经济使用年限;r0表示电力工业投资回收率。

以新增35k V线路为例 (在新的路径上) , 其投资等年值和可表示为:

式 (3) 中, PF35表示可行的35k V线路路径集合;Z035表示35k V线路投资中与导线截面无关的系数;Z135表示35k V线路投资中与导线截面有关的系数;Li35表示第i条可行的35k V线路路径长度, i∈PF35;S135、S235分别代表《导则》规定的35k V线路所能选的导线截面。

需满足约束:

显然, 在新路径上新建的110k V线路的投资等年值和也可作类似表述。

(2) 原有线路路径的新增投资等年值计算

仍以35k V为例。在规划水平年, 原有35k V线路有三种可能情形:维持原状不变;换线改造;增加回路。分别用三类0-1标志参量来表示:

其中, 如果第m条原有35k V线路的导线截面已经为《导则》规定最大值, 则。

以上三式需满足约束:

根据式 (1) 、 (2) , 可写出原有35k V线路在规划期末的新增投资等年值计算式为:

式 (13) 中, OF35为原有35k V线路集合;为原有第m条35k V线路的长度, ;为原有第m条35k V线路的截面积, 。

显然, 在原有路径上的110k V线路的新增投资等年值和也可作类似表述。

4.2 规划水平年网损和运行费用计算

根据高压输电线路的特点, 采用直流潮流法来计算规划水平年的网损, 如下所示:

式 (14) 中, ρ为线路电阻率;τ为年最大负荷损耗小时数;U为线路额定电压;cosφ为功率因数;S为线路截面积;L为线路长度;P为线路传输功率;α为电价。

根据文献[4], 规划水平年的线路维护费用为:

式 (15) 中, μ为折旧率;I为线路投资。

4.3 总体建模

(1) 目标函数:水平年总费用最小

式 (16) 中, It为所有新建线路的投资等年值之和;Iw为所有新建线路的年电能损耗费;Iy为所有新建线路的年运行维护费;Dt为原有线路由于改造或增加回路而产生的新投资等年值之和;Dw为原有线路的年电能损耗费;Dy为规划期末原有线路的年运行维护费。

(2) 约束

B、B'为正常和“N-1”情况下的节点导纳矩阵虚部;θ、θ'为正常和“N-1”情况下的节点电压相角向量;Pl、Pl'为正常和“N-1”情况下的支路潮流向量;Bl、Bl'为正常和“N-1”情况下的各支路导纳虚部组成的矩阵;Φ、Φ'为正常和“N-1”情况下的支路两端相角差向量;为支路允许通过的最大容量。

5 算例分析

取文献[5]中18节点系统数据进行计算。限于篇幅, 仅将系统初始图展示, 如图一所示, 系统参数等不做列示。

网架计算分两个步骤: (1) 根据各节点发电出力、各节点负荷需求、已有线路等情况, 运用本文所建0-1模型, 在待选线路集合中选出最少线路组合, 以维持正常运行。 (2) 进行“N-1”检验, 得出还需增加的线路集合。最终的网架图如图二所示, 相关费用测算如表一所示。

6 结束语

本文在紧紧抓住电网规划本质的基础上, 建立了适合农网情况的0-1规划模型。该模型将所有可能区分为“0”状态或“1”状态, 并应用LINGO软件进行模型计算。算例表明, 文章建立的模型直观、有效, 值得推广。但本算例计算用时1分40秒, 迭代332857次, 若用于实时计算显得较为缓慢, 因此需要在今后研究中做持续改进。

参考文献

[1]吴思谋, 蔡秀雯, 王海亮.面向供电可靠性的配电网规划方法与实践应用[J].电力系统及其自动化学报, 2014, 26 (06) :70-75.

[2]聂宏展, 郑鹏飞, 李帅, 等.考虑支路负载率均衡性的输电网规划[J].电工电能新技术, 2014, 33 (03) :7-12.

[3]孔祥聪, 周步祥, 汝锐锐, 等.改进GAAA算法在多目标电网规划中的应用[J].电力系统及其自动化学报, 2014, 25 (06) :112-116.

[4]潘智俊, 张焰, 祝达康, 等.计及电网运行非均匀性的多目标输电网规划[J].电力自动化设备, 2014, 34 (05) :53-58.

0-1博弈 篇6

0-1背包问题是一个典型的组合优化难题, 有着广泛的实际应用背景, 许多优化问题都可以通过一系列背包问题子问题来解决。随着问题规模的增长, 求解背包问题的时间复杂性增长非常快, 从计算复杂性理论来看, 背包问题是个NP完全问题, 在最坏的情况下的时间复杂性为O (2n) 。贪婪算法、遗传算法[1]、蚂蚁算法[2,3]等, 是该问题的求解方法所采用的主要启发式算法, 因此设计新的高效算法来求解背包问题具有重要的实际意义。

人工蜂群算法[4]是一种基于群体智能的随机优化算法, 它是Karaboga于2005年提出的。蜜蜂根据各自的分工进行不同的活动, 人工蜂群算法比遗传算法、粒子群算法具有更好的优化性能。实现蜂群信息的共享和交流, 从而找到问题的最优解。由于人工蜂群算法目前未能有效解决离散及组合优化问题, 所以只能用于求解连续空间的优化问题, 这已成为限制其发展的瓶颈问题。

针对0-1背包问题的特点, 对人工蜂群算法的运算规则进行重新定义, 利用启发式信息, 使算法既具有人工蜂群算法的整体优化特性, 同时在算法中加入贪婪算法这个很有效的局部搜索方法, 又加快了算法的收敛速度。

通过对0-1背包问题测试算例的仿真实验和与其它算法的比较, 表明了本文算法在迭代相同次数的情况下更容易找到最优解, 体现了算法的可行性和高效性。为我们将人工蜂群算法应用到离散问题, 特别是组合优化问题具有一定的启发性, 也为进一步深入研究奠定了基础。

1 0-1背包问题的描述

0-1背包问题的一般提法为:已知n个重量和价值分别为wj>0和cj>0 (j=1, 2…n) 的物品, 背包的容量假设为C>0, 如何选择哪些物品装入背包可使在背包的容量限制之内所装物品的价值最大。引入变量xj, 当物品j被选择装入时, xj=1, 否则, xj=0。则该问题的数学模型为:

2 人工蜂群算法

在人工蜂群算法中, 蜂群由采蜜蜂、观察蜂和侦察蜂三个部分组成, 每个蜜源的位置代表优化问题的一个可能解, 蜜源的收益度 (蜜量) 对应于问题的适应度 (函数值) 。首先, 人工蜂群算法随机产生初始种群, 即N个初始解 (N为采蜜蜂的数目也为蜜源数目) 。每个解xi (i=1, 2, …, N) 为一个D维的向量 (D为搜索空间的维数) 。经过初始化, 采蜜蜂、观察蜂和侦察蜂开始进行循环搜索。采蜜蜂记住自己以前的最优解, 在采蜜源附近邻域搜索, 搜索公式为

式中, k∈{1, 2, …, N}和j∈{1, 2, …, D}是随机选择的下标, 并且k≠i, 准是[-1, 1]上均匀分布的随机数。随着迭代次数的增加, (xij-xkj) 之间的距离缩小, 搜索的空间也缩小, 即搜索的步长缩小, 动态的调整步长有助于算法提高精度, 并最终获得最优解。

采蜜蜂采用贪婪准则, 比较记忆中的最优解和邻域搜索解, 当搜索解优于记忆最优解时, 替换记忆解;反之, 保持不变。所有的采蜜蜂完成搜索过程后, 观察蜂据此按与花蜜量相关的概率选择一个蜜源位置, 将蜜源信息通过舞蹈区与观察蜂共享。蜜量大的采蜜蜂吸引观察蜂的概率大于蜜量小的采蜜蜂。检查新位置的花蜜量, 若新位置没有大的改变, 则保持不变。观察蜂像采蜜蜂那样对记忆中的位置做一定的改变, 若新位置优于记忆中的位置, 则用新位置替换原位置。一个观察蜂选择某个蜜源的概率为:

式中fiti为第i个解的适应值。

在人工蜂群算法中, 还有一个重要的控制参数“limit”, 它用来记录某个解被更新的次数。假定某个解连续经过limit次循环之后没有得到改善, 表明这个解陷入局部最优, 那么这个位置就要被放弃, 与这个解相对应的采蜜蜂也转变为侦察蜂。假设被放弃的解是xi, 则侦察蜂通过下列公式替换xi:

3 求解0-1背包问题的人工蜂群算法

目前人工蜂群算法, 对于离散域上组合优化问题难以解决, 它只是应用于连续域上的数值优化问题, 主要是因为计算公式 (3) 是基于实数域上的四则运算, 公式 (3) 对自然数不满足封闭性, 而离散域上组合优化问题的解通常由自然数表示。

由公式 (1) 、 (2) 所示的数学模型可知, 0-1背包问题是带约束的离散优化问题, 为了使人工蜂群算法能处理离散优化问题, 有必要对人工蜂群算法的运算规则 (3) 进行重新定义。我们采用如下运算规则:

即当xij, xkj相等均为0或1时, x′ij也为0或1, 因为xkj是从群体中随机选取出来的, 且它与xij的取值相同, 则令x′ij等于xij正确的概率应该会大一些;当xij, xkj不相等时, x′ij的取值由f (xi) 和f (xk) 的优劣来决定, 以概率使x′ij=xij, 以概率使x′ij=xkj。在新的运算规则下, 当xij为0-1变量时, 新产生的个体x′ij也为0-1变量, 这使得人工蜂群算法可以对0-1背包问题进行求解。

采用人工蜂群算法求解0-1背包问题时在迭代过程中形成的新个体未必满足约束条件, 因此需要对形成的新个体进行调整, 使用启发式修正算子, 用来保证个体满足约束条件, 在这里我们引入了局部搜索机制—贪婪算法, 同时在保证个体满足约束条件的前提下尽量增加其适应值。

若个体不满足约束条件, 按物品j的价值密度ρj=cj/wj, (j=1, 2, …n) , 由小到大的方向将xj=1变为xj=0, 直到将不满足约束条件的个体变成满足约束条件;若个体满足约束条件, 在保证满足约束条件的前提下, 尽量增加其适应值, 这是对个体质量的改良。按ρj由大到小的方向将xj=0变成xj=1。

4 仿真实验

为了说明算法的效果, 采用VC++为本文算法编写了程序。我们选用文献[5]采用的4个算例来进行测试, 并与文献[5]中的基本郭涛算法和改进的郭涛算法进行对比, 其中改进的郭涛算法也采用了本文使用的贪婪算法。每次试验均进行100次。对于算例1和算例2, 基本郭涛算法和改进的郭涛算法的种群大小为50, 最大进化代数为2000;对于算例3和算例4, 基本郭涛算法和改进的郭涛算法的种群大小为50, 最大进化代数为10000;本文算法对4个算例的种群大小均为20, 最大进化代数均为200。本文算法与基本郭涛算法和改进的郭涛算法的试验结果见表1。

在种群数小于基本郭涛算法和改进的郭涛算法的情况下, 从表1的结果中可以看出, 本文提出的算法, 每次都可以找到问题的最优解, 仍取得了比他们好的求解结果, 表明了本文算法对0-1背包问题的求解具有良好的性能。

5 结论

人工蜂群算法对离散及组合优化问题难以优化, 只是擅长连续空间的优化问题, 是一种基于群体智能的演化算法。本文通过重新定义人工蜂群算法的邻域搜索公式, 使其可以求解0-1整数规划问题。通过4个0-1背包问题的仿真实验, 表明所提算法的可行性和有效性。同时, 本文算法简单易行、方便操作, 可以用来求解许多可以转化为0-1背包问题的组合优化问题。

摘要：提出了一种用于求解0-1背包问题的人工蜂群算法, 详细阐述了该算法求解背包问题的具体操作过程。算法主要使用了两个思想策略:启发式贪婪算法和人工蜂群算法。通过对其它文献中仿真实例的计算和结果对比, 表明该算法对求解0-1背包问题的有效性, 这对人工蜂群算法解决其它离散问题会有很大帮助。

关键词：人工蜂群算法,背包问题,群体智能

参考文献

[1]李娟, 方平, 周明.一种求解背包问题的混合遗传算法[J].南昌航空工业学院学报, 1998, 12 (3) :31-35.

[2]秦玲, 白云, 章春芳等.解0-1背包问题的蚁群算法[J].计算机工程, 2006, 32 (6) :212-214.

[3]熊伟清, 魏平.二进制蚁群进化算法[J].自动化学报, 2007, 33 (3) :259-264.

[4]Karaboga.D.An idea based on honey bee swarm fornumerical optimization[R].Technical Report-TR06, Kayseri:ErciyesUniversity, Engineering Faculty, Computer Engineering Department, 2005.

基于0-1背包问题的两种算法 篇7

0-1背包问题是子集选取问题, 最早由Dantzing于20世纪50年代首次提出, 现已成为计算机学科中一个经典的NP完全难题。它在很多领域有广泛的应用, 很多实际问题都可转换为0-1背包问题, 有效解决0-1背包问题具有重要意义。

由于0-1背包的解空间树是一棵子集树, 所要求的解具有最优性质。0-1背包问题满足回溯法和分支限界法的求解条件, 因而本文就采用回溯法和分支限界法来解决0-1背包问题。

1 问题描述

0-1背包问题是计算机算法中的一个NP完全难题。0-1背包问题的一般描述:给定n种不同物品和一个背包。物品i的重量是wi, 其价值为vi, 背包的容量为C。问:应该如何选择装入背包的物品, 使得装入背包中物品的总价值最大?在选择装入背包的物品时, 对每种物品i只有两种选择, 即装入背包或不装入背包不能将物品装入背包多次也不能只装入部分的i。因此, 该问题称为0-1背包问题。

此问题的形式化描述是, 给定C>0, wi>0, vi>0, 1≤i≤n, 要求找出n元0-1向量 (x1, x2, …, xn) , xi∈{0, 1}, 1≤i≤n, 使得≤C, 而且达到最大。因此, 0-1背包问题是一个特殊的整数规划问题。

2 用回溯法解0-1背包问题

2.1 回溯法

回溯法有“通用解题法”之称。用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。回溯法的求解目标是找出解空间树T上满足约束条件的所有解, 按深度优先的策略, 从根结点出发搜索T。算法搜索至T的任一结点时先判断该结点是否包含问题的解如果肯定不包含, 则跳过对以该结点为根的子树的搜索, 逐层向其祖先结点回溯;否则, 进入该子树, 继续按深度优先策略搜索。回溯法求问题的所有解时, 要回溯到根, 且根结点的所有子树都被搜索遍才结束。回溯法求问题的一个解时, 只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法, 它适用于求解组合数较大的问题。

2.2 回溯法的基本思想

构造一些长度为i的部分向量 (x1, x2, …, xn) , 1≤i≤n。以每次改变其中的一个向量成份 (分量) 的方式来测试判定函数 (有时也称之为约束函数) , 一旦发现部分向量 (x1, x2, …, xi) 不可能导出所需要的解时, 就不必再考虑对 (xi+1, xi+2, …, xi+n) 的各种可能的选择。

2.3 回溯法的搜索策略

用回溯法解决0-1背包问题, 可以采用如下的搜索策略:在搜索解空间树时, 只要一个结点的左儿子结点是一个可行结点就搜索其左子树;而对于右子树, 需要用贪心算法构造一个上界函数 (这个函数表明这个结点的子树所能达到的可能的最大容量, 因为只有将0-1背包问题改变为背包问题才可能利用贪心算法, 因此这个上界函数在绝大多数情况下不会是上确界函数) , 只在这个上界函数的值超过当前最优解时才进入搜索。随着搜索进程的推进, 最优解不断得到加强, 对搜索的限制就越来越严格。

2.4 回溯法解0-1背包问题的算法

在0-1背包问题中, 假定n个物体pi, 其重量为wi, 价值为vi, 0≤i≤n-1, 背包的载重量为C。xi表示物体vi被装入背包的情况, xi=0, 1。当xi=0时, 表示物体没被装入背包;xi=1时, 表示物体被装入背包。根据问题要求, 使得而且达到最大。

如果用和分别表示当前正在搜索的部分解中装入背包物体的总重量和总价值;用表示当前正在搜索的部分解可能达到的最大价值的估计值;用表示当前搜索到的所有有效解中的最大价值;用yk和xk分别表示问题的部分解的第k个分量及其复制, 同时k也表示当前对搜索树的搜索深度, 则回溯法解0-1背包问题的步骤如下:

(1) 把物体按价值重量比的非增顺序排序。

(2) 把和初始化为0, 把部分解初始化为空, 搜索树的搜索深度k置为0。

(4) 如果, 转步骤 (5) , 否则转步骤 (8) 。

(5) 从pk开始把物体装入背包, 直到没有物体可装或装不下物体pi为止, 并生成部分解xk, …, xi, k≤i

(6) 如果i≥N, 则得到一个新的有效解, 把所有yi的复制到xi, , 则是目标函数的新上界;令k=n, 转步骤 (3) , 以便回溯搜索其他的可能解。

(7) 否则, 得到一个部分解, 令k=i+1, 舍弃物体pi, 从物体pi+1继续装入, 转步骤 (3) 。

(8) 当i≥0并且yi=0, 执行i=i-1, 直到条件不成立, 即沿右儿子分支结点方向向上回溯, 直到左儿子分支结点。

(9) 如果i<0, 算法结束, 否则, 转步骤 (10) 。

(10) 令yi=0, , k=i+1转步骤 (3) ;从左儿子分支结点转移到相应的右儿子分支结点, 继续搜索其他的部分解或可能解。

3 用分支限界法解0-1背包问题

3.1 分支限界法

分支限界法, 是一种在问题的解空间树T上搜索问题解的算法。

分支限界法的求解目标是找出满足约束条件的一个解, 或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解, 即在某种意义下的最优解。分支限界法以广度优先或以最小耗费优先的方式搜索解空间树T。

3.2 分支限界法的基本思想

分支限界法常以广度优先或以最小耗费 (最大效益) 优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树, 常见的有子集树和排列树。在搜索问题的解空间树时, 每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点, 就一次性产生其所有儿子结点。在这些儿子结点中那些导致不可行解或导致非最优解的儿子结点被舍弃, 其余儿子结点被加入活结点表中。此后, 从活结点表中取下一结点成为当前扩展结点, 并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

3.3 分支限界法的搜索策略

用分支限界法解决0-1背包问题, 可以采用如下的搜索策略:在扩展结点处, 先生成其所有的儿子结点 (分支) , 然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一个扩展结点, 以加速搜索的进程, 在每一个活结点处, 计算一个函数值 (限界) , 并根据这些已计算出的函数值, 从当前活结点表中选择一个最有利的结点作为扩展结点, 使搜索朝着解空间树上有最优解的分支推进, 以便尽快地找出一个最优解。

用分支限界法解决0-1背包问题, 需要用到贪心算法构造的上界函数, 所不同的是, 这个上界函数的作用不在于判断是否进入一个结点的子树继续搜索, 因为在搜索到达叶节点之前, 无法知道已经得到的最优解是什么。因此, 用一个最大堆来实现活结点的优先队列, 上界函数的值将作为优先级, 这样一旦有一个叶结点成为扩展结点, 就表明已经找到了最优解。

3.4 分支限界法解0-1背包问题的算法

假定, n个物体重量分别为w0, w1, …, wn-1, 价值分别为v0, v1, …, vn-1, 背包载重量为C。令每一个结点都包含集合当前S1、S2、S3中的物体, 以及搜索深度k和上界b等数据。用最大堆来存放结点表, 这样, 0-1背包问题的分支限界法的求解过程如下:

(1) 把物体按价值重量比递减顺序排序。

(2) 建立根结点X, 令X.b=0, X.k=0, X.S1=φ, X.S2=φ, X.S3=S。

(3) 若X.k=n, 算法结束, X.S1即为装入背包中的物体, X.b即为装入背包中物体的最大价值;否则, 转步骤 (4) 。

(4) 建立结点Y, 令Y.S1=X.S1∪{X.k}, Y.S2=X.S2, Y.S3=X.S3-{X.K}, Y.K=X.K+1;按式 (1) - (2) 计算Y.b;把结点Y和Y.b插入堆中。

(5) 建立结点Z, 令Z.S1=X.S1, Z.S2=X.S2∪{X.K}, Z.S3=X.S3-{X.k}, Z.k=X.k+1;按式 (1) - (2) 计算Z.b;把结点Z插入堆中。

(6) 取下堆顶元素于结点X, 转步骤 (3) 。

4 回溯法与分支限界法的比较

通过上面介绍可以看出, 用这两种方法处理0-1背包问题都有一定的可行性, 相比之下回溯法的思路容易理解一些, 但是这是一个寻找最优解的问题, 由于采用了优先队列处理, 不同的结点不再像n后问题那样没有相互之间的牵制和联系, 用分支限界法处理效果一样很好。

其实有一些问题无论用回溯法还是分支限界法都可以得到很好的解决, 但是另外一些则不然。表1给出了回溯法和分支限界法的一些区别。

5 结束语

求解0-1背包问题, 除了用回溯法和分支限界法外, 还可以用动态规划法、蚁群算法、DNA算法、粒子群优化算法、人工神经网络、穷举搜索法、递归法、贪婪法、分治法等算法。也就是说, 求解同一个问题, 可以用不同的算法, 选择算法的主要标准是算法的正确性、可靠性、简单性和易理解性, 还要注意算法所需的存储空间和执行速度等。在程序设计中很多情况下都是将几种算法结合起来使用以达到最佳效果。

参考文献

[1]王晓东.算法设计与分析[M].北京:清华大学出版社, 2003.

[2]卢开澄.组合数学—算法与分析[M].北京:清华大学出版社, 1983.

[3]郑宗汉, 郑晓明.算法设计与分析[M].北京:清华大学出版社, 2005.

[4]曹新谱.算法设计与分析[M].长沙:湖南科学出版社, 1983.