计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2014年
8期
1794-1808
,共15页
仿生算法%旅行商问题%蚊子追踪算法%分布并行算法
倣生算法%旅行商問題%蚊子追蹤算法%分佈併行算法
방생산법%여행상문제%문자추종산법%분포병행산법
bio-inspired algorithm%traveling salesman problem (TSP)%mosquito host-seeking algorithm (MHSA)%distributed and parallel algorithm
旅行商问题(Traveling Salesman Problem,TSP)是NP完全问题中最为著名的问题,它易于陈述而难于求解,至今尚未找到准确有效的求解大规模TSP问题的方法.文中提出了能求出TSP有效近似最优解的新的蚊子追踪(Mosquito Host Seeking,MHS)算法,证明了蚊子的目标追踪行为和MHS数学模型的一致性、蚊子追踪算法的收敛性,并通过理论证明确定了MHS算法中各参数的选择范围.蚊子追踪算法是一个全新的仿生算法.文中以TSP问题为载体,详细提出了蚊子追踪算法的动机、生物学模型、数学模型、算法、理论基础(数学证明)及大量实验结果.从理论和实验两方面证明了蚊子追踪算法能够求出TSP问题理论上的优化解.
旅行商問題(Traveling Salesman Problem,TSP)是NP完全問題中最為著名的問題,它易于陳述而難于求解,至今尚未找到準確有效的求解大規模TSP問題的方法.文中提齣瞭能求齣TSP有效近似最優解的新的蚊子追蹤(Mosquito Host Seeking,MHS)算法,證明瞭蚊子的目標追蹤行為和MHS數學模型的一緻性、蚊子追蹤算法的收斂性,併通過理論證明確定瞭MHS算法中各參數的選擇範圍.蚊子追蹤算法是一箇全新的倣生算法.文中以TSP問題為載體,詳細提齣瞭蚊子追蹤算法的動機、生物學模型、數學模型、算法、理論基礎(數學證明)及大量實驗結果.從理論和實驗兩方麵證明瞭蚊子追蹤算法能夠求齣TSP問題理論上的優化解.
여행상문제(Traveling Salesman Problem,TSP)시NP완전문제중최위저명적문제,타역우진술이난우구해,지금상미조도준학유효적구해대규모TSP문제적방법.문중제출료능구출TSP유효근사최우해적신적문자추종(Mosquito Host Seeking,MHS)산법,증명료문자적목표추종행위화MHS수학모형적일치성、문자추종산법적수렴성,병통과이론증명학정료MHS산법중각삼수적선택범위.문자추종산법시일개전신적방생산법.문중이TSP문제위재체,상세제출료문자추종산법적동궤、생물학모형、수학모형、산법、이론기출(수학증명)급대량실험결과.종이론화실험량방면증명료문자추종산법능구구출TSP문제이론상적우화해.
