没有合适的资源?快使用搜索试试~ 我知道了~
首页遗传算法中局部优化操作对旅行商问题性能的影响
本文档深入探讨了遗传算法在旅行商问题(Traveling Salesman Problem, TSP)中的性能分析,特别是在局部优化操作部分应用的影响。TSP是一个著名的组合优化难题,由于其实际应用广泛,如物流路线规划、网络设计等,吸引了众多研究者研发各种启发式算法和精确解法。该研究的主要目标是评估遗传算法与局部优化器的混合策略在解决不同规模城市数量(76至439个)的TSP实例时的效果。 作者米兰·约尔杰维奇、马可·格鲁戈维奇和安德烈·布罗尼克来自斯洛文尼亚普里莫尔斯卡大学的信息科学和技术部门,他们关注的是如何在遗传算法的不同阶段(初始、随机或最后)融合局部优化器,以及这种混合策略对算法性能的影响。研究方法包括对不同混合频率和应用时间点进行实验,以期找到最有效的优化策略。 实验结果显示,混合策略的频率和应用时机对于解决TSP问题具有显著影响。较少的混合可能会导致算法收敛速度减慢,而过度频繁的混合可能导致搜索空间过度细化,降低全局最优解的探索效率。通过对不同情况的测试,研究人员试图找到一个平衡点,以提高算法在大规模TSP问题上的性能。 这篇论文不仅提供了关于遗传算法与局部优化器结合策略的深入洞察,还为TSP问题的实际求解提供了一种可能的改进方案,有助于优化问题求解的效率和精度。对于那些在优化领域工作或者对TSP有研究兴趣的人来说,这篇文章提供了有价值的经验教训和实践指导。
资源详情
资源推荐
Vol. 3 No.1. / June 2012
14
Business Systems Research
Performance analysis of the partial use of a local
optimization operator on the genetic algorithm for
the Travelling Salesman Problem
Milan Djordjevic, Marko Grgurovič and Andrej Brodnik
Department of Information Science and Technology, University of Primorska, Koper, Slovenia
Background: The Travelling Salesman Problem is an NP-hard problem in combinatorial optimization
with a number of practical implications. There are many heuristic algorithms and exact methods for
solving the problem. Objectives: In this paper we study the inuence of hybridization of a genetic
algorithm with a local optimizer on solving instances of the Travelling Salesman Problem. Methods/
Approach: Our algorithm uses hybridization that occurs at various percentages of generations of a
genetic algorithm. Moreover, we have also studied at which generations to apply the hybridization
and hence applied it at random generations, at the initial generations, and at the last ones. Results:
We tested our algorithm on instances with sizes ranging from 76 to 439 cities. On the one hand, the
less frequent application of hybridization decreased the average running time of the algorithm from
14.62 sec to 2.78 sec at 100% and 10% hybridization respectively, while on the other hand, the quality
of the solution on average deteriorated only from 0.21% till 1.40% worse than the optimal solution.
Conclusions: In the paper we have shown that even a small hybridization substantially improves the
quality of the result. Moreover, the hybridization in fact does not deteriorate the running time too
much. Finally, our experiments show that the best results are obtained when hybridization occurs in
the last generations of the genetic algorithm.
Keywords: genetic algorithm, travelling salesman problem, hybridization, optimization, grafted
genetic algorithm
JEL classication: C61
Paper type: Research article
Recieved: 28, April, 2012
Revised: 30, May, 2012
Accepted: 29, June, 2012
Citation: Djorjevic, M., Grgurović, M., Brodnik, A. (2012). “Performance analysis of the partial use of a
local optimization operator on the genetic algorithm for the Travelling Salesman Problem”, Business
Systems Research, Vol. 3, No. 1, pp. 14-22.
DOI: 10.2478/v10305-012-0002-4
Introduction
Genetic Algorithms (GA) use mechanisms inspired by biological evolution (Holland, 1975; Haupt and Haupt,
2004). They are applied on a nite set of individuals called population. Each individual in a population
represents one of feasible solutions in a search space. Mapping between genetic codes and the search
space is called encoding and can be binary or over some alphabet of higher cardinality. Good choice
of encoding is a prime condition for successful application of a genetic algorithm. Each individual in the
population is assigned a value called tness. Fitness represents a relative indicator of quality of an individual
compared to other individuals in the population. Selection operator chooses individuals from the current
population and takes the ones that are transferred to the next generation. Thereby, individuals with better
tness are more likely to survive in the next generation. The recombination operator combines parts of
genetic code of the individuals (parents) into codes of new individuals (offspring).
The components (operators) of the genetic algorithm software system are: Genotype, Fitness function,
Recombinator, Selector, Mater, Replacer, Terminator, and in our system (Local) Optimizer which is a new
extended component.
Abstract
Unauthenticated
Download Date | 1/8/18 3:28 PM
下载后可阅读完整内容,剩余8页未读,立即下载
YuCV
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- JavaScript DOM事件处理实战示例
- 全新JDK 1.8.122版本安装包下载指南
- Python实现《点燃你温暖我》爱心代码指南
- 创新后轮驱动技术的电动三轮车介绍
- GPT系列:AI算法模型发展的终极方向?
- 3dsmax批量渲染技巧与VR5插件兼容性
- 3DsMAX破碎效果插件:打造逼真碎片动画
- 掌握最简GPT模型:Andrej Karpathy带你走进AI新时代
- 深入解析XGBOOST在回归预测中的应用
- 深度解析机器学习:原理、算法与应用
- 360智脑企业内测开启,探索人工智能新场景应用
- 3dsmax墙砖地砖插件应用与特性解析
- 微软GPT-4助力大模型指令微调与性能提升
- OpenSARUrban-1200:平衡类别数据集助力算法评估
- SQLAlchemy 1.4.39 版本特性分析与应用
- 高颜值简约个人简历模版分享
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功