遗传算法 1.前言
遗传算法是一种基于生物界自然群体遗传进化机制的自适应全局优化概率搜索算法。它与传统算法不同,不依赖梯度信息,而是通过模拟自然进化过程来搜索最优解。
例子:兔子的遗传进化
有人说,现代医学阻碍了人类的进化?你怎么看?
2.发展历程遗传算法由密歇根大学的约翰·霍兰德和他的同事于二十世纪六十年代在对细胞自动机(英文:cellular automata)进行研究时率先提出。在二十世纪八十年代中期之前,对于遗传算法的研究还仅仅限于理论方面,直到在匹兹堡召开了第一届世界遗传算法大会。随着计算机计算能力的发展和实际应用需求的增多,遗传算法逐渐进入实际应用阶段。1989年,纽约时报作者约翰·马科夫写了一篇文章描述第一个商业用途的遗传算法--进化者(英文:Evolver)。之后,越来越多种类的遗传算法出现并被用于许多领域中,财富杂志500强企业中大多数都用它进行时间表安排、数据分析、未来趋势预测、预算、以及解决很多其他组合优化问题。
3.应用领域 4.适用问题全局最优化问题(用其他优化方法较难求解,通常选择GA和LINGO)
5.算法详解刚才说到了遗传算法的来源与基础,下面我们来具体说一说生物进化与遗传算法名词的对应关系。
5.1 对应关系生物进化
遗传算法
环境
适应函数
适者生存
适应函数值最大的解被保留的概率最大
个体
问题的一个解
染色体
解的编码
基因
编码的元素
种群
根据适应函数选择的一组解
交叉(交配)
以一定的方式由双亲产生后代的过程
变异
编码的某些分量发生变化的过程
了解了上面的对应关系之后,我们再一起来看遗传算法究竟是怎么实现的。
5.2 算法思想遗传算法是从代表问题可能潜在解集的一个种群(population)
开始的,而一个种群则由经过基因编码(coding)的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。为了简化,往往采用二进制编码。对种群反复进行选择(selection)、交叉(crossover)、变异(mutation)操作,估计各个体的适应值(fitness),根据”适者生存、优胜劣汰”的进化规则,产生最好的种群,使适应性好的个体比适应性差的个体有更多的繁殖机会。最后把末代种群中的最优个体经过解码(decoding),可以获得满足要求的最优解。
5.3流程图描述 5.4 伪代码描述(1) 随机产生初始种群;
(2) 计算种群体中每个个体的适应度值,判断是否满足停
止条件,若不满足,则转第(3)步,否则转第(7)步;
(3) 按由个体适应值所决定的某个规则选择将进入下一代
的个体;
(4) 按交叉概率Pc进行交叉操作,生产新的个体;
(5) 按变异概率Pm进行变异操作,生产新的个体;
(6) 输出种群中适应度值最优的染色体作为问题的满意解
或最优解。
Ø 具体讲解
遗传算法的具体实现
问题
如何进行编码?
如何产生初始种群?
如何定义适应函数?
如何进行遗传操作(复制、交叉、变异)?
如何产生下一代种群?
如何定义停止准则?
6.例题解析 6.1 例1:求解多变量多约束非线性规划问题求解以下问题的解
函数图像: