信息论讲义_第十一讲

《信息论讲义_第十一讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息理论基础信息理论基础（第十一讲）（第十一讲）授课教师：于泽电子信息工程学院201教研室第四章离散信道•内容提要4.1信道模型及其分类4.2离散无记忆信道4.3离散无记忆扩展信道4.4信道的组合4.5信道容量4.6信源与信道匹配24.5信道容量信道容量迭代算法¾目的：对于任意离散信道求出其信道容量¾条件：任意给定的精度有限步数I()()X;Y=HX−H(X

2、Y)=−∑p(x)lnp(x)+∑∑p(x)p(y

3、x)lnp(x

4、y)iiijiijiijI[p(x),p(x

5、y)]iij34.5信道容量（续）44.5信道容量（续）54.5信道容量（续）64.5信道容量（续）74.5信道容量（续）

6、I()()X;Y=HX−H(X

7、Y)=−∑p(x)lnp(x)+∑∑p(x)p(y

8、x)lnp(x

9、y)iiijiijiij84.5信道容量（续）94.5信道容量（续）104.5信道容量（续）遗传算法¾遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。¾它最早由美国密西根大学的H.Holland教授提出，起源于60年代对自然和人工自适应系统的研究¾1967年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用“遗传算法（GeneticAlgorithm）”一词。¾70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。

10、¾在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。114.5信道容量（续）对于一个求函数最大值的优化问题（求最小值也类同），一般可描述为下述数学规划模型：maxf(X)s.t.X∈RR⊆U其中：X＝[x,x,…,x]T为决策变量，f(X)为目标函数，12n式(2)、(3)为约束条件，U是基本空间，R是U的一个子集。满足约束条件的解X称为可行解；集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。124.5信道容量（续）对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值

11、的，有的是多峰值的。随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价来解决上述最优化问题的通用方法仍是个难题。而遗传算法却为我们解决这类问题提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。134.5信道容量（续）遗传算法中：将n维决策向量X＝[x,x,…,x]T用n个记号X(i=1,2,…,n)所12ni组成的符号串X来去示：X＝xx…x⇒X＝[x，x，…,x]Tl2n12n•把每一个x看作一个遗传基因，这样，X就可

12、看做是由n个遗i传基因所组成的一个染色体。•对于每一个个体X，要按照一定的规则确定出其适应度，个体的适应度与目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。•遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。144.5信道容量（续）生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体（或称种群）。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最

13、终在群体中将会得到一个优良的个体X，达到或接近于问题的最优解X*。154.5信道容量（续）遗传算法的生物学基础：生物的遗传和进化。1.复制父代的遗传物质DNA被复制到子代。即细胞在分裂时，遗传物质DNA通过复制(Reproduction)而转移到新生的细胞中，新细胞就继承了旧细胞的基因。2.交叉两个同源染色体之间通过交叉(Crossover)而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交义组合而形成两个新的染色体。3.变异在进行细胞复制时，以很小的概率产生某些复制差错，从而使DNA发生某种变异(Mutation)，产生出新的染色体。164.5信道容量（续）4.进化物竞

14、天择适者生存（1）生物的进化是以集团的形式共同进行的，这样的一个团体称为群体(Population)，或称为种群。（2）组成群体的单个生物称为个体(Individual)，（3）每一个个体对其生存环境都有不同的适应能力，这种适应能力称为个体的适应度(Fitness)。174.5信道容量（续）遗传算法是一种概率搜索算法。1.避免陷入局大值或局小值2.可同时进行多变数的寻优3.自由度极高184.5信道容量（续）遗