遗传算法的二进制编码

1. 基本遗传算法介绍

遗传算法是群智能优化计算中应用最为广泛、最为成功、最具代表性的智能优化方法。它是以达尔文的生物进化论和孟德尔的遗传变异理论为基础，模拟生物进化过程和机制，产生的一种群体导向随机搜索技术和方法。

遗传算法的基本思想：首先根据待求解优化问题的目标函数构造一个适应度函数。然后，按照一定的规则生成经过基因编码的初始群体，对群体进行评价、遗传运算（交叉和变异）、选择等操作。经过多次进化，获得适应度最高的一个或几个最优个体作为问题的最优解。

编码是对问题的可行解的遗传表示，是影响算法执行效率的关键因素的之一。遗传算法中，一个解 称为个体或染色体（chromosome），染色体由被称为基因（gene）的离散单元组成，每个基因控制颜色体的一个或多个特性，通常采用固定长度的0-1二进制编码，每个解对应一个唯一的二进制编码串编码空间中的二进制位串称为基因型（genotype）。而实际所表示问题的解空间的对应点称为表现型（phenotype）。

种群由个体构成，每个个体的染色体对应优化问题的一个初始解。

适应度函数是评价种群中个体对环境适应能力的唯一确定性指标，体现出“适者生存，优胜劣汰”这一自然选择原则。

遗传算法在每次迭代过程中，在父代种群中采用某种选择策略选择出指定数目的哥特体提进行遗传操作。最常用的选择策略是正比选择（proportional selection）策略。

在 交叉算子中，通常由两个被称为父代（parent）的染色体组合，形成新的染色体，称为子代（offspring）。父代是在种群中根据个体适应度进行选择，因此适应度较高的染色体的基因更有可能被遗传到下一代 。通过在迭代过程中不断地应用交叉算子，使优良个体的基因得以在种群中频繁出现，最终使得整个种群收敛到一个最优解。

在染色体交叉之后产生的子代个体，其基因位可能以很小的概率发生转变，这个过程称为变异。变异是为了增强种群的多样性，将搜索跳出局部最优解。

遗传算法的停止准则一般采用设定最大迭代次数或适应值函数评估次数，也可以是规定的搜索精度。

已Holland的基本GA为例介绍算法等具体实现，具体的执行过程描述如下：

Step 1： 初始化 。随机生成含有 个个体的初始种群 ，每个个体经过编码对应着待求解优化问题的一个初始解。

Step 2： 计算适应值 。个体 ，由指定的适应度函数评价其适应环境的能力。不同的问题，适应度函数的构造方式也不同。对函数优化问题，通常取目标函数作为适应度函数。

Step 3： 选择 。根据某种策略从当前种群中选择出 个个体作为重新繁殖的下一代群体。选择的依据通常是个体的适应度的高低，适应度高的个体相比适应度低的个体为下一代贡献一个或多个后代的概率更大。选择过程提现了达尔文“适者生存”原则。

Step 4： 遗传操作 。在选出的 个个体中，以事件给定的杂交概率 任意选择出两个个体进行 交叉运算 ，产生两个新的个体，重复此过程直到所有要求杂交的个体杂交完毕。根据预先设定的变异概率 在 个个体中选择出若干个体，按一定的策略对选出的个体进行 变异运算 。

Step 5： 检验算法等停止条件 。若满足，则停止算法的执行，将最优个体的染色体进行解码得到所需要的最优解，否则转到 Step 2 继续进行迭代过程。

2. 遗传算法理解

遗传算法是一种进化算法，进化是什么哪？就是种群逐渐适应生存环境，种群中个体不断得到改良的过程。

遗传算法是一种对生物遗传的模拟、在算法中，初始化一个种群，种群中的每个染色体个体都是一种解决方案，我们通过适应性fitness来衡量这个解决方案的好坏。并对它们进行选择、变异、交叉的操作，找到最优的解决方案。

总结一下遗传算法的基本的步骤：

1.初始化一个种群，并评估每条染色体所对应个体的适应度。

2.选择、交叉、变异，产生新的种群

3.再评估每个个体的适应值，如果适应值达到要求或者达到最大循环次数，否则重复2，不断产生新种群。

知道了GA的大致流程之后、来具体分析一下细节，怎么实现吧

我们知道遗传算法起源于生物遗传，因此在种群中每个个体就是一个染色体，那如何对染色体进行编码，让它表示我们的解决方案那（就是把现实要优化的参数用编码表示成一个染色体）。这里就遇到了一个编码、解码的问题，我们将需要优化的目标编码成染色体，然后再解码为我们可以用来计算fitness的解；

一般在进行参数优化时，一般有两种方式：实数编码、二进制编码

实数编码：基因直接用实数进行表示，这样的表示方法比较简单，不用特意解码了，但是在交叉和变异时，容易过早收敛，陷入局部最优。

二进制编码：将基因用二进制的形式表示，将参数的值转化为二进制形式，这样交叉、变异时更好操作，多样性好，但是占用的存储空间大，需要解码。

染色体就称为个体。对于一次实验，个体就是需要优化参数的一种解、许多这样的个体就构成了种群。

在面对群体中那么多个体时，如何判断个体的好坏呢，就是通过适应值函数了，将解带入适应值函数，适应值越大、解越好。

在遗传算法中，我们怎么使得里面的个体变得越来越优秀呢？

核心思想就是：选择优秀的、淘汰不好的，并且为了生成更好的解，我们要尝试交叉、变异，带来新的解。

选择就是从当前的种群中选择出比较好的个体、淘汰不好的个体

常见的选择方法有：轮盘赌选择、锦标赛选择、最佳保留选择等等

轮盘赌选择就是根据每个个体fitness和种群所有fitness之和比较，确定每个个体被选中的概率，然后进行n次选择，选择n个个体构成新种群，是一种放回抽样的方式。

锦标赛就是每次从种群中选择m个个体，选择最优的，放入新种群，重复选择，直到新种群中个体数目达到n。

最佳保留选择就是在轮盘赌的基础上，将fitness个体先加进新种群，因为轮盘赌是一种概率模型，可能存在最优个体没有进入新种群的情况。

在选择之后，就要考虑产生新的、更优秀的解，为种群带来新的血液。遗传算法的思路是交叉两个优秀的解，往往get好的解。

交叉通过在经过选择的种群中，随机选择一对父母，将它们的染色体进行交叉，生成新的个体，替代原来的解。

常用的交叉方法有：单点交叉、多点交叉等等。

交叉就像生物里面，染色体交换基因一样的～但是并不是种群中所有个体都进行交叉的，实现时可以，设置一个交叉率和交叉概率，随机选择种群中两个体、随机一个数，小于交叉率就进行交叉操作，并根据交叉概率判断交叉的程度，从而生成新个体，反之就保留这两个体。

变异也是一种产生新个体的方式，通过改变个体上基因，期望产生更好的解。比如在以二进制编码的个体上，将里面的0、1进行等位变化啥的，就是0变1、1变0这样。同样也要考虑变异率、变异产生的新解是不可控的，可能很好，也可能很坏，不能像交叉一样，确保一定的效果，所以往往变异率设置的比较小。

3. MATLAB中遗传算法编程中，二进制编码如何处理实数变量

假如你想要编码为x，设x的范围是【min,max】，二进制编码长度为10，那二进解码方式是：x*（max-min)/1023,这个不用开始编码，开始你可以用rand(n,10)产生n个样本的随机数，然后优化即可。
不是能把“数学模型中的目标函数和每一条约束函数分别编程Matlab里的M文件”，是你用遗传算法就必须要编进去，电脑怎么知道往哪个方向优化是好的，要不把你邮箱留下，我给你发个寻求最大值的遗传算法。

4. 遗传算法的基本原理

遗传算法的基本原理和方法

一、编码

编码：把一个问题的可行解从其解空间转换到遗传算法的搜索空间的转换方法。

解码（译码）：遗传算法解空间向问题空间的转换。

二进制编码的缺点是汉明悬崖（Hamming Cliff），就是在某些相邻整数的二进制代码之间有很大的汉明距离，使得遗传算法的交叉和突变都难以跨越。

格雷码（Gray Code）：在相邻整数之间汉明距离都为1。

（较好）有意义的积木块编码规则：所定编码应当易于生成与所求问题相关的短距和低阶的积木块；最小字符集编码规则，所定编码应采用最小字符集以使问题得到自然的表示或描述。

二进制编码比十进制编码搜索能力强，但不能保持群体稳定性。

动态参数编码（Dynamic Paremeter Coding）：为了得到很高的精度，让遗传算法从很粗糙的精度开始收敛，当遗传算法找到一个区域后，就将搜索现在在这个区域，重新编码，重新启动，重复这一过程，直到达到要求的精度为止。

编码方法：

1、 二进制编码方法

缺点：存在着连续函数离散化时的映射误差。不能直接反映出所求问题的本身结构特征，不便于开发针对问题的专门知识的遗传运算算子，很难满足积木块编码原则

2、 格雷码编码滚如：连续的两个整数所对应的编码之间仅仅只有一个码位是不同的，其余码位都相同。

3、 浮点数编码方法：个体的每个基因值用某一范围内的某个浮点数来表示，个体的编码长度等于其决策变量的位数。

4、 各参数级联编码：对含有多个变量的个体进行编码的方法。通常将各个参数分别以某种编码方法进行编码，然后再将他们的编码按照一定顺序连接在一起就组成了表示全部参数的个体编码。

5、 多参数交叉编码：将各个参数中起主要作用的码位集中在一起，这样它们就不易于被遗传算子破坏掉。

评估编码的三个规范：完备性、健全性、非冗余性。

二、选择

遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取那些个体遗传到下一代群体中的一种遗传运算，用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。

常用的选择算子：

1、 轮盘赌选择（Roulette Wheel Selection）：是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。

2、 随机竞争选择（Stochastic Tournament）：每次按轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高的被选中，如此反复，直到选满为止。

3、 最佳保留选择：首先按轮盘赌选择方法执行遗传算法的选择操作，然后将当前群体中适应度最高的大宏启个体结构完整地复制到下一代群体中。

4、 无回放随机选择（也叫期望值选择Excepted Value Selection）：根据每个个体在下一代群体中的生存期望来进行随机选择运算。方法如下

（1） 计算群体中每个个体在下一代群体中的生存期望数目N。

（2） 若某一个体被选中参与交叉运算，则它在下一代中的生存期望数目减去0.5，若某一个体未被选中参与交叉运算，则它绝配在下一代中的生存期望数目减去1.0。

（3） 随着选择过程的进行，若某一个体的生存期望数目小于0时，则该个体就不再有机会被选中。

5、 确定式选择：按照一种确定的方式来进行选择操作。具体操作过程如下：

（1） 计算群体中各个个体在下一代群体中的期望生存数目N。

（2） 用N的整数部分确定各个对应个体在下一代群体中的生存数目。

（3） 用N的小数部分对个体进行降序排列，顺序取前M个个体加入到下一代群体中。至此可完全确定出下一代群体中M个个体。

6、无回放余数随机选择：可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中，因而选择误差比较小。

7、均匀排序：对群体中的所有个体按期适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。

8、最佳保存策略：当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来代替掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。

9、随机联赛选择：每次选取几个个体中适应度最高的一个个体遗传到下一代群体中。

10、排挤选择：新生成的子代将代替或排挤相似的旧父代个体，提高群体的多样性。

三、交叉

遗传算法的交叉操作，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。

适用于二进制编码个体或浮点数编码个体的交叉算子：

1、单点交叉（One－pointCrossover）：指在个体编码串中只随机设置一个交叉点，然后再该点相互交换两个配对个体的部分染色体。

2、两点交叉与多点交叉：

（1） 两点交叉（Two－pointCrossover）：在个体编码串中随机设置了两个交叉点，然后再进行部分基因交换。

（2） 多点交叉（Multi－pointCrossover）

3、均匀交叉（也称一致交叉，UniformCrossover）：两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新个体。

4、算术交叉（ArithmeticCrossover）：由两个个体的线性组合而产生出两个新的个体。该操作对象一般是由浮点数编码表示的个体。

四、变异

遗传算法中的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换，从而形成以给新的个体。

以下变异算子适用于二进制编码和浮点数编码的个体：

1、基本位变异（SimpleMutation）：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。

2、均匀变异（UniformMutation）：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）

3、边界变异（BoundaryMutation）：随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。

4、非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。

5、高斯近似变异：进行变异操作时用符号均值为P的平均值，方差为P2的正态分布的一个随机数来替换原有的基因值。

5. 遗传算法二进制编码问题：二进制编码的位数是如何确定的

用这个公式试试，这个是解码用的，至于你说的位数，可以给你举个例子，比如[0,1],精度千分之1，就是相当于里面离散化出来1000+1个点，2的10次方是1024,2的9次方是512，这时候你就只要取10位就可以把这1001个点的变化全部包含到二进制里面了

6. 遗传算法的编码方法有几种

常用的编码介绍
1、二进制编码：
（1）定义：二进制编码方法是使用二值符号集{0,1}，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。
（2）举例：0≤x≤1023,精度为1,m表示二进制编码的长度。则有建议性说法：使
2m-1≤1000（跟精度有关）≤2m-1。取m=10
则X:0010101111就可以表示一个个体，它所对应的问题空间的值是x=175。
（3）优缺点
优点：符合最小字符集原则，便于用模式定理分析；
缺点：连续函数离散化时的映射误差。
2、格雷码编码
（1）定义：格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。它是二进制编码方法的一种变形。
十进制数0—15之间的二进制码和相应的格雷码分别编码如下。
二进制编码为：0000，0001，0010，001
1，0100。0101，0110，0111，
1000，1001，1010，1011，1100，1101，1110，1111；
格雷码编码为：0000，0001，0011，0010，0110，0111，0101，0100，
1100，1101，1111，1110，1010，1011，1001，1000。
（2）举例：对于区间[0。1023]中两个邻近的整数X1=175和X2=176，若用长度为10位的二进制编码，可表示为X11：0010101111和X12
0010110000，而使用同样长度的格雷码，它们可分别表示为X21：0010101111和X22：0010101000。
（3）优点：增强了遗传算法的局部搜索能力，便于连续函数的局部控件搜索。
3、浮点数(实数)编码
（1）定义：浮点数编码是指个体的每个基因值用某一范围内的一个浮点数来表示，而个体的编码长度等于其决策变量的个数。因为这种编码方法使用的决策变量的真实值，也称之为真值编码方法。
（2）举例：
（3）优点：实数编码是遗传算法中在解决连续参数优化问题时普遍使用的一种编码方式，具有较高的精度，在表示连续渐变问题方面具有优势。
4、排列编码
排列编码也叫序列编码，是针对一些特殊问题的特定编码方式。排序编码使问题简洁，易于理解。该编码方式将有限集合内的元素进行排列。若集合内包含m个元素，则存在m!种排列方法，当m不大时，m!也不会太大，穷举法就可以解决问题。当m比较大时，m!就会变得非常大，穷举法失效，遗传算法在解决这类问题上具有优势。如解决TSP问题时，用排列编码自然、合理。
5、其它编码方式
多参数级联编码等

7. 阆椾紶绠楁硶绠鍗曟槗镍傜殑渚嫔瓙

阆椾紶绠楁硶镄勪緥瀛愬备笅锛

姹傝В鍑芥暟 f锛坸锛 锛 x 锛 10锛妔in锛5锛妜锛 锛 7锛奵os锛4锛妜锛 鍦ㄥ尯闂达蓟0锛9锛界殑链澶у笺

阃氲繃涓婅堪鍏寮忥纴鎴戜滑灏卞彲浠ユ垚锷熷湴灏嗕簩杩涘埗镆撹壊浣扑覆瑙ｇ爜鎴愶蓟0锛9锛藉尯闂翠腑镄勫崄杩涘埗瀹炴暟瑙ｃ