为求解给定节拍最小化工作站数的第Ⅰ类装配线平衡问题,提出了一种改进的蚁群算法。在该算法中,针对装配线平衡问题的具体特点,给出了蚂蚁分配方案的生成策略。通过在任务和任务分配序列的位置之间释放信息素,并采用信息素总合规则进行更有效的信息素累积。为提高搜索效率,以综合考虑装配任务作业时间和后续任务数的分级位置权重为蚁群算法的启发式信息。最后,通过对大量测试问题
维普资讯 doc.guandang.net
计算机集成制造系统
第 1卷 3
单只蚂蚁 AL P解的构造, B即分配方案生成策略,部分分配方案中通过逐步添加可供分配的任在务而生成完整的可行分配方案。将蚂蚁某时刻的所有可供分配的任务集合称为该时刻的候选任务集, 记为 N,。解的构造过程如下:在尚未分配的任务①集合中,按优先顺序关系构建可选任务集合,而根进 图 1作业优先顺序图实例
据节拍时间,构建当前可供分配的任务集,即候选任务集 Nj②若 N,;为非空集合,则按某规则从集合 N,中选出一项任务,分配至当前工作站;重复①③和②,到 N,直变为空集,还剩有尚未分配完的任若务,开启一个新的工作站;重复①~③,到则④直全部任务分配完毕,即求得了一个解。其求解流程如图 2示。蚁使用伪随机比率选择规则来分配任所蚂务,构造一步解,每候选任务集 N相应地更新。作采用该分配方案生成策略产生可行分配方案,行分可配方案集里总是存在着最优分配方案。
穴到食物源的最短路径。蚂蚁在行进的过程中不断分泌信息素,其他的蚂蚁会根据地面信息素的强弱选择行走路径。这样,离较短的路径信息素水平距高,从而又可以吸引更多的蚂蚁;距离长的路径,而
信息素水平低,有很少的蚂蚁经过。通过这种正只 反馈作用,最优的路径就会逐渐凸现出来。由此,意大利学者 D rg o io等提出了一种分布式仿生的搜索算法——蚂蚁系统模型_在后续工作中针对蚂蚁 1, 系统中存在的问题进行了一系列改进,出了一些提
新的算法模型_,进一步总结出了求解组合最优 9并] 化问题的蚁群算法元模型——蚂蚁群体优化 ( t An Co o y Op i i to l n t z i n,ACO) 1。 m a[= 6
蚁群算法先将所研究的问题抽象为节点模型, 不同的节点对应问题中的不同实物。人工蚂蚁在节
点图中根据转移概率的大小随机游走,完成一次每
周游,构成问题的一个完整解。通过信息素的正就 反馈作用,最后收敛到最优解。但对于本文研究的 AL P, B算法需要作适当转换才能得到较好的应用。
3求解装配线平衡问题的蚁群算法 3 1分配方案的生成策略 .
由于 AL P任务间优先顺序关系约束的存在, B 使问题复杂化而难以求解,过采用候选任务集方通法,直接在可选任务列表中进行任务的选择分配,通过减少问题搜索空间来提高搜索速度。为定义和生成候选任务集,装配线任务作如下定义:对 () 1可选任务 ( v i bets )从优先顺序约 a al l ak a
图2装配线平衡问趣的解的构造策略
3 2蚁群算法模型 . 3 2 1构造图 . .
AL P可用图 G一 ( B C,L)表示,中 C是来其 AL P中任务和分配序列位置的集合, B L为任务与
分配序列位置之间的连接所构成的集合。将任务分 配到各序列位置的过程,以看成是一群蚂蚁在信可
束角度,一个尚未分配的任务 i若的所有先行任务 h ∈ P都已分配 ( 示任务 i P表的紧前任务集)则任, 务 i是可供选用的。 () 2可供分配的任务 ( sin bets )从优先 as a l ak g
息素轨迹和局部启发式信息的指引下沿着图 G移动,同时蚂蚁的移动会受到一些条件的约束,从而确保蚂蚁在移动过程中找到合适的解。 3 2 2信息素 ..
顺序关系和节拍这两个约束角度,一项尚未分配若 的任务 i的所有先行任务都已分配至工作站足或更早的工作站 1,,一 1以及当前工作站足的空,2…足,闲时间对于该任务 i充分的,任务被称为可供是该 分配的任务。
用蚁群算法求解 T P时, S信息素轨迹通常表 示为紧随城市 i问城市 J的期望,访即提供城市 i和
城市 J相对位置期望的一些信息。由于在 TS中, P 数列是循环的,即仅有组成解的元素的相对次序是

.82oO 7年8月ComputerIntegrated M删facturi“gSystemsAug.2o07 文章编号:l006—5911(2007)08—1632—07 求解装配线平衡问题的一种改进蚁群算法张则强,程文明,...
求解带区域约束的双边装配线平衡问题的一种改进蚁群算法_教育学/心理学_人文社科...运用改进蚁群算法求解直... 暂无评价 6页 2.00 多目标装配线平衡的优化....
宋莉波 (华南理工大学 工商管理学院, 广东 广州 510640) 摘要: 针对直线型 和 U 型装配线第一类平衡问题, 提出一种基于最优成分 信息素更新规则的改进蚁群算法...
一种基于混合品种装配线均匀零部件消耗速 率的方差算法,对目标追踪法进行了改进...当前已有蚁群算法用于混合品种装配线平衡 问题的求解,文献[17]提出了一种基于...
计算机系统应用 201 0年第1 9卷第1期 蚁群算法求解装配线平衡第一类问题毛凌...王金诺 求解装配线平衡问题的一种改进蚁群算法[期刊论文]-计算机集成制造系统 ...
基于一种新蚁群算法的装配线平衡研究 2 2 城, 张超勇 ( 1. 湖北汽车工业...陈志楚 ,田 摘要: 采用改进蚁群优化算法来 解决装配 线平 衡的第 一类 问题...
基于一种新蚁群算法的装配线平衡研究 2 2 城, 张超勇 ( 1. 湖北汽车工业...2 2. 1 基于改进的蚁群算法的装配线平 衡问题研究可行解的构造 考虑到 2. ...
ALBP)是制造领域里的一个重要问题,其 微小的改进都可以导致经济上显著的收益,...当前已有蚁群算法用于混合品种装配线平衡 问题的求解,文献〔17】提出了一种基于...
求解装配线平衡问题的一种... 9页 5财富值 运用改进蚁群算法求解直线... 暂无...在已有装配线平衡设计迭代算法的基础上,提出了一种改进的迭代算法,该方法采用...
运用改进蚁群算法求解直线型和U型装配线平衡问题 针对直线型和U型装配线第一类平衡问题,提出一种基于最优成分信息素更新规则的改进蚁群算法。算法在任务和工作站之间释...
针对混合型双边装配线平衡问题 的具体特点,本文运用一种改进的智能蚁群优化算法来平衡装配线。首先,建 立数学模型,描述这个问题。然后,利用智能蚁群优化算法来解决...
热门文档