遗传算法中的选择

1. 遗传算法的基本原理

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

一、编码

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

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

二进制编码的缺点是汉明悬崖（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的正态分布的一个随机数来替换原有的基因值。

2. 遗传算法的选择概率

如果用轮盘赌选择法,则待选择的个体选择概率之和一定是1；
如果是基于排序的选择,则不需要计算每个个体的选择概率,也就谈不上概率之和是不是1的说法.
我不知道你看的是什么资料,不同的资料对排序选择法的说明不同.一般情况下,排序不是根据个体在群体中的位置来确定什么复制概率的,而是根据每个个体的适应度好坏来排序的.

3. 遗传算法，交叉概率，和变异概率，选择，通常在多少值，合适

这几个操作的概率是相互独立的，并不要求和为1。
选择操作中的概率，以轮赌法为例，概率只反映了个体被选择到的可能性，与个体的适应度大小有关，一般是适应度越大，对应轮赌法中的概率值越大。
交叉操作中的概率是用于判定两个个体是否进行交叉操作，一般都会大于0.9。
变异操作的概率是允许少数个体存在变异情况，以避免限入局部最优解，其值一般都在0.1以下。

4. 遗传算法中的锦标赛选择算法的思想是什么

我理解的是，在50个人中，随机选择两组人，每组10个人，对于每组的10个人按适应度进行排列，选择两组中适应度最好的两个个体作为母代进行两两交叉；
然后再从剩下来的48个人中，随机选择两组人，每组10个人，对于每组的10个人按适应度进行排列，选择两组中适应度最好的两个个体作为母代进行两两交叉；
依此类推，知道你选出的母代个数满足你的要求，这里母代个数肯定是少于50的。

5. 遗传算法中选择算子的问题

首先介绍sort函数用法：
[B,I]=sort(A,.....),I为返回的排序后元素在原数组中的行位置或列位置.B一般为排序后的数组。举例：
A = 3 4 2
1 5 3
4 7 1
[B,I]=sort(A)
B = 1 4 1
3 5 2
4 7 3
I = 2 1 3
1 2 1
3 3 2
[Oderfi,Indexfi]=sort(fi)，因此这句话中的Oderfi保存了从小到大排列的结果，而Indexfi保存了Oderfi中对应原始数组（fi）的的原始位置。
fi_Size=(Oderfi/fi_sum)*Size 这句话挺难理解的，不过我运行了这个程序后，还是被我发现了
其中Oderf为 适应值 由小到大排列，fi_sum为适应值的总和，Size为总的个数，而fi_sum/size就是平均值，因此。fi_size中所存放的数据是Oderf中数值除以其平均值后的结果。其中必有大于1的，小于1的。我们这里的淘汰规则是淘汰掉 种群中小于平均值的数据，下边的代码是对这个规则的具体化
fi_S只包含0和1，其中0是小于平均值的个体，1是大于平均值的个体。
for j=1:1:fi_S(i) %Select and Reproce
TempE(kk,:)=E(Indexfi(i),:);
kk=kk+1; %kk is used to reproce
end
E中保存的是初始种群，我们每一代种群中都会有80个个体（每一行是一个个体，列数决定了个体范围和精度），当fi_S中某个个体（记为个体A）不是0的时候，就执行了TempE(kk,:)=E(Indexfi(i),:);
这句代码，Indexfi保存了个体A在E中的行数（也就是fi的列数），我们认定这一行（这个个体A）具有优良基因，因此保存在TempE中，进化到下一代。

好久没看遗传算法了，上边的有些术语是我自己编的，看懂就好
还有，你的程序不完全，你能把这个完整的遗传算法代码给我吗，我感觉这个程序写的很简洁，非常好。我的邮箱[email protected]
另外你用这个程序算做什么？一般智能算法解决解决问题具有随机性，因此很难对误差做出评价，这也是应用受到阻碍的主要原因，如果在解决具体问题的时候，还是优先考虑定量算法的。
希望我的回答对你有所帮助。

6. 遗传算法的选择，交叉和变异概率的和是1吗

这几个操作的概率是相互独立的，并不要求和为1。
选择操作中的概率，以轮赌法为例，概率只反映了个体被选择到的可能性，与个体的适应度大小有关，一般是适应度越大，对应轮赌法中的概率值越大。

交叉操作中的概率是用于判定两个个体是否进行交叉操作，一般都会大于0.9。
变异操作的概率是允许少数个体存在变异情况，以避免限入局部最优解，其值一般都在0.1以下。

7. 遗传算法选中次数怎么算

遗传算法选中次数算法如下：

1、在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T。

2、随机产生U中的N个个体s1, s2, sN，组成初始种群S={s1, s2, sN}，置代数计数器t=1。

3、计算S中每个个体的适应度f() 。

4、若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。

5、按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1。

6、按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2。

7、按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3。

8、将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3。

相关基本概念：

1、个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。

2、种群就是模拟生物种群而由若干个体组成的群体, 它一般是整个搜索空间的一个很小的子集。

3、适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。

4、适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。

8. 遗传算法中选择算子是怎样根据选择次数得到结果的

选择操作是从初始群体(群体规模为N，即N个个体)或当代进化群体(群体规模为N)中选择N个个体，根据选择所采用的方法，劣质个体必然会被丢弃（未选择到），而为了保证群体规模不变，优质个体就必然会被选到多次。

9. 基本遗传算法介绍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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