搜索
优化决策技术的前沿优化决策技术的前沿•遗传算法•神经网络•模糊决策•混沌•协同学•耗散结构•……优化决策技术的前沿遗传算法•产生与发展•JohnHolland与其同事和学生在20世纪60年代末到70年代初期的开创性工作。•1975年他的专著《AdaptationinNaturalandArtificialSystem》的出版标志着GAs的诞生。。•“GeneticAlgorithms”一词首先出现在J.D.Bagleg的博士论文中，他研究了遗传算法在博弈论中的参数搜索，这是遗传算法的最早的应用。优化决策技术的前沿关键人物•J.H.Holland•J.D.Bagley（遗传算法的第一篇应用论文，自适应遗传算法）•K.A.DeJong（数值计算，参数设置，测试函数，在线指标，离线指标）•D.J.Goldberg（搜索、优化和机器学习中的遗传算法，1989，系统总结主要研究成果）•L.Davis（遗传算法手册，1991，大量应用实例）•J.R.Koza（1992，应用于计算机程序的优化设计与自动生成，提出遗传编程的概念）优化决策技术的前沿遗传算法•遗传算法的发展高潮始于20世纪80年代末，并一直延续至今。•人们对遗传算法的兴趣日益增长有两个背景：•其一是工程领域，特别是人工智能与控制领域，不断地涌现超大规模的、复杂的非线性系统，在这些系统的研究中存在着大量经典优化方法所不能有效求解的优化问题。•其二是遗传算法能独立的或与其他方法相结合的形式用于智能机器的学习系统的设计中，而不依赖于问题的种类优化决策技术的前沿六峰值驼背函数24422111122212()(42.11/3)(44)33,22fxxxxxxxxxx•Six-humpcamelbackfunction•该函数有6个局部极小点，•其中全局最小点•(-0.0898,0.7126)T•(0.0898,-0.7126)T•全局最小值：-1.031628遗传算法LINGO优化决策技术的前沿遗传算法•遗传算法（GeneticAlgorithms，简称GAs）的生物学背景：•Darwin的进化论和Mendel的遗传学说•适者生存，劣质淘汰•即优胜劣汰优化决策技术的前沿遗传算法的基本思想•GAs是将问题的求解表示成“染色体”，从而构成一群染色体。•将它们置于问题的“环境”中，根据适者生存的原则，从中选择出适应环境的染色体进行复制，即再生（Reproduction，也称Selection），通过交叉（Crossover）、变异（Mutation）两种基因操作产生出新的一代更适应环境的染色体群。•这样一代代的不断进化，最后收敛到一个最适合环境的个体上，求得问题的最优解。优化决策技术的前沿自然进化与GAs的对应关系基因串（染色体）问题的可行解基因型表现型适应度解码编码目标函数解码不同环境解的评价值优化决策技术的前沿GAs的流程图实际问题参数集确定表示问题解答的染色体（串）生成初始染色体串群计算每个个体的适应度是否收敛选择高适应值的串进行复制交叉变异输出最优解是否优化决策技术的前沿遗传算法的基本概念•个体和个体空间•适应度函数（F(t)）•遗传算子:选择、交叉和变异算子•控制参数:种群规模M、交叉概率Pc、变异概率Pm、进化代数T优化决策技术的前沿基本遗传算法的构成要素•（1）染色体编码方法•采用固定长度的二进制符号串来表示群体的个体，其等位基因是{0,1}组成。如•X＝100111001000101101•该个体的染色体长度是n＝18优化决策技术的前沿基本遗传算法的构成要素•（2）个体适应度评价•基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代的机会的多少。•必须预先确定好由目标函数值到个体适应度之间的转换规则。优化决策技术的前沿个体适应度评价minminmin()()0()0()0fXCiffXCFXiffXCmaxmaxmax()()()0()CfXiffXCFXiffXC优化决策技术的前沿基本遗传算法的构成要素•（3）遗传算子•基本遗传算法使用三种遗传算子：•选择算子（比例选择算子）•交叉运算（单点交叉算子）•变异算子（基本位变异或均匀变异算子）优化决策技术的前沿比例选择算子•也称赌盘选择，个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。金银铜铁10％20％30％40％优化决策技术的前沿单点交叉算子•（1）对群体中的个体进行两两随机配对•（2）对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点•（3）对每一对相互配对的个体，依设定的交叉概率与其交叉点相互交换两个个体的部分染色体，从而产生两个新的个体。•A:1011011100单点交叉A’:1011011111•B:0001110011B’:0001110000优化决策技术的前沿基本位变异算子•（1）对个体的每一个基因座，依变异概率指定其为变异点；•（2）对每一个指定的变异点，对其等位基因值作取反运算或用其他等位基因来代替，从而产生一个新的个体。•A:1011011100A’:1011111100基本位变异变异点优化决策技术的前沿基本遗传算法的构成要素•（4）运行参数•群体大小M，即种群中所含个体的数量；一般取20～100•终止进化代数T：•交叉概率Pc：一般取0.4～0.99•变异概率Pm：一般取0.0001～0.1优化决策技术的前沿遗传算法的数学基础•模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将得以指数级增长。•积木块假设：低阶、距短、高平均适应度的模式（积木块）在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，可最终生成全局最优解。•隐含并行性：遗传算法有效处理的模式个数为•收敛性分析与证明：基本遗传算法收敛于最优解的概率小于1；使用最佳保留策略的遗传算法能收敛于最优解的概率为1优化决策技术的前沿遗传算法的特点•（1）良好的并行性•（2）很强的通用性•（3）良好的全局优化性能和稳健性•（4）良好的可操作性与简单性优化决策技术的前沿函数优化的实例22121212max(,)..{0,1,2,,7}{0,1,2,,7}fxxxxstxx•（1）个体编码，把编码为一种符号串。•本例中x1，x2可分别用3位无符号二进制整数表示，把它们连接在一起组成的6位无符号二进制整数就形成个体的基因型，表示一个可行解。优化决策技术的前沿函数优化的实例•基因型X＝101110•表现型X＝[5,6]T•个体的表现型和基因型之间可通过编码和解码相互转换。优化决策技术的前沿函数优化的实例•（2）初始种群的产生•群体规模的大小取4•每个个体随机产生•（3）适应度计算•直接以目标函数值作为个体的适应度优化决策技术的前沿函数优化的实例•（4）选择运算•先计算出群体中个体的适应度之和•其次计算每个个体的相对适应度的大小•最后产生一个0－1之间的随机数，依据该随机数出现在上述哪一个概率区间来确定各个个体被选中的次数。优化决策技术的前沿函数优化的实例•（5）交叉计算•先对群体进行随机配对•其次随机设置交叉位置•最后在相互交换配对染色体之间的部分基因优化决策技术的前沿函数优化的实例•（6）变异操作•首先确定各个个体的基因变异位置；•然后依据某一概率将变异点的原有基因值取反。优化决策技术的前沿函数优化的实例个体编号初始群体P(0)x1x2fi(x1，x2)fi/∑fi101110135340.24210101153340.24301110034250.17411100171500.35∑fi＝143fmax＝50faver=35.75优化决策技术的前沿函数优化的实例选择次数选择结果配对情况交叉点位置交叉结果变异点变异结果10111011－21－2：201100140111011111001111101511111101010113－43－4：4101001211100121110011110116111010优化决策技术的前沿轮盘赌规则个体317%个体124%个体435%个体224%00.240.480.65优化决策技术的前沿函数优化的实例子代群体P(1)x1x2fi(x1，x2)fi/∑fi01110135340.1411111177980.4211100171500.2111101072530.23∑fi＝235fmax＝98faver=58.75优化决策技术的前沿考试方式•开卷考试•题目形式：•名词解释•简答•计算建模题