大多数演化计算技术.doc

大多数演化计算技术都是用同样的过程: 2. 对种群内的每一个个体计算适应值(fitness value). 适应值与最优解的距离直接有关。 。 ,就停止,否则转步骤 2。一: 遗传算法( ic Algorithm ) 是一类借鉴生物界的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机化搜索方法。对于一个求函数最大值的优化问题( 求函数最小值也类同), 一般可以描述为下列数学规划模型: 式中 x为决策变量,式 2-1 为目标函数式,式 2-2 、2-3 为约束条件, U是基本空间,R是U的子集。满足约束条件的解 X称为可行解,集合 R表示所有满足约束条件的解所组成的集合,称为可行解集合。遗传算法的基本运算过程如下: a)初始化:设置进化代数计数器 t=0 ,设置最大进化代数 T,随机生成 M个个体作为初始群体 P(0) 。 b)个体评价:计算群体 P(t) 中各个个体的适应度。 c) 选择运算: 将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。 d) 交叉运算; 将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。 e) 变异运算: 将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体 P(t) 经过选择、交叉、变异运算之后得到下一代群体 P(t 1)。 f) 终止条件判断:若 t=T, 则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。适应度(Fitness) 各个个体对环境的适应程度叫做适应度(fitness) 。为了体现染色体的适应能力,引入了对问题中的每一个染色体都能进行度量的函数,叫适应度函数。这个函数是计算个体在群体中被使用的概率。,也称粒子群优化算法( Particle Swarm Optimization ),缩写为 PSO ,是近年来发展起来的一种新的进化算法(( Evolu2tionary Algorithm - EA )。 PSO 算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发, 通过迭代寻找最优解,它也是通过适应度来评价解的品质,但它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作,它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。简介如前所述, PSO 模拟鸟群的捕食行为。设想这样一个场景:一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO 从这种模型中得到启示并用于解决优化问题。 PSO 中,每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value) , 每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就