蚁群算法.ppt

趋化性算法Chemotaxis Algorithm趋化性算法趋化性算法((CA)CA)趋化性算法(Chemotaxis Algorithm, CA)是模拟细菌生长过程中的趋光性原理而提出的一种随机优化方法,它与模拟退火算法有相似之处,但结构更加简单。CACA算法步骤算法步骤?Step 1 算法初始化随机产生一初始解i 作为当前解,计算其性能指标c(i);?Step 2 生成高斯分布的随机变量,用此随机变量对当前解进行扰动产生一个新解j IF c(j)<=c(i) THEN 接受j 为当前解ELSE 不接受j?如果满足算法的终止条件则终止算法,以当前解作为最优解输出,否则返回Step ,GA,CASA,GA,CA的性能比较的性能比较算法的性能SAGACA接受劣解的方式按概率接受交叉、变异不接受全局搜索能力较强较强较差局部搜索能力较强较强强收敛速度慢较快快主要存在问题最优性与时间矛盾超级个体封闭竞争易陷入局部极小搜索方式单点群体单点综合优化算法综合优化算法?启发式—GA算法?启发式—SA算法?综合SA,GA,CA,SAGAQCIA算法蚁群算法Ant Colony Algorithm蚂蚁群体的进化蚂蚁群体的进化–蚂蚁是最古老的社会昆虫,它的起源可追溯到1亿年前,大约与恐龙同一时代。–从化石蚁巢得的证据显示,高级的社会性组织给予昆虫社会进化的稳定性蚁群社会的组成蚁群社会的组成蚂蚁属膜翅目,蚁总科,已知360属,约9000种,估计应有12000—15000种。其中大多数种类(80%)在热带,亚热带。百万亿的蚂蚁悄悄地布满了我们的星球,象人类一样,蚁占据了几乎每一片适于居住的土地,只有永远雪封的冰山的南北两级未曾被其涉足。蚁虽然有成千累万种,但无一种是独居的,都是群体生活,建立了自己独特的蚂蚁社会。蚂蚁的特点蚂蚁的特点?蚁群是母系社会,以雌性为中心。?家族成员有:雌蚁、雄蚁、大工蚁、小工蚁和兵蚁。?严密的社会组织(组织、分工合作、相互通讯联系和信息传递)–合作–品级分化–个体利他蚂蚁的通讯手段蚂蚁的通讯手段————化学语言化学语言?信息激素(外激素)——蚂蚁平时行走时腹部挺起,当进入新地带或食物源时,腹部垂下,通过排泄口挤出直肠腺,沿着植物枝条或地面的路线放出信息激素,形成气味踪迹,同巢的蚂蚁就会闻讯赶到。?信息激素(外激素)的强度随时间延长而挥发。