基于改进遗传算法的舰船物资转运方案研究

14522009,30(6)计算机工程与设计Computer Engineering and Design0引言舰船路径规划对于舰船实现自动化航行和航线优化具有重要的意义，要求在复杂的海上环境中，根据已知的地理信息数据，寻找出一条从起点到终点的最安全且航程最短的航线。

传统的图搜索法、栅格法、人工势场法等都有一定局限性[1]。

由于遗传算法在解决非线性问题上具有良好的适用性，已成为路径规划中使用较多的一种方法，被广泛的应用于机器人、飞行器的路径规划[1-3]。

但是标准的遗传算法本身也存在着一些缺陷，如早熟、局部最优解、占据较大的存储空间和运算时间，并且在实际应用中缺乏对特定知识的利用[2]，保证不了对路径规划的计算效率和可靠性要求。

为了提高路径规划问题的求解质量和求解效率，本文提出了一种用于舰船路径规划的改进遗传算法，使用简单的编码方式，有效降低了遗传算法的搜索空间；根据舰船航行的特点设计了交叉算子、插入算子、删除算子和平滑算子。

最后通过计算机仿真证明了改进后的遗传算法对于搜索效率和收敛速度都有显著的提高，并能保证收敛到全局最优解，克服了标准遗传算法的缺点。

1应用于舰船路径规划的改进遗传算法在本文的舰船路径规划中，目标是在一幅障碍物分布已知的二维地图上寻找一条最优路径使到达目标点距离最短，同时尽可能地最大化与障碍物的距离。

为了简化讨论，舰船被作为一个质点来考虑，而障碍物的边界向外扩张舰船的最大安全距离。

1.1路径编码编码长度是影响遗传算法收敛速度的重要因素之一，因此应当尽量使用简单的遗传编码[4]。

舰船航行路径可以看作由起点和终点及一系列中间点组成的路径，其结构为(x0，y0)→(x1，y1)…(xi，y i)→(xn，y n)式中：(x0，y0)——起点，(xn，y n)——终点，(xi，y i)——起点和终点之间的一系列中间点，称之为转向点，i=1，2，…，n人工智能唐琳，蔡德荣，黄猛：基于改进遗传算法的舰船路径规划2009,30(6)1453平分成x 1，x 2，…，x n-1，则路径点可以简化为一维的y 轴坐标编码形式，表示为y 1，y 2，…，y n ，在遗传操作中，只需要对y 轴坐标进行优化即可，可以大大的提高算法的速度。

ｆ ／ ｌ有 车 辆ｋ 从 点ｉ 行 驶 到 点ｉ
ｏ 否 则
应急 资源调 度模 型如下 ： 目标 函数 ：
ｍ ｉ ｎ ∑ ∑ ∑Ｃ ， ｊ Ｘ ¨ ｋ
ｉ ｌ ｔ Ｉ
（ ３ ） （ ４ ）
科技・ 探索・ 争Ｉ 乌
Ｓ ｃ 科 ｉ ｅ ｎ ｃ ｅ ＆ 技 Ｔ ｅ ｃ ｈ 视 ｎ ｏ ｌ ｏ ｇ ｙ 界 Ｖ ｉ ｓ ｉ ｏ ｎ
２ ． ２ 问题 情 景 描 述 Ｓ ｔ ｅ ｐ １ ： 设定初始参数。主要是遗传迭代次数 、 初始种群大小 、 交叉 假设 中国西南 部某地 发生 了一定强度的地震内． 震后造 成交通线路 阻断 ． 围 绕 震 中 形 成 了 几个 受 灾 较 为 Ｓ ｔ ｅ ｐ ２ ： 随机产生初始种群 ． 利用适应度函数计 算种群适 应度 ：
严 重的区域 ， 区域 内交通能力恢 复迅速 ， 区域与 区域之 间处 于半 隔离 Ｓ ｔ ｅ ｐ ３ ：根据适应度按轮 盘赌方 法和最佳个体 复制选择下 一代染 状 态。 处于各受灾 区域的政府救 助力量迅速组织人员和工具分别进行 色体 ： 难 民的搜寻和治疗 ， 并以最快 的速 度恢复通信 能力 ． 与上 一级 政府组 ｓ ｔ ｅ ｐ ４ ： 根据交叉概率 ， 对染色体（ 候 选解） 进行顺 序交 叉操作 ； 织取得联系并发出求救 信息。 上 级地震 灾害救助领导组织汇集各 区域 Ｓ ｔ ｅ ｐ ５ ： 根 据变异概 率 ， 对染 色体 （ 候选解 ） 进行 变异 操作 ｆ 二 元 变 需求， 利用 空 中设 备（ 直 升机） 将救灾 物资空投 至各 区域 ． 其 中包括医 异 ） ： 药、 食物 、 饮用水 、 救灾车辆及 工具等具体物 资 ． 另各救灾 区域内的救 Ｓ ｔ ｅ ｐ ６ ： 产 生新 的种 群 ， 利用 适应度 函数计算 种群适应 度 ． 记 录新 灾应急小组抓紧组织收集可利用 的机动性运输 工具 ． 在各区域 内形成 种 群 中 的最 佳 个 体 ： 配送中心 ， 根据各需求 点需求进行救灾物 资配送和伤员运输 Ｓ ｔ ｅ ｐ ７ ： 判断是否满 足遗传算 法迭代次数 ． 若满 足则停止并输 出优 ２ ． ３ 模 型 的 建 立 化结果 ， 否则转 Ｓ ｔ ｅ ｐ ２对新种群继续操作。 ２ ＿ ３ ． １ 模 型的假设 条件 ２ ． ４ ． ２ 案例分析 假设一 ： 应 急资源调度 中心与各物 资需求 点 、 各物 资需求点之 间 本 文采用 Ｍａ ｔ ｌ ａ ｂ编程 ． 对有 ３ Ｏ个节点 、 ５ Ｏ个 节点和 ７ ５个节点 ＝ 的运输距离已知 ． 可以作为常数 种情况进行试验分析 假设二 ： 受 灾 地 点 及 各 应 急 资 源 调度 中 心 根 据 其 地 理 位 置 及 交 通 （ １ ） ３ ｏ节 点 时 便利情况完成最 优区域划分 ． 形成局部地震救 灾单元 ． 单 元区域 内可 各算法参数设置为 ： 以 以最快速度进行物资分配及救灾响应 各单元 地震灾 区资源运输费 Ｇ Ａ迭代步数为 ２ ０ ０ ０ ， 种群规模 为 １ ０ ０ ， 交叉 概率为 Ｏ ． ８ ． 变异概率 用有限可加 ， 总和为地震总灾区资源调度 费用 为０ ． ２： 假设三 ： 救灾物资运送车辆所 在停车场 与应 急物资调度 中心之 间 Ｇ Ａ — ｐ ｌ ｕ ｓ 迭代 步数为 ２ ０ ０ ０ ． 种群规 模为 １ ０ ０ ． 交叉 概率 为 ０ ． ８ ． 变 的 距 离 可 以忽 略 不 计 异概率为 ０ ． ２ ・ 假设 四： 所 有的需求点 之间都可 以相互 通行 ． 即此路 径网络是完 （ ２ ） ５ ０节点 时 全路网 。 各算法参数设 置为 ： 假设五 ： 所有的受灾地 点的资源需求 ． 在时间 和数 量方面都能够 Ｇ Ａ迭代步数为 ３ ０ ０ ０ ． 种群规模为 １ ５ ０ ． 交叉 概率为 ０ ＿ ８ ． 变异概率 得到满足 为Ｏ ． ２： 假设六 ： 物资从调运车辆上卸载的时间忽略 ． 不予计算 Ｇ Ａ — ｐ ｌ ｕ ｓ 迭 代步数 为 ３ ０ ０ ０ ． 种群 规模 为 １ ５ ０ ， 交 叉概率 为 Ｏ ． ８ ， 变 ２ ＿ ３ ． ２ 问题的数学模型描述 异概率为 ０ ． ２ 应急 资源车辆调度 问题的数学模型可以概述如下 ： 对于单一地震 （ ３ ） ７ ５节 点 时 灾害救助单元 ， 把各物资需求节点 和应急 资源调度中心组成一个 图 Ｇ 各算法参数设 置为 ： （ ， ，其 中 是 图中所有 节点的集合 ， Ｖ ｏ ∈Ｖ是应 急资源调度 中心 ． Ｇ Ａ迭代步数为 ７ ０ ０ ０ ， 种群规模为 ２ ０ ０ ， 交叉概率为 Ｏ ． ８ ， 变异概 率 其余节 点为物 资需求节 点 ； Ｅ为 图中所有边 的集合 ∈Ｅ为节点 ｉ ， 为０ ． ２ ： 之间的边 ， 图 Ｇ为无向图 ， 即边 ｅ 是无方 向的 。有 ｎ个受灾地 向救 灾 Ｇ Ａ — ｐ ｌ ｕ ｓ 迭 代步数 为 ７ ０ ０ ０ ， 种群 规模 为 ２ ０ ０ ， 交 叉概 率为 Ｏ ． ８ ， 变 指挥 中心请求物资配送 ． 物资储备 中心与受灾节点 、 受灾节点之 间的 异概率为 ０ ． ２ 广 义 运 输 费用 （ 距离） 为 Ｇ √ ＝ ０， １ ， ２ ， …， ｎ ） ， 物 资储 备 中 心 编号 为 ０， 受 灾节点编号为 １到 ｎ ． 要求为各地震应急救助 区域指派运输 车辆 ｋ． 并 确定车辆运输路线 ． 使得总运输费用最低 。 对 于模 型 图 中 的每 条弧 （ ｉ ， ｉ ） ≠； ） 和 车 辆 ｋ定 义 变 量 ｘ ：

（ ， ） （ ， ） 。 由此 可 见 采 用 网格 序 号 编 码 较 直 ３ ３ ，４ ４ ） 角 坐标 编 码 具 有 编 码 长 度 短 、 明 、 观 的 优 点 。 简 直 编码 过 程 中网格 点 的数 据结 构为 ：
ｓｒｅ ｉＮ ｄ ／ 个 节 点 的数 据 结 构 包 括 该 节 点 ｘ ｙ坐 ｔｕｔ ｄ ｏ ｅ／每 Ｇｒ ，
表 达式 为 ：
Ｄ 一 （ ＋ ＿ １ ＿兰二 ）
１ 兰
２ ３ ４
８ ９
由于 采 用 蚁 群 算 法
的搜 索 策 略 生 成 航 线 的 初 始种 群 ， 因此种 群 的编 码 方 法 既要 适 用 于 蚁 群
１ １ Ｏ １
ｌ １ ３ ４
￡， ｚ
目标 函数 不可 微 甚 至不 连 续 ， 或者 虽 然 目标 函数 可
微但 问题 的规 模 非 常大 的优化 问题 ， 多传 统 的优 很 化 方法往往 不再适用 ＿ 。由于遗 传算法 不 要求 目标 ２ ］ 函数 的可微 及 连 续性 ， 且 可 以在 容许 的时 间范 围 而 内找到大规 模 优 化 问题 的满 意解 ， 因此 ， 年来 ， 近 遗
２ 遗 传 算 法 用 于 航 路 规 划
２ １ 初始 群体 的产 生 方法 ．
初 始 种群 是遗 传算 法迭 代运 算 的起 点 ， 由一 它
收 稿 Ｅ期 ：０ １年 ４月 ２日 ， 回 日期 ：０ １ ５ ８日 ｔ ２１ 修 ２１年 月 作者简 介 ： 田鹤 ， ， 士研 究 生 ， 究 方 向 ： 事 航 海 理 论 与 方 法 。李 启 华 ， ， 授 ， 士 生 导 师 ， 究 方 向 ： 事 航 男 硕 研 军 男 教 硕 研 军 海 方 法 与 理 论 。孟 一 鸣 ， ， 士 研 究 生 ， 究 方 向 ： 战 指 挥 与 控 制 。 男 硕 研 作

《军事运筹与系统工程》文稿格式要求1.文稿内容构成来稿应要素齐全，包括：题目（中、英文），作者姓名（中文、汉语拼音），单位，摘要和关键词（中、英文），作者简介，正文，参考文献。

每篇论文正文(含图表)一般不得超过7000字。

题目一般不超过20字，须提供与之对应的英文标题。

作者姓名按照署名顺序排序。

作者只列出对全文有贡献的主要参加者，数量不超过4人，同时须提供每位作者的汉语拼音，例如：WANG Dong-fang。

文末须提供所有作者的简介和通信作者联系方式。

作者简介包括出生年、性别、职称、学位、是否是博士生导师或硕士生导师、主要研究方向。

通信作者联系方式包括电话、详细通信地址和邮政编码。

2.插图插图应当清晰，不得有阴影，字不要压线。

上传稿件时须同时上传文中所有图的JPEG格式原图。

图中所有线条需要区分时应当用线形或标识符区分，不得用颜色区分。

图序、图题、单位、坐标值要完整，并与正文一致。

图中文字的正斜体要与正文统一。

3.公式与量符号文中公式须用Mathtype公式编辑器编辑。

公式居中，公式的编号居右。

文中所有量符号，应在首次出现时加以定义或者说明。

同一个量的符号，应全文统一。

4.参考文献所引用文献必须是作者本人直接阅读过的、正式公开出版的相关文献。

非公开发行的书籍、杂志、报纸，内部资料及未公开发表的文章不能作为参考文献。

参考文献应当在文中标明引用，参考文献的编写顺序按照论文中引用文献的顺序进行编排。

参考文献必须依照类别格式提供完整的引用信息，不可缺项。

请参考国家标准《信息与文献参考文献著录规则（GB/T7714－2015）》中的参考文献著录格式。

（1）专著作者. 专著名[M]. 版本. 出版地: 出版者, 出版年.原作者. 译著名: 原著版本[M]. 译者, 译. 译著版本. 出版地: 出版者, 出版年.（2）期刊论文作者1，作者2，作者3，等. 文题[J]. 刊名, 年, 卷(期): 起始页码－终止页码.（3）会议论文作者. 文题[C]//会议文集名. 出版地: 出版者, 出版年: 起始页码－终止页码.（4）学位论文作者. 文题[D]. 出版地: 出版者, 发布年份.（5）报纸文章作者. 文题[N]. 报纸名, 出版日期(版次).（6）网络资源作者. 文题[文献类别/OL]. (上传日期) [引证日期]. http://网址.5.排版正文采用小4号国标仿宋字体，单栏排版，便于专家审稿。