经典一维装箱问题的适应近似算法的研究
摘要
本文研究经典一维装箱问题（Bin Packing Problem）及其适应近似算法，给出了一个新的适应近似算法：交叉装填算法（简称CF算法），而且证明了当这些物件大小按非增性预先排序后，CF算法时间复杂度是线性的；通过具体例子说明交叉装填算法优于其它适应
近似算法，并且推断CF算法达到装箱问题的最好近似值3
2
。
关键词：一维装箱问题，近似算法，适应算法，交叉装填算法
ABSTRACT
In this paper the Bin-Packing problems and any-fit approximation algorithm are studied. We give a new any-fit approximation algorithm (Cross Fit Approximation Algorithm) in O(nlogn)steps. In addition, if the sizes of all objects decreasing according to their sizes, The
any-fit approximation algorithm runs in O(n)steps. This paper proved the cross fit approximation algorithm’s capability excelled other any-fit approximation algorithm’s by some
example,and extrapolate the new any-fit algorithm is a 3
2
-approximation algorithm.
Key Words：Pin Packing Problem，Approximation Algorithm，Any-fit Algorithm，Cross Any-fit Algorithm.
1． 引言
1．1 问题的提出
装箱问题也就是把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品体积之和不超过箱子容量并使所用的箱子数目最少。其应用在实际生活中无处不在，货物装运，服装裁剪，以及计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。例如某国际物流公司有一批固体货物要装进集装箱用船从广州运到美国。每个集装箱的规格都一样（体积均为150立方米），而每件货物体积不一定相同但其长宽高都小于集装箱的。问怎样的装箱方案最省钱，即所用集装箱最少？研究装箱问题能够更好解决上述这些问题，有很大的经济效益。所以装箱问题有着广泛的应用背景，具有很大的研究价值。
但是装箱问题是NP 难解问题[7]，这意味着该问题不存在在多项式时间内求得精确解的算法（如果P ≠NP ）因此对装箱问题算法的研究指的是对其近似算法的研究，所谓近似算法即该算法可以求得与精确解接近的结果但不一定得到精确解。目前，已经提出了大量的近似算法，其中适应近似算法是目前时间复杂性比较低的一种近似算法。如下次适应（NF ）算法、首次适应（FF ）算法、最佳适应（BF ）算法、降序首次适应(FFD)算法、降序最佳适应(BFD)算法等。
装箱问题中最早被研究的是一维装箱问题。随着研究的深入，人们发现实际生活中更多存在的是一些带约束的装箱问题，因此也就抽象化出了，如二维装箱问题（条形装箱问题、剪裁问题）、三维装箱问题、变容装箱问题、有色装箱问题、对偶装箱问题等等一系列的带约束的装箱问题。但是由于这些问题的NP 困难性，虽然已经有一些研究成果，但是还有很许多未解问题,甚至一些是一维装箱问题[5]。一维装箱问题是指要求把一些物品放入到具有固定容量的箱子中，并最小化所使用的箱子数目。本文所讨论的是一维装箱问题。
1．2 相关知识
在研究一维装箱问题的适应近似算法之前，我们先来了解一下一些相关的知识。 1．2．1近似算法的定义
一个组合最优化问题π是一个最小化或最大化的问题,由三部分组成:实例的集合
f π;?I ∈f π,有一个有限的可行解集合()F I π;有一个目标函数
g π,使得?I ∈f π及σ∈()F I π,赋予一个正有理数g π(I, σ),称为σ的目标值.
对于最小(大)化问题,称*σ∈()F I π为I ∈f π的最优值是指σ∈()F I π,恒有
**(,)(,)((,)(,)).g I g I g I g I ππππσσσσ≤≥
最优解*σ的目标值*(,)g I πσ成为I 的最优值,记作OPT (I)π,当这个问题明确时通常省略下标
π.
定义1 称算法A 是π的一个近似算法(Approximation Algorithm)是指: ?I ∈f π,应用算法A 总可以找出I 的一个可行解σ∈()F I π.对应的解的目标值(,)g I πσ记作()I A ,表示由算法A 得到的I 的目标值.若?I ∈f π,都有()I A =OPT(I)，则称A 是π的最优算法(Optimization Algorithm)。 1．2．2适应算法
定义2 适应算法(Any Fit Algorithm)：适应算法是解装箱问题的一个近似算法。当处理当前物品，如果有已经打开的箱子中能够放下这个物品，则不打开新的箱子，符合该条件的算法被称为适应算法。
其中下次适应算法、首次适应算法、最佳适应算法、最坏适应算法和几乎最坏适应算法是几个著名的适应算法。适应算法的最坏情况性能比被证明一定处于[1.7,2]范围内，即在最坏情况性能上不可能优于首次适应算法[2]。 1．2．3经典一维装箱问题
在经典一维装箱问题中，处理对象是n 个输入物品的序列和一个无限多的等容量箱子序列；目标是把所有物品放入箱子中并最小化所使用的箱子数目。可以对其做如下定义： 经典一维装箱问题：给定n 个物品的序列L n =（a 1,a 2,…,a n ），物品a i （1≤i ≤n ）的大小s (a i ) ∈(0,1]，要求将这些物品装入最小数量的单位容量的箱子中。例如，把a i （1≤i ≤n ）分别放入箱子序列B 1,B 2,…,B m 中，使得每个箱子中的物品大小之和不超过1，即∑∈j i B a s (a i )≤1，1≤j ≤m ，且使所用的箱子数目m 最小。
2． 经典一维装箱问题的适应近似算法
近似算法并不保证给出最优解,那么应当如何来评价近似算法的好坏呢?主要基于两个方面的考虑.首先是时间复杂性方面的要求,即要求有一个多项式时间界;其次是性能方面的要求,即希望所求得的近似解尽可能地“接近”最优解.可以从不同的角度来评价近似算法性能,大体可以分为三类:第一类是以算法在最坏情况下的行为标准，研究算法得到最优解的接近程度，越接近越好；第二类是以算法的平均行为为标准研究得到最优解的概率；第三类是局部搜索算法，寻找局部最优解，这种算法有时很好，有时很坏，只能通过实践加以评定。本文所讨论的是第一种类型。
为了更好地从性能方面来讨论近似算法，我们给出度量近似算法性能的两个指标。 设π是一个最小（大）化问题，I 是π的实例。设A 是π的一个近似算法，由A 得到的目标值为A （I ），而I 的最优目标值为OPT （I ），记
()()()A A I R I OPT I =
（()
()()
A OPT I R I A I =）,
定义3 π的近似算法A 的绝对性能比（absolute performance ratio ）记为 {}i n f (),A A R r R I r I f π=≤?∈， 定义4 π的近似算法A 的渐近性能比（asymptotic performance ratio ）记为
{}i n f ,I r A
A R r n OPT n R ∞
*=?∈?≥≤的实例，有N ，
其中{}*
=全体非零自然数N 。 A
R ∞
又称为近似算法A 的近似值。 我们分析装箱问题的近似算法的性能包括两个主要内容[2]： （1）建立近似算法在最坏情况下所得目标值的一个界；
（2）构造实例说明得到的界可以达到或渐近达到，从而说明这个界已经相当好了。 首先我们用下面的经典结果说明一维装箱求解的困难程度。
引理1[1] 如果P NP ≠，那么对于任意给定的0ε>，不存在近似值为3
2
ε-的近似算法来
解决一维装箱问题。
因此这个3
2
近似值是我们对一维装箱问题的近似算法的最好期待，事实上，很多近似
算法的近似值都是朝这个目标迈进[3]。本文给出的算法也是朝这个目标前进。
2．1已知的常用适应近似算法[2][3][4] 2．1．1 NF(Next Fit)近似算法
该算法的做法是随到随装,装不下就封箱运走.将n 个物品12,,n s s s 依次装箱,设
12,,i s s s 已装入1B 箱,且1211()i i a a a a +-+++< 即1i s +不能装入1B 箱,则1B 箱虽未装满也装箱送走, 1i s +装入下一个箱子2B ,……
这种装箱方法适合流水作业,其时间复杂性为O(n)。 定理1[2] 对装箱问题的何实例I ，均有
()2()1NF I OPT I ≤- （2.1）
例1 设物品集{}124,,,m s s s s = ，各物品得体积为
1
21.2i i a i m
???=????，为奇数，，为偶数 对这个实例I ，易知OPT （I ）＝m+1，而NF （I ）＝2m ，从而
()22()()1
N F I m
m O P T I m =
→→∞+
由定理1和例1，我们有 推论2[2]
2NF R =. (2.2)
2．1．2 FF （First Fit ）近似算法
这是一种较为直观的、容易想到的装箱方法，其基本思想是将n 个物品12,,,n s s s 顺次装箱，设装箱的次序是12,,B B ；对某一物i s ，它总是被装到第一个能装下它的箱子中，也就是说物品i s 被装到已装进的物品的体积不超过1i a -的下标最小的箱子中。这种装箱办法虽然不要求n 个物品全部到达后再装箱，但要求所有箱子都装好后一起送走，可以说适合半流水线作业。
由于每个物品i s 装箱时都必须从1B 开始顺次查看各个箱子是否能装下它，故FF 算法的时间复杂性为2()O n 。
关于FF 算近似法的性能我们有如下结果：
定理3[3] 对装箱问题的任何实例I ，均有 17
()()110FF I OPT I ≤+， （2.3）
并且，存在实例I ，使得()OPT I 充分大且满足 17
()(()1)10
FF I OPT I ≥
-， 从而17
10
FF
R ∞
=。 公式（2..3给出了FF 近似算法在最坏情况下所得到的目标值的界，反映了近似解
“接近”最优解的程度。
下面用FF 算法计算一个例子所需的箱子数目。 例2设物品集{}1218,,,m s s s s = ，物品i s 的体积i a 为
1
,16
,71,612,31
,12
18,2i i m a m i m m i m εεε?+≤≤???=+<≤???+<≤??
其中0ε>充分小。在这个实例I 中，最优值()6O P T I m =，而()10F F I m =，故
5
()()3
FF I OPT I =，装箱方案如图1所示，左边第一个图是最优装箱方案，右边的三个图
是FF 近似算法的装箱方案
6m 个 m 个 3m 个 6m 个
图1 例2的装箱方案
2．1．3 FFD （First Fit Decreasing ）近似算法
该算法要求n 个物品全部到达后才开始装箱（因为物品全部到达后才能将它们按体积从大到小排列），同时也要求所有箱子全部装好后一起送走。FFD 近似算法比FF 近似算法多了排序的计算量(log )O n n ，因而它的时间复杂性仍然为2()O n [4]。
定理4[2] 对装箱问题的任何实例I ，均有
11
()()19FFD I OPT I ≤+，
并且存在实例I ，使得()OPT I 充分大且满足
11
()()9
FFD I OPT I =
， （2.3） 从而119
FFD
R ∞
=。 下面的例子表明（2.3）式的成立。
例3 设物品集{}1230,,,m s s s s = ，各物品的体积为
1
,16
,212,612,41,1218,41
2,1830,4
i i m m i m a m i m m i m εεεε?+≤≤??
?+<≤?=?
?+<≤???-<≤?
其中0ε>充分小，该实例I 的最优值为()9OPT I m =，而()11F F D I m
=，故11
()()9
FFD I OPT I =
。装箱方案如图2所示，其中前面两个图为最优装箱方案 ，后三个图为FFD 近似算法的装箱方案。
6m 个 3m 个 6m 个 2m 个 3m 个
图2 例3的装箱方案
上述三种一维装箱问题的适应算法虽然逐步逼近引理1的解决方案，平均性能比也达到
了1[2],但离最优值还有一定距离，并且得到的装填方案有比较大的随机性，实际操作起来有一定难度，下面对上述一维装箱问题的适应近似算法加以改进，给出一种可操作性强的一种更优化的近似算法。
如果对FF 算法稍加修改：物品i s 装进j B 中要求留下的空隙最小，即
{}1()min 1()1()j i k i k i k
c B a c B a c B a --=---≥
这就得到另一个近似算法——BF （best fit ）近似算法。但如果在装箱前先把物品按体积从大到小排列，再利用FF 近似算法（或BF 近似算法）就得到改进的近似算法——FFD （或BFD ）近似算法。在FFD （或BFD ）近似算法的基础上利用交叉装填的思想，就得到一种新的经典一维装箱问题的适应近似算法——交叉装填近似算法。 2．2新的适应近似算法
算法的主要意思是：先把物件按大小从大到小的顺序排列，然后首先把左端最大的一个物件放入箱子中，再从物件序列的最右端开始从右往左依次把物件放入箱子中，直到下一个物件不能放入该箱子，那么开启新的箱子，重复上述装填步骤，直到所有的物件都装入箱子中。
下面给出经典一维装箱问题的交叉装填算法： 交叉装填算法（CF 近似算法）
输入：12(,,,)n L a a a = 及每个物件的大小(]()0,1,1,2,,i s a i n ∈= 。
输出：需要的箱子数目m 。
步骤1：把物件12,,,n a a a 按其大小进非增序排列，不妨设12()()()n s a s a s a ≥≥≥ 。 步骤2：首先把1a 放入箱子1B 中，然后从最右端开始，依次把物件1,,n n a a - 放入1B ，直到下一个物件不能再装入箱子为止，此时开启新的箱子2B 。
步骤3：设在第i 步循环时，打开第i 个箱子，此时把物件i a 放进箱子i B 中，再从最右端开始从右往左把物件依次放入i B 中。假设第1i -步循环时第1i -个箱子1i B -中最后一个放入的物件为k a ，则在第i 步循环时最右端的物件为1k a -，那么当
12()()()()1i k k l s a s a s a s a --++++≤ 且121()()()()()1i k k l l s a s a s a s a s a ---+++++> 时，把12,,k k l a a a -- 放入i B 中，同时开启新的箱子1i B +。直到把所有物件都放进m 个箱子里。 步骤4：得出交叉装填算法所需的箱子数目m 。
下面作者用新的一维装箱问题的适应近似算法求解例13 ，在求解过程中比较该近似算法较上述几种算法性能。
例1’ 设物品集{}124,,,m s s s s = ，各物品得体积为
1
2
1.2i i a i m
???=????，为奇数，，为偶数
对这个实例I ，易知OPT （I ）＝m+1，而CF （I ）＝m ＋1，从而
()
1
1()1
C F I m O P T I
m +=
=+. 装箱方案如图3所示，其中前面两个图为最优装箱方案 ，后两个图为FFD 近似算法的装箱方案。
1个 m 个 2个 1m -个 图3 例1’的装箱方案
例2’ 设物品集{}1218,,,m s s s s = ，物品i s 的体积i a 为
1
,16
,71
,612,31
,12
18,2i i m a m i m m i m εεε?+≤≤???=+<≤???+<≤??
其中0ε>充分小。在这个实例I 中，最优值()6OPT I m =，而(I)=6 m CF ，故：
()61()6C F I m
O P T I m
==
装箱方案如图4所示，其中左边第一个图是最优装箱方案，右边的三个图是FF 近似算法的装箱方案。
6m 个 2m 个 3m 个 m 个
图4 例2’装箱方案
13
ε+
例3’ 设物品集{}1230,,,m s s s s = ，各物品的体积为
1
,16
,212,612,41,1218,41
2,1830,4
i i m m i m a m i m m i m εεεε?+≤≤??
?+<≤?=?
?+<≤???-<≤? 其中0ε>充分小，该实例I 的最优值为()9OPT I m =，而()10C F I m
=，故10
()()9
CF I OPT I =
。装箱方案如图5所示，其中前面两个图为最优装箱方案 ，后三个图为FFD 近似算法的装箱方案。
6m 个 3m 个 6m 个 3m 个 m 个
图5 例3’的装箱方案
在用交叉装填近似算法（CF 算法）对例1、例2和例3求解的过程中，我们得到例1’、例2’和例3’的求解方案得到：
说明1：观察例1和例1’的求解方案，我们得到CF 近似算法能够达到最优解，性能优于NF 近似算法。
说明2：观察例2和例2’的求解方案，我们得到CF 近似算法能够达到最优解，性能优于FF 近似算法。
说明3：观察例3和例3’的求解方案，我们得到CF 近似算法虽然未能达到最优解，但是
103(3')92
CF R ∞
=<例，而且性能优于NF 近似算法。
说明4：交叉装填近似算法是一维装箱问题的适应近似算法中机械操作最强的一种算法，对所有一维装箱问题都有固定的装箱方案，对半流水线作业容易达到最优解。
猜想5：交叉装填近似算法是目前经典一维装箱问题的适应近似算法中最优化的一种算法，
交叉装填算法是一维装箱问题的32-近似算法,即32
CF
R ∞
=。
论断6：交叉装填近似算法的时间复杂性为(log )O n n 。
证明： 由于在初始化步骤（步骤1）中，由文献[6]得到排序所用的时间为(log )O n n 。在迭代步骤中，第1次循环所用的时间为1(())O B σ，第2次循环所用的时间为2(()),,O B σ 第
m 次循环所用时间为(()),m O B σ而12(())(())(()).m O B O B O B n σσσ+++= 从而迭代步骤所需的时间为()O n .故交叉装填算法的时间复杂性为(log )O n n 。如果物件按非增性质先排列好序，则交叉装填算法的复杂性为()O n 。 结论：
本文对经典一维装箱问题给出了一个新的适应近似解法，它是多项式时间算法；用新旧适应近似算法求解具体例子，通过对新旧算法的性能比较，得出新算法求得的问题的
解与“最优值3
2
” 更进一步地接近。由于本文给出的适应近似算法优于已有的适应近似
算法，我们完全可以猜想经典一维装箱问题的交叉装填适应近似算法是一维装箱问题的3
2
-近似算法。 通过对一维装箱问题适应近似算法的研究，我们可以很容易得到具体装箱问题比较理想的解决方案，例如在引言里叙述的物流公司的集装箱问题，在只考虑体积和已知各物件的体积的情况下就可以利用交叉装填近似算法来装箱。读者不妨自己尝试设定各物件的体积，看看能不能算出该物流公司这次所需的集装箱个数，同时看能否找到比交叉装填近似算法更好的装箱方案。
此外，现在人们更多的关注于由一维经典装箱问题所衍生出来的一些装箱问题，这些问题一方面与一维装箱问题有着密切联系，另一方面又有着更广泛的实际应用背景。我们未来的工作应继续关注研究经典一维装箱问题交叉装填适应近似算法的性能以及装箱问题衍生的各种问题，以其能对实际生活工作提供更大的帮助。
参考文献
[1] 孙春玲，陈智斌，李建平. 装箱问题的一种新的近似算法[J].云南大学学报（自
然科学版）. 2004，26（5）.392－396
[2]谢政编著.网络算法与复杂性理论[M].国防大学出版社.2003,12.223-275
[3] 顾晓东，陈国良.装箱问题的并行近似算法[J].计算机学报.2001，24（5）.548
－552
[4] 冯晓慧，李菊娥，任春丽.装箱问题的一种新算法及其性能比的证明[J].西安电
子科技大学学报.1998，4（25卷2期）.231－238
[5]顾晓东，陈国良，顾钧等.调和装箱问题的平均性能分析[J].计算机学报.2001,5
[6]（美）Papadimitriou，C.H，Steigtisz K. 组合最优化算法和复杂性[M].清华
大学出版社.1988,6.228-235
[7]胡知能，徐玖平.运筹学——线性系统优化[M].科学出版社.2003,3.
致谢
感谢我的论文指导老师刘岩副教授，她严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；她循循善诱的教导和不拘一格的思路给予我无尽的启迪。这篇论文的每个方法和每个例子，都离不开刘岩教授的析心指导；而她开朗的个性和宽容的态度，使我能够很愉快地完成了这篇论文。
感谢我的爸爸妈妈，焉得谖草，言树之背，养育之恩，无以回报，你们永远健康快乐是我最大的心愿。
在论文即将完成之际，我的心情无法平静，从开始选题到论文的顺利完成，有多少可敬的师长、同学、朋友给了我无私的帮助，在这里请接受我诚挚的谢意！
遗传算法入门到掌握 读完这个讲义，你将基本掌握遗传算法，要有耐心看完。 想了很久，应该用一个怎么样的例子带领大家走进遗传算法的神奇世界呢？遗传算法的有趣应用很多，诸如寻路问题，8数码问题，囚犯困境，动作控制，找圆心问题（这是一个国外网友的建议：在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆心。），TSP问题（在以后的章节里面将做详细介绍。），生产调度问题，人工生命模拟等。直到最后看到一个非常有趣的比喻，觉得由此引出的袋鼠跳问题（暂且这么叫它吧），既有趣直观又直达遗传算法的本质，确实非常适合作为初学者入门的例子。这一章将告诉读者，我们怎么让袋鼠跳到珠穆朗玛峰上去(如果它没有过早被冻坏的话)。 问题的提出与解决方案 让我们先来考虑考虑下面这个问题的解决办法。 已知一元函数： 图2-1 现在要求在既定的区间内找出函数的最大值。函数图像如图2-1所示。 极大值、最大值、局部最优解、全局最优解
在解决上面提出的问题之前我们有必要先澄清几个以后将常常会碰到的概念：极大值、最大值、局部最优解、全局最优解。学过高中数学的人都知道极大值在一个小邻域里面左边的函数值递增，右边的函数值递减，在图2.1里面的表现就是一个“山峰”。当然，在图上有很多个“山峰”，所以这个函数有很多个极大值。而对于一个函数来说，最大值就是在所有极大值当中，最大的那个。所以极大值具有局部性，而最大值则具有全局性。 因为遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。所以也可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。在这个多维曲面里面也有数不清的“山峰”，而这些最优解所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遗传算法不一定要找“最高的山峰”，如果问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应的，遗传算法所要找的就是“最深的谷底”）如果至今你还不太理解的话，那么你先往下看。本章的示例程序将会非常形象的表现出这个情景。 “袋鼠跳”问题 既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰（尽管袋鼠本身不见得愿意那么做）。所以求最大值的过程就转化成一个“袋鼠跳”的过程。下面介绍介绍“袋鼠跳”的几种方式。 爬山法、模拟退火和遗传算法 解决寻找最大值问题的几种常见的算法： 1. 爬山法（最速上升爬山法）： 从搜索空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来的个体，不断重复上述过程。因为只对“邻近”的点作比较，所以目光比较“短浅”，常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。（在爬山法中，袋鼠最有希望到达最靠近它出发点的山顶，但不能保证该山顶是珠穆朗玛峰，或者是一个非常高的山峰。因为一路上它只顾上坡，没有下坡。） 2. 模拟退火： 这个方法来自金属热加工过程的启发。在金属热加工过程中，当金属的温度超过它的熔点（Melting Point）时，原子就会激烈地随机运动。与所有的其它的物理系统相类似，原子的这种运动趋向于寻找其能量的极小状态。在这个能量的变
算法分析 题目：装箱（Bin Packing）问题 院别：数学与计算科学学院 专业：信息与计算科学 姓名：蒋文明 学号：0800710313 指导老师：宁黎华 日期： 2011. 06. 9
目录 一、问题描述 (1) 二、问题分析 (1) 三、代码实现 (2) 四、测试结果 (3) 五、心得体会 (4) 六、源程序 (4)
一、问题描述 一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1， 2*2， 3*3， 4*4， 5*5，6*6.这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。 二、问题分析 对于6*6的一个箱子来说，最多只能放一个6*6或一个5*5或4*4的盒子，所以我们初始化需要的箱子数时就是这这几种箱子的个数和，对于3*3的箱子来说，我们可以放一个或2个或3个或4个，这我们可以通过整除和取模来确定放了3*3盒子的箱子数，再把它加入到总箱子数中，接下来我们就是把1*1和 2*2的盒子塞进前面所需的箱子中，当塞不完时再来新增盒子，我们首先要将前面的箱子剩余的空间统计出来，并且要以2*2的优先考虑，因为我们可以把多余的2*2的位置变为填充4个1*1的，毕竟1*1的只要有空间随处都可以塞。所以当我们的箱子要是装了1个5*5的盒子的话，那么它就只能塞1*1的了，一个可以塞11个1*1的，对于装了4*4的盒子的话，那么还可以装5个2*2的盒子，暂且不要去转话成1*1的，除非没办法只能装1*1的，对于3*3 的话就可以根据取模之后一个箱子剩下的空间了，如果一个箱子中只放了一个3*3的，那么还剩下3个3*3的空间可以放，我们知道可以放5个2*2的和7个 1*1的，对于放了2个3*3的箱子，我们剩下的空间可以放3个2*2的以及6个1*1的，对于放了
本科生毕业设计年产10万吨啤酒厂设计 姓名 学号 专业食品科学与工程班级 指导教师 学部食品与环境学部答辩日期
黑龙江东方学院本科生毕业论文（设计）评语（一） 姓名学号专业 班级 05-D 总 成绩 毕业论文（设计）题目：年产10万吨啤酒厂设计 答 辩 委 员 会 评 语 答辩成绩 主任签字：年月日答辩委员会成员签字 学部 毕业 论文 （设 计）领 导小 组意 见 组长签字：年月日学部公章
黑龙江东方学院本科生毕业论文（设计）评语（二）姓名李季学号054131235 专业班级05-D 毕业论文（设计）题目：年产10万吨啤酒厂设计 指导教师成绩 指 导 教 师 评 语 指导教师签字：年月日
黑龙江东方学院本科生毕业论文（设计）评语（三）姓名李季学号054131235 专业班级05-D 毕业论文（设计）题目：年产10万吨啤酒厂设计 评阅教师成绩 评 阅 教 师 评 语 评阅教师签字：年月日
黑龙江东方学院本科生毕业论文（设计）任务书姓名李季学号054131235专业班级05-D 毕业论文（设计）题目：年产10万吨啤酒厂设计 毕业论文（设计）的立题依据 主要内容及要求 进度安排 学生签字： 指导教师签字： 年月日本表一式三份，学生本人、指导教师、学部各一份。
年产10万吨啤酒厂设计 摘要 本文主要是简要的介绍年产10万吨10度淡色啤酒厂的工厂设计。它主要包括啤酒发展，啤酒原料，啤酒厂建设的目的，啤酒厂的规划，啤酒工艺计算、啤酒厂设备的计算和重点设备的计算，啤酒厂的发展状况，啤酒厂资金的估算等方面的内容主要是糖化车间的工艺。本设计一共画二张图：全厂平面布置图、工艺流程图。 本文设计的工厂采用3班倒的工作制，每天工作时间24小时，除去设备清洗和升温时间4小时，实际生产时间按20小时计，本设计设计了一个年产量10万吨啤酒厂主车间平面图及项目工艺方案的设计原则、方法、程序、设备、等等。 关键词：啤酒厂；工厂设计；工艺流程
论文 题目：遗传应用算法 院系：计算机工程系 专业：网络工程 班级学号： 学生姓名： 2014年10月23日
摘要: 遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。本文在简要介绍遗传算法的起源与发展、算法原理的基础上,对算法在优化、拟合与校正、结构分析与图谱解析、变量选择、与其他算法的联用等方面的应用进行了综述。该算法由于无需体系的先验知识,是一种全局最优化方法,能有效地处理复杂的非线性问题,因此有着广阔的应用前景。 关键词: 遗传算法; 化学计量学; 优化 THEORY AND APPL ICATION OF GENETIC AL GORITHM ABSTRACT: Genetic Algo rithm( GA) is a kind of recursive computational procedure based on the simulation of principle principles of evaluati on of living organisms in nature1Based on brief int roduction of the principle ,the beginning and development of the algorithms ,the pape r reviewed its applications in the fields of optimization ,fitting an d calibration,structure analysis and spectra interpretation variable selection ,and it s usage in combination with othersThe application o f GA needs no initiating knowledge of the system ,and therefore is a comprehensive optimization method with extensive application in terms of processing complex nonlinear problems。 KEY WORDS : Genetic Algorithm( GA) Chemometrics Optimization 遗传算法是在模拟自然界生物遗传进化过程中形成的一种自适应优化的概率搜索算法，它于1962年被提出，直到1989年才最终形成基本框架。遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法, 由美国J. H. Ho llad教授提出, 其主要特点是群体搜索策略和群体中个体之间的信息交换。该算法尤其适用于处理传统搜索方法难以解决的复杂和非线性问题, 可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。 顾名思义,遗传算法(Genetic Algorithm ,GA)是模拟自然界生物进化机制的一种算法 ,即遵循适者生存、优胜劣汰的法则 ,也就是寻优过程中有用的保留 ,无用的则去除。在科学和生产实践中表现为 ,在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法 ,即找出一个最优解。这种算法是 1960 年由
一、原始依据（包括设计或论文的工作基础、研究条件、应用环境、工作目 的等。） 工作基础：了解C++的基本概念和语法，熟练使用Visual C++6.0软件。 研究条件：BP神经网络的基本原理以及图像处理的基本常识。 应用环境：基于BP神经网络的图片图像文件中的字符识别。 工作目的：掌握基于Visual C++6.0应用程序的开发。 了解人工智能的基本概念并掌握神经网络算法的基本原理。 掌握Visual C++6.0中的图片处理的基本过程。 二、参考文献 [1]人工智能原理及其应用，王万森，电子工业，2007. [2]VC++深入详解，鑫，电子工业，2006. [3]人工神经网络原理, 马锐，机械工业，2010. [4]Visual C++数字图像处理典型案例详解，晶，机械工业，2012. [5]Application of Image Processing to the Characterization of Nanostructures Manuel F. M. Costa，Reviews on Advanced Materials Science,2004. 三、设计（研究）容和要求（包括设计或研究容、主要指标与技术参数，并根据课题性质对学生提出具体要求。） 1、掌握C++的基本概念和语法。 2、掌握二维神经网络的基本原理。了解BP神经网络的基本概念。 3、完成Visual C++中对于图像的灰度、二值化等预处理。 4、完成基于样本的神经网络的训练以及图像中数字的识别，并对其性能进 行统计和总结，分析其中的不足。
指导教师（签字） 年月日 审题小组组长（签字） 年月日理工大学本科生毕业设计（论文）开题报告
遗传算法 遗传算法（Genetic Algorithm）是基于进化论的原理发展起来的一种广为应用，高效的随机搜索与优化的方法。它从一组随机产生的初始解称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，成为“染色体”是一串符号。这些染色体在每一代中用“适应度”来测量染色体的好坏, 通过选择、交叉、变异运算形成下一代。选择的原则是适应度越高,被选中的概率越大。适应度越低，被淘汰的概率越大。每一代都保持种群大小是常数。经过若干代之后，算法收敛于最好的染色体，它很可能是问题的最优解或次优解。这一系列过程正好体现了生物界优胜劣汰的自然规律。 比如有编号为1到10的特征，现在要选取其中的5个，基于遗传算法的特征选择可以如下这样直观的理解： 下续（表格） 下续……
即设有4个不同的初始特征组合，分别计算判别值，然后取最大的2个组合（[1,2,3,4,9]和[1,3,5,7,8]）进行杂交，即互换部分相异的特征（4和7），得到新的两个特征组合（[1,2,3,7,9]和[1,3,4,5,8]）,然后再计算这两个新的组合的判别值，和原来的放在一起，再从中选择2个具有最大判别值的组合进行杂交。如此循环下去，在某一代的时候就得到了一个最好的特征组合（比如第2代的[1,3,5,7,9]的特征组合）。当然，在实际中每代的个体和杂交的数量是比较大的。 遗传算法的具体的步骤如下：
1.编码：把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。为了减少组合数量，在图像中进行分块（比如5*5大小的块），然后再把每一块看成一个基因进行组合优化的计算。每个解的基因数量是要通过实验确定的。 2.初始群体（population）的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体。N个个体，构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。这个参数N需要根据问题的规模而确定。 3.交换(crossover)：交换（也叫杂交）操作是遗传算法中最主要的遗传操作。由交换概率( P)挑选的每两个父代 c 通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而没什么意义），从而产生新的个体。可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。 4.适应度值(fitness)评估检测：计算交换产生的新个体的适应度。适应度用来度量种群中个体优劣（符合条件的程度）的指标值，这里的适应度就是特征组合的判据的值。这个判据的选取是GA的关键所在。
摘要 随着科学技术和社会信息技术的不断提高，计算机科学的日渐成熟，其强大的功能已为人们深刻认识，它在人类社会的各个领域发挥着越来越重要的作用，给人们的生活带来了极大的便利，成为推动社会发展的首要技术动力。排课是学校教学管理中十分重要、又相当复杂的工作之一。解决好教学工作中的排课问题对整个教学计划的进行，有着十分重要的意义。首先对排课的已有算法作了相关的调查研究，决定采用遗传算法。通过设计实现基于遗传算法的自动排课系统，研究了遗传算法在排课系统中的应用。 关键词：遗传算法、自动排课、Java。
Abstract Along with science technical and community information technical increases continuously, calculator science is gradually mature, its mighty function has behaved deep cognition, and it has entered the human social each realm erupts to flick the more and more important function, bringing our life biggest of convenience. Curriculum arrangement is an important and complicated working in school,so solving the problem is of great importance for teaching programming.Investigated and studied the algorithm existed, determine that adoptgenetic algorithm. ThroughDesign Implementation theAuto CourseArrangementManagement System Base onGenetic Algorithm, researched the application of genetic algorithmin theCourseArrangementManagement System. Keywords: Genetic Algorithm Auto Course Arrangement ManagementJava.
毕业论文 题目粒子群算法及其参数设置专业信息与计算科学 班级计算061 学号3060811007 学生xx 指导教师徐小平 2010年 I
粒子群优化算法及其参数设置 专业：信息与计算科学 学生： xx 指导教师：徐小平 摘要 粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，粒子群优化算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。论文介绍了粒子群优化算法的基本原理，分析了其特点。论文中围绕粒子群优化算法的原理、特点、参数设置与应用等方面进行全面综述，重点利用单因子方差分析方法，分析了粒群优化算法中的惯性权值，加速因子的设置对算法基本性能的影响，给出算法中的经验参数设置。最后对其未来的研究提出了一些建议及研究方向的展望。 关键词：粒子群优化算法；参数；方差分析；最优解 II
Particle swarm optimization algorithm and its parameter set Speciality: Information and Computing Science Student: Ren Kan Advisor: Xu Xiaoping Abstract Particle swarm optimization is an emerging global based on swarm intelligence heuristic search algorithm, particle swarm optimization algorithm competition and collaboration between particles to achieve in complex search space to find the global optimum. It has easy to understand, easy to achieve, the characteristics of strong global search ability, and has never wide field of science and engineering concern, has become the fastest growing one of the intelligent optimization algorithms. This paper introduces the particle swarm optimization basic principles, and analyzes its features. Paper around the particle swarm optimization principles, characteristics, parameters settings and applications to conduct a thorough review, focusing on a single factor analysis of variance, analysis of the particle swarm optimization algorithm in the inertia weight, acceleration factor setting the basic properties of the algorithm the impact of the experience of the algorithm given parameter setting. Finally, its future researched and prospects are proposed. Key word：Particle swarm optimization; Parameter; Variance analysis; Optimal solution III
An ef?cient placement heuristic for three-dimensional rectangular packing Kun He,Wenqi Huang? School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan430074,China a r t i c l e i n f o Available online28April2010 Keywords: Cutting and packing Three-dimension Rectangular packing Container loading Heuristic a b s t r a c t By embodying the spirit of‘‘gold corner,silver side and strawy void’’directly on the candidate packing place such that the searching space is reduced considerably,and by utilizing the characteristic of weakly heterogeneous problems that many items are in the same size,a?t degree algorithm(FDA)is proposed for solving a classical3D rectangular packing problem,container loading problem. Experiments show that FDA works well on the complete set of1500instances proposed by Bischoff, Ratcliff and Davies.Especially for the800dif?cult strongly heterogeneous instances among them,FDA outperforms other algorithms with an average volume utilization of91.91%,which to our knowledge is 0.45%higher than current best result just reported in2010. &2010Elsevier Ltd.All rights reserved. 1.Introduction Cutting and packing problems are representative combinational optimization problems with many important applications in the industry.This paper addresses the problem of loading a subset of three-dimensional(3D)rectangular items into a3D rectangular container,such that the total volume of the packed items is maxi- mized,i.e.the container’s wasted volume is minimized.A layout is called feasible,if each packed item is located orthogonally and completely in the container and there is no overlapping between any two items.This problem is an NP-hard problem,whose1D degradation,the0–1knapsack problem,is still NP-hard. This3D rectangular packing problem is also called the container loading problem,because the most common and important application of this problem is to load rectangular cargoes into containers,vehicles or ships in the transportation industry.There are some additional considerations that would be taken into account in the real world[1,2],among which the orientation constraint and the stability constraint are the most important ones.In our opinion,if there is an ef?cient approach to solve the basic problem that has no additional constraints,then it is not dif?cult to make the approach adapted to problems considering some additional ones. Since the orientation constraint has been widely considered by the researchers,and it has been accepted by the famous BR benchmarks[1],we take the orientation constraint into account that one or two sides of the items may not be used as the height. This situation usually happens when cargoes are boxes full of oil or wine.We do not concern the stability constraint for the following reasons:(1)Stability constraint is not considered as widely as the orientation one and the stability criteria is inconsistent in the literature.In some cases it requires that each item is fully supported,or partially supported with at least a given percentage;in other cases it requires that the gravity center of each item falls over an underlying item or over the bottom of the container.(2)Stability could become a consequence of the high cargo compactness when the container’s volume utilization is high enough.(3)Foam rubber or other stuf?ng could be used to ?ll the small empty spaces left,as what has been done in some freight companies. Many ef?cient algorithms have been proposed for solving this classical3D packing problem.The most prevalent approach is wall building or layering[1,3–9],?rst proposed by George and Robinson in1980[3].In the past thousand years,people usually start packing goods from the bottom and build up the packing in layers,inserting each goods such that it is contiguous with what is already packed.Inspired by these human’s experience,the wall building or layering method usually opens a new layer or wall with a width equals to some item dimension,then each layer is?lled up by a number of horizontal strips,and each strip is packed in a greedy way.Another ef?cient approach widely adopted by the researchers is block arrangement[10–12],?rst proposed by Bortfeldt and Gehring in1998[10],which binds items of the same or similar size into a larger rectangular block to do the tentative packing.By utilizing the block arrangement method,Parren?o proposed an approach that always places a column or layer built by same size items into a maximal space,the largest empty parallelepiped spaces[13,14].Above approaches all utilized the characteristic of the weakly heterogeneous instances that many items are in the same size.Therefore,the solution qualities are in a downtrend when the problems become more Contents lists available at ScienceDirect journal homepage:https://www.doczj.com/doc/51225153.html,/locate/caor Computers&Operations Research 0305-0548/$-see front matter&2010Elsevier Ltd.All rights reserved. doi:10.1016/j.cor.2010.04.015 ?Corresponding author.Tel.:+862787543018;fax:+862787545004. E-mail addresses:brooklet60@https://www.doczj.com/doc/51225153.html,(K.He),wqhuangwh@https://www.doczj.com/doc/51225153.html, (W.Huang). Computers&Operations Research38(2011)227–233
毕业设计（论文）原创性声明和使用授权说明 原创性声明 本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。 作者签名：日期： 指导教师签名：日期： 使用授权说明 本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。 作者签名：日期：
学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 涉密论文按学校规定处理。 作者签名：日期：年月日 导师签名：日期：年月日
实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： 序号遗传学概念遗传算法概念数学概念 1 个体要处理的基本对象、结构也就是可行解 2 群体个体的集合被选定的一组可行解 3 染色体个体的表现形式可行解的编码 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体， 淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解 9 交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组新解 10 交叉概率染色体对应基因段交换的概 率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.90 11 变异染色体水平上基因变化编码的某些元素被改变
【题10】装箱问题 有一个箱子容量为v （正整数，0≤v ≤20000），同时有n 个物品（0
毕业设计（论文） 课题名称基于MATLAB的图像压缩感知 算法的实现 系：电气工程系 专业：电子信息工程 毕业设计（论文）原创性声明和使用授权说明
原创性声明 本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。 作者签名：日期： 指导教师签名：日期： 使用授权说明 本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。 作者签名：日期：
学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 涉密论文按学校规定处理。 作者签名：日期：年月日 导师签名：日期：年月日
北京师范大学珠海分校 本科生毕业论文（设计）开题报告
理论和实践的意义及可行性论述 (包括文献综述) 理论和实践的意义：当前，现代物流是企业继续降低物资消耗、提高劳动生产 率后的第三利润源泉。但我国物流企业的运输成本普遍偏高。其中很重要一个 原因就是对配送车辆运输路线规划不科学。要想降低运输成本，离不开对配送 路线的优化和配送车辆的合理安排。对物流配送车辆行驶路径进行优化，可以降低物流成本，节约运输时间，是提高物流经济效益的有效手段。 可行性论述：配送路径优化问题是典型的优化组合问题，具有很高的计算复杂 性。但遗传算法解决作为一种有效的全局搜索方法具有隐并行性和较强的鲁棒性，在解决非线性的大规模复杂问题上具有很好的适应性，适合于对VPR问 题进行优化求解。标准遗传算法虽然未必每次都能找到最优解，但通过对标准 遗传算法进行改进，完全可以在有限时间内对较复杂的VPR问题计算出次优 解或可行解。因此，用遗传算法来解决物流车辆调度问题还是完全可行的。 文献综述： [1]朱剑英?非经典数学方法[M].武昌：华中科技大学出版社，2001 [2]李敏强，寇纪淞，林丹，李书全?遗传算法的基本理论与应用[M].北京：科 学技术出版社，2002 [3]孙丽丽?物流配送中车辆路径算法分析与研究[D].上海：上海海事大学，2007 [4]盖杉.基于遗传算法的物流配送调度系统 [D].长春：长春理工大学，2007 [5]高运良，基于免疫遗传算法的物流配送V RP 求解[D].武汉：武汉科技大学， 2007 论文撰写过程中拟采取的方法和手段 本论文主要采用遗传算法作为解决物流配送路径优化问题的主要算法。但由于标准遗传算法具有“早熟收敛”的缺陷，有可能使算法陷入局部最优解。论文还将尝试通过把其他算法和遗传算法相结合，来有效控制早熟现象的发生。为了快速得到任意两个配送点之间的最优路线。本论文还拟采用佛洛依德 算法构造配送路线的地理数据库的方式来对路线网络进行预处理。从而减少整 个算法的时间复杂度和空间复杂度。