原文传递
多约束三维装箱问题的研究及实现
| 论文题名： | 多约束三维装箱问题的研究及实现 |
| 关键词： | 多约束条件;三维装箱;组合优化;遗传算法;目标函数;常规罚函数 |
| 摘要： | 多约束条件下三维装箱问题是一个NP-hard组合优化问题,它是将n个货物装入一组集装箱中,其目的是满足一定约束条件(诸如方向、限重、重心、装卸顺序、耐压等)的最大化体积装载率,以提高集装箱的利用率。 遗传算法因其较好的全局搜索性和鲁棒性,被应用在解决三维装箱问题上。遗传算法求解有约束组合优化问题是对目标函数在整个遗传空间中搜索满足约束条件的可行解。不满足约束条件的染色体被称为致死染色体。由于装箱问题约束条件复杂、苛刻,在种群进化过程中使得很多染色体不能满足,形成大量致死染色体,使算法的搜索性能恶化,甚至使算法不能运行。 因此在利用遗传算法解决装箱问题时引入了罚函数的概念,即对装箱问题的目标函数添加一个违背约束条件的惩罚处理。将多约束组合优化问题转化成了单约束组合优化问题,此法解决多约束问题虽简单直观,但在对约束条件的处理时要求所有的约束条件都不能有丝毫的违背,这就大大缩小了可行域的范围。事实上,最优解会在可行域的边界附近取得,刚性约束条件有可能排除掉一些非常优秀的装箱方案,甚至是最适用的装箱方案。 针对常规罚函数的缺点,利用模糊理论对约束条件进行模糊处理,该方法不仅能表示某一个点是否在可行域内,而且对在可行域外的点按照离可行域的远近程度进行模糊处理。可行域与不可行域没有明显的界限,对不完全可行解按其违反约束的程度加以评价,若其违反约束的程度很小时,可近似认为解为可行解。其扩大初始阶段搜索范围,充分利用包含有优秀基因的部分致死染色体,防止有效基因丢失,保留近优解的遗传,从而达到降低致死染色体数目的目的；扩充了可行解的范围,实现了全局搜索最优的装箱组合的目的,计算实例表明了算法具有比较好的装箱效果。 |
| 作者： | 雍文君 |
| 专业： | 模式识别与智能系统 |
| 导师： | 马炫 |
| 授予学位： | 硕士 |
| 授予学位单位： | 西安理工大学 |
| 学位年度： | 2008 |
| 正文语种： | 中文 |
检索历史
应用推荐
