长沙网络营销推广,移动端排名优化软件,案例学——网页设计与网站建设,wordpress配置文件下载目录
一、大体实现过程
二、开始我们的进化(具体实现细节)
2.1 先从编码说起
2.1.1 二进制编码法
2.1.#xff12; 浮点编码法
2.1.3 符号编码法
2.2 为我们的袋鼠染色体编码
2.3 评价个体的适应度
2.4 射杀一些袋鼠
2.5 遗传--染色体交叉(crossover)
2.6 变异--基…目录
一、大体实现过程
二、开始我们的进化(具体实现细节)
2.1 先从编码说起
2.1.1 二进制编码法
2.1. 浮点编码法
2.1.3 符号编码法
2.2 为我们的袋鼠染色体编码
2.3 评价个体的适应度
2.4 射杀一些袋鼠
2.5 遗传--染色体交叉(crossover)
2.6 变异--基因突变(Mutation)
三、代码实现环节
3.1 基础概念
3.2 代码尝试
3.2.1 遗传算法算子
3.2.2 变异算子mutation
3.3 遗传算法策略
3.4 小刷例题
3.4.1 例题1牛刀小试
3.4.2 例题2糖果 一、大体实现过程
遗传算法中每一条染色体对应着遗传算法的一个解决方案一般我们用适应性函数fitness function来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。遗传算法的实现过程实际上就像自然界的进化过程那样。
我们用袋鼠跳中的步骤一一对应解释
1) 首先寻找一种对问题潜在解进行“数字化”编码的方案。建立表现型和基因型的映射关系
2) 随机初始化一个种群那么第一批袋鼠就被随意地分散在山脉上种群里面的个体就是这些数字化的编码。
3) 接下来通过适当的解码过程之后得到袋鼠的位置坐标。
4) 用适应性函数对每一个基因个体作一次适应度评估袋鼠爬得越高当然就越好所以适应度相应越高。
5) 用选择函数按照某种规定择优选择每隔一段时间射杀一些所在海拔较低的袋鼠以保证袋鼠总体数目持平。
6) 让个体基因变异让袋鼠随机地跳一跳。
7) 然后产生子代希望存活下来的袋鼠是多产的并在那里生儿育女。
遗传算法并不保证你能获得问题的最优解但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。你不必去指导袋鼠向那边跳跳多远。而只要简单的“否定”一些表现不好的个体就行了。把那些总是爱走下坡路的袋鼠射杀这就是遗传算法的精粹
由此我们可以得出遗传算法的一般步骤
1) 随机产生种群。
2) 根据策略判断个体的适应度是否符合优化准则若符合输出最佳个体及其最优解结束。否则进行下一步。
3) 依据适应度选择父母适应度高的个体被选中的概率高适应度低的个体被淘汰。
4) 用父母的染色体按照一定的方法进行交叉生成子代。
5) 对子代染色体进行变异。
由交叉和变异产生新一代种群返回步骤2直到最优解产生。 二、开始我们的进化(具体实现细节)
2.1 先从编码说起
编码是应用遗传算法时要解决的首要问题也是设计遗传算法时的一个关键步骤。编码方法影响到交叉算子、变异算子等遗传算子的运算方法很大程度上决定了遗传进化的效率。
迄今为止人们已经提出了许多种不同的编码方法。总的来说这些编码方法可以分为三大类二进制编码法、浮点编码法、符号编码法。下面分别进行介绍。
2.1.1 二进制编码法
就像人类的基因有AGCT 4种碱基序列一样。不过在这里我们只用了0和1两种碱基,然后将它们串成一条链形成染色体。一个位能表示出2种状态的信息量因此足够长的二进制染色体便能表示所有的特征。这便是二进制编码。如下
1110001010111
它由二进制符号0和1所组成的二值符号集。它有以下一些优点
1) 编码、解码操作简单易行
2) 交叉、变异等遗传操作便于实现
3) 符合最小字符集编码原则
4) 利用模式定理对算法进行理论分析。
二进制编码的缺点是对于一些连续函数的优化问题由于其随机性使得其局部搜索能力较差如对于一些高精度的问题当解迫近于最优解后由于其变异后表现型变化很大不连续所以会远离最优解达不到稳定。
2.1. 浮点编码法
二进制编码虽然简单直观一目了然。但是存在着连续函数离散化时的映射误差。个体长度较短时可能达不到精度要求而个体编码长度较长时虽然能提高精度但增加了解码的难度使遗传算法的搜索空间急剧扩大。
所谓浮点法是指个体的每个基因值用某一范围内的一个浮点数来表示。在浮点数编码方法中必须保证基因值在给定的区间限制范围内遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。如下所示
1.2-3.2-5.3-7.2-1.4-9.7
浮点数编码方法有下面几个优点
1) 适用于在遗传算法中表示范围较大的数。
2) 适用于精度要求较高的遗传算法。
3) 便于较大空间的遗传搜索。
4) 改善了遗传算法的计算复杂性提高了运算效率。
5) 便于遗传算法与经典优化方法的混合使用。
6) 便于设计针对问题的专门知识的知识型遗传算子。
7) 便于处理复杂的决策变量约束条件。
2.1.3 符号编码法
符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如A,B,C…。
符号编码的主要优点是
1) 符合有意义积术块编码原则。
2) 便于在遗传算法中利用所求解问题的专门知识。
3) 便于遗传算法与相关近似算法之间的混合使用。
2.2 为我们的袋鼠染色体编码
在上面介绍了一系列编码方式以后那么如何利用上面的编码来为我们的袋鼠染色体编码呢首先我们要明确一点编码无非就是建立从基因型到表现型的映射关系。这里的表现型可以理解为个体特征比如身高、体重、毛色等等。那么在此问题下我们关心的个体特征就是袋鼠的位置坐标因为我们要把海拔低的袋鼠给杀掉。无论袋鼠长什么样爱吃什么。我们关心的始终是袋鼠在哪里并且只要知道了袋鼠的位置坐标位置坐标就是相应的染色体编码可以通过解码得出我们就可以
1) 在喜马拉雅山脉的地图上找到相应的位置坐标算出海拔高度。相当于通过自变量求得适应函数的值然后判读该不该射杀该袋鼠
2) 可以知道染色体交叉和变异后袋鼠新的位置坐标。
回到一元函数最大值的问题。在上面我们把极大值比喻为山峰那么袋鼠的位置坐标可以比喻为区间[-1, 2]的某一个x坐标有了x坐标再通过函数表达式可以算出函数值 得到了袋鼠染色体编码解码得到位置坐标在喜马拉雅山脉地图查询位置坐标算出海拔高度。这个x坐标是一个实数现在说白了就是怎么对这个x坐标进行编码。下面我们以二进制编码为例讲解不过这种情况下以二进制编码比较复杂就是了。如果以浮点数编码其实就很简洁了就一浮点数而已。
我们说过一定长度的二进制编码序列只能表示一定精度的浮点数。在这里假如我们要求解精确到六位小数由于区间长度为2 - (-1) 3 为了保证精度要求至少把区间[-1,2]分为3 × 10^6等份。又因为
2^21 2097152 3*10^6 2^22 4194304
所以编码的二进制串至少需要22位。
把一个二进制串 (b0,b1,....bn) 转化为区间里面对应的实数值可以通过下面两个步骤
1) 将一个二进制串代表的二进制数转化为10进制数 2) 对应区间内的实数 例如一个二进制串(1000101110110101000111)通过上面换算以后表示实数值0.637197。
好了上面的编码方式只是举个例子让大家更好理解而已编码的方式千奇百怪层出不穷每个问题可能采用的编码方式都不一样。在这一点上我们要注意。
2.3 评价个体的适应度
前面说了适应度函数主要是通过个体特征从而判断个体的适应度。在本例的袋鼠跳中我们只关心袋鼠的海拔高度以此来判断是否该射杀该袋鼠。这样一来该函数就非常简单了。只要输入袋鼠的位置坐标在通过相应查找运算返回袋鼠当前位置的海拔高度就行。
适应度函数也称评价函数是根据目标函数确定的用于区分群体中个体好坏的标准。适应度函数总是非负的而目标函数可能有正有负故需要在目标函数与适应度函数之间进行变换。
评价个体适应度的一般过程为 对个体编码串进行解码处理后可得到个体的表现型。 由个体的表现型可计算出对应个体的目标函数值。 根据最优化问题的类型由目标函数值按一定的转换规则求出个体的适应度。
2.4 射杀一些袋鼠
遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取那些个体以便遗传到下一代群体。选择操作用来确定重组或交叉个体以及被选个体将产生多少个子代个体。前面说了我们希望海拔高的袋鼠存活下来并尽可能繁衍更多的后代。但我们都知道在自然界中适应度高的袋鼠越能繁衍后代但这也是从概率上说的而已。毕竟有些适应度低的袋鼠也可能逃过我们的眼睛。
那么怎么建立这种概率关系呢
下面介绍几种常用的选择算子 轮盘赌选择Roulette Wheel Selection是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。 随机竞争选择Stochastic Tournament每次按轮盘赌选择一对个体然后让这两个个体进行竞争适应度高的被选中如此反复直到选满为止。 最佳保留选择首先按轮盘赌选择方法执行遗传算法的选择操作然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。 无回放随机选择也叫期望值选择Excepted Value Selection根据每个个体在下一代群体中的生存期望来进行随机选择运算。方法如下: 计算群体中每个个体在下一代群体中的生存期望数目N。 若某一个体被选中参与交叉运算则它在下一代中的生存期望数目减去 0.5若某一个体未被选中参与交叉运算则它在下一代中的生存期望数目减去1.0。 随着选择过程的进行若某一个体的生存期望数目小于0时则该个体就不再有机会被选中。 确定式选择按照一种确定的方式来进行选择操作。具体操作过程如下 计算群体中各个个体在下一代群体中的期望生存数目N。 用N的整数部分确定各个对应个体在下一代群体中的生存数目。 用N的小数部分对个体进行降序排列顺序取前M个个体加入到下一代群体中。至此可完全确定出下一代群体中个个体。 无回放余数随机选择可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中因而选择误差比较小。 均匀排序对群体中的所有个体按其适应度大小进行排序基于这个排序来分配各个个体被选中的概率。 最佳保存策略当前群体中适应度最高的个体不参与交叉运算和变异运算而是用它来代替掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。 随机联赛选择每次选取几个个体中适应度最高的一个个体遗传到下一代群体中。 排挤选择新生成的子代将代替或排挤相似的旧父代个体提高群体的多样性。
下面以轮盘赌选择为例给大家讲解一下
假如有条染色体他们的适应度分别为、、、、。
那么总的适应度为F 5 8 3 7 2 25。
那么各个个体的被选中的概率为
α1 ( 5 / 25 ) * 100% 20%
α2 ( 8 / 25 ) * 100% 32%
α3 ( 3 / 25 ) * 100% 12%
α4 ( 7 / 25 ) * 100% 28%
α5 ( 2 / 25 ) * 100% 8%
所以转盘如下 当指针在这个转盘上转动停止下来时指向的个体就是天选之人啦。可以看出适应性越高的个体被选中的概率就越大。
2.5 遗传--染色体交叉(crossover)
遗传算法的交叉操作是指对两个相互配对的染色体按某种方式相互交换其部分基因从而形成两个新的个体。
适用于二进制编码个体或浮点数编码个体的交叉算子 单点交叉One-point Crossover指在个体编码串中只随机设置一个交叉点然后再该点相互交换两个配对个体的部分染色体。 两点交叉与多点交叉 两点交叉Two-point Crossover在个体编码串中随机设置了两个交叉点然后再进行部分基因交换。 多点交叉Multi-point Crossover 均匀交叉也称一致交叉Uniform Crossover两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换从而形成两个新个体。 算术交叉Arithmetic Crossover由两个个体的线性组合而产生出两个新的个体。该操作对象一般是由浮点数编码表示的个体。 咳咳根据国际惯例。还是抓一个最简单的二进制单点交叉为例来给大家讲解讲解。
二进制编码的染色体交叉过程非常类似高中生物中所讲的同源染色体的联会过程――随机把其中几个位于同一位置的编码进行交换产生新的个体。 对应的二进制交叉 2.6 变异--基因突变(Mutation)
遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换从而形成新的个体。
例如下面这串二进制编码
101101001011001
经过基因突变后可能变成以下这串新的编码
001101011011001
以下变异算子适用于二进制编码和浮点数编码的个体 基本位变异Simple Mutation对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。 均匀变异Uniform Mutation分别用符合某一范围内均匀分布的随机数以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。特别适用于在算法的初级运行阶段 边界变异Boundary Mutation随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。 非均匀变异对原有的基因值做一随机扰动以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后相当于整个解向量在解空间中作了一次轻微的变动。 高斯近似变异进行变异操作时用符号均值为的平均值方差为P**2的正态分布的一个随机数来替换原有的基因值。 三、代码实现环节
3.1 基础概念
拿古代人类来举例子
个体Individual每个生物。即每个古人类个体。种群population一个系统里所有个体的总称。比如一个部落。种群个体数POPULATION一个系统里个体的数量。比如一个部落里的人数。染色体chromosom每个个体均携带用来承载基因。比如一条人类染色体。基因Gene用来控制生物的性状表现。适应度fitness对某个生物是否适应环境的定量评分。比如对某个古人类是否强壮进行 [1,100] 的评分。迭代次数TIMES该生物种群繁衍的次数。比如古人类繁殖了 100 万年。
一定要记住这些英文名字后面会经常用到
在算法中我们对每个个体计算其染色体的适应度fitness来决定它是否优秀。
3.2 代码尝试
尝试构建一个名字叫做 Individual 的结构体里面存储一个个体的信息。
struct Individual{string chromosome; //染色体int fitness; //个体的适应度int calc_fitness(); //计算适应度 Individual(string chromosome); //初始化 Individual mate(); //交叉算子CrossOver Individual mutation(); //变异算子Mutation
};Individual(string chromosome){this-chromosomechromosome;this-fitnesscalc_fitness();
}
3.2.1 遗传算法算子
交叉算子CrossOver
也有将该算子称为 mate 的。我更倾向于第二种叫法因为第二种字数更少。
交叉算子就是模拟父母双方交配过程。想一想人类交配时每个基因会随机的来自父亲或者母亲。我们可以模拟这个过程。假设我们的染色体用 string 存储可以实现下面的交配代码
// par 代表母亲chromosome 代表父亲即本身的染色体par.chromosome 则代表母亲染色体。
Individual Individual::mate(Individual par) { // 交叉string child ; // 子代染色体int len chromosome.size();for (int i 0; i len; i ) {double p random(0, 100) / 100; // 计算来自父母的概率if (p 0.5) child chromosome[i]; // 一半概率来自父亲else child par.chromosome[i]; // 另一半来自母亲}return Individual(child);
}
当然我们也可以思考一些其他的交叉思路比如随机抽取某些段进行交换。如下图所示 这种算法通常在二进制条件下更加实用。
3.2.2 变异算子mutation
即低概率地随机地改变某个基因。这样可以有效避免程序陷入局部最优或者过慢收敛。例如 一般来说我们可以设计一个变异概率。变异率大概在 0.01∼0.050.01∼0.05 之间最优。变异率太高会导致收敛过慢变异率太低则会导致陷入局部最优。
3.3 遗传算法策略
精英保留策略
还是拿古人类举例。假设我们是上帝我们想要古人类实现长久发展最好的办法就是尽可能的将那些头脑敏捷肢体强壮的个体保留下来淘汰那些老弱病残的个体。
在程序中我们将个体按照适应度排序把适应度最好前 k% 的保留下来剩下的随机交配。通常k 可以设成 1∼20。设置太高则会局部最优太低则会收敛过慢。
概率保留策略
学名好像是 Stoffa改进方法这不重要。总之就是为了避免父母生出傻孩子浪费时间把傻孩子适应度低的后代直接抛弃。
假设我们要求收敛到最低适应度后代适应度为 y父代适应度为 x有 Δy−x。若 Δ0证明子代比父代更好我们一定接受。对于 Δ0证明子代不如父代好我们以一定概率接受。之所以要有一定概率接受是为了避免出现局部最优解。
这个概率我们怎么来算呢有一种方法给出了概率的计算函数 其中 t 是我们设定的参数值一般随着迭代次数增大而减小。
如果 rand(0,1)那么我们就接受它。
为什么是 −Δ 呢因为 Δ0我们要保证 e^x 小于 1 才能保证部分接受。因此要用 −Δ。
为什么要用 e^x 呢我不知道大概是因为它的积分等于原函数吧。。。
下面放一张遗传算法求最短哈密尔顿路径的收敛图像。其中绿色实线是加了概率函数的蓝色虚线则没有加。可以看出绿色实现收敛的比较快侧面证明了 Stoffa改进方法 的正确性。 思考题
如果我们要求最大适应值那么概率的计算函数应当怎么计算呢
答案Delta0。
3.4 小刷例题
3.4.1 例题1牛刀小试
给定一个目标字符串target目标是从相同长度的随机字符串开始生成目标字符串。
比如从 114514QAQ 生成 123456789。
这里先讲一下适应度函数的构造方法比较当前染色体与目标字符串之间不同的字符个数即为适应度。显然适应度越低越好。
样例代码如下
#includeiostream
#includealgorithm
#includecstring
#includecstdio
#includectime
#includevector
#define POPULATION 1000
using namespace std;typedef long long LL;
//using LLlong long;
typedef pairint,int PII;
//using PIIpairint,int;
typedef pairLL,LL PLL;
//using PLLpairLL,LL;const string targetIve got it!;
const string GeneBaseabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP\QRSTUVWXYZ 1234567890, .-;:_!\#%/()?${[]}; // 基因库int random(int l,int r){ //随机一个位于[l,r]之间的整数 return rand()%(r-l1)l;
}char mutate(){int lenGeneBase.size();return GeneBase[random(0,len-1)];
} string create(){ //产生新的染色体 string chromosome;int lentarget.size();for(int i0;ilen;i){chromosomemutate();}return chromosome;
}struct Individual{string chromosome; //染色体int fitness; //个体的适应度int calc_fitness(); //计算适应度 Individual(string chromosome); //初始化 Individual mate(Individual parent); //交配 void mutation(); //随机变异 bool operator (const Individual tmp) const {return fitnesstmp.fitness;}
};Individual::Individual(string chromosome){this-chromosomechromosome;this-fitnesscalc_fitness();
}// par 代表母亲chromosome 代表父亲即本身的染色体par.chromosome 则代表母亲染色体。
Individual Individual::mate(Individual par) { // 交叉string child ; // 子代染色体/后代 int len chromosome.size();for (int i 0; i len; i ) {double p random(0, 100) / 100; // 计算来自父母的概率if (p 0.5) child chromosome[i]; // 一半概率来自父亲else child par.chromosome[i]; // 另一半来自母亲}return Individual(child);
}int Individual::calc_fitness(){ //计算适应度 int lentarget.size(); int now_fitness0;for(int i0;ilen;i){now_fitness(chromosome[i]!target[i]);}return now_fitness;
}void Individual::mutation(){int Prandom(1,2),LENtarget.size();for(int i1;iP;i){int posrandom(0,LEN-1);chromosome[pos]mutate();}this-fitnesscalc_fitness();
} int main(){srand(time(0));int cnt 0; // 计算当前迭代到第几代vectorIndividual population;bool found false;for (int i 0; i POPULATION; i ) { // 随机个体population.push_back(Individual(create()));}while (!found) {sort(population.begin(), population.end()); // 按照适应度排序if (population[0].fitness 0) {found true; break;}vectorIndividual new_population;int s (10 * POPULATION) / 100; // 保留精英种子for (int i 0; i s; i ) new_population.push_back(population[i]);s POPULATION - s; // 剩下的随机交配for (int i 0; i s; i ) {int len population.size();Individual p1 population[random(0, 50)];Individual p2 population[random(0, 50)];Individual ch p1.mate(p2);int P random(0, 100);if (P 20) ch.mutation();new_population.push_back(ch);}population new_population;printf(Generation: %d , cnt);cout String : population[0].chromosome ;cout Fitness : population[0].fitness \n; cnt ;}printf(Generation : %d , cnt);cout String : population[0].chromosome ;cout Fitness : population[0].fitness \n; cnt ;return 0;
}
运行结果
Generation: 0 String : !n m fhrd$tI Fitness : 10
Generation: 1 String : E u BoiDiyp Fitness : 9
Generation: 2 String : E u BoiDiyp Fitness : 9
Generation: 3 String : sI] Ptt! Fitness : 8
Generation: 4 String : I u BoiDit5 Fitness : 7
Generation: 5 String : I u BoiDit! Fitness : 6
Generation: 6 String : I u BoiDit! Fitness : 6
Generation: 7 String : I u4 Boi it! Fitness : 5
Generation: 8 String : I ue BoiDit! Fitness : 5
Generation: 9 String : I u4 Bot it! Fitness : 4
Generation: 10 String : I u4 Bot it! Fitness : 4
Generation: 11 String : Iu4 Bot it! Fitness : 3
Generation: 12 String : Iu4 Bot it! Fitness : 3
Generation: 13 String : Iue Bot it! Fitness : 2
Generation: 14 String : Iue eot it! Fitness : 2
Generation: 15 String : Iue Bot it! Fitness : 2
Generation: 16 String : I3e Bot it! Fitness : 2
Generation: 17 String : Iue eot it! Fitness : 2
Generation: 18 String : Iue Bot it! Fitness : 2
Generation: 19 String : Ive Bot it! Fitness : 1
Generation: 20 String : Ive Bot it! Fitness : 1
Generation: 21 String : Ive Bot it! Fitness : 1
Generation : 22 String : Ive got it! Fitness : 0
3.4.2 例题2糖果 题目描述 糖果店的老板一共有 M 种口味的糖果出售。为了方便描述我们将 M 种口味编号 1 ∼ M。 小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果而是 K 颗一包整包出售。 幸好糖果包装上注明了其中 K 颗糖果的口味所以小明可以在买之前就知道每包内的糖果口味。 给定 N 包糖果请你计算小明最少买几包就可以品尝到所有口味的糖果。 输入格式 第一行包含三个整数 N、M 和 K。 接下来 N 行每行 K 这整数 T1,T2,⋯,TK代表一包糖果的口味。 输出格式 一个整数表示答案。如果小明无法品尝所有口味输出 −1。 样例 #1 样例输入 #1 6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2样例输出 #1 2提示 对于 30% 的评测用例1≤N≤20。 对于所有评测样例1≤N≤1001≤M≤201≤K≤201≤Ti≤M。 蓝桥杯 2019 年省赛 A 组 I 题。 这一题是不是很熟悉咧曾经用状态压缩写过请看链接
状态压缩DP-CSDN博客
使用遗传算法样例代码
#include algorithm
#include iostream
#include cstring
#include cstdio
#include vector
#include ctime#define POPULATION 1000
#define TIMES 10using namespace std;const int N 110, M 21;
int a[N][M], n, m, K, ans 0x3f3f3f3f;int random(int l, int r) {return rand() % (r - l 1) l;
}
struct Individual {vectorint p;int fitness;Individual(vectorint p);Individual mate();int calc_fitness();bool operator (const Individual tmp)const {return fitness tmp.fitness;}
};Individual::Individual(vectorint P) {this - p P;this - fitness calc_fitness();
}Individual Individual::mate() {vectorint _p this - p;int P random(0, 3);for (int i 1; i P; i ) {int pos1 random(0, n - 1), pos2 random(0, n - 1);swap(_p[pos1], _p[pos2]);}return _p;
}int Individual::calc_fitness() {int state 0;for (int i 0; i n; i ) {for (int j 0; j K; j )state | (1 a[p[i]][j] - 1);if (state (1 m) - 1) return i 1;}puts(-1); exit(0);
}int main() {scanf(%d%d%d, n, m, K);for (int i 0; i n; i )for (int j 0; j K; j )scanf(%d, a[i][j]);vectorIndividual population; vectorint P;for (int i 0; i n; i ) P.push_back(i);for (int i 1; i POPULATION; i ) {random_shuffle(P.begin(), P.end());population.push_back(Individual(P));}for (int i 0; i TIMES; i ) {sort(population.begin(), population.end());ans min(ans, population[0].fitness);vectorIndividual new_population;int s (10 * POPULATION) / 100;for (int i 0; i s; i )new_population.push_back(population[i]);s POPULATION - s;for (int i 0; i s; i ) {Individual p population[random(0, 50)];new_population.push_back(p.mate());}population new_population;}printf(%d\n, ans);return 0;
}当然遗传算法还可以用到寻路问题8数码问题囚犯困境动作控制找圆心问题在一个不规则的多边形中寻找一个包含在该多边形内的最大圆圈的圆心TSP问题生产调度问题人工生命模拟等问题这里不再展开。
当然遗传算法的实现还有其他方式鉴于这是入门篇不再深入实现其他方法日后可以再做研究。 以上遗传算法入门笔记
祝好
