我的网站

耀世注册

联系我们

地址:海南省海口市

邮编:570521

电话:0898-08980898

传真:0898-1230-5678

行业新闻

当前位置: 首页 > 耀世资讯 > 行业新闻

优化算法3--蚁群算法(原理)

添加时间:2024-03-04 12:52:46

优化问题在科学和工业领域都非常重要。这些优化问题的实际例子有时间表调度、护理时间分配调度、列车调度、容量规划、旅行商问题、车辆路径问题、群店调度问题、组合优化等。为此,开发了许多优化算法。蚁群优化就是其中之一。

蚁群优化(Ant colony optimization,ACO))是一种寻找?最优路径?的?概率?技术。在计算机科学和研究中,蚁群优化算法被用于解决不同的计算问题。

蚁群优化算法(Ant colony optimization, ACO)最早由Marco Dorigo在90年代的博士论文中提出。该算法是根据蚂蚁的觅食行为来寻找蚁群与源食物之间的路径。最初,它被用来解决著名的旅行推销员问题。后来,它被用于解决各种困难的优化问题。

蚂蚁是群居的昆虫。他们生活在殖民地。蚂蚁的行为受?寻找食物?目标的控制。

  1. 在?搜寻的过程?中,蚂蚁们会在它们的聚居地四处游荡。蚂蚁?反复?地从一个地方跳到另一个地方去寻找食物。

  2. 在?移动过程?中,它会在地面上沉积一种叫做?信息素?(pheromone) 的有机化合物。蚂蚁通过信息素痕迹相互交流。当蚂蚁找到一些食物时,它会尽可能多地携带。

  3. 当它?返回?时,它会根据食物的数量和质量在路径上?沉积信息素。蚂蚁能闻到信息素。所以,其他蚂蚁可以闻到,然后沿着那条路走。

  4. 信息素?水平?越高选择?那条路径的?概率越高,跟随那条路径的蚂蚁越多,那条路径上信息素的数量也会增加。

案例:

1?起初,地面上没有信息素。因此,选择这两条路径的概率是等于50%

图片

2?这两条路径的距离是不同的。走较短路径的蚂蚁会比其他蚂蚁更早到达食物。

图片

3?在找到食物后,它会随身携带一些食物,然后返回蜂巢。当它追踪返回的路径时,它会将信息素沉积在地面上。走较短路径的蚂蚁会更早到达蚁群。

图片

?

4?当第三只蚂蚁想出去寻找食物时,它会根据地面上的?信息素水平,选择?距离较短的?路径。由于较短的路径比较长的路径具有更多的信息素,第三只蚂蚁将沿着信息素较多的路径行走。

图片

5?当蚂蚁沿着较长的路径返回蚁群时,更多的蚂蚁已经沿着信息素水平较高的路径返回。

然后,当另一只蚂蚁试图从蚁群到达目的地(食物)时,它会发现每条路径都有相同的信息素水平。它?随机选择?一个。

图片

6?重复这个过程一遍又一遍,经过一段时间后,较短的路径比其他路径的信息素水平更高,跟随该路径的概率也更高,下一次?所有的蚂蚁?都会跟随较短的路径。

蚁群算法针对不同的蚁群问题,提出了三种不同版本的蚁群算法:

  1. 蚁群密度与蚁群数量:当蚂蚁从一个位置移动到另一个位置时,信息素就会更新。

  2. 蚁群周期:在?所有蚂蚁?完成它们的旅程后更新信息素。

大致步骤:

  1. 第一步,每只蚂蚁?生成?一个解。

  2. 第二步,比较?不同蚂蚁找到的路径。

  3. 第三步,更新?路径值或信息素。

蚁群算法框架如下:

图片

蚁群算法主要由初始化、解构建和信息素更新三部分组成:

步骤1 ?初始化。

包括信息素初始化,启发信息初始化,以及种群规模、信息素挥发率等?参数初值?的设置。

步骤2 ?解构建。

解构建是蚁群算法迭代运行的基础,是算法最关键的环节,主要内容是在问题空间依据?状态转移?规则如何构建候选解。

每只蚂蚁都需要?构造一个解?来在图中移动。为了在它的行程中选择下一条边,蚂蚁将考虑从它当前位置可以得到的每条边的长度,以及相应的信息素水平。

?

步骤3 信息素更新。

所有蚂蚁完成他们的解决方案时,路径通常会更新(信息素更新),分别根据“好”或“坏”解决方案的移动增加或减少对应的轨迹水平。

信息素更新包括两个环节:

  1. 信息素挥发,用于?降低?路径上的信息素,减小?信息素对未来蚂蚁行为的影响,增加算法的探索能力;

  2. 信息素释放,蚂蚁在其所经过的路径上?释放?信息素,加强?对蚂蚁未来选择该路径的影响,增强算法的开发能力。

全局信息素?更新规则

?

蚁群算法存在收敛速度慢、易陷入局部最优、早熟收敛等问题:

  1. 收敛速度慢。?蚁群算法中信息素初值相同,选择下一个节点时倾向于随机选择,有助于找到潜在全局最优解,但需要较长时间才能发挥正反馈的作用,初期收敛速度较慢。

  2. 局部最优问题。?蚁群算法具正反馈的特点,初始时刻信息素完全相同,蚂蚁按随机方式完成解的构建,这些解存在优劣之分。在信息素更新时,在较优解经过的路径上留下更多的信息激素,而更多的信息激素又吸引了更多的蚂蚁,这个正反馈的过程迅速地扩大初始的差异,引导整个系统向最优解的方向进化。如果算法开始得到的较优解为次优解,那么正反馈会使算法陷入局部最优,且难以跳出局部最优。

  3. 优化能力问题。?蚁群算法中参数众多并且具有一定的关联性,参数选择更多是依赖经验和试错,不恰当的初始参数会减弱算法的寻优能力。

  4. 种群多样性与收敛速度的矛盾。?种群多样性对应于候选解在问题空间的分布。个体分布越均匀,种群多样性就越好,得到全局最优解的概率就越大,但寻优时间越长;个体分布越集中,种群多样性就越差,不利于发挥算法的探索能力。正反馈加快了蚁群算法的收敛速度,却较早地集中于部分候选解,降低了种群多样性。

?

地址:海南省海口市电话:0898-08980898传真:0898-1230-5678

Copyright © 2012-2018 耀世娱乐-耀世注册登录入口 版权所有ICP备案编号:琼ICP备xxxxxxxx号

平台注册入口