一类问题的描述方式及其算法

本文给出了一类问题的一种描述方式，这类问题包括有向图的最短路问题、赫夫曼问题、矩阵链问题、汉密顿回路问题等等。在这种描述方式的基础上，给出了一个算法模式，并讨论了如何通过该算法模式得到回溯算法、动态规划算法、分枝限界算法、贪心算法以及启发式搜索算法等等，只要对这个算法模式中的变量给出不同的定义就可以得到求解这类问题中某一具体问题的算法，最后还给出了ＳＩＭＤ模型上的一个并行算法模式，通过该并行算法模     

分治递归算法的解题能力

为了培养学习编程的逆向思维，运用分治思想的递归算法提高解决问题的能力，理解分治和递归的关系，掌握递归算法解决问题的条件和原理是十分必要的。从提出问题、分析问题、抽象问题的特征、解决问题和分析递归算法的局限性的过程，运用比较法比较迭代与递归之间的关系，结合具体问题，对理解递归算法解决问题给出了有效的方法。用分治的递归方法求解问题，其结构简单，可读性强，但是递归算法理解起来有一定难度，研究了递归算法的特征、递归与分治之间的关系、递归与迭代之间的关系，根据时间和空间复杂度，给出了递归算法的深度建议。实践的结果证明，采用这样的方式，能够帮助读者理解逆向思维和分治思想的本质，提升运用递归算法解决生活和学习中的问题的能力。     

蚁群算法及其实现方法研究

蚁群算法是一种相对较新的启发式方法，通过模拟蚂蚁的觅食行为解决问题，是目前昆虫算法中较成功的例子.蚁群算法的本质是一种并行的、自组织的算法，它可应用于更好地组织大数目实体的相互作用过程，如货郎担问题、车辆绕径问题、排程问题等。该文简述了蚁群算法的起源和发展，总结了蚁群算法的特点和不足及针对这些不足提出的各种改进方法，并介绍了和蚁群算法相关的几种具体应用。最后，文章探讨了蚁群算法研究中仍存在的问题和以后的发展方向。     

改进型蚁群算法求解运输调度问题

运输调度问题是一类复杂的组合优化问题，是近年来物流控制优化中的研究热点。通过对基本蚁群算法中的选择策略和信息素挥发速度的改进，提出了一种新的蚁群算法，克服了基本蚁群算法搜索时间长、易陷入局部最优解等缺陷，将其用于求解一类运输调度问题，实验发现算法有效，并且对于规模越大的问题，相对其它算法有更优的解。     

联盟运输调度问题模型结构与算法研究

联盟运输调度问题是在基本运输调度问题基础上衍生出的最具现实意义的一类组合优化难题，是近年来物流控制优化领域的研究热点。依据运输调度问题分类方法，描述了联盟运输调度问题的结构；通过分析遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法、粒子群算法的特点及其求解运输调度问题的现状，讨论了它们求解联盟运输调度问题的可能性；展望了联盟运输调度问题发展的前景，指出改进原算法、提出新算法、并行算法是解决联盟运输调度问题的重要手段。     

基于矩阵的通信加密算法设计

设计了一种基于矩阵的加密通信算法。由于单片机资源的局限性，分析了单片机通信中加密时要注意的3个问题，并针对这3个问题，分别给出了解决方案和算法的设计；针对反编译破解问题对算法进行了升级，分别在私钥生成、加密和解密过程中引入矩阵；针对密文可互解问题，给出了两种算法变换方案，极大增强了单片机中网络通信的安全性。     

不确定车辆数的有时间窗车辆选径问题的混合算法

针对标准遗传算法在求解车辆选径问题中出现的早熟、收敛、易陷入局部极值点的问题，提出了一种由遗传算法结合模拟退火算法的混合算法求解车辆选径问题，并与遗传算法进行了比较。该算法利用了模拟退火算法具有的较强的局部搜索能力的特性，有效地克服了传统遗传算法的“早熟收敛”问题。实验结果表明，该算法具有计算效率高、收敛速度快和求解质量优的特点，是解决车辆选径问题的有效方法。     

蚁群优化算法及其应用

蚂蚁算法是由意大利学者M．Dorigo等人提出的一种新型的模拟进化算法。该算法首先应用于旅行商问题并获得了极大的成功，其后，又被用于求解指派问题、Job—shop调度问题、图着色问题和网络路由问题等。实践证明，蚂蚁算法是一种鲁棒性强、收敛性好、实用性广的优化算法，但同时也存在一些不足，如收敛速度慢和容易出现停滞现象等。     

求解Job Shop调度问题的混合蚁群算法研究

为了解决单一算法求解Job Shop调度问题存在的不足，该文提出了一种混合算法，将蚁群算法用于全局搜索。针对蚁群算法易于陷入局部最优的情况，提出了一种基于关键工序的邻域搜索方法，将使用此邻域搜索方法的TS算法作为局部搜索策略。利用TS算法较强的局部搜索能力，提高了蚁群算法的优化能力，达到改善Job Shop调度问题解的质量。实验结果表明，混合算法在较短的时间内，找到了FT10、LA24、LA36等典型benchmarks问题的最优解，得到的makespan的平均值较并行遗传算法(PGA)和TSAB算法均有所提高。     

基于遗传算法的混合优化策略研究

最优化问题是工程设计、科学研究、经济管理等众多领域经常遇到的一类问题。随着待解决问题范围的不断扩大以及优化算法研究的不断深入，混合优化策略已成为解决大规模、高复杂度优化问题的一种重要而有效的方法。介绍了遗传算法、贪婪法、模拟退火算法、禁忌搜索的基本原理，阐述了各种算法的优缺点；针对各单一算法存在的缺陷和不足．对三种以遗传算法为主体框架的混合优化算法进行了分析；最后，指出了混合优化算法存在的问题及今后的发展方向。     

求解多目标流水车间调度Pareto最优解的遗传强化算法

针对多目标流水车间调度Pareto最优问题, 本文建立了以最大完工时间和最大拖延时间为优化目标的多目标流水车间调度问题模型, 并设计了一种基于Q-learning的遗传强化学习算法求解该问题的Pareto最优解. 该算法引入状态变量和动作变量, 通过Q-learning算法获得初始种群, 以提高初始解质量. 在算法进化过程中, 利用Q表指导变异操作, 扩大局部搜索范围. 采用Pareto快速非支配排序以及拥挤度计算提高解的质量以及多样性, 逐步获得Pareto最优解. 通过与遗传算法、NSGA-II算法和Q-learning算法进行对比实验, 验证了改进后的遗传强化算法在求解多目标流水车间调度问题Pareto最优解的有效性.     

On uniqueness of solution to the multi-peg towers of hanoi

The multi-peg Towers of Hanoi problem is still open. No provably optimal constructive algorithm to solve the problem is known. The minimum number of moves required is also unknown. Though optimal solutions are observed to be non-unique, the exact uniqueness criteria of an optimal solution are little known to the literature. This paper revisits a deterministic algorithm conjectured to optimally solve the problem and addresses the uniqueness characteristics of an optimal solution.     

一种融合模拟退火和单亲遗传的优化求解算法

度约束最小生成树是一个经典的组合优化NP难题,其在网络设计和优化中有广泛的应用;现有求解方法往往不能很好地兼顾求解效率和求解精度;为了在缩短求解时间的同时,更好地获得最优解,提出了一种结合模拟退火算法和单亲遗传算法的改进求解算法;首先,改进遗传算法中变异因子的生成方式,避免不可行解个体的产生,并且设计自适应变异率,以提高算法的求解效率;其次,针对单亲遗传算法仅有变异操作可能导致最优解个体跳跃的问题,结合模拟退火的思想,来保证解的全局最优性;最后,在具体的度约束最小生成树问题中进行了三组实验,从运行时间和最优解的情况等方面与传统单亲遗传算法进行对比,实验表明该算法在求解效率和获得最优解方面都有较好的改进效果。     

并行机间歇过程生产调度的遗传局部搜索算法

研究了一类集成分批的并行机间歇过程调度问题(parallel machine batch process scheduling problem,简称PBPSP),将此问题转化为固定费用运输问题(6xed charge transportation problem,简称FCTP)后,提出了具有集中邻域搜索机制和局部最优逃逸机制的遗传局部搜索算法(genetic local search algorithm,简称GLSA).GLSA算法用先根遍历边排列模式编码生成树解,具有高效的子树补充式单点交叉操作.将基于网络单纯型方法的邻域搜索作为变异算子,并提出了连续随机节点邻域搜索的集中邻域搜索策略以及随机旋转变异与全局邻域搜索相结合的局部最优逃逸策略,极大地强化了遗传局部搜索算法的全局寻优能力.实验表明:GLSA算法获得的解质量优于基于排列编码的遗传算法和基于矩阵编码的遗传算法,得到了所有Benchmark问题的最优解,且具有高鲁棒性.针对一定规模的FCTP问题,GLSA算法比Tabu启发式搜索算法具有更高的获得最优解几率.     

用于间歇化工过程最优设计的遗传算法

间歇化工过程的最优设计问题是一类复杂且难以求解的组合优化问题。通过把这类问题分解为只包含离散变量的主导问题和只含连续变量的子问题,把遗传算法和线性规划法结合起来对其进行求解。并在算法中引入了一类新的算子,显著地提高了收敛概率、算例表明,该方法可以避免直接求解过程的复杂性和困难,并且具有很好的全局收敛性。     

求解0-1背包问题的融合贪心策略的回溯算法

0-1背包问题作为经典的NP完全问题一直得到广泛的关注和研究.研究发现,经典回溯算法在解决0-1背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差.虽然经典贪心算法和现阶段涌现出的大量新型算法能够极大地缩减算法的运行时间,但普遍是以牺牲算法的准确性为代价的,不能保证可...     

一种用于求解TSP问题的随机最佳插入烟花算法

TSP问题是一个NP难问题,求解时间随问题规模呈几何级数增长,如何在较短时间内求得更精确的解一直是重要的研究问题。因为烟花算法在求解过程中能够快速收敛,而且能跳出局部最优解,所以基于烟花算法改进了爆炸资源分配的方式,创新性地提出了2个算子：抛弃节点重新插入的爆炸算子和抛弃路径重新插入的变异算子。再使用精英与轮盘赌相结合的烟花选择策略,设计了一种随机最佳插入的烟花算法（RBIFWA）。将该算法与基本烟花算法、混沌烟花算法、离散蝙蝠算法和自适应模拟退火蚁群算法进行比较,结果显示,RBIFWA算法在迭代次数上明显优于其他算法,且算法的解更加接近已知最优解,表明RBIFWA算法在求解TSP问题上具有更加优秀的性能和更高的求解质量。     

基于免疫算法的车辆路径优化问题

分析了车辆路径问题的研究方法和免疫算法相对于其它进化算法的优势,提出了用免疫算法求解车辆路径问题的方法。在算法的求解过程中,构造了一种新的编码方式,在减少编码长度的基础上能够提高算法的运行效率。通过免疫记忆库的设计以及抗体之间浓度的促进和抑制机制,本算法可以实现解的多样性,避免收敛于局部最优解,同时可以有效地防止在进化的过程中失去最优解的可能性。实验结果表明,本算法可以快速求得优化解,是求解车辆路径问题的一种有效算法。     

一种混合化学反应优化算法求解最小顶点覆盖问题

最小顶点覆盖问题是组合最优化问题,在实际应用中有较广泛的应用,是一个NP难问题。论文针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学化反应的分子编码和目标函数;同时把贪心算法思想创造性地融入到化学反应优化算法的四个重要反应算子中,以加快局部较优解的搜索过程;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解。模拟实验结果表明,该算法对于求解无向图的最小顶点覆盖问题是有效的,并且在求解效率等方面有一定的改善。     

求解煤炭水运配船的免疫优化算法

煤炭水运配船属于多约束混合整数线性规划问题。当问题规模大、约束条件多时很难获得最优解,并且求解时间过长。针对上述问题,提出一种基于免疫克隆算法的求解方案。通过构建相应的数学模型,设计了基于二维矩阵的抗体表示形式和混合整数编码方式,构造了罚函数处理不等式约束。算法使用克隆、变异和抗体浓度抑制等免疫操作,保持了抗体的多样性,避免陷入局部最优。算法仿真表明,该算法在全局最优解和运行速度方面优于遗传算法,优化结果验证了算法的有效性。