智能仿生算法及其网络优化中的应用研究进展
丁建立陈增强袁著祉
(南开大学信息技术科学学院,天津300071)
E—-mail:jianliding@yahoocom.en
摘要网络优化问题是一类特殊的组合优化问题,很多问题找不到求最优解的多项式时间算法.属于NP田难问题;
智能仿生类算法主要是模拟生物进化和生物群体的智能化方击,如人工神经网络、遗传算法、DNA分子算法、蚂蚁算法等.它们在解决NP问题上表现出得天被厚的优势,取得了诸多丰硕的成果。困此,该文系统地综速了近年来智能仿生算法噩其网络优化中的应用研究进展和未来发展方向.关键词
网络优化NP问题
神经网络遗传算法DNA分子算法蚂蚁算法
文献标识码A
中图分类号TPl8
文章编号1002—833l一(2003)12—0010一06
ASurveyofSimulatingBiologyIntelligentAlgorithmsand
It7SApplication
DiIlgJianli
(Collegeof
on
NetworkOptimization
YuanZhuzhi
ChenZengqiang
InformationTechnologyandScience,NankaiUniversity,Tianjin300071)
to
Abstract:Networkoptimizationisistie
on
specialproblemofcombinatorialoptimization.Manyquestionsbelong
intelligentalgorithms
andheredity
show
is
method
11011一deterrnin—
strategy
polynomial
problems(NP).Simulatingbiology
biologicaloptimization
based
biologypopulati011behaviorand
naturalselectionand
ant
evolutionary,forexample:neuralnetworks,genetical—type
eharactelistics
to
gerithms.DNAcomputingalgorithms
many
algorithmsTheysystematic
all
solveNPsimulating
problems
and
get
goodresnhs.Because.£h。paperprovides
on
overview
out
ofdevelopmentforfutureresearch
biologyintelligent
algorithmsandit'sapplicationnetworkoptimization.and
points
directions
Keywords:NetworkOptimization,NPgorithms
Problem.NeuralNetworks,GeneticAlgorithms,DNAComputingAlgorithms,AntAI—
l
引言
人们生活的现代社会是一个由计算机信息网络、电话通信
2网络优化的概念及特征
网络优化:与图和网络相关的最优化问题,多数网络优化问题是以网络上的流为研究对象。网络优化问题是一类特殊的组台优化问题。
组合优化:绢台优化就是离散优化.它是通过数学方法寻找离散事件的最优编排,分组、次序或筛选等。这类问题可用数学模型描述为:
目标函数:Min“x)约束条件:s1.Fh)≥0
决策变量:《ED,其叶ID为有限个点组成的集合。
特点:足可行解集台为有限点集,只要将D中有限个点逐一判别足☆满足g(x)的约束许比较目标值的大小,就町以得到该『廿】题的虽优解。
因此,对丁组合优化问题,人们一般关心的小是最优解的存在性和唯一|生,而是如何找到有效的算法求得一个最优解。
网络、运输服务网络、能源和物流分派网络等各种网络组成的复杂网络系统。网络优化就是研究如何有效地计划、管理和拧制这个网络系统,使之发挥最大的社会效益和经济效益。网络
优化是运筹学的一个经典和蘑要的分支.所研究的问题涉及增多领域.如最短路|1】】题、最大流问题,最小费用流问题和匹配问
题等都是网络优化的基本问题。
网络优化问题是一类特殊的组合优化问题,很多问题找不到求最优解的多项式时间算法,属于N}1困难同题.如旅行商问题,背包问题、装箱问题、机器调度问题等。对于此类NP问题,传统运筹学的优化与法显得无能为力.寻找、研究、应用启发吱智能化的优化冉法就显得尤为重要。
智能仿牛类算法主要是模拟生物进化和生物群体的智能化方法,日前热点研究的主要有人T神经网络、遗传算法、DNA
分子算法、蚂蚁算法等,它们在并行性、随机性、自适应件、鲁棒
性、非线性复杂问题的搜索能力等力面表现出r显著的特点,尤萁在解决NP问题表现其得天独厚的优势,取得了诸多丰硕的成果。蹦此.该文系统地综述了近年来智能仿生算法艟其网络优化巾的应用研究进展和未来发展方向。
非确定多项武时问可解问题(NP问题):由组台优化问题
的定义,每个组合优化问题都可以通过完牟枚举的方法求得最优解,枚举是以时间为代价的.有的枚举时fnJ吖以接受,有的则
不能接受。如旅行商问题('PAl'--Traveling
SalesmanProblem).
则需要(n一】)!个枚举,随着n的增加,汁算所需时间增加之快,
基奎项目:同亲自然科学基金(编号:60174021t;天滓自然科学基盘蕈点项目(编号:013800711);河南科技攻芰项14(编号:0124140141)
作者筒舟:T建立(1963一t,男.州南i鑫阻人,博士。副教授,从事智能仿生算法、智能优化等研究:陈增强(1964一),男,天津人,教授,博士生导师,从
事智能预测控制、智能网管等研究。袁著祉(1937一).男.山东青岛人,教授,博士生导师.从事自适应控制、智能决策等研究。
10
2003.12计算机工程与应用
因此, 该文系统地综述了近年来智能仿生算法及其网 络优化中的应用研究进展和未来发展方向。 问题是以网络上的流为研究对象。 网络优化问题是一类特殊的 组合优化...
IP网络优化研究和应用 57页 5财富值 智能仿生算法及其网络优化... 6页 20财富...随着我国移动通信市场的蓬勃发展, 国内移动运营商通过多年的努力, 移动网络质量...
智能仿生算法及其网络优... 6页 7下载券 仿生方法在桥梁设计与优... 140页...II 仿生优化算法研究及其在电磁工程中的应用 本文首次将蚁群算法引入到电磁工程...
智能优化技术在无线网络优化中的应用及算法研究_专业资料。智能优化技术主要是针对网络优化工作中遇到的小区异常指标故障.通过对网络统计数据源(包括话务指标统计、小区...
一种新型混合仿生智能算法及其应用研究_信息与通信_工程...百度图片搜索引擎优化方法88份文档 2014年全国注册造价...维普网 中国最大最早的专业内容网站 0 0 0.0 ...
新的仿生优化算法食物车蟑... 4页 免费 智能优化算法程序代码集锦 31页 免费...南昌大学 博士学位论文 网络优化中若干问题高效能算法研究及其在管理中的应用 姓名...
仿生优化算法在片上网络映射的应用研究_专业资料。片上系统发展到片上网络阶段,能耗问题已经成为片上网络技术的重要约束。在片上网络映射中应用了生物仿生算法—蚁群...
智能仿生算法及其网络优化... 6页 20财富值 半仿生提取法_的特点与应用... ...研究现状 三、研究内容和目标 四、已完成的工作 五、进度安排 六、参考文献 ...
一种新颖的仿生群智能优化算法:萤火虫算法_专业资料...第2 8卷第 9期 210 1年9月 计算机应用研究 ...维普网 中国最大最早的专业内容网站 0 0 0.0 文档...
研究关于对网络优化问题,普遍集中于理论算法研究,缺乏与实际工程背景的有效结合,因而限制了网络优化算法应用的可行性。针对网络的时效性和应用的智能性问题,为了深化...
热门文档