求解三维装箱问题的混合模拟退火算法的实现 MATLAB

由于要数学建模中需要解决一个三维装箱的问题,我经过搜寻选定了张德富教授等在计算机学报上发表的《求解三维装箱问题的混合模拟退火算法》这篇论文作为解决问题的理论基础。 该论文的摘要如下: 提出了一个高效求解三维装箱问题(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

九月 30, 2021

方便快速地写好.gitignore

如果你建立了一个Git仓库,.gitignore是你需要考虑的一个选项。 如果你想套用模板的话,推荐使用如下仓库地址中提供的模板: 进入仓库地址: https://github.com/github/gitignore 各种模板覆盖比较全,可以根据你的具体需求组合使用。

五月 26, 2021

正确地进行SSH的相关配置文件的权限设置

如果当导入外部的SSH公私密钥之时,可能需要在家目录下新建.ssh文件夹并将公私密钥移动到该文件夹下。但如果没有将权限问题配置正确的话,会导致密钥无法使用的问题。 这里给出一组命令对分别配置文件夹、公私密钥的权限进行设置: % chmod 700 ~/.ssh % chmod 600 ~/.ssh/id\_rsa % chmod 600 ~/.ssh/id\_rsa.pub % chmod 600 ~/.ssh/authroized\_keys

五月 26, 2021

为MacOS的终端加上代理设置

MacOS现在默认采用Zsh,所以在用户家目录下寻找.zshrc配置文件,如果没有则自行创建。 编辑.zshrc文件,在最后加入下列代码 \# set proxy alias proxy='export all\_proxy=socks5://127.0.0.1:1234' alias unproxy='unset all\_proxy' 添加完毕后,保存,在终端输入以下命令 % source ~/.zshrc 完毕。 如果需要使用代理,则预先输入proxy命令。如果需要取消代理,则输入unproxy命令。 或者如果需要默认启用代理的话,在.zshrc配置文件末尾添加 % export https\_proxy=http://127.0.0.1:7890 http\_proxy=http://127.0.0.1:7890 all\_proxy=socks5://127.0.0.1:7890 保存。 % source ~/.zshrc 完毕。

五月 25, 2021

HyperV Ubuntu虚拟机开启增强会话 调整分辨率 启用剪切板

在HyperV下Windows系虚拟机默认就能够开启增强会话。在增强会话下可以方便地和宿主机共享剪切板与文件,并且在增强会话开启时也能够比较方便地调整分辨率。而Ubuntu等Linux系统下则默认为基本会话,分辨率的调整需要修改引导文件,而剪切板和宿主机是独立的非常不方便。 进过查找,找到了一种可以在Ubuntu 20.04下开启增强会话的方法,使用后有效,遂在此记录。 首先需要开启增强会话的话必须先在创建虚拟机的时候开启第二代虚拟机选项,在首次启动的时候关闭Secure Boot。记得在安装Ubuntu的时候不要开启自动登录选项。 在终端下输入 % wget https://raw.githubusercontent.com/Hinara/linux-vm-tools/ubuntu20-04/ubuntu/20.04/install.sh % sudo chmod +x install.sh % sudo ./install.sh 在Windows Power Shell运行以下命令,然后重启。 \> Set-VM -VMName <your\_vm\_name> -EnhancedSessionTransportType HvSocket 重启后,就能看到链接虚拟机后会话已经为增强会话模式而后Ubuntu进入的XRDP登录页面,此时正常输入用户名密码即可。

五月 25, 2021

解决oh-my-zsh plugin 'zsh-autosuggestions' not found 与 plugin 'zsh-syntax-highlighting' not found问题

安装zsh插件 zsh-autosuggestions或者zsh-syntax-highlighting的时候,我们一般会遇到oh-my-zsh plugin ‘xxx’ not found的问题。现在,我们分析并解决oh-my-zsh plugin ‘zsh-autosuggestions’ not found 与 plugin ‘zsh-syntax-highlighting’ not found问题。 问题产生的原因是,没有把插件的代码仓库克隆到本地位置上,所以你想要的插件其实并没有被安装。 解决问题非常简单,只需要简单输入以下命令: $ git clone https://github.com/zsh-users/zsh-autosuggestions ~/.oh-my-zsh/custom/plugins/zsh-autosuggestions $ git clone https://github.com/zsh-users/zsh-syntax-highlighting.git ~/.oh-my-zsh/custom/plugins/zsh-syntax-highlighting $ source ~/.zshrc 然后,你可以重新打开shell,可以发现问题已解决。你也可以用该方法解决其他插件的此类问题。

五月 25, 2021

Synology Drive版本控制功能使用心得

经过一段时间对于Synology Drive的版本控制功能的使用,总结出以下不建议使用版本控制的常见使用场景: Synology Drive版本控制不适用于对音乐库与视频库的版本控制。这两种场景适合使用回收站机制来管理。因为音乐和视频库的容量变动幅度较大,在一段时间内进行大量的删除或者格式转换操作后,磁盘可用空间将迅速下降。不建议将音乐库与视频库加入到版本控制。 版本控制不适用于对于应用程序相关数据文件(例如Docker容器的映射目录下的相关文件)的备份,经过长期观察,版本控制对文件修改并不敏感。我往往发现经常变动的应用程序数据文件一直维持在较老的版本,并没有在应用程序对该文件作出修改后立即备份上一版本。建议使用Cloud Sync或者Hyper Backup对应用程序数据文件进行备份。 上述问题经过长期使用总结出,如果发现其他问题则会更新此文章。

五月 19, 2021

通过Gparted Live ISO可引导镜像调整硬盘分区大小

介绍 手上有一张安装了Openwrt的8G的TF卡,根分区的容量已经不太能够满足我的使用需求了。所以开始着手扩大根分区的大小。根分区的所使用的的文件系统格式是Ext4。首先,尝试使用DiskGenius等Windows下的工具进行扩容,很遗憾都不可以。于是准备使用Gparted进行扩容。由于该工具需要在Linux环境下运行,我不太想安装为此安装一个Linux发行版虚拟机所以使用Gparted的轻量ISO镜像配合Virtual Box虚拟机进行使用。 准备工作 首先下载安装VritualBox虚拟机和 VM VirtualBox Extension Pack。VirtualBox并默认不支持USB外设操作,所以要安装而外后者来为VirtualBox添加USB2.0、USB3.0等外设支持。 VirtualBox下载地址 VM VirtualBox Extension Pack 以上两者下载完后,先安装VirtualBox。 然后安装VM VirtualBox Extension Pack,具体在首选项界面扩展栏目中安装。 下载 GParted Live CD/USB/HD/PXE Bootable Image,下载链接。 步骤 创建虚拟机,分配单核、内存512MB即可,可以不创建虚拟硬盘。 在虚拟机设置界面中,在USB设备栏目中启用USB控制器,根据需要选择USB2.0或者USB3.0。 在储存栏目光驱下,选择下载好的ISO镜像,启动虚拟机。 在第一个引导菜单中选择第一项。 而后,按步骤一次选择或者输入Dont touch keymap, 26(简体中文),0(启动X Window系统)。 然后就能够进入图形界面了,点击桌面上的Gparted工具镜像分区操作。 分区后,记得点击应用。

二月 9, 2021

YouCompleteMe C/C++ VIM CMake 工程 代码提示不可用问题

YouCompleteMe介绍 如果安装完YouCompleteMe并配置好后(本站有过程记录,点击这里查看),就可以使用单文件来检测代码提示效果了。但是,当S&E打开他的C/C++工程时,却发现代码提示、跳转等功能不能正常使用。在查阅文档后,S&E发现原来是YouCompleteMe相关的索引数据库没有建立,相关的编译选项并不正确,所以YouCompleteMe所使用的的clangd就不能将多个源文件联系起来。 建立 C/C++ VIM 代码提示索引的方法 如果是使用CMake建立工程,则可以在CMakeList.txt中加入 set( CMAKE\_EXPORT\_COMPILE\_COMMANDS ON ) 或者在命令行cmake后加上-DCMAKE_EXPORT_COMPILE_COMMANDS=ON也行 建立索引的原理 YouCompleteMe读取由构建系统CMake生成的编译数据库(通常名字叫做compile_commands.json),这样就可以完成对于工程文件的索引。而编译数据库包含项目中每个编译单元的编译器调用。YouCompleteMe会寻找打开文件所在目录中的compile_commands.json,如果没找到会递归地向上查找这个文件。如果在它找到.ycm_extra_conf.py之前,找到了compile_commands.json,那么它就会停止搜索,然后,让clangd处理接管并处理该文件中含有的标志。 在完成上述这些操作后,YouCompleteMe的相关功能就可以正常使用了。

二月 6, 2021

Vim 代码提示插件 YouCompleteMe 安装与配置

介绍 对于在Vim下的C/C++程序编写,如果有代码提示插件会大大提高编写效率。大型IDE用的多了,刚回归Vim的S&E比较依赖这个。正好YouCompleteMe能够满足他的相关需求。索性把安装与配置的过程记录在这里,以供下次回忆使用。 除了C/C++,YouCompleteMe支持Java、Go、C#、Objective-C、CUDA等,可以说是比较强大了。但是话说,写Java为什么要用Vim呢?IDEA貌似更好。 使用后发现这插件还支持代码跳转、引用查找、修改函数名和格式调整等操作,挺方便。 Giuhub仓库地址:https://github.com/ycm-core/YouCompleteMe 前置条件 安装最新的YouCompleteMe插件需要满足一些条件 Vim 8.1 以上 并且启用了Python3扩展支持(本站有过程记录,点击这里查看) GCC 8 以上 或者 Clang 7 以上 Python3.6以上编译的时候有–enable-shared选项(一般包管理器安装都带有) 对于Debian 10, 通过包管理器安装的Gcc版本为8.3.0。 然后可以通过以下命令查看编译器版本 % cc -v 对于python3的版本,使用以下命令查看 % python3 --version 对于Vim版本,使用执行以下命令查看 % vim --version 检查完以上依赖后,也执行一下以下命令确认安装相关依赖 % sudo apt install build-essential cmake vim-nox python3-dev 安装 先确认用过了Vim插件管理器安装了YouCompleteMe,推荐使用Vundle。 确认安装了YouCompleteMe后,进行下面的步骤 如果你想要安装所有的功能,包括Java(JDK 8),Go、C#等代码提示功能,可以直接执行以下命令安装 % cd ~/.vim/bundle/YouCompleteMe % python3 install.py --clangd-completer 如果你只想使用C/C++代码提示功能,则执行以下命令 % cd ~/.vim/bundle/YouCompleteMe % python3 install.py --clangd-completer

二月 6, 2021