6.3蚁群算法教程.ppt

*;6.4 蚁群算法;6.4 蚁群算法;在非洲的大草原上，如果你发现羚羊在奔逃，那一定是狮子来了；如果见到狮子在躲避，那一定是象群在发怒了；如果见到成百上千的狮子和大象集体逃命的壮观景象，那是什么来了呢;--regulation of nest temperature within 1 degree celsius range; --forming bridges;;A living bridge;--regulation of nest temperature within 1 degree celsius range; --forming bridges; --raiding specific areas for food; --building and protecting nest; --sorting brood and food items; --cooperating in carrying large items;;Co-operative carrying;--regulation of nest temperature within 1 degree celsius range; --forming bridges; --raiding specific areas for food; --building and protecting nest; --sorting brood and food items; --cooperating in carrying large items; --emigration of a colony; --finding shortest route from nest to food source;; ;蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。;本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。;假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1;寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1; 若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1;若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线;蚁群算法是一种由自然界真实蚂蚁觅食行为提炼而 成的优化算法，于1991年，由意大利学者M.Dorigo在其博士论文中提出，并成功的解决了旅行商(TSP)问题;1998年10月在比利时布鲁塞尔召开了第一届蚁群算法国际研讨会(ANTS)，标志着蚁群算法的正式国际化;6.4 蚁群算法;6.4.2 蚁群算法基本步骤;6.4.2 蚁群算法基本步骤;6.4.2 蚁群算法基本步骤;Tour 循环(内循环)过程详解— 1.（初始化生成N个蚂蚁）;;;;;;;6.4.2 蚁群算法基本步骤;;6.4.2 蚁群算法基本步骤;;6.4.2 蚁群算法基本步骤;6.4.2 蚁群算法基本步骤;Ant System (Ant Cycle) Dorigo [1] 1991;1. 精英策略(Elitist strategy);2. 考虑信息素的挥发(pheromone evaporation);6.4 蚁群算法;; 定义蚁群优化算法的每步迭代对应随机变量为： ; 定义蚁群优化算法的每步迭代对应随机变量为： ; 证明分析: 蚁群算法中,一但达到全局最优,由 只记录第一个最优解.证明分三部分: 证明以概率1达到一个最优路径 证明(1)上式成立 证明以概率1收敛到一个最优路径;;;;;随机过程以概率1达到一条最优路径.当某条最优路径Z在第k次循环被首次走到后,在第k+1轮循环按信息素的更新原则,可以用归纳法证明,对于任意;;;;6.4 蚁群算法;Problem Name