应用数学学报
應用數學學報
응용수학학보
ACTA MATHEMATICAE APPLICATAE SINICA
2008年
2期
239-248
,共10页
蚁群优化%收敛性%最小steiner树%信息素%算法
蟻群優化%收斂性%最小steiner樹%信息素%算法
의군우화%수렴성%최소steiner수%신식소%산법
蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法.在蚁群优化算法中,信息素的更新规则直接影响着算法性能,固定挥发率条件下,虽然也能得到求解Steinei树蚁群优化算法的收敛性结果,但算法的探优能力差,易于陷入局部最优.本文在设计求解最小Steiner树蚁群优化算法时,采用了动态更新信息索挥发率的方法,并给出了时变挥发率条件下算法的收敛性证明.具体的,在时变挥发率条件下,当迭代次数充分大时,该算法能以概率1找到最优解.另外,在动态更新信息素下界的条件下,也能得到类似的收敛性结果.
蟻群優化算法是最近提齣的求解複雜組閤優化問題的啟髮式算法.在蟻群優化算法中,信息素的更新規則直接影響著算法性能,固定揮髮率條件下,雖然也能得到求解Steinei樹蟻群優化算法的收斂性結果,但算法的探優能力差,易于陷入跼部最優.本文在設計求解最小Steiner樹蟻群優化算法時,採用瞭動態更新信息索揮髮率的方法,併給齣瞭時變揮髮率條件下算法的收斂性證明.具體的,在時變揮髮率條件下,噹迭代次數充分大時,該算法能以概率1找到最優解.另外,在動態更新信息素下界的條件下,也能得到類似的收斂性結果.
의군우화산법시최근제출적구해복잡조합우화문제적계발식산법.재의군우화산법중,신식소적경신규칙직접영향착산법성능,고정휘발솔조건하,수연야능득도구해Steinei수의군우화산법적수렴성결과,단산법적탐우능력차,역우함입국부최우.본문재설계구해최소Steiner수의군우화산법시,채용료동태경신신식색휘발솔적방법,병급출료시변휘발솔조건하산법적수렴성증명.구체적,재시변휘발솔조건하,당질대차수충분대시,해산법능이개솔1조도최우해.령외,재동태경신신식소하계적조건하,야능득도유사적수렴성결과.