软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2010年
12期
3068-3081
,共14页
度约束最小生成树%遗传算法%嫁接%剪接
度約束最小生成樹%遺傳算法%嫁接%剪接
도약속최소생성수%유전산법%가접%전접
为求解大规模结点度约束最小生成树问题,提出一种带有嫁接和剪接算子操作的优化算法.通过借鉴花草果树种植技术,建立一种以基本遗传算子为基础、带有加速和调节算子作为激励的进化计算体系;嫁接以一种贪婪的思想加速搜索,按收益最大化原则进行剪接.对可能陷入局部极值引起冲突的现象及冲突检测的方法进行分析,并提出了冲突的若干解决方法.针对DCMST问题求解中的复杂性,提出了几种有效的嫁接和剪接的策略,并对算法的收敛性和计算复杂度进行了分析.通过该算法对结点数为50～500之间的Euclidean问题和按均匀随机方式产生的non-Euclidean度约束最小生成树问题进行求解.与现有文献的实验结果对比表明,该方法在求解最好解的精度和收敛速度上均有一定的优势.
為求解大規模結點度約束最小生成樹問題,提齣一種帶有嫁接和剪接算子操作的優化算法.通過藉鑒花草果樹種植技術,建立一種以基本遺傳算子為基礎、帶有加速和調節算子作為激勵的進化計算體繫;嫁接以一種貪婪的思想加速搜索,按收益最大化原則進行剪接.對可能陷入跼部極值引起遲突的現象及遲突檢測的方法進行分析,併提齣瞭遲突的若榦解決方法.針對DCMST問題求解中的複雜性,提齣瞭幾種有效的嫁接和剪接的策略,併對算法的收斂性和計算複雜度進行瞭分析.通過該算法對結點數為50～500之間的Euclidean問題和按均勻隨機方式產生的non-Euclidean度約束最小生成樹問題進行求解.與現有文獻的實驗結果對比錶明,該方法在求解最好解的精度和收斂速度上均有一定的優勢.
위구해대규모결점도약속최소생성수문제,제출일충대유가접화전접산자조작적우화산법.통과차감화초과수충식기술,건립일충이기본유전산자위기출、대유가속화조절산자작위격려적진화계산체계;가접이일충탐람적사상가속수색,안수익최대화원칙진행전접.대가능함입국부겁치인기충돌적현상급충돌검측적방법진행분석,병제출료충돌적약간해결방법.침대DCMST문제구해중적복잡성,제출료궤충유효적가접화전접적책략,병대산법적수렴성화계산복잡도진행료분석.통과해산법대결점수위50～500지간적Euclidean문제화안균균수궤방식산생적non-Euclidean도약속최소생성수문제진행구해.여현유문헌적실험결과대비표명,해방법재구해최호해적정도화수렴속도상균유일정적우세.
