遗传算法与蚁群算法简介.ppt

《遗传算法与蚁群算法简介.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、遗传算法与群智能优化算法简介主要内容智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization...北京交通大学计算机与信息技术学院22021/9/2智能优化算法简介20世纪80年代以来，一些优化算法得到发展GA、EP、ACO、PSO、SA、TS、ANN及混合的优化策略等基本思想：模拟或揭示某些自然现象或过程为用传统的优化方法难以解决的NP-完全问题提供了有效的解决途径

2、由于算法构造的直观性与自然机理，因而通常被称作智能优化算法（intelligentoptimizationalgorithms），或现代启发式算法（meta-heuristicalgorithms）[智能优化算法及其应用，王凌，清华大学出版社，2001]北京交通大学计算机与信息技术学院32021/9/2智能优化算法简介-问题的NP-完全特性求解n个城市的TSP问题。典型的组合优化问题，是NP-完全的要准确求解该问题只能用枚举类的办法要枚举的解的个数为(n-1)!例：n=24，则要枚举的解的个数为：23!=25,852,016,738,884

3、,976,640,000北京交通大学计算机与信息技术学院42021/9/2n2425262728293031时间1s24s10m4.3h4.9d136.5d10.8y325y北京交通大学计算机与信息技术学院52021/9/2北京交通大学计算机与信息技术学院62021/9/2北京交通大学计算机与信息技术学院72021/9/2智能优化算法简介-常用的智能优化算法遗传算法（GeneticAlgorithm，GA）演化规划（EvolutionaryProgramming，EP）蚁群优化算法（AntColonyOptimization，ACO）粒子群

4、优化算法（ParticleSwarmOptimization，PSO）模拟退火算法（SimulatedAnnealing，SA）禁忌搜索算法（TabuSearch，TS）人工神经网络（ArtificialNeuralNetwork，ANN）…北京交通大学计算机与信息技术学院82021/9/2主要内容智能优化算法简介问题的NP-完全特性常用的智能优化算法遗传算法-GeneticAlgorithm群智能优化算法蚁群优化算法-AntColonyOptimization粒子群优化算法-ParticleSwarmOptimization…北京交通大学

5、计算机与信息技术学院92021/9/2遗传算法(GeneticAlgorithm)1975年，Holland出版了著名的《AdaptationinNaturalandArtificialSystems》，标志着遗传算法的诞生。在一定程度上解决了传统的基于符号处理机制的人工智能方法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难基于“适者生存”原则，是并行优化算法，其自组织、自适应、自学习及群体进化的能力适合大规模复杂优化问题将问题求解表示为“染色体”，通过选择（selection）、交叉（crossover）和变异（mutation）操

6、作的迭代，实现种群的演化，最后终收敛到“最适应环境”的个体，从而求得问题的最优解（满意解）北京交通大学计算机与信息技术学院102021/9/2遗传算法-简单遗传算法简单遗传算法（SimpleGeneticAlgorithms，SGA），又称基本遗传算法、标准遗传算法基于二进制编码，是最基本的遗传算法，其遗传进化操作过程简单、容易理解，是其他遗传算法的雏形和基础三种基本操作选择：通常用比例选择，即选择概率正比于个体的适配值，使适配值高的个体在下一代中被选中的概率大，提高种群平均适配值交叉：交换两父代个体的部分信息构成后代个体，使得后代继承父代

7、的有效模式，有助于产生优良个体变异：随机改变个体中的某些基因，有助于增加种群多样性，避免早熟收敛北京交通大学计算机与信息技术学院112021/9/2北京交通大学计算机与信息技术学院122021/9/2随机产生N个个体构成初始种群P(0),令k=0对种群P(k)中各个体进行评价终止？令m=0从种群中选择两个体rand()>pc将所选个体作为临时个体对临时个体以概率pm执行变异操作，产生两个新个体并放入P(k+1)中，令m=m+2对选中个体执行交叉操作生成两个临时个体输出优化结果m

8、率大，即被选中用来繁殖下一代的概率大。常用的选择方法有：比例选择（轮盘选择）基于排名的选择：由好到坏排序，然后以一定方式给每一个体分配选择概率（线性、非线性等方式，要求好的个体被