数学建模——遗传算法

数学建模——遗传算法

简单遗传算法（SGA）

由编解码、个体适应度评估和遗传运算三大模块构成，而遗传运算又包括染色体复制、交叉、变异甚至倒位等。

1. 编码
   设某一参数的取值范围为（L，U），使用长度为k的二进制编码表示该参数，则它有2^k种不同的编码。
   
2. 解码
   将不直观的二进制数据串还原成十进制。设某一个体的二进制编码为b_kb_k-1b_k-2……b₃b₂b₁，则对应的解码公式为：
   
3. 交配
   首先用随机数产生一个或多个交配点位置，然后两个个体在交配点位置互换部分基因码，形成两个子个体。例如，有两条染色体S₁=01001011，S₂=10010101，交换后4位基因，S^’₁=01000101,S’₂=10011011可以被看做是原染色体S₁和S₂的子代染色体。
4. 突变
   “突变运算”是使用基本位进行基因突变对于二进制编码即0变成1，而1变成0。
5. 倒位
   倒位是指一个染色体某区段正常排列顺序发生180°的颠倒。
   例如：
   
6. 个体适应度评估
   遗传算法依照与个体适应度成正比的几率决定当前种群中各个个体遗传到下一代群体中的机会。个体适应度大的个体更容易被遗传到下一代。通常，求目标函数最大值的问题可以直接把目标函数作为检测个体适应度大小的函数。
7. 复制
   若设种群中个体总数为N，个体i的适应度为f，则个体i被选取的几率
   
   当个体复制的几率决定后，再产生[0,1]区间的均匀随机数来决定哪些个体参加交配。若个体适应度高，则Pi大，可能被多次选中，它的遗传基因就会在种群中扩散；反之将逐渐淘汰。