61优化问题简介

自动化系仪自教研室1智能控制基础6.智能优化方法ShanghaiUniversity,Shanghai,P.R.China6.1概述6.1概述6.1.1优化问题简介6.1.2优化问题的分类6.1.3典型的组合优化问题6.1.4常见的组合优化算法6.1概述6.1.1优化问题简介6.1.2优化问题的分类6.1.3典型的组合优化问题6.1.4常见的组合优化算法minf(x)目标函数Subjectto(s.t.)g(x)=a约束条件h(x)b约束条件6.1.1优化问题简介什么是优化问题？最优化问题，主要是指以下形式的问题：给定一个函数，寻找一个元素使其对于所有A中的，（最小化）；或者（最大化）。这类定式有时还称为“数学规划”（譬如，线性规划）。许多现实和理论问题都可以建模成这样的一般性框架。最优化，是应用数学的一个分支。在优化过程中决策变量搜索的范围或值，组合优化问题中往往是一个可计算的范围。6.1.1优化问题简介最优化问题的搜索空间可行性解满足所有约束条件的解最优解近似最优/次优解可行解且提供最佳目标函数值近似最优解是可行的且提供较好目标函数值，但并非最佳的优化问题的解是指决策变量的值，以及目标函数的值解最优化问题的解6.1.1优化问题简介优化问题一个计算问题，其目的是找到所有可能解中的最优解.(即在可行区域内找到一个解使得目标函数具有最大值或者最小值.)决策问题问题的答案是“是”或者“否”.最优值是什么?优化问题转化为等价的决策问题目标函数的值等于或大于指定值的问题是否存在可行解?6.1.2优化问题的分类优化问题vs决策问题松约束---课程安排上在10点以前没有课程紧约束vs松约束紧约束---在课程安排上没有重叠的课显性约束vs隐性约束线性约束vs非线性约束显性约束--问题中明确说明隐性约束---问题中未明确说明但很明显线性约束---非线性约束---最优化问题的约束条件6.1.1优化问题简介6.1概述6.1.1优化问题简介6.1.2优化问题的分类6.1.3典型的组合优化问题6.1.4常见的组合优化算法连续优化问题一般为连续变量函数的最大值或最小值(无限个可行性解)min4x+5y式中x和y为实数组合优化问题一般为离散变量函数的最大值或最小值(有限个可行性解).min4x+5y式中x和y为countableitems(例如整数)6.1.2优化问题的分类连续优化问题vs组合优化问题确定性优化问题随机性优化问题目标函数和/或一些决策变量和/或一些约束条件是随机变量所有变量都是确定的6.1.2优化问题的分类确定性优化问题vs随机性优化问题凸非凸SRnisconvexifitcontainsallconvexcombinationsofpairsx,yS.z=x+(1)y016.1.2优化问题的分类凸优化问题vs非凸优化问题多项式(P)问题（Polynomial(P)problem）非确定多项式(NP)问题（NondeterministicPolynomial(NP)problems）就是我们能够在多项式时间内检验解是否正确的一类决策问题.即容易验证但是解答起来不易一些算法能够在多项式时间内提供解的一类问题称为P类或者就是P.6.1.2优化问题的分类多项式(P)问题vs非确定多项式(NP)优化问题多项式(P)问题非确定多项式(NP)问题Example:子集和问题,没有已知的算法在多项式时间内找到这样的一个子集(有一个算法，但是是在指数时间内，其需要进行2n-1次尝试),给定一个整数集，它们中的一些非空子集的和可否为0?例如，子集{−2,−3,15,14,7,−10}的和是否为0?答案“是，因为{−2,−3,−10,15}的和为0能够很快将这几个数相加得到。很容易验证，但其解是难以求出的。6.1.2优化问题的分类多项式(P)问题vs非确定多项式(NP)优化问题如果NP所有问题到某一问题都是多项式归约的，则这个问题P称为NP-Hard。NP-Hardproblem多项式归约:问题P在多项式时间内归约另一个问题P´，当且仅当：对于问题P存在一个算法将问题P´作为子程序每次调用问题P'的子程序算作一个单一的步骤对于问题P´，这个算法在多项式时间内运行6.1.2优化问题的分类NP-Hard优化问题vsNP-Complete优化问题16PNPNP-HardNPComplete问题P称为NP-Complete，如果(a)P∈NP,and(b)PisNP-Hard.NP-Completeproblem如果NP所有成员对于这个问题都是多项式归约的，则这个问题P称为NP-Hard。NP-Hardproblem6.1.2优化问题的分类NP-Hard优化问题vsNP-Complete优化问题6.1.2优化问题的分类NP-Hard优化问题vsNP-Complete优化问题6.1概述6.1.1优化问题简介6.1.2优化问题的分类6.1.3典型的组合优化问题6.1.4常见的组合优化算法旅行商问题（TravelingSalesmanProblem－TSP）调度问题（SchedulingProblem）背包问题（KnapsackProblem）装箱问题（BinPackingProblem）图着色问题（GraphColoringProblem）聚类问题（ClusteringProblem）6.1.3典型的组合优化问题典型的组合优化问题TSPwasdefinedinthe1800sbytheIrishmathematicianW.R.HamiltonandbytheBritishmathematicianThomasKirkman.旅行商问题－TSP给定几个城市以及每两个城市之间的距离。如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走的路径最短?问题描述6.1.3典型的组合优化问题旅行商问题－TSP11min()NNijijijdxij数学模型111(,1,2,...)1(,1,2,...)NijiNijjxijjNxijiN1ijijuuNxn..st(,2,...,,2,...,)ijiNjNEachcitybearrived/departedfromexactlyoneothercity只有一条旅行线路覆盖所有城市城市i和j之间距离旅行中城市i和j之间的路径是否包括ijd{0,1}ijx{1,...,}iuN虚拟变量，城市序列6.1.3典型的组合优化问题旅行商问题－TSP中国的旅行商问题(C-TSP)6.1.3典型的组合优化问题旅行商问题－TSP德国的旅行商问题6.1.3典型的组合优化问题旅行商问题－TSP美国旅行商问题6.1.3典型的组合优化问题旅行商问题－TSPTSP最短路径问题在图论中,最短路径问题是在一个图中的两个顶点（或节点）间找到一条路径使得构成边的权重的总和最小的问题。(6,4,5,1)和(6,4,3,2,1)都是顶点6和1之间的路径.任何给定的最短路径往往含有该图中节点的一个合适子集多项式时间问题找到一条路径包含图中每个节点的排列，要求结果为一个循环。NP-completeproblem6.1.3典型的组合优化问题调度问题机器调度（ProcessorScheduling）远程通信带宽调度（Tele-communicationBandwidthScheduling）机场闸门调度（AirportGateScheduling）作业车间调度（Job-shopScheduling）6.1.3典型的组合优化问题作业车间调度（Job-shopScheduling）6.1.3典型的组合优化问题调度问题机器调度（ProcessorScheduling）远程通信带宽调度（Tele-communicationBandwidthScheduling）机场闸门调度（AirportGateScheduling）作业车间调度（Job-shopScheduling）机组检修调度（RepairCrewScheduling）6.1.3典型的组合优化问题调度问题有n个加工量不同的工作J1,J2,...,Jn，需要在m个相同机器上完成加工调度，同时需要使得完工时间最短。完工时间是所有工作完成加工的时间总长度。问题描述6.1.3典型的组合优化问题(最小完工时间)调度问题miny混合整数规划111Nijixin10,1niijiypxjm..st每个作业安排在一台机器每台机器的工作量最多为y工作Ji的加工时间xij=1表示工作i安排在机器j上ipijxxij=0表示工作i未安排在机器j上6.1.3典型的组合优化问题背包问题（KnapsackProblem）给定一系列物品的质量和价值，确定每个物品装包的数量使得总重量小于或者等于给定包给定的限度，并且使得总价值最大。问题描述6.1.3典型的组合优化问题MaximizeMaximizeMaximizesubjecttosubjecttosubjectto0-1背包问题有界背包问题二次型背包问题背包问题6.1.3典型的组合优化问题minimizesubjectto装箱问题（BinPackagingProblem）6.1.3典型的组合优化问题图着色问题（Graphcoloringproblems）顶点着色将图的顶点着色使得图中没有任何相邻两个顶点的颜色相同。边着色颜色分配给每条边使得没有两个相邻边颜色相同。面着色颜色分配给每个面或区域使得没有两个面的边界颜色相同。6.1.3典型的组合优化问题6.1概述6.1.1优化问题简介6.1.2优化问题的分类6.1.3典型的组合优化问题6.1.4常见的组合优化算法算法设计&分析算法效率运行时间存储要求在最坏情况下解决问题基本计算机操作数目设计算法编码算法（算法的步骤/数据结构）应用算法6.1.4常见的组合优化算法优化算法的设计与评价连续最优问题一般为连续变量函数的最大值或最小值(无限个可行性解)min4x+5y式中x和y为实数组合最优问题一般为离散变量函数的最大值或最小值(有限个可行性解).min4x+5y式中x和y为可数项(countableitems)(例如整数)实际上，组合问题通常更难，因为其没有可推导的信息且表面非平滑。6.1.4常见的组合优化算法连续优化问题和组合优化问题的不同牛顿/拟牛顿/高斯--牛顿算法Newton‘s/Quasi-Newton/Gauss–Newtonalgorithms共轭梯度（ConjugateGradient）随机梯度算法（StochasticGradientalgorithms）6.1.4常见的组合优化算法连续优化问题的常见算法状态空间/图表/树搜素算法遗传算法（Geneticalgorithm）群算法（蚁群/粒子群）Swarmalgorithms(Antcolony/Particleswarm)进化优化算法深度优先搜索算法（Depth-firstsearchalgorithm）广度优先搜索算法（Breadth-firstsearchalgorithm）最佳优化搜索算法（Best-firstsearchalgorithms(A*/B*/Greedy)）和谐搜索算法（Harmonysearchalgorithm）“神经”计算算法Hopfield神经网络算法（Hopfieldneuralnetworkalgorithm）模拟退火6.1.4常见的组合优化算法组合优化问题的常见算法分类遗传算法群算法(蚁群/粒子群）深度优化搜素算法广度优化搜素算法最佳优化算法(A*/B*/Greedy)模拟退火算法Hopfield神经网络算法盲目搜索构造型启发式搜素元启发式搜素6.1.4常见的组合优化算法组合优化问题的常见算法分类和声搜索算法非常灵活通常全局最优对问题的大小、