《一种求解一维装箱问题的拟人算法 毕业论文》由会员分享，可在线阅读，更多相关《一种求解一维装箱问题的拟人算法 毕业论文（25页珍藏版）》请在金锄头文库上搜索。
1、 I摘 要一维装箱问题来源于人们的长期以来的生产实践，是一种组合优化问题。给定有穷个物体，每个物体的重量是已知的正实数。给定足够多个空箱子，问题是要在满足两个约束条件的前提下，将所有物体放到箱子中去，使得所用箱子的个数尽可能地少。两个约束条件是：第一，每个物体均保持完整，恰好放到一个箱子中去。不能将物体分割成几块。第二，每个箱子中所放的物体的重量之和均不能超过一个相同的上限，这个上限是一个已知的正实数。一维装箱问题具有很高的理论价值和实际价值。一方面，学者已经证明一维装箱问题是一个 NP 难度问题，因此一维装箱问题具有很高的理论价值。另一方面，一维装箱问题出现在实际生产的一些领域，因此也具有很
2、高的实际价值。迄今为止，国内外学者提出了许多用来求解一维装箱问题 的严格算法和近似算法。一方面，严格的最优算法所花时间太长，实际部门无法忍受。另一方面，近似算法由于可能快速地生成最优解或者接近最优解而为实际生产部门所广泛采用。人类把物体往容器中装，已有几千年以上的经验。这些生活经验可引导出高效率的算法。本文提出了一种拟人算法。算法由三个部分组成。第一部分是降序最佳适合算法，用于生成初始解。第二部分是邻域搜索算法。给定一个解，用邻域搜索算法可以通过迭代改进这个解。本文的邻域定义的思想来源于“天之道损有余而补不足” 。第三部分是跳坑策略。跳坑策略用于跳出局部最优解，将搜索引向有希望的区域，从而提高
3、算法的效率。跳坑策略的思想来源是“三十六计走为上” 。本文的程序计算了一组共 17 个国际公认的问题实例。这组问题实例分为两类。第一类为 8 个问题实例，目前尚未确定其客观最优解。第二类为 9 个问题实例，目前已经确定了其客观最优解。拟人算法对第一类问题实例中的 6 个问题实例找出了与当前已知最好解质量相同的解。拟人算法还证明了 TEST0068 这个问题实例的目前已知最好解正是客观最优解。拟人算法快速地找出了第二类问题实例中全部 9 个问题实例的客观最优解。计算结果表明，拟人算法是一种有效的求解一维装箱问题的近似算法。II关键词关键词： NP 难度； 拟人； 邻域搜索； 跳坑； 装箱Abst
4、ractThe one dimensional 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 nenough identical bins, the weight of ea
5、ch item is a known positive 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 in
6、to several parts and put 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
7、the other hand, the one dimensional 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 work
8、ers. On the other hand, approximation 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 algor
9、ithm is presented in this 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 de
10、finition of the neighborhood 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 IIIimprove the algorithm. The i
11、dea of the off-trap strategy 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 stil
12、l unknown. The second class 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 instanc
13、e named as TEST0068 up to now 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 packingIV目 录1 绪论 .11.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 释放内存 .
