Simulated Annealing Algorithm and Its Application in Irregular Polygons Packing

Two dimensional irregular polygons packing problem is very difficult to be solved in traditional optimal way.Simulated annealing(SA)algorithm is a stochastic optimization technique that can be used to solve packing problems.The whole process of SA is introduced firstly in this paper. An extended neighborhood searching method in SA is mainly analyzed. A general module of SA algorithm is given and used to lay out the irregular polygons. The judgment of intersection and other constrains of irregular polygons are analyzed. Then an example that was used in the paper of Stefan Jakobs is listed.Results show that this SA algorithm shortens the computation time and improves the solution.

防空作战中多边形责任区预警机空域配置方法

针对防空作战中不规则多边形责任区预警机空域配置问题,基于预警机巡逻航线最短直飞距离和最小转弯直径所形成的实时探测区,通过寻优算法确定预警机责任子区和相应的预警机巡逻可用空域,再基于预警机稳定覆盖度评估准则,对其空域配置进一步寻优,得到预警机空域配置优化方案。通过算例仿真验证了此种方法在不规则多边形责任区中规划预警机空域配置的可行性和提升作战效能的有效性,其方法具有较强的实用价值和军事价值。

基于轨迹线改进的临界多边形算法

在异形件的下料排样问题中,最为困难的就是求解裁片在板料中的位置以保证材料较高的利用率,算法复杂度随着料片数量和料片轮廓复杂度的增加迅速上升。临界多边形算法是计算异形件之间靠接位置和重叠关系的一种基础性几何工具,临界多边形算法的性能与下料排样算法效率密切相关。本文在基于轨迹线的求解临界多边形算法基础上,提出一种求解临界多边形(NFP)的改进算法。该算法有效地将移动碰撞算法和轨迹线算法相结合,充分发挥两类算法各自的优点,提高了临界多边形求解的计算速度。仿真实例验证了改进方法的正确性和有效性。

设计知识驱动的不规则多边形排样算法及应用

为高效解决实际生产制造中的二维不规则多边形排样问题,提出一种设计知识驱动的启发式算法。利用临界多边形判定多边形之间的相对位置,并建立局部适应度数学模型用于衡量多边形的贴合程度;根据设计知识建立数学模型来评价多边形待摆放位置,利用基于局部搜索的贪心算法完成排样。通过对国际通用基准用例进行实验测试并与现有智能优化算法进行对比,证明了所提算法在排样质量与时间性能上不但具有一定优势,而且稳定性高。通过实际生产中样片数据的实验测试证明了所提算法的实用性。

超边界约束条件下异形件排样问题的求解算法研究

针对超边界约束条件,提出了板材动态边界搜索的处理策略,然后以临界多边形(NFP)为基础,同时引入无碰撞区域(CFR)的概念,以保证排样方案的可行性,在综合考虑零件之间的重合率和BL(bottom left)策略,以及CFR可能退化为点或线段的情况之后,提出基于CFR的混合启发式定位算法。在上述零件定位算法的基础上,采用遗传算法对零件排样顺序进行优化以解决超边界约束排样问题,并通过实例验证了所提算法的有效性。

基于改进免疫遗传算法的汽车零件排样

为提高汽车零件排样的板材利用率,对汽车零件的排样技术进行研究.汽车零件大多是不规则零件,因此其排样属于二维不规则排样问题范畴.在智能优化算法求解二维不规则排样领域,遗传算法容易产生早熟现象,并且局部寻优能力较差,而免疫算法具有很强的局部寻优能力.结合遗传算法与免疫算法的全局与局部寻优能力,提出一种改进的免疫遗传算法.该算法的遗传选择操作加入个体浓度计算,操作步骤和变异概率可以自适应调整,从而有效避免早熟现象.自适应计算免疫选择个体数以及免疫克隆个体数以提高算法的收敛性能.分别使用ESICUP网站提供的公开数据和实际汽车零件专用数据对提出的免疫遗传算法的性能进行测试,实验结果表明,和现有的几种算法相比,本研究提出的免疫遗传算法能获得更高的材料利用率.

基于小波时频分析的车轮多边形和轨道不平顺分析研究

车轮多边形和轨道不平顺是当下影响地铁车辆运行品质的最主要原因。轴箱的振动是轮轨耦合振动的最直接反映,车轮多边形引起的周期性激励和轨道不平顺信息可以从轴箱振动信号中分析出来。本文使用西门子SimcenterTestLab振动控制采集分析系统采用小波变换对实测轴箱振动信号进行时频分析,得到车轮多边形引起的振动主频在59.81~88.45Hz的范围内,本方法可快速得到被测车辆车轮多边形情况以及定位轨道不平顺较为严重的区段,为工程师分析车辆异常振动提供依据。使用小波变换对轴箱振动信号进行时频分析的方法相较于传统车轮和轨道测试手段更为方便可靠。

模拟退火法的研究及其在不规则多边形布局中的应用

对模拟退火算法的搜索方法进行分析，给出其一般搜索模型．把该模型应用于不规则多边形的布局，并针对不规则多边形的具体情况，对它的相交判断以及其它约束条件进行了论述，在此基础上应用模拟退火法很好的改善了问题的解．

量子行为粒子群优化算法的布局问题研究

基于多边形扫描转换的启发式底左(HBL)算法,将量子行为的粒子群算法(QPSO)应用于布局问题——二维不规则多边形优化排样,给出了该问题的粒子构造方法及其布局优化过程。通过与模拟退火遗传算法(SAGA)进行布局优化比较,验证了该算法求解布局优化问题的有效性。

带圆弧简单多边形的面积公式获取算法

从房地产管理部门对房屋面积进行精确测量的同时需要获得房屋面积丈量公式,并且在房产证明上要给出面积计算公式的实际需求出发,提出一种基于扫描线方法的带圆弧简单多边形面积算法该算法解决了现有房屋面积计算方法中存在的计算精度不高、难以获得房屋面积丈量公式、计算方法不利于客户理解等问题;同时也解决了现有算法不能方便地对含有圆弧等形状的多边形进行精确的面积计算问题文中算法已成功地应用于浙江省海宁市房产局的智能化房屋面积核算分摊CAD系统。

基于摇瓶策略求解二维不规则件排样问题

针对基于序列的二维排样问题求解策略的不足,提出采用"摇晃瓶子"的策略求解二维不规则件排样问题。基于图像和颜色直方图方法实现零件的重叠检测、出界检测和方案评价。对模拟退火提出两种改进措施:动态邻域尺度方法和并行退火方法。动态邻域尺度方法可使模拟退火用于摇瓶策略,解决了采用离散方法检测零件重叠时精度和时间的矛盾;并行退火方法进一步加快了求解速度。实验对比证明了动态邻域算法和并行退火算法有效,且能满足工程应用要求。分析了动态邻域和并行退火的复杂度,从理论上说明了这两种方法缩短排样时间的原因。

临界多边形生成算法的改进

二维不规则形状零件排样是将给定的若干不规则形状零件合理、较优地排放在给定的材料中,使得材料利用率最大.求解一个多边形相对于另一个多边形的临界多边形,是不规则形状零件自动排样算法中的关键技术,而且需要反复调用.探讨了斜率法求解临界多边形的优点,分析了该方法在任意两个多边形有多边重叠的情形时出现错误的原因,给出了对斜率法的改进方法,通过实例验证,该方法是有效可行的.

二维不规则多边形自动布局系统的研究与设计

布局问题来源于现代生产的许多领域 ,并且表现为多种形式 ,但由于该问题在理论上已属于NP完备问题 ,很难用传统的优化算法求解。讨论了二维不规则多边形自动布局系统的思想和设计技术 ,对模拟退火算法的搜索方法进行了分析 ,给出其一般搜索模型。针对不规则多边形的具体情况 ,对它的相交判断以及其它约束条件进行了论述。

二维Delaunay三角网的任意点删除算法研究

针对目前基于影响域多边形剖分的点删除算法缺陷,提出一种二维Delaunay三角网点删除算法。首先利用具有拓扑关系的三角网搜索影响多边形,并以三角形矢量面积为工具三角剖分影响域多边形,最后通过镶嵌优化后的剖分三角网完成点的删除,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。

不规则多边形的干涉算法

研究了二维两不规则多边形图形之间的干涉计算问题，借鉴有限元法的思想，将不规则多边形视为若干三角形的组合，从而转化为两三角形之间干涉计算问题． 分析了两三角形之间干涉图形的有关性质，给出了两三角形之间干涉量的计算方法，进而给出了两不规则多边形之间干涉量计算的有限三角形单元干涉算法．

工艺约束策略下的二维不规则零件排样算法

针对已有排样算法在实际工业生产情况下缺乏对零件工艺约束等问题,提出一种基于工艺约束策略的二维不规则排样算法(PCTNA)。该算法结合临界多边形算法,通过对零件内含有的空洞进行填充,实现提高被加工板材材料的利用率;再通过引入等距偏移思想,解决实际生产时所需要的零件间的工艺间隙问题。通过对欧洲排样问题兴趣小组提供的测试算例进行实验测试,从12个测试算例的测试结果得到平均时间优化比率为10.33%,平均路径优化比率为11.06%,实验结果显示PCTNA可以降低排样的切割时间和减少路径,提高切割效率。

应用临界多边形方法与小生境遗传算法求解不规则排样问题

针对现代制造业中广泛存在的不规则排样问题进行了研究,提出一种基于临界多边形排样策略和小生境遗传算法的排样优化算法.算法通过改进的移动碰撞法计算零件之间的临界多边形,以确定最佳的零件靠接排放位置;通过基于小生境策略的遗传算法优化零件的排样顺序,确定最佳排样序列.对所提出的排样优化算法作了实验测试和算法评估,验证算法的可行性与有效性.排样实验结果表明,该算法能够用于求解不规则排样问题,且在一定程度上优于已有算法,能够提高材料利用率.

基于梯形分解的不规则多边形干涉算法

研究了二维两不规则多边形之间的干涉量计算问题,将不规则多边形离散为有限个梯形的组合,从而转化为两两梯形对之间干涉量计算问题。分析了两梯形间干涉拓扑图形类型,并按内点个数区间及干涉量多边形顶点性质将其归类,给出两梯形对干涉量计算方法。在此基础上提出用水平梯形剖分不规则多边形的思想,进而得到基于梯形分解的平面多边形干涉算法,并进行该算法复杂度分析。最后,算例表明了本算法的可行性。

轨道交通车辆车轮显著多边形提取方法

设计一种切比雪夫带通滤波器模型,可以便捷地将轨道车辆车轮周向不平顺数据分解为若干阶次的车轮多边形,同时完整地保留其幅值与相位信息。在对模型校核验证后,将其应用于某地铁车轮显著多边形的识别与提取,得到理想的结果。

基于临界多边形的不规则件启发式排样算法

为提高不规则件启发式排样的材料利用率,提出一种基于重心临界多边形和边适应度的不规则件启发式排样算法GEFHNA。首先,定义了边适应度以衡量排样过程中原材料与不规则件间贴合程度,在此基础上给出了将边适应度与重心NFP(GNFP)相结合的排放策略以减少排样过程中可能产生的空隙面积;其次,给出了基于WeilerAtherton多边形裁剪算法的剩余原材料求解方法,重用排样过程中产生的孔洞,减少孔洞面积;最后,给出了基于上述排样策略和材料重用策略的启发式排样算法GEFHNA,给出了与智能算法和同类软件的实验比较。对欧洲排样问题兴趣小组提供的基准测试用例的实验结果表明,GEFHNA的耗时约为基于智能算法的排样方法的千分之一,同时在与两款商业软件Nest Lib和Sigma Nest的11个基准测试的对比中,GEFHNA获得了7/11个相对最优的排样面积利用率。