资源下载地址：https://download.csdn.net/download/sheziqiong/85734241
资源下载地址：https://download.csdn.net/download/sheziqiong/85734241

港口调度问题

摘 要

内容摘要：为港口安排货轮的入泊顺序，按照规定的入泊实际入泊后，有两个泊位，有两个起吊机与泊位并不绑定，为起吊机分配对在泊位轮船所带货物的起吊顺序，为小车安排运送货物的顺序（本实验中弱化了），使得总计的全部时间最短。

使用的方法：贪心算法，遗传算法

结果：贪心算法一：结果 419，对应的解：货轮的顺序：C2 C1 C3 C4，货物顺序：P25 P26 P21 P22 P14 P24 P11 P12 P23 P15 P13 P31 P34 P33 P35 P41 P42 P43 P32；贪心算法二：结果 420，对应的解：货轮的顺序：C2 C1 C3 C4，货物顺序：P25 P26 P21 P22 P14 P24 P11 P12 P23 P15 P13 P31 P34 P33 P35 P41 P42 P43 P32；遗传算法：结果 419，对应的解：货轮的顺序 C2 C1 C4 C3 货物顺序： P42 P41 P24 P13 P23 P43 P33 P21 P32 P12 P11 P25 P35 P15 P26 P34 P14 P31 P22

更改实验测试用例后得到的实验结果：GA:结果 233，对应的解：货轮的顺序：C2 C1 C3 C4，货物顺序：P35 P26 P22 P41 P11 P14 P32 P12 P24 P13 P42 P33 P25 P31 P15 P23 P10 P34 P21

贪心算法一：结果：253，对应的解：货轮的顺序：C2 C1 C3 C4，货物顺序：P25 P26 P21 P22 P14 P24 P11 P12 P23 P15 P13 P31 P34 P33 P35 P41 P42 P43 P32；贪心算法二：结果:303,对应的解对应的解：货轮的顺序：C2 C1 C3 C4，货物顺序：P25 P26 P21 P22 P14 P24 P11 P12 P23 P15 P13 P31 P34 P33 P35 P41 P42 P43 P32；

关键词: 贪心，遗传算法，安排调度顺序;
目录
[港口调度问题] 1
1 引言 1
2 算法设计 2
2.1 三个算法所共用到的设计（对于时间的计算）： 2
2.2 贪心算法1： 2
2.3 贪心算法2： 2
2.4 元启发算法（GA）： 3
3 实验 3
3.1 实验设置 3
3.2 实验结果 [可包含参数实验、对比实验等，可以组织在不同的小节中] 4
4 总结 4

三、实验

3.1 实验设置

实验环境：采用 C++ 程序语言，CPU:CORE i7-4720HQ 2.59GHz，4 内核，8 逻辑处理器，内存：8.0GB DDR3

GA 算法的运行时间：179.35s

贪心算法 1：19ms

贪心算法 2：5ms

更改测试用例后的：

GA 算法的运行时间:146s

贪心算法 1：0.03ms

贪心算法 2：0.03ms

3.2 实验结果 [可包含参数实验、对比实验等，可以组织在不同的小节中]

参数实验

对于未指定的参数默认 交叉概率=0.9 变异概率=0.05 种群的大小 10 迭代次数 5500

对于 GA 的交叉概率对结果和收敛速度及结果的影响实验

对于 GA 的变异概率对结果和收敛速度及结果的影响实验

对于 GA 的种群大小对结果和收敛速度的及结果影响实验

分析：遗传概率和变异概率不一定越大越好，当其较大时，可能出现的情况，陷入局部最优，使 得收敛速度变慢，种群越大收敛速度越快，这样每个个体的交配对象可选则面广，使得产生最优解的概 率增加，但是过大的种群会成倍的增加计算量。

四、总结

本文中采用的是 GA，对其的改进可以从多个方面，如交叉操作，变异操作，优选策略等。贪心算法对于 NP 问题的设计需要比较复杂的全局考虑，并且得到的结果不一定就是全局最优。

对于货轮所花费总时间的计算的时间复杂度比较高，如若用到生产生活中会比较慢，这里可以用更加精细的设计，对于遗传算法的改进，可以参考 SA 让其的种群交叉，变异的概率随着迭代的代数增加而降低，使得对解的收敛效果增加，但是也要注意不要使其陷入局部最优，可以再找到一个局部最优之后进一步的改变交叉变异概率。

在更改测试用例后更加贴近真实性，本文的两个贪心算法都距离 GA 给出来的最优解有很大的差距，都很差，对于贪心算法一的对小车的运输顺序的决策可以改进，对于贪心算法二较为严重的问题是，如果第一艘船已就剩一个了，但是这时候来了第二艘船，它的所有的货物都比第一艘船的最后一个货物所用时间小，那么第一艘船要一直等到第二艘船运完再走，十分浪费时间，这种决策方法更加适合那种数据比较集中的情况，每艘船的情况相差不多的情况。

资源下载地址：https://download.csdn.net/download/sheziqiong/85734241
资源下载地址：https://download.csdn.net/download/sheziqiong/85734241