军事物流中的NP问题及智能计算方法运用

所属栏目:物流论文 论文作者:/
论文摘要

  现代高技术战争条件下,作战部队作战半径大、突击速度快,作战装备数量多、技术含量高,作战物资需求量大、时效性强,战场前、后方界限模糊,后勤保障系统是敌方空中力量和地面武装力量的重点打击对象,战争经济成本空前提高,战争形态和样式发生了根本性的变化。

  随着武器装备的发展,高技术条件下的局部战争呈现出高机动性、高消耗的特点,战前和战中部队的大规模机动成为赢得战争主动权,乃至影响战争胜负的重要因素,这就给军用物资保障工作提出了更高的要求。

  1、 军事物流中的 NP 问题

  战场的空间扩展,战役规模扩大,战役持续时间缩短,节奏加快,战役将在全纵深紧张激烈地进行,敌我态势交错,情况复杂多变,有利的歼敌时机稍纵即逝,从而导致选择和创造战机的要求提高。然而这些都是随着问题规模的增大,计算量常常急剧增大,甚至发生所谓待搜索空间的“组合爆炸”,造成问题难解。

  军事物流中运载量大,要求速度快、效率高,尤其是通用军用物资,比如弹药占有着重要的位置,起着重要的作用,无论从数量上还是质量上都有着较高的要求,是军用物资保障工作的一个重要内容。要在战场上占有绝对优势,在战场上实现及时、准确的军用物资保障目标,就必须对军用物资的保障进行研究,就必须为军用物资保障提供先进的、适合于现代作战的理论指导、保障方法、保障模式,使之战之能用,用之能胜。提高通用军用物资输送的效率和效益对我军打赢未来战争具有十分重要的意义。

  在作战中每个作战指挥机关都要考虑在这复杂多变的战场环境中,如何以最高的效率、最快的速度、最准确的数量将所需军用物资送达每一个战斗单元。在此问题中就涉及了军用仓库放在哪里才是最安全、最方便、最满足联结前方后方要求。每个战斗单元、战役单元的各种军用物资消耗的可能需求量是多少,以便更加准确地配送物资; 如果在已经确定需求量的情况下,怎么对物资进行装载上车,怎样才能以最大的效率充分利用有限的车辆、才能尽量减少出去车数以减少被发现的概率; 在物资配送过程中,能否严格按照上级的指示不早于最早允许时间、不迟于最晚允许时间,这样方可避免因过早而暴露目标及作战意图、过晚则延误战机。所有这些问题都是在战场上急需解决的问题。

  军事物流系统中的若干问题多属于 NP 问题或是 NP -hard 问题,是一类随着问题规模的增加而出现计算量爆炸性增长的问题。如军事物流配送中心选址问题,军用物资的装载问题,军用物资的配送问题等都是 NP 问题。军事物流配送中心选址问题: 军事物流配送中心( 后勤基地和补给站) 是军事物流系统的中心枢纽,决定着军事物流体系能否有效地发挥整体功能。选择军事物流配送中心的位置,以费用低、后勤与装备保障效益高为目标,以运输方便、投资少、有利于快速、高效调运军事物资为基本原则。高效能的军事物流配送中心能够保证物流系统的高效和平衡发展,产生巨大的军事和经济效益。

  军用物资装载问题根据集装箱数量的有限和无限划分成两类: 集装箱数量无限,物资必须全部装完,使装箱数量最少; 二是集装箱数量有限,为了提高集装箱的装载能力,要求被装载盒子的总体积达到最大,使空间利用率最高。在军事物资配送过程中,应用到的是第一种情况,即要用最少的车辆将所需要的所有物资送往各个战术需求点。装载问题求解的核心是针对该问题的算法,算法是求解一个问题类的无二义性的有穷过程,就是执行的一步一步动作的集合,每步动作需要有限的存储单元和有限的操作时间。

  军用物资配送路径优化问题一般可以这样描述: 从某军事物流配送中心用多辆配送车辆向多个单位运送物资。每个单位的位置和货物需求量一定,每辆车的载重量一定,其一次配送的最大行驶距离一定,要求合理安排车辆配送路线,使目标函数得到最优。

  在现代战争中战机稍纵即逝,已有的优化算法耗时长,求解精度不高,已不足以胜任指挥自动化系统中的任务。如何为指挥自动化系统中的以上诸多问题以最少的时间获取最优的解、提供最具有参考价值的方案已成为了一个刻不容缓的问题,一种新的更加快捷的最优化方法也随之产生: 智能计算。

  2、 智能计算方法

  智能计算是以生物进化的观点认识和模拟智能。按照这一观点,智能是在生物的遗传、变异、生长以及外部环境的自然选择中产生的。在用进废退、优胜劣汰的过程中,适应度高的( 头脑) 结构被保存下来,智能水平也随之提高。因此说智能计算就是基于结构演化的智能。智能计算的主要方法有人工神经网络、遗传算法、粒子群算法、蚁群算法、模拟退火等等。这些方法具有以下共同的要素: 自适应的结构、随机产生的或指定的初始状态、适应度的评测函数、修改结构的操作、系统状态存储器、终止计算的条件、指示结果的方法、控制过程的参数。智能计算的这些方法具有自学习、自组织、自适应的特征和简单、通用、鲁棒性强、适于并行处理的优点,在并行搜索、联想记忆、模式识别、知识自动获取等方面得到了广泛的应用。

  2. 1 遗传算法

  遗传算法是一种建立在达尔文生物进化论和孟德尔基因遗传学基础上的算法。生物的进化是一个奇妙的优化过程,它通过选择淘汰,突然变异,基因遗传等规律产生适应环境变化的优良物种。遗传算法模拟了这一生物进化的过程,遗传算法的操作对象是解空间中的数型串。首先从串结构空间中生成初始种群,从初始种群出发,采用恰当的选择算子在当前种群中选择若干较优良的个体,使用杂交和变异算子来产生下一代种群。再用适应度函数筛选出更好的个体群体作为下一次遗传和变异的父体。如此模仿生命的进化一代代演化下去,直到满足期望的终止条件为止。

  2. 2 蚁群算法

  蚁群算法是在 90 年代初提出来的一类新的仿生算法,其特点是模拟自然界中蚂蚁的群体行为。科学家们发现,蚁群总是能够发现从蚁巢到食物源的最短路径。经研究发现,蚂蚁在行走过的路上留下一种挥发性的激素,蚂蚁就是通过这种激素进行信息交流,它们趋向于走激素积累较多的路径。

  找到最短路径的蚂蚁总是最先返回巢穴,从而在路上留下了较多的激素。因最短路上积累了较多的激素,选择该路径的蚂蚁就会越来越多,直到最后所有的蚂蚁都会趋向于选择这条最短路径。与其它优化算法相比,蚁群算法具有正反馈、分布式计算以及贪婪的启发式搜索等主要特点,正反馈过程使得该算法能够发现较好解; 分布式计算使得该算法易于并行实现,更快得到较好解; 与启发式算法相结合,使得该算法易于发现较好解,这些特点为更好求解复杂问题提供了可能。

  2. 3 粒子群算法

  粒子群算法是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发。粒子群算法与其它进化类算法相类似,也采用“群体”与“进化”的概念,同样也是依据个体( 粒子) 的适应度值大小进行操作。所不同的是,粒子群算法不像其它进化算法那样对于个体使用进化算子,而是将每个个体看作是在 n 维搜索空间中的一个没有重量和体积的粒子,并在搜索空间中以一定的速度飞行。该飞行速度由个体的飞行经验和群体的飞行经验进行动态调整。

  2. 4 神经网络

  人工神经网络是对人脑最简单的一种抽象和模拟,是对人的大脑系统一定特性的描述。简单地讲,它是一个数学模型,可以用电子线路来实现或用计算机来模拟人的自然智能。其中 BP 神经网络是目前应用最为广泛的神经网络模型之一。BP 神经网络通常是指基于误差反向传播算法的多层前向神经网络,采用由导师的训练方式。BP 网络的学习训练过程由两部分组成,即网络输入信号正向传播和误差信号反向传播,按有导师学习方式进行训练。

  3、 几种智能计算的设计思想比较及其与军事物流的有机结合

  3. 1 几种智能计算的设计思想比较

  几种智能计算方法的共同点在于它们都是受大自然中的生物的启发,从有灵性的动物中得出规律,对其进行计算机程序模拟,并将其运用于各种优化之中,得到了良好的应用效果。它们都是基于迭代的算法,且初始解都是随机产生的。

  在每次迭代中都以某种规则随机产生新的解,这种随机不是完全的随机,是基于规则下的趋向较好方向发展的随机,并对其进行评价,也就是所说的评价函数,进入下一个迭代过程后,以对个体的评价引导它们进化的方式,且它们都不是保证一定找到最优解的。它们都利用计算机程序的特点,即为简单的加减乘除及判断、循环、选择的简单语句且运算快,但需要人把问题都化为这些语句,这也为编程的构思,以此来模拟大自然的各种灵性的现象。

  各种算法有各自的算法思想及理念,它们程序运算的组织机理有着本质的不同。遗传算法首先要对问题进行编码,也就是问题的因素集能够以一种编码形式表达出来,且该编码形式所包括的解空间要等于或是在不方便的时候大于实际问题的解空间; 每一个编码必须能够有一个决定它的优良中差的尺度,也就是用适应值函数来判断它; 它们的编码要能够进行交叉与变异。而神经网络则是对人脑的一种模拟,它说到最终的数值问题就是通过对权值矩阵及阈值矩阵的操作,使目标函数趋向理想状态。粒子群算法及蚁群算法则与以上的几种算法在理念上就有所不同,它们是利用没有智能性的个体组成了智能性的群体,它们能过某种个体之间的信息通讯方式来控制进化。群体中每个个体留下对群体的修正信息,而每个个体则依群体信息进行对自身的进化。

  3. 2 智能计算方法与军事物流的有机结合

  智能优化算法作为一种模拟自然界中各个生物行为的算法,通过个体及群体行为体现了智能性,军事物流系统中的若干问题同样作为自然界中的一种组织行为,有其智能的规律性,从哲学层面上考虑,将智能优化算法应用于军事物流系统之中,并将它们进行有机的结合也是可行的。

  除以上所提及的仿生类算法之外,还有像模拟退火算法、鱼群算法、禁忌搜索算法等等诸多算法。智能优化算法方兴未艾,以后的研究工作还很多。作为一种先进的优化算法,可以在我军指挥自动化系统中的决策、评估、优化等等方面发挥不可估量的作用,同时因其算法思想有着本质的不同,所以它们应用的领域有着很大的不同,只有将各种算法针对不同的应用领域进行深入研究,并运用到指挥自动化系统中,才能使我军指挥自动化水平有更大的突破和成绩。

  军事物流系统中的若干问题多属于 NP 问题或是 NP -hard 问题,是一类随着问题规模的增加而出现计算量爆炸性增长的问题。针对此类问题,在现有的理论研究中,智能计算是一种有效的求解最优或是次优解的方法。智能计算方法是一种带有一定方向性的随机搜索方法,虽然难以给出最为严格的数学证明,难以计算每个程序中包括所有算子的时间复杂度,但一定程度上能够快速、准确地搜索到最优解或次优解,对于工程应用而言是行之有效的,同时对于在一定战术背景下的军事问题而言,也是可行的。然而对于军事问题中的各个具体问题,有着不同的性质,同时各种智能计算也有着不同的算法思想和理念,如模拟遗传学和进化论中的基因排序的遗传算法更加适合解决整数规划、组合优化等类型的问题,模拟鸟类捕食行为的粒子群算法则是更加适合于求解一些连续型的函数优化,模拟蚂蚁行走路径的蚁群算法则是更加擅长于求解类 TSP 问题,模拟人的大脑的神经网络算法则是更加擅长于解决一类评估、预测等问题。充分发挥它们的各自优势,并将它们应用于军事物流系统之中是有益的。但军事问题作为一种最高形式的斗争问题,有着固有的复杂性,随着问题的复杂性增加,附加条件的增多,单一的算法求解效率明显降低,针对此问题,可以将一种算法的思想作为主导求解算法,同时加入了其他智能计算的方法作为改进的算子,形成了多个混合智能计算方法,增强了算法的可行性,快速性。

  把智能计算应用到军事物流中的若干问题中,找出并验证其可行性、有效性,验证对于典型的 NP 问题的计算效果,所提供的方案是否更加合理可靠。如果可行,则将先进的智能计算方法应用于我军现代的指挥自动化中是可行的,将有益于提高我军精确化后勤保障的理论研究。

'); })();