共查询到19条相似文献,搜索用时 187 毫秒
1.
基于递阶遗传算法的最小加权完工时间并行机调度 总被引:1,自引:0,他引:1
针对最小化加权完工时间的等同和非等同并行多机调度一类问题,提出了一种递阶遗传算法.该算法根据问题的特点,采用一种染色体递阶编码方案,此编码与调度方案一一对应.计算结果表明,递阶遗传算法是有效的,能适用于大规模等同和非等同并行多机调度问题,通过与Cheng所作编码的遗传算法比较,用递阶遗传算法优化并行机调度操作简单并且收敛速度快. 相似文献
2.
基于差分进化算法的多旅行商问题优化 总被引:4,自引:1,他引:3
针对所有旅行商路径最大值最小的多旅行商问题,提出改进的差分进化算法优化.在该优化方法中,编码采用实数编码;改进的差分进化算法采用轮盘赌选择;根据旅行商问题的特点,在差分进化算法中增加邻域搜索算子.该方法适于距离对称和非对称的多旅行商问题求解.以距离非对称的多旅行商问题的实例进行了仿真和比较,可以看出所提出的改进差分用来解决多旅行商这类离散组合优化问题是有效的. 相似文献
3.
为优化生物反恐条件下的应急物资配送过程,将该环境下的应急物资配送问题构造为一多旅行商问题(MTSP),并从理论上分析了该旅行商回路为最短Hamilton路径。以此问题为背景,针对应用传统遗传算法求解多旅行商问题时存在收敛速度缓慢等问题,提出并设计了一类新的混合遗传算法。该类新遗传算法与传统遗传算法的最主要区别在于,针对多旅行商问题专门设计了一种新的染色体编码规则、排序算子和交叉算子。仿真结果表明,该算法能够快速收敛到问题的近似最优解,并能很好地维持种群的多样性。 相似文献
4.
混合递阶遗传算法优化小波神经网络的研究 总被引:3,自引:1,他引:3
在研究小波神经网络结构及其学习算法的基础上,提出了一种以混合递阶遗传算法优化小波神经网络的新方法,混合递阶遗传算法是递阶遗传算法和多元线性回归的结合。此方法可同时优化小波神经网络的结构及其参数,具有学习速度快,精度高的特点。并与传统的BP算法进行了对比,证明了本算法的有效性。 相似文献
5.
基于仿真的遗传算法求解动态旅行商问题 总被引:1,自引:0,他引:1
以标准旅行商问题的扩展问题--动态旅行商问题为对象,分析了动态旅行商问题中由于道路流量实时变化所引起的标准旅行商问题的数学建模与优化求解的问题复杂性.通过建立其计算机仿真模型再现动态旅行商问题中众多复杂的非平稳、随机因子.进而提出了基于计算机仿真模型的遗传算法,即根据计算机仿真的结果,应用改造后的遗传算法搜索原问题的优化解.最后,在多智能体仿真平台上实现该优化算法,并以此求解20个城市的动态旅行商问题,计算结果验证了算法的有效性. 相似文献
6.
提出了一种将递阶遗传算法和奇异值分解的优点相结合的新型径向基神经网络学习算法--混合递阶遗传算法。它具有较高的学习效率,并能同时确定径向基神经网络的结构和参数。利用所提出的混合递阶遗传算法对混沌时间序列学习和预测,取得了较好的效果。 相似文献
7.
多目标旅行商问题(MOTSP)是经典旅行商问题的扩展,其优化目标包含了距离、成本、收益及风险等多个相互冲突的指标.本文提出了一种基于偏好的Pareto演化算法p-PEA用于建模并求解此NP-hard问题.该优化算法建立在MOTSP的智能体仿真模型之上,从而解决了数学建模不能真实再现实际MOTSP中众多影响因素的问题.通过仿真的方法,算法能够得到MOTSP可行解的各项评价指标值.在此基础士,通过设计演化算法搜索问题的Pareto优化解集.其中,将决策者的决策偏好信息引入到Pareto优化解集的求解过程中,所得结果将更合理.最后,以一个130个城市的旅行商问题为例验证了算法的有效性. 相似文献
8.
解旅行商问题的一个新的遗传算法 总被引:2,自引:1,他引:2
对旅行商(TSP)问题设计了一个新的遗传算法.首先,对n个城市的旅行商问题设计了一个新的编码方法,并且对这种编码方法,给出了简便的解码方法.其次,针对编码的特点,设计了一种新的、有效的杂交算子和变异算子,这些算子均能直接产生可行的后代.为提高杂交算子的搜索能力,结合了一个局部搜索技术来改进杂交算子.在此基础上,提出了求解TSP的一个新的遗传算法,并证明了其全局收敛性.为了验证算法的有效性,对10个国际标准算例(城市规模从14到1000)进行了计算机仿真,结果表明算法是有效的. 相似文献
9.
10.
旅行商问题(Traveling Salesman Problem,简称TSP)是一个典型的组合优化问题,而且是一个NP完全问题。遗传算法(Genetic Algorithm,简称GA)是求解组合优化问题的行之有效的算法。但遗传算法并不是一个完美无缺的算法,它最突出的问题是早熟现象。在解决像旅行商这类组合优化中的NP完全问题。是极易陷入早熟收敛,城市规模越大越难求得最优解。如何缓和旅行商问题中的早熟现象。使问题的解尽可能接近最优解.这是本文研究的主要内容。本文在分形法的基础上提出.了一种分形法与范例库推理相结合的改进方法用以求解TSP问题。首先建立范例库,选取其中优良的个体来指导城市规模大的旅行商问题进行合理的区域分割,由于优良个体与最优值的结构大体相同,相似度大,故可以有效地实施“分而治之”的策略。在寻优进化过程中,还要对范例库进行更新与维护。通过对TSPLIB测试库中的eil51、eil101、ch130和ch150问题的求解,说明该方法在求解TSP问题上是行之有效的。 相似文献
11.
遗传算法求解旅行商问题时的基因片段保序 总被引:15,自引:0,他引:15
针对基于遗传算法的 TSP问题求解 ,尝试了多种遗传操作 ,分析了这些操作在遗传算法中的作用 ,讨论了基因片段保序在利用遗传算法求解 TSP问题中的重要性 . 相似文献
12.
小规模TSP边集裁剪策略研究 总被引:1,自引:0,他引:1
由于旅行商问题的计算复杂性,随着问题规模的扩大,精确算法逐渐不能在较短的时间内得到或不能得到问题的全局最优解.通过对该类问题的高质量优化解与全局最优解之间关系的分析,基于概率统计原理建立了问题的简化初始边集,并在分支裁减法中应用了合理的动态上界调整,新建立的混合分支裁减法实现了对小规模旅行商问题的快速精确求解. 相似文献
13.
求解度限制最小生成树问题的启发式遗传搜索算法 总被引:5,自引:1,他引:4
CM(1,1)模型一般以模型还原值与实际值平均相对误差检验模型的模拟精度。本文以模型还原值与实际值平均相对误差最小化为目标函数将CM(1,1)模型转化成一个不用进行灰微分方程参数辨识的优化模型,称之为改进的GM(1,1)模型,简称IGM(1,1)。IGM(1,1)避开了灰微分方程参数辨识时传统的优化无法求解,本文针对IGM(1,1)模型的直接建模。由于IGM(1,1)目标函数非连续,不可导,用传统的优化无法求解,本文针对IGM(1,1)模型的模拟特性设计了求解该优化模型的遗传算法并进行了算例验证,秋解结果表明了IGM(1,1)模型IGM(1,1)模型。 相似文献
14.
遗传算法与禁忌搜索算法的混合策略 总被引:30,自引:0,他引:30
遗传算法与禁忌搜索算法的出现为解决高维组合优化问题提供了强有力工具.二者既有共性,又有个性.通过对遗传算法与禁忌搜索算法的分析,提出了一种遗传算法与禁忌搜索算法的混合策略,把禁忌搜索算法独有的记忆思想引入到遗传算法的搜索过程中,构造了新的重组算子,并把禁忌搜索算法作为遗传算法的变异算子,对旅行商问题的求解表明:混合策略在许多方面优于遗传算法. 相似文献
15.
求解度约束最小生成树的单亲遗传算法 总被引:6,自引:0,他引:6
宋海洲 《系统工程理论与实践》2005,25(4):61-66
提出了求解度约束最小生成树问题的单亲遗传算法.该算法首先利用Prufer数对生成树进行编码;然后精心地设计了一个随机地产生初始种群的方法,用这种方法产生的初始种群,不会含有任何不可行解;在遗传操作中只使用选择和变异操作,共设计了三种变异操作,其中两种变异操作均不会产生不可行解,只有一种变异操作可能会产生不可行解,需要作树的度的检查和修改;这样就大大的降低了不可行解产生的机会,从而提高了遗传算法的效率;而且只使用变异算子,有效的避免了早熟收敛现象的产生;通过大量的数值试验,表明该算法简单,高效,收敛率高;最后对此算法做了适当推广,并给出了它求解TSP问题的具体步骤和实例。 相似文献
16.
刘永红 《系统工程与电子技术》2002,24(11):123-126
最优聚丛原理是解决算法集和演算集极小化问题、NP完全问题的一个基本的计算复杂性原理 ,引入了稠密、有洞算法概念。以此为基础 ,提出了GED聚丛法 ,它是几何算法G、生态算法E和判定问题D的近似演算等三方面合力求解旅行商问题 (TSP)的方法。给出了求解TSP流程及实例 ,计算结果验证了该原理和方法的正确性和精巧性。 相似文献
17.
一种基于能量熵的快速遗传算法研究 总被引:4,自引:0,他引:4
在分析标准遗传算法的优越性与存在不足的基础上,提出了对遗传算法的改进方法.将能量熵的选择加入到遗传算法的退火选择中,以充分地探索解空间,保持种群的多样性.将伪梯度搜索应用于对个体的邻域搜索,利用当前种群的有效信息及系统信息,提高寻优速度.对典型的TSP问题及一实际电力网络故障恢复的仿真研究表明,改进算法全局优化性能优于启发式遗传算法及标准、退火遗传算法,同时使收敛速度有了较大的提高. 相似文献
18.
求解TSP的改进人工鱼群算法 总被引:2,自引:0,他引:2
利用遗传算法的交叉算子,并引入去交叉策略,对人工鱼群算法进行了改进,提出了一种改进型人工鱼群算法,并将该算法用于求解旅行商问题(traveling salesman problem,TSP)这一经典的NP难问题。通过实验仿真与目前TSP已知最优解进行对比分析,结果表明,改进后的人工鱼群算法在种群规模较小,迭代次数较少的情况下也可以收敛到已知最优解。 相似文献