遗传算法的简单应用

作者: 赫尔特 | 来源:发表于2019-12-24 20:06 被阅读0次

遗传算法采用概率化的寻优方法，在大范围内对解进行优化，不限于局部。遗传算法擅长解决全局最优化问题。
基本过程可以是：
（1）随机产生第一代个体
（2）计算第一代个体的适应度
（3）循环（达到某个条件跳出）
$1^0根据适应度从这一代中挑选下一代的父母$
$2^0杂交产生下一代$
$3^0新一代个体发生基因突变$
$4^0计算新一代个体的适应度$

下面的这个例子用遗传算法产生指定的字符串“nino is beautiful”

#include<iostream>
#include<vector>
#include<string>
#include<time.h>
#include<algorithm>
using namespace std;
const int population_size = 100;
const string genes = " zxcvbnmasdfghjklqwertyuiop"
"ZXCVBNMASDFGHJKLQWERTYUIOP1234567890";
const string target = "nino is beautiful";
//产生随机数
int random_num(int start, int end)
{
    int range = (end - start) + 1;
    int random_int = start + (rand() % range);
    return random_int;
}

//产生随机基因,在变异中使用
char mutated_genes()
{
    int len = genes.size();
int r = random_num(0, len - 1);
return genes[r];
}

//产生染色体（由基因组成）
string create_gnome()
{
    int len = target.size();
    string gnome = "";
    for (int i = 0; i < len; ++i) {
        gnome += mutated_genes();
    }
    return gnome;
}

//用一个类来代表一个个体
class Individual
{
public:
    string chromosome;
    int fitness;
    Individual(string chromosome);
    Individual mate(Individual parent2);
    int cal_fitness();
};
Individual::Individual(string _chromosome)
{
    this->chromosome = _chromosome;
    fitness = cal_fitness();
}

//模仿杂交，产生新个体
Individual Individual::mate(Individual parent2)
{
    string child_chromosome = ""; //代表孩子
    int len = chromosome.size();
    for (int i = 0; i < len; ++i) {
        float p = random_num(0, 100) / 100;
        //有0.45的概率插入第一个亲代（爸爸）的基因
        if (p < 0.45)
            child_chromosome += chromosome[i];
        //有0.45的概率插入第二个亲代（妈妈）的基因
        else if (p < 0.9)
            child_chromosome += parent2.chromosome[i];
        //剩下0.1的概率用来基因突变
        else
            child_chromosome += mutated_genes();
    }
    return Individual(child_chromosome);
}
//计算适应度（分数）
int Individual::cal_fitness()
{
    int len = target.size();
    int fitness = 0;
    for (int i = 0; i < len; ++i) {
        if (chromosome[i] != target[i])
            ++fitness;
    }
    return fitness;
}

//重载<运算符，用于sort函数
bool operator <(const Individual&ind1,const Individual&ind2)
{
    return ind1.fitness < ind2.fitness;
}

int main()
{
    srand((unsigned)time(0));
    int generation = 0;

    vector<Individual>population;
    bool found = false;

    //初始化第一代
    for (int i = 0; i < population_size; ++i) {
        string gnome = create_gnome();
        population.push_back(Individual(gnome));
    }

    while (!found) {
        //将适应度（分数）升序排列
        sort(population.begin(), population.end());
        if (population[0].fitness <= 0) {
            found = true;
            break;
        }
        vector<Individual> new_generaton;
        //保留前十个优秀的个体，让他们直接进入第二代
        int s = (10 * population_size) / 100;
        for (int i = 0; i < s; ++i)
            new_generaton.push_back(population[i]);
    //把第一代的前50%用来杂交(包括刚才的前10)
        s = (90 * population_size) / 100;
        for (int i = 0; i < s; ++i) {
            int len = population.size();
            int r = random_num(0, 50);
            Individual parent1 = population[r];
            r = random_num(0, 50);
            Individual parent2 = population[r];
            Individual offspring = parent1.mate(parent2);
            new_generaton.push_back(offspring);
        }
        population = new_generaton;
        ++generation;
        cout << "Generation: " << generation << "\t";
        cout << "String: " << population[0].chromosome << "\t";
        cout << "Fitness: " << population[0].fitness << "\n";
    }
    cout << "Generation: " << generation+1 << "\t";
    cout << "String: " << population[0].chromosome << "\t";
    cout << "Fitness: " << population[0].fitness << "\n";
    return 0;
}

应用2（寻找最短路径）：
小曾同学要去某城市旅游，该城市有5个景点需要参观，分别为A,B,C,D,E,小曾从酒店出发，最后要回到酒店，每个景点必须要走且只走一遍，景点间的距离（0-酒店,1-A,2-B...）如下表，求最短路径。

在这里插入图片描述

应用遗传算法，随机创建100条路径可重复，然后让他们演化到稳定，得出最短路径（概率最大）

#include<iostream>
#include<vector>
#include<string>
#include<time.h>
#include<algorithm>
using namespace std;
const int population_size = 100;
const string genes = "ABCDE";
vector<vector<int>>distances{ {0,482,424,138,458},
{482,0,158,522,179},{424,158,0,438,303},{138,522,438,0,518},
{458,179,303,518,0}};
vector<int>distance_fromstart{ 258,264,319,367,164 };
//产生随机数
int random_num(int start, int end)
{
    int range = (end - start) + 1;
    int random_int = start + (rand() % range);
    return random_int;
}

//产生随机基因,在基因突变中使用
char mutated_genes()
{
    int len = genes.size();
    int r = random_num(0, len - 1);
    return genes[r];
}
//因为输入可以保证前面的字符串肯定没有重复，所以只要检查最后一个字符即可
bool isrepeatstr(string str)
{
    int len = str.size();
    for (int i = 0; i < len-1; ++i) {
        if (str[len - 1] == str[i])
            return true;
    }
    return false;
}
//第一代的随机产生染色体（由基因组成）
string create_gnome()
{
    int len = genes.size();
    string gnome = "";
    for (int i = 0; i < len; ++i) {
        gnome += mutated_genes();
        while (isrepeatstr(gnome) == true)
            gnome.back() = mutated_genes();
    }
    return gnome;
}

//用一个类来代表一个个体
class Individual
{
public:
    string chromosome;
    int fitness;
    Individual(string chromosome);
    Individual mate(Individual parent2);
    int cal_fitness();
};
Individual::Individual(string _chromosome)
{
    this->chromosome = _chromosome;
    fitness = cal_fitness();
}

//模仿杂交，产生新个体
Individual Individual::mate(Individual parent2)
{
    string child_chromosome = ""; //代表孩子
    int len = chromosome.size();
    for (int i = 0; i < len; ++i) {
        float p = random_num(0, 100) / 100;
        //有0.45的概率插入第一个亲代（爸爸）的基因
        if (p < 0.45)
            child_chromosome += chromosome[i];
        //有0.45的概率插入第二个亲代（妈妈）的基因
        else if (p < 0.9)
            child_chromosome += parent2.chromosome[i];
        //剩下0.1的概率用来基因突变
        else
            child_chromosome += mutated_genes();
    }
    return Individual(child_chromosome);
}
//计算适应度（分数）
int Individual::cal_fitness()
{
    int len = genes.size();
    for (int i = 0; i < len; ++i) {
        for (int j = i+1; j < len; ++j) {
            if (chromosome[i] == chromosome[j])
                return 10000;
        }
    }
    int fitness = 0;
    fitness += distance_fromstart[chromosome[0] - 'A'];
    for (int i = 1; i < len; ++i) {
        fitness += distances[(chromosome[i] - 'A')][(chromosome[i - 1] - 'A')];
    }
    fitness += distance_fromstart[chromosome[len - 1] - 'A'];
    return fitness;
}

//重载<运算符，用于sort函数
bool operator <(const Individual& ind1, const Individual& ind2)
{
    return ind1.fitness < ind2.fitness;
}

int main()
{
    srand((unsigned)time(0));
    int generation = 0;

    vector<Individual>population;
    bool found = false;
    //初始化第一代
    for (int i = 0; i < population_size; ++i) {
        string gnome = create_gnome();
        population.push_back(Individual(gnome));
    }

    while (!found) {
        //将适应度（分数）升序排列
        sort(population.begin(), population.end());
        if (generation>10000) {
            found = true;
            break;
        } 
        vector<Individual> new_generaton;
        //保留前十个优秀的个体，让他们直接进入第二代
        int s = (10 * population_size) / 100;
        for (int i = 0; i < s; ++i)
            new_generaton.push_back(population[i]);
        //把第一代的前50%用来杂交(包括刚才的前10)
        s = (90 * population_size) / 100;
        for (int i = 0; i < s; ++i) {
            int len = population.size();
            int r = random_num(0, 50);
            Individual parent1 = population[r];
            r = random_num(0, 50);
            Individual parent2 = population[r];
            Individual offspring = parent1.mate(parent2);
            new_generaton.push_back(offspring);
        }
        population = new_generaton;
        ++generation;
        cout << "Generation: " << generation << "\t";
        cout << "String: " << population[0].chromosome << "\t";
        cout << "Fitness: " << population[0].fitness << "\n";
    }
    return 0;
}

还有多元不定方程求正整数解问题，也可以用遗传算法解决。

Reference:GEEKSFORGEEKS

遗传算法的简单应用

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员