遗传算法(Genetic Algorithm,GA)最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
遗传算法流程图
以上的内容是从百度百科复制来的。
我写的代码参考了上面的流程但有些不同,主要利用了其中遗传进化和随机的思想。
图片来自网络
!这就是随机的力量。
对于优化问题,利用遗传进化可以有方向性地搜索局部最优解,但可能陷入死胡同,找不到全局最优解。加上一点随机,就更有可能搜索到全局最优解。注意一点,遗传算法不保证一定能找到全局最优的精确解。
要利用遗传进化的思想,就需要把解空间中的所有点(候选解)通过编码映射到遗传空间的基因图谱,每组候选解一一对应一张基因图。当然,如果求解域是连续性的,只能将求解域离散,求得近似解。有各种各样的编码方式。
代码中用 M 行 N 列的二维数组表示一张基因图。每一个基因点(数组元素)有K种取值变化,则总共可以表示 K^(M*N) 张不同的基因图。
这样解空间就得有K^(M*N)个候选解与之对应。
f(x,y) =100.112 - (x - 3) * (x - 3) - (y - 5) * (y - 5)
对于代码中这种二元连续函数求最大值问题(求最小值的问题,可以通过取反转化为最大值问题),就可以将解空间离散成 K^(M*N) 个栅格,每个栅格代表一个候选解。不妨K^(M*N) 拆成 K^m 和 K^n 的乘积 ,m 取 M*N 整除2的结果,n 则取 M*N-m。至此将 x 定义域均分成了 K^m 份,将 y 定义域均分成了 K^n 份。3 元函数优化问题则将 K^(M*N) 拆成3份,依次类推。
下面是源代码:
// 遗传算法二元.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
// my 2nd 遗传算法
#include <math.h>
#include <array>
#include<vector>
#include <random>
#include <iostream>
using std::array, std::cout, std::endl, std::vector;
//算法依赖于C++ long double的精度,K的(M*N)次方不能大到有精度损失
constexpr int K = 3; //每个基因点的可变类型有多少种,越大则父代性状越难遗传给子代,宜取2~4,
constexpr int M = 6; // 个体染色体数// 每个个体用 M * N个元素,元素值为0 ~ K-1的数组表示
constexpr int N = 6; //每个染色体上的基因点数
constexpr int Qty = 1000; // 种群大小
constexpr double reserve_rate = 0.05; //直接免考复制到下一代的精英个体的比率
constexpr double elamilation_rate = 0.25; //末位淘汰率
constexpr int Iteral_num = 100; //迭代的代数
// 定义域(搜索范围)
constexpr double LSL_x = -6;
constexpr double USL_x = 20;
constexpr double LSL_y = -1;
constexpr double USL_y = 22;
//求最大值,如果是求最小值要取反
double f(vector<double>& x_y)
{
double x = x_y[0];
double y = x_y[1];
//return x + 10 * sin(5 * x) + 7 * cos(4 * x);
return 100.112 - (x - 3) * (x - 3) - (y - 5) * (y - 5);// +sin(x * y);
}
//约束方程在这里写!
bool g(vector<double>& x_y)
{
double x = x_y[0];
double y = x_y[1];
double c1 = x * x - 2 * y;
double c2 = x - y;
//c1 = 1.0;
//c2 = 1.0;
return c1 > 0 and c2 > 0;
}
array<array<int, N>, M> generate_rand_individuality()
{
std::random_device rd;
std::default_random_engine eng(rd());
std::uniform_int_distribution<int> distr(0, K - 1);//生成0到K-1的之间的平均分布的随机整数
array<array<int, N>, M> I{};
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
I[i][j] = distr(eng);
}
}
return I;
}
//打印基因
std::ostream& operator<<(std::ostream& out, const array<array<int, N>, M>& I)
{
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N - 1; j++)
{
out << I[i][j] << ',';
}
out << I[i][N - 1] << '\n';
}
return out;
}
long double count(const array<array<int, N>, M>& I)
{
//数出传入的基因是第几种基因(基因ID),总共有K的(MXN)次方种
long double sum = 0.0L;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
sum += I[i][j] * pow(K, i * N + j);
}
}
return sum;
}
vector<double> decode(const array<array<int, N>, M>& I)
{
long double Id = count(I);//数出传入的基因是第几种基因(基因ID)
//映射回求解域上的一个小栅格内(即一个点(x0,y0))
// 不妨 把x 的 值域分割为 pow(K, m)个区间, 把y 的 值域分割为 pow(K, n)个区间 ,其中m=(M*N)//2, n= M*N - m
// 共有pow(K, M*N)个栅格, 第 row 行第 col 列 (x对应列,y对应行)个格栅对应的基因ID是 row* pow(K,m) + col
// 第 row 行第 col 列个格栅对应的x,y 的值是 LSL_x +(USL_x-LSL_x)*row/(pow(K,m)-1), LSL_y +(USL_y-LSL_y)*col/(pow(K,n)-1)
//将基因ID 逆映射回 row ,col
int m = M * N / 2; // 2 是自变量的个数
int n = M * N - m;
long double pow_K_m = pow(K, m);
long double row = floor(Id / pow_K_m);
long double col = Id - row * pow_K_m;
//cout <<"ID= "<<Id<< ", row= " << row << ", column= " << col << endl;
return { static_cast<double>(LSL_x + (USL_x - LSL_x) * col / (pow_K_m - 1.0)),
static_cast<double>(LSL_y + (USL_y - LSL_y) * row / (pow(K,n) - 1.0)) };
}
double assess(const array<array<int, N>, M>& I) //评估
{
vector<double> x_y = decode(I);
if (g(x_y)) //约束条件检查
return f(x_y);
else // 不满足约束条件的打最低分
return std::numeric_limits<double>::min();
}
array<array<int, N>, M> reproduce(const array<array<int, N>, M>& I1, const array<array<int, N>, M>& I2)
{
//繁衍
std::random_device rd;
std::default_random_engine eng(rd());
std::uniform_int_distribution<int> distr(0, K-1);//生成0到K-1的之间的平均分布的随机整数
array<array<int, N>, M> I{};
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
if (I1[i][j] == I2[i][j]) I[i][j] = I1[i][j]; // 遗传
else I[i][j] = distr(eng); //随机
}
}
return I;
}
struct Grater
{
bool operator()(const array<array<int, N>, M>& I1, const array<array<int, N>, M>& I2)
{
return assess(I1) > assess(I2);
}
};
vector<array<array<int, N>, M>> regroup(const vector<array<array<int, N>, M>>& group)
{
int top_qty = static_cast<int> (reserve_rate * Qty);
int bottom_qty = static_cast<int> (elamilation_rate * Qty);
vector<array<array<int, N>, M>> new_group{ group };
int i = top_qty;
for (int j = 0; j < Qty - bottom_qty; j += 2)
{
//除去淘汰的个体外,每两个个体强强结合,生两个仔...
new_group[i] = reproduce(group[j], group[j + 1]);
new_group[i + 1] = reproduce(group[j], group[j + 1]);
i += 2;
}
//淘汰的个体用随机产生的个体替代掉
for (int i = Qty - bottom_qty; i < Qty; i++)
{
new_group[i] = generate_rand_individuality();
}
return new_group;
}
int main()
{
vector<array<array<int, N>, M>> group{};
for (int i = 0; i < Qty; i++)
{
group.push_back(generate_rand_individuality());
}
std::sort(group.begin(), group.end(), Grater());
// 打印初代评分
//cout << "初代评分:" << endl;
//for (auto& I : group)
//{
// cout << assess(I) << ", ";
// break;//只打印第一名
//}
//cout << endl<<endl;
//迭代
cout << "每代的第一名的得分:" << endl;
for (int i = 0; i < Iteral_num; i++)
{
group = regroup(group);
std::sort(group.begin(), group.end(), Grater());
cout << assess(group.at(0)) << "-> ";
}
cout << endl << endl;
// //打印迭代完成后的评分
//cout << "迭代完成后的评分:" << endl;
//for (auto& I : group)
//{
// cout << assess(I) << ", ";
// break;//只打印第一名
//}
//cout << endl << endl;
cout << "迭代完成后的最优基因是" << endl;
//print_individuality(group.at(0));//打印最优基因
cout << group.at(0) << endl;//打印最优基因
vector<double> x_y = decode(group.at(0));
cout << "求得的x和y的值是" << x_y.at(0) << "," << x_y.at(1) << endl;
cout << "此时对应的函数值是" << f(x_y) << endl;
cout << "std::numeric_limits<double>::min(): " << std::numeric_limits<double>::min() << endl;
cout << "std::numeric_limits<double>::max(): " << std::numeric_limits<double>::max() << endl;
//cout << (1 << 3);
}
本文分享自 Python可视化编程机器学习OpenCV 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!