一种从目标空间反向引导种群进化的进化算法

目前进化算法大多是通过解从决策空间到目标空间的映射，来判断解的质量。针对约束多目标优化问题，将极限学习机代理模型与不可行解存档方法相结合，提出一种通过目标向量反向预测来引导决策空间种群进化的算法。在CTP和TYPE系列的测试问题上进行了HV度量、IGD度量的性能测试。与几种经典的算法比较，该算法在大多情况下都表现出具有竞争力的性能，且在高难度问题下比其他算法表现更好。     

PBIL进化算法在自动组卷系统中的应用

进化计算是一种搜索方法，广泛用于求解各类优化问题。PBIL算法将进化获得的知识——学习概率用以指导后代的产生，使搜索更具方向性，因而往往能取得更好的效果。自动组卷问题是一个典型的组合优化问题。文中针对PBIL算法的特点，设计了一个自动组卷求解方案，并用实验数据进行计算。结果表明；该算法计算速度快、稳定性好，尤其是在约束条件比较多的情况下，显示出算法的高适应性，是解决组卷问题较为理想的算法。     

求解PDPTW问题的快速启发式算法

提出了一种解决有时间窗口装卸货问题（PDPIW）的快速启发式算法．该算法基于局域搜索和随机扰动的思想，以减少车辆数目为主要目标，采用了启发式的搜索方法并加入了随机扰动以跳出局部最小点。该算法可以在很短的时间内显著地提高解的质量，这是仅以减少总路程为主要目标的局域搜索和现代启发式算法不能达到的。对标准算例的测试和与禁忌搜索算法计算结果的比较，表明该算法对于求解此类有时间窗口装卸货问题比传统的启发式算法在计算速度和减少车辆数目上更具优势。     

一种进化型蚁群算法及其在TSP问题中的检验

蚁群算法是通过模拟蚂蚁觅食而发展出的一种新的启发算法，其收敛速度一直是人们关心的问题。针对蚁群算法的一些不足，提出基于最小生成树的进化型蚁群算法。它利用了最小生成树与最优路径之间的关系限制了蚂蚁在每一个城市的搜寻范围，进化了寻优策略，节省了在不可能构成最优路径的路段上的计算时间，提高了运算速度，克服了以往蚁群算法的计算时间长、精度低的缺点，使得蚁群算法有了显著的提高。计算机仿真结果表明，该文算法改进了标准蚂蚁群算法的效率和计算结果的质量。     

求解一类并行多机调度问题的混合启发式算法

该文研究了一类工件具有不同释放时间的并行多机调度问题，调度目标为使总流程时间最小。针对该类调度问题具有强NP—hard的特点，首先构造了的一种启发式算法，该算法能够在很短的时间内找到次优解。由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降，结合遗传算法的全局搜索能力，提出了一种混合启发式算法进一步改善解的质量。仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点，能够在较短的时间内求解较大规模的调度问题，算法的计算量小，鲁棒性好。     

集装箱码头岸桥最优调度理论研究和高效算法

岸桥调度问题是集装箱码头中最核心的调度问题之一.现有研究成果无法在可行时间内计算出对较大规模业务的最优调度,因此现有岸桥调度算法普遍采用启发式策略,以保障在可行时间内计算出一种调度.首先从理论角度证明了完工时间下界的正确性,设计了一种最优调度构造方法,完备了岸桥调度问题的理论体系;其次,在此理论工作基础上,设计了线性时间复杂度的算法求出最优调度;最后,用实验验证了所提方法在解的质量和效率上显著优于现有方法.     

分支定界算法的分布并行化研究

介绍了一种专用于计算分支定界算法的机群计算平台，其中所使用的分布并行策略减少了分支定界算法计算时间复杂度，减小了问题的规模；可以把计算平台机群中的任何一台计算机上计算出的当前全局最佳本分值，实时地广播给所有其他并行的计算机，并作为它们新的最佳本分值，实现分支节点的快速并行淘汰；应用启发式算法修改了分支定界算法，提高了分支节点的淘汰效率。选用旅行商问题实例作为测试基准。计算表明，在保证求得最优解的前提下，该平台能很好地提高分支定界算法的效率。     

旅行商问题的闭环DNA算法

旅行商问题TSP是NP完全问题,在工程实践中有着广泛的应用,利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式,与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA计算模型及其改进;随后提出了一种基于改进的闭环模型求解TSP问题的算法,并对算法的实验过程进行了详细的描述;最后运用该算法解决了一个小规模的TSP问题算例,结果表明,该算法能在较低的时间复杂度内有效地解决TSP问题。     

求解PDPTW问题的快速LNS算法

提出了一种解决有时间窗口的装卸货问题（PDPTW）的快速大规模领域搜索（LNS）算法。该算法基于大规模邻域搜索理论和随机扰动思想，在第一阶段主要以减少车辆为目标，第二阶段对第一阶段得到的解优化总路程长度。该算法能在较短时间内显著提高初始解的质量．克服了单纯以车辆数目或以总路程长度为目标的算法所得到解的局限性。通过标准算例的测试和同禁忌搜索的比较表明，该算法在求解PDPTW问题时，在计算时间和优化整体目标上更具优势。     

旅行商问题的闭环DNA算法

旅行商问题TSP是NP完全问题,在工程实践中有着广泛的应用,利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式,与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA 计算模型及其改进;随后提出了一种基于改进的闭环模型求解TSP问题的算法,并对算法的实验过程进行了详细的描述;最后运用该算法解决了一个小规模的TSP问题算例,结果表明,该算法能在较低的时间复杂度内有效地解决TSP问题。     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

二次分配问题的粒子群算法求解

文章采用了一种新的算法,即粒子群算法(PSO)去解决二次分配问题(QAP),构造了该问题的粒子表达方法,建立了此问题的粒子群算法模型,并对不同的二次分配问题算例进行了实验,结果表明:粒子群算法可以快速、有效地求得二次分配问题的优化解,是求解二次分配问题的一个较好方案。PSO算法在很多连续优化问题中已经得到较成功的应用,而在离散域上的研究和应用还很少。文章应用PSO算法解决QAP问题是一种崭新的尝试,它对于将PSO算法应用于离散问题,特别是组合优化问题无疑具有启发性,并为进一步深入研究奠定了基础。     

改进后的D_时刻表算法及其在实际中的应用

为了处理现实生活中事件发生除了先后关系以外还客观存在的时间宽度问题，文中实现了一种可以实际操作的方法。该方法是以文献[1]中的求解D_时刻表的方法为基础，分析找到了其不足的地方并加以改进。文中利用改进后的算法对该校校园运动会项目进行安排，结果表明该方法取得了较好的效果，从而实现了对该类问题的一种新的解决方法，使得解决该类问题成为现实。     

A heuristic algorithm to minimize total weighted tardiness on a single machine with release times

This paper attempts to solve a single machine‐scheduling problem, in which the objective function is to minimize the total weighted tardiness with different release dates of jobs. To address this scheduling problem, a heuristic scheduling algorithm is presented. A mathematical programming formulation is also formulated to validate the performance of the heuristic scheduling algorithm proposed herein. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. Overall, this algorithm can find the optimal solutions for 2200 out of 2400 randomly generated problems (91.67%). For the most complicated 20 job cases, it requires less than 0.0016 s to obtain an ultimate or even optimal solution. This heuristic scheduling algorithm can therefore efficiently solve this kind of problem.     

基于遗传算法的考虑优先约束和负载平衡的多任务调度

文章研究了考虑负载平衡、有优先约束的n个任务在m个同等处理机上处理,使总完成时间最小的分布式任务调度问题。对两个以上处理机的这类问题便是NP难题,因此以往都是用启发式算法来求解。文章首次提出了使用遗传算法来解决该类问题,设计了相应的编码方法和适应值评估方法,并用一个一维向量来表示任务间的优先关系。仿真结果证实了算法的有效性。     

基于改进遗传算法的舰载机弹药调度

舰载机弹药调度所涉及设备及限制条件多,其方案设计属于NP-hard组合优化问题。传统的基本遗传算法(SGA)求解此类问题在全局搜索和收敛方面存在不足,因而提出了改进的遗传算法。采用实值分段方式编码,保证解的可行性;在交叉和变异运算中采取精英保留策略,自适应地调整保留精英及更新"劣等"个体的数量,保证了样本多样性,同时大大加快了收敛速度;通过实例仿真实验验证了此改进遗传算法在寻求最优调度方案上的优越性。     

小容量网络上的最大流算法

最大流问题是一类经典的组合优化问题。描述了一种小容量网络,这种网络有强的实际应用背景,同时给出了专门解这种网络上最大流问题的算法。该算法比通用的算法快。它已经突破了最大流问题的O（mn)时间障碍,具有较强的理论意义,也为解决许多实际应用问题提供了更有效的算法。同时,由于判断一个网络是否为小容量网络非常简单,因此该算法也具有普遍意义。     

Solving the Identifying Code Problem by a Genetic Algorithm

Identifying code is a concept in information theory and can be applied to problems of fault detection and location detection. In this paper, by assigning cost to every code word, we propose an optimization problem to find an identifying code with minimum cost and formulate the problem by an integer program. We generalize the results to the robust identifying code problem, which is proposed for poor environments. A tailored genetic algorithm is provided to solve the problem, and the experimental result shows that it is competitive for large-scale problems     

基于遗传算法的数码问题求解

在人工智能研究中，数码问题常被用来作为一些搜索算法的测试实例。数码问题的搜索空间巨大，对于24数码问题，目前最好的启发式搜索算法找到最优解(最少移动步数)通常也至少需要2．25小时^[1]。遗传算法具有简单、通用、鲁棒性强的特点，适合于在复杂而庞大的搜索空间中寻找最优解。该文给出了求解该问题的遗传算法，并针对遗传算法容易过早收敛的问题，对传统遗传算法进行了改进。通过用多个随机生成的]5数码和24数码问题作为测试实例，本算法均在较短的时间内找到了问题的解，从而证明了算法的有效性。     

带杂交算子的蚁群算法

蚁群算法是一种由意大利学者Macro Dorigo等提出的新型模拟进化算法,它具有许多优良性质,因此被广泛用于求解组合优化问题。但基本蚁群算法有许多不足。特别是许多搜索速度慢,且容易陷入局部最优。该文针对这个问题提出了一种改进算法。该算法通过引入遗传算法中用到的杂交算子来改善蚁群,使其对应的问题的解更加优良,用改进算法求解TSP问题的结果表明改进算法是有效的。