面向多最优解组合优化问题的决策求解算法

针对具有固定物品总和、多最优解特征的组合优化问题,以固定总和实数子集问题和购买鸡翅问题为例,给出了这类多最优解组合优化问题的形式化表示。在分析枚举等经典算法基础上,提出了基于整数状态表示和实数状态表示的0-1决策递归搜索多最优解动态规划算法。针对该算法在最优解数量较大时,时间复杂度趋向O(mⁿ)的问题,提出了基于相同决策路径合并和基于0-x决策的两种改进算法。实验中两种改进算法的计算时间基本符合与O(nb+nm)的正比关系,表明对于这类多最优解组合优化问题具有良好的求解性能。     

应用单亲遗传算法进行大规模UCAVs任务分配

在应用GA求解大规模无人作战飞机(UCAVs)任务分配这个典型组合优化问题时,需要使用描述问题直观的序号编码方式,但由于传统的交叉、变异算子操作复杂,因而进化效率不高.针对上述的不足,提出了一种单亲遗传算法,采用序号编码,使用基因换位等遗传算子,简化了遗传操作.通过对单亲遗传算法、传统遗传算法求解该问题所得的结果作了详细的比较,证明了单亲遗传算法在寻优效率上的优越性.     

基于组合设计的软件可靠性测试方法

提出了将实验设计中的组合设计方法应用于软件可靠性测试。分析了组合设计方法在软件可靠性测试用例设计中应用的理论基础和基于组合设计的软件可靠性测试的一般方法。同时指出了利用软件操作剖面信息和失效数据进行可靠性评估的方法。     

提高装备战备完好性的新举措——综合诊断

介绍了国外正在发展的一种提高武器系统战备完好性的新设计与管理思想和采取的措施一综合诊断,对其涵义、特点、实施途径和诊断方案作了简要说明,对综合诊断的权衡方法进行了深入的研究,并开发出了综合诊断权衡辅助程序,指出了在我军开展综合诊断工作的必要性并提供了几点建议。     

战车火控系统射击命中三要素函数误差分析

火控系统射击(函数)误差可分解为射弹散布函数误差和火控射击准备函数误差。而射击准备函数则是命中三要素函数即瞄准函数、解算函数和控制函数的合成函数。命中三要素的提出,为火控系统射击误差(精度)的分析提供了新的途径。它们均是命中目标的关键要素,又各具特色,为火控系统射击精度乃至系统反应速度的提高,指出了应该努力的方向。针对此进行了具体的分析。     

Quadratic bottleneck problems

We study the quadratic bottleneck problem (QBP) which generalizes several well‐studied optimization problems. A weak duality theorem is introduced along with a general purpose algorithm to solve QBP. An example is given which illustrates duality gap in the weak duality theorem. It is shown that the special case of QBP where feasible solutions are subsets of a finite set having the same cardinality is NP‐hard. Likewise the quadratic bottleneck spanning tree problem (QBST) is shown to be NP‐hard on a bipartite graph even if the cost function takes 0–1 values only. Two lower bounds for QBST are derived and compared. Efficient heuristic algorithms are presented for QBST along with computational results. When the cost function is decomposable, we show that QBP is solvable in polynomial time whenever an associated linear bottleneck problem can be solved in polynomial time. As a consequence, QBP with feasible solutions form spanning trees, s‐t paths, matchings, etc., of a graph are solvable in polynomial time with a decomposable cost function. We also show that QBP can be formulated as a quadratic minsum problem and establish some asymptotic results. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Approximating the nondominated frontiers of multi‐objective combinatorial optimization problems

Finding all nondominated vectors for multi‐objective combinatorial optimization (MOCO) problems is computationally very hard in general. We approximate the nondominated frontiers of MOCO problems by fitting smooth hypersurfaces. For a given problem, we fit the hypersurface using a single nondominated reference vector. We experiment with different types of MOCO problems and demonstrate that in all cases the fitted hypersurfaces approximate all nondominated vectors well. We discuss that such an approximation is useful to find the neighborhood of preferred regions of the nondominated vectors with very little computational effort. Further computational effort can then be spent in the identified region to find the actual nondominated vectors the decision maker will prefer. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009