利用遗传算法求解函数
f(x,y)=1/(x2+y2+1),x,y∈[−5,5]f(x,y)=1/(x^2+y^2+1),x,y\in[-5,5]f(x,y)=1/(x2+y2+1),x,y∈[−5,5]的最大值。
显然答案为1。
代码:
/** @author: codancer* @createTime: -11-28, 21:58:25*/#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>#include <vector>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <queue>#include <ctime>#include <cassert>#include <complex>#include <string>#include <cstring>#include <chrono>#include <random>#include <bitset>using namespace std;typedef long long ll;typedef unsigned long long ull;const ll mod = 1e9+7;#define pb push_back#define fi first#define se second#define SZ(x) ((int)(x).size())#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define fep(i,a,b) for(int i=(a);i>=(b);i--)#define deb(x) cerr<<#x<<" = "<<(x)<<"\n"typedef vector<int> VI;typedef vector<ll> VII;typedef pair<int,int> pii;mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());ll Rand(ll B) {return (ull)rng() % B;}/*由于精度为15位，因此需要10^16个种群需要2^54，二进制需要54位*/const int M = 100;//种群个数const int D = 54;vector<pair<string,string>> person;//个体/*将基因id换成小数*/double trans(string s){ll ans=0;for(char c:s){ans=ans*2+c-'0';}return -5+ans*10.0/((1LL<<D)-1);}/*随机产生M个种群成员*/void Gen(){for(int i=0;i<M;i++){string a="";string b="";for(int j=0;j<D;j++) a+=Rand(2)==0?'0':'1';for(int j=0;j<D;j++) b+=Rand(2)==0?'0':'1';person.pb({a,b});}}/*基因评估*/double eval(pair<string,string> a){double x1=trans(a.first);double x2=trans(a.second);return 1.0/(x1*x1+x2*x2+1);}/*遗传算法*/void Genetic(){double ans=-1e9;//最大值初始化/*不断迭代*/for(int steps=1;steps<=1000;steps++){vector<double> v(M),p(M);double F=0;//种群适度值之和for(int i=0;i<M;i++){v[i]=eval(person[i]);//v[i]是每个个体的评估值ans=max(ans,v[i]);//每一轮更新最大值F+=v[i];p[i]=v[i]/F;//p[i]代表i被选择的概率}/*模拟轮盘赌，q[i]代表个体i的累积概率*/vector<double> q(M);vector<int> cnt(M,0);//每个个体被选择的次数q[0]=p[0];for(int i=1;i<M;i++){q[i]=q[i-1]+p[i];}for(int i=0;i<M;i++){double r=1.0*Rand(100)/100.0;//随机一个[0,1]的小数for(int j=0;j<M;j++){if(r<=q[j]){++cnt[j];break;//选择一次j}}}vector<pair<string,string> > next_gen;//下一代for(int i=0;i<M;i++){for(int j=0;j<cnt[i];j++) next_gen.pb(person[i]);}/*单点交叉,交叉率为0.8*/for(int i=0;i<M;i+=2){double r=Rand(10)/10.0;//交叉概率<=0.8则不交叉if(r>0.8) continue;int dig=Rand(2*D);//随机交叉位数if(dig<D) swap(next_gen[i].first[dig],next_gen[i+1].first[dig]);//交叉第digit位else swap(next_gen[i].second[dig-D],next_gen[i].second[dig-D]);}/*单点变异,变异率0.1*/for(int i=0;i<M;i++){for(int j=0;j<D;j++){double r=Rand(10)/10.0;if(r<=0.1) next_gen[i].first[j]='0'+!(next_gen[i].first[j]-'0');//变异取反}for(int j=0;j<D;j++){double r=Rand(10)/10.0;if(r<=0.1) next_gen[i].second[j]='0'+!(next_gen[i].second[j]-'0');//变异取反}}for(int i=0;i<M;i++) person[i]=next_gen[i];//换代printf("第%d代 的最大值为: %.15lf\n", steps,ans);}}int main(){Gen();Genetic();return 0;}
