论文部分内容阅读
装箱问题就是将不同尺寸的物品摆放入有一定容量的容器中,以获得某种最佳的效益。装箱问题广泛地用于机械生产和交通运输等行业当中。对该问题的求解方法的研究无论是在理论上,还是在实践中都具有一定的意义。装箱问题属于组合最优化问题和NP完全问题,具有高度复杂性,用一般的数学方法根本无法求解,目前只能用启发式方法解决装箱问题,因此,从六十年代开始,陆续提出的都是近似算法。 文中首先对装箱问题的种类、求解算法,以及装箱问题的研究现状进行了综述和分析。重点放在研究用于解决装箱问题的各种启发式算法,在总结概括了当前主要的装箱优化算法的基础上,指出构造式启发式算法与遗传算法相结合,是改进装箱算法的一种有效的途径。然后依据该混合遗传算法,采用Delphi语言开发了用于解决任意尺寸三维物体装载的智能装载系统,并详细说明了系统的整体结构、设计过程以及数据流程图,对部分系统运行结果进行了分析。并且给出了该算法和第二章给出的构造启发式算法的性能比较。 遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法,对于非常复杂、高度非线性大型系统的优化求解,表现出比其它传统优化方法更加独特和优越的性能,是21世纪有关智能计算中的核心技术之一。利用简单的编码技术和繁殖机制来表现复杂的现象,从而解决非常困难的问题。特别是它不受搜索空间的限制性假设的约束,不必要求诸如连续性、导数存在和单峰等的假设。 文中综述了遗传算法的基本原理和方法,分析了遗传算法的编码、适应度函数、选择算子、交叉算子和变异算子在整个遗传算法的运算过程中的作用。针对装箱问题对编码方式作了改进,采用数字符号编码方式。本文采用了跨世代精英选择策略来保持种群中的优良个体,使得产生的遗传算法更加有效,同时,提出了与装箱问题相适应的交叉和变异策略。但是单一地使用一种算法不易得到十分满意的结果,因此在遗传算法的搜索策略和变动策略中应用了启发式方法,引导装箱问题方法研究及其集成应用搜索方向。结果表明应用该混合方法缩短了计算时间,同时使得问题的解得到了很好的改善。最后,总结了本文的工作并展望了进一步的研究方向。