【摘要】 本发明公开了一种对计算机组成原理实验箱元器件进行布局的方法，特别涉及在计算机组成原理实验中对计算机组成原理实验箱元器件进行布局的方法。该方法首先为目标值构造目标函数、并引入拉格朗日乘子对目标函数进行松弛、定义了松弛后的目标函数的对偶形式、利用次梯度优化算法来解决松弛后的目标函数的对偶形式的非光滑性、定义了构造目标函数的完全有向图形式，并结合该完全有向图形式设计了方案的构造过程，最终产生了一个对计算机组成原理实验箱元器件进行布局的方案。。数据由整理 【专利类型】发明授权 【申请人】南阳理工学院 【申请人类型】学校 【申请人地址】473000 河南省南阳市长江路80号 【申请人地区】中国 【申请人城市】南阳市 【申请人区县】宛城区 【申请号】CN201210113757.2 【申请日】2012-04-18 【申请年份】2012 【公开公告号】CN102682648B 【公开公告日】2014-01-01 【公开公告年份】2014 【授权公告号】CN102682648B 【授权公告日】2014-01-01 【授权公告年份】2014.0 【IPC分类号】G06F17/50 【发明人】吕聪颖; 赵刚彬; 张凌晓; 吕聪枝; 苗治国 【主权项内容】1.一种对计算机组成原理实验箱元器件进行布局的方法，要将n个元器件布局到实验箱中的n个地点，各个地点之间的距离用距离矩阵表示为D＝(dij)n*n，各个元器件之间的流量用流量矩阵表示为F＝(fij)n*n，其中，D为距离矩阵，F为流量矩阵，i、j和n均为正整数，且i＝1，…，n；j＝1，…，n；其特征在于，包括以下步骤： 1)为目标值构造目标函数，具体如下： 约束条件： 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)松弛为： 令 zij＝dijfp(i)(j)-λi-λj (6) 则松弛后的目标函数为： 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)被定义为： λk+1的计算公式为： λk+1＝max{λk+θkgk，0} 步长θk被定义为： 其中，0＜βk≤2，当ZLRcf(λ)上升时，βk不变，当ZLRcf(λ)在给定的若干步没有变化时，则取其一半；式(11)的思想是用Z*-ZLRcf(λ)来修正变化的速度； 5)得出对计算机组成原理实验箱元器件进行布局的方案。 【当前权利人】南阳理工学院 【当前专利权人地址】河南省南阳市宛城区长江路80号 【专利权人类型】公立 【统一社会信用代码】12411300419037443Q 【家族引证次数】4.0

未经允许不得转载：http://www.zhongzhencnc.com/1791080117.html