英语原文共 6 页
模拟退火最优船舶航线
摘要：在本文中，我们提出了一种基于模拟退火的最优船舶确定算法，通过最小化成本函数来确定路线，该成本函数被定义为航次和航行时间的加权和航程舒适度（安全性也被考虑在内）。该成本函数取决于风速及其方向以及波高和方向。构造的算法在开始离散初始路线，然后通过考虑小偏差来优化它通过使用模拟退火技术接受或拒绝。使用微积分变量，我们证明了一个关键定理，它极大地加速了算法的收敛性。对于所描述的构建方法的优点，包括计算和实际实验已经进行了介绍和讨论。
关键词：最优船舶航线 模拟退火 离散力学 微积分变异
1、引言
船舶航线优化与船舶特征和环境因素密切相关。船舶和货物的特性对船舶航线的应用有重要影响[1-3]。路线选择的过程在航行和完善路途中的监视程序之前进行[5]，船舶尺寸，速度能力和货物类型作为重要的因素被考虑在内。该船舶的特征是能够评估不利条件下的损害程度及避免它们的能力[4,5,7]。
众所周知，环境因素对于船舶航行的重要性是指大气和海洋等此类因素可能对船舶的过境状况产生一个改变[1,5]。航行路线的确定是为了分配可用资源（例如POSEIDON系统）以便完全满足某些要求。在船舶航线研究中，要考虑的环境因素包括风，海浪，雾和洋流。尽管所有的环境因素对于航线的选择和监视都很重要，但通常认为风和浪的影响可被优化的路线是最佳航线[7,8]。
风速对船舶性能的影响很难确定。在微风（低于20节）中船舶会失去逆风中的速度并在随后的风速中稍微加速。对于更高的风速，船速在逆风和随后的风浪中都会降低。浪高是影响船舶性能的主要因素性能。一般来说，波浪行为负责船舶运动，减少螺旋桨推力并导致阻力增加从转向修正。船速与波浪高度的关系类似于风。逆向海浪降低船速，随后朝着另一个方向增加船速，同时延迟最大速度的到达。在强海浪的情况下，精确的性能可能难以预测[1,7]。
关于雾，虽然它不直接影响船舶性能，但航行时应尽可能避开雾，以便在安全的条件下保持正常速度行驶。即便为了避开雾航线可能会变长，但由于能见度降低时不能减速，运输时间会更短[4,7]。
通常，洋流不会导致明显的航行问题，但它们可能是路线选择和改变的决定因素。在不考虑以希望通过洋流增加船速的标准来选择最优洋流下的航线时，即不把洋流考虑在内时，最优航线的益处作为重要的考虑因素被评估。关于环境因素对船舶影响的更多细节可以在参考文献中找到[1,5,6]。
在本文中，我们专注于在仅考虑浪高及其方向的情况下研究最优航线问题。针对优化过程，我们构建了一个适当的模拟优化程序退火算法[9,10]。众所周知，模拟退火方法是由Metropolis等人开发的Monte Carlo方法的扩展[11]，用来确定平衡状态在任何给定温度（T）下的原子集合，不久之后模拟退火首先在参考文献中被提出[10]，深入研究已经致力于其性质和应用[2,12,13]。
该技术由于能适当解决大规模的优化问题在当时也引起了极大的关注。当理想的全球极致条件隐藏在许多较贫穷的极端地方时它可以给出解决方案[14,15]。令人惊讶的是，尽管其他实用的方法也为此目的而开发，算法在模拟退火方法中的实现相对的更为简单。这种操作方法的基本工具与热力学过程类似，特别是液体的冷冻和结晶，或金属的缓慢冷却和在失去热流动性时的退火。对于缓慢冷却的系统来说，它的自然特性能够找到最小的能量状态[10,11]。
在目前的工作中，我们利用了这种物理属性系统来找到在环境因素尤其是风的影响下的最佳航线。此外，我们充分利用离散的配方初始船舶离散化的变分力学路线，如下所述。
本文的其余部分概况如下。首先，第2节概述了问题的建立过程同时简要描述了基于离散变分法的方法的主要特征。在第3节中，一个关键定理被给予证明，该定理提供了一个在船舶航行中有效寻找最优航线的解决方法。第4节解释和分析了在这项工作中构建的模拟退火算法的操作步骤。第5节演绎了该算法的仿真实验和实际测试，并呈现出结果给予讨论。最后，在第6节主要讨论总结了本研究中提出的结论。
2、简要概述
假设船的初始路线（见图1）用平滑曲线表示，其中参数s是从一些固定点A（即船舶路线的起始点）测量的弧长。在问题中将船舶初始路线的切线向量定义为
（1）
（参见参考文献[16]），其中是船的速度（另见[22,23]）。
假设移动的船舶受到了（通过高度和方向呈现的）波浪的矢量和（由速度和方向呈现的）风的矢量影响。
图1
（从A点到B点的路线。是路线的参数，，分别是波浪矢量和风矢量。）
在上述情况下，我们定义在两点之间的每条可能路线的成本函数（标量）包括航程的加权组合时间和航行的安全（或舒适度）。 路线总成本函数S记为
（2）
其中T是总航行时间，C是代表航行的安全（舒适度）的标量参数。权重参数a可以由用户根据问题中的具体需求进行调整。 值得注意的是，当，那么唯一可以优化的变量是航程时间；当，只有船员舒适度C这一变量可以被优化。
其中标量C按照以下方式通过在路径中的线积分进行计算（直到线性近似）[6,7]：
（3）
其中和分别表征船舶对风（风矢量）和波浪（波浪矢量）的响应参数。总航程时间T的计算稍许复杂，因为风和波浪都可以改变船的速度（见第3节）。通常情况下，对于船速的规模我们可以写作
（4）
其中u是无风时的船速，F是表征船舶的特性，风，波浪和船舶移动方向的函数。为了简化，假设F = 0。
2.1离散变分原理
近来，在机械问题的变异离散化发展方面，无论是基础理论上还是最优化挑战性问题的应用，都已经取得了进展[17-20]。以此为目的，一种基于汉密尔顿原理的离散化变分的方法积分器已经开发出来，它强调了整个机制的必要性，从粒子力学到连续介质力学[17,18]。不仅如此，拉格朗日-达朗贝尔原理的离散化已经形成并投入使用，特别是在外部耗散力量存在的情况下[18,19]。
除了在构造算法中保持基本变分结构，它在算法层面也保留了力学的结构属性（如守恒定律）。这避免了许多在某些现有集成商中出现的问题，例如虚假耗散，为了消除它可能需要非常昂贵的标准技术运行[18]。
随着离散化的机械和几何之间联系的适当发展，人们能够使用几何参考文献[20]和参考文献[17-19]中描述的方法。
在目前工作的第一步，我们构建舒适函数C，随后用最小化技术处理它，作为变异演算的基本问题。它类似于汉密尔顿原理的问题，初定义拉格朗（对于特定的机械正在考虑的系统），形成行为积分状态，从而构建欧拉 - 拉格朗日方程。
针对船舶航线问题，行动积分扮演方程（2）中的成本函数或方程（3）中的舒适程度，我们要求
（5）
对于与路线弧s（A和B是固定的路线终点）相关的所有变量都有上式成立。人们可以模仿程序和利用船舶航行离散变分力学的优点解决路由问题如下所示。
3、初始船舶航线的离散化
我们首先考虑离散情况，即航线由边线，k = 0,1，...... M的折线近似代替（见图1）。每个线段的长度是
，k=0,1,...,M-1, （6）
在每一边线上路线的切向量是
，k=0,1,...,M-1, （7）
然后，方程式（2）的成本函数的自变量对应于路线可以如下表示
（8）
在下面的等式
（9）
是在点和时间上计算的
（10）
随后，方程（2）中的成本函数写作
（11）
考虑形式下的的微小变化，其中是一个很小的正数和是与水平轴成角度的方向上的单位向量。新的路线有成本函数，因此我们有
或者
（12）
为了得出后面的式子我们假设
（13）
在我们的模拟退火方法中，为了定义优化的路线，方程（12）中的表达式进入麦克斯韦玻尔兹曼概率分布，如下面第4节中所述。
3.1模拟退火搜索
我们认为图1所示的初始路线是分开进入几个不同的路段，其路段数量取决于风和波浪预测情况。通过这种方式，任何船舶航线都可由一组航路点表示。那么初始路线的总成本可以被随意估算。因此，在任何迭代步骤，路线的每个航路点都按照以基本长度连接出发点和到达点的线（该部分的终点）垂直移动。这个基本长度由风的分辨率和波浪的预测指定。
每个因素对总成本都有积极或消极的贡献，即使它可能对总成本的贡献是积极的，也会被接受，然而，概率取决于算法的温度参数，这与物理系统的温度扮演着相同的角色。
在模拟退火方法中，概率分布是由所谓的玻尔兹曼概率分布描述
（14）
（数量k即玻尔兹曼常数，是将温度与能量联系起来的自然常数。后者的物理意义是对于一个温度T下处于热平衡的系统，它的能量状态以自身的能量E按概率分布。即使在低温下，尽管可能性非常小，物理系统也有可能占据高能量状态。相应地，系统有可能退出当地能源最低状态来寻找更好，更全球化的最小化能源。 换句话说，系统有时会去上坡和下坡，但温度越低，任何上坡过渡的可能性越少。
最初，算法的温度参数很高，但随着算法的进行，温度会降低到零。 此时，只有消极贡献的行为被接受了。该方法称为模拟退火，用来防止算法被困在局部最小值，通过上述机制，它可以进一步发现 全局最小值（或最小值）。
值得注意的是，没有系统的方法来决定计算出的路线是否为最佳路线。然而在大多数情况下航行时间非常关键，因此最佳路线近似于
最短的初始路线。在我们的实验中（迭代程序被锁定在本地最小）我们观察到的唯一此类情况，出现在出发点和到达点之间的线非常接近一个小障碍的情况下（见图2）。 在大多数此类情况下，该方法可以不绕过障碍使得算法终止。原因是只有路线的连续变换被允许在算法的任何步骤执行。为了克服这种困难，我们会考虑几条初始路线，在下一节中解释。
3.2 加速搜索机制的收敛
为了加速搜索机制的收敛，事先知道哪个方向的成本函数对初始路径的变换更敏感是很有必要的。幸运的是，人们可以证明，在最大限度地降低船舶航线任何部分的成本函数时，产生的运动方向与波传播方向平行或反平行。
图2
（如果通过初始路线的连续变换不能产生最佳路线，则可以将解决方案锁定在局部最小值。）
只考虑波的贡献，等式（8）中的成本函数的证明如下。
在上述条件下，方程（8）的成本函数给出如下
（15）
我们假设路线的变化接近点，从而形成一个新切线向量
（16）
（是狄拉克函数或函数）其中在3.1节中已经定义了，。成本函数的变化对应于
（17）
也被写作
（18）
或者
（19）
其中，即在的路线点经计算的向量。
从等式（19）中可以明显看出，如果向量和之间的角度为0或，成本函数会出现的变化最大。 因此，加速度的收敛只有通过在上述方向上选择初始路线的变化才能实现。在我们的实验中，向量的方向始终与波的方向相同，因此可接受的初始路线的变化是与波场方向平行或反平行的那些。
4 关于新算法的描述
4.1 初始路线的选择及其表示方式
在使用算法开始优化过程之前，我们必须提供一条（或几条）初始路线。在这种情况下起点和终点之间没有障碍，初始路线只是连接这两点的线。而且，如果在开始和结束的点之间存在一个障碍，那么将会有两个可能的初始路线，每个路线都从不同的方向绕过障碍。从最短的初始路线（即有所有绕过障碍可能性的路线）开始是一个很好的做法，也已经优化了航行时间。显然在这种情况下，如果点B属于在点A和C之间的最短路径，那么点B和C之间的最短路径是点A和C之间最短路径的一部分[24,23]。
这在参考文献[7]中得到证实，绕过障碍物的最短路径与障碍物的凸向相切。因此解决最短路径的问题降低到了计算从这个接触点到与终点相切的最短路径。
如果有超过一个障碍，以此类推，我们将会得到条初始路径，其中n是起点和终点之间障碍物的数量。此算法必须检查所有初始路线以确定最佳解决方案，即便进行这些检查，会使计算时间显著增加。
一旦计算出初始路线，路线点的数量也必须被随之确定，用来呈现该初始路线。从一种观点来看，人们认为这个数量的确定与确定用于拟合给定平滑曲线的多项式次数起到了相同的作用。在后一种情况下，增加多项式次数会使得更好的拟合，但却不完全是这种情况，原因如下
（1）第一个原因是，增加路线点的数量，计算时间也会增加（在实际的船舶旅行中船员的必要行为也增加了）。
（2）第二个原因涉及预测数据的时期。如果船的速度是u，那么在时间间隔中环境漂移的数据未知，因此在空间间隔上。
（3）最后一个原因与用来预测环境数据的模型细节有关，更准确地说是用的网格。如果是网格点间距，那么船舶的时间间隔会在恒定的环境参数下变化。
用不同数量的路线点进行实验，结果表明最佳的路线点距离应该接近。因此不断调整路点数是一个很好的方法。如果两个连续的路点间距大于选定的，则在它们之间添加另一个路点。如果两个连续的路点间距接近于特殊距离，则将两个路点合并为一个。在本文（见下文第5节）进行和呈现的实验中，我们选定
（20）
4.2 算法阶段
最优路线的计算步骤如下：
（1）选定
资料编号：[4973]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
