13第六专题第1次：智能决策-遗传算法

编写组决策理论与方法第一讲遗传算法专题六智能决策主要内容智能决策基本概念1遗传算法的基本原理2基于遗传算法的智能决策3一.智能决策基本概念

决策问题：单人决策—>群决策

单目标决策—>多目标决策静态决策—>动态决策决策环境：确定型—>不确定型决策过程：结构化—>非结构化背景简介传统决策支持系统(DecisionSupportSystem，DSS)智能决策支持系统(IntelligentDecisionSupportSystem，IDSS)引例

智能决策是在动态和多维信息收集的基础上，对复杂问题进行自主识别、判断、推理，并做出前瞻性、实时性的决策过程，同时系统要具有自优化、自适应的能力。

具体来说，就是收集大量的信息与知识，并将之存储在数据库和知识库中，基于此对问题进行分解和分析，建立问题求解模型，根据模型各部分的目标、功能、数据和要求进行求解，并将结果返回给决策者的过程。基本概念基本概念

智能决策支持系统将人工智能融入决策系统中，对数据库、模型库、方法库、知识库进行管理和调用，并使用智能方法进行决策。基本概念基本概念优化问题函数极值问题背包问题最短路径问题形状优化多孔材料的设计拓扑问题基本概念

优化算法，就是一种搜索过程或规则，是基于某种思想或者机制，通过一定的途径或规则得到满足用户要求的问题解决方案。经典优化算法线性规划、动态规划、整数规划、分支定界等（运筹学）智能优化算法人工神经网络、遗传算法、进化规划、模拟退火、禁忌搜索、蚁群搜索、粒子群算法及其混合优化策略等基本概念智能优化算法（IntelligentOptimizationAlgorithms）又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。基本概念特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。通过模拟或揭示某些自然现象或过程而得到的优化算法。算法构造：直观性+自然机理智能优化算法蚁群算法人工鱼群算法粒子群算法遗传算法模拟退火算法基本概念人工蜂群算法二.GA基本原理

简介遗传算法简称GA（GeneticAlgorithms）是由美国密切根大学（Michigan）的霍兰德（Holland）教授于1975年在他的专著《自然系统和人工系统的适应性》中详细阐述的，它是模拟自然界遗传机制和生物进化论而形成的一种并行随机搜索最优化方法。遗传算法是以达尔文的自然选择学说为基础发展起来的。GA基本原理个体（individual）：指模拟生物个体而对问题中的对象的一种称呼，一个个体也就是搜索空间中的一个点。种群（population）：指模拟生物种群而由若干个体组成的群体，它一般是整个搜索空间的一个很小的子集。染色体（chromosome）：指对个体进行编码后所得到的编码串，是遗传物质的主要载体。自然选择学（遗传学）的术语：GA基本原理自然选择学（遗传学）的术语：基因（gene）：指染色体中的每一个位，即编码串中的一个字符，是控制生物性状遗传物质功能和结构的基本单元，表示问题解中每一分量的特征。1111111

1110111GA基本原理基因型（genotype）：染色体的内部表现模式，是指与表现密切相关的基因组成。表现型（phenotype）：染色体的外部表现，是指生物个体表现出来的性状。编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。自然选择学（遗传学）的术语：1111111

编码解码适应度（fitness），指借鉴生物个体对环境的适应程度，而对问题中的个体对象所设计的表征其优劣的一种测度。GA基本原理适应度函数（fitnessfunction），指问题中的全体个体与其适应度之间的一个对应关系，用来对种群中各个个体进行环境适应性度量的函数。选择（selection）：又称为复制（reproduction），是用某种方法从群体中选取若干个体的操作。交叉（crossover）：又称重组或杂交，是指互换两个染色体某些位上的基因，实现两个染色体重新组合的操作。变异（mutation）又称突变，是指改变染色体某个（些）位上的基因，让遗传因子以一定概率变化的操作。自然选择学（遗传学）的术语：GA基本原理基本思想

遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数编码形成的基因码链群体中，按所选择的适应度函数并通过遗传中的选择、交叉及变异对个体进行筛选，使适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的终止条件。遗传算法的算法简单，可并行处理，并能到全局最优解。GA基本原理算法流程基本遗传算法可定义为一个7元组：

GA＝(M,F,s,c,m,pc,pm)M——群体大小；F——个体适应度评价函数；s——选择操作算子；c——交叉操作算子：m——变异操作算子；pc——交叉概率；pm——变异概率；GA基本原理求下列一元函数的最大值(求解结果精确到6位小数)：编码二进制，实数，格雷码型，…GA基本原理假设某一参数的取值范围是[umin,umax]，我们用长度为λ的二进制编码符号串来表示该参数，则它总共能够产生2λ种不同的编码，参数编码时的对应关系如下：00000000…00000000＝0umin

00000000…00000001＝1umin+

……11111111…11111111=2λ–1umax编码精度假设某一个体的编码是：

x：bλ-1bλ-2……b1b0

则对应的解码公式为：GA基本原理解码精度要求

1/1000000

解：采用多少位二进制数进行编码？2097152=221<3000001<222=4194304x需要22位二进制数表示，例如1000101110110101000111

解码：

编码过程实质上是将区间[-1,2]内对应的实数值转化为一个二进制串（b21b20…b0）。求下列一元函数的最大值(求解结果精确到6位小数)：表现型：0.637197编码解码染色体：1000101110110101000111基因求下列一元函数的最大值(求解结果精确到6位小数)：适应度函数所有个体的适应度必须为正数或零，不能是负数如果不能保证所有个体的适应度为非负，则需要进行尺度转化，f(x)->F(x)100010111011010100011110101011101101011001111100101110110101001000……初始种群初始种群的适应度值0.6371971.0122201.387198

……1）Generations（代数）——当产生的代数达到规定的代数值时，算法停止。2）Timelimit（时限）——当运行时间等于时限时，算法停止。

3）Fitnesslimit（适应度限）——当适应度函数的值到达某一限度时，算法停止。算法终止迭代的条件：算法终止迭代的条件：4）Stallgenerations（停滞代数）——在连续繁殖的时间序列中，若长时间不繁殖新代，亦即目标函数无改进，到达停滞代数规定的代数时，则算法停止。5）Stalltimelimit（停滞时限）——在秒数等于停滞时限的时间间隔期间，若目标函数无改进，则算法停止。选择算子（SelectionOperator）目的：从当前群体中选出优良个体，使其有机会作为父代。判断个体优良与否的标准是个体适应度值。适应度值越高，个体被选中的概率越大。常见的方法有比例选择法（比率法）、排序选择法（排列法）、联赛选择法（竞技法）三种类型轮盘赌：是比例选择中最常用的一种策略。基本思想：个体被选中的概率取决于该个体的相对适应度，根据相对适应度值产生一个轮盘，然后产生一个随机数，这个数落入轮盘的哪个区域就选择相应个体。特点：个体适应度越高，被选中概率越大。但是适应度小的个体也有可能备选中，以增加下一代群体多样性。可采用精英策略。实现：首先计算群体中所有个体适应度的总和，然后计算每个个体适应度所占比例，并以此作为选择相应个体的概率。GA基本原理交叉算子（CrossoverOperator）

模拟生物进化过程中的繁殖现象，通过来自双亲的两个染色体的交换组合，以产生新的优良个体。实现：选择群体中的两个个体，将这两个个体作为双亲，进行基因链码的交叉，从而产生两个新个体作为个体的后代。GA基本原理a.单点交叉b.两点交叉c.均匀交叉单点交叉算子对群体中的个体进行两两随机配对；每一对配对个体，随机设置某个基因座之后的位置为交叉点；对每一对配对个体，按照交叉概率在其交叉点处相互交换两个个体的部分染色体，产生出两个新的个体。GA基本原理单点交叉x1；1011011100

x1’：1011011111x2：0001110011x2’：0001110000N—种群中个体的数目Nc—种群中被交换个体的数目交叉概率变异算子（MutationOperator）目的：通过在染色体上某些基因位置产生突变，使得新产生个体与其他个体有所不同。实现：对群体中的某个个体（即基因链码）随机选择一位（即基因），将该基因改变（对于二进制，就是0改为1，1改为0）。GA基本原理基本位变异算子对个体的每一个基因座，按变异概率指定其为变异点；对每一个指定的变异点，对其基因值取反，从而产生出一个新的个体。A：1010101010A’：1010001010基本位变异pm—变异概率式中B——种群中变异的基因数目；N——种群拥有的个体数目

λ

——个体中基因串长度。为什么需要变异算子？若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。GA基本原理求下列一元函数的最大值(求解结果精确到6位小数)：对参数的编码进行操作，而非对参数本身，便于在优化计算过程中借鉴生物学中染色体和基因等概念；可同时使用多个搜索点的搜索信息，克服了传统优化方法往往从解空间的单个初始点开始最优解的迭代搜索过程的局限性，极大地提高了搜索效率；直接使用由目标函数值变换来的适应度函数值作为搜索信息，以确定进一步的搜索方向和搜索范围，而无需目标函数的导数值等其他一些辅助信息。GA基本原理优缺点分析GA基本原理优缺点分析使用概率搜索技术。复制、交叉、变异等运算都是以一种概率的方式来进行的，因而其搜索过程具有很好的灵活性。对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广。具有并行计算的特点，可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化。GA基本原理优缺点分析随机性是遗传算法的本质，因此很难对其进行预测。有时候可能经过几代就可以找到正确解，有时候可能要无休止的迭代下去。如果需要快速求解问题，不能依赖于随机性。遗传算法需要将求解的整个群体参与计算，即使是简单的基因型，都需要占用大量的内存和计算资源。对于复杂的问题，即使用足够高速的计算机进行交互式优化，通常也是不现实的。适用范围（1）函数优化。（2）组合优化。（3）任务分配（生产调度）（4）自动控制领域（5）机器人（6）图像处理GA基本原理三.基于遗传算法的智能决策

遗传算法则先罗列出可行的分配方案集，再对各个可行方案进行比较，最终选择最优方案。能够对各种火力分配方案进行比较后保留最优方案。火力分配一般由指挥实体完成。常见的决策方法是最近邻目标分配法：各个目标由离该目标最近的火力单元打击。最近邻目标分配法是按照一定的分配规则确定火力分配方案，仅仅制定了一种方案，没有进行多种方案之间的比较，该方法在目标数量较大时存在明显的局限性。案例：基于遗传算法的火力最优分配航空兵对地火力突击并实施对地攻击为作战任务，通过算法解决作战中可能出现的空中作战力量完全出动情况：空中作战力量通过一次突击力争彻底摧毁对方核心力量，使其不具备反制能力，即不按照传统战术保留预备力量，己方飞机全部出动，力求一次饱和攻击，摧毁目标价值最大，即解决哪种机型多少飞机攻击哪个目标（群）的效果最佳。约束条件假设某机场当前可用于执行攻击任务的飞机有2架H1型、2架H2型轰炸机，1架JH1型、2架JH2型歼轰机，1架QJ1型强击机，1架QJ2型强击机，现拟定所有可用飞机出动，对敌方7个目标进行打击。目标的价值系数（此处用威胁度评价）和一架飞机对目标的任务完成率是已知的，制定出兵