董素媛遗传算法.doc

icAlgorithm(GA)-----AnBriefIntroduction-----一、遗传算法的概述起源和特点:遗传算法是模拟达尔文的遗传选择和自然淘汰、适者生存的生物进化过程的计算模型,是由美国Michigan(密西根),是搜索最优解的一种随机化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换,是近十多年来备受关注的一种算法。搜索机制:遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象,在每次迭代中都保留一组候选解,并按某种指标从解群中选取较优的个体,利用遗传算子(选择、交叉和变异)对这些个体进行组合,产生新一代的候选解群,重复此过程,直到满足某种收敛指标为止。群体竞争种群婚配子群变异淘汰生物进化循环图构造初始种群计算个体(染色体)的适应值选择交叉变异遗传算法基本流程遗传算法概要:对于一个求函数最大值的优化问题(求最小值也类同),一般可描述为下述数学规划模型:maxf(X)(1-1)(1-2)R属于U(1-3)其中:X=[x1,x2,…,xn]T为决策变量,f(X)为目标函数,(1-2)、(1-3)为约束条件,U是基本空间,R是U的一个子集。满足约束条件的解X称为可行解;集合R表示由所有满足约束条件的解所组成的一个集合,叫做可行解集合。对于上述最优化问题,目标函数和约束条件种类繁多,有的是线性的,有的是非线性的;有的是连续的,有的是离散的;有的是单峰值的,有的是多峰值的。随着研究的深入,人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能,也不现实,因而求出其近似最优解或满意解是人们的主要着眼点之一。总的来说,求最优解或近似最优解的方法主要有三种:枚举法、启发式算法和搜索算法。随着问题种类的不同,以及问题规模的扩大,要寻求到一种能以有限的代价来解决上述最优化问题的通用方法仍是个难题。而遗传算法却为我们解决这类问题提供了一个有效的途径和通用框架,开创了一种新的全局优化搜索算法。遗传算法中:将n维决策向量X=[xl,x2,…,xn]T用n个记号Xi(i=1,2,…,n))所组成的符号串X来表示:X=xlx2…xn?X=[x1,x2,…,xn]T?把每一个xi看作一个遗传基因,这样,X就可看做是由n个遗传基因所组成的一个染色体。?这里的等位基因可以是一组整数。也可以是某一范围内的实数值,或者是纯粹的一个记号。最简单的等位基因是由0和1这两个整数组成的,相应的染色体就可表示为一个二进制符号串。?这种编码所形成的排列形式X是个体的基因型,与它对应的X值是个体的表现型。?对于每一个个体X,要按照一定的规则确定出其适应度,个体的适应度与其对应的个体表现型X的目标函数值相关联,X越接近于目标函数的最优点,其适应度越大;反之,适应度越小。?遗传算法中,决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。从而所有的染色体X就组成了问题的搜索空间。?生物的进化是以集团为主体的。与此对应,遗传算法的运算对象是由M个个体所组成的集合,称为群体(或称种群)。与生物一代一代的自然进化过程相类似,遗传算法的运算过程也是一个反复迭代过程:?第t代群体记做P(t),?经过一代遗传和进化后,得到t+1代群体,记做P(t+1),这个群体不断地经过遗