遗传算法1.ppt

现代智能优化算法现代智能优化算法——遗传算法遗传算法华北电力大学输配电技术研究所华北电力大学输配电技术研究所刘自发刘自发20082008年年22月月简简介介??1995 1995 毕业于东北电力学院,获学士学位毕业于东北电力学院,获学士学位??20002000年毕业于东北电力学院,获硕士学位年毕业于东北电力学院,获硕士学位??20052005年毕业于天津大学,获博士学位年毕业于天津大学,获博士学位??20072007年年UniveristyUniveristy of of OA混沌算法DE??遗传算法(遗传算法(ic Algorithm, ic Algorithm, GA),是模),是模拟达尔文的遗传选择和自然淘汰的生物进化拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它是由美国过程的计算模型。它是由美国MichiganMichigan大学大学的的J. HollandJ. Holland教授于教授于19751975年首先提出的。年首先提出的。??其主要特点是群体搜索策略和群体中个体之其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息,尤间的信息交换,搜索不依赖于梯度信息,尤其适用于处理传统搜索方法难于解决的复杂其适用于处理传统搜索方法难于解决的复杂和非线性问题,可广泛用于组合优化、机器和非线性问题,可广泛用于组合优化、机器学****自适应控制等领域,是学****自适应控制等领域,是2121世界有关智世界有关智能计算中的关键技术之一。能计算中的关键技术之一。GA GA 四个基本条件四个基本条件????,或,或全体全体具有具有多样性多样性????,具有生存能力,具有优良优良基因基因结构结构的的个体个体繁殖能力強,反之則弱繁殖能力強,反之則弱GA -- GA -- 特点特点??遗传算法以决策变量的编码作为运算对象。传遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值统的优化算法往往直接利用决策变量的实际值本身进行优化计算,但遗传算法不是直接以决本身进行优化计算,但遗传算法不是直接以决策变量的值,而是以决策变量的某种形式的编策变量的值,而是以决策变量的某种形式的编码为运算对象,从而可以很方便地引入和应用码为运算对象,从而可以很方便地引入和应用遗传操作算子遗传操作算子??遗传算法直接以目标函数值作为搜索信息。传遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值,还需统的优化算法往往不只需要目标函数值,还需要目标函数的导数等其它信息。这样对许多目要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数,遗传算法标函数无法求导或很难求导的函数,遗传算法就比较方便。就比较方便。GA -- GA -- 特点特点??遗传算法同时进行解空间的多点搜索。传统的遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索,优化算法往往从解空间的一个初始点开始搜索,这样容易陷入局部极值点。遗传算法进行群体这样容易陷入局部极值点。遗传算法进行群体搜索,而且在搜索的过程中引入遗传运算,使搜索,而且在搜索的过程中引入遗传运算,使群体又可以不断进化。这些是遗传算法所特有群体又可以不断进化。这些是遗传算法所特有的一种隐含并行性。的一种隐含并行性。??遗传算法使用概率搜索技术遗传算法使用概率搜索技术。遗传算法属于。遗传算法属于一种自适应概率搜索技术,其选择、交叉、变一种自适应概率搜索技术,其选择、交叉、变异等运算都是以一种概率的方式来进行的,从异等运算都是以一种概率的方式来进行的,从而增加了其搜索过程的灵活性。实践和理论都而增加了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总是以概率已证明了在一定条件下遗传算法总是以概率11收敛于问题的最优解。收敛于问题的最优解。达尔文达尔文18581858年用自然选择来解释物种年用自然选择来解释物种起源和生物的进化,其自然选择学说起源和生物的进化,其自然选择学说包括以下三个方面包括以下三个方面??1 1 遗传遗传种瓜得瓜,种豆得豆。生物有了这种瓜得瓜,种豆得豆。生物有了这个特征,物种才能稳定存在;个特征,物种才能稳定存在;??2 2 变异变异一母生九子,九子各不同。变异的一母生九子,九子各不同。变异的选择和积累是生物多样性的根源;选择和积累是生物多样性的根源;??3 3 适者生存适者生存具有适应性变异的个体被保留具有适应性变异的个体被保留下来,通过一代代生存环境的选