The Solution for Irregular Parts Nesting Problem Based on Immune Genetic Algorithm
-
摘要: 基于遗传算法难以保持群体的多样性及存在易早熟、效率低的缺陷,提出免疫遗传算法应用于不规则零件排样的优化方法。该算法在遗传算法的全局随机搜索基础上,借鉴了人工免疫系统中的免疫记忆和浓度机制。通过疫苗接种实现种群个体中基因位的局部调整优化,并将其优良个体保存于免疫记忆库中,提高了算法的搜索速度。同时浓度机制保证了遗传交叉和变异过程中生成下代种群个体的多样性,扩大了搜索空间,更利于最优解的获取。该方法在开发的不规则件排样系统中进行了实算求解,通过与标准遗传算法的实验结果比对,板材的利用效率得到显著提高。Abstract: A novel solution for 2D irregular parts nesting with immune genetic algorithm(IGA) was presented,which overcome the shortages of premature constringency and low efficiency existing in genetic algorithms(GA).The immune memory and concentration mechanism of artificial immune system was introduced in global randomsearching of IGA. Vaccination realized individual gene a local adjustment and optimization,and the best individualcould be saved in immune memory library to improve the search speed of algorithm. At the same time the concen-tration mechanism ensured genetic population diversity during crossover and mutation process, expanded the search-ing space,more conducive to the optimal solution of the acquisition. Comparing with the standard genetic algo-rithm,the experimental results by immune genetic algorithm showed that the utilization of material is increased,theeffectiveness has been fairly proved in solving irregular parts nesting problem.
-
Key words:
- irregular parts nesting /
- artificial immune system /
- genetic algorithms
-
[1] 贾志欣. 二维不规则零件排样问题的遗传算法求解[J]. 计算机辅助设计与图形学学报,2002,14(5):1~4 [2] Jokobs S. On genetic algorithms for the packing of polygons[J].European Journal of Operational Research,1996,88: 165~181 [3] Jiao L C,Wang L. A novel genetic algorithm based on immunity[J]. IEEE Transactions on Systems,Man and Cybernetics-Patr A: Systems and Humans,2000,30(5):552~561 [4] 于喜洋,王小平. 免疫遗传算法在 TSP 求解中的应用[J]. 计算机应用与软件,2006,23(5) [5] 谢克明,郭红波,谢刚. 人工免疫算法及其应用[J]. 计算机工程与应用,2005,29(18):77~80 [6] 李满江,孟祥旭. 矩形件和任意多边形排样问题的算法及应用[J]. 贵州工业大学学报(自然科学版),2002,31(4):126~130 [7] 梁利东,叶家玮. 基于剩余矩形匹配算法的船体零件排样[J].船海工程,2008,37(4):7~9 [8] 刘嘉敏,张胜男,黄有群. 二维不规则形状自动排料算法的研究与实现[J]. 计算机辅助设计与图形学学报,2000,12(7):488~491
点击查看大图
计量
- 文章访问数: 241
- HTML全文浏览量: 24
- PDF下载量: 5
- 被引次数: 0