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

文档介绍：遗传算法与群智能优化算法简介主要内容?智能优化算法简介?问题的NP-完全特性?常用的智能优化算法?遗传算法-ic Algorithm?群智能优化算法?蚁群优化算法-Ant Colony Optimization?粒子群优化算法-Particle Swarm Optimization?...北京交通大学计算机与信息技术学院22016-11-27智能优化算法简介?20世纪80年代以来,一些优化算法得到发展?GA、EP、ACO、PSO、SA、TS、ANN及混合的优化策略等?基本思想:模拟或揭示某些自然现象或过程?为用传统的优化方法难以解决的NP-完全问题提供了有效的解决途径?由于算法构造的直观性与自然机理,因而通常被称作智能优化算法(intelligent optimization algorithms),或现代启发式算法(meta-heuristic algorithms)?[智能优化算法及其应用,王凌,清华大学出版社,2001]北京交通大学计算机与信息技术学院32016-11-27智能优化算法简介- 问题的NP-完全特性?求解n个城市的TSP问题。?典型的组合优化问题,是NP-完全的?要准确求解该问题只能用枚举类的办法?要枚举的解的个数为(n - 1)!?例:n = 24,则要枚举的解的个数为:23!=25,852,016,738,884,976,640,000北京交通大学计算机与信息技术学院42016-11--11-27北京交通大学计算机与信息技术学院62016-11-27北京交通大学计算机与信息技术学院72016-11-27智能优化算法简介-常用的智能优化算法?遗传算法(ic Algorithm,GA)?演化规划(Evolutionary Programming,EP)?蚁群优化算法(Ant Colony Optimization,ACO)?粒子群优化算法(Particle Swarm Optimization,PSO)?模拟退火算法(Simulated Annealing,SA)?禁忌搜索算法(Tabu Search,TS)?人工神经网络(Artificial work,ANN)?…北京交通大学计算机与信息技术学院82016-11-27主要内容?智能优化算法简介?问题的NP-完全特性?常用的智能优化算法?遗传算法-ic Algorithm?群智能优化算法?蚁群优化算法-Ant Colony Optimization?粒子群优化算法-Particle Swarm Optimization?…北京交通大学计算机与信息技术学院92016-11-27遗传算法(ic Algorithm)?1975年,Holland出版了著名的《Adaptation in Natural and Artificial Systems》,标志着遗传算法的诞生。?在一定程度上解决了传统的基于符号处理机制的人工智能方法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难?基于“适者生存”原则,是并行优化算法,其自组织、自适应、自学****及群体进化的能力适合大规模复杂优化问题?将问题求解表示为“染色体”,通过选择(selection)、交叉(crossover)和变异(mutation)操作的迭代,实现种群的演化,最后终收敛到“最适应环境”的个体,从而求得问题的最优解(满意解)北京交通大学计算机与信息技术学院102016-11-27