程序实现---遗传算法与最小生成树算法解决旅行商问题分析对比
13页1、遗传算法与最小生成树算法解决旅行商问题分析对比摘要:本实验采用遗传算法实现了旅行商问题的模拟求解,并在同等规模问题上用最小生成树算法做了一定的对比工作。遗传算法在计算时间和占用内存上,都远远优于最小生成树算法。这间接证明了智能算法在解决大规模问题上性能优于传统算法程序采用 Microsoft visual studio 2008 结合 MFC 基本对话框类库开发。32 位 windows 7 系统下调试运行。引言遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,由密歇根大学的约翰霍兰德和他的同事于二十世纪六十年代在对细胞自动机(英文:cellular automata)进行研究时率先提出, 并于 1975 年出版了颇有影响的专著Adaptation in Natural and Artificial Systems ,GA这个名称才逐渐为人所知,约翰霍兰德教授所提出的 GA 通常为简单遗传算法(SGA) 。在二十世纪八十年代中期之前,对于遗传算法的研究还仅仅限于理论方面,直到在
2、伊利诺伊大学召开了第一届世界遗传算法大会。随着计算机计算能力的发展和实际应用需求的增多,遗传算法逐渐进入实际应用阶段。1989 年,纽约时报作者约翰马科夫写了一篇文章描述第一个商业用途的遗传算法-进化者(英文:Evolver) 。之后,越来越多种类的遗传算法出现并被用于许多领域中,财富杂志 500 强企业中大多数都用它进行时间表安排、数据分析、未来趋势预测、预算、以及解决很多其他组合优化问题。 遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出
3、越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation) ,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding) ,可以作为问题近似最优解1。遗传算法是借鉴生物界的进化规律(适者生存,优胜劣汰遗传机制)演化而来的。其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。遗传算法的这些性质,已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。综述:程序总体流程图:初始化算法参数创建初试基因组(种群) 生成点的序列,随机打乱进化得到最优基因组 输出程序运行的性能指标对大部分基因 进行单性繁殖自我进行两点交 叉变异排序基因组,最 好
《程序实现---遗传算法与最小生成树算法解决旅行商问题分析对比》由会员mg****85分享,可在线阅读,更多相关《程序实现---遗传算法与最小生成树算法解决旅行商问题分析对比》请在金锄头文库上搜索。
高中数学配套课件:第1部分 第二章 2.2 2.2.1 用样本的频率分布估计总体分布
高中数学必修2红对勾答案1-1-2-2
高中数学全程复习方略第二章 圆锥曲线与方程 章末总结 阶段复习课(共57张ppt)
高三文科数学一轮复习数列5--5
高一数学对数函数课件
马克思主义政党是工人阶级的先锋队
青岛版数学六年级上册第八单元百分数的整理和复习1
阿拉伯糖操纵子
逻辑基本规律1
选修4《化学反应速率和化学平衡》 第3节 化学平衡(5) 有关化学平衡常数及转化率的计算
辅修用 辅助费用分配
软件无线电 第3章 多模式调制解调
跳槽员工与辞退员工管理技巧及典型案例解析(ppt 40)
费用组成(工管、辅修、专升本)
财政学公共支出课件
苏教版数学四年级上册《平行和相交(一)》课件
船舶推进第2章 螺旋桨几何特征
自考第3章4调和函数
自动控制课件 第4章
育新小学 魏秀珍
2022-11-29 2页
2023-12-02 1页
2022-09-02 17页
2022-10-06 2页
2023-10-24 10页
2023-05-18 3页
2023-10-01 54页
2024-01-14 2页
2023-01-06 4页
2022-12-15 12页