西安电子科技大学学报（自然科学版）
西安電子科技大學學報（自然科學版）
서안전자과기대학학보（자연과학판）
JOURNAL OF XIDIAN UNIVERSITY(NATURAL SCIENCE)
2009年
3期
527-534
,共8页
TSP问题%人工免疫系统%克隆选择%遗传算法
TSP問題%人工免疫繫統%剋隆選擇%遺傳算法
TSP문제%인공면역계통%극륭선택%유전산법
在探讨遗传算法求解TSP问题中编码方式和交叉、变异算子作用特点的基础上,发现模板理论已经不能很好地适应TSP问题,主要是因为非二值符号编码和交叉算子对边的过度破坏导致子代难以继承父代的优良模式.为了克服上述问题,提出一种三角形表示的路径编码方案,并给出相应的启发式路径搜索策略;引入生物免疫系统的克隆选择机理加强局部搜索,进而构造一种适合TSP问题求解的人工免疫系统算法--超变异抗体克隆选择算法(HACSA).典型TSP问题的求解表明,和Endoh等人的免疫算法和遗传算法相比,HACSA的计算复杂度相当,60%以上的求解结果达到或者超过问题已知的最优值,而相应的免疫算法和遗传算法几乎均陷入局部极值,无法获得满意的求解结果.
在探討遺傳算法求解TSP問題中編碼方式和交扠、變異算子作用特點的基礎上,髮現模闆理論已經不能很好地適應TSP問題,主要是因為非二值符號編碼和交扠算子對邊的過度破壞導緻子代難以繼承父代的優良模式.為瞭剋服上述問題,提齣一種三角形錶示的路徑編碼方案,併給齣相應的啟髮式路徑搜索策略;引入生物免疫繫統的剋隆選擇機理加彊跼部搜索,進而構造一種適閤TSP問題求解的人工免疫繫統算法--超變異抗體剋隆選擇算法(HACSA).典型TSP問題的求解錶明,和Endoh等人的免疫算法和遺傳算法相比,HACSA的計算複雜度相噹,60%以上的求解結果達到或者超過問題已知的最優值,而相應的免疫算法和遺傳算法幾乎均陷入跼部極值,無法穫得滿意的求解結果.
재탐토유전산법구해TSP문제중편마방식화교차、변이산자작용특점적기출상,발현모판이론이경불능흔호지괄응TSP문제,주요시인위비이치부호편마화교차산자대변적과도파배도치자대난이계승부대적우량모식.위료극복상술문제,제출일충삼각형표시적로경편마방안,병급출상응적계발식로경수색책략;인입생물면역계통적극륭선택궤리가강국부수색,진이구조일충괄합TSP문제구해적인공면역계통산법--초변이항체극륭선택산법(HACSA).전형TSP문제적구해표명,화Endoh등인적면역산법화유전산법상비,HACSA적계산복잡도상당,60%이상적구해결과체도혹자초과문제이지적최우치,이상응적면역산법화유전산법궤호균함입국부겁치,무법획득만의적구해결과.
