文档介绍：2016-12-171蚁群算法蚁群算法Yuehui ChenYuehui ChenSchool of Inform. Sci. and of Inform. Sci. and of Jinan, 2009University of Jinan, 2009://-12-172内内容容一、启发式方法概述一、启发式方法概述二、蚁群优化算法二、蚁群优化算法2016-12-173背背景景??传统实际问题的特点传统实际问题的特点连续性问题连续性问题————主要以微积分为基础,且问题规模较小主要以微积分为基础,且问题规模较小??传统的优化方法传统的优化方法追求准确追求准确————精确解精确解理论的完美理论的完美————结果漂亮结果漂亮主要方法:线性与非线性规划、动态规划、多目标规划、整数规划等;主要方法:线性与非线性规划、动态规划、多目标规划、整数规划等;排队论、库存论、对策论、决策论等。排队论、库存论、对策论、决策论等。??传统的评价方法传统的评价方法算法收敛性(从极限角度考虑)算法收敛性(从极限角度考虑)收敛速度(线性、超线性、二次收敛等)收敛速度(线性、超线性、二次收敛等)2016-12-174传统运筹学面临新挑战传统运筹学面临新挑战??现代问题的特点现代问题的特点离散性问题离散性问题————主要以组合优化理论为基础主要以组合优化理论为基础不确定性问题不确定性问题————随机性数学模型随机性数学模型半结构或非结构化的问题半结构或非结构化的问题————计算机模拟、决计算机模拟、决策支持系统策支持系统大规模问题大规模问题————并行计算、大型分解理论、近似理论并行计算、大型分解理论、近似理论??现代优化方法现代优化方法追求满意追求满意————近似解近似解实用性强实用性强————解决实际问题解决实际问题??现代优化算法的评价方法现代优化算法的评价方法算法复杂性算法复杂性2016-12-175现代优化现代优化((启发式启发式))方法种类方法种类??禁忌搜索(禁忌搜索(tabu searchtabu search))??模拟退火(模拟退火(simulated annealingsimulated annealing))??遗传算法(遗传算法(ic ic algorithms))??神经网络(神经网络(works))??蚁群算法(群体智能,蚁群算法(群体智能,Swarm IntelligenceSwarm Intelligence))??拉格朗日松弛算法(拉格朗日松弛算法(lagrangean relaxationlagrangean relaxation))2016-12-1761 1 现代优化计算方法概述现代优化计算方法概述?? 组合优化问题组合优化问题?? 计算复杂性的概念计算复杂性的概念?? 启发式算法启发式算法2016-12- 组合优化问题组合优化问题组合优化(binatorial binatorial optimization))::解决离散问题的优化问题解决离散问题的优化问题————运筹学分支。通过数学方法的研究运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等,可以涉及信去寻找离散事件的最优编排、分组、次序或筛选等,可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。息技术、经济管理、工业工程、交通运输和通信网络等许多方面。数学模型:数学模型:决策变量有限点集约束函数目标函数,.,0)(..)(minDxxgtsxf??2016-12- 组合优化问题组合优化问题组合优化问题的三参数表示:组合优化问题的三参数表示:????.|)(min)(,:::,,0)(,|:),,(FxxfxfFxxFxfxgDxxFDfFD??????????最优解,如果可行解(点)目标函数有限点集可行域决策变量定义域2016-12- 组合优化问题组合优化问题??例例1 0-11 0-1背包问题(背包问题(0-1 0-1 knapsack problemknapsack problem))装包?问题:如何以最大价值件物品单位价值,第件物品单位体积,第背包容积.,,1:.,,1::iiabii????2016-12- 组合优化问题组合优化问题????.1,0i0i1().,,1,1,0(),.()maxn1ii1iniiiniiDxnixbxxc????????????物品,不装第物品装第,其中决策变量包容量限制总价值数学模型:?