绝对值距离Steiner最小树问题的二进制粒子群算法

绝对值距离Steiner最小树问题是在铺设网络线缆等领域应用广泛的一个NP难的经典组合优化问题。针对此问题,提出基于最小生成树问题的二进制粒子群算法。该算法首先对网络节点进行编码,计算适应度函数值,并使用二进制粒子群算法求解Steiner点。数据实验结果表明,该算法具有实用性。     

一种求解对称TSP的简单候选集方法

TSP（旅行商问题）作为一种解决组合优化问题的有效方法,在近几十年来受到了广泛的研究。理论证明它是一个典型的NP难问题,为了更快捷地求解,候选集方法在多种求解算法比如LKH算法中都有用到,一般是用于产生一个接近局部最优的初始解,较少用于寻路过程中。本文提出了一种新的简单的候选集方法,它采用一种新的距离度量,更好地符合了对称TSP的寻路规则。将其应用于最大最小蚁群算法（MMAS）的寻路过程中,实验结果表明针对对称TSP问题,该方法能比基本的MMAS取得更好的性能。这种候选集方法也可以用于其他求解对称TSP问题的进化计算。     

一种改进的求解TSP问题的遗传算法

TSP问题是典型的NP难组合优化问题,而遗传算法是求解此类问题的一种方法。但遗传算法存在收敛速度慢和陷入局部最优的问题。针对上述问题并结合TSP的特点提出了一种改进的遗传算法,对传统遗传算法的各种操作与算子进行了优化与改进,较好地解决了种群多样性与算法收敛性的矛盾。实验结果表明,改进后的算法明显优于传统遗传算法,说明该算法具有良好的有效性与可行性。     

一种求解带权集合覆盖问题的近似算法

以优化形式描述的集合覆盖问题是一个NP难问题,设计快速有效的近似算法,具有重要的理论与现实意义．基于贪心算法思想,提出了一种求解带权集合覆盖问题的近似算法,并讨论了该算法的相对近似比．     

求解装箱问题的一种模拟退火算法

装箱问题在现实生活中具有广泛的应用,如作业调度、最优任务分配等,是一个NP完全问题。针对一维装箱问题,提出了基于首次适应(FF)近似算法和模拟退火算法相结合的一种模拟退火算法,给出了具体的算法描述。实验结果分析表明,该算法是高效可行的。     

基于DNA算法的Ad hoc路由协议优化算法研究

针对移动Ad Hoc网络中的Qo S路由问题,提出一种基于DNA算法的全新优化算法,该算法采用DNA编码方式,对每条路径进行编码,利用合成技术完成NP完全路径,最后通过实验得出优化数据.实验结果验证了该算法的有效性,并且在降低算法复杂程度下,得到了路由优化的最优解.     

基于禁忌算法的长沙移动网络优化

移动网络优化问题是一个NP难问题,所以它并不能保证在合理的运行次数里就找到最优的方案。常用的人工智能求解优化问题有遗传算法、蚁群算法和禁忌算法。相对于这几种算法在离散对象的组合优化问题中优势比较明显,而禁忌算法更容易跳出局部极值从而能在更大的范围内寻找到一个较优解。我们开发的基于禁忌算法的长沙移动网络优化软件,通过科学分析采集的数据,从而解决话务阻塞和掉话问题,优化了网络,提高了长沙移动的网络质量。     

一种物流优化的蚁群算法设计

物流配送中求最优解是一类典型的NP难问题,具有很高的时空复杂性。目前,还没有较完善的算法能在一定的时间限制内快速地寻到问题的最优解,只能尽可能地在规定的时间内寻到问题的近似最优解。由于蚁群算法具有鲁棒性和正反馈等特点,因此它被成功运用到物流配送问题的求解中。根据蚁群算法存在的一些缺陷,如搜索时间长、过早收敛等,采用OOP进行优化。通过实验,验证了改进算法的性能。     

图像并行集群复原校正方法研究

论述了图像校正算法的并行集群实现方法。针对图像复原问题,对复原算法结构与流程的并行处理进行研究,提出了整体数据传输、按行分片计算复原的并行处理方法。该方法在基于MPI的计算机并行集群系统中的8个计算节点上通过了测试,给出了集群校正实验结果和MPI并行计算时空图。实验结果表明,基于集群计算的并行复原方法十分有效,可缩短计算时间,提高计算效率。     

一种改进的属性约简方法

属性约简是粗糙集理论的核心问题之一,寻找最优约简现已证明是NP—hard问题。本文在差别矩阵的基础上,采用贪心算法的策略,提出了一种启发式算法来寻求最优约简。该算法不仅能在有核的决策表中通过核进行属性扩充求得最优约简,而且在无核的决策袁中也能根据属性在差别矩阵中出现的频率求得最优约简。经实例验证该算法是有效的。     

带有批移动方式的流水车间极小化平均流程时间的启发式方法(英文)

以极小化平均流程时间为目标的批排序问题是十分重要的,因为极小化平均流程时间等价于极小化平均在制品占用．由于这一问题属于ＮＰ－难题,不存在多项式算法保证求得最优解．基于对该问题模型结构分析,本文提出了一个新的启发式算法．计算机模拟结果表明,该算法简便且优度高．     

基于优先级和性价比机制的网格调度算法研究

网格任务调度算法是一个复杂的算法,并且被认为是一个NP难问题,在分析该算法的基础上,指出该算法的缺点：负载不均衡,算法的经济效益比较高以及不能兼顾到任务的紧迫程度,因此,从经济效益和优先级角度改进该算法,通过建立数学模型的方法,证明了改进后的算法能够在一定程度上均衡负载,并且也降低了算法调度过程中的费用问题,还满足了优先级高的任务的需求,从总体上来说,该算法提高了算法的效率,并提高了网络的整体性能。     

0/1背包问题的DNA计算

0／1背包问题是一个著名NP——复杂问题，以前人们主要用分支——限界法、贪心法等方法去解决该问题。本文主要论述了一种新的计算模式——DNA计算来解决0／1背包问题。依据分子生物学的实验方法，文中所提出的算法是有效和可行的。     

计算问题的空间难解性

在计算问题中有些是不可解的或称难解的 .虽然它们在理论上是可解的 ,但解法需要大量的时间和空间 ,而无法在实践中应用 .计算理论中的空间函数、层次推理、正则运算等都从空间角度论证了计算问题的不可解性即计算问题的难解性 .     

基于遗传算法求解TSP问题的算法设计

TSP是一个典型的组合优化问题,并且是一个NP难题,其可能的路径总数与城市数目n是成指数型增长的,所以一般很难精确地求出其最优解,因而寻找出有效的近似求解算法就具有重要的意义.现提出一种求解TSP问题比较有效的遗传算法,从其数学模型、遗传算子、评估函数、种群多样性等方面对算法进行了分析,结果表明提出的算法在求解TSP问题上是有效的.     

基于粒子群算法的可靠性优化

系统可靠性优化已被证明是一个NP完全问题,不存在精确的求解方法。人们构造了大量的启发式算法,如遗传算法(GA),蚁群算法(ACO),模拟退火算法(SA)等。针对各种算法所存在的早熟收敛,易陷入局部极值点的缺点,提出了将粒子群算法(particle swarm optimization,PSO)用于求解可靠性问题。给出了基于粒子群算法的可靠性优化求解策略,根据数学模型,详细讨论了求解步骤,最后给出了实验仿真结果。结果表明该算法具有较强的局部搜索能力,同时也有更高的搜索效率,与其它方法相比,该算法能够找到更优解,验证了该算法的可行性和有效性。     

用动态规划法和贪心法解决背包问题

0-1背包问题和背包问题是一类经典的NP困难问题。采用动态规划法和贪心法对该问题进行求解,分析和比较这两种算法在求解同一问题时的差异。     

基于Yager法的随机模糊自由分布报童模型

研究了基于随机模糊需求的自由分布报童问题,并建立了相应的数学模型.利用Yager法,将模糊的目标函数逆模糊化为实值目标函数,进而寻求模型最优解,同时说明所建模型是对传统的自由分布报童问题的一种扩展.最后,通过数字实例,对上述两种报童模型的最优解进行了比较,并且分析了需求的模糊性对所建模型最优解的影响.     

Chebyshev-Legendre method for discretizing optimal control problems

In this paper, a numerical method for solving the optimal control (OC) problems is presented. The method is enlightened by the Chebyshev-Legendre (CL) method for solving the partial differential equations (PDEs). The Legen-dre expansions are used to approximate both the control and the state functions. The constraints are discretized over the Chebyshev-Gauss-Lobatto (CGL) collocation points. A Legendre technique is used to approximate the integral involved in the performance index. The OC problem is changed into an equivalent nonlinear programming problem which is directly solved. The fast Legendre transform is employed to reduce the computation time. Several further illustrative examples demonstrate the efficiency of the proposed method.     

一类推广的Bottleneck问题的多项式算法

本文讨论了一类Bottleneck问题,给出了判定最优解的三个定理,并在此基础上给出了一个求最优解的算法和算例,算法的复杂度为O(n2).