基于改进遗传—模拟退火算法的公交排班优化研究

结合公交车辆调度自身的特点,兼顾公交公司与乘客双方的利益,建立了公交排班优化模型,以发车时刻为基因变量进行编码,对两个相邻的发车间隔之差、最大最小发车时间间隔、乘客的满载率等条件进行约束限制,提出了基于改进的遗传—模拟退火算法;对该模型进行优化求解,克服了传统优化算法的缺陷,提高了优化设计过程的求解效率。通过仿真实验得到了利用改进的遗传—模拟退火算法进行求解的不均匀发车时刻表。结果表明,改进的遗传—模拟退火算法能够在公交智能排班优化问题的巨大搜索空间中可靠地找到近似最优解,大大提高了计算效率。     

基于分等级公平竞争模型的可持续模拟退火算法的应用

通过改进可持续模拟退火算法(HFCSA)算法的个体定义与编码方式、种群的生成方式以及设计新的算子,成功解决了医学实验安排这种带约束的优化问题。设计的最优实验方案所需时间是某医学院所使用方案的77%,拓宽了算法的应用领域,为带约束优化问题的求解找到了新的途径。     

求解约束优化问题改进的水波优化算法

为提高约束优化模型的求解精度,提出一种改进的水波优化算法。设计主-从异构种群,结合ε约束处理技术使主群实现探索可行解,从群利用可行解搜寻全局最优解。为加快收敛速度和增强信息交互,主群中个体可以依概率进行个体间学习,设计水波波长函数,使其随着水波的适应度值和违反约束度及时调整。为避免早期收敛,从群采用自适应学习策略以平衡群体的探索和利用。设计随迭代次数变化的放松约束度,提高算法收敛精度。对比实验结果表明,该算法可以获得高质量的可行解。     

基于有导向变异算子的GM-EA算法*

为了进一步提高演化算法的效率,提出基于有导向变异算子的GM-EA算法（guided mutation evolutio-nary algorithm）。通过结合粒子群优化的方法改进郭涛算法,更好地利用当前最优解指导变异,并将算法分为探索与开采两个阶段;在开采阶段基于模拟退火方法决定是否用新个体取代旧个体,在巩固所获取的建筑块成分的同时,尽可能克服早熟收敛问题。实验结果证明了新算法的有效性。     

求解旅行商问题的探索—开发—跳跃策略单亲遗传算法

针对遗传算法求解旅行商问题(TSP)时容易早熟、收敛速度慢等问题,提出一种基于探索—开发—跳跃策略的单亲遗传算法(EDJS-PGA)。该算法将基因移位、倒序、交换三种算子组合构成探索策略,用于扩展解的搜索空间,增强算法全局搜索能力;再将logistic混沌映射和改良圈操作融合为一种混沌映射改良圈算子,用于增强算法的局部搜索能力,构成开发策略;最后针对种群中的同优个体设计了近邻变异算子,构成跳跃策略,增强了算法跳出局部最优解的能力,使其兼具个体变异、局部优化、防止早熟等多重作用。通过对18个TSP实例进行仿真实验,结果表明EDJS-PGA相较于传统单亲遗传算法具有更高的求解精度和收敛速度,且最优解偏差率和平均误差率均处于较低水平;与其他文献对比,EDJS-PGA具有更强的鲁棒性和求解效率。     

求解度约束最小生成树的新的遗传算法

针对度约束最小生成树问题的特征,设计了一种新的编码方式,并在此基础上提出了一个新遗传算法来求解该问题。该算法采用新的启发式杂交算子、变异算子和局部搜索算子,以概率1收敛到全局最优解。数值实验表明该算法优于文中提出的其他4种算法。     

带作业范围约束的岸桥调度模型及其算法设计

受电缆线坑位置与缆线长度的限制,岸桥作业只能在一定的横向移动范围之内。考虑到这一现实要求,结合岸桥作业禁止跨越与安全距离等特有约束,以最小化装卸作业的makespan为目标,构建了新的岸桥作业调度混合整数规划模型。针对问题的NP-hard特性,设计了一种混合模拟退火算法,运用启发式算法生成质量较高的初始解,结合遗传算法的变异运算生成邻域新解,增强了解的多样性,引入禁忌搜索算法的禁忌表操作,避免了循环搜索,提高了求解效率。大规模实验结果表明所建立的模型是有效的,算法的求解质量与效率明显优于标准模拟退火算法与禁忌搜索算法。当实验规模逐渐增大时,与LINGO软件相比,算法在求解效率方面的优势越来越明显。     

遗传模拟退火算法在组播路由选择中的应用

本文研究基于带宽、时延及时延抖动约束最小代价的QoS组播路由优化算法.针对遗传算法在求解多目标优化问题时局部搜索能力弱、易早熟的缺陷,提出了一种基于遗传算法和模拟退火算法混合策略的多目标优化方法.该算法采用树结构编码机制和改进的交叉和变异算子,利用模拟退火算法在可行解范围内构造邻域解集,采用种群早熟评价函数进行局部细化...     

求解决策表最小属性约简的SAGA

首先给出求解决策表核属性集的算法,然后采用动态调节近邻子集的方法改进模拟退火遗传算法,应用于求解决策表的最小属性约简。该约简算法利用核属性集优化初始种群,并采用自适应方式动态选取交叉和变异概率,有效地抑制了早熟收敛现象,提高了算法在解空间中的探索能力和效率。实验结果显示该算法能有效求解决策表最小属性约简问题。     

聚类筛选的人体物理运动生成算法

由于人体物理运动具有高维、非线性以及关节之间强耦合性等特点,导致物理运动生成求解困难.通过分析人体物理运动解空间,提出一种基于空间划分筛选和智能进化策略相结合的优化求解算法.首先对采集的运动数据进行预处理,并随机取样变异获得进化算法的初始种群;然后利用多组协方差矩阵进化策略算法分别对初始种群中的个体优化求解;再对优化求解得到的若干个体采用子空间划分,选取每个子空间中的最优个体作为下一时刻的初始解;最后经过多次迭代获得物理控制轨迹,生成物理运动.实验结果表明,相对于现有算法,该算法不仅能够使人体物理模型更好地跟踪运动数据,而且在鲁棒性、时间性能、稳定性方面都有较大程度提高.     

模拟退火遗传算法在机械臂路径规划中的应用

为研究机械臂的路径规划问题,将传统的退火算法与遗传算法相结合,提出了一种改进的模拟退火遗传算法.该算法不仅能自适应改变遗传过程中的交叉概率和变异概率,还加入了局部退火操作,对每代子种群进行退火处理以克服路径规划过程中陷入局部最优的问题.此外,引入整体退火观念,在整个进化过程中,随着温度的降低,不断拉伸适应度函数提高算法效率.将该算法应用于实验室自主研制的七自由度轻型冗余机械臂上,以时间冲击最优为目标进行轨迹规划.实验表明,该算法可以在保证各项约束的条件下获得最优路径.     

基于融合算法的测试优化选择问题研究

测试优化选择是个集覆盖问题,而启发式算法是求解集覆盖问题的有效方法。文中将遗传算法、BP神经网络和模拟退火算法进行融合,提出了一种融合算法,该算法充分利用遗传算法全局搜索能力强、BP神经网络训练能力强和模拟退火算法搜索速度快的优点,既避免陷入局部最优的现象,又提高了搜索的效率和精度。该算法已应用于求解测试优化问题。实例证明,该算法能够快速有效地求得测试优化问题的最优解。     

遗传算法在求解最小生成树中的运用

以图论和遗传算法为基础,提出了求解最小生成树问题的遗传算法。该算法解决了常用二进制编码不能正确表达最小生成树的问题,利用Prufer数对生成树进行编码;在遗传操作中对变异算子进行了改进,避免了由于变异产生大量不可行解。从而提高了遗传算法的效率;通过数值试验,表明该算法简单,高效,收敛率高。     

图的Steiner最小树问题的混合遗传算法

图的Steiner最小树问题是经典的组合优化问题,在通信网络和电路设计中有广泛应用。文中在遗传算法的基础上,对交叉率pc和变异率pm采用自适应过程,构造一种新的确定pc和pm的公式,有效解决了参数选取对最终结果的影响问题。再与模拟退火算法相结合,提出了一种解决Steiner最小树问题的混合遗传算法。该算法克服了遗传算法易早熟和收敛性能差的缺点,有效地增强了算法的进化能力。通过对OR-Library的部分实例进行计算结果表明,在大多数情况下混合遗传算法比遗传算法有更好的性能。     

面向无线内容分发网络的树形拓扑生成算法

在无线内容分发网络中,为减轻骨干网络的传输压力,可将网络拓扑结构构建为以基站和Wi Fi接入点为根的若干棵最小生成树,并对生成树的深度和每个节点的度数进行约束。这种深度和度数约束的最小生成树问题是一个NP完全问题。针对该问题,首先提出能够生成优质近似解的启发式算法,该算法在不违反深度以及度数约束的情况下构建生成树,算法思想为在服务性节点相连的边中选择与当前生成树相连且权值最小的边加入生成树。然后在生成初始近似解的基础上采用定制的禁忌搜索算法和模拟退火算法对该近似解实施进一步优化。实验结果表明,在给定的约束条件下,禁忌搜索算法求得的解优于现有的遗传算法,在深度约束为4以及度数约束为10的条件下,解的改进幅度可达18.5%,所提算法的运行速度比遗传算法提高了10倍。     

Memetic算法在智能组卷问题中的应用

Memetic算法是一种启发式搜索方法,常用于解决一些NP问题。本文通过对遗传Memetic算法的改进与优化,结合智能组卷问题的特点,提出一套完整的解决方案。算法使用Memetic算法框架,全局搜索策略采用分段实数编码的遗传算法,融合了算法的交叉变异操作,局部搜索策略采用模拟退火算法,有效解决陷入局部最优问题。通过不同算法的对比实验表明,本文提出的Memetic算法能够快速高效地解决智能组卷问题,大大提升试卷生成质量,减少迭代次数,可快速获得最优解。      

求解多目标最小生成树的改进多目标蚁群算法

多目标最小生成树问题是典型的NP问题。针对此问题,提出一种改进的多目标蚁群算法。为获得更好的非劣前端,通过合理选取多个信息素扩散源与扩散策略来避免其早熟收敛,并引入非支配排序算子,提高种群多样性并避免算法过早陷入局部最优解。对比实验结果表明：对于多目标最小生成树问题,该算法是有效的,不但在求解效率和解的质量方面优于相关算法,而且随着问题规模的扩大,算法仍保持较好的性能。     

交通选线优化算法的设计与实现

将交通选线问题求解转化为最小生成树（Minimun Spanning Tree,MST）的求解,对比了经典MST求解算法,以图论为基础,采取一种求最小生成树的改进遗传算法．该算法以二进制编码表示最小树问题,用深度优先搜索算法进行图的连通性判断,并采用相应的适应度函数、单亲换位算子和单亲逆转算子及多种控制进化策略,能在一次遗传进化过程中获得一批最小生成树,可供决策部门综合评价与决策．     

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

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