现代智能优化

现代智能优化第1页，共70页，2023年，2月20日，星期六引言现代优化算法包括禁忌搜索（Tabusearch）、模拟退火（Simulatedannealing）、遗传算法（Geneticalgorithms）等，这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念，都是以一定的直观基础而构造的算法，我们称之为启发式算法。启发式算法的兴起与计算复杂性理论的形成有密切的联系，当人们不满足常规算法求解复杂问题时，现代智能优化算法开始体现其作用。现代智能优化算法自八十年代初兴起，至今发展迅速，这些算法同人工智能、计算机科学和运筹学迅速融合，促进了复杂优化问题的分析和解决。下面我们就简要介绍这些算法的基本理论以及MATLAB实现。第2页，共70页，2023年，2月20日，星期六遗传算法特点遗传算法直接以适应度作为搜索信息，求解问题时，搜索过程不受优化函数连续性的约束，无需导数或其他辅助信息；遗传算法具有很高的并行性，可以同时搜索解空间的多个区域搜索信息，从而降低算法陷入局部最优解的可能性；遗传算法具很强的鲁棒性。在待求解问题为非连续、多峰以及有噪声的情况下，它能够以很大的可能性收敛到最优解或近似最优解；遗传算法具有较高的可扩充性。它易于与其它领域的知识或算法相结合来求解特定问题；遗传算法的基本思想简单，具有良好的可操作性和简单性；遗传算法具有较强的智能性，可以用来解决复杂的非结构化问题。第3页，共70页，2023年，2月20日，星期六遗传算法算法流程第4页，共70页，2023年，2月20日，星期六遗传算法基本要素问题编码初始群体的设定适应度函数的设计遗传操作设计控制参数设定(主要是指群体大小和使用遗传操作的概率等)第5页，共70页，2023年，2月20日，星期六遗传算法问题编码第6页，共70页，2023年，2月20日，星期六遗传算法初始群体的设定遗传算法是群体型操作，这样必须为遗传操作准备一个由若干初始解组成的初始群体。初始种群的好坏对于遗传算法的计算结果的优劣和算法的效率有着重要影响。产生初始种群通常有两种方法。一种是完全随机的产生方法，它适用于对待求解问题的解无任何先验知识的情况；另一种是把某些先验知识转化为必须满足的一组要求，然后在满足这些要求的解中随机的选取。这种选择初始种群的方法可以使遗传算法较快地达到最优解。初始群体也称做进化的初始代，即第一代（firstgeneration）。第7页，共70页，2023年，2月20日，星期六遗传算法适应度函数的确定解析性质：连续、非负

合理性：要求适应度函数设计应尽可能简单近似量小：适应度函数对某一类具体问题，应尽可能通用。目标函数的处理方法第8页，共70页，2023年，2月20日，星期六遗传算法第9页，共70页，2023年，2月20日，星期六遗传算法遗传算子选择算子交叉算子变异算子第10页，共70页，2023年，2月20日，星期六选择算子第11页，共70页，2023年，2月20日，星期六选择算子第12页，共70页，2023年，2月20日，星期六选择算子第13页，共70页，2023年，2月20日，星期六交叉算子两个步骤首先在新复制的群体中随机选取两个个体；沿着两个个体（字符串）随机的取一个位置，二者互换从该位置起的末尾部分第14页，共70页，2023年，2月20日，星期六变异算子变异算子模拟了自然界中生物进化过程中个体的基因突变现象，从而改变染色体的结构和物理性状。它是指将个体编码串中的某些基因位上的基因值用该基因位上的其他等位基因来替换，从而产生新的个体。在遗传运算过程中，当交叉操作产生的后代适应度值不再进化，且没有达到最优时，意味着算法陷入了早熟。早熟的根源在于有效基因的缺损，变异算子在一定程度上克服了这种情况，它可以改善遗传算法的局部搜索能力，增加种群的多样性。常见的变异算子包括位点变异、插入变异、对换变异、边界变异、非均匀变异和高斯变异等形式。变异操作就是改变染色体某个（些）位上的基因。例如，设染色体，将其第三位上的0变为1，即。也可以看做是原染色体的子代染色体。第15页，共70页，2023年，2月20日，星期六遗传算法的参数设置第16页，共70页，2023年，2月20日，星期六遗传算法的基本步骤第17页，共70页，2023年，2月20日，星期六遗传算法求解实例第18页，共70页，2023年，2月20日，星期六遗传算法求解实例第19页，共70页，2023年，2月20日，星期六遗传算法求解实例第20页，共70页，2023年，2月20日，星期六遗传算法求解实例第21页，共70页，2023年，2月20日，星期六遗传算法求解实例第22页，共70页，2023年，2月20日，星期六遗传算法求解实例第23页，共70页，2023年，2月20日，星期六遗传算法求解实例第24页，共70页，2023年，2月20日，星期六遗传算法求解实例第25页，共70页，2023年，2月20日，星期六遗传算法求解实例第26页，共70页，2023年，2月20日，星期六遗传算法求解实例第27页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现调用方法x=ga(fitnessfcn,nvars)x=ga(fitnessfcn,nvars,A,b)x=ga(fitnessfcn,nvars,A,b,Aeq,beq)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options)[x,fval]=ga(...)[x,fval,exitflag]=ga(...)第28页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现输入参数和输出参数

第29页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现控制参数设置第30页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现命令详解第31页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现第32页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现第33页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现第34页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现第35页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现第36页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现第37页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现第38页，共70页，2023年，2月20日，星期六遗传算法的MATLAB实现第39页，共70页，2023年，2月20日，星期六模拟退火算法第40页，共70页，2023年，2月20日，星期六模拟退火算法的基本思想第41页，共70页，2023年，2月20日，星期六模拟退火的原理第42页，共70页，2023年，2月20日，星期六模拟退火算法新解的产生和接受第43页，共70页，2023年，2月20日，星期六冷却进度表参数第44页，共70页，2023年，2月20日，星期六模拟退火的算法步骤第45页，共70页，2023年，2月20日，星期六模拟退火算法的参数控制问题第46页，共70页，2023年，2月20日，星期六模拟退火算法的参数控制问题第47页，共70页，2023年，2月20日，星期六模拟退火算法的参数控制问题第48页，共70页，2023年，2月20日，星期六模拟退火算法的参数控制问题第49页，共70页，2023年，2月20日，星期六模拟退火算法的应用实例第50页，共70页，2023年，2月20日，星期六编码选择第51页，共70页，2023年，2月20日，星期六模拟退火新状态产生函数的设计第52页，共70页，2023年，2月20日，星期六新状态接受函数的设计第53页，共70页，2023年，2月20日，星期六初温和初始状态第54页，共70页，2023年，2月20日，星期六温度下降函数的设计第55页，共70页，2023年，2月20日，星期六温度修改准则和算法终止准则的设计第56页，共70页，2023年，2月20日，星期六模拟退火算法的应用实例第57页，共70页，2023年，2月20日，星期六模拟退火的MATLAB工具箱求解第58页，共70页，2023年，2月20日，星期六模拟退火的MATLAB工具箱求解函数详解第59页，共70页，2023年，2月20日，星期六模拟退火的MATLAB工具箱求解第60页，共70页，2023年，2月20日，星期六禁忌搜索禁忌搜索(tabusearch)算法是局部邻域搜索算法的推广，是人工智能在组合优化算法中的一个成功应用．G1over在1986年首次提出这一概念，进而形成一套完整算法，禁忌按索算法的特点是采用了禁忌技术．所谓禁忌就是禁止重复前面的工作。为了回避局部邻城搜索陷入局部最优的主要不足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择的搜索这些点，以此来跳出局部最优点。禁忌搜索算法是—种人工智能算法。第61页，共70页，2023年，2月20日，星期六局部邻域搜索简介第62页，共70页，2023年，2月20日，星期六局部邻域搜索简介第63页，共70页，2023年，2月20日，星期六局部邻域搜索简介局部邻域搜索是基于贪婪算法思想，在当前解的邻域进行持续的搜索，虽然算法比较通用且容易理解实现，但是搜索的性能完全依赖于邻域结构和初始解的选择，尤其容易陷入局部极小值，而无法保证全局最优。针对局部邻域搜索，为了跳出局部最优的限制，可以采用的禁忌搜索尽量避免迂回搜索，禁忌搜索是一种人工智能算法，是局部搜索算法的扩展，它的一个重要思想是标记已得到的局部最扰解，并在进一步的迭代中避开这些局部最优解，下面我们讲解禁忌搜索算法如何避开和记忆这些点。第64页，共70页，2023年，2月20日，星期六禁忌搜索的基本原理第65页，共70页，2023年，2月20日，星期六禁忌搜索算法流程图第66页，共70页，2023年，2月20日，星期六禁忌搜索算法的简化步骤第67页，共70页，2023年，2月20日，星期六禁忌搜索的关键技术初始解的设置适应度函数邻域结构禁忌