优化问题智能优化算法笔试试题南京理工

最优化问题一般最优化问题的数学模型为其中x为决策变量，D为一个集合称为可行域，f为D上的一实值函数称为目标函数.集合D中的任一元素称为问题的可行解，如果有一可行解x*满足f(x*)=min{f(x)|x属于D}，则称x*为问题的最优解，而f(x*)称为最优值.在大多数情况下，可行域D是由一些称之为约束条件来确定的.求解最优化问题就是寻找问题的最优解.最优化问题也可以是极大化目标函数，此时若将f换作一f，那么极大化问题可转化为上述极小化问题.组合优化问题当最优化问题中的可行域D是一个由有限个元素组成的集合时，该最优化问题称为组合优化问题.通常组合优化问题可表示为现实生活中大量问题是组合优化问题，典型的组合优化问题有旅行商问题，背包问题，并行机排序问题等等.旅行商问题(travelingsalesmanproblem,TSP):设有n个城市1,2,……，n,城市i与城市j间的距离为dij，一售货商要去这些城市推销货物，他希望从一城市出发后走遍所有的城市且旅途中每个城市只经过一次，最后回到起点.选择一条路经使得售货商所走路线总长度最短，这就是旅行商问题.其中|S|表示集合S中元素的个数.背包问题(knapsackproblem):设有一个容量为b的背包，n个容积分别为Wi，价值分别为Ci(i=1，2，…，n}的物品，选择那些物品放入背包中以使装入的物品总价值最大，这就是背包问题.引入决策变量Xi，若第i个物品被放入包中，则Xi=I，否则Xi=O(i=1,2,…，n).那么背包问题的数学模型为并行机排序问题(parallelmachinescheduling):设有m台同型机器M1,M2,M3-……Mm,n个相互独立的工件J1,J2,…,Jn.现在要安排这些工件到机器上进行加工，设每个工件只需在任一台机器上加工，工件Ji的加工时间为ti(i=1,2,…，n).如何安排这些工件的加工方案，以使机器完成所有工作的时间最少.这就是并行机排序问题.由于组合优化问题中的可行域是有限集，所以从理论上看可以将这有限个可行解枚举出来，一一地计算出他们对应的目标值，然后通过比较大小找出最优解.对于小规模的组合优化问题，用这种方法很容易求出最优解.但对于大规模或稍大规模的组合优化问题，这种求解方法就不一定可行了.计算复杂性计算复杂性我们考虑这样一个问题:有n种作物种子，把它们分别播种到n块地里，每种种子在不同的地块里的产量不同因而所得产值也就不同，要求做一个播种方案，以使总产值最大.所有可能的播种方案有n!种，若把列出一种方案作为一次基本操作，则需n!次基本操作.用每秒执行一千万次操作的计算机来运算，当n=19时，至少需要385.7年才能完成这些操作找出最优解.当n=20时，至少需要7714.6年才能完成这些操作找出最优解.这是不可实现的.要了解问题的复杂性，从而针对性地设计算法解决所研究的问题.启发式算法启发式算法是一种技术，这种技术使得在可接受的计算费用内去寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近视程度.背包问题的贪婪算法简单的邻域搜索算法Step1.任选一个初始解xo属于D.Step2.在N(so零)中按一定规则选择一个s;若f(s)f(so),则So:=s.否则，N(So)=N(So)-{s};若N(So)-{So}=fai，停止;否则，重复step2.启发式算法分类1.简单直观的算法(1)一步算法.如背包问题的贪婪算法(2)改进算法.如邻域搜索算法2.数学规划算法.如分支定界法，割平面法3.智能算法启发式算法的性能分析最坏情形分析对所有实例工，评价关系式为数学规划1线性规划2非线性规划3多目标规划4目标规划5动态规划6多层规划7Benchmark问题线性规划线性规划(LP)是指目标函数是线性函数，约束条件由线性函数确定的优化问题.标准的LP可表示为:一个点x称为凸集S的极点如果xES且x不能表示为S中两点的凸组合.已证明，如果LP的可行集S是有界的，那么LP的最优解对应可行集的一个极点.单纯形算法单纯形算法由Dantzig(1963)提出，它是求解LP的一个非常有效的算法.单纯形算法只需在可行集的极点上进行操作.首先，单纯形算法任选一个极点作为初始点此后以改进目标值为依据选取下一个极点.该过程一直到目标值不再改进为止最后一个极点就是最优解.非线性规划非线性规划(NLP)中目标函数是非线性函数或约束条件由非线性函数确定.NLP的一般形式为Kuhn一Tucker条件下降法选一个认为最可能是极大值的点从该点出发构造一个点列，每个点的目标值都比前面点的目标值有所改进.该操作直到满足某终止标准为止.卜直接法只需要目标函数的值.卜梯度法需要函数f的一阶导数的值.卜Hessian法需要函数f的二阶导数的值.实际上，没有一个最好的方法适合所有的问题.一个方法的有效性非常依赖于目标函数.多目标规划MultiobjectiveProgramming在有些时候需要同时考虑多重的，不可比较的，甚至是对立的目标.多目标规划(MOP)由此被提出当各目标呈对立状态时，没有最优解同时极大化所有的目标函数.此时我们借助Pareto解(有效解)的概念，Pareto解意味着若不牺牲其他一个或多个目标，就不可能改进任何一个目标的可行解。目标规划GoalProgramming目标规划(GP)是由Charnes和Cooper(1961)提出的.GP可以看成是多目标优化问题的一种特殊妥协模型.GP的一般形式是算法：线性目标规划可用单纯形法求解.非线性目标规划的求解方法大致有以下几种(a)基于单纯形的方法，其主要思想是把非线性目标规划转化为一组近似的单目标非线性规划问题;(b)直接搜索法，就是把给定的非线性目标规划问题转化为一组单目标非线性规划问题，然后，用单目标非线性规划的直接搜索法求解;(c)基于梯度的方法，该方法是利用约束的梯度，确认一个可行的方法，然后，以可行方向法为基础对目标函数求解;(d)交互法，通过决策者对求解过程的参与，在多次重复的交互程中，最终得到一个满意解;(e)遗传算法，该方法可以处理结构复杂的非线性目标规划模型，但是所花费的CPU时间较多.动态规划多阶段决策过程Bellman最优性原理无论系统的过去状态与决策如何，对于前面的决策所形成的当前状态与决策而言，最优决策的余下的各个分量仍构成一个最优策略.多层规划假设领导者首先在其可行集中选择决策X，而其下属根据这个决策制定了相应的决策(yl，yZ，…，y初.这样就得到如下形式的二层规划模型: