算法为王系列文章，涵盖了计算机算法，数据挖掘(机器学习)算法，统计算法，金融算法等的多种跨学科算法组合。在大数据时代的背景下，算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国，就像Google。 算法为王的时代正式到来…. 关于作者： 张丹(Conan), 程序员Java,R,PHP,Javascript weibo：@Conan_Z blog: http://blog.fens.me email: bsspirit@gmail.com 转载请注明出处： http://blog.fens.me/algorithm-ga-r/ 前言 人类总是在生活中摸索规律，把规律总结为经验，再把经验传给后人，让后人发现更多的规规律，每一次知识的传递都是一次进化的过程，最终会形成了人类的智慧。自然界规律，让人类适者生存地活了下来，聪明的科学家又把生物进化的规律，总结成遗传算法，扩展到了更广的领域中。 本文将带你走进遗传算法的世界。 目录 遗传算法介绍 遗传算法原理 遗传算法R语言实现 1. 遗传算法介绍 遗传算法是一种解决最优化的搜索算法，是进化算法的一种。进化算法最初借鉴了达尔文的进化论和孟德尔的遗传学说，从生物进化的一些现象发展起来，这些现象包括遗传、基因突变、自然选择和杂交等。遗传算法通过模仿自然界生物进化机制，发展出了随机全局搜索和优化的方法。遗传算法其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程，计算出全局最优解。 遗传算法的操作使用适者生存的原则，在潜在的种群中逐次产生一个近似最优解的方案，在每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程会导致种群中个体的进化，得到的新个体比原来个体更能适应环境，就像自然界中的改造一样。 如果从生物进化的角度，我们可以这样理解。在一个种群中，个体数量已经有一定规模，为了进化发展，通过选择和繁殖产生下一代的个体，其中繁殖过程包括交配和突变。根据适者生存的原则，选择过程会根据新个体的适应度进行保留或淘汰，但也不是完全以适应度高低作为导向，如果单纯选择适应度高的个体可能会产生局部最优的种群，而非全局最优，这个种群将不会再进化，称为早熟。之后，通过繁殖过程，让个体两两交配产生下一代新个体，上一代个体中优秀的基因会保留给下一代，而劣制的基因将被个体另一半的基因所代替。最后，通过小概率事件发生基因突变，通过突变产生新的下一代个体，实现种群的变异进化。 经过这一系列的选择、交配和突变的过程，产生的新一代个体将不同于初始的一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个个体被评价，计算出适应度，两个个体交配，然后突变，产生第三代。周而复始，直到终止条件满足为止。 遗传算法需要注意的问题： 遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。 初始种群的数量很重要，如果初始种群数量过多，算法会占用大量系统资源；如果初始种群数量过少，算法很可能忽略掉最优解。 对于每个解，一般根据实际情况进行编码，这样有利于编写变异函数和适应度函数。 在编码过的遗传算法中，每次变异的编码长度也影响到遗传算法的效率。如果变异代码长度过长，变异的多样性会受到限制；如果变异代码过短，变异的效率会非常低下，选择适当的变异长度是提高效率的关键。 变异率是一个重要的参数。 对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地收敛，而对以后变化了的数据不再产生变化。对于这个问题，研究者提出了一些方法增加基因的多样性，从而防止过早的收敛。其中一种是所谓触發式超级变异，就是当染色体群体的质量下降（彼此的区别减少）时增加变异概率；另一种叫随机外来染色体，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。 选择过程很重要，但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要，因为变异仅仅是保证不丢失某些可能的解；而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新，对于初期的种群来说，交叉几乎等效于一个非常大的变异率，而这么大的变异很可能影响进化过程。 遗传算法很快就能找到良好的解，即使是在很复杂的解空间中。 遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。所以在使用遗传算法的同时，也可以尝试其他算法，互相补充，甚至根本不用遗传算法。 遗传算法不能解决那些“大海捞针”的问题，所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题，使得算法的进化失去导向。 对于任何一个具体的优化问题，调节遗传算法的参数可能会有利于更好的更快的收敛，这些参数包括个体数目、交叉率和变异率。例如太大的变异率会导致丢失最优解，而过小的变异率会导致算法过早的收敛于局部最优点。对于这些参数的选择，现在还没有实用的上下限。 适应度函数对于算法的速度和效果也很重要。 遗传算法的应用领域包括计算机自动设计、生产调度、电路设计、游戏设计、机器人学习、模糊控制、时间表安排，神经网络训练等。然而，我准备把遗传算法到金融领域，比如回测系统的参数寻优方案，我会在以后的文章中，介绍有关金融解决方案。 2. 遗传算法原理 在遗传算法里，优化问题的解是被称为个体，它表示为一个变量序列，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，也有其他表示法，这一过程称为编码。首先要创建种群，算法随机生成一定数量的个体，有时候也可以人工干预这个过程进行，以提高初始种群的质量。在每一代中，每一个个体都被评价，并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序，适应度高的在前面。 接下来，是产生下一代个体的种群，通过选择过程和繁殖过程完成。 选择过程，是根据新个体的适应度进行的，但同时并不意味着完全的以适应度高低作为导向，因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解，我们称之为早熟。作为折中，遗传算法依据原则：适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。 繁殖过程，表示被选择的个体进入交配过程，包括交配(crossover)和突变(mutation)，交配对应算法中的交叉操作。一般的遗传算法都有一个交配概率，范围一般是0.6~1，这个交配概率反映两个被选中的个体进行交配的概率。 例如，交配概率为0.8，则80%的“夫妻”个体会生育后代。每两个个体通过交配产生两个新个体，代替原来的“老”个体，而不交配的个体则保持不变。交配过程，父母的染色体相互交換，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里指的半段並不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意位置。 突变过程，表示通过突变产生新的下一代个体。一般遗传算法都有一个固定的突变常数，又称为变异概率，通常是0.1或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的突变，通常就是改变染色体的一个字节（0变到1，或者1变到0）。 遗传算法实现将不断的重复这个过程：每个个体被评价，计算出适应度，两个个体交配，然后突变，产生下一代，直到终止条件满足为止。一般终止条件有以下几种： 进化次数限制 计算耗费的资源限制，如计算时间、计算占用的CPU，内存等 个体已经满足最优值的条件，即最优值已经找到 当适应度已经达到饱和，继续进化不会产生适应度更好的个体 人为干预 算法实现原理： 1. 创建初始种群 …
Read more →