遗传算法

第9章遗传算法~wjluo/ci/计算机科学与技术学院中国科学技术大学第Ⅲ部分进化计算遗传算法•遗传算法（GA）可能是最早提出的模拟遗传系统的算法模型。–首先由Fraser提出，然后由Bremermann和Reed等人再次提出。–最后由Holland对遗传算法做了大量工作并使之推广。–因此，Holland被认为是遗传算法的奠基人。•遗传算法模拟基因进化。–个体的性状（即“特征”）通过基因型表达。–遗传算法的主要驱动操作是：选择操作和重组操作。–选择操作模拟适者生存，重组（recombination）操作通过交叉算子（模拟繁殖）实现。本章内容•经典遗传算法•交叉•变异•控制参数•遗传算法的变体•前沿专题•应用•标准的遗传算法是具有“生成+测试”（generate-and-test）迭代过程的搜索算法。•遗传算法通过迭代进化，从一群初始解找到所期望的解。遗传算法的流程图解编码评估函数遗传操作初始群体选择交叉结束是否最优解？开始评估每个个体变异下一代种群经典遗传算法•经典遗传算法（canonicalGAs：CGA）由Holland提出。•CGA的基本实现方式：–使用比特串表示。–使用比例选择来选择进行重组的父代。–使用单点交叉来选择作为生成子代的主要方法。–使用均匀变异作为不太重要的配套算子。•在原始遗传算法中，变异并不认为是一个重要算子。后来，为了利用变异带来探索性能上的提高，改进遗传算法的搜索能力，一些遗传算法才使用了变异算子。•CGA和遗传算法的各种变种在表示方案、选择算子、交叉算子和变异算子上各不相同，一些算法还引入了集群灭绝、淘汰、种群孤岛等来自自然的概念。用CGA求解背包问题•0/1背包问题：已知n个物品和一个背包，每一个物品有一个价值vi和一个重量wi（i=1……n），而背包可以容纳总重量不超过C的物品。要求找出n个物体的一个子集，使所装入的物品的总价值最大，且物品的总重量不超过C，物品只能选择装还是不装。niiixv1max,..1Cxwtsniii}.,...,1{},1,0{nixi用CGA求解背包问题•编码：•适应度函数：110……01……1123ii+1nCxwCxwxwxvxfniiiniiiniiiniii11110)(为当前种群。，；CCxxfxfxf})(min{)()(0用CGA求解背包问题•交叉算子：单点交叉•变异算子：均匀变异，每一位以一定的概率变异。Before:（11110010）After:（11000110）本章内容•经典遗传算法•交叉•变异•控制参数•遗传算法的变体•前沿专题•应用交叉•根据元数（即使用的父个体数目），交叉（Crossover）算子可以分为三类。–无性（asexual）：子代由一个父个体产生。–有性（sexual）：由两个父个体产生一个或两个个体。–多亲重组（multi-recombination）：由多于两个的父个体产生一个或多个个体。•根据表示方案对交叉算子进行分类。–用于二进制串表示的二进制算子–用于浮点表示的浮点算子•用于交叉的父代个体使用选择策略来选择。–但是，并不是选中的父代个体一定会交叉，而是具有概率性的。交叉•每对（或组）父个体都会以概率pc产生子代。–pc称做交叉概率（thecrossoverrate）。–通常都会使用比较高的交叉概率。•选择父代个体时，需要考虑两点：①由于父个体的选择具有随机性，相同的个体可能被选择两次作为两个父个体，因而生成的子个体即为父个体的一个复制品。因此，在父个体的选择过程中，应该进行验证，以避免多余的操作。②相同的个体可能参与多次交叉操作。当使用基于适应度的比例选择时，这是一个问题。交叉•除了父个体选择和重组过程之外，交叉算子也要考虑替换策略。①如果生成一个子个体，可以用来替换最差的父个体。–这个替换规则可以（或者必须）基于子个体的适应度优于父个体。②玻尔兹曼（Boltzmann）选择可以用来确定子个体是否能替换父个体。③交叉算子也可以用子个体替换掉种群中的劣势个体。④生成两个子个体时，类似替换策略也可以使用。交叉—二进制表示•大多数基于二进制表示的交叉算子都作用于两个父个体。设x1(t)和x2(t)为两个父个体，交叉算法如下。//位串交叉的遗传算法1.令ỹ1(t)=x1(t)和ỹ2(t)=x2(t)；2.ifU(0,1)≤pcthen3.计算二元掩码m(t)；//掩码，确定哪些位应交换4.forj=1,…,nxdo5.ifmj=1then6.ỹ1j(t)=x2j(t)；ỹ2j(t)=x1j(t)；7.end8.end9.end交叉—二进制表示•不同的掩码计算方式，不同的交叉算子：–单点交叉（One-pointcrossover）–双点交叉（Two-pointcrossover）–均匀交叉（Uniformcrossover）交叉—二进制表示•单点交叉：在父代比特串中随机选择一个交叉点，交换交叉点之后的比特串以产生子代。//单点交叉的掩码计算1.选择交叉点～U(1,nx-1)；2.forj=1,…,nxdo3.mj(t)=0；4.end5.forj=+1,…,nxdo6.mj(t)=1；7.end交叉—二进制表示•双点交叉：随机选择两个位置，交换两个位置间的比特串。该算子可泛化为n点交叉。//两点交叉的掩码计算1.选择交叉点1～U(1,nx-1)；2.选择交叉点2～U(1,nx-1)；3.forj=1,…,nxdo4.mj(t)=0；5.end//假设1≤26.forj=1+1,…,2do7.mj(t)=1；8.end交叉—二进制表示•均匀交叉：nx维掩码由算法随机生成。其中，px是比特位的交换概率。//均匀交叉的掩码计算1.forj=1,…,nxdo2.mj(t)=0；3.end4.forj=1+1,…,2do5.ifU(0,1)≤pxthen6.mj(t)=1；7.end8.end交叉—二进制表示•Bremermann等人首先提出了针对二进制的多父个体交叉算子。–给定n个父个体向量，交叉生成一个个体的方式：的父个体的数目。是其中，其它情况，如果0)(1,...,120)(~tnnlnntljijxx•Bremermann等人还提出了n点交叉的多父个体交叉算子，其中n个父个体选择了n－1个唯一的交叉点，子个体都由每个父个体的片段组成。交叉—二进制表示•Jose提出了一种可以用于任意表示法的交叉爬山算子（acrossoverhill-climbingoperator）。–从两个父个体开始，不断产生子个体，直到达到最大的交叉次数或生成更好的子个体（至少有一个子个体更好）。–交叉爬山不断使用新生成的子个体作为下次生成过程的父个体。–如果在指定的时间内找不到更好的个体，则用随机个体替换较差的父个体。交叉—浮点表示•用于浮点表示的交叉算子–线性算子（thelinearoperator），最早的浮点交叉算子，Wright提出–带方向启发的交叉算子（adirectionalheuristiccrossoveroperator），Wright提出–算术交叉算子（thearithmeticcrossoveroperator），Michalewicz提出–混合交叉（BLX-，theblendcrossoveroperator）算子，Eshelman和Schaffer提出–几何交叉算子（thegeometricalcrossoveroperator），Michalewicz等人提出–模拟二进制交叉（SBX，thesimulatedbinarycrossover），Deb和Agrawal提出交叉—浮点表示•线性算子：通过父个体x1(t)和x2(t)产生三个备选子个体x1(t)＋x2(t)，1.5x1(t)－0.5x2(t)，－0.5x1(t)＋1.5x2(t)，其中最好的两个解被选为子个体。•带方向启发的交叉算子：差。不比其中，父个体)()()()()()1,0()(~12212tttttUtjjjijxxxxxx交叉—浮点表示•算术交叉算子：多父个体的重组策略，它根据权重从两个父个体获得信息。–子个体生成公式为：。，其中1)()(~11nllnlljlijtxtx简单平均。，则子个体为父个体的若。，其中（的一个特例：时，可得算术交叉算子当5.0]1,0[)()()1)(~221txtxtxnjjij交叉—浮点表示•混合交叉（BLX-）：.)1,0()21()()()1)(~21Utxtxtxjjjjjij其中（•BLX-算子随机生成的元素，其范围为：)()()()()()()()(12112121txtxtxtxtxtxtxtxjjjjjjjj，，假设•Eshelman与Schaffer的研究认为，=05时，算子的效果最好。•在混合交叉算子中，子个体的位置依赖于父个体间的距离。如果距离较大，则子个体与父个体的距离也会比较大。交叉—浮点表示•几何交叉算子：两个父个体几何交叉生成子个体。5.021)()()(~txtxtxjjij•几何交叉算子可以泛化为多亲重组算子：。为父个体数目，且其中，1)(~12121nlljnjjijnxxxtx交叉—浮点表示•模拟二进制交叉：模拟二进制表示的单点交叉。。建议和为分布指数。，且其它情况如果）（其中，（（1AgrawalDeb0)1,0(U)1(215.02)()1()()15.0)(~)()1()()15.0)(~1111212211jjjjjjjjjjjjjjjuuuutxtxtxtxtxtx交叉—浮点表示•用于浮点表示的交叉算子（多亲算子）–单模分布算子（UNDX，unimodaldistributedoperator），Ono与Kobayashi提出–单纯形交叉算子（SPX，thesimplexcrossoveroperator）–基因扫描技术–对角交叉算子•多亲交叉算子的主要目标时加强探索能力。通过综合多个父个体的信息，子代和父代之间的相似性与双亲算子相比平均起来更小，获得了更多的破坏。交叉—浮点表示•单模分布算子：使用3个父个体生成子个体。–子个体通过椭圆概率分布生成，其中椭圆的一个轴是两个父个体的连线。与之正交的轴则由第三个父个体与另一轴的垂直距离决定。正交的基向量。是与连线的距离，和与个体为个体，，，，其中ddeexxxxxdxxxedxx)(35.0212/)()()(),0(),0()()(~213212121112221tnttNNttlxnlljix交叉—浮点表示•单模分布算子（父个体数目为n）：•UNDX算子可以一般化为使用多个父个体（要求3nns）。从种群中选择n－1个父个体，其中心（即均值）11)(11)(nlljjtntxx–根据这一均值，可得n－1个距离向量1,...,1)()()(nltttll，xxd–令el为方向余弦，则的长度。表示，其中)()()(/)()(tttttllllldddde交叉—浮点表示•单模分布算子（父个体数目为n）：–……。，其中235.021)(),0()(),0()()(~21221121nnntNtNttsnnllnllljixeedxx–随机选择的一个父个体，设下标为n，令。，令正交于全体)()()()()(tttttnlnxxdxx则子个体按下式生成，的正交子空间的正交基是令－1211,,,,,,nnnneeeeees交叉—浮点表示•单模分布算子（父个体数目为n）：–可以生成取样于