《一种求解一维装箱问题的拟人算法》由会员分享，可在线阅读，更多相关《一种求解一维装箱问题的拟人算法（24页珍藏版）》请在金锄头文库上搜索。
1、 摘 要一维装箱问题来源于人们的长期以来的生产实践，是一种组合优化问题。给定有穷个物体，每个物体的重量是已知的正实数。给定足够多个空箱子，问题是要在满足两个约束条件的前提下，将所有物体放到箱子中去，使得所用箱子的个数尽可能地少。两个约束条件是：第一，每个物体均保持完整，恰好放到一个箱子中去。不能将物体分割成几块。第二，每个箱子中所放的物体的重量之和均不能超过一个相同的上限，这个上限是一个已知的正实数。一维装箱问题具有很高的理论价值和实际价值。一方面，学者已经证明一维装箱问题是一个NP难度问题，因此一维装箱问题具有很高的理论价值。另一方面，一维装箱问题出现在实际生产的一些领域，因此也具有很高的实
2、际价值。迄今为止，国内外学者提出了许多用来求解一维装箱问题的严格算法和近似算法。一方面，严格的最优算法所花时间太长，实际部门无法忍受。另一方面，近似算法由于可能快速地生成最优解或者接近最优解而为实际生产部门所广泛采用。人类把物体往容器中装，已有几千年以上的经验。这些生活经验可引导出高效率的算法。本文提出了一种拟人算法。算法由三个部分组成。第一部分是降序最佳适合算法，用于生成初始解。第二部分是邻域搜索算法。给定一个解，用邻域搜索算法可以通过迭代改进这个解。本文的邻域定义的思想来源于“天之道损有余而补不足”。第三部分是跳坑策略。跳坑策略用于跳出局部最优解，将搜索引向有希望的区域，从而提高算法的效率
3、。跳坑策略的思想来源是“三十六计走为上”。本文的程序计算了一组共17个国际公认的问题实例。这组问题实例分为两类。第一类为8个问题实例，目前尚未确定其客观最优解。第二类为9个问题实例，目前已经确定了其客观最优解。拟人算法对第一类问题实例中的6个问题实例找出了与当前已知最好解质量相同的解。拟人算法还证明了TEST0068这个问题实例的目前已知最好解正是客观最优解。拟人算法快速地找出了第二类问题实例中全部9个问题实例的客观最优解。计算结果表明，拟人算法是一种有效的求解一维装箱问题的近似算法。关键词： NP难度； 拟人； 邻域搜索； 跳坑； 装箱AbstractThe one dimensional
4、bin packing problem, which is a famous combinatorial optimization problem, comes from long term practice of human being. The definition of the one dimensional bin packing problem discussed in this paper is as following. Given items and enough identical bins, the weight of each item is a known positi
5、ve real number. The capacities of all bins are equal. The problem is to pack all items into the bins with the objective of minimizing the number of occupied bins, subject to two following constraints. (1) Each item is packed into exact one bin. Each item cannot be divided into several parts and put
6、into different bins. (2) The sum of weight of all items of each bin cannot exceed its capacity. The one dimensional bin packing problem is of both highly theoretical and practical values. On one hand, the one dimensional bin packing problem has been proved to be NP-hard. On the other hand, the one d
7、imensional bin packing problem appears in some real world factories.So far, many exact algorithms and approximation algorithms have been proposed to solve the one dimensional bin packing problem. Exact algorithms require too much computing time and cannot be accepted by workers. On the other hand, a
8、pproximation algorithms are widely used by workers, since they may give optimal or near optimal solutions quickly.Mankind have more than several thousands of years of experience to pack items into containers. The experience can induce efficient algorithm. A quasi-human algorithm is presented in this
9、 paper, which is composed of three parts. The first part is best fit decreasing algorithm to generate initial solution. The second part is local search algorithm. Given a solution, local search algorithm is used to improve this solution by iterative steps. The idea of the definition of the neighborh
10、ood comes from a Chinese motto “It is the Way of Heaven to diminish superabundance, and to supplement deficiency”. The third part is off-trap strategy, which is used to jump off local optimum and guide the search into promising areas, so as to improve the algorithm. The idea of the off-trap strategy
11、 comes from a Chinese motto “decamping being the best”.Computational experiments are carried out on a set of 17 benchmark problems. This set of 17 benchmark instances can be divided into two classes. The first class consists in 8 instances whose optimal solutions are still unknown. The second class
12、consists in 9 instances whose optimal solutions are already known. For 6 out of 8 instances of the first class, our algorithm finds out solutions which are equal to the best known solutions up to now. Our algorithm proves that the best known solution for benchmark instance named as TEST0068 up to no
13、w is optimal. For all 9 instances of the second class, our algorithm finds out optimal solutions quickly.The results show that the quasi-human algorithm is an efficient algorithm for the one dimensional bin packing problem.Keywords: NP-hard; Quasi-human; Local search; Off-trap; Bin packing目 录1 绪论11.
14、1 引言11.2 问题描述11.3 研究现状21.4 本论文的主要结构52 算法描述62.1 拟人算法的大致框架62.2 生成初始解72.3 邻域搜索72.4 跳坑策略93 程序设计113.1 程序流程113.1.1 读取文本文件中的数据133.1.2 生成初始解133.1.3 邻域搜索143.1.4 释放内存153.2 调试程序154 计算结果165 结论18参考文献19致谢21IV1 绪论1.1 引言当前世界经济高速发展，人口日益增加，资源日渐紧张。人们在生产生活中希望提高效率，节约资源，以实现可持续发展。在运筹学领域有一类所谓最优化问题。最优化问题的一般形式是：在满足约束条件的前提下，给
15、出自变量的值，使得目标函数值最优 (通常是使得目标函数值最小或者最大)。一维装箱问题1来源于人们的长期以来的生产实践，是一种最优化问题，一维装箱问题具有很高的理论价值和实际价值。一方面，学者已经证明一维装箱问题是一个NP难度问题，因此一维装箱问题具有很高的理论价值。在现实的工业、商业、交通、通信、军事等领域出现了大量的所谓NP难度问题，例如车间调度问题、货郎担问题等等。人们虽然目前不能证明，但是强烈相信NP难度问题不存在时间复杂度为多项式的完整算法。所谓完整算法，对于优化问题来说就是能保证找到最优解的算法，对于判定问题来说就是能够保证正确判定的算法。另一方面，一维装箱问题出现在实际生产的一些领
16、域，因此也具有很高的实际价值。世界各国学者已经对一维装箱调度问题做了数十年的研究，人们还提出了许多种算法来求解一维装箱调度问题。另外，在现实中存在二维、三维、多维的装箱问题。本文仅讨论一维装箱问题。1.2 问题描述本文研究的这种一维装箱问题的描述如下。给定有穷个物体，每个物体的重量是已知的正实数。给定足够多个空箱子，问题是要在满足两个约束条件的前提下，将所有物体放到箱子中去，使得所用箱子的个数尽可能地少。两个约束条件是：第一，每个物体均保持完整，恰好放到一个箱子中去。不能将物体分割成几块。第二，每个箱子中所放的物体的重量之和均不能超过一个相同的上限，这个上限是一个已知的正实数。为了将问题描述得确切，本文提出一种形式化描述。表示物体的集合。
