粒子群优化算法解决场地资源布局问题-算法原型探讨_dkjkls的博客-程序员ITS203_粒子群算法解决实际问题

技术标签: 算法  布局  优化  粒子群  算例  学习笔记【机器学习重点与实战】  原创技术文档  

版权声明:本文为博主原创文章,未经博主允许不得转载。

  本篇文章的命题来源于博主参加工作后的第一项任务,用智能优化算法解决工程实际中关于某施工场地相关资源布局的问题。由于博主的硕士毕业论文(详见第3章 基于PSO的已知静态路径规划方法)涉及到了粒子群优化算法,有一定经验,固对于本命题欲采用粒子群优化算法进行求解。
  对于本命题而言,与博主的硕士毕业论文中解决的问题有很大差别,可以说是应用在不同的工程领域。当时花了两周的时间讨论并实现算法的原型,通过算法原型求解出的结果验证了粒子群优化算法还是能有效解决该类问题的。本篇博文要分享的就是关于场地资源布局问题,算法原型的设计、结果的分析和验证。博主对于粒子群优化算法的研究还尚浅,也就刚刚好能解决一些问题,完全可以将本篇文章当做粒子群优化算法的一个小算例,如有纰漏恳请各路大仙不吝赐教。

1. 场地资源布局问题描述

  由于现实中的场地资源布局问题涉及到相关的业务流程和专业术语,为了方便描述,将该问题抽象化。如图1所示,场地共分为两大区域:总装区域和装配区域。总装区域中各个矩形块即为该问题中的建造资源,而各个建造资源所组成的多边形即为最终的产品,每个矩形块在总装区域中的位置即为该矩形块在该问题中的目标位置(已知条件)。各个矩形块为了能运输到总装区域进行总装,需要预先在装配区域完成一系列的装配作业,每个矩形块因各自的装配作业不同,在装配区域中装配的周期(已知条件,矩形块中t参数)也不尽相同;每个矩形块在装配区域中的布局(待求解)需要满足的条件包括:矩形块不与其他矩形块相干涉,不与装配区域中障碍物(现实中用来运输相关资源的绿色通道)相干涉,布局不超越装配区域。而矩形块从装配区域运输到总装区域,运输的方向仅能为水平的X方向和垂直的Y方向。
  需要解决的优化问题可描述为:为每个在装配区域装配的矩形块分配有效位置,使各个矩形块从装配区域运输到总装区域的X方向和Y方向的距离总和最小。
  实际问题中,需要考虑的优化目标不仅仅为距离,仍需考虑每个矩形块重量,运输矩形块的X、Y方向权重。而在原型算法中为了能更快速的实现及更直观的对结果进行判断,仅考虑了X、Y方向运输距离。
这里写图片描述
图1 场地资源布局问题示意图

2. 算法原型设计

  对于该场地资源布局问题,每个矩形块均需要求解X、Y方向的布局位置,即每个矩形块包含2个维度,若某批装配包含N个矩形块,则该批的求解维度为2×N。该问题无法通过简单的数值求解进行计算,所以需采用智能优化算法求解该问题,以期得到全局最优解。

2.1 粒子群优化算法描述

  关于粒子群优化算法描述详见第3章 基于PSO的已知静态路径规划方法

2.2 初始化

  对于标准粒子群优化算法,种群的初始化都是随机产生的,以保证初始化种群的分布性,以较大概率覆盖整个布局解空间。然而盲目的随机选择位置会降低求解效率,另一方面,装配区域空间是有限的,当某批装配中矩形块过多、区域利用率较高的情况下,随机分布可能会导致区域中矩形块摆放过于杂乱无章,无法利用的区域过多,后进入的矩形块没有位置摆放。
  所以为减少粒子群算法初始化的随机性和盲目性,引入正态分布赋值,以使各矩形块在装配区域的初始化位置更接近其在总装区域中的位置;说白了就是让1号矩形块在初始化X方向位置时,使其落在总装区域的总装X方向位置概率最大,越向两边概率越小。同时,为了保证初始化种群的分布性,以较大概率覆盖整个布局解空间,仍需保留随机方法生成初始化种群。
  算法原型采用随机初始化和正态分布赋值初始化相结合的策略对种群进行初始化。若某批装配中矩形块过多,即矩形块占装配区域可用面积较大的情况下,随机初始化会导致区域浪费空间较多,进而导致粒子易陷入初始化。正态分布赋值初始化种群占种群比例为:每天矩形块占用面积和/每天装配区域可用面积和。采用该粒子初始化策略,即保证了区域利用率较高情况下的求解效率,同时也保证了初始种群的分布性。

2.3 参数设置

1)惯性权重ω的取值

  算法原型采用线性递减公式取权值,即:
   ω=ωmax(ωmaxωmin)runrunmax ω = ω max − ( ω max − ω min ) ∙ r u n r u n max
  式中, ωmax ω m a x 为最大惯性权重,取1.2; ωmin ω m i n 为最小惯性权重,取0.4;run是当前迭代次数; runmax r u n m a x 为算法迭代的总次数。
  这种迭代方法在初期时局部搜索能力较弱,后期全局搜索能力变弱。

2)学习因子 c1 c 1 c2 c 2 的取值

   c1 c 1 c2 c 2 通常为相等的常数,取值在0~4之间时,可搜索到较优的解。经过多次试验,本文 c1 c 1 c2 c 2 值均取为2.0。

2.4 位置优化算法

  由装配区域与总装区域布局形式可知,较优的布局方案会紧贴距总装区域较近的一边,如图1中装配区域的下边;且朝向矩形块在总装区域中位置紧密靠拢。因此,为将布局结果与区域布局形式相结合,得到更符合实际的最优结果,加入位置优化算法策略(以图1中装配区域为例):
  Y轴坐标临位移动优化算法:将矩形块沿Y轴方向紧贴装配区域下边移动。当然算法原型由于目的在于验证,仅考虑了Y轴方向的优化,后续发现与X方向进行优化(X轴坐标临位移动优化算法、X轴坐标正位搜索移动优化算法,实际算法中用到,算法原型未加入)配合,计算效果更好。

2.5 适应度函数

  装配区域布局优化要求布局方案中所有矩形块移动距离之和最小,适应度函数如下:
   F=ni=1(LXi+LYi) F = ∑ i = 1 n ( L X i + L Y i )

2.6 算法实现过程

  本文提出的针对场地资源布局问题算法原型流程图见图2所示:
这里写图片描述
图2 算法原型流程图

3. 计算结果及探讨

  采用上述描述的算法原型,对模拟数据进行计算。由于算法原型程序未进行优化,后续实践中发现仅对算法进行代码级别的优化,即可实现计算耗时的大幅缩短,因此计算结果中的计算耗时仅代表相对计算耗时值。

3.1 模拟数据计算-5个矩形块

  模拟数据计算-5个矩形块数据及甘特图详见表1。表中时间单位为天,代表在起始和终止时间内矩形块都在装配区域;装配位置即为优化计算结果;计算的原点(X=0,Y=0)为总装区域左下角;通过甘特图可知只需第2天(t=2)的布局图即可反应整个优化计算结果。经过多次计算,可得出最优计算结果唯一,最佳适应度为124,见图3所示。从计算结果可知通过算法原型优化计算出的结果,符合约束条件,且得到了最优解,可以尝试更为复杂的模型进行测试。本次计算的粒子群优化算法参数见图3中所示。

表1 模拟数据计算-5个矩形块数据表及甘特图
这里写图片描述

这里写图片描述
图3 模拟数据计算-5个矩形块计算结果(t=2)

  图4为该次计算出的适应度值随迭代次数变化情况,可知初始化的第一代适应度值为141,初始化没有过于盲目的随机赋值,即引入的正态分布赋值和位置优化算法显现成效。在第25代适应度值达到了130,与最优值的差距在5%以内,可以说收敛速度也较快。
这里写图片描述
图4 模拟数据计算-5个矩形块,计算适应度值随迭代次数变化情况

  表2为使用不同的迭代次数、粒子数参数计算结果的汇总,从平均计算耗时和平均最佳适应度值来看,越大的迭代次数和粒子数,计算结果越优,而计算耗时越长。从相同条件下的计算耗时可知,该算法原型计算并不是很稳定,迭代次数100、粒子数50的计算数据中,甚至计算耗时能相差10倍以上,究其原因是因为初始化的随机性造成的。

表2 模拟数据计算-5个矩形块,计算结果汇总
这里写图片描述

3.2 模拟数据计算-9个矩形块

  模拟数据计算-9个矩形块数据及甘特图详见表3。即在上节中5个矩形块的基础上再新增4个矩形块。通过甘特图可知需展示第2、4、5天的布局图反应整个优化计算结果。经过多次计算,亦得出最优计算结果唯一,最佳适应度为230,见图5所示。从计算结果可知通过算法原型优化计算出的结果,符合约束条件,且得到了最优解。本次计算的粒子群优化算法参数见图5中所示。

表3 模拟数据计算-9个矩形块数据表及甘特图
这里写图片描述

  从图5中可以看到与上节计算结果不同的地方在4和5的位置,再通过图6、7可知,4和5的布局方式是为了在第5天,9号矩形块进入装配区域时能落位到最好的位置,即4和5为9进行了让位。
这里写图片描述
图5 模拟数据计算-9个矩形块计算结果(t=2)

这里写图片描述
图6 模拟数据计算-9个矩形块计算结果(t=4)

这里写图片描述
图7 模拟数据计算-9个矩形块计算结果(t=5)

  然而你可能会质疑4和5的摆放位置,如图8中A即为求出的最优解,B为另外一种方案,看似结果相似;但经分析可知:若采用B方案9号(X方向增加4步),4号(X方向减少8步,Y方向增加6步;共减少2步),固B方案比A方案多耗费2步。
这里写图片描述
图8 9个矩形块方案对比

  表4为使用不同的迭代次数、粒子数参数计算结果的汇总,总结同上节。

表4 模拟数据计算-9个矩形块,计算结果汇总
这里写图片描述

4. 算法优势

  算法原型考虑的问题较简单,涉及因素较少,虽然能求解出简单计算模型的最优解,但未能充分提现出该算法的优势。结合后续的工作提前提出该算法解决该类问题的优势:
  1)矩形块优先占用距离该矩形块在总装区位置最近的区域,靠近总装区域的矩形块排列紧密,场地利用率最高。
  2)考虑全局最优,周转率、优先级较低的矩形块会为周转率、优先级较高的矩形块让位置。
  3)充分有效利用装配区域中距离总装区域位置最近区域,最近区域变化最快,各矩形块尽量向总装位置靠拢,占地面积较大及占用场地周期长的矩形块尽量放置在距总装位置较远区域。

5. 仍需探讨的问题

  通过算法原型的计算结果,可以初步判定该算法还是可以解决场地资源布局问题的,但算法原型设计过程中抽象并省略了很多约束条件及相关业务限制。在真正设计处理工程实际的算法中还有很多需要探讨的问题:
  1) 原型算法中装配区域仅为一个,而实际中可能会存在两个及以上个装配区域,如何协调多个装配区域?
  2) 原型算法初始化是随机的,可能每次计算结果都不一样,如何让每次计算结果相同,以便对结果进行重现?
  3) 若因矩形块位置分布过于随机,且矩形块占装配区域面积较大,而导致后续入场的矩形块没有位置可放无法计算下去时,该如何处理?
  4) 原型算法基于资源为矩形,若资源为不规则多边形如何处理?
  5) 原型算法是基于矩形块周期不会改变的情况下的,但现实中该周期可能会经常改变,如何协调?
  6) 若矩形块周期可前后浮动,如何与位置分布结合,计算出更优的方案?


==============文档信息===============
版权声明:本文为博主原创文章,未经博主允许不得转载
署名(BY) :dkjkls(dkj卡洛斯)
文章出处:http://blog.csdn.net/dkjkls

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/dkjkls/article/details/72825327

智能推荐

微信扫码:关注公众号后网站自动登录的实现原理_公众号:Java后端的博客-程序员ITS203

点击上方Java后端,选择设为星标优质文章,及时送达作者:destiny链接:segmentfault.com/a/1190000022188562序言常见方式平常大家见到过最多的扫...

微信小程序与微信公众号同一用户登录问题_powerfuler的博客-程序员ITS203_公众号小程序openid

微信小程序与微信公众号同一用户登录问题最近在做微信小程序与微信公众号登录合并的接口。整理相关资料以及个人认识的心得写了这篇文章与大家一起分享。首先,简单说下我遇到的问题是我们的程序调用微信小程序得到openid,然后通过openID得到用户的唯一标识,用户得以登录,然而,当我们调用微信公众号也同样的到openid,同一以用户两个不同的openid,不能区分是否为同一用户,然

牛客练习赛52 BGalahad 树状数组_Pikachu_Yj的博客-程序员ITS203

传送门题意: 求一个区间的和,但如果某一个数在这个区间出现了多次,这个数只能被计算一次。官方题解:按右端点从小到大排序。建立树状数组ccc,维护贡献的前缀和。由于权值ai 满足1≤ai≤500000,所以不用离散化,直接维护 last[ a[i] ] 表示元素 a[i] 上一次出现的位置。设当前更新到的位置为t 。如果ai没有出现过,即last[ai]=0,则不产生影响;否...

Qt信号和槽机制_lsfreeing的博客-程序员ITS203

一个小例子一个实际例子带有默认参数的信号和槽信号和槽的进一步使用和第三方库信号槽使用Qt一个小例子一个小的C++类声明如下: class Counter { public: Counter() { m_value = 0; } int value() const { return m_value; } void setValue(int value)

Unity3D 动画回调方法_七大黍的博客-程序员ITS203

欢迎来到unity学习、unity培训、unity企业培训教育专区,这里有很多U3D资源、U3D培训视频、U3D教程、U3D常见问题、U3D项目源码,【狗刨学习网】unity极致学院,致力于打造业内unity3d培训、学习第一品牌。最近发现很多coder.在用Unity开发游戏的时候都需要一个需求就是..动画播到某一帧就要干什么事情.而且希望能得到回调.在unity里面的window菜

MySQL-Connector-ODBC免安装版本的配置和使用_晓琴儿的博客-程序员ITS203_mysql-connector-odbc

0x00 ODBC介绍ODBC(Open Database Connectivity,开发式数据库连接)是微软公司为应用程序访问关系型数据库时提供的一组标准接口规范。ODBC对不同的关系型数据库提供了统一的API,使用该API来访问任何提供了ODBC驱动程序的数据库。0x01 mysql-connector-odbc的下载MySQL官网:下载Connector/ODBC我选用的是免安装版本,安装版本直接下一步安装即可。0x02 mysql-conne...

随便推点

linux部署web App_我有颗小粒的痣的博客-程序员ITS203

服务器阿里云服务器Apache tomcat只能在官网下载tar.gz文件详见:https://blog.csdn.net/jenyzhang/article/details/70159769注意事项:openJDK的安装目录:/usr/lib/jvm/java-8-openjdk-amd64根据

CSP认证 中间数 (C++)_Absorbent的博客-程序员ITS203

问题描述试题编号: 201612-1 试题名称: 中间数 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   在一个整数序列a1,a2, …,an中,如果存在某个数,大于它的整数数量等于小于它的整数数量,则称其为中间数。在一个序列中,可能存在多个下标不相同的中间数,这些中间数的值是相同的。   给定...

Rails3.2使用mongoDB学习笔记之mongoid_hotsunshine的博客-程序员ITS203

前段时间写过一个mongo_mapper的demo程序,在写那个测试程序的时候,看见很多人都说mongoid更好,于是打算用一下试试,写了好久了,最近公司比较忙,没时间整理,现在贴出来。新建项目[code="ruby"]rails new spec_mongoid[/code]一、mongonid 官方首页[url]http://mongoid.org/[/url]...

interface学习_狮子QH的博客-程序员ITS203

interface的应用场景(1)类型转换(2)实现多态1、底层分析golang中的接口分为带方法的接口和空接口。带方法的接口在底层用iface表示,空接口的底层则是eface表示。下面我们透过底层分别看一下这两种类型的接口原理。以下是接口的原型://runtime/runtime2.go//非空接口type iface struct { tab *itab data unsafe.Pointer}type itab struct { inter *int

SHOW PROFILE参数_kf_panda的博客-程序员ITS203

SHOW PROFILE [type [, type] ... ]    [FOR QUERY n]    [LIMIT row_count [OFFSET offset]]type:    ALL - displays all information    BLOCK IO - displays counts for block input and output op

推荐文章

热门文章

相关标签