人工智能导论笔记-第六章-遗传算法_修正的交叉方法

遗传算法：

    基本思想：在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解

    遗传算法的基本要素：

        编码

        生成初始种群

        适应度函数

        个体选择概率

        个体选择方法

        交叉操作

        变异

 

    编码：

        位串编码：

            将问题空间的参数用一维数组表示

            (1)二进制编码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间B={0,1}上，然后在位串空间上进行遗传操作

                优点：类似生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多

                缺点：相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率；要先给出求解精度

            (2)Gray编码：将二进制编码通过一个变换进行转换得到的编码

                

        实数编码：

            采用实数表达不必进行数制转换，可直接在解的表现型上进行遗传操作

            多参数映射编码的基本思想：把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体

            多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围

 

    适应度函数的尺度变换：

        欺骗问题：在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称欺骗问题

        过早收敛：缩小这些个体的适应度，以减低这些超级个体的竞争力

        停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力

        适应度函数的尺度变换或者定标：对适应度函数值域的某种映射变换

        

        (1)线性变换：

            f'=af+b；满足f'avg=favg，f'max=Cmult*favg

        (2)幂函数变换：

            f'=f^k

        (3)指数变换：

            f'=e^-af

 

    选择：

        (1)适应度比例法：

            各个个体被选择的概率和其适应度值成比例

            个体i被选择的概率：

                                

 

        (2)排序方法：

            线性排序：

                

 

            非线性排序：

                

 

    交叉：

        一般的交叉方法：

            (1)一点交叉：

                在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行交换，并生成两个新的个体

            (2)两点交叉：

                随机设置两交叉点，将两个交叉点之间的码串相互交换

        修正的交叉方法：

            (1)部分匹配交叉PMX：

                A=9 8 4 | 5 6 7 | 1 3 2

                B=8 7 1 | 2 3 9 | 5 4 6

                先交换匹配区中的内容

                A' = 9 8 4 | 2 3 9 | 1 3 2

                B' = 8 7 1 | 5 6 7 | 5 4 6

                将A'和B'中匹配区域外出现的重复项，按照匹配区内对应关系交换

                A'' = 7 8 4 | 2 3 9 | 1 6 5

                B'' = 8 9 1 | 5 6 7 | 2 4 3

            (2)顺序交叉OX：

                将匹配区外与另一基因匹配区内相同的值置为H

                A' = H 8 4 | 5 6 7 | 1 H H 

                B' = 8 H 1 | 2 3 9 | H 4 H

                将匹配区移动到起点位置，H移动到中间位置，其余值按顺序补在后面

                A'' = 5 6 7 | H H H | 1 8 4

                B'' = 2 3 9 | H H H | 4 8 1

                将A，B的匹配区交换，放入预留区H的位置，即得到两个子代

                A''' = 5 6 7 | 2 3 9 | 1 8 4

                B''' = 2 3 9 | 5 6 7 | 4 8 1

            (3)循环交叉CX：

                A=1 2 3 4 5 6 7 8 9

                B=5 4 6 9 2 3 7 8 1

                得到从A第一位开始的循环基因：1-5-2-4-9-1

                可用循环的基因A'，顺序与A相同

                 A=1 2 3 4 5 6 7 8 9

                A'=1 2 x 4 5  x x  x 9 

                剩余部分填入B对应的基因

                A'=1 2 6 4 5 3 7 8 9

 

    变异：

        (1)位点变异：

            群体中的个体码串，随机挑选一个或多个基因，并对这些基因的基因值以变异概率作变动

        (2)逆转变异：

            在个体码串中随机选择两点，然后将两点之间的基因值以逆向排序插入到原位置

        (3)插入变异：

            在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间

        (4)互换变异：

            随机选取染色体的两个基因进行简单互换

        (5)移动变异：

            随机选择一个基因，向左或向右移动一个随机位数

 

    遗传算法的一般步骤：

        

 

    遗传算法的特定：

        遗传算法是一种全局优化概率算法

            遗传算法对所求解的优化问题没有太多的数学要求，由于进化特性，搜索过程中不需要问题的内在性质，不论是线性还是非线性的，离散还是连续的都可以处理，可直接对结构对象进行操作

            利用随机技术指导对一个被编码的参数空间进行高效搜索

            采用群体搜索策略，易于并行化

            仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换