计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2012年
9期
1899-1909
,共11页
黎自强%田茁君%王奕首%岳本贤
黎自彊%田茁君%王奕首%嶽本賢
려자강%전촬군%왕혁수%악본현
平衡约束%圆形Packing问题%蚁群算法%物理模型%启发式方法%并行算法
平衡約束%圓形Packing問題%蟻群算法%物理模型%啟髮式方法%併行算法
평형약속%원형Packing문제%의군산법%물리모형%계발식방법%병행산법
带平衡约束圆形Packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆数不超过3的布局方案).然后将蚁群优化与并行搜索相结合,使种群个体快速收敛到最优解或迭代出存在少量干涉的近似最优解(1～3个相交圆).若为后者,则基于物理模型用最速下降法将其快速调整成最优解.所采用的启发式方法、并行蚁群搜索机制和快速调整策略有机结合提高了算法的搜索精度和效率.数值实验表明该算法在性能指标上优于已存在的算法.
帶平衡約束圓形Packing問題屬于NP-hard問題,求解睏難.提齣一種求解該問題的快速啟髮式併行蟻群算法.首先提齣一種啟髮式方法:在輪盤賭選擇定序的概率公式中增加質量因子和外圍逆時針排列定位待佈圓,併用它構造齣多樣性種群箇體(相交圓數不超過3的佈跼方案).然後將蟻群優化與併行搜索相結閤,使種群箇體快速收斂到最優解或迭代齣存在少量榦涉的近似最優解(1～3箇相交圓).若為後者,則基于物理模型用最速下降法將其快速調整成最優解.所採用的啟髮式方法、併行蟻群搜索機製和快速調整策略有機結閤提高瞭算法的搜索精度和效率.數值實驗錶明該算法在性能指標上優于已存在的算法.
대평형약속원형Packing문제속우NP-hard문제,구해곤난.제출일충구해해문제적쾌속계발식병행의군산법.수선제출일충계발식방법:재륜반도선택정서적개솔공식중증가질량인자화외위역시침배렬정위대포원,병용타구조출다양성충군개체(상교원수불초과3적포국방안).연후장의군우화여병행수색상결합,사충군개체쾌속수렴도최우해혹질대출존재소량간섭적근사최우해(1～3개상교원).약위후자,칙기우물리모형용최속하강법장기쾌속조정성최우해.소채용적계발식방법、병행의군수색궤제화쾌속조정책략유궤결합제고료산법적수색정도화효솔.수치실험표명해산법재성능지표상우우이존재적산법.
