《演化算法概述》PPT课件

《《演化算法概述》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、智能优化方法NatureInspiredComputation考核方式课程设计报告用一种（或多种）智能优化方法，实现实际或者虚拟优化问题的求解。鼓励与本人未来研究领域的结合。报告形式：小论文或实验报告的形式，要求包含：实验目的、技术方案、量化的实验结果、对结果的简单分析（或解释）。提交源程序。12月17日前，将1份打印件放到我的信箱里。课程资源ftp://202.38.67.66Username:networksPassword:networks参考教材：1.《智能优化算法及其应用》，王凌，清华版。2.《

2、遗传算法及其应用》，陈国良等，人民邮电版，1999。第一章概述最优化问题的定义最优化问题的分类关于计算复杂性最优化方法的一般结构最优化问题的定义最优化问题的一般形式为其中xRn是决策变量，f(x)为目标函数，XRn为约束集或可行集。特别地，如果约束集X=Rn，则最优化问题称为无约束最优化问题不仅限于实数集不一定能表示为数学表达式最优化问题的定义约束最优化问题通常写为这里E和I分别是等式约束的指标集和不等式约束的指标集，ci(x)是约束函数．最优化问题的分类按照运筹学的观点分类：线性规划非线性规划整数规

3、划动态规划多目标规划。。。。。。最优化问题的分类从应用的角度分类：数值优化（函数优化，建模）组合优化可靠性设计问题调度问题高级运输问题网络设计与路径……有限资源的最优调配最优化问题举例(1)函数优化令S为Rn上的有界子集，f:SR为n维实值函数，所谓函数f在S域上全局最大化就是寻求点XmaxS使得函数优化问题函数优化问题函数优化问题最优化问题举例(2)系统建模给定模型的结构f(x)和决策变量的定义域；给定实际系统的输入和输出样本数据；寻找一组最优决策变量，使得模型在测试样本集上的输出误差最小。最优化问

4、题举例(3)组合优化定义：组合优化问题π是一个最小化问题，或是一个最大化问题，它由下面三部分组成：(1)实例集合；(2)对每一个实例I，有一个有穷的可行解集合S(I)；(3)目标函数f，它对每一个实例I和每一个可行解，赋以一个有理数。组合优化问题一个通俗的定义：所谓组合优化，是指在离散的、有限的数学结构上，寻找一个（或一组）满足给定约束条件并使其目标函数值达到最大或最小的解。—般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全（难）问题，因此

5、，精确地求解组合优化问题的全局最优解的“有效”算法一般是不存在的。组合优化问题集覆盖问题（set-coveringproblem）装箱问题（bin-packingproblem）背包问题（knapsackproblem）指派问题（assignmentproblem）旅行商问题（travelingsalesmanproblem）影片递送问题（filmdeliveryproblem）最小生成树问题（minimumspantreeproblem）图划分问题（graphpartitioningproblem）作业

6、调度问题（job-shopschedulingproblem）组合优化问题——集覆盖问题集覆盖问题（set-coveringproblem）对于一个m行n列的0－1矩阵A，每行代表一种任务，每列代表一个人，aij=1表示第j个人能完成第i个任务。每个人都有一个雇佣代价。问题的目标是：用最小的代价选择一些人（矩阵的列），使得每一个任务都至少有一个人能完成。设向量x的元素xj=1表示列j被选中（费用是cj>0），xj=0则表示其未被选中（j=1,2,…,n）。已经证明集覆盖问题是NP完全问题。组合优化问题——

7、集覆盖问题如果所有费用cj都相同，则问题称为单一费用问题（unicostset-coveringproblem）。如果为等式约束，则称为集划分问题（setpartitioningproblem）组合优化问题——集覆盖问题Cost=29101010组合优化问题——装箱问题装箱问题（binpackingproblem）所装物品不得超过箱子的容积一个物品只能放入一个箱子用最少的箱子将所有物品都装下组合优化问题——装箱问题货运装箱问题截铜棒问题布匹套裁问题。。。装箱问题属于NP－难问题组合优化问题——背包问题0/

8、1背包问题：给出几个体积为S1，S2，…，Sn的物体和容量为C的背包；要求找出n个物件的一个子集使其尽可能多地填满容量为C的背包。数学形式：最大化满足组合优化问题——背包问题广义背包问题：输入由背包容积C和两个向量：物品体积S＝(S1，S2，…，Sn)和物品价值P＝(P1，P2，…，Pn)组成。设X为一整数集合（物品的标识），X＝1，2，3，…，n，T为X的子集，则问题就是找出满足约束条件，并使总价值最大的子集T。数学形式：最