共查询到20条相似文献,搜索用时 203 毫秒
1.
文化基因算法在多约束背包问题中的应用 总被引:1,自引:0,他引:1
刘漫丹 《计算技术与自动化》2007,26(4):61-63,67
文化基因算法是一种启发式算法,与一些经典数学方法相比,更适于求解多约束背包问题.文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,针对多约束问题,提出采用贪婪策略通过违反度排序的方法处理多约束条件,全局搜索采用遗传算法,局部搜索采用模拟退火策略,解决具有多约束条件的0-1背包问题.通过对几个实例的求解,表明文化基因算法与标准遗传算法相比,具有更优的搜索性能. 相似文献
2.
混合遗传算法在路径选择问题的应用 总被引:2,自引:0,他引:2
本文建立单配送中心的物流配送路径优化问题的数学模型,并针对遗传算法在局部搜索能力方面的不足,提出将禁忌搜索启发式与遗传算法相结合,并在编码时引入虚拟配送点,从而构造了求解物流配送路径优化问题的混合遗传算法,并进行了试验计算。计算结果表明该算法是很有效的。 相似文献
3.
通过对求解虚拟企业资源结盟博弈问题与求解经典SAT问题相似性的分析,提出了一种求解虚拟企业资源结盟博弈的启发式群智能优化算法.算法融合萤火虫优化算法与布谷鸟优化算法部分原理,并设计可行的交叉算子以及变异优化算子,能够修复不可行解并保持种群多样性.实验结果表明本文算法的迭代次数与搜索到的稳定联盟数成线性增长,较启发式遗传算法有着更好的爬山性能和搜索能力. 相似文献
4.
多星测控调度是一个具有大搜索空间的多峰问题。针对简单遗传算法求解易陷入局部最优和不稳定的缺陷,借鉴分散搜索多样化采样、局部寻优的特点,提出一种基于分散搜索的混合遗传算法,在全局的随机搜索中嵌入全局的定向搜索。在描述问题的基础上,提出可进行细粒度搜索的可行解表示方式,构建算法的整体流程,并设计由输入参数控制的多样化初始集产生方法、基于质量和多样性原则的参考集生成和更新方法、吸取被组合个体优良成份的解组合方法及基于启发式局部搜索的解提高方法等算法要素。仿真表明新算法在求解质量上比简单遗传算法有明显提高。 相似文献
5.
研究三维空间机器人路径规划问题,由于系统求解时间较长、过早失去解的多样性、易陷入局部最优、个体适应度较差等问题,通过构建三维工作空间模型、引入变异算子和搜索无碰路径策略来解决,提出适宜于三维机器人路径规划的一种变异算子蚁群算法(Mutation Operator Ant Colony Algorithm,MOACA)。MOACA是一种关于模型构造的启发式搜索算法,算法在改进启发式函数设计、选择概率确定、信息素更新策略等基础上,引入逆转变异和插入变异算子,通过选择逆转点反序排列部分路径节点和随机插入路径节点的方法搜索无碰路径,对蚁群算法进行了局部优化改良。仿真结果表明,MOACA在搜索路径、收敛时间、适应度等方面较传统蚁群算法有明显改善,算法是有效可行的。 相似文献
6.
最大团问题的改进遗传算法求解 总被引:1,自引:0,他引:1
最大团问题是组合优化中经典的NP完全问题,该问题的枚举算法只适用于求解中小规模的图。提出了基于遗传算法的最大团问题求解算法,引入概率模型指导变异产生新的个体,并结合启发式局部算法搜索最大团。经算例测试,获得了较好的效果。 相似文献
7.
带时间窗车辆路径问题的文化基因算法 总被引:1,自引:0,他引:1
针对物流配送中带时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),建立了数学模型,并设计了求解VRPTW的文化基因算法。种群搜索采用遗传算法的进化模式,局部搜索采用禁忌搜索机制,并结合可行邻域结构避免对不可行解的搜索,以提高搜索效率。与单纯的遗传算法和禁忌搜索算法进行对比实验,表明该算法是求解VRPTW的一种有效方法。 相似文献
8.
为解决传统遗传算法求解带容量约束的车辆路径问题时收敛速度慢和局部搜索能力差的问题,对传统遗传算法提出一种改进策略。使用基于贪婪策略的启发式交叉算子加强算法接近最优解的能力,加快算法收敛速度,在变异操作中,引入最近邻搜索算子,缩小基因变异范围,使用单点局部插入算子提高算法的局部优化能力。采用精英选择和轮盘赌法结合的选择策略,保持种群多样性以加强算法的全局搜索能力。实例计算测试表明,与传统遗传算法相比,所提算法求解平均偏差降低了70.25%,求解时间减少了87.41%;与ALNS和AGGWOA算法相比,有更高的求解质量和更好的稳定性。 相似文献
9.
蚁群算法与遗传算法对TSP的一种融合 总被引:1,自引:0,他引:1
蚁群算法是通过信息素的累积和更新收敛于最优路径上,求解速度慢,而遗传算法具有快速随机的局部搜索能力。为此本文将遗传算法和蚁群算法相融合,给出一种改进的算法并用于TSP问题的求解。在问题求解中,用蚁群算法迭代每只蚂蚁走过的路径序列作为遗传算法的初始种群,克服随机选择的盲目性,从而提高算法的性能。模拟结果显示该算法是有效的和可行的。 相似文献
10.
11.
为了减少救灾物资配送的延误时间和救灾车辆的总运输时间,引入紧急度的概念,建立了基于紧急度的救灾物资车辆路径问题模型,并设计了一种改进遗传算法对该模型进行求解。首先,采用多种策略生成初始种群;然后,提出一种基于紧急度的任务再分配算法作为局部搜索算子,该算法依据紧急度为延误安置点重新安排配送车辆或调整配送顺序从而减少延误时间,对无延误的车辆优化其路线从而减少总运输时间,以达到延误时间和总运输时间两者最优。在17个数据集上与先来先服务(FCFS)算法、按紧急度排序(URGS)算法和遗传算法(GA)三种算法进行了对比。实验结果表明,具有基于紧急度的任务再分配策略的遗传算法(TRUD-GA)与GA相比,平均延误时间减少25.0%,平均运输时间减少1.9%,与FCFS、URGS算法相比改进则更加明显。 相似文献
12.
考虑多种运输方式的整车物流服务供应链订单分配问题 总被引:1,自引:0,他引:1
针对整车物流服务供应链的订单分配问题,提出了考虑多种运输方式的双层订单分配模型。首先,考虑到运输方式会影响运输成本、客户的准时送达要求等因素,建立以准时送达和最小化物流采购成本为目标的双层规划模型;其次,设计启发式算法(HA)确定各运输方式的任务量;然后,借助混合蛙跳算法(SFLA)求解各功能物流服务提供商间各运输方式的任务量分配;最后,通过不同规模的算例与遗传算法(GA)、粒子群算法(PSO)、蚁群算法(ACO)等进行求解对比。算例结果表明,与原有的成本438万元相比,所提模型得到显著优化的421万元,说明所构建模型的订单分配方案能够更有效解决整车物流的订单分配问题。实验对比表明,较传统智能算法(GA、PSO、ACO)的求解结果,两阶段的HA-SFLA算法能更快得出显著优化的结果,说明HA-SFLA算法能更好地求解考虑运输方式的双层订单分配规划模型。在满足客户送达时间要求的同时,考虑运输方式的双层订单分配模型及算法显著降低物流成本,促进物流集成商为获取更多利益而在订单分配阶段考虑运输方式。 相似文献
13.
针对具有机器柔性和机床折旧特性的柔性作业车间调度问题(FJSP),为了降低生产过程的能耗,建立了以最大完工时间和能耗加权的和最小为优化目标的数学模型,并提出了一种改进遗传算法(IGA)。首先,根据遗传算法(GA)随机性强的特点,引入正交试验的均衡分散原则生成初始种群,用于提高在全局范围的搜索性能;然后,为了克服交叉操作后的基因冲突,采用三维实数的编码方式并结合双个体算术交叉用于染色体交叉,减少了冲突检测步骤,提高了求解速度;最后,在变异操作阶段采用了动态步长的方式进行基因变异,保证了全局范围内的局部搜索能力。通过对8个Brandimarte算例进行仿真测试,并与近年来3个改进启发式算法进行对比,计算结果表明该算法求解FJSP的有效性和可行性。 相似文献
14.
在利用串行调度启发式方法解决资源受限的运输任务调度问题(RCTTSP)的基础之上,提出了一种混合遗传算法(HGA)。该算法通过对运输任务执行优先次序进行基因编码,利用串行调度方法获得初始种群,并在遗传个体调度目标值与适应值确定的过程中使用了局部搜索启发式规则,从而充分地结合了遗传算法的全局搜索与启发式方法的局部搜索能力。首先对RCTTSP进行了描述,给出了混合遗传算法的基本原理,然后针对测试案例进行实现,并与单纯使用串行调度方法进行了比较。结果显示,该混合遗传算法能有效地改进调度效果。 相似文献
15.
针对最小生成树问题,提出了一种小生境遗传禁忌算法。算法中使用Prfer数对生成树进行编码。在选择交叉之前使用小生境技术,使得被选中交叉的个体之间的适应值的距离大于一定的阈值,从而保证了个体的多样性。遗传变异算子使用禁忌搜索算法,提高了遗传算法的局部搜索能力,加快了算法的收敛速度。模拟实验结果证明该算法是有效的。 相似文献
16.
17.
服务级别协议(SLA)等级感知的服务选择是NP难题。针对服务选择中维度与粒度方面的问题,提出结合语义与事务属性的服务质量(QoS)感知的服务优化选择模型。该模型从语义链接匹配度、QoS与事务三个维度对服务进行优化选择,并设计了支持多粒度的编码策略。针对服务选择中时间复杂度高的问题,提出了克隆选择与遗传算法相结合的混合优化算法。该算法首先采用动态适应度函数,逐代淘汰不满足约束的个体;其次给出了事务属性的优先级,并根据优先级设计了知识启发式的交叉与变异算子,以保证个体满足事务属性要求;最后在遗传算法中对优秀个体进行克隆选择,以增强对最优解的搜索能力。仿真实验中,该算法在服务选择的精确度和成功率方面均优于遗传算法;在时间花费上稍高于遗传算法但远低于穷举法。实验结果表明,所提算法能在较少时间花费的基础上保证服务选择的质量。 相似文献
18.
员工技能熟练程度对现场服务调度问题(FSSP)的执行效率有极大影响,现有研究中未考虑员工技能因素。针对上述问题,首先以员工的旅行时间、服务时间和等待时间为优化目标,建立考虑员工技能熟练程度的FSSP模型;然后,提出混合果蝇优化算法(HFOA)对该模型进行优化求解,根据问题特征和算法特点,设计了基于矩阵的编码方法;定义了两类矩阵操作,提出了3种搜索算子,重构了果蝇优化算法(FOA)的嗅觉搜索和视觉搜索过程;为了提升算法性能,构造了基于最邻近插入启发式算法的初始化算子;最后,通过典型实例对算法进行了仿真实验,并与遗传算法(GA)、贪婪随机自适应搜索过程(GRASP)算法进行了比较。实验数据显示,与其他两种算法相比,HFOA在均值和最优值方面表现更优秀。结果表明改进初始化方法和搜索策略后,HFOA在优化的精度和稳定性上优于其他算法。 相似文献
19.
20.
Generation bidding strategy in a pool based electricity market using Shuffled Frog Leaping Algorithm
In an electricity market generation companies need suitable bidding models to maximize their profits. Therefore, each supplier will bid strategically for choosing the bidding coefficients to counter the competitors bidding strategy. In this paper optimal bidding strategy problem is solved using a novel algorithm based on Shuffled Frog Leaping Algorithm (SFLA). It is memetic meta-heuristic that is designed to seek a global optimal solution by performing a heuristic search. It combines the benefits of the Genetic-based Memetic Algorithm (MA) and the social behavior-based Particle Swarm Optimization (PSO). Due to this it has better precise search which avoids premature convergence and selection of operators. Therefore, the proposed method overcomes the short comings of selection of operators and premature convergence of Genetic Algorithm (GA) and PSO method. Important merit of the proposed SFALA is that faster convergence. The proposed method is numerically verified through computer simulations on IEEE 30-bus system consist of 6 suppliers and practical 75-bus Indian system consist of 15 suppliers. The result shows that SFLA takes less computational time and producing higher profits compared to Fuzzy Adaptive PSO (FAPSO), PSO and GA. 相似文献