基于知识型蚁群算法的时间依赖型成像调度方法研究

本项目针对时间依赖型成像调度问题进行一些预先研究。将时间依赖型成像调度问题分解为多星多任务分配、单星多任务观测调度和多任务多资源数传任务调度三个子问题；研究时间依赖型成像调度问题的求解框架，构建总问题求解和子问题求解之间的循环迭代关系；设计并实现求解多星多任务分配问题、单星多任务观测调度问题和多任务多资源数传任务调度问题的知识型蚁群算法：根据具体问题定义不同类型的知识，构建能有效管理各种知识的知识模型，基于蚁群优化思想设计可行方案构建机制，建立蚁群优化模型和知识模型之间的交互机制，设计能有效评价可行方案的指标集，最终实现对不同问题的高效求解；以高分辨率对地观测系统为背景，设计一个比较完善的能反映出时间依赖型成像调度问题本质特征的应用实例。力争该项目在理论、方法和结合国情方面达到国内先进水平。

本项目的主要研究成果可总结如下：.（1）在现有智能优化方法的基础上，论文建立了知识型蚁群算法的基本框架。该框架采用蚁群优化模型和知识模型相结合的集成建模思路：蚁群算法按照“邻域搜索”策略对待优化问题的可行空间进行搜索；知识模型从前期的优化过程中挖掘出一些有用的知识，然后采用得到的知识来指导蚁群算法的后续优化过程。知识型蚁群算法的基本框架为现有优化方法改进提供了一种有益的借鉴。提出了精英个体知识、构件知识、算子知识和参数知识等四种典型的知识形式，可辅助知识型智能优化方法高效地求解复杂优化问题。.（2）提出了考虑提早-延期惩罚调度问题的求解算法。机器加工一个工件引起的惩罚项不是一个固定值，而是依赖于工件的完工时间。考虑每个工件具有不等的释放时间、交货期、提早和延期惩罚系数，为并行机环境下的调度问题建立了数学模型。并行机环境下，一是将求解单机问题的模因演化算法进行了扩展使之应用于并行机环境，二是在给定工件加工序列的情况下提出了一种改进的构造启发式算法确定工件的加工机器及开工时间，通过实验分析给出了这两种算法各自的适用场景。.（3）提出了订单受理与调度问题的求解算法。为最大化完工订单的收益，需要将选择和调度这两个决策过程集成考虑，从所有订单中选择出一部分加工并为各订单安排加工时间，加工订单获得的收益依赖于订单的完工时间。建立了该问题的数学模型，提出了求解该问题的差异化控制遗传算法。算法中针对该问题的特点提出了一种衡量个体之间差异大小的准则，使用差异化控制策略使算法在搜索过程中始终保持一个差异化种群，引入基于析构与构造策略的迭代贪婪启发式算法作为局部搜索算法。.（4）提出了具有多时间依赖特点调度问题的求解算法。该问题是在订单受理与调度问题的基础上，引入时间依赖转换时间以及提早-延期惩罚，非常复杂、难以求解。采用位于0和1之间的实数作为编码方式，每个实数表示工件的实际完工时间占整个时间窗口长度的比率。当给定一个实值向量时，根据向量中的各实数预先确定对应工件的开工时间和完工时间，并且根据工件的开工和完工时间计算不同工件之间需要的转换时间。在此基础上建立一个有向无环图，图中最长路径上的节点即为被安排加工的工件，路径的长度即为该实值向量对应的目标函数。提出一种基于该有向图适应度评价的混合差分进化算法，通过和其他三种算法在测试算例上的实验分析验证了算法的有效性。