改进群体智能算法及其在背包问题中的应用

《改进群体智能算法及其在背包问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学硕士学位论文改进群体智能算法及其在背包问题中的应用姓名：赵培怡申请学位级别：硕士专业：计算机应用技术指导教师：马军20071015山东大学硕士学位论文摘要随着人类社会、经济和科学技术的飞速发展，许多复杂性、非线性、庞大巨系统和快速反应性系统等方面的问题大量呈现在人们的面前，传统的优化方法逐渐陷入困境．这时，自然界中那些群居的简单生物表现出来的复杂的群体智慧给人们很好的启迪．这些生物群体中每一个个体的行为都很简单，也没有受到集中统一的指挥，但它们之间的有机协调和自组织能力，却使得整个群体表现出高度的智慧，能够完成非常

2、复杂的任务．这种现象吸引了众多学者的关注，去深入研究在现象背后存在的机理，并通过计算机模拟其中可循的规律，用来指导和解决传统方法难以解决的实际问题．目前通过模拟生物群体的行为来解决优化问题已经成为优化领域新的研究热点，并已经在一些实际应用领域取得突破性的进展．其中有代表性的有意大利学者MarcoDo“go于1991年提出的蚁群优化方法和1995年JamesKennedy和RussellEberhart基于对鸟群、鱼群捕食行为的模拟，提出了粒子群优化方法．由于这些方法概念简明、实现方便，特别用以解决复杂的组合优化问题具有优越

3、性，迅速得到国际优化计算领域的认可，并在工程设计、生产优化等应用领域取得成功的应用．本论文重点研究了当前应用最广泛、最典型的群体智能优化方法一一蚁群优化方法和粒子群优化方法．系统深入地分析了蚁群优化算法基本原理和对已有的NP．hard问题的求解过程，然后给出了改进的对背包问题的蚁群算法．此外，本文对基本粒子群算法原理作了系统深入的研究，对NP-难问题求解的已有工作进行了深入分析，在此基础上，设计了一种新型的混合粒子群算法和实现步骤．上述理论研究成果都通过实际算例给出验证．体现了改进算法的有效性和优越性．本文的主要创新点体现

4、在三个方面；一是在对基本蚁群算法原理、实现过程深入研究的基础上，为了减囊磊&国衙■藿碥奄噶芎镯妻TR趸￡王蓼剖引海蠡磊嚣摧辩麓蔫誊冀鬟嚣嚣塑萋磊醚黧．瀚攀囊鋈塑器鲢琵瑟瑟强溺铺灏I堇!襄翻．嚣矍葬瓣拜携懿劈静箱塑霾蓊霆慝瑙引捌，黧蓊妻萄型并篓萄翔，磐嚣也疆韵到涮舞萄篓器骚鏊一～篓慧漫藩爨麓，淄凰醺稀鞠靖薷翼毳姜3蓊警蔷邕篓；惩旺藕矍鞠蔷裂美霸蕊霆一婪蚓耄霸蓊黼蕊。翻需囊薰毯篓冀薷豢嚣蓍眷麓；圈攒熏矍黎矬醚霆蟊捌嚣馥毳霎舔鞍繇嚣羚鹞弹嚣魏联秘酗，孬錾港一蕊粥銎翼积褥邀j耋弱划璧蠢磊弧皤坦蓬蓊矗囊釜终墅滢基i黉邕撼搿塑露裂蠢露

5、裁交萋鞫灏鞠蛙嚣蓑篓野毡鳃鹱羹；鬻嗣魈剿蕃鳇羹j麓燮嚣菇溺翻鲴。塑萄删塑墅蓠颡南。塑醛鲞謦*nl}矍鬓翼嚣鞭避鞫剜鬟；荔蠢魏释艘曩羹霎囊翳鑫鞭菲琵鐾。羹筹强弱蚕一蠢羹囊薹翻理篓攀蠢奏娶骚疆褐璧阉，蒌雾鎏蠹墼雾群塾獭引翼塞潮鬻鲤霸爨铂壁lP鐾靛赘舞垂善．夔羹篓一一测强蠢嚣。弱羹荭强鬻翌磊鞠莲辩鬟鬟型嚣i拍篷蘩螽鞋器疆羹鲤；强弱霞娶鹭蠹爨娶鸯璧疆剜羽毳曦。靛鬃娶鬻i臻凝潮鬣"≯iil晶麓羲琵蠢嚣筵馨篓消器翼黝霎翻臻嚣蔺；翼霪冀鞫滞雾圈萋夔耄羹蓊巍藏妻，舅警鞠嚣漤嚣澄蠹装，鬻美垂器燃懑嚣蜊啸跫嚣霸蘸嚣萄蛹鞴篓영"x山东大学硕士学

6、位论文operatorandoutermutationoperator．Accordingtothemixedmutation，wegaVeanewinlprovedaIgorithmanddesignedoperationsteps．2．ThedissertationgaveanewimprovedPSOalgorithmwhichintroducedcrossoveroperatorandmutationoperatorofGA．Wecangetthenewfitnessvaluefromcrossoveringoft

7、hecurrentfitnessvalue，theindividualfitnessvalueandtheglobalfitnessvalue，thenextstepisthemutationoperater．Inthecourseofcrossover，weuseDavis’smethodofsequencecrossover，besidesthisweadoptreversemutationinthemutationstep．Onthebasisofthis，weobtainedanewhyb“dPSOalgorimm

8、andoperationsteps．3．TheimprovedtwoswarmintelligencealgorithmsareusedtosolvethetypicalNP·hardproblem——theknapsackprobIemWegotbetterresultthroughthepracti