资源描述：
《现代优化计算方法课件(未加密版)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、现代优化计算方法第一章概论现代优化算法包括:•禁忌搜索(tabusearch)•模拟退火(simulatedannealing)•遗传算法(geneticalgorithms)•蚁群优化(antcolonyoptimizationalgorithm)•人工神经网络(artificialneuralnetworks)•拉格朗日松弛等算法•这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念•都是以—定的直观基础而构造的算法，也称之为元启发式算法(meta-heuristics)•启
2、发式算法的兴起与计算复杂性理论的形成有密切的联系•现代优化算法自80年代初兴起，至今发展迅速•这些算法同人工智能、计算机科学和运筹学相融合1．1组合最优化问题1.组合最优化(combinatorialoptimization)是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学中的一个经典且重要的分支，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等诸多领域2.该问题可用数学模型描述为：minf(x)s.t.g(x)≥0,x∈D其中，f(x)为目标函数，g(
3、x)为约束函数，x为决策变量，D为决策变量的定义域3.一个组合最优化问题可用三参数(D，F，f)表示，F={x
4、x∈D,g(x)≥0}表示可行解集,为有限点集，D通常也为有限点集，f表示目标函数4.满足f(x*)＝min{f(x)
5、x∈F}的可行解x*称为该问题的最优解．5.组合最优化的特点是可行解集合为有限点集6.例例1.1.10-1背包问题(knapsackproblem)设有一个容积为b的背包，n个尺寸分别为a(i＝l,2,…,n)，价值分别为c(i＝1,2,…,n)的ii物品，如何以最大的价
6、值装包?nmax∑cixi(1.1)包内所装物品的价值最大i=1n包的能力限制ts..∑aixi≤b(1.2)i=1x＝1:装第i个物品ix∈1,0{},i=,1?,n(1.3)iD={0,1}n，F为D中满足(1.2)的可行解．f为目标函数例1.1.2旅行商问题(TSP，travelingsalesmanproblem)一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为d，如何选择ij一条道路使得商人每个城市走一遍后回到起点且所走路径最短TSP还可以细分为:对称(d=d)和非对称距离两大类
7、问题ijji对一般的TSPmin∑dx(1.4)ijiji≠j从城市i出来1次nts..∑xij=,1i=,2,1?,n(1.5)j=1n走入城市j只1次∑xij=,1j=,2,1?,n(1.6)i=1∑xij≤
8、s
9、−,12≤
10、s
11、≤n−,2i,j∈ss⊂,2,1{?,n},城市子集(1.7)xij∈1,0{},i,j=,1?,n,i≠j(1.8)x=1:经过城市i→j的路径ij共n×(n-1)个决策变量D={0,1}n×(n-1)一条回路是由k(1≤k≤n)个城市和k条弧组成，因此，(1．7)约
12、束旅行者在任何一个城市真子集中不形成回路，其中
13、S
14、表示集合S中元素个数例1.1.3整数线性规划(integerlinearprogramming)Tmaxcxts..Ax=bnx≥,0x∈Zc为n维列向量，A为m×n矩阵、b为m维列向量，x为n维决策变量，Zn表示n维整数向量的集合系数A、b和c的元素都是整数•例1.1.2和1.1.3的数学模型都具有(IP)的形式•一些组合优化问题可以写成整数线性规划问题•IP与LP形式非常相似，不同之处是前者的决策变量部分或全部取整数例1.1.4装箱问题(bin
15、packing)设有n个一维尺寸不超过１的物品集合{a,1a,…,a},如何以个数最少的一维尺寸为2n１的箱子装进这n个物品？（一维装箱问题）例1.1.5约束机器排序问题(capacitatedmachinescheduling)n个加工量为{d
16、i＝l，2，…，n}的i产品在一台机器上加工，机器在第t个时段的工作能力为c，求完成所有t产品加工的最少时段数minT(1.9)加工所用的时段数最少Tts..∑xit=,1i=,2,1?,n(1.10)t=1产品i一定在某个时段加工n∑dixit≤ct,t
17、=,2,1?,T(1.11)i=1每个时段的加工量不超过能力的限制x∈1,0{},i=,1?,n;it(1.12)决策变量t=,1?,Tx＝1表示第t时段加工产品i、T:时段数it组合优化问题的表示形式•组合优化问题通常可以用整数规划模型的形式表示，如例1.1.1和1.1.2•有些组合优化问题用IP模型表示则比较复杂且不易被理解，不如对问题采用直接叙述更易理解，如例1.1.2,1.1.4和1.1.5•根据对解的精度要求和分析的需要，有大量的组合优化问题是通过文字语言叙
