深入浅出遗传算法

正文

请到「今天看啥」查看全文

遗传算法属于智能优化算法之一。

常用的智能优化算法有：

遗传算法 、模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法。

（本经典算法研究系列，日后将陆续阐述模拟退火算法、粒子群算法、蚁群算法。）

2、遗传算法概述

遗传算法是由美国的J. Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的。

借鉴生物界自然选择和自然遗传机制的随机化搜索算法。

模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象。

在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个

体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

基本遗传算法（Simple Genetic Algorithms，GA)又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。

3、基本遗传算法的组成

（1）编码（产生初始种群）

（2）适应度函数

（3）遗传算子（选择、交叉、变异）

（4）运行参数

接下来，咱们分门别类，分别阐述着基本遗传算法的五个组成部分：

1）编码

遗传算法（GA）通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。

正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。

基本遗传算法（SGA）使用二进制串进行编码。

初始种群：基本遗传算法（SGA）采用随机方法生成若干个个体的集合，该集合称为初始种群。

初始种群中个体的数量称为种群规模。

2）适应度函数

遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。

适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，

它的设计应结合求解问题本身的要求而定。

3.1、选择算子

遗传算法使用选择运算对个体进行优胜劣汰操作。

适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。

选择操作的任务就是从父代群体中选取一些个体，遗传到下一代群体。

基本遗传算法（SGA）中选择算子采用轮盘赌选择方法。

Ok，下面就来看下这个轮盘赌的例子，这个例子通俗易懂，对理解选择算子帮助很大。

轮盘赌选择方法

请到「今天看啥」查看全文