Chinaunix首页 | 论坛 | 博客
  • 博客访问: 89934
  • 博文数量: 22
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 445
  • 用 户 组: 普通用户
  • 注册时间: 2013-04-11 22:57
文章分类
文章存档

2013年(22)

我的朋友

分类: 信息化

2013-05-12 13:37:33

    集体智慧即群智。单一个体所做出的决策往往会比起多数决的决策来的不精准,集体智慧是一种共享的或者群体的智能,以及集结众人的意见进而转化为决策的一种过程。它是从许多个体的合作与竞争中涌现出来的。集体智慧在细菌、动物、人类以及计算机网络中形成,并以多种形式的协商一致的决策模式出现。对于集体智慧的研究,实际上可以被认为是一个属于社会学、商业、计算机科学、大众传媒和大众行为的分支学科——研究从夸克层次到细菌、植物、动物以及人类社会层次的群体行为的一个领域。
    集体智慧中常用的算法有蚁群算法,粒子群算法,人工鱼群算法,遗传算法等。接下来介绍这四种算法。
    蚁群算法((Ant Colony Optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。
    蚁群算法已应用于许多组合优化问题,包括蛋白质折叠或路由车辆的二次分配问题,很多派生的方法已经应用于实变量动力学问题,随机问题,多目标并行的实现。它也被用于产生货郎担问题的拟最优解。在图表动态变化的情况下解决相似问题时,他们相比模拟退火和遗传算法方法有优势;蚁群算法可以连续运行并适应实时变化。这在网络路由和城市交通系统中是有利的。 第一蚁群优化算法被称为“蚂蚁系统”,它旨在解决货郎担问题,其目标是要找到一系列城市的最短遍历路线。总体算法相对简单,它基于一组蚂蚁,每只完成一次城市间的遍历。在每个阶段,蚂蚁根据一些规则选择从一个城市移动到另一个:它必须访问每个城市一次;一个越远的城市被选中的机会越少(能见度更低);在两个城市边际的一边形成的信息素越浓烈,这边被选择的概率越大;如果路程短的话,已经完成旅程的蚂蚁会在所有走过的路径上沉积更多信息素,每次迭代后,信息素轨迹挥发。
    粒子群算法,也称粒子群优化算法(Particle Swarm Optimization),缩写为 PSO, 是近年来发展起来的一种新的进化算法((Evolu2tionary Algorithm - EA)。PSO 算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质,但它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作,它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。
    粒子群优化算法是一种进化计算技术(evolutionary computation),1995 年由Eberhart 博士和kennedy 博士提出,源于对鸟群捕食的行为研究 。该算法最初是受到飞鸟集群活动的规律性启发,进而利用群体智能建立的一个简化模型。粒子群算法在对动物集群活动行为观察基础上,利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程,从而获得最优解。
    PSO同遗传算法类似,是一种基于迭代的优化算法。系统初始化为一组随机解,通过迭代搜寻最优值。但是它没有遗传算法用的交叉(crossover)以及变异(mutation),而是粒子在解空间追随最优的粒子进行搜索。同遗传算法比较,PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化,神经网络训练,模糊系统控制以及其他遗传算法的应用领域。
    人工鱼群算法,在一片水域中,鱼存在的数目最多的地方就是本水域中富含营养物质最多的地方,依据这一特点来模仿鱼群的觅食,聚群,追尾等行为,从而实现全局最优,这就是鱼群算法的基本思想。鱼类的活动中,觅食行为,聚群行为,追尾行为和随机行为与寻优命题的解决有较密切的关系,如何利用简单有效的方式来构造实现这些行为将是算法实现的主要问题。
以下是鱼的几种典型行为:
(1)觅食行为:一般情况下鱼在水中随机地自由游动,当发现食物时,则会向食物逐渐增多的方向快速游去。
(2)聚群行为:鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集成群,鱼聚群时所遵守的规则有三条:分隔规则:尽量避免与临近伙伴过于拥挤;对准规则:尽量与临近伙伴的平均方向一致;内聚规则:尽量朝临近伙伴的中心移动。
(3)追尾行为:当鱼群中的一条或几条鱼发现食物时,其临近的伙伴会尾随其快速到达食物点。
(4)随机行为:单独的鱼在水中通常都是随机游动的,这是为了更大范围地寻找食物点或身边的伙伴。
特点
(1)具有较快的收敛速度,可以用于解决有实时性要求的问题;
(2)对于一些精度要求不高的场合,可以用它快速的得到一个可行解;
(3)不需要问题的严格机理模型,甚至不需要问题的精确描述,这使得它的应用范围得以延伸。
停止条件
(1)判断连续多次所得的均方差小于允许的误差;
(2)判断某个区域的人工鱼群的数目达到某个比率;
(3)联系多次所获取的值均不能超过已寻找的极值。
    遗传算法(Genetic Algorithm)是一类借鉴生物界的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出,其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。遗传算法的这些性质,已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。
    遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。
    其基本运算过程如下:
(a)初始化:设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P(0)。
(b)个体评价:计算群体P(t)中各个个体的适应度。
(c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
(d)交叉运算:将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。
(e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。
(f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。
阅读(1244) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~