| 主权项 |
一种对计算机组成原理实验箱元器件进行布局的方法，要将n个元器件布局到实验箱中的n个地点，各个地点之间的距离用距离矩阵表示为D＝(dij)n*n，各个元器件之间的流量用流量矩阵表示为F＝(fij)n*n，其中，D为距离矩阵，F为流量矩阵，i、j和n均为正整数，且i＝1，…，n；j＝1，…，n；其特征在于，包括以下步骤：1)为目标值构造目标函数，具体如下： <mrow> <msub> <mi>Z</mi> <mi>cf</mi> </msub> <mo>=</mo> <mi>min</mi> <mo>{</mo> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <munderover> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>d</mi> <mi>ij</mi> </msub> <msub> <mi>f</mi> <mrow> <mi>p</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> <mi>p</mi> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </mrow> </msub> <msub> <mi>x</mi> <mrow> <mi>jp</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </msub> <mo>}</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> </mrow>约束条件： <mrow> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>x</mi> <mrow> <mi>jp</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </msub> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mrow> <mo>(</mo> <mi>j</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>n</mi> <mo>)</mo> </mrow> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>2</mn> <mo>)</mo> </mrow> </mrow> <mrow> <munderover> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>x</mi> <mrow> <mi>jp</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </msub> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mrow> <mo>(</mo> <mi>i</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>n</mi> <mo>)</mo> </mrow> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>3</mn> <mo>)</mo> </mrow> </mrow>xjp(i)∈{0，1}，(i＝1，…，n；j＝1，…，n) (4)其中，Zcf为目标值；n为给定的元器件数目和地点数目，且每个元器件的编号∈{1，…，n}，每个地点的编号∈{1，…，n}；目标是找到一个使Zcf最小的排序P＝(p(1)，p(2)，...p(n))，p(j)表示地点j上分配的元器件编号；fp(i)p(i)为元器件p(i)和元器件p(j)之间的流量；dij为地点i和地点j之间的距离；xjp(i)为二进制变量，用来描述元器件p(i)是否被分配在地点j，如果元器件p(i)被分配在地点j，则xjp(i)取值为1，否则为0；换句话说，如果地点j上被分配了元器件p(i)，则xjp(i)取值为1，否则为0；式(2)说明1个地点只能分配1个元器件，如当j＝1时，也即对于地点1有：x1p(1)+x1p(2)+...+x1p(n)＝1；式(3)说明1个元器件只能被分配在1个地点，如当i＝1时，也即对于元器件p(1)有：x1p(1)+x2p(1)+...+xnp(1)＝1；2)采用拉格朗日松弛方法对目标函数进行松弛引入拉格朗日乘子λ＝(λ1，…，λn)且λ≥0，并结合式(2)和(3)，将式(1)松弛为： <mrow> <msub> <mi>Z</mi> <mi>LRcf</mi> </msub> <mrow> <mo>(</mo> <mi>λ</mi> <mo>)</mo> </mrow> <mo>=</mo> <mi>min</mi> <mo>{</mo> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <munderover> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>d</mi> <mi>ij</mi> </msub> <msub> <mi>f</mi> <mrow> <mi>p</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> <mi>p</mi> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </mrow> </msub> <msub> <mi>x</mi> <mrow> <mi>jp</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </msub> <mo>+</mo> <munderover> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>λ</mi> <mi>j</mi> </msub> <mrow> <mo>(</mo> <mn>1</mn> <mo>-</mo> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>x</mi> <mrow> <mi>jp</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </msub> <mo>)</mo> </mrow> <mo>+</mo> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>λ</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mn>1</mn> <mo>-</mo> <munderover> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>x</mi> <mrow> <mi>jp</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </msub> <mo>)</mo> </mrow> <mo>}</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>5</mn> <mo>)</mo> </mrow> </mrow>令zij＝dijfp(i)(j)‑λi‑λj (6)则松弛后的目标函数为： <mrow> <msub> <mi>Z</mi> <mi>LRcf</mi> </msub> <mrow> <mo>(</mo> <mi>λ</mi> <mo>)</mo> </mrow> <mo>=</mo> <mi>min</mi> <mo>{</mo> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <munderover> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>z</mi> <mi>ij</mi> </msub> <msub> <mi>x</mi> <mrow> <mi>jp</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </msub> <mo>+</mo> <mn>2</mn> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>λ</mi> <mi>i</mi> </msub> <mo>}</mo> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>7</mn> <mo>)</mo> </mrow> </mrow>xjp(i)∈{0，1}，(i＝1，…，n；j＝1，…，n) (8)λ＝(λ1，…，λn)且λ≥0 (9)其中，ZLRcf为松弛后的目标函数的目标值；3)定义松弛后的目标函数的对偶形式式(7)是对计算机组成原理实验箱元器件进行布局的原问题的松弛后的描述，而松弛后的目标函数的对偶形式的目标值形成了原问题的所有可行方案对应的目标值的最小下界；松弛后的目标函数的对偶形式被定义为：Z*＝max{ZLRcf(λ)} (10)其中，Z*为对偶形式的最优目标值；4)利用次梯度优化算法来解决松弛后的目标函数的对偶形式的非光滑性由于松弛后的目标函数的对偶形式可能是非光滑的，在此采用次梯度优化算法来解决其非光滑性，具体设计思想为：令λk为第k次迭代所产生的拉格朗日乘子，则在算法的第k+1次迭代过程中，将根据λk计算出λk+1，由此可得函数ZLRcf的一个改进方案的方向，该方向由梯度量g＝(g1，...，gn)来衡量，且梯度元素gi(i＝1，..，n)被定义为： <mrow> <msub> <mi>g</mi> <mi>i</mi> </msub> <mo>=</mo> <mn>2</mn> <mo>-</mo> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>x</mi> <mrow> <mi>jp</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </msub> <mo>-</mo> <munderover> <mi>Σ</mi> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>x</mi> <mrow> <mi>jp</mi> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </msub> <mo>,</mo> <mrow> <mo>(</mo> <mi>i</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>n</mi> <mo>;</mo> <mi>j</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>n</mi> <mo>)</mo> </mrow> </mrow>λk+1的计算公式为：λk+1＝max{λk+θkgk，0}步长θk被定义为： <mrow> <msub> <mi>θ</mi> <mi>k</mi> </msub> <mo>=</mo> <msub> <mi>β</mi> <mi>k</mi> </msub> <mfrac> <mrow> <msup> <mi>Z</mi> <mo>*</mo> </msup> <mo>-</mo> <msub> <mi>Z</mi> <mi>LRcf</mi> </msub> <mrow> <mo>(</mo> <msup> <mi>λ</mi> <mi>k</mi> </msup> <mo>)</mo> </mrow> </mrow> <mrow> <mo>|</mo> <mo>|</mo> <msub> <mi>g</mi> <mi>k</mi> </msub> <mo>|</mo> <mo>|</mo> </mrow> </mfrac> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>11</mn> <mo>)</mo> </mrow> </mrow>其中，0＜βk≤2，当ZLRcf(λ)上升时，βk不变，当ZLRcf(λ)在给定的若干步没有变化时，则取其一半；式(11)的思想是用Z*‑ZLRcf(λ)来修正变化的速度；5)得出对计算机组成原理实验箱元器件进行布局的方案。 |
