遗传算法 ( GA , Genetic Algorithm ) ,也称进化算法 。 遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识。
一.进化论知识
作为遗传算法生物背景的介绍,下面内容了解即可:
种群
(Population)
:
生物的进化以群体的形式进行,这样的一个群体称为种群。
个体
:组成种群的单个生物。
基因
( Gene )
:
一个遗传因子。
染色体
( Chromosome )
:包含一组的基因。
生存竞争,适者生存
:对环境适应度高的、牛B的个体参与繁殖的机会比较多,后代就会越来越多。适应度低的个体参与繁殖的机会比较少,后代就会越来越少。
遗传与变异
:新个体会遗传父母双方各一部分的基因,同时有一定的概率发生基因变异。
简单说来就是:繁殖过程,会发生基因交叉( Crossover )
,基因突变 ( Mutation ) ,适应度( Fitness
)低的个体会被逐步淘汰,而适应度高的个体会越来越多。那么经过N代的自然选择后,保存下来的个体都是适应度很高的,其中很可能包含史上产生的适应度最高
的那个个体。
二.遗传算法思想
借鉴生物进化论,遗传算法将要解决的问题模拟成一个生物进化的过程,通过复制、交叉、突变等操作产生下一代的解,并逐步淘汰掉适应。
下面是一个根据遗传算法的思想写出来的简单例子。
人类种群分为,男人和女人,男人是奇数,女人是偶数,每个人都有一个智商值(代码里为num)。男人会分裂成两个染色体X (奇数)和Y(偶数),女人也会分裂成两个染色体X(偶数)和X(偶数)。在染色体分裂的过程中会有一定几率(这里几率为0.25)基因突变(这里是值加2)。然后男人的一个染色体和女人的一个染色体结合产生后代。
产生的后代也有智商值,那些智商值低的个体将不会生存下来(适者生存),这里有一个适应度函数来模拟适者生存。
最后看产生的后代是否智商达到100,达到了100就结束繁殖。
代码如下:
import java.util.ArrayList;
import java.util.List;
//遗传算法
public class GA {
//男人是奇数,女人是偶数
List<human> manPop = new ArrayList<human>();
List<human> womanPop = new ArrayList<human>();
double Pm = 0.25; //变异发生的概率
int score = 100;
public GA(human man ,human woman){
manPop.add(man);
womanPop.add(woman);
}
//种群(Population)
public Boolean Population(){
int num = manPop.size()<womanPop.size()?manPop.size():womanPop.size();
for(int i = 0; i < num;i++){
boby(manPop.get(i),womanPop.get(i));
}
//适者生存,淘汰最差的
manPop = Fitness(manPop);
womanPop = Fitness(womanPop);
//得到需要的后代后停止
if(check(manPop)||check(womanPop)){
return true;
}else{
return false;
}
}
private void boby(human m,human w){
//染色体分裂
split(m);
split(w);
//组合
human newhuman = new human(m.getA() + w.getA());
if( newhuman.getNum() % 2 != 0){//产生的是男人,放到男人种群
manPop.add(newhuman);
}else{ //产生的是女人,放到女人种群
womanPop.add(newhuman);
}
newhuman = new human(m.getA() + w.getB());
if( newhuman.getNum() % 2 != 0){//产生的是男人,放到男人种群
manPop.add(newhuman);
}else{ //产生的是女人,放到女人种群
womanPop.add(newhuman);
}
newhuman = new human(m.getB() + w.getA());
if( newhuman.getNum() % 2 != 0){//产生的是男人,放到男人种群
manPop.add(newhuman);
}else{ //产生的是女人,放到女人种群
womanPop.add(newhuman);
}
newhuman = new human(m.getB() + w.getB());
if( newhuman.getNum() % 2 == 0){//产生的是男人,放到男人种群
manPop.add(newhuman);
}else{ //产生的是女人,放到女人种群
womanPop.add(newhuman);
}
}
//染色体分裂,男人分裂为X Y,女人分裂为 X1 X2
private human split(human h){
//男人
if(h.getNum() % 2 != 0){
h.setA(h.getNum()/2);
h.setB(h.getNum() - (h.getNum()/2));
}else{//女人
int temp = h.getNum()/2;
if(temp % 2 != 0){
temp = temp + 1;
}
h.setA(temp);
h.setB(h.getNum() - temp);
}
//染色体变异(基因突变)
h.setA(Mutation(h.getA()));
h.setB(Mutation(h.getB()));
h.setDeadStatus(1);
return h;
}
//变异(Mutation):在繁殖过程,新产生的染色体中的基因会以一定的概率出错,称为变异。变异发生的概率记为Pm
private int Mutation(int a){
if(Math.random()<Pm){ //变异有一定概率发生
return a = a + 2;
}else{
return a;
}
}
//适应度函数 ( Fitness Function ) 适者生存,将不适应的个体淘汰掉
private List<human> Fitness(List<human> pop){
//新的种群
List<human> newPop = new ArrayList<human>();
pop = StayMax(pop);
for(human h:pop){
if(h.getDeadStatus() == 0){
newPop.add(h);
}
}
return newPop;
}
//淘汰算法(只要num最大的)
private List<human> StayMax(List<human> pop){
//只要最大num的
int max = pop.get(0).getNum();
int maxId = 0;
for(int i = 0; i < pop.size();i++){
human h = pop.get(i);
if(h.getDeadStatus() == 0&&h.getNum() > max){
max = h.getNum();
maxId = i;
}
pop.get(i).setDeadStatus(1);
}
pop.get(maxId).setDeadStatus(0); //最大的留下
return pop;
}
//去掉最小的,其他留下。
private List<human> RemoveMin(List<human> pop){
//去掉
int min = pop.get(0).getNum();
int minId = 0;
for(int i = 0; i < pop.size();i++){
human h = pop.get(i);
if(h.getDeadStatus() == 0&&h.getNum() < min){
min = h.getNum();
minId = i;
}
}
pop.get(minId).setDeadStatus(1); //最小的被淘汰
return pop;
}
//
public Boolean check(List<human> pop){
for(human h:pop){
if(h.getNum() >= score){
return true;
}
}
return false;
}
public void Print(){
for(human h:manPop){
if(h.getDeadStatus() == 0){
System.out.println(h.getNum());
}
}
for(human h:womanPop){
if(h.getDeadStatus() == 0){
System.out.println(h.getNum());
}
}
}
public static void main(String[] args) {
GA ga = new GA(new human(1),new human(2));
for(int i = 1;i < 1000000;i++){
if(ga.Population()){
System.out.println("第"+i+"代满足条件");
ga.Print();
break;
}
}
}
}
//一个人有两条性染色体,X Y 或者 X X
class human{
private int num;
private int a;
private int b;
private int deadStatus = 0; //当为0时,表示个体死亡,被淘汰.
public int getDeadStatus() {
return deadStatus;
}
public void setDeadStatus(int deadStatus) {
this.deadStatus = deadStatus;
}
public human(int num){
this.num = num;
}
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public int getA() {
return a;
}
public void setA(int a) {
this.a = a;
}
public int getB() {
return b;
}
public void setB(int b) {
this.b = b;
}
}
分享到:
相关推荐
关于遗传算法的收敛性关于遗传算法的收敛性关于遗传算法的收敛性
自己收集的一些关于遗传算法的资料,包括遗传算法工具箱,还有一些很好的论文,文档,源代码等
这是一个有关于遗传算法的资料教程 为杭电 数学建模 学习培训内部资料 主要内容:遗传算法与模拟退火算法
关于遗传算法的构想关于遗传算法的构想关于遗传算法的构想关于遗传算法的构想关于遗传算法的构想
IEEE最新的关于遗传算法的论文,很值得拥有
此程序是关于遗传算法的,是c++语言编写,
这是关于遗传算法的最短路径问题,c++编写的
关于遗传算法在云计算环境下应用的有关问题,是一种协同进化理论的算法
MATLAB关于遗传算法的所有源程序祥解.rar MATLAB关于遗传算法的所有源程序祥解.rar
遗传算法课件:详细介绍了遗传算法的理论基础和应用。复制,遗传和变异实现方法。
关于遗传算法应用的一些参考文献
关于遗传算法的实验报告.pdf
关于遗传算法的中国股市波动性研究,主要讲述怎么用遗传算法研究中国股市
该文章主要先对遗传算法进行简单的介绍,使读者对其有初步的了解。之后通过举一些例子来加深读者理解
关于遗传算法的实验报告.doc
找到了一些遗传算法的资料,感兴趣的可以看看!
基于遗传算法的背包问题,一般背包问题都是用动态规化或是贪心算法来解。这个是用遗传算法解决的程序。。。
关于遗传算法应用的一些参考文献.zip
关于遗传算法在组卷中的研究.pdf
包含了大量matlab关于遗传算法的源程序,有代码,有详细注释