现代优化算法

现代智能优化算法授课教师：肖亚峰院系：理学院数学系邮箱：jerry2005@目录Part1概论Part2模拟退火算法Part3遗传算法Part4粒子群算法Part5禁忌搜索算法Part1概论主要是说明现代优化算法的重要性。现代优化算法

现代优化算法禁忌搜索算法模拟退火算法遗传算法人工神经网络蚁群算法粒子群算法混合算法特点：基于客观世界中的一些自然现象；建立在计算机迭代计算的基础上；具有普适性，可解决实际应用问题。如何解决问题？经典数学理论的解法：Viete定理：由公理、定理形成的演绎逻辑体系优点：准确、快速、有明确数学意义不足：只能解决有限问题、解法是特定的无法解决高次问题及更复杂问题。考虑一个一元方程：数值解法：通过引入一些假设来获得问题的近似解

取初始值为1，代入得：

11.580531.577021.57705

优点：可求解问题的范围比较广泛不足：解法的特殊性，要求迭代收敛如何解决问题？（1）传统算法的局限解法是特定的

----不同的问题需要使用不同的解法所能解决的问题是有限的

----和数学工具直接相关，若没有解决问题的数学方法，则难以解决数学建模竞赛中的算法(1)93A非线性交调的频率设计:拟合、规划93B足球队排名次:矩阵论、图论、层次分析法、整数规划94A逢山开路:图论、插值、动态规划94B锁具装箱问题:图论、组合数学95A飞行管理问题

:非线性规划、线性规划95B天车与冶炼炉的作业调度:非线性规划、动态规划、层次分析法、PETRI方法、图论方法、排队论方法96A最优捕鱼策略：微分方程、积分、非线性规划96B节水洗衣机：非线性规划97A零件参数设计：微积分、非线性规划、随机模拟97B截断切割：组合优化、几何变换、枚举、蒙特卡罗、递归、最短路98A投资收益与风险：线性规划、非线性规划98B灾情巡视：最小生成树、Hamilton圈、旅行商问题99A自动化车床：积分、概率分布、随机模拟、分布拟合度检验数学建模竞赛中的算法(2)99B钻井布局：几何变换、枚举、最大完全子图、混合整数规划00ADNA分类：神经网络、最小二乘拟合、统计分类00B管道订购：最短路、二次规划01A血管的三维重建：数据挖掘、曲面重建与拟合01B公交车调度：非线性规划02A车灯光源优化设计：最优化02B彩票中的数学：概率与优化数学建模竞赛中的算法(3)1.

蒙特卡罗方法(Monte-Carlo方法,MC)数学建模竞赛常用算法(1)

该算法又称计算机随机性模拟方法，也称统计试验方法。MC方法是一种基于“随机数”的计算方法，能够比较逼真地描述事物的特点及物理实验过程，解决一些数值方法难以解决的问题。MC方法的雏型可以追溯到十九世纪后期的蒲丰随机投针试验，即著名的蒲丰问题。MC方法通过计算机仿真(模拟)解决问题，同时也可以通过模拟来检验自己模型的正确性，是比赛中经常使用的方法。97年的A题每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。02年的B题关于彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。数学建模竞赛常用算法98年美国赛A题

生物组织切片的三维插值处理94年A题逢山开路

山体海拔高度的插值计算数学建模竞赛常用算法(2)2.数据拟合、参数估计、插值等数据处理算法

比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB作为工具。与图形处理有关的问题很多与拟合有关系。

此类问题在MATLAB中有很多函数可以调用，只有熟悉MATLAB，这些方法才能用好。98年B题用很多不等式完全可以把问题刻画清楚数学建模竞赛常用算法(3)3.规划类问题算法

此类问题主要有线性规划、整数规划、多元规划、二次规划等。竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了。

因此列举出规划后用Lindo、Lingo等软件来进行解决比较方便，所以还需要熟悉这两个软件。98年B题、00年B题、95年锁具装箱等问题体现了图论问题的重要性。数学建模竞赛常用算法(4)4.

图论问题

这类问题算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等问题。92年B题用分枝定界法97年B题是典型的动态规划问题98年B题体现了分治算法数学建模竞赛常用算法(5)5.计算机算法设计中的问题

计算机算法设计包括很多内容：动态规划、回溯搜索、分治算法、分枝定界等计算机算法.

这方面问题和ACM程序设计竞赛中的问题类似，可看一下与计算机算法有关的书。97年A题用模拟退火算法00年B题用神经网络分类算法01年B题这种难题也可以使用神经网络美国89年A题也和BP算法有关系美国03年B题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。数学建模竞赛常用算法(6)6.最优化理论的三大非经典算法:

模拟退火法(SA)、神经网络(NN)、遗传算法(GA)

近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。97年A题、99年B题都可以用网格法搜索数学建模竞赛常用算法(7)

网格算法和穷举法一样，只是网格法是连续问题的穷举。此类算法运算量较大。7.网格算法和穷举算法

这种方法最好在运算速度较快的计算机中进行，还有要用高级语言来做，最好不要用MATLAB做网格，否则会算很久的。

很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此需要将连续问题进行离散化处理后再用计算机求解。比如差分代替微分、求和代替积分等思想都是把连续问题离散化的常用方法。数学建模竞赛常用算法(8)8.连续问题离散化的方法

数值分析研究各种求解数学问题的数值计算方法，特别是适合于计算机实现方法与算法。数学建模竞赛常用算法(9)9.数值分析方法

它的主要内容包括函数的数值逼近、数值微分与数值积分、非线性方程的数值解法、数值代数、常微分方程数值解等。数值分析是计算数学的一个重要分支，把理论与计算紧密结合,是现代科学计算的基础。MATLAB等数学软件中已经有很多数值分析的函数可以直接调用。01年A题中需要你会读BMP图象98年美国A题需要你知道三维插值计算03年B题要求更高，不但需要编程计算还要进行处理数学建模竞赛常用算法(10)10.图象处理算法

赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB进行处理。

数模论文中也有很多图片需要展示，解决这类问题要熟悉MATLAB图形图像工具箱。最优化问题(OptimizationProblem)最优化问题:组合优化问题(CombinatorialOptimizationProblem):最优化问题中的解空间X或S由离散集合构成。其中很多问题是NP完全(NondeterministicPolynomialCompleteness)问题.待解决的问题

连续性问题，以微积分为基础，规模较小传统的优化方法理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性、收敛速度

传统优化方法

现代优化算法

现代优化算法又称智能优化算法或现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据,而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。待解决的问题

离散性、不确定性、大规模现代的优化方法启发式算法（heuristicalgorithm）追求满意（近似解）实用性强（解决实际工程问题）现代的评价方法算法复杂性

现代优化方法

现代优化算法的特点

它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。全局优化Rastrigin’sFunction全局最小点(0,0)现代优化算法特点：1)不依赖于初始条件；2)不与求解空间有紧密关系,对解域无可微或连续的要求;容易实现，求解稳健。3)但收敛速度慢,能获得全局最优;适合于求解空间不知的情况。4)SA,GA可应用于大规模、多峰多态函数、含离散变量等全局优化问题;求解速度和质量远超过常规方法。常用的现代优化算法

遗传算法

GeneticAlgorithm，简称GA模拟退火算法

SimulatedAnnealing，简称SA禁忌搜索算法

TabuSearch，简称TS

……常用的现代优化算法（续）

神经网络算法群智能算法，包括蚁群算法(AntColonyOptimization)、粒子群算法(ParticleSwarmOptimization)

微分进化算法（DifferentialEvolution）

智能优化计算典型问题——旅行商问题（Travelingsalesmanproblem,TSP）给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。123412181032搜索示例：TSP问题典型问题——旅行商问题（Travelingsalesmanproblem,TSP）计算复杂度：指数灾难

城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325yearTSP的搜索的困难Part2模拟退火法模拟退火算法及模型

算法的提出

模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。物理退火过程物理退火过程

什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。物理退火过程模拟退火算法及模型

智能优化计算物理退火过程

加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。物理退火过程模拟退火算法及模型

智能优化计算数学表述

在温度T，分子停留在状态r满足Boltzmann概率分布物理退火过程模拟退火算法及模型

智能优化计算数学表述在同一个温度T，选定两个能量E1<E2，有在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。物理退火过程<1>0模拟退火算法及模型

智能优化计算数学表述

若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于1。物理退火过程能量最低状态非能量最低状态模拟退火算法及模型

智能优化计算Metropolis准则（1953）——以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。物理退火过程模拟退火算法及模型

智能优化计算Metropolis准则（1953）——以概率接受新状态若在温度T，当前状态i→新状态j

若Ej<Ei，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]

大于[0,1)区间的随机数，则仍接受状态j

为当前状态；若不成立则保留状态i

为当前状态。物理退火过程模拟退火算法及模型

智能优化计算Metropolis准则（1953）——以概率接受新状态

p=exp[-(Ej-Ei)/kBT]

在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。物理退火过程模拟退火算法及模型

智能优化计算相似性比较

组合优化与物理退火的相似性组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量算法描述模拟退火算法及模型

智能优化计算基本步骤

给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。模拟退火算法的基本思想和步骤模拟退火算法及模型

智能优化计算影响优化结果的主要因素

给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。模拟退火算法的基本思想和步骤三函数两准则初始温度模拟退火算法关键参数和操作的设计智能优化计算原则

(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；

(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；

(3)当温度趋于零时，只能接受目标函数下降的解。方法

具体形式对算法影响不大一般采用min[1,exp(-∆C/t)]状态接受函数模拟退火算法关键参数和操作的设计智能优化计算收敛性分析

通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；初温应充分大；实验表明

初温越大，获得高质量解的机率越大，但花费较多的计算时间；初温模拟退火算法关键参数和操作的设计智能优化计算方法

（1）均匀抽样一组状态，以各状态目标值得方差为初温；（2）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；（3）利用经验公式。初温模拟退火算法关键参数和操作的设计智能优化计算时齐算法的温度下降函数

（1），α越接近1温度下降越慢，且其大小可以不断变化；（2），其中t0为起始温度，K为算法温度下降的总次数。温度更新函数模拟退火算法关键参数和操作的设计智能优化计算非时齐模拟退火算法

每个温度下只产生一个或少量候选解时齐算法——常用的Metropolis抽样稳定准则

（1）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；（3）按一定的步数抽样。内循环终止准则模拟退火算法关键参数和操作的设计智能优化计算常用方法

（1）设置终止温度的阈值；（2）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法。外循环终止准则智能优化计算模拟退火算法的优点

质量高；初值鲁棒性强；简单、通用、易实现。模拟退火算法的缺点

由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。模拟退火算法的优缺点模拟退火算法的实现与应用智能优化计算30城市TSP问题（d*=423.741byDBFogel）

TSPBenchmark问题

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450模拟退火算法的实现与应用智能优化计算算法流程

30城市TSP问题（d*=423.741byDBFogel）

模拟退火算法的实现与应用智能优化计算初始温度的计算

fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0))/log(0.9);

30城市TSP问题（d*=423.741byDBFogel）

模拟退火算法的实现与应用智能优化计算状态产生函数的设计（1）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。30城市TSP问题（d*=423.741byDBFogel）

283591467283591467283591467281593467283419567235981467模拟退火算法的实现与应用智能优化计算参数设定

截止温度tf=0.01;

退温系数alpha=0.90;

内循环次数L=200*CityNum;34城市TSP问题智能优化计算优化前的一个随机路线轨迹图智能优化计算优化后的路线轨迹图最优解的进化过程计算结果初始种群中的一个随机值:33—>29—>11—>15—>27—>16—>3—>17—>32—>26—>9—>2—>24—>19—>30—>13—>31—>34—>5—>25—>22—>21—>4—>6—>7—>28—>12—>20—>10—>14—>23—>18—>8—>1—>33总距离：41.4801最优解:27—>7—>1—>3—>24—>21—>16—>20—>18—>10—>4—>25—>11—>34—>5—>17—>22—>26—>33—>13—>15—>23—>19—>12—>8—>30—>14—>31—>32—>9—>29—>2—>28—>6—>27总距离：17.9213-------------------------------------------------------------Elapsedtimeis4.363902seconds.算法的改进(1)设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。(2)设计高效的退火策略。(3)避免状态的迂回搜索。(4)采用并行搜索结构。(5)为避免陷入局部极小，改进对温度的控制方式(6)选择合适的初始状态。(7)设计合适的算法终止准则。算法的改进也可通过增加某些环节而实现对模拟退火算法的改进。主要的改进方式包括：(1)增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。(2)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将“BestSoFar”的状态记忆下来。(3)增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。(6)上述各方法的综合应用。Part3遗传算法遗传算法(GeneticAlgorithm)进化算法(EvolutionaryAlgorithm)遗传算法(GA)Darwin(1859):“物竟天择，适者生存”JohnHolland(universityofMichigan,1975)

《AdaptationinNaturalandArtificialSystem》遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工的方式对目标空间进行随机化搜索。

遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法的搜索机制局部全局遗传算法(GA)Wehaveadream!!IamatthetopHeightis...Iamnotatthetop.Myhighisbetter!Iwillcontinue遗传算法(GA)GA-----第0代DeadoneNewone遗传算法(GA)GA----第1代Notatthetop,ComeUp!!!遗传算法(GA)GA----第?代IamtheBEST!!!遗传算法(GA)GA----第N代适者生存(SurvivaloftheFittest)GA主要采用的进化规则是“适者生存”较好的解保留，较差的解淘汰遗传算法(GA)基本遗传算法基本遗传算法（SimpleGeneticAlgorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。SGA实例1：函数最值SGA参数:编码方式:二进制码

e.g.000000;01101

13;1111131种群规模:4随机初始群体“转盘赌”选择一点杂交,二进制变异求函数f(x)=x2的最大值，x为自然数且0≤x≤31.手工方式完成演示SGA过程SGA实例1maxx2:选择操作SGA实例1maxx2:交叉操作SGA实例1maxx2:变异操作SGA实例2:连续函数最值求下列函数的最大值：SGA实例2:编码高精度

编码[x,y]

{0,1}L

必须可逆(一个表现型对应一个基因型)

解码算子：

:{0,1}L

[x,y]

染色体长度L决定可行解的最大精度长染色体(慢进化)

实数问题：变量z为实数，如何把{a1,…,aL}

{0,1}Lz∈[x,y]SGA实例2:编码设定求解精确到6位小数，因区间长度位2-(-1)=3,则需将区间分为3X106等份。因2097152＝221<3X106≤222＝4194304。故编码的二进制串长L=22。将一个二进制串(b21b20…b0)转化为10进制数：e.g.<0000000000000000000000>-1;<1111111111111111111111>2<1110000000111111000101>1.6278881.627888=-1+3x(1110000000111111000101)2

/(222-1)=-1+3x3674053/(222-1)SGA实例2:初始化种群、适应函数随机初始化种群适应函数本实例目标函数在定义域内均大于0，且是求函数最大值，故直接引用目标函数作为适应函数：

f(s)=f(x)

其中二进制串s对于变量x的值。

e.g.s1=<0000001110000000010000>x1=-0.958973

适应值:f(s1)=f(x1)=1.078878

s2=<1110000000111111000101>x2=1.627888

适应值:f(s2)=f(x2)=3.250650SGA实例2:遗传操作选择操作(“轮盘赌”选择)交叉操作(单点交叉)

交叉前(父):

s1=<00000|01110000000010000>s2=<11100|00000111111000101>

交叉后(子):

s’1=<00000|

00000111111000101>s’2=<11100|

01110000000010000>

适应值:f(s’1)=f(-0.998113)=1.940865f(s’2)=f(1.666028)=3.459245

s’2的适应值比其双亲个体的适应值高。SGA实例2:遗传操作变异操作

变异前(父):

s2=<1110000000111111000101>

变异后(子):

s’2=<1110100000111111000101>

适应值

f(s’2)=f(1.721638)=0.917743

比f(s2)小

变异前(父):

s2=<1110000000111111000101>

变异后(子):

s”2=<1110000001111111000101>

适应值

f(s”2)=f(1.630818)=3.343555比f(s2)大变异操作有”扰动”作用，同时具有增加种群多样性的效果。SGA实例2:模拟结果遗传算法的参数:

种群规模:50

染色体长度:L=22

最大进化代数:150

交叉概率:Pc=0.25

变异概率:Pm=0.01

SGA实例2:模拟结果(最佳个体进化情况)世代数染色体编码变量x适应值141117344054718915010001110000101100011110000011011000101001111011010101110011100111111101010111111010011111100001101111011001111110100100010001100111110001101101000110011110100110110001011001111110100111111001100111111010011111100110011111.8316241.8424161.8548601.8475361.8532901.8484431.8486991.8508971.8505491.8505493.5348063.7903623.8332863.8420043.8434023.8462323.8471553.8501623.8502743.850274

遗传算法简介

达尔文的自然选择说遗传（heredity）：子代和父代具有相同或相似的性状，保证物种的稳定性；变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。自然选择过程是长期的、缓慢的、连续的过程。

生物进化理论和遗传学的基本知识

遗传算法简介

遗传学基本概念与术语染色体（chromosome）：遗传物质的载体；脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；

生物进化理论和遗传学的基本知识

遗传算法简介

遗传学基本概念与术语基因型（genotype）：遗传因子组合的模型；表现型（phenotype）：由染色体决定性状的外部表现；

生物进化理论和遗传学的基本知识

1111111

1110111

遗传算法简介

遗传学基本概念与术语基因座（locus）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（allele）；个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合，该集合内个体数称为种群的大小；

生物进化理论和遗传学的基本知识

遗传算法简介

遗传学基本概念与术语进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;

生物进化理论和遗传学的基本知识

遗传算法简介

智能优化计算遗传学基本概念与术语选择（selection）：指决定以一定的概率从种群中选择若干个体的操作；复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;

生物进化理论和遗传学的基本知识

遗传算法简介

智能优化计算遗传学基本概念与术语变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。

生物进化理论和遗传学的基本知识

遗传算法简介

智能优化计算进化论与遗传学的融合

1930～1947年，达尔文进化论与遗传学走向融合，Th.Dobzhansky1937年发表的《遗传学与物种起源》是融合进化论与遗传学的代表作。生物进化与智能学的关系生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。

生物进化理论和遗传学的基本知识

遗传算法简介

智能优化计算遗传算法的基本思路

遗传算法的思路与特点

遗传算法简介

智能优化计算自组织、自适应和自学习性在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。本质并行性内在并行性与内含并行性不需求导只需目标函数和适应度函数概率转换规则强调概率转换规则，而不是确定的转换规则

遗传算法的思路与特点

遗传算法简介

智能优化计算选择

适应度计算：按比例的适应度函数（proportionalfitnessassignment）基于排序的适应度计算（Rank-basedfitnessassignment）

选择算法：轮盘赌选择（roulettewheelselection）

遗传算法的基本操作

遗传算法简介

智能优化计算选择

选择算法：随机遍历抽样（stochasticuniversalselection）局部选择（localselection）截断选择（truncationselection）锦标赛选择（tournamentselection）

遗传算法的基本操作

遗传算法简介

智能优化计算交叉或基因重组

实值重组（realvaluedrecombination）：离散重组（discreterecombination）中间重组（intermediaterecombination）线性重组（linearrecombination）扩展线性重组（extendedlinearrecombination）

遗传算法的基本操作

遗传算法简介

智能优化计算交叉或基因重组

二进制交叉（binaryvaluedcrossover）：单点交叉（single-pointcrossover）多点交叉（multiple-pointcrossover）均匀交叉（uniformcrossover）洗牌交叉（shufflecrossover）缩小代理交叉（crossoverwithreducedsurrogate）

遗传算法的基本操作

遗传算法简介

智能优化计算变异

实值变异

二进制变异

遗传算法的基本操作

生物进化与遗传算法对应关系生物进化遗传算法适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交叉以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程环境适应函数遗传算法的基本操作选择(selection):

根据各个个体的适应值，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。交叉(crossover):

将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率Pc(称为交叉概率，crossvoerrate)交换它们之间的部分染色体。变异(mutation):

对群体P(t)中的每一个个体，以某一概率Pm(称为变异概率，mutationrate)改变某一个或一些基因座上基因值为其它的等位基因。如何设计遗传算法如何进行编码？如何产生初始种群？如何定义适应函数？如何进行遗传操作(复制、交叉、变异)？如何产生下一代种群？如何定义停止准则？编码(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间={0,1}L0111010010100010011001001010010001选择(Selection)选择(复制)操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中

主要思想:适应值较高的染色体体有较大的选择(复制)机会实现1：”轮盘赌”选择(Roulettewheelselection)将种群中所有染色体的适应值相加求总和，染色体适应值按其比例转化为选择概率Ps产生一个在0与总和之间的的随机数m从种群中编号为1的染色体开始，将其适应值与后续染色体的适应值相加，直到累加和等于或大于m选择(Selection)设种群的规模为Nxi是i为种群中第i个染色体AC1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=2染色体xi被选概率选择(Selection)染色体的适应值和所占的比例轮盘赌选择选择(Selection)随机数23491338627所选号码262514所选染色体110000001111000011000111010010染色体编号123456染色体011101100000100100100110000011适应度81525128被选概率0.160.30.040.10.240.16适应度累计8

23

253042

50染色体被选的概率被选的染色体选择(Selection)轮盘上的片分配给群体的染色体，使得每一个片的大小与对于染色体的适应值成比例从群体中选择一个染色体可视为旋转一个轮盘，当轮盘停止时，指针所指的片对于的染色体就时要选的染色体。模拟“轮盘赌”算法：r=random(0,1)，s=0，i=0；如果s≥r，则转(4)；s=s+p(xi)，i=i+1,转(2)xi即为被选中的染色体，输出I结束选择(Selection)其他选择法：随机遍历抽样(Stochasticuniversalsampling)局部选择(Localselection)截断选择(Truncationselection)竞标赛选择(Tournamentselection)特点：选择操作得到的新的群体称为交配池，交配池是当前代和下一代之间的中间群体，其规模为初始群体规模。选择操作的作用效果是提高了群体的平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体的多样性。选择操作没有产生新的个体，群体中最好个体的适应值不会改变。交叉(crossover,Recombination)遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体，从而检测搜索空间中新的点。选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取的两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不同，且彼此不同,每个子染色体都带有双亲染色体的遗传基因。单点交叉(1-pointcrossover)在双亲的父代染色体中随机产生一个交叉点位置在交叉点位置分离双亲染色体互换交叉点位置右边的基因码产生两个子代染色体交叉概率Pc一般范围为(60%,90%)，平均约80%11111111父代1111000000000000子代111100000000000011111111交叉点位置交叉(crossover,Recombination)单点交叉操作可以产生与父代染色体完全不同的子代染色体；它不会改变父代染色体中相同的基因。但当双亲染色体相同时，交叉操作是不起作用的。假如交叉概率Pc＝50%,则交配池中50%的染色体(一半染色体)将进行交叉操作，余下的50%的染色体进行选择(复制)操作。GA利用选择和交叉操作可以产生具有更高平均适应值和更好染色体的群体变异(Mutation)以变异概率Pm改变染色体的某一个基因,当以二进制编码时，变异的基因由0变成1，或者由1变成0。变异概率Pm一般介于1/种群规模与1/染色体长度之间，平均约1-2%11010100父代01010101子代变异基因变异基因变异(Mutation)比起选择和交叉操作，变异操作是GA中的次要操作，但它在恢复群体中失去的多样性方面具有潜在的作用。

在GA执行的开始阶段，染色体中一个特定位上的值1可能与好的性能紧密联系，即搜索空间中某些初始染色体在那个位上的值1可能一致产生高的适应值。因为越高的适应值与染色体中那个位上的值1相联系，选择操作就越会使群体的遗传多样性损失。等到达一定程度时，值0会从整个群体中那个位上消失，然而全局最优解可能在染色体中那个位上为0。如果搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是到达全局最优解所需要的。适应函数(FitnessFunction)GA在搜索中不依靠外部信息，仅以适应函数为依据，利用群体中每个染色体(个体)的适应值来进行搜索。以染色体适应值的大小来确定该染色体被遗传到下一代群体中的概率。染色体适应值越大，该染色体被遗传到下一代的概率也越大；反之，染色体的适应值越小，该染色体被遗传到下一代的概率也越小。因此适应函数的选取至关重要，直接影响到GA的收敛速度以及能否找到最优解。群体中的每个染色体都需要计算适应值适应函数一般由目标函数变换而成适应函数(FitnessFunction)适应函数常见形式：直接将目标函数转化为适应函数若目标函数为最大化问题：

Fitness(f(x))=f(x)若目标函数为最小化问题：

Fitness(f(x))=-f(x)缺点:(1)可能不满足轮盘赌选择中概率非负的要求

(2)某些代求解的函数值分布上相差很大，由此得到的评价适应值可能不利于体现群体的评价性能，影响算法的性能。适应函数(FitnessFunction)界限构造法

目标函数为最大化问题其中Cmin为f(x)的最小估计值

目标函数为最小化问题其中Cmaxn为f(x)的最大估计值停止准则(TerminationCriteria)种群中个体的最大适应值超过预设定值种群中个体的平均适应值超过预设定值种群中个体的进化代数超过预设定值基本步骤(StepbyStep)(1)随机产生初始种群;(2)计算种群体中每个个体的适应度值,判断是否满足停止条件，若不满足，则转第(3)步,否则转第(6)步;(3)按由个体适应值所决定的某个规则选择将进入下一代的个体;(4)按交叉概率Pc进行交叉操作,生产新的个体;(5)按变异概率Pm进行变异操作,生产新的个体;(6)输出种群中适应度值最优的染色体作为问题的满意解或最优解。流程图(FlowChart)SGA伪码描述ProcedureGeneticAlgorithm

begint=0;初始化P(t);计算P(t)的适应值;while(不满足停止准则)dobegint=t+1;

从P(t-1)中选择P(t);%selection

重组P(t);%crossoverandmutation

计算P(t)的适应值;end

end无约束最优化问题GA编码：X=(x1,x2,…,xn)的各个变量可以按二进制编码方法分别编码。对于变量xi的上、下限约束li≤xi≤

ui(i=1,2,…,n)，依据解的精度要求(有效位数)求得各个变量X=(x1,x2,…,xn)的二进制码位数(m1,m2,…,mn)(确定方法类似于SGA实例2)，因此将n个二进制位串顺序连接起来，构成一个个体的染色体编码，编码的总位数m＝m1+m2+…+mn。无约束最优化问题:无约束最优化问题GA解码：解码时仍按各个变量的编码顺序分别实现常规的二进制编码解码方法。二进制遗传编码示意图如下：约束最优化问题常规解法：(1)把约束问题转化为无约束问题，在用无约束问题方法求解，如罚函数法(2)改进无约束问题的方法，再用于约束问题，如梯度投影法、广义简约梯度法约束最优化问题:约束最优化问题遗传算法求解关键:约束条件的处理等式约束可以包含到适应函数，仅考虑不等式约束。假设按无约束问题那样求解，在搜索过程中计算目标函数值，并检查是否有约束违反。如果没有违反，则表明是可行解，就根据目标函数指定一适应值；否则，就是不可行解，因而没有适应值(适应值为0)。这样的处理实际不可行，因为找到一个可行解几乎与找到最优解一样困难。一般解法：通过引入罚函数，从不可行解中得到一些信息。将罚函数包含到适应函数中。关键是如何设计罚函数；不同问题需要设计不同的罚函数；对一般的约束处理，通常很困难。约束最优化问题组合最优化问题典型问题：巡回旅行商问题(TravelingSalesmanProblem)作业调度问题(JobShopSchedulingProblem)背包问题(KnapsackProblem)图着色问题…

…

…很多组合最优化问题是NP难问题或NP完全问题巡回旅行商问题(TSP)TSP，也称货郎担问题，是一个NP完全问题。TSP描述：图论:设图G=(V,E),其中V是顶点集，E是边集。设C=(cij)是与E相联系的距离矩阵。寻找一条通过所有顶点且每个顶点只通过一次的最短距离回路(Hamilton回路)。实际应用中，C也可解释为费用或旅行时间矩阵。实际:一位推销员从自己所在城市出发，必须遍访所有城市之后又回到原来的城市，求使其旅行费用最少的路径。巡回旅行商问题(TSP)中国货郎担问题:城市数:40城市编号1,2,…,40寻找一条最短路径TSP复杂性搜索空间庞大TSP涉及求多个变量的函数的最小值，求解很困难。其可能的路径条数随着城市数目n成指数增长，如，5个城市对应12条路径；10个城市对应181440条路径；100个城市对应4.6663X10155条路径。如此庞大的搜索空间，常规解法和计算工具都遇到计算上的困难。只能寻找近似解法，如神经网络方法、模拟退火法、遗传算法等。TSP编码:路径表示染色体表示成所有城市的一个排列，若有n个城市，一条可能路径编码为长度为n的整数向量(i1,i2,…,in),其中ik表示第ik个城市。例如:路径编码向量(517894623)直接表示一条旅行路程(5->1->7->8->9->4->6->2->3)。此向量是1到n的一个排列，即从1到n的每个整数在这个向量中正好出现一次,不能有重复。这样，基本遗传算法的基因操作生成的个体不能满足这一约束条件，需寻求其他遗传操作。TSP交叉需其他方式的交叉(重组)操作,如部分匹配交叉(PartiallyMatchedCrossover,PMX)、顺序交叉(OrderedCrossover,OX)、循环交叉(CycleCrossover,CX)、边重组(EdgeRecombination)。12345543211232154345一般的交叉操作会产生不合适的解，如TSP交叉1:部分匹配交叉(PMX)双亲P1,P2随机选取两个交叉点，得到一个匹配段,根据交叉点中间段给出映射关系。123456789937826514xxx4567xxxxx8265xxP1P2映射关系：48、52、75c1c2

交换两个交叉点之间的编码,(X表示未定码)TSP交叉1:部分匹配交叉(PMX)子个体C1，C2分别从其父个体中继承未映射城市码12345678993782651493x45671x1x38265x9P1P2c1c2映射关系：48、52、75932456718173826549c1c2

再根据映射关系，对以上未定码，使用最初双亲码，得到子个体的对应码。映射关系存在传递关系，则选择未定码交换。TSP交叉2:顺序交叉(OX)双亲P1,P2随机选取两个交叉点123456789937826514P1P2xxx4567xxxxx8265xxc1c2

两个交叉点间的中间段保存不变

子个体C1的未定码的确定需要父个体P2的未选定城市码，子个体C2的未定码的确定需要父个体P1的未选定城市码。TSP交叉2:顺序交叉(OX)记取父个体P2从第二个交叉点开始城市码的排列顺序，当到达表尾时，返回表头继续记录，直到第二个交叉点。937826514P2xxx4567xxc1382456719c1347826591c2

得到父个体P2的排列顺序1-4-9-3-7-8-2-6-5,并将C1已有城市码4,5,6,7从中去掉，得到排列顺序1-9-3-8-2，再将此顺序复制到C1，复制点也是从第二个交叉点开始，得到C1。同理的C2，TSP交叉3:循环交叉(CX)CX操作中子个体中的城市码顺序根据任一父个体产生确定循环编码

复制循环编码到子个体TSP变异InsertMutation随机选取个体中两个编码，然后把第二个编码放在第一个编码之后，其他编码顺次调节位置。

Swapmutation随机选取个体中两个编码，然后交换它们的位置。TSP变异Inversionmutation随机选取个体中一段编码，然后颠倒这段编码的顺序。

Scramblemutation随机选取个体上一段编码,然后打乱这段编码的顺序。选取的编码不一定是邻接编码TSP的GA过程从N个随机起点开始产生N条路径，N为种群的规模;利用最优方法搜索每条路径的局部最优解;选择交叉对使在平均性能之上的个体得到更多的子代;交叉和变异;搜索每条路径得到其极小解，如果不收敛，则回到第3步；否则，停止。GA的MATLAB实现软件平台(SoftwarePlatforms):MATLAB7.xGeneticAlgorithmandDirectSearchToolbox

2.0.1

MATLAB6.x(or7.x)+GAOTGAOT:GeneticAlgorithmOptimizationToolbox美国NorthCarolinaStateUniversity开发MATLAB6.x(or7.x)+GEATbxGEATbx:GeneticandEvolutionaryAlgorithmToolbox英国TheUniversityofSheffield开发《MATLAB遗传算法工具箱及应用》(雷英杰等,西安电子科技大学出版社,2005)基于此工具箱

GAOT工具箱核心函数：[pop]=initializega(num,bounds,eevalFN,eevalOps,options)------初始种群的生成函数【输出参数】pop-----生成的初始种群【输入参数】num-----种群中的个体数目

bounds-----代表变量的上下界的矩阵

eevalFN-----适应度函数

eevalOps-----传递给适应度函数的参数

options-----选择编码形式(浮点编码或是二进制编码)与精度，如[typeprec]，type-----为1时选择浮点编码，否则为二进制编码prec-----变量进行二进制编码时指定的精度，默认[1e-61]GAOT工具箱(2)[x,endPop,bPop,traceInfo]=ga(bounds,evalFN,evalOps,startPop,opts,termFN,termOps,selectFN,…selectOps,xOverFNs,xOverOps,mutFNs,mutOps)

-------遗传算法函数

【输出参数】

x------求得的最优解

endPop------最终得到的种群

bPop------最优种群的一个搜索轨迹

traceInfo------每代种群中最优及平均个体构成的矩阵

【输入参数】

bounds------代表变量上下界的矩阵

evalFN------适应度函数

evalOps------传递给适应度函数的参数

startPop------初始种群GAOT工具箱【输入参数】opts-------[epsilonprob_opsdisplay]，opts(1:2)等同于initializega的options参数，第三个参数控制是否输出，一般为0。如[1e-610]termFN-------终止函数的名称,如['maxGenTerm']termOps-------传递个终止函数的参数,如[100]selectFN-------选择函数的名称,如['normGeomSelect']selectOps-------传递个选择函数的参数,如[0.08]xOverFNs-------交叉函数名称表，以空格分开，如['arithXoverheuristicXoversimpleXover']xOverOps-------传递给交叉函数的参数表，如[20;23;20]mutFNs-------变异函数表，如['boundaryMutationmultiNonUnifMutationnonUnifMutationunifMutation']mutOps-------传递给交叉函数的参数表,如[400;61003;41003;400]GAOT:函数最值(实例)求下列函数的最大值：GAOT:函数最值(实例2)Fitness.m文件function[sol,eval]=fitness(sol,options)x=sol(1);eval=x*sin(10*pi*x)+2.0;MATLAB运行结果：GeneticAlgorithmandDirectSearchToolbox(GA&DS)包含工具:遗传算法/直接搜索运行方式:commandline;gatoolGA解决的问题类:

最大化问题要转化为最小化问题

最小化问题GeneticAlgorithmandDirectSearchToolbox(GA&DS)最优化问题案例讲解算例1.简单一元函数优化利用遗传算法寻找以下函数的最小值 ，注：○是每代的最优解，*是优化20代后的种群分布，从图中可以看出，○和*大部分都集中在一个点，该点即为最优解。目标函数图、每代的最优解及经过20代进化后的种群分布图最优解的进化过程最后的计算结果：最优解:X=1.1491Y=-0.8699算例2.多元函数优化利用遗传算法计算函数，