学术

由于要数学建模中需要解决一个三维装箱的问题，我经过搜寻选定了张德富教授等在计算机学报上发表的《求解三维装箱问题的混合模拟退火算法》这篇论文作为解决问题的理论基础。 该论文的摘要如下： 提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟 退火 算法 .三维装箱问题要求装载给定箱子集合的一个子 集到容器中 , 使得被装载 的箱子总体 积最大 .文中介绍 的 混合 模拟退火算法基于三个重要算法 :(1)复合块生成算法 , 与传统算法 不同的是文中提出的复合块 不只包含单 一 种类的箱子 , 而是可以在一定的限制条件下包含 任意种类的箱子 .(2)基础启发式算法 , 该算法 基于块装 载 , 可以 按 照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础, 将装载序列作为可行 放置 方案的编码 , 在编码空间中采用模拟退火算法进行搜 索以寻找问题的近似最 优解 .文 中采用 1 50 0 个弱异构 和 强异构的装箱问题数据对算法进行测试 .实验结 果表明 , 混合模拟退火算法的填充率超过了目前已知的 优秀算法 . DOI 号 :10.3724/ SP .J.1016 .2009.02147 本文算法实现其计算结果 该实现的核心函数MATLAB代码 function \[solution, newPlan, rate\] = container\_packeting(bcon, plan, blockTable, blockNeed) %UNTITLED2 根据大小容器的规格以及小容器的数量信息计算出打包的方案 % bigContainer 大容器的规格向量 \[L W H\] % smallContainers 小容器的规格矩阵\[L W H;\] % smallContainersNumber 小容器的数量向量 \[n\] solution = {}; newPlan = \[\]; searchDeep = 40960; clf; draw\_container(\[0,0,0\], bcon); % 剩余空间栈 lspace\_s = get\_stack(); % 空隙栈 iterval\_s = get\_stack(); itervalSpace\_s = get\_stack(); % 初始化剩余空间为大容器空间 lspace\_s = stack\_push(lspace\_s, get\_space(\[0,0,0\], bcon)); psCount = 0; while lspace\_s.count > 0 psCount = psCount + 1; % 从剩余空间栈中取得可用的剩余空间 lspace = stack\_top(lspace\_s); lspace\_s = stack\_pop(lspace\_s); lspace\_size = lspace.size; lspace\_base = lspace.base\_point; if\_input = 0; \[blockList, blockListNeed\] = get\_block\_list(blockTable, blockNeed, lspace\_size(1), lspace\_size(2), lspace\_size(3)); theBlockNeed = NaN; find\_idx = 1; if size(blockList, 1) == 0 find\_avaliable = 0; else find\_avaliable = 1; if plan(psCount) <= size(blockListNeed, 1) theBlockNeed = blockListNeed(plan(psCount),:); find\_idx = plan(psCount); else theBlockNeed = blockListNeed(size(blockListNeed, 1),:); find\_idx = size(blockListNeed, 1); end newPlan = \[newPlan, find\_idx\]; end %% locate container if find\_avaliable == 1 newLocatedBlock = {lspace\_base, blockList(find\_idx, :), theBlockNeed{1}, theBlockNeed{2}}; solution(size(solution, 1) + 1, :) = newLocatedBlock; spaceInfo = newLocatedBlock{4}; spaceLastInfo = spaceInfo(size(spaceInfo,1), :); locateInfo = newLocatedBlock{2}; hold on; draw\_container(lspace\_base, locateInfo(1:3)); itervalSpace\_s = stack\_push(itervalSpace\_s, (1-spaceLastInfo(1)) \* prod(locateInfo(1:3))); if\_input = 1; % 剩余空间计算 % H方向剩余空间 location = lspace\_base; location(2) = location(2) + locateInfo(2); iterval\_space = get\_space(location, \[locateInfo(1) , lspace\_size(2) - locateInfo(2), locateInfo(3)\]); lspace\_s = stack\_push(lspace\_s, iterval\_space); % L方向剩余空间 location = lspace\_base; location(1) = location(1) + locateInfo(1); left\_space = get\_space(location, \[lspace\_size(1) - locateInfo(1), lspace\_size(2), lspace\_size(3)\]); lspace\_s = stack\_push(lspace\_s, left\_space); % W方向剩余空间 location = lspace\_base; location(3) = location(3) + locateInfo(3); iterval\_space = get\_space(location, \[locateInfo(1) , lspace\_size(2), lspace\_size(3) - locateInfo(3)\]); lspace\_s = stack\_push(lspace\_s, iterval\_space); end if if\_input == 1 else % 压入空隙栈 iterval\_s = stack\_push(iterval\_s, lspace); % lspace\_s = stack\_push(lspace\_s, lspace); end end rate = space\_used\_rate(bcon, solution); end function rate = space\_used\_rate(container, solution) spaceHasTotal = 0.0; for i = 1:1:size(solution, 1) mergeMessage = solution{i, 4}; for k = 1:1:size(mergeMessage,1) spaceHasTotal = spaceHasTotal + prod(mergeMessage(k, 3:5)); end end rate = spaceHasTotal / prod(container); end 箱体产生函数 function \[blockTable, boxNeedTable\] = simple\_block\_generate\_indepent(container, box, num) simBlockCount = 0; simBlockTable = zeros(256, 8); for type = 1:1:size(box, 1) for nx = 1:1:num(type) for ny = 1:1:num(type)/nx for nz = 1:1:num(type)/ny/nx if box(type,3) \* nx < container(3) && box(type, 1) \* ny < container(1) && box(type, 2) \* nz < container(2) newSimBlock = \[box(type, :), nx, ny, nz, type, prod(box(type, :)) \* nx \* ny \* nz\]; simBlockTable(simBlockCount + 1, :) = newSimBlock; simBlockCount = simBlockCount + 1; end end end end end simBlockTable = simBlockTable(1:simBlockCount, :); simBlockTable = sortrows(simBlockTable, 8); simBlockTable = simBlockTable(:, 1:7); % 处理成启发式算法可以处理的格式 simBlockTable(:, 13) = ones(size(simBlockTable, 1), 1); simBlockTable(:, 11) = simBlockTable(:,4) .\* simBlockTable(:,3); simBlockTable(:, 12) = simBlockTable(:,5) .\* simBlockTable(:,1); % ly = ay simBlockTable(:, 8) = simBlockTable(:, 12); % lx = ax simBlockTable(:, 10) = simBlockTable(:, 11); % lz = lz0 \* nz simBlockTable(:, 9) = simBlockTable(:, 2) .\* simBlockTable(:, 6); boxNeedTable = cell(size(simBlockTable, 1), 2); for i = 1:1:size(simBlockTable, 1) boxNeedTable{i, 1} = zeros(1, size(box ,1)); boxNeedTable{i, 1}(simBlockTable(i, 7)) = simBlockTable(i, 4) \* simBlockTable(i, 5) \* simBlockTable(i, 6); boxNeedTable{i, 2} = \[simBlockTable(i, 7), 0, simBlockTable(i, 8:10)\]; end blockTable = simBlockTable(:, 8:13); blockTable(:,7) = blockTable(:, 1) .\* blockTable(:, 2) .\* blockTable(:, 3); \[blockTable, idx\] = sortrows(blockTable, \[ 7 \]); boxNeedTable = boxNeedTable(idx, :); end 箱体组合产生函数 function \[blockTable, boxNeedTable\] = complex\_block\_genrate(container, box, num, level) simBlockTable = simple\_block\_generate(container, box, num); simBlockTable(:, 13) = ones(size(simBlockTable, 1), 1); simBlockTable(:, 11) = simBlockTable(:,4) .\* simBlockTable(:,3); simBlockTable(:, 12) = simBlockTable(:,5) .\* simBlockTable(:,1); spaceUsedRateMin = 0.90; % ly = ay simBlockTable(:, 8) = simBlockTable(:, 12); % lx = ax simBlockTable(:, 10) = simBlockTable(:, 11); % lz = lz0 \* nz simBlockTable(:, 9) = simBlockTable(:, 2) .\* simBlockTable(:, 6); boxNeedTable = cell(size(simBlockTable, 1), 2); for i = 1:1:size(simBlockTable, 1) boxNeedTable{i, 1} = zeros(1, size(box ,1)); boxNeedTable{i, 1}(simBlockTable(i, 7)) = simBlockTable(i, 4) \* simBlockTable(i, 5) \* simBlockTable(i, 6); boxNeedTable{i, 2} = \[simBlockTable(i, 7), 0, simBlockTable(i, 8:10)\]; end blockTable = simBlockTable(:, 8:13); for level = 1:1:level newBlockTable = zeros(128,6); newBlockCount = 1; boxNeedCount = size(boxNeedTable, 1); for a = 1:1:size(blockTable,1) for b = a:1:size(blockTable, 1) if b == a continue; end if blockTable(a, 6) == blockTable(b, 6) % x 方向合并 if blockTable(a, 1) == blockTable(a, 5) && blockTable(a, 3) == blockTable(a, 4) && blockTable(a, 2) == blockTable(b, 2) tempBlockMerged = \[max(blockTable(a,1), blockTable(b,1)), max(blockTable(a,2), blockTable(b, 2)), blockTable(a,3) + blockTable(b,3), blockTable(a,4) + blockTable(b,4), min(blockTable(a,5), blockTable(b,5)), max(blockTable(a, 6), blockTable(b, 6)) + 1\]; rate = space\_used\_rate(tempBlockMerged(1:3), blockTable(a,1:3), blockTable(b,1:3)); if rate > spaceUsedRateMin newBlockTable(newBlockCount, :) = tempBlockMerged; boxNeedCount = boxNeedCount + 1; newBlockCount = newBlockCount + 1; boxNeedTable{boxNeedCount, 1} = boxNeedTable{a,1} + boxNeedTable{b,1}; boxNeedTable{boxNeedCount, 2} = \[boxNeedTable{a, 2}; rate, 1, blockTable(b, 1:3)\]; end end % y 方向合并 if blockTable(a, 5) == blockTable(a, 1) && blockTable(b, 5) == blockTable(b, 1) && blockTable(a, 2) == blockTable(b, 2) tempBlockMerged = \[blockTable(a,1) + blockTable(b,1), max(blockTable(a, 2), blockTable(b, 2)), max(blockTable(a, 3), blockTable(b, 3)), min(blockTable(a, 4), blockTable(b, 4)), blockTable(a, 5) + blockTable(b, 5), max(blockTable(a, 6), blockTable(b, 6)) + 1\]; rate = space\_used\_rate(tempBlockMerged(1:3), blockTable(a,1:3), blockTable(b,1:3)); if rate > spaceUsedRateMin newBlockTable(newBlockCount, :) = tempBlockMerged; newBlockCount = newBlockCount + 1; boxNeedCount = boxNeedCount + 1; boxNeedTable{boxNeedCount, 1} = boxNeedTable{a,1} + boxNeedTable{b,1}; boxNeedTable{boxNeedCount, 2} = \[boxNeedTable{a, 2}; rate, 2, blockTable(b, 1:3)\]; end end % z 方向合并 if blockTable(a,4) >= blockTable(b,3) && blockTable(a, 5) >= blockTable(b, 1) tempBlockMerged = \[max(blockTable(a,1), blockTable(b, 1)), blockTable(a, 2) + blockTable(b, 2), max(blockTable(a, 3), blockTable(b, 3)), blockTable(b, 4), blockTable(b, 5), max(blockTable(a, 6), blockTable(b, 6)) + 1\]; rate = space\_used\_rate(tempBlockMerged(1:3), blockTable(a,1:3), blockTable(b,1:3)); if rate > spaceUsedRateMin newBlockTable(newBlockCount, :) = tempBlockMerged; newBlockCount = newBlockCount + 1; boxNeedCount = boxNeedCount + 1; boxNeedTable{boxNeedCount, 1} = boxNeedTable{a,1} + boxNeedTable{b,1}; boxNeedTable{boxNeedCount, 2} = \[boxNeedTable{a, 2}; rate, 3, blockTable(b, 1:3)\]; end end end end end blockTable = cat(1, blockTable, newBlockTable(1:newBlockCount-1, :)); % 消除等价复杂块 blockTableTemp = blockTable(:, 1:5); \[~, ia\] = unique(blockTableTemp, 'stable', 'rows'); blockTable = blockTable(ia, :); boxNeedTable = boxNeedTable(ia, :); end blockTable(:,7) = blockTable(:, 1) .\* blockTable(:, 2) .\* blockTable(:, 3); \[blockTable, idx\] = sortrows(blockTable, \[ 7 \]); boxNeedTable = boxNeedTable(idx, :); end function \[rate\] = space\_used\_rate(container, box1, box2) rate = (prod(box1) + prod(box2)) /prod(container); end Main函数 ts = 1; tf = 0.005; dt = 0.98; length = 50; maxSeq = 64; maxChoice = 1024; click = 1; tempRate = \[\]; tempRateX = \[\]; numList = \[64,64,64,64,64,64,64,128,128,128\]; container = StandardISOContainer; % \[blockTable, blockNeed\] = complex\_block\_genrate(StandardISOContainer, Packets, numList, 1); ps = ones(1, maxSeq); ps(1) = 1; \[solution, plan, rate\] = container\_packeting(container, ps, blockTable, blockNeed); best = plan; best\_rate = rate; best\_solution = solution; t = ts; while t > tf for i = 1:1:length k = randi(size(ps)); nps = ps; nps(k) = randi(maxChoice); \[solution, nplan, nrate\] = container\_packeting(container, nps, blockTable, blockNeed); % disp(\['TempPlan: ', mat2str(nplan)\]); % fprintf("TempRate: %f\\n",nrate); click = click + 1; if nrate > rate ps = nps; plan = nplan; rate = nrate; tempRateX = \[tempRateX, click\]; tempRate = \[tempRate, nrate\]; elseif rand(0, 1) > exp((nrate - rate) \* 10 / t) ps = nps; plan = nplan; rate = nrate; end if nrate > best\_rate best = nplan; best\_rate = nrate; best\_solution = solution; disp(\['BestPlan: ', mat2str(best)\]); fprintf("BestRate: %f\\n",best\_rate); end end t = (1 - t \* dt) \* t; end disp(\['BestPlan: ', mat2str(best)\]); fprintf("BestRate: %f\\n",best\_rate); figure(1) draw\_solution(container, best\_solution); figure(2) plot(tempRateX, tempRate); save Solution best\_solution best\_rate tempRateX tempRate

最近，我阅读了一篇名为 TransRepair: Automatic Testing and Improvement of Machine Translation 的研究论文。该论文介绍了一种名为TransRepair的方法，用于在软件测试领域下自动测试机器翻译模型。下面，我将从几个方面对论文的内容进行总结，并讨论其中的关键点。 TransRepair简介 TransRepair是一种用于自动检测和修复机器翻译软件一致性问题的方法。它提供了黑盒和灰盒两种方法来解决机器翻译软件的一致性问题。TransRepair的主要步骤包括生成测试用例、创建测试准则和自动修复过程。该方法提供了清晰、严谨和详细的测试用例生成算法，并采用了四种句子差异的量化方法进行比较。此外，TransRepair还运用了结构一致性原理作为断言，并提供了全面的实验设计和多样化的结果。 关键问题的理解 一致性问题是指机器翻译软件在处理一组具有相似语义和结构但某些特定词语上略有不同的句子时，在对应翻译句集合中的某一句或几句中的某个或几个部分出现的语义、结构不一致的现象。 TransRepair生成测试用例的方法是对输入的原句进行词语替换，形成突变句组。为了实现这一操作，TransRepair使用了词向量模型来计算词语之间的关联性。在选择候选词后，还会将其带入句子中进行成分分析，以确定句子的语义和语法是否发生较大变化。 在验证测试用例输出句子对的一致性时，TransRepair首先使用Widiff进行字符串成分的差异性比较分析。为了增强相似度量化的可靠性，TransRepair还构造了原句和翻译句中涉及的差异成分的部分删除集合，并计算集合中每个元素之间的相似度，选择最大相似值。论文中使用了四种不同的方法来量化相似度，其中部分方法与之前提到的SIT方法有相似之处。 论文中的实验设计具有独特的特点。它首先提出问题并对解决方法进行探讨，然后围绕这四个问题设计实验并提供适当形式的实验数据。实验从多个角度论证了该方法的有效性，包括准确度、有效性、修复能力以及与人工方式的对比等。实验数据的呈现直观易懂。 TransRepair在处理阈值上与SIT方法不同。它通过机器小步遍历运算来获得统计上最优的阈值，并采用人工辅助和统计学分析的方式进行一致性判别，其阈值设定逻辑更具说服力。而SIT方法的阈值设定大多依靠经验，说服力和可操作性较低。 在TransRepair中，自动修复可以分为黑盒和灰盒两种方式。黑盒对应于Google Translate，由于该软件未开源，对于输入输出的相关参数了解有限，因此只能对输入和输出本身进行操作。灰盒对应于Transformer，它的源码和训练集可获取，因此可以对其输出结果的可能性进行把握，并在训练集和模型结构上进行修复操作。 TransRepair的优势在于对一致性问题的自动检测和修复。该方法具有高准确度、可行性和可复现性，这与其准确的实施方法以及对现有方法缺陷的考虑和补充密切相关。然而，该方法的效率较低，有效性仅限于一致性问题。 总体而言，论文 TransRepair 介绍了TransRepair方法作为一种有效的自动测试和改进机器翻译软件的方法，特别解决了一致性问题。论文详细解释了该方法，并提供了实验证据和比较分析。

我之前阅读了 Structure-Invariant Testing for Machine Translation 这篇论文，它提出了一种关于机器翻译软件系统鲁棒性问题的检测方法。下面我将从几个方面详细介绍我对其中内容的理解。 主要内容 SIT是关于机器翻译软件系统鲁棒性问题的检测方法。这种方法利用了一个蜕变测试中的蜕变关系，即"结构不变性"。通过选择原始句子、生成相似句子、从翻译软件获取结果、进行成分解析并量化句子差异、根据设定的阈值筛选并发现问题，SIT可以高效地检测出机器翻译软件系统的鲁棒性问题。根据实验结果，SIT在19秒内可以处理2k+句子，并且对于Google/Bing Translate的准确度达到了70%。然而，仍有提升的空间，可能是由于阈值选择的原因。 对几个关键问题的理解 为什么机器翻译软件存在鲁棒性问题？ 机器翻译软件系统的核心模块通常采用深度学习方法或技术。深度学习模型中每层的维度较高，导致训练模型在向量空间中对不同标签区域的界定可能模糊不清。当输入值接近边界时，稍微做出微小改变可能导致模型输出剧烈变化。 什么是结构不变性？ 结构不变性是指经过对某种语言的句子进行一些特定且微小的词单位修改后，其语义和语法上的结构在转换为对应翻译后通常保持不变。结构不变性是研究机器翻译软件系统相关问题的经验和统计学意义上的一个切入点。 为什么要引入结构不变性？ 引入结构不变性是为了进行蜕变测试，以探索机器翻译软件系统的鲁棒性问题。引入结构不变性的目的有两个：一是由于自然语言关系和变化复杂多样，难以得到一种通用的测试定理作为基准进行测试，因此通过控制变量，得到类似于经验或统计意义上正确的起点，展开测试研究；二是自然语言相关测试的测试用例难以人工构建，引入结构不变性可以方便地利用现有少量样本生成大量测试用例。 如何利用结构不变性生成语义与语法相似的语句？ 在SIT中，使用了BERT模型来生成语义与语法相似的语句。SIT依赖于BERT的大型语料训练以及遮罩和双向反馈学习等技术，以抑制词语替换后整个句子的语义改变或不符合语法和使用习惯等问题。SIT通过在BERT之后增加一个轻量级的分类器来辅助生成预备替换词语的候选列表。 如何量化句子的差异以判断机器翻译软件系统是否存在鲁棒性问题？ SIT使用了三种方法来量化句子差异：字符串差异分析、成分解析树分析和依存解析树分析。SIT直接对翻译软件的输出结果进行以上三种分析，并对它们的效果进行比较。然而，这三种句子差异分析方法都有一定的局限性，可以在进一步的工作中探索综合使用这三种方法进行判定的方式。 SIT具有哪些优势？有哪些不足？ 在论文中，作者讨论了SIT的优势和不足。总的来说，SIT的优势在于其能够检测多种类型错误（未翻译、过度翻译、错误调整、逻辑不清）。然而，我认为其测试用例的生成方式、错误量化和检测方法相对粗糙，导致实验下准确性并不高。修复和阈值设定需要人工参与，这也是其另一个不足之处。 SIT可以有哪些应用？ SIT主要应用于对运用了AI模型的机器翻译软件系统进行鲁棒性测试。通过SIT的自动检测和人工修复训练样本，机器翻译软件的鲁棒性可以得到提升。 总结 SIT是一种检测机器翻译软件系统鲁棒性问题的方法。通过选择原始句子、生成相似句子、获取翻译结果、进行成分解析和量化句子差异，SIT可以高效地检测机器翻译软件系统的鲁棒性问题。实验结果显示，SIT可以在19秒内处理2k+句子，并且对于Google/Bing Translate的准确度达到了70%。然而，仍有改进的空间，可能是由于阈值选择的原因。SIT利用BERT模型生成语义和语法相似的语句，并使用三种方法来量化句子差异。总体而言，SIT的优势在于能够检测多种类型的错误，但其测试用例生成方式和检测方法仍有改进空间。SIT主要应用于对应用AI模型的机器翻译软件系统进行鲁棒性测试，并通过自动检测和人工修复训练样本来提升鲁棒性。