第1章优化算法基本理论.ppt

智能优化算法,第一章优化算法基本理论第二章神经网络基本理论第三章遗传算法基本理论第四章蚁群算法基本理论第五章蜂群算法基本理论第六章粒子群算法基本理论第七章鱼群算法基本理论第八章其他群智能优化算法,课程结构及学时安排,1.1优化的概念与方法1.1.1优化的概念1.1.2优化的一般数学模型1.1.3优化的分类1.1.4优化问题的求解方法1.1.5常用的无约束优化方法1.2智能优化的概念及分类1.2.1智能优化的概念1.2.2智能优化的分类1.3群体智能的概念及分类1.3.1群体智能的概念1.3.2群体智能的分类1.3.3群体智能的特点1.3.2群体智能算法的一般流程,第1章优化算法基本理论,1.1优化的概念及方法1.1.1优化的概念优化、最优化均是一个术语，是指关于求解一个问题的“最优”解的计算科学的一个分支，也就是从各种可能方案中选取一个最好的，以达到最优目标。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。,1.1优化的概念及方法,优化技术是一种以数学为基础、用于求解各种工程问题优化解的应用技术。,1.2智能优化的概念及方法,1.2智能优化的概念及方法1.2.1智能优化的概念人工智能（ArtificialIntelligent，简称AI）是在计算机科学、控制论、信息论、哲学、语言学等多种学科研究基础上发展起来的一门综合性交叉学科。即人工智能就是用人工的方法在机器（计算机）上实现的智能，或者说是人们使机器具有类似于人的智能。智能优化算法（intelligentoptimizationalgorithms）是以模拟物质变化过程或模拟生命体而设计的搜索方式为基础的各类算法的总称。有时也称为启发式算法（modernheuristicalgorithms）、仿生算法、演化算法或进化算法。,1.2智能优化的概念及方法,智能优化算法的本质都属于随机性算法，最大优点是不需要目标函数具有可导性，甚至不需要目标函数有明确的表达形式，只要知道输入输出即可。1.2.2智能优化的分类兔子理论：为了找出地球上最高的山，一群兔子开始想办法。兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。,1.2智能优化的概念及方法,兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。,1.3群体智能的概念及方法,1.3群体智能的概念及方法1.3.1群体智能的概念群体智能（SI）简称群智能，指的是简单智能的个体通过合作表现出复杂智能行为的特性，也就是无智能的主体通过合作表现出智能行为的特性。其本质上是一种概率搜索，不需要问题的梯度信息。群体智能算法的基本思想是模拟自然界生物的群体行为来构造随机优化算法。将搜索和优化过程模拟成个体的进化或觅食过程，用搜索空间中的点模拟自然界中的个体，将求解问题的目标函数度量成个体对环境的适应能力，将个体的优胜劣汰过程或觅食过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。,1.2智能优化的概念及方法,因此，形成一种以“生成+检验”特征的迭代搜索算法，是一种求解极值问题的自适应人工智能技术。也可以说，群智能是一种自下而上的优化方法，即首先设计单个实体的感知、行为机制，然后将一个或一群实体置于环境中，让它们在与环境的交互作用中解决问题。1.3.2群体智能的分类由于群体智能是由社会性动物的自组织行为产生的，因此新算法不断涌现。根据目前的有关报道，主要有粒子群算法、蚁群算法、鱼群算法、蜂群算法、蛙跳算法、布谷鸟算法、萤火虫算法、蝙蝠算法、磷虾群算法、细菌觅食算法、烟花算法、头脑风暴算法、智能水滴算法、磁铁算法等等。,1.2智能优化的概念及方法,1.3.3群体智能的特点灵活性：群体可以适应随时变化的系统或网络环境；分布性：在群体智能中，相互协作的个体是分布式存在的，其初始分布状态可以是均匀或非均匀随机分布，且无中心，个体间完全自组织，体现出群体的智能特征。稳健性：不存在中心或统一的控制，即使某个个体失败，整个群体仍然具有完成任务的能力，不会出现由于某一个或某几个个体出现故障而影响整个问题的求解。也就是说群体智能的整体智慧是通过个体间以及个体与环境间的相互作用而综合体现出来的，因此单个个体对整体的影响较小，不会因其中一个个体的因素影响整体性能。【稳健性】指在不同条件和环境下算法的适应性和有效性。,1.2智能优化的概念及方法,简单性：群体智能中的个体是低智能和简单的，每个个体只能感知局部信息，也只能与局部个体进行信息交流，并且群体中每个个体的能力或遵循的行为规则非常简单，因而群体智能的实现比较方便。可扩充性：群体智能中的个体不仅可以进行相互之间的直接通信，也可以通过环境进行非直接通信，即个体之间通过所处的小环境作为媒介进行交互，具有自组织性。这样就使得整个系统具备良好的可扩展性。自组织性：个体活动既不受中央控制，也不受局部监管，即群体表现出来的复杂行为是通过简单个体的交互而凸现出来的智能。,1.2智能优化的概念及方法,1.3.4群体智能的一般流程Step1：设置参数，初始化种群；Step2